深度探秘！一文全方位讲透 Git 底层数据结构与原理

Git状态模型与基础概念解析

上图展示了Git对象在不同生命周期中的存储位置。通过各种Git命令，我们能够改变Git对象的存储生命周期。

工作区（Workspace）

工作区即我们当前的工作空间，呈现为本地文件夹中的文件结构。在初始化工作区或工作区处于clean状态时，文件内容与index暂存区保持一致。但随着对文件的修改，在尚未将其add到暂存区之前，工作区与暂存区的内容就会出现不一致。

暂存区（Index）

在旧版本中，暂存区也被称为Cache区，它是文件的临时存放地。所有暂存于该区域的文件，会在执行commit操作时一并提交至local repository。此时，local repository中的文件将完全被暂存区的内容所更新。暂存区在Git的架构设计中极为关键，同时也是较难理解的部分。

本地仓库（Local Repository）

Git作为分布式版本控制系统，与其他版本控制系统的显著区别在于其去中心化特性。用户无需与中央服务器（Remote Server）通信，便能在本地完成全部离线操作，如log记录查看、历史追溯、提交（commit）以及差异比较（diff）等。实现这一离线操作的核心在于，Git拥有一个与远程仓库几乎相同的本地仓库，所有本地离线操作都可在此完成，待有需要时，再与远程服务进行交互。

远程仓库（Remote Repository）

远程仓库属于中心化仓库，供所有人共享。本地仓库需要与远程仓库进行交互，以便将其他人的内容更新至本地，同时也能将自己的内容上传分享给他人。其结构与本地仓库大致相似。

文件在不同操作下会处于不同的Git生命周期，下面通过一个文件变化的例子来进一步了解。

文件变化

Git 的对象模型与基础概念深度剖析

仓库结构

Git 作为分布式版本控制系统，其分布式特性的一个重要体现是在本地拥有一个完整的 Git 仓库，即 .git 文件目录。借助这个本地仓库，Git 能够实现完全离线化操作。在这个本地化的仓库中，存储着 Git 所有的模型对象。以下是 Git 仓库的目录树结构及其相关说明：

Git 主要包含四个核心对象，分别为 Blob、Tree、Commit 和 Tag，它们均采用 SHA-1 算法进行命名。

你可以运用 git cat-file -t 命令查看每个 SHA-1 所对应的对象类型，使用 git cat-file -p 命令查看每个对象的内容以及简单的数据结构。git cat-file 堪称 Git 的“瑞士军刀”，是 Git 底层的核心命令。

Blob 对象

Blob 对象专门用于存储单个文件的内容，通常为二进制数据文件。它不包含任何与文件相关的额外信息，例如文件名和其他元数据。

Tree 对象

Tree 对象对应着文件系统的目录结构，其内部主要包含子目录（tree）、文件列表（blob）、文件类型以及一些数据文件的权限模型等信息。

以下是具体的输出示例：

→ git cat-file -t ed807a4d010a06ca83d448bc74c6cc79121c07c3
tree

