Git底层数据结构和原理之四：检索模型
本文仅供笔者学习记录之用，侵删
来源：阿里技术公众号，作者 与水
原文：https://mp.weixin.qq.com/s/l5JU9e6_HrS_-ixiBIrqsA
两种git对象
→ cd .git/objects/
git 的对象有两种：
一种是松散对象，就是在如上 .git/objects 的文件夹 03 28 7f ce d0 d5 e6 f9 等，这些文件夹只有 2 个字符开头，其实就是每个文件 SHA-1 值的前 2 个字母，最多有 #OXFF 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-byte "PACK", 4-byte "版本号", 4-byte "Object 条目数"。
- Body 部分主要是一个个 Git 对象依次存储，存储位置在 idx 索引文件中记录改对象在 pack 文件中的偏移量 offset。
- Trailer 部分主要是所有 Objects 的名 (SHA-1）的校验和，为了安全可靠的文件传输。
下面我们看具体的 pack 文件：
从上图可知：通过 idx 索引文件在 pack 文件中定位到对象之后，对象的结构主要 Header 和 Data 两部分。
1、Header 部分
Header 中首 8-bits：1-bit 是 MSB，接着的 3-bits 表示的是当前对象类型，主要有6种存储类型，接着的 4-bits 是用于表示该 Object 展开的 (length) 大小的一部分，只是一部分，完整的大小取决于MSB和接下来的多个 bits，完整算法如下：
- 如果 8-bits 中第一位是 1，表示下一个字节还是 header 的一部分，用于表示该对象展开的大小。
- 如果 8-bits 中第一位是 0，表示从下一个字节开始，将是数据 Data 文件。
- 如果对象类型是 OBJ_OFS_DELTA 类型, 表示的是 Delta 存储，当前 git 对象只是存储了增量部分，对于基本的部分将由接下来的可变长度的字节数用于表示 base object 的距离当前对象的偏移量，接下来的可变字节也是用 1-bit MSB 表示下一个字节是否是可变长度的组成部分。对偏移量取负数，就可知 base 对象在当前对象的前面多少字节。
- 如果对象类型是 OBJ_REF_DELTA 类型，表示的是 Delta 存储，当前 git 对象只是存储了增量部分，对于基本的部分，用 20-bytes 存储 Base Object 的 SHA-1 。
2 Data 部分
经过 Zlib 压缩过的数据。可能是全部数据，也有可能是 Delta 数据，具体看 Header 部分的存储类型，如果是 OBJ_OFS_DELTA 或者 OBJ_REF_DELTA 此处存储的就是增量 (Delta) 数据，此时如果要取得全量数据的话，需要递归的找到最 Base Object，然后 apply delta 数据，在 base object 基础上进行 apply 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) 表示对象的 base object SHA-1 是 cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804，base 对象最大深度 (depth) 为 1，如果cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804 还有引用对象，则改变 depth 为 2。
pack Header 中最后 4-bytes 用于表示的 pack 文件中 objects 的数量，最多 2 的 32 次方个对象，所以一些大的工程中有多个 pack 文件和多个 idx 文件。
文件的 size (文件解压缩后大小) 有什么用呢，这个是为了方便我们进行解压的时候，设置流的大小，也就是方便知道流有多大。这里 size 不是说明下一个文件的偏移量，偏移量都是来自索引文件，见下面 idx：
index 文件
由于 version1 比较简单，下面用 version2 为例子：
分层模式：Header，Fanout,SHA，CRC，Offset，Big File Offset，Trailer。
Header 层
version2 的 Header 部分总共有 8-bytes，version 1 的 header 部分是没有的，前 4-bytes 总是 255, 116, 79, 99 因为这个也是版本 1 的开头四个字节，后面 4-bytes 用于表示的是版本号，在当前就是 version 2。
Fanout 层
fanout 层是 git 的亮点设计，也叫 Fanout Table（扇表）。fanout 数组中存储的是相关对象的数目，数组下标是对应 16 进制数。fanout 最后一个存储的是整个 pack 文件中所有对象的总数量。Fanout Table 是整个 git 检索的核心，通过它我们可以快速进行查询，用于定位 SHA 层的数组起始 - 终止下标，定位好 SHA 层范围之后，就可以对 SHA 层进行二分查找了，而不用对所有对象进行二分查找。
fanout 总共 256 个，刚好是十六进制的 #0xFF。fanout 数组用 SHA 的前面 2 个字符作为下标(对应 .git/objects 中的松散文件目录名，将 16 进制的目录名转换 10 进制数字)，里面值就是用这两个字符开头的文件数量，而且是逐层累加的，后面的数组数量是包含前面数组的数据的个数的一个累加。
举例如下：1）如果数组下标为 0，且 Fanout[0] = 10 代表着 #0x00 开头的 SHA-1 值的总数为 10 个。
2） 如果数组下标为 1，且 Fanout[1] = 15 代表着小于 #0x01 开头的 SHA-1 值的总数为 15 个，从 Fanout[0] = 10 知 Fanout[1] = （15-10）
为什么 git 设计上 Fanout[n] 会累加 Fanout[n-1] 的数量？这个主要是为了快速确定 SHA 层检索的初始位置，而不用每次去把前面所有 fanout[..n-1] 数量进行累加。
SHA 层
是所有对象的 SHA-1 的排序，按照名称排序，按照名称进行排序是为了用二分搜索进行查找。每个 SHA-1 值占 20-bytes。
CRC 层
由于文件打包主要解决网络传输问题，网络传输的时候必须通过 crc 进行校验，避免传输过程中的文件损坏。CRC 数组对应的是每个对象的 CRC 校验和。
Offset 层
是由 4 byte 字节所组成，表示的是每个 SHA-1 文件的偏移量，但是如果文件大于 2G 之后，4 byte 字节将无法表示，此时将：
4 byte 中的第一 bit 就是 MSB，如果是 1 表示的是文件的偏移量是放在第 6 层去存储，此时剩下的 31-bits 将表示文件在 Big File Offset 中的偏移量，也就是图中的，通过 Big File Offset 层 就可以知道对象在 pack 中的 offset。
4 byte 中的第一 bit 就是 MSB，如果是 0 31-bits 表示的存储对象在 packfile 中的文件偏移量，此时不涉及 Big File Offset 层
Big File Offset 层
用于存储大于 2G 的文件的偏移量。如果文件大于 2G，可以通过 offset 层最后 31 bits 决定在 big file offset 中的位置，big file offset 通过 8 bytes 来表示对象在 pack 文件中的位置，理论上可以表示 2 的 64 次方文件大小。
Trailer 层
包含的是 packfile checksum 和关联的 idx 的 checksum。
索引流程
从上面的分层知道 git 设计的巧妙。git 索引文件偏移量的查询流程如下：
查询算法通过 idx 文件查询 SHA-1 对应的偏移量：
在 pack 文件中通过偏移量找到对象：
如果是普通的存储类型。定位到的对象就是用 Zlib 压缩之后的对象，直接解压缩即可。
如果是 Delta 类型需要 递归查出 Delta 的 Base 对象，然后再把 delta data 应用到 base object 上(可参考 git-apply-delta)。
