借 Git 的第一个 commit 探索 Git 原理

最近想了解一下 Git 的实现，首先是看了 pro git 的 git 原理部分。看完之后对 git 的实现有了个大概的了解，但还是不过瘾。于是把 git 的源码 clone 下来看源码是如何实现的，但是 git 的源码实在太多了，要耗费太多精力了。

我尝试把跳转到 Git 的第一个 commit，代码量就少了很多，只有差不多 1000 行左右。修改了一些代码把程序编译起来了。看了下初始版本的 git，发现很多概念还是可以和现在的 git 的相通，有阅读的价值。

之后还看到 jacob Stopak 的解析，对 git 的代码做了很多注释。看到的时候很是惊喜，因为网上对 git 这样的解析很少，看日期还是今年的 5 月 22 号发布的，新鲜的 >_<。

What Can We Learn from the Code in Git’s Initial Commit?

获取源代码并编译

在这里使用 Jacob Stopak 的项目，它对 Git 的第一个 commit 里面的代码添加了大量注释，还修改了一些代码方便我们在现代操作系统上编译。

获取代码

git clone https://bitbucket.org/jacobstopak/baby-git.git

编译直接 make 就好了，不过这里还是会出现编译错误，需要在 cache.h 文件修改下面的变量，加上 extern

extern const char *sha1_file_directory;
extern struct cache_entry **active_cache;
extern unsigned int active_nr, active_alloc;

直接 make

make

如果你想要尝试使用 github 上 git 的源码来编译的话，可以进行下面操作

# 先 clone 源码
git clone https://github.com/git/git.git
# 根据 log 找到第一个 commit
git log --reverse
# 检出第一个 commit
git checkout e83c5163316f89bfbde7d9ab23ca2e25604af290

这里的源码直接 make 的话会编译失败，还需要作出下面的修改

首先是 Makefile 文件

# 把 LIBS 这行修改成这样
LIBS= -lcrypto -lz

然后在 cache.h 中

#添加头文件
#include <string.h>

和前面同样的操作，把下面几个变量加上 extern

extern const char *sha1_file_directory;
extern struct cache_entry **active_cache;
extern unsigned int active_nr, active_alloc;

之后就可以直接 make 了。或者你嫌麻烦可以用我 z.diff 文件，直接 apply 一下。

git apply z.diff

效果一样。

源码结构

可以看到 git 的开始的时候只有 8 个 .c 文件和 1 个 .h 文件。

可以看到一下包含代码和注释行数只有 1037 行

cat *.c *.h | wc -l
1037

其中 7 个 .c 文件可以对应现在的 7 个 git 命令

文件 当前 Git 作用
init-db git init 初始化 git 仓库
update-cache git add 添加文件到暂存区
write-tree git write-tree 将暂存区的内容写入到一个 tree 对象到 git 的仓库
commit-tree git commit 基于指定的 tree 对象创建一个 commit 对象到 git 的 仓库
read-tree git read-tree 显示 git 仓库的树对象内容
show-diff diff 显示暂存的文件和工作目录的文件差异
cat-file git cat-file 显示存储在 Git 仓库中的对象内容

至于 read-cache.c 文件则定义了一些程序一些公用的函数和几个全局变量。

概念分析

Linus Torvalds 在 readme 中对 git 的实现原理作出了一些解释。

首先它给出了为什么要使用 git 这个名字的原因

  • 随机的三个字母组合，没有和其他的 unix 命令冲突
  • 简单
  • 当它好使的时候叫 global information tracker
  • 不好使的时候叫 goddam idiotic truckload of sh*t
  • random three-letter combination that is pronounceable, and not
    actually used by any common UNIX command. The fact that it is a
    mispronounciation of "get" may or may not be relevant.
  • stupid. contemptible and despicable. simple. Take your pick from the
    dictionary of slang.
  • "global information tracker": you're in a good mood, and it actually
    works for you. Angels sing, and a light suddenly fills the room.
  • "goddamn idiotic truckload of sh*t": when it breaks

它有两个核心的概念

  • objects databases
  • current directory cache （相当于现在的暂存区）

Object Databases

object database 相当于一个基于文件系统的键值对数据库，用文件的 sha-1 值作为键，在 .dircache/objects 中存放各种类型的数据。

在这里介绍三种类型：

  • blob
  • tree
  • commit