→ git cat-file -p ed807a4d010a06ca83d448bc74c6cc79121c07c3
100644 blob 36a982c504eb92330573aa901c7482f7e7c9d2e6    .cise.yml
100644 blob c439a8da9e9cca4e7b29ee260aea008964a00e9a    .eslintignore
100644 blob 245b35b9162bec4ef798eb05b533e6c98633af5c    .eslintrc
100644 blob 10123778ec5206edcd6e8500cc78b77e79285f6d    .gitignore
100644 blob 1a48aa945106d7591b6342585b1c29998e486bf6    README.md
100644 blob 514f7cb2645f44dd9b66a87f869d42902174fe40    abc.json
040000 tree 8955f46834e3e35d74766639d740af922dcaccd3    cli_list
100644 blob f7758d0600f6b9951cf67f75cf0e2fabcea55771    dep.json
040000 tree e2b3ee59f6b030a45c0bf2770e6b0c1fa5f1d8c7    doc
100644 blob e3c712d7073957c3376d182aeff5b96f28a37098    index.js
040000 tree b4aadab8fc0228a14060321e3f89af50ba5817ca    lib
040000 tree 249eafef27d9d8ebe966e35f96b3092d77485a79    mock
100644 blob 95913ff73be1cc7dec869485e80072b6abdd7be4    package.json
040000 tree e21682d1ebd4fdd21663ba062c5bfae0308acb64    src
040000 tree 91612a9fa0cea4680228bfb582ed02591ce03ef2    static
040000 tree d0265f130d2c5cb023fe16c990ecd56d1a07b78c    task
100644 blob ab04ef3bda0e311fc33c0cbc8977dcff898f4594    webpack.config.js
100644 blob fb8e6d3a39baf6e339e235de1a9ed7c3f1521d55    webpack.dll.config.js
040000 tree 5dd44553be0d7e528b8667ac3c027ddc0909ef36    webpack

详细解释如下：

Commit 对象

Commit 对象代表着一次修改的集合，是当前所有修改文件的汇总，可类比为一批操作的“事务”。它是修改过的文件集的一个快照，随着一次 commit 操作的执行，修改过的文件将会被提交到本地仓库（local repository）中。通过 Commit 对象，在版本控制过程中可以检索出每次修改的具体内容，是版本化管理的基石。

以下是一个 Commit 对象的示例：

→ git cat-file -t fbf9e415f77008b780b40805a9bb996b37a6ad2c
commit
→ git cat-file -p fbf9e415f77008b780b40805a9bb996b37a6ad2c
tree bd31831c26409eac7a79609592919e9dcd1a76f2
parent d62cf8ef977082319d8d8a0cf5150dfa1573c2b7
author xxx  1502331401 +0800
committer xxx  1502331401 +0800
修复增量bug

详细解释如下：

Tag 对象

Tag 可被视为一个“固化的分支”，一旦为某个版本打上 Tag 之后，该 Tag 所代表的内容将永远保持不变，因为 Tag 只会关联当时版本库中最后一个 Commit 对象。

与之不同的是，分支随着不断的提交操作，其内容会持续发生改变，这是因为分支指向的最后一个 Commit 对象会不断更新。因此，在应用或软件版本发布时，通常会使用 Tag 来标记特定的版本。

Git 的 Tag 类型主要分为以下两种：

1. 轻量级（lightweight）

创建方式如下：

git tag tagName

采用这种方式创建的 Tag，Git 底层并不会创建一个真正意义上的 Tag 对象，而是直接指向一个 Commit 对象。此时，如果使用 git cat-file -t tagName 命令，会返回一个 commit。

以下是一个示例：

→ git cat-file -t v4
commit
→ git cat-file -p v4
tree ceab4f96440655b0ff1a783316c95450fa1fb436
parent 7f23c9ca70ce64fc58e8c7507c990c6c6a201d3d
author 与水  1506224164 +0800
committer 与水  1506224164 +0800
rawtest2

2. 含附注（annotated）

创建方式如下：

git tag -a tagName -m ''

使用这种方式创建的标签，Git 底层会创建一个 Tag 对象，该对象会包含相关的 Commit 信息以及 Tagger 等额外信息。此时，如果使用 git cat-file -t tagname 命令，会返回一个 tag。

以下是一个示例：

→ git cat-file -t v3
tag
→ git cat-file -p v3
object d5d55a49c337d36e16dd4b05bfca3816d8bf6de8   //commit 对象 SHA - 1
type commit
tag v3
tagger xxx  1506230900 +0800
与水测试标注型tag

总结：所有对象模型之间的关系大致如下：

Git的存储模型深度解析

概念阐述

Git之所以显著区别于其他版本控制系统（VCS），关键原因之一在于其对文件版本管理的实现理念与其他VCS截然不同，这也正是Git版本管理功能强大的核心所在。

