代码托管从业者 Git 指南（上）

本文作者：李博文 - CODING 后端开发工程师

前言

六七年前，我机缘巧合进入了代码托管行业，做过基于 Git 支持 SVN 客户端接入、Git 代码托管平台分布式、Git 代码托管读写分离、Git 代码托管高可用等工作，所幸学到了一些知识，积累了一些经验，本次分享我的一点经验之谈，希望对即将进入或者已在代码托管行业的朋友有所帮助。

Git 的发展历史

版本控制系统的发展历史

版本控制系统历史悠久，最早的开源的版本控制系统可以追溯到几乎与 C 语言同时诞生的 Source Code Control System (SCCS)，作者 Marc J. Rochkind 来自著名的贝尔实验室，他于 1973 年发布了 SCCS 的初始版本。SCCS 的寿命悠久，直到 2007 年再没有人维护而终结。SCCS 本质上是一种 Local Only 版本控制系统，如今网络快速发展，无法跟上时代的脚步只能消亡，同类型的 RCS 虽然维护至今，也鲜有人问津。

1986 年诞生的 CVS 是一款真正的自由软件，使用 GPL 协议发布。一个有趣的事实是：CVS 是 RCS 的前端，也就是说 CVS 将 RCS 从 Local Only 变成了 Client-Server 版本控制系统。随着 2000 年 Apache Subversion 诞生，CVS 的市场快速萎缩，到了 2008 年 CVS 不再维护，集中式版本控制系统渐渐也只剩 Subversion 在维护了。　

最早的分布式版本控制系统是 1992 年诞生的 Sun WorkShop TeamWare，但它并没有发展的很好。从 2000 年到 2007 年，分布式版本控制系统如雨后春笋一样冒了出来，2005 年诞生的 Git 和 Mercurial 幸运流传开来，时至今日，Git 终于在版本控制领域独占鳌头。

Git 的发展史

2005 年，开发 BitKeeper 的商业公司结束与 Linux 内核开源社区的合作关系，他们收回了 Linux 内核社区免费使用 BitKeeper 的权利。Linus Torvalds 花了十天时间编写了 Git 的第一个版本，Git 的故事由此展开。

Git 原本只能在 Linux 上运行，随着开源社区的参与，逐渐能在各个平台上运行。在 Windows 上，最初有两个方案，一个是让 Git 在 Cygwin 的环境下编译，Cygwin 是 Windows 上的 POSIX 兼容层，但缺陷是需要带一大堆 DLL 。另一个方案是 msysgit，基于 MSYS 运行时，MYSY 是更小的 POSIX 兼容环境。到了 2015 年，msysgit 不再维护，主要开发者基于 MSYS2 环境推出了 Git for Windows，而 MSYS2 的核心运行时基于 Cygwin 进行了定制。值得一提的是，在 Git for Windows 中，Git 命令并不是基于 MSYS2 运行时，而是原生的 Windows 程序，到今天我们已经可以使用 Visual C++ 编译 Git 源码了，Git for Windows 的维护者 Johannes Schindelin 加入微软后，在 Windows 上使用 Git 的体验也越来越好。

2008 年 11 月 Shawn O. Pearce 写下了 libgit2 的第一个提交； 2009 年 9 月，Shawn 写下了 JGit 的第一个提交。Libgit2/jgit 被代码托管平台，Git 客户端广泛使用，比如 GitHub 使用 libgit2 的 Ruby 绑定 rugged 提供页面读写存储库能力。遗憾的是 Shawn 已经离开这个世界两年多了。

再来回顾 Git 的一些大事件：2008 年 GitHub 诞生，是最成功的代码托管平台，几乎以一己之力带来了 Git 的繁荣； 2008 年 BitBucket 诞生，最初 BitBucket 还支持 Mercurial，到了 2020 年已不再支持； 2011 年 GitLab 诞生，而国内的 Gitee 也是基于 GitLab 发展而来的； 2014 年 CODING 成立，国内国外代码托管平台百花齐放； 2018 年，微软花费 75 亿美元收购 GitHub，大家才猛然发现，基于 Git 的代码托管平台已经有了这样大的价值。

Git 是一个充满活力的版本控制系统，每一年，Git 的开发者们都在将他们新的知识、经验实践到 Git 中。2018 年 5 月，在谷歌工作的 Git 开发者们发布了 Git Wire Protocol，这解决了 Git 协议中最低效的部分；到了 2020 年 10 月，Git 实验性地支持 SHA256 哈希算法，在 SHA1 被破解几年后，我们终于可以在 Git 中尝试淘汰 SHA1 了。

