在我之前的 Git Internal 系列的第一篇《Git Internal - Git 中的 Object 和 Reference》中，我简单介绍了 Git 如何用 object 文件存储 Git 的所有 object，但事实上，这种方法不够高效，它存在三个性能问题：

  1. 大规模读取提交日志时，需要反复读取多个文件才能获取全部信息
  2. 对于大量小修小改的情况，blob 或 tree 之间改动不大，但每次修改都要存储整个 blob 和 tree，从执行性能和存储空间来说都不够高效
  3. 大量小文件降低了对存储空间的有效利用

因此 Git 后来改进了存储方式，通过 git gc 命令可以将多个 object 文件打包成 pack 存储，并增加了两种 DIFF object 来提高读写小规模改动的性能。

在这篇 Blog 中，我将给出读取 pack 文件的方法。

在 Git 文件中，pack 文件存储在 .git/objects/pack/ 目录中，全部以 pack- 开头。每个 pack 由两个文件构成，一个索引文件 .idx，用于 object 的定位，一个 .pack 文件存储 object 的内容。

先从索引文件 .idx 开始讲，Git 的索引文件有两个版本，版本 1 比较简单，文件内容共分四个部分：

  1. 扇出表，共 256 项，每项有 4 个字节的网络序数字构成，用于定位 SHA-1 在索引表中的位置
  2. 索引表，存储所有索引项，每项 24 个字节，前 20 个字节是 object 的 SHA-1，后面 4 个字节是 object 在 .pack 文件中的偏移量（由此可以看出，版本 1 的 .pack 文件不能大于 4 GB，否则无法存储偏移量），网络序存储，所有索引项按照 SHA-1 排序
  3. .pack 文件内容的 SHA-1，20 个字节
  4. 上述所有文件内容的 SHA-1，20 个字节

版本 2 改进了版本 1 中的几个问题，是目前 Git 广泛采用的版本，现在文件内容共分 9 个部分：

  1. 文件签名 \377tOc，4 个字节
  2. 索引文件版本，4 个字节
  3. 扇出表，和版本 1 一致
  4. 索引表，每项 20 个字节，存储所有索引的 SHA-1 部分，按 SHA-1 排序
  5. CRC32 表，每项 4 个字节，顺序与其对应的 SHA-1 顺序一致
  6. 偏移量表，每项 4 个字节，与版本 1 的偏移量不同，版本 2 中的偏移量当最高位为 0 时，低 31 位表示 object 在 .pack 文件中的偏移量，总共能表示 2 GB。当最高位为 1 时，低 31 位表示实际偏移量在扩展偏移量表的位置。
  7. 扩展偏移量表，每项 8 个字节，当偏移量大于 2 GB 时，就会改用扩展偏移量表存储，扩展偏移量可以用 8 个字节表示。
  8. .pack 文件内容的 SHA-1，20 个字节
  9. 上述所有文件内容的 SHA-1，20 个字节

以在 pack 文件中搜索 7105cee64d76781823dbc68f4e154e51e47c3585 为例，其 SHA-1 的第一个字节用数字表示是 113(计算方法是 7 * 16 + 1)，因此取出扇出表第 113 项数据，其值是 41834，还要取出扇出表第 112 项数据（即前一项数据），其值是 41502，这表示 7105cee64d76781823dbc68f4e154e51e47c3585 这个数据的索引项一定位于索引表第 41502 ～ 41834 项中，由于索引表按照 SHA-1 排序，因此可以用二分法找到它在索引表中的位置，例如是 41517。

对于版本 1 的索引文件，直接取出 SHA-1 部分后面 4 个字节就得到了它在 .pack 文件中的位置。如果是版本 2，则需要再取出偏移量表的第 41517 项，还需要判断该偏移量的最高位是否是 0。假设这里的偏移量大于 2 GB，因此最高位是 1，例如是 0x80000005，则需要再次从扩展偏移量表中取出第 5 项，才能得到实际的偏移量。

然后我们再来看看 .pack 文件，.pack 负责存储 object 文件的大小，类型和内容，它的格式比较简单：

  1. 文件签名 PACK，4 个字节
  2. pack 文件版本，4 个字节
  3. object 的数量，4 个字节
  4. 所有 object 大小，类型和内容，对于每项 object，格式是这样的：
    1. N 个字节表示 object 的大小和类型
    2. 对于 OBJ_REF_DELTA 类型，用 20 个字节表示基于的 object 的 SHA-1。 对于 OBJ_OFS_DELTA 类型，用 N 个字节表示基于的 object 的相对位置。 对于其它类型，这段省略
    3. object 的内容，被 deflate 算法压缩

这里首先详细讲下 .pack 文件中表示 object 大小和类型的方法。首先 Git 会根据 object 在索引文件中存储的偏移量找到 object 在 .pack 文件中的位置。对于 object 项的第一个字节，其 1 ～ 4 个位表示 object 的大小，而第 5 ～ 7 位表示 object 的类型，类型的编号和其含义有以下几种：

  • 1: OBJ_COMMIT
  • 2: OBJ_TREE
  • 3: OBJ_BLOB
  • 4: OBJ_TAG
  • 6: OBJ_OFS_DELTA
  • 7: OBJ_REF_DELTA

