Git 底层原理

在阅读本篇之前, 确保你已经安装好了 Git 并且配置了.gitconfig (邮箱及用户等).

为什么要学习 Git?

动机: 怎么多人协作?

不是像几个人做英语的小组作业那样灾难
- 一个文件被传几遍. 改了什么内容?
- 这段文案是谁改的...? 为啥要改?
- ...

有了版本管理系统(VCS)就能解决大部分上面的问题.

别人都干了些啥?
同步项目
解决并行开发引起的冲突

我不和别人协作!

项目快照
记录改动目的
多分支并行开发

如果愿意, 你也可以用 Git 打造专属自己的一套个人笔记系统!

Git 这么强大, 那要怎么实现 Git?
这是我该问的问题吗?
- 为Git祛魅: Write Yourself a Git! 563 行 Python 代码实现了 Git 的底层机制.

大部分的 Git 教程通常都是自上而下的: 从命令行接口开始, git add/commit/push/fetch/pull...

看起来你学到了很多, 但事实上, 你还是一个接口侠(这也是我们后端最不愿意看到的). 或者, 一旦学深入, 就不得不涉及到一些底层的原理. Git 被人诟病 "leaky abstraction", 就是因为它的接口太过丑陋 (就连Linus 本人也吐槽这一点).

虽然说现代 IDEs (例如Jetbrain, vscode) 已经提供了 Git 图形化的界面, 但是这不妨碍很多人依然不会.

什么是 leaky abstraction 泄露抽象?

简单来说, 抽象层次的不完全封装, 导致底层细节和实现细节对上层抽象产生意外影响或泄漏出来, 这就是泄露抽象.

举一个例子, matching_user(id:int)是你写的一个匹配指定用户的函数, 你只需要传入用户 id 即可完成匹配, 但如果你写成 matching_user(pattern:SQL_query), 这个接口就是泄露抽象的.

作为一名合格的后端人员, 你应当避免泄露抽象的出现.

本次的介绍会从 Git 的底层设计和模型开始讲起.

Git 的后端模型很简洁.
理解一定的原理, 至少能让你在复制命令的时候不会感到一脸茫然.

Git 的底层原理

存储结构

文件内容: Blob 对象 (Binary Large OBject)
对象: 对象按照 SHA1-Hash 寻址
Git 的一切都是对象

不同于传统的文件存储系统: key-value

文件的内容是 value
文件或目录有一个唯一的名称/路径作为 key

你不是修改了文件, 而是在另一个位置新建了文件

文件的内容是 value
根据内容计算一个 hash key, 这个哈希值相当于路径
这就是 Git 的后端模型: 内容寻址文件系统(IPFS) (听起来很吓人)

什么是哈希函数? strlen() 就是一个哈希函数, 你可以知道字符串的长度, 但永远不知道原字符串是长什么样的. 你可以想象哈希函数就是数据的身份证, 它唯一, 并且不可逆. 利用这些特点, SHA-1哈希值就是一个对象的唯一标识符.

示例1: `git hash-object/cat-file`

这个示例中我们会演示两个"底层" (plumbing) 的指令: git hash-object 和 git cat-file. 即便这两个命令在我们日常使用中几乎不会见到, 但是对于我们了解 Git 的底层机制来说是很有用的.

在这个示例中, 一个文本被 hash 化, 同时作为一个新的数据对象被存储进 Git 数据库中(.git/objects/). 然后我们又用 cat-file 取回了原数据.

$ git init git_demo
Initialized empty Git repository in /home/besthope/git_demo/.git/
$ cd git_demo
$ echo 'hello git' | git hash-object -w --stdin
8d0e41234f24b6da002d962a26c2495ea16a425f
$ git cat-file -p 8d0e41234f24b6da002d962a26c2495ea16a425f
hello git

你可能会好奇 hash-object 是怎么做到的. 实际上这并不黑科技, 我们可以用 Python 简单地去实现:

>>> import hashlib
>>> data = 'hello git'
>>> content = f'blob {len(data)}\x00{data}'
>>> content
'blob 9\x00hello git'
>>> hashlib.sha1(content.encode()).hexdigest()
'f09e9c379f5fe8f4ce718641c356df87906d87a6'
>>>
$ echo -n "hello git" | git hash-object --stdin
f09e9c379f5fe8f4ce718641c356df87906d87a6

然后是数据的存储. 这条文本消息会用 zlib 进行压缩, 并写入指定的路径. 用 Python 代码表示就是:

# .git/objects/f0/9e9c379f5fe8f4ce718641c356df87906d87a6
path = repo_file(obj.repo, "objects",
                 sha[0:2], sha[2:])

with open(path, 'wb') as f:
    f.write(zlib.compress(result))

让我们再用实际的一个例子来演示:

$ echo 'version 1' > a.txt
$ git hash-object -w a.txt
83baae61804e65cc73a7201a7252750c76066a30
$ echo 'version 2' > a.txt
$ git hash-object -w a.txt
1f7a7a472abf3dd9643fd615f6da379c4acb3e3a

$ find .git/objects -type f
.git/objects/1f/7a7a472abf3dd9643fd615f6da379c4acb3e3a
.git/objects/83/baae61804e65cc73a7201a7252750c76066a30

$ git cat-file -p 83baae61804e65cc73a7201a7252750c76066a30 > a.txt
$ cat a.txt
version 1

这就已经是一个简单的版本控制系统了! 并且我们看到了, 在Git版本控制系统中, 文件都以对象存储. 但是这种方法有一个问题: 文件名, 以及文件所在的路径的信息并没有被保存. 为了解决这个问题, 于是引入了树对象 (tree object):

一棵树可以包含其它树, 以及文件. (树是递归定义的!)
树将文件名和 hash 值进行了关联. 正如下图所示:

历史记录

接下来介绍的提交(Commit), 可能是Git中最重要的一个概念. 但有了上面的基础, 它很好理解:

实际上就是一棵树, 附带一些其它信息, 例如提交者, 提交时间, 它的父提交等.
一次提交, 就是当前项目的一次快照(Snapshot).

示例 2: Object Walkthrough

不用对看不懂示例中的指令感到担忧, 你很快就会上手并且变着花地去使用这些 Git 指令.

我们用一个现有的 Git 仓库来演示这些对象的概念. 看看 Linus 的 first commit: Git 的源码在 Github (代码托管网站) 有存档, 你可以将其克隆下来(虽然可能这会比较慢):

$ git clone https://github.com/git/git.git
...
$ git log --reverse
commit e83c5163316f89bfbde7d9ab23ca2e25604af290
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Thu Apr 7 15:13:13 2005 -0700

    Initial revision of "git", the information manager from hell

提交有着属于它的 SHA-1 值, 它也是一个对象, 存储在 /.git/objects 目录下(你可以去找找看). 如果你去查看这条 commit 记录(运用我们上面提到的 cat-file 命令), 它的结果

$ git cat-file -p e83c5163316f89bfbde7d9ab23ca2e25604af290
tree 2b5bfdf7798569e0b59b16eb9602d5fa572d6038
author Linus Torvalds <torvalds@ppc970.osdl.org> 1112911993 -0700
committer Linus Torvalds <torvalds@ppc970.osdl.org> 1112911993 -0700

Initial revision of "git", the information manager from hell

$ git cat-file -p 2b5bfdf7798569e0b59b16eb9602d5fa572d6038
100644 blob a6bba79ba1f46a1bbf7773449c3bd2bb9bf48e8b    Makefile
100644 blob 27577f76849c09d3405397244eb3d8ae1d11b0f3    README
100644 blob 98a32a9ad39883c6d05a000a68511d4b1ee2b3c7    cache.h
100644 blob 74a0a234dd346fff51c773aa57d82fc4b83a8557    cat-file.c
...