以Subversion（Svn）为代表的其他VCS，在文件版本管理理念上，是以文件为水平维度，记录每个文件在不同版本下的增量变化（delta）。

而Git对文件版本的管理理念则是以每次提交作为一次快照。在提交时，Git会对所有文件进行一次全量快照，然后存储该快照的引用。

在Git的存储层面，对于文件数据未发生改变的文件，Git仅存储指向源文件的引用，而非多次重复存储文件，这一特性在pack文件中能够清晰体现。

如下图所示：

存储结构剖析

尽管随着需求的日益复杂和功能的持续拓展，Git版本也在不断更新迭代，但其主要的存储模型大体保持稳定。如下图所示：

Git的检索模型详解

→ cd .git/objects/
→ ls
03   28   7f   ce   d0   d5   e6   f9   info pack

Git中的对象主要分为两种类型：

一种是松散对象，它们存储在 .git/objects 文件夹下以 03、28、7f、ce、d0、d5、e6、f9 等命名的子文件夹中。这些文件夹名称仅由 2 个字符组成，实际上是每个文件 SHA - 1 值的前 2 个字母。由于十六进制字符的组合，最多会有 0XFF 即 256 个这样的文件夹。

另一种是打包压缩对象，经过打包压缩后的对象主要存于 pack 文件中。这种设计主要是为了在文件进行网络传输时，减少网络消耗，提高传输效率。

若要节省存储空间，用户可以手动触发打包压缩操作（使用 git gc 命令），将松散对象打包成 pack 文件对象。反之，也能将 pack 文件解压缩为松散对象（使用 git unpack - objects 命令）。

→ cd pack
→ ls
pack - efbf3149604d24e6ea427b025da0c59245b2c2ea.idx  pack - efbf3149604d24e6ea427b025da0c59245b2c2ea.pack

为了提升 pack 文件的检索效率，Git 会基于 pack 文件生成相应的索引 idx 文件。

pack 文件剖析

pack 文件的设计十分精密且巧妙，它遵循降低文件大小、减少文件传输量、降低网络开销以及确保安全传输的原则。

pack 文件设计的概览图如下：

pack 文件主要由三部分构成，分别是 Header（头部）、Body（主体）和 Trailer（尾部）：

• Header 部分：主要包含 4 字节的 “PACK” 标识、4 字节的 “版本号” 以及 4 字节的 “Object 条目数”。这些信息为后续对 pack 文件的解析和处理提供了基础。
• Body 部分：主要是一个个 Git 对象依次存储其中。每个对象的存储位置会在 idx 索引文件中记录其在 pack 文件中的偏移量（offset），通过这个偏移量，能够快速定位到具体的对象。
• Trailer 部分：主要是所有 Objects 的名称（SHA - 1）的校验和。这一设计是为了确保文件在传输过程中的安全可靠，防止数据在传输过程中出现损坏或篡改。

下面我们来看具体的 pack 文件：

从上图可以看出：通过 idx 索引文件在 pack 文件中定位到对象之后，对象的结构主要由 Header 和 Data 两部分组成。

1. Header 部分

在 Header 部分，其前 8 位（8 - bits）具有特定的含义。其中，第 1 位是最高有效位（MSB），紧接着的 3 位用于表示当前对象的类型，主要存在 6 种存储类型。而随后的 4 位则是该对象展开后大小（length）的一部分，但并非完整大小。完整的大小取决于 MSB 以及后续的多个位，其完整算法如下：