可以看到前四种是传统的 Git object，后两种是为了提高读取性能和存储性能而设计的增量补丁，增量补丁可以基于任何一种 object 类型也可以基于另一个增量补丁。

如果 object 的大小只能由 4 位来表示（可以最多表示 16 字节），显然是不够的。Git 会判定该字节的最高位是否是 1，如果是的话，会接着读取下一个字节，并将这个字节的 1 ～ 7 位填充 object 大小的高位部分，然后再判定这个字节的最高位是否是 1 来判定是否还要再读取下一个字节，依次循环。

例如当读取的第一个字节是 183，其二进制形式是 10110111，那么可以看到，object 的类型是 011，即 3，表示 OBJ_BLOB，而 0111 表示 object 大小的低位部分，最高位为 1 使得 Git 会继续读取下一个字节。假设下一个字节是 46，二进制形式是 00101110，将 1 ～ 7 位填充在 object 大小的高位部分，这样得到的 object 大小的二进制格式是 01011100111，根据网络序，它所代表的数字是 743，这正是 object 的大小。

接着，如果 type 是 OBJ_REF_DELTA，会紧跟 20 个字节表示所基于的 object 的 SHA-1，这种方法普遍运用于早期的 Git，比较易懂，但是 Git 必须重新在整个 Git Repo 中搜索这个 SHA-1 的 object 的位置，效率比较低下。因此现在的 Git 普遍采用 OBJ_OFS_DELTA 这种增量方法，它的算法是：

  1. 读取文件的下一个字节
  2. 取出文件的第 1 ～ 7 位作为偏移量
  3. 当最新读到的字节的最高位不再是 1 的时候，结束算法，返回得到的偏移量，否则继续
  4. 偏移量 + 1
  5. 偏移量向左移动 7 位（相当于 * 128）
  6. 读取文件的下一个字节，加在之前计算得到的偏移量上作为新的偏移量
  7. 回到 3

将增量补丁的起始位置减去算法得到的偏移量，即可得到补丁所基于的 object 的位置。这种方法的优势在于不用根据 SHA-1 在整个 Git Repo 中搜索，只需要直接从 .pack 文件的另一个位置读出文件即可，不仅效率大大提高了，存储容量也更为节省。

随后部分就是 object 的内容，和传统的存储方法一致，.pack 文件中所有 object 都会被 deflate 算法压缩（和传统存储方法不一致的是，object 的内容中不再包含 object 的类型和大小），因此需要用 inflate 算法解压。必须注意的是，在之前计算得到的 object 的大小并非压缩后的 object 的大小，而是压缩前的。在解压时，Git 通过设定 zlib 的 avail_out 功能来限制 object 解压后的尺寸，至于 zlib 实质上读取了 .pack 文件中多少字节的内容，Git 并不关心。

在了解了 pack 文件的存储方法后，我们还需要掌握如何将增量补丁应用在它所基于的 object 上。正如之前所说，增量文件可以基于任何一种 object 类型也可以基于另一个增量补丁，Git 并不限制补丁链的长度。在应用补丁时，Git 会根据补丁链层层搜索，直到找到一个非增量的 object，然后将整个补丁链放入一个堆栈中，之后挨个取出，应用在最基层的 object 上，最终就能还原出整个 object 的内容了。

Git 采用的增量补丁结构非常易于理解：

  1. N 个字节表示从补丁基于的 object 的大小，这个数据通常只是作为签名验证 patch 的正确性
  2. N 个字节表示补丁本身的大小
  3. 补丁内容

一开始是补丁的元信息部分，两段数据都采用一个共同的算法获取，即读取一个字节，将所读字节的第 1 ～ 7 位填在所得到的尺寸的高位部分，然后根据这个字节的最高位是否是 1 确定是否还有必要读取下一个字节，如果是则循环，反之则结束。

至于补丁的内容部分的算法比较复杂：

  • 首先读取一个补丁字节
  • 当读取的字节的最高位为 1，表示接下来会从基层 object 的数据中复制一定的数据到缓存区，其中第 1 ～ 4 位表示获取到复制的起始点的方法而第 5 ～ 7 位表示获取到复制数据的长度的方法。两种获取方法很类似，从起始点开始，如果右起第 n 个字符为 1，表示接来下读取到的一个字节会是起始点的第 8(n-1)+1 ～ 8n 位。同样的算法也会应用在数据长度上。例如 11011011 表示先读取第 1 ～ 3 个字节，分别复制到起始点数据的第 1 ～ 8 位，第 9 ～ 16 位，第 25 ～ 32 位，再读取两个字节，分别复制到长度数据的第 1 ～ 8 位和第 17 ～ 25 位。
  • 当读取的字节的最高位为 0，表示接下来会从补丁中复制一定长度的数据到缓存区，复制的长度是读取到的字节的第 1 ～ 7 位。
  • 反复循环这个算法直到补丁全部被读取完毕。

最后缓存区的数据就是被还原的 object 内容。

我已经在 GitCafe 上创建了一个项目 Play Git，里面的 read_object.rb 可以在整个 Git Repo 中根据指定的 SHA-1 搜索 object，可以通过

1 ruby read_object.rb sha1 [git_repo_path]

来执行，有兴趣的话可以去试试看。