Git 的发展必然会挤占其他版本控制系统份额，随着 Git 越来越流行，更多的项目也从其他的版本控制系统迁移到 Git 上来：

• 编译器基础设施 LLVM 从 SVN 迁移到 Git
• FreeBSD 从 SVN 迁移到 Git
• GCC （仍处于迁移过程中）从 SVN 迁移到 Git
• Windows 源码（已经迁移到 Git，使用 VFS for Git 技术）
• VIM 迁移到 GitHub
• OpenJDK 从 Mercurial 迁移到 Git

2016 年，Git 诞生 11 年之后，BitKeeper 宣布采用 Apache 2.0 许可协议开源，如果再回到 2005 年，BitKeeper 又会做出怎样的抉择呢？

Git 的存储原理

对于代码托管从业人员来说，只了解 Git 的使用并不足以参与代码托管平台服务开发和架构优化等工作，所以了解 Git 的一些原理非常必要。

Git 的目录结构

首先需要了解 Git 存储库的目录结构，Git 存储库分为常规存储库和 Bare （裸）存储库，普通用户从远程克隆下来的存储库，或者本地初始化的存储库大多是常规存储库，这类存储库和特定的工作区相关联；另一类是没有工作区的存储库，就是裸存储库，在代码托管平台的服务器上，存储库几乎都是以裸存储库的方式存储的。对于常规存储库而言，其存储库真正的路径是工作区根目录下的 .git 文件夹，或者 .git 文件指向的目录，后者通常用于 Git 子模块。

知道了 Git 存储库的位置，就可以查看存储库的目录结构，下面是一个查看存储库的截图。

不同的目录具备不同的作用，大致如下：

在这些目录或者文件中，最重要的是 objects 和 refs ，只需要两个目录的数据就可以重建存储库了。在 objects 目录下，Git 对象可能以松散对象也可能以打包对象的形式存储：

Git 在实现其复杂功能的时候还会创建一些其他目录，更详细的细节可以查阅：Git Repository Layout。

Git 对象的存储

Git 的对象可以按照松散对象的格式存储，也可以按照打包对象的格式存储，用户将文件纳入版本控制时，Git 会将文件的类型标记为 blob，将文件长度和 \x00 以及文件内容合并在一起计算 SHA1 哈希值后，使用 Deflate 压缩，存储到存储库的 objects 目录下，路径匹配正则为 objects\/[0-9a-f]{2}\/[0-9a-f]{38}$，当然如果使用 SHA256 则应该匹配 objects\/[0-9a-f]{2}\/[0-9a-f]{62}$，松散对象的空间布局如下：

Git 使用的 Deflate 是 Phil Katz 为 PKZIP 创建的压缩算法，也是使用最广泛的压缩算法之一，其变体 GZIP 也被广泛用于 POSIX 文件压缩和 HTTP 压缩。Git 命令行，libgit2 目前依赖 zlib 提供 deflate 算法，jgit 则使用 Java 提供的 deflate 实现，Golang 则在 compress/zlib 包中提供 deflate 支持，但算法实现在 compress/flate，严格来说 Git 使用的是 deflate 的 zlib 包装，比如我们使用 zlib 创建 zip 压缩包时会使用 -15 作为 WindowBits，而在创建 GZIP 时会使用 31 作为 WindowBits，在 Git 中，则会使用 15 作为 WindowBits。

在 Git 中，除了有 blob 对象，还有 commit ，tag，以及 tree ，commit 对象存储了用户的提交信息，tree 顾名思义，存储的是目录结构。下面是一个 commit 对象的内容：

tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579
author Scott Chacon <[email protected]> 1243040974 -0700
committer Scott Chacon <[email protected]> 1243040974 -0700

First commit

下面是 tree 对象的内容：

100644 blob a906cb2a4a904a152e80877d4088654daad0c859      README
100644 blob 8f94139338f9404f26296befa88755fc2598c289      Rakefile
040000 tree 99f1a6d12cb4b6f19c8655fca46c3ecf317074e0      lib

解析松散对象非常容易，我们只需要使用能够解析 zlib 的库就可以完成这一操作，这里有一个例子可以参考 https://gist.github.com/fcharlie/2dde5a491d08dbc45c866cb370b9fa07。

想要了解更多的 Git 对象的细节可以参考: Git Internals - Git Objects。

站在文件系统的角度上看，数量巨大的小文件性能通常会急剧下降，而松散对象就是这样的小文件，Git 的解决方案是引入了打包文件，打包文件就是将多个松散对象依次存储到打包文件的存储空间之中，相关的布局如下：