• 若 8 位中的第 1 位为 1，这表明下一个字节仍属于 Header 的一部分，用于表示该对象展开后的大小。
• 若 8 位中的第 1 位为 0，则意味着从下一个字节开始将是数据（Data）文件。
• 当对象类型为 OBJ_OFS_DELTA 时，代表采用 Delta 存储方式。此时，当前的 Git 对象仅存储增量部分，而基本部分则由接下来可变长度的字节数来表示基础对象（base object）相对于当前对象的偏移量。这些可变字节同样使用 1 位的 MSB 来表示下一个字节是否为可变长度的组成部分。通过对偏移量取负数，就能知晓基础对象位于当前对象前面多少字节处。
• 当对象类型为 OBJ_REF_DELTA 时，同样表示采用 Delta 存储方式。当前的 Git 对象仅存储增量部分，对于基本部分，会使用 20 字节来存储基础对象的 SHA - 1 值。

2. Data 部分

Data 部分是经过 Zlib 压缩处理的数据。它可能是全部数据，也可能是 Delta 数据，具体取决于 Header 部分的存储类型。如果存储类型为 OBJ_OFS_DELTA 或者 OBJ_REF_DELTA，那么此处存储的就是增量（Delta）数据。若要获取全量数据，就需要递归地找到最基础的对象（Base Object），然后应用 Delta 数据。在基础对象上应用 Delta 数据的过程十分精妙，本文暂不做详细介绍。

从上述内容中，我们可以清晰地了解 pack 文件的格式。接下来，让我们深入本地仓库一探究竟：

非增量 delta 格式如下：

SHA - 1 type size size - in - packfile offset - in - packfile

增量 delta 格式如下：

SHA - 1 type size size - in - packfile offset - in - packfile depth base - SHA - 1

→ git verify - pack - v pack - efbf3149604d24e6ea427b025da0c59245b2c2ea.pack
cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804 commit 275 189 12
399334856af4ca4b49c0008a25b6a9f524e40350 commit 69 81 201 1 cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804
e0efbd5121c31964af1615cf24135a7c6c11cc1d commit 268 187 282
7bc9a5e0199bd4a6d4d223ce7e13239631df9635 commit 29 41 469 1 e0efbd5121c31964af1615cf24135a7c6c11cc1d
2e43c62f6ff99c88d20329487137f8dbabc8b3ec commit 220 157 510
b6f173085f49f109a00b2a3f08a7dc499cc47f1f commit 220 157 667
0466b3f1aadde74234f7dd3f4ef7f1505c50fb0c commit 220 157 824
76c5e45f8e295226b1bc5c8c7e2bc98d7eae6be1 commit 74 85 981 1 b6f173085f49f109a00b2a3f08a7dc499cc47f1f
2729f1fa896d384b49a2f5c53d483eacc0929ebb commit 172 127 1066
3cc58df83752123644fef39faab2393af643b1d2 blob   2 11 1193
62189d1a10cc2a544c4e5b9c4aba9493cf5782dc blob   8 15 1204
a9a5aecf429fd8a0d81fbd5fd37006bfa498d5c1 blob   4 13 1219
2b8982f7c281964658d2cd8b6c17b541533dd277 tree   104 105 1232
92c4aafa39ee387a1f8237f00c78c499aebaf0b2 tree   104 105 1337
223b7836fb19fdf64ba2d3cd6173c6a283141f78 blob   2 11 1442
1756ca64f21724f350fe2cc5cfb218883e314c3d tree   71 80 1453
e11ddfa79f01b01a8e1553bbffaa2d6c03ae9f6e tree   71 80 1533
f70f10e4db19068f79bc43844b49f3eece45c4e8 blob   2 11 1613
e982b6207b10a869164e2c8d19d25ffb059e6a16 tree   66 73 1624
f2e9f73f27124916344e0fd03bb449bc6feca59d tree   66 74 1697
d09da444f461d7cee3679666a1ded5ab79832ed0 tree   33 44 1771
non delta: 18 objects
chain length = 1: 3 objects
pack - efbf3149604d24e6ea427b025da0c59245b2c2ea.pack: ok