$ git cat-file -p 8bc9a0c769ac1df7820f2dbf8f7b7d64835e3c68
tree 4f856748145b27bc669a98cd4d66574dfd01b083
parent e83c5163316f89bfbde7d9ab23ca2e25604af290
author Linus Torvalds <torvalds@ppc970.osdl.org> 1112912170 -0700
committer Linus Torvalds <torvalds@ppc970.osdl.org> 1112912170 -0700

Add copyright notices.

The tool interface sucks (especially "committing" information, which is just
me doing everything by hand from the command line), but I think this is in
theory actually a viable way of describing the world. So copyright it.

你会发现这里的 parent e83c5163316f89bfbde7d9ab23ca2e25604af290 其实就是第一条提交的 hash. 这表明, 树本身会包含一些指向其他内容的指针. 也就是说, Git 对象引用其它对象时, 并不会真正储存对象, 只保存了他们的哈希值作为引用.

一个大型项目(例如一个kernel), 各个版本都要进行备份, 这难道不会导致内存被占满吗?
提交历史就是这么智能. 它会比较各个 commit 之间的不同, 然后仅储存这些不同的对象, 其余的引用历史版本即可.

事实上, Git内部储存还有包文件 (packfiles) 的机制, 它类似于一个压缩打包的过程, git gc 或者上传远程服务器时, Git 都会这么做. 如果你仔细阅读 git push 的 log 的话

Delta compression using up to 16 threads
Compressing objects: 100% (122/122), done.
Writing objects: 100% (140/140), 1.03 MiB | 1.44 MiB/s, done.
Total 140 (delta 27), reused 40 (delta 1), pack-reused 0

Delta 就是差值, Git 只完整保存其中一个对象, 再保存另一个对象与之前版本的差异内容.

一个 commit ID 不仅和文件内容相关, 还和整个提交历史和仓库相关.

所以历史记录(log)就是这些快照组成的有向无环图(DAG), 对于单分支而言, 它就是一个链表, 对于多分支的仓库来说, 你可以按照下面的方式可视化历史记录:

$ git log --graph --oneline --decorate
* aa9166bcc0 (HEAD -> master, origin/master, origin/HEAD) The ninth batch
*   b00ec259e7 Merge branch 'jk/fsck-indices-in-worktrees'
|\
| * 6e6a529b57 fsck: avoid misleading variable name
* |   7f5ad0ca8d Merge branch 'js/empty-index-fixes'
|\ \
| * | 2ee045eea1 commit -a -m: allow the top-level tree to become empty again
| * | 7667f4f0a3 split-index: accept that a base index can be empty
...

这个示例也显示一点: Git 的提交(git commit)其实就是:

将被改写的文件保存为数据对象(object-hash)
更新暂存区(update index) (你可以暂且不管)
记录树对象(write-tree)
最后创建一个指明了顶层树对象和父提交的提交对象(commit-tree)

commit 是不可变的 (immutable), 因为一旦创建, 它就是一个冰冷冷的对象, 躺在仓库里了. 假设你想撤回刚才的提交, 其实你是新建了一个删除它的的提交. 这点对于了解 git reset 和 git rebase 是至关重要的.

引用和分支

假设你正在开发一款游戏, 按照进度, 你目前开发到第二个关卡, 但突然发现第一关出 BUG 了. 为了解决这个问题, 你打算对第一关之前的代码进行审阅, 也就是说, 你需要查看某一提交前的历史.

首先你需要定位到这次的提交, 根据 commit 信息, 你找到了这次的提交, 假如说它是cac56c61a49613280ec3eff9752c12612864b572, 但显然长度为 40 的 Hash 实在不适合人类记忆, 虽然说 Git 支持短 hash (cac56c), 你也只需要 git log cac56c 就可以完成这项任务, 但这并没有改变事情的本质. 假设你需要反复查看, 那必然的, 你可能需要反复的复制这个 Hash 值.