Pack 文件的路径正则为 objects\/pack\/pack-[0-9a-f]{40}.pack$，当存储库使用 SHA256 哈希算法时，相应的路径正则为objects\/pack\/pack-[0-9a-f]{64}.pack$，Pack 文件的魔数是 'P','A','C','K'，随后的 4 字节是版本信息，版本可以为 2，也可以为 3，后者是 SHA256 支持的前提。我们在读取 Pack 文件版本的时候需要注意，Git 使用网络字节序存储数据，也就是常说的大端，目前 Windows 全部使用小端字节序，macOS/iOS 等也是这样，Linux x86/AMD64 也是小端，ARM/ARM64 事实上也使用小端，使用大端的平台非常少。版本后紧接着是 4 字节的数字，用于表示这个包中有多少个 Git 对象，4 字节意味着单个 Pack 中最多只能有 2³²-1 个 Git 对象。接下来的事情就稍微复杂一些，Git 存储对象时使用 3-bit表示对象类型，(n-1)*7+4 bit 表示文件长度，这种机制主要是支持大于 4G 的文件和支持 OBJ_OFS_DELTA ，也就是说，尽管 Git 是基于快照的，但是在 pack 文件中，我们依然可以看到一些对象使用差异存储，这样的好处是节省空间，坏处就是查看对象复杂度上升，因此，Git 会倾向于将历史久远的用 OBJ_OFS_DELTA 存储，以降低影响，不管怎么说，都是权衡利弊，保证存储和读取的平衡。最后是 20 字节的 checksum SHA1，当然如果是 SHA-256 存储库，则需要使用 SHA-256 计算 checksum。

上图一目了然，如果没有其他措施，我们要在 Pack 文件中查找某个对象是非常难的，所幸这个问题一开始就被重视了，在 Pack 文件的同级目录下存在文件后缀名为 .idx 的文件，就是 Pack Index，其布局如下：

版本 1 的 Pack-Index 现在已经很难见到，原因很简单，不支持 Pack 文件大于 4 GB，版本 2 格式非常有趣，魔数为 '\377','t','O','c'，第二个 4 字节就是版本信息，随后是 256 * 4 的扇区表，0~254 分别表示前缀从 0x00~0xFE 的对象数量，而 fanout[255] 则表示所有对象的数量，随后对象 ID 按字典排序到 sha listing，紧接着是相应的 crc checksums，然后是 packfile offsets，packfile offsets 是 4 字节的，这并不能支持 Pack 大于 4 GB 。而后续的 large packfile offsets 则支持了 Pack 大于 4 GB 。当 4byte offset 最高位是 1 时说明需要从 large packfile offsets 读取长度。

Pack Index 文件很好的解决了 Pack 文件的随机读取的问题，按照其特性，我们在查找 Git 对象时，使用二分法查找，最多 8 次就可以在找到对象在 Pack 中的偏移，进一步读取文件。

但如果 Pack 文件数量特别多时，还是会遇到查找对象性能较多，微软在将 Windows 源码迁移到 Git 后也遇到了这个问题，后来在微软工程师的努力下，multi-pack-index （ MIDX ）出现了，存在多个 Pack 文件时，MIDX 便可以加快 Git 对象的查找。

既然我们已经对 Git 的存储有了个简单的认识，那么要找到某个文件也不在话下，分支对应了一个提交，提交有一个 ID，我们可以在松散对象或者打包对象中找到该 ID，然后获得提交的内容，找到 tree 后，按照路径一级级往下找，找到路径匹配的 blob，该 blob 解压后的内容就是文件的原始内容，一个简单的流程如下：

对于引用而言，通常存储在 refs 目录下，和松散对象一样，这种机制可能存在性能问题，因此，在运行 git gc 后，引用会被打包到 packed-refs 文件中集中管理，为了加快引用的查询，引用名会使用字典排序，Git 同样会使用二分法查找在 packed-refs 中查找引用。尽管查找引用的速度非常快，但面对 Android 这样引用数量巨大的项目，Git 依然会显得心有余而力不足，这就需要设计一个好的方案解决其性能问题。

Git 存储原理的运用

了解到 Git 的存储原理后，我们可以基于其原理做一些有趣的事情，比如要快速找到存储库中存在哪些大文件，我们可以通过分析 Pack Index，将文件的偏移按照递减的顺序排列，依次相减就可以知道某一对象在 Pack 中占据的大致大小，这样就可以实现大文件的检测。这种机制要比从 Pack 中依次读取文件大小高效的多，同时对于平台而言，尽管存在一些误差，但这种方案却是十分经济有效的。

另外，在实现代码托管平台存储库快照的功能时，可以通过研究存储库引用的存储机制，利用引用名称空间实现存储库的快照，相对于直接克隆快照的方案，该方案节省了非常大的存储空间。