例如，399334856af4ca4b49c0008a25b6a9f524e40350（SHA - 1）表示该对象的基础对象 SHA - 1 是 cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804，基础对象的最大深度（depth）为 1。若 cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804 还有引用对象，那么深度（depth）将变为 2。

pack Header 中的最后 4 个字节用于表示 pack 文件中对象的数量，最多可表示 2 的 32 次方个对象。因此，在一些大型工程中，会存在多个 pack 文件和多个 idx 文件。

文件解压缩后的大小（size）有什么作用呢？这主要是为了方便我们在进行解压操作时，设置流的大小，即能够方便地知晓流的大小。需要注意的是，这里的 size 并非用于说明下一个文件的偏移量，偏移量信息均来自索引文件，如下所示的 idx 文件：

index 文件

由于版本 1 相对简单，下面以版本 2 为例进行介绍。

版本 2 的 index 文件采用分层模式，具体分为：Header、Fanout）、SHA、CRC、Offset、Big File Offset和 Trailer。

Header 层

版本 2 的 Header 部分总共占用 8 字节，而版本 1 没有这部分内容。前 4 字节固定为 255、116、79、99，这也是版本 1 的起始 4 字节。后面 4 字节用于表示版本号，当前为版本 2。

Fanout 层

Fanout 层是 Git 的亮点设计，也被称为 Fanout Table（扇表）。在 Fanout 数组中，存储着相关对象的数量，数组下标对应十六进制数。Fanout 数组的最后一个元素存储的是整个 pack 文件中所有对象的总数。

Fanout Table 是整个 Git 检索的核心，借助它可以实现快速查询。其作用是定位 SHA 层数组的起始和终止下标，确定好 SHA 层的范围后，就能够对 SHA 层进行二分查找，而无需对所有对象进行二分查找，大大提高了查找效率。

Fanout 数组共有 256 个元素，恰好对应十六进制的 #0xFF。该数组以 SHA 值的前 2 个字符作为下标（这与 .git/objects 中的松散文件目录名相对应，需将十六进制的目录名转换为十进制数字），数组元素的值表示以这两个字符开头的文件数量，并且这些数量是逐层累加的，即后面数组元素的值包含了前面数组元素所代表的数据个数。

下面举例说明：

1. 若数组下标为 0，且 Fanout[0] = 10，这意味着以 #0x00 开头的 SHA - 1 值的对象总数为 10 个。
2. 若数组下标为 1，且 Fanout[1] = 15，这表示以小于 #0x01 开头的 SHA - 1 值的对象总数为 15 个。结合 Fanout[0] = 10 可知，以 #0x01 开头的 SHA - 1 值的对象数量为（15 - 10）个。

那么，为什么 Git 在设计上会让 Fanout[n] 累加 Fanout[n - 1] 的数量呢？这主要是为了能够快速确定 SHA 层检索的初始位置，避免每次都要对前面所有的 fanout[..n - 1] 数量进行累加操作。

SHA 层

该层存储着所有对象的 SHA - 1 值，并且这些值是按照名称进行排序的。按名称排序的目的是为了能够使用二分搜索算法进行查找，提高查找效率。每个 SHA - 1 值占用 20 字节。

CRC 层

由于文件打包主要是为了解决网络传输问题，而在网络传输过程中，必须通过 CRC（循环冗余校验）进行校验，以避免文件在传输过程中损坏。因此，CRC 数组中存储的是每个对象的 CRC 校验和。

Offset 层

这一层由 4 字节组成，用于表示每个 SHA - 1 文件的偏移量。然而，如果文件大小超过 2G，4 字节将无法表示其偏移量，此时会有以下两种情况：

• 若 4 字节中的第一位（即最高有效位，MSB）为 1，表示文件的偏移量存储在第 6 层（Big File Offset 层）。此时，剩下的 31 位表示文件在 Big File Offset 层中的偏移量。通过 Big File Offset 层，就可以确定对象在 pack 文件中的实际偏移量。
• 若 4 字节中的第一位（MSB）为 0，那么剩下的 31 位直接表示存储对象在 packfile 中的文件偏移量，此时不涉及 Big File Offset 层。

