借 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阅读 204,189评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,577评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,857评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,703评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,705评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,620评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,995评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,656评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,898评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,395评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,982评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2 342