blob 对象用来存储完整的文件内容，用于 git 追踪文件内容。blob 的结构

blob size\0blobdata(file content)

git 除了要追踪文件内容外还要追踪文件名、文件存储路径和权限属性之类的信息。这个时候我们引入 tree 对象来存储这些信息。tree 只会保留 blob 对象的 sha-1 值，不会追踪文件内容。（现在的 tree 对象还会可以 tree 对象嵌套 tree 对象，现在这里还没有）

大致的结构是这样的（省略了头）

100644 a.txt (6e666502660a7e810b276afd62523c56b34c1671)
100644 b.txt (b 的 sha-1 值)
100644 c.txt (c 的 sha-1 值)

commit 对象，可以理解为我们的一个 commit，它记录了特定时间的目录树（tree 对象）、父 commit 的 sha-id（可以有多个或 0 个）、作者和提交者信息和对应的 commit message。git 通过 commit 对象来追踪存储库的完整历史开发记录。

同样是大致结构：

tree 1c93ac491de01f734fedbe70f31c47ca965c93b6
parent 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
author  <zzk@archlinux> Sat Jun 27 14:41:43 2020
committer  <zzk@archlinux> Sat Jun 27 14:41:43 2020

second commit

现在的 git 同样还是一直在使用上面这些概念，通过管理这些对象来实现我们的版本控制。

Git 把每个文件的版本都完全保存下来，会不会占用很多空间？是不是太暴力了？

git 会使用 zlib 对所有对象进行压缩，代码这类文本数据可以做到很高的压缩率（因为代码中很多都是重复的，比如关键字、函数调用）。在现在的 git 还引入了 packfiles 机制，会查找找命名及大小相近的文件，只保存文件不同版本之间的差异，也是可以只保存 diff 的。关于暴力的话，就是空间换时间方式了，这样做在版本跳转的时候很快，不用一个一个地应用 diff，直接拿出来就好了。

Git 如何存储这些对象？

它们都被存放在 .dircache/objects 文件夹中，通过内容的 sha-1 值来索引对用的对象。在 dircache/objects 下还会生成 256 个子目录（00～ff），用来索引前两位的 sha-1 值。

Current directory cache

current directory cache 就是我们使用的暂存区，它存储在 .dircache/index 文件中，可以看作是一个临时的 tree 对象。当执行 update-cache 时，就会创建对应文件的 blob 对象，并将树信息加到 .dircache/index 文件中。

如何使用

前面说的那些可能没有实际使用会不太好理解，下面我们可以实战一下，使用一些初始版本的 git。

在这里我们会利用这些现有的命令

  • 把暂存区的文件取出来（相当于 git checkout -- file）

  • 提交两个 commit 并在这两个 commit 的之间切换

先使用 init-db 创建存储库

$ ./init-db

可以看到创建了 .dircache 文件夹，和现在的 .git 文件是一样的。

创建一个文件写入到暂存区，执行 update-cache 会在 .dircache/objects 文件夹中生成一个 blob 对象并把它加入到 .dircache/index 暂存区中。

$ echo "123456" > a.txt
$ ./update-cache a.txt

使用 find 查看创建的 blob 对象

$ find .dircache/objects -type f
.dircache/objects/6e/666502660a7e810b276afd62523c56b34c1671

查看一下

$ cat .dircache/objects/6e/666502660a7e810b276afd62523c56b34c1671
xKOR0g0426156%

由于是用 zlib 压缩过的没解压看不出来啥，我们可以使用 cat-file 查看

$ ./cat-file 6e666502660a7e810b276afd62523c56b34c1671
temp_git_file_O5J3ZL: blob

他会生成一个临时文件，里面是解压好的文件内容，可以看到我们保存到存储库里 a.txt 的内容

$ cat temp_git_file_O5J3ZL
123456

现在我们把当前的暂存区的内容保存为 tree 对象到 .dircache/objects 中

$ ./write-tree
433aef473a665a9efe1cf21fbc617fbf833c71b5

写入成功会打印对象的 SHA-1 值，我们可以用 read-tree 查看这个 tree 对象有什么

$ ./read-tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
100644 a.txt (6e666502660a7e810b276afd62523c56b34c1671)

现在可以提交我们的第一个 commit 了，填写完 commit message 后按 crtrl+d 退出

$ ./commit-tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
Committing initial tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
first commit 
4ae1f8aae02d7178aa4fc52f45f068cd750aa3de