Big File Offset 层

该层专门用于存储大于 2G 的文件的偏移量。当文件大小超过 2G 时，可以通过 Offset 层的最后 31 位确定其在 Big File Offset 层中的位置。Big File Offset 层使用 8 字节来表示对象在 pack 文件中的位置，理论上可以表示 2 的 64 次方大小的文件。

Trailer 层

该层包含 packfile 的校验和以及关联的 idx 文件的校验和，用于确保文件的完整性和准确性。

索引流程

从上述对 index 文件的分层介绍中，我们能深切体会到 Git 设计的精妙之处。Git 索引文件偏移量的查询流程如下：

Git 凭借这种精心设计的分层结构和查询流程，能够高效且准确地定位文件偏移量，为后续的操作提供了坚实的基础。

查询算法

1. 通过 idx 文件查询 SHA-1 对应的偏移量：

   在进行对象检索时，通过 idx 文件来查询特定 SHA-1 所对应的偏移量是关键步骤。具体流程如以下图示所示：

   

   这一过程借助了 idx 文件中各层的有序结构，通过巧妙的算法实现快速查找，从而迅速获取到目标对象在 pack 文件中的偏移位置信息。

2. 在 pack 文件中通过偏移量找到对象：

   当获取到 SHA-1 对应的偏移量后，便可以在 pack 文件中依据该偏移量定位到相应的对象。其操作流程如下：

   

   找到对象后，根据对象的存储类型会有不同的处理方式：

   • 普通存储类型：若定位到的对象属于普通存储类型，那么该对象就是经过 Zlib 压缩后的结果。在这种情况下，直接对其进行解压缩操作，即可获取到对象的原始数据。
   • Delta 类型：对于 Delta 类型的对象，情况相对复杂一些。需要通过递归的方式查出 Delta 的 Base 对象，即找到该对象所基于的基础对象。然后，将 delta data 应用到 base object 上（具体操作可参考 git-apply-delta），从而还原出完整的对象数据。

参考资料

git 大多资料主要介绍是 git 使用，很少系统去讲解底层数据结构和原理。本文通过多个开源代码入手，结合 git 文档，参考相关 git 开发者或相关研究文章，git 邮件列表等。下面是我探究觉得比较可靠的资料文档集。

参考文档

https://stackoverflow.com/questions/8198105/how-does-git-store-files https://www.npmjs.com/package/git-apply-delta https://git-scm.com/book/en/v2/Git-Internals-Packfiles https://codewords.recurse.com/issues/three/unpacking-git-packfiles http://shafiulazam.com/gitbook/7_the_packfile.html http://wiki.jikexueyuan.com/project/git-community-book/packfile.html http://documentup.com/skwp/git-workflows-book http://www.runoob.com/git/git-workspace-index-repo.html http://shafiulazam.com/gitbook/1_the_git_object_model.html http://eagain.net/articles/git-for-computer-scientists/ https://www.kernel.org/pub/software/scm/git/docs/user-manual.html#object-details https://stackoverflow.com/documentation/git/topics https://stackoverflow.com/search?page=2&tab=Votes&q=user%3a1256452%20%5bgit%5d http://git.oschina.net/progit/9-Git-%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86.html#9.5-The-Refspec https://codewords.recurse.com/issues/three/unpacking-git-packfiles http://shafiulazam.com/gitbook/7_the_packfile.html https://w.org/pub/software/scm/git/docs/user-manual.html#object-details

git 源码

• sha1_file.c sha1_object_info_extended 读取对象
• sha1_file.c find_pack_entry_one 从索引中寻找

其他 git 源码

• go-git https://github.com/src-d/go-git
• gitgo https://github.com/ChimeraCoder/gitgo