有没有一种更优雅的内部操作来解决这个问题呢? Git 采用的是引用 (reference).

也就是用一个文件作为这个SHA-1值的指针.

你可以用 git update-ref 来实现这一点:

$ git update-ref refs/lv1 cac56c
$ git log lv1 --pretty=oneline --decorate
cac56c61a49613280ec3eff9752c12612864b572 (refs/lv1) 道具系统+第一关开发完毕
f7d329dee0564e3b8f2737745029ffea03b33fa5 关卡逻辑
11e4fe4309d9cb7db31f19e7c171b36dd61c2db6 战斗系统
$ cat .git/refs/lv1
cac56c61a49613280ec3eff9752c12612864b572

如果你还记得, 在上面演示的仓库中, 我们看到它的历史记录是错综复杂的好几条线, 当时我们提到了分支(branch), 现在就可以回答分支的本质:

它就是一个特殊的引用.
...只不过以当前最新提交的SHA-1值作引用.

假设你的游戏开发团队来了两名新人, alice 和 bob, 他们现在同时开发第三关, 要怎么才能让他们的工作互不影响, 并且最终能将成果合并到一起呢?

我们可以新建两个分支, git branch alice 以及 git branch bob, 然后让他们俩人分别在各自的分支里干活.

如果你查看了 /refs 这个目录的话, 你还会发现两个 heads 和 tags 的文件夹. 这时候你会发现我们创建的分支就在这个 heads 里头:

└── refs
    ├── heads
    │   ├── alice
    │   ├── bob
    │   └── master
    ├── lv1
    └── tags

Git 用一个特殊的HEAD文件保存最新提交的引用. 也就是说它又是一个指向另一个分支的指针.

$ cat .git/HEAD
ref: refs/heads/master

这里 master 分支就是 git init 默认创建的分支. 当你创建第一个 commit, 就创建了一个 refs/heads/master 的一个引用, 并指向这个提交. 当你第二次提交的时候, 它会读取 HEAD 引用指向的 SHA-1 值去设置它的父提交, 并更新当前引用:

tmp = branch_master         # old commit
branch_master = new_commit  # update
new_commit.parent = tmp

切换分支 git checkout 实际上就是更新 HEAD 文件:

$ git checkout bob
Switched to branch 'bob'
$ cat .git/HEAD
ref: refs/heads/bob

当我们的仓库为空时, 我们能不能创建一个新的分支? 答案为否. 想想看, 这是为什么? 你可以试试看到了什么报错.

额外的一个问题是, 为什么我们又可以创建一个空分支? git branch --orphan

分支就是 git update-ref refs/heads/<branch> HEAD. 用图表示, 那么就是一条主线出现了一条分叉:

* 8a71a79 (HEAD -> master) 添加用户反馈
| * 06f5564 (alice) 第三关关卡逻辑
|/
| * 1d388c6 (bob) 第三关开发
|/
* 4892c7d 第二关逻辑
* cac56c6 (refs/lv1) 道具系统+第一关开发完毕
* f7d329d 关卡逻辑
* 11e4fe4 战斗系统

剩下我们再来讨论下 refs/ 里剩下的一类引用: 标签(tag). 假如我们的游戏已经可以发布demo了, 我们想为其附上一个别名, 就叫它 demo1.0, 那么我们可以使用 git tag 命令(这里创建了一个附注标签)

$ git tag -a demo1.0 4892c7dc37d034f41443c67b89f97e2562929e2c -m 'demo 1.0 version released'

我们之前提到过 tag 也是一个对象. 用 cat-file 可以看到这个对象的内容

$ git cat-file -p demo1.0
object 4892c7dc37d034f41443c67b89f97e2562929e2c
type commit
tag demo1.0
tagger Besthope <874256269@qq.com> 1689530116 +0800

demo 1.0 version released