可以查看一下 commit 对象有什么东西

$ ./cat-file 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
temp_git_file_pNLmni: commit
$ cat temp_git_file_pNLmni
tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
author  <zzk@archlinux> Sat Jun 27 14:20:55 2020
committer  <zzk@archlinux> Sat Jun 27 14:20:55 2020

first commit

我们完成了第一个提交，现在我们对 a.txt 做一下修改

$ echo "version2" > a.txt

用 show-diff 可以查看和暂存区的版本的差异

$ ./show-diff
a.txt:  6e666502660a7e810b276afd62523c56b34c1671
--- -   2020-06-27 14:27:19.975168003 +0800
+++ a.txt       2020-06-27 14:27:18.048129094 +0800
@@ -1 +1 @@
-123456
+version2

如果想取出暂存区的文件，有两个方法

  • 使用生成的 diff，修改文件
  • 用 cat-file 取出暂存区文件内容（第二行有文件的 SHA-1 值）

先用 diff 试试

$ ./show-diff > a.diff
$ patch --reverse a.txt a.diff
patching file a.txt
$ cat a.txt
123456

可以看到文件又回到暂存区的版本了。现在把文件再修改回去，使用 cat-file 来试试

$ echo "version2" > a.txt
$ ./show-diff
a.txt:  6e666502660a7e810b276afd62523c56b34c1671
--- -   2020-06-27 14:33:53.795263485 +0800
+++ a.txt       2020-06-27 14:33:50.726893274 +0800
@@ -1 +1 @@
-123456
+version2
$ ./cat-file 6e666502660a7e810b276afd62523c56b34c1671
temp_git_file_d4cTZ7: blob
$ mv temp_git_file_d4cTZ7 a.txt
$ cat a.txt
123456

现在我们准备第二个 commit ，再执行一遍之前的操作

$ echo "verison2" > a.txt
$ ./update-cache a.txt
$ ./write-tree
1c93ac491de01f734fedbe70f31c47ca965c93b6

执行 commit-tree 时候要注意，由于这是第二个提交，需要用 -p 指定一下父提交的 SHA-id 也就是第一个 commit

$ ./commit-tree 1c93ac491de01f734fedbe70f31c47ca965c93b6 -p 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
second commit
3d4340867cb1dd857987fc2db9b1b4bc14af7051

看一下这个 commit

$ ./cat-file 3d4340867cb1dd857987fc2db9b1b4bc14af7051
temp_git_file_8Cguru: commit
$ cat temp_git_file_8Cguru 
tree 1c93ac491de01f734fedbe70f31c47ca965c93b6
parent 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
author  <zzk@archlinux> Sat Jun 27 14:41:43 2020
committer  <zzk@archlinux> Sat Jun 27 14:41:43 2020

second commit

现在我们要把 a.txt 的版本切换到上一个 commit，从上面的输出可以找出 parent 提交的 SHA-id

我们利用这个父提交的 sha-id 找到对应的 tree object 的 sha-id，再从 tree object 找到对应 a.txt 的 blob object 的 sha-id。最后利用 cat-file 就可以还原出来原始 a.txt 的内容了。

$ ./cat-file 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
temp_git_file_MssRdY: commit
$ cat temp_git_file_MssRdY
tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
author  <zzk@archlinux> Sat Jun 27 14:20:55 2020
committer  <zzk@archlinux> Sat Jun 27 14:20:55 2020

first commit
$ ./read-tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
100644 a.txt (6e666502660a7e810b276afd62523c56b34c1671)
$ ./cat-file 6e666502660a7e810b276afd62523c56b34c1671
temp_git_file_2RlDAI: blob
$ mv temp_git_file_2RlDAI a.txt
$ cat a.txt
123456

现在 a.txt 就被还原到了 第一个 commit 时的状态。

总结：原始的 git 很难用。经过不断地打磨才成了今天这样子好用，现在的 git 很多人只要会 add、commit、push 就完事了，也不用了解 git 原理。

代码分析

这里对 git 的部分源码进行分析，由于前面已经写了很多篇幅了，这里就不会对太多的代码进行分析，里面的代码也是超简单，可以说是 linus 代码写得漂亮。你自己看估计也花不了一会儿，而且 Jacob Stopak 对代码做超多的注释，真的没啥好说的。 甚至你可以根据前面的知识脑补出大概源码了>_<。

