最近想了解一下 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 命令

至于 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 暂存区文件。

这里可以访问我的博客