在这里推荐一个阅读源码的工具 sourcetrail。看源码时很方便。

init-db.c

int main(int argc, char **argv)
{
    char *sha1_dir = getenv(DB_ENVIRONMENT), *path;
    int len, i, fd;
    
    // 创建 .dircache 的目录
    if (mkdir(".dircache", 0700) < 0) {
        perror("unable to create .dircache");
        exit(1);
    }

    /*
     * If you want to, you can share the DB area with any number of branches.
     * That has advantages: you can save space by sharing all the SHA1 objects.
     * On the other hand, it might just make lookup slower and messier. You
     * be the judge.
     */
    sha1_dir = getenv(DB_ENVIRONMENT);
    if (sha1_dir) {
        struct stat st;
        if (!stat(sha1_dir, &st) < 0 && S_ISDIR(st.st_mode))
            return 1;
        fprintf(stderr, "DB_ENVIRONMENT set to bad directory %s: ", sha1_dir);
    }

    /*
     * The default case is to have a DB per managed directory. 
     */
    sha1_dir = DEFAULT_DB_ENVIRONMENT;
    fprintf(stderr, "defaulting to private storage area\n");
    len = strlen(sha1_dir);
    if (mkdir(sha1_dir, 0700) < 0) {
        if (errno != EEXIST) {
            perror(sha1_dir);
            exit(1);
        }
    }
    path = malloc(len + 40);
    memcpy(path, sha1_dir, len);
    // 创建 .dircache/objects 下的 256 个子目录
    for (i = 0; i < 256; i++) {
        sprintf(path+len, "/%02x", i);
        if (mkdir(path, 0700) < 0) {
            if (errno != EEXIST) {
                perror(path);
                exit(1);
            }
        }
    }
    return 0;
}

init-db 就只是单纯创建好这些目录而已，和我们前面看到的效果也一样。

这里介绍 update-cache.c 文件，主要说一下怎么创建 blob 和加入 .dircache/index 文件。

首先看 main

int main(int argc, char **argv)
{
    int i, newfd, entries;
    
    // 将 .dircache/index 中的内容读入到 active_cache 这个全局变量中
    entries = read_cache();
    if (entries < 0) {
        perror("cache corrupted");
        return -1;
    }
    
    // 这里创建 lock 文件是为了不让多个 update-cahce 同时运行的锁文件
    newfd = open(".dircache/index.lock", O_RDWR | O_CREAT | O_EXCL, 0600);
    if (newfd < 0) {
        perror("unable to create new cachefile");
        return -1;
    }
    for (i = 1 ; i < argc; i++) {
        char *path = argv[i];
        // 验证路径
        if (!verify_path(path)) {
            fprintf(stderr, "Ignoring path %s\n", argv[i]);
            continue;
        }
        // 把文件添加到 object 数据库中
        if (add_file_to_cache(path)) {
            fprintf(stderr, "Unable to add %s to database\n", path);
            goto out;
        }
    }
    // 更新 index 文件
    if (!write_cache(newfd, active_cache, active_nr) && !rename(".dircache/index.lock", ".dircache/index"))
        return 0;
out:
    unlink(".dircache/index.lock");
}

通过 main 函数可以看到生成 blob 应该是在 add_file_to_cache 中做的、而更新 index 则是在 write_cache 中做的。后面的可以自己追踪一下。我说一下大概做了啥

add_file_to_cache 中读取文件然后构造一个 blob 对象进行压缩，最后计算 sha-1 值，把 压缩好的 blob 对象存到 sha-1 值对应的位置。（现在看文档好像是先计算 sha-1 值再进行压缩了）之后通过文件名二分查找放入 active_cache 中（也就是 .dircahce/index 暂存区，这个变量是个全局变量开始时将 .dircache/index 中的内容读入到里面），因为是暂存区是通过文件名进行排序的，所以确认一个文件是否在暂存区很快，二分只要 logn。

write_cache 中就是把 active_cache 再写回 .dircache/index.lock 文件，最后把锁文件重命名为 .dircache/index 暂存区文件。

这里是我的博客

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,236评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,867评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,715评论 0赞 340
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,899评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,895评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,733评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,085评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,722评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,025评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,696评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,816评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,447评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,057评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,009评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,254评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,204评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,561评论 2赞 343