简体中文 ▾ 主题 ▾ 最新版本 ▾ multi-pack-index 上次更新于 2.50.0

Git 对象目录包含一个 pack 目录，其中包含包文件（后缀为 ".pack"）和包索引（后缀为 ".idx"）。包索引提供了一种查找对象及其在包内偏移量的方法，但这些必须与包文件成对出现。这种配对取决于文件名，因为包索引与包文件仅在后缀上有所不同。虽然包索引为每个包文件提供快速查找，但随着包文件数量的增加，这种性能会下降，因为摘要需要检查每个包文件，并且我们更有可能在最近使用的包文件中发生未命中。对于某些大型仓库，由于存储空间或过多的打包时间，将其重新打包成单个包文件是不可行的。

多包索引（简称 MIDX）存储对象列表及其在多个包文件中的偏移量。它包含：

  • 包文件名列表。

  • 对象 ID 的排序列表。

  • 第 i 个对象 ID 的元数据列表，包括：

    • 一个值 j，指向第 j 个包文件。

    • 对象在第 j 个包文件中的偏移量。

  • 如果需要大偏移量，我们使用另一个大偏移量列表，类似于版本 2 包索引。

    • 对象在伪包顺序中的可选列表（与 MIDX 位图一起使用）。

因此，我们可以为任意数量的包文件提供 O(log N) 的查找时间。

设计细节

  • MIDX 存储在 .git/objects/pack 目录中名为 multi-pack-index 的文件中。这可以存储在备用目录的包目录中。它仅引用同一目录中的包文件。

  • 必须启用 core.multiPackIndex 配置设置（这是默认设置）才能使用 MIDX 文件。将其设置为 false 会阻止 Git 读取 MIDX 文件，即使它存在。

  • 文件格式包含对象 ID 哈希函数的参数，因此将来更改哈希算法不需要更改格式。

  • MIDX 每个对象 ID 只保留一条记录。如果一个对象出现在多个包文件中，则 MIDX 会选择首选包文件中的副本，否则从最近修改的包文件中选择。

  • 如果包目录中存在未在 MIDX 中注册的包文件，那么这些包文件将被加载到 packed_git 列表和 packed_git_mru 缓存中。

  • 包索引（.idx 文件）保留在包目录中，以便我们可以删除 MIDX 文件，设置 core.midx 为 false，或降级而不会丢失任何信息。

  • MIDX 文件格式使用基于块的方法（类似于 commit-graph 文件），允许添加可选数据。

增量多包索引

随着仓库规模的增长，编写包含所有包文件的多包索引（MIDX）变得更加昂贵。为了适应这一点，“增量多包索引”功能允许组合一个多包索引的“链”。

链中的每个单独组件只需要包含少量包文件。向链中添加内容不会使链的早期部分失效，因此仓库可以通过确定 MIDX 链的每一层中的包数量来控制更新 MIDX 链所花费的时间。

设计状态

目前，增量多包索引功能缺少两个重要组件：

  • 重写 MIDX 链早期部分的能力（即，将一些相邻的 MIDX 层“压缩”成一个 MIDX）。目前，缩小 MIDX 链的唯一支持方法是从头开始重写整个链，而不使用 --split 标志。

    这方面没有根本性的限制。它被省略在最初的实现中是为了降低复杂性，但将在以后添加。

  • 支持可达性位图。经典的单 MIDX 实现支持可达性位图（有关更多详细信息，请参见 gitformat-pack[5] 中“multi-pack-index reverse indexes”部分）。

    如上所述，将增量 MIDX 格式扩展到支持可达性位图没有任何根本性的限制。下面的设计特别考虑了这一点，并且将在将来的补丁系列中添加对可达性位图的支持。出于同样的原因，它被省略在当前实现中。

    简而言之，为了支持增量 MIDX 功能的可达性位图，伪包顺序的概念被扩展到增量 MIDX 链的每个层，形成一个连接的伪包顺序。这种连接以链本身的顺序进行（换句话说，链 {$H1, $H2, $H3} 的连接伪包顺序将是 $H1 的伪包顺序，然后是 $H2 的伪包顺序，然后是 $H3 的伪包顺序）。

    然后将布局扩展，以便增量 MIDX 链的每一层都可以写入一个 *.bitmap 文件。每一层位图中的对象都通过链中先前图层的对象数量进行偏移。

文件布局

增量 MIDX 不再将单个 multi-pack-index 文件（带有可选的 .rev 和 .bitmap 扩展名）存储在 $GIT_DIR/objects/pack 中，而是采用以下布局：

$GIT_DIR/objects/pack/multi-pack-index.d/
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-chain
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H1.midx
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H2.midx
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H3.midx

multi-pack-index-chain 文件包含链中增量 MIDX 文件的列表，按顺序排列。上面的示例显示了一个链，其 multi-pack-index-chain 文件将包含以下行：

$H1
$H2
$H3

multi-pack-index-$H1.midx 文件包含多包索引链的第一层。multi-pack-index-$H2.midx 文件包含链的第二层，依此类推。

当同时存在增量和非增量 MIDX 时，总是先读取非增量 MIDX。

增量 MIDX 的对象位置

在原始的多包索引设计中，我们通过对象 ID 在仓库的单个多包索引中的字典序位置来引用对象。在增量多包索引设计中，我们通过对象在 MIDX 链中每个组件的连接字典序排序中的索引来引用对象。

如果 objects_nr() 是一个返回给定 MIDX 层中对象数量的函数，那么位于字典序位置 i 的对象在（例如）$H3 中的索引定义为：

objects_nr($H2) + objects_nr($H1) + i

（在 C 实现中，这通常计算为 i + m->num_objects_in_base）。

增量 MIDX 的伪包顺序

多包可达性位图的原始实现定义了 gitformat-pack[5] 中的伪包顺序（参见“multi-pack-index reverse indexes”部分），大致如下：

简而言之，MIDX 的伪包是 MIDX 存储的包中对象的去重连接，按包顺序排列，包按 MIDX 顺序排列（首选包在前）。

在增量 MIDX 设计中，我们将此定义扩展到包含来自 MIDX 链多个层中的对象。增量 MIDX 的伪包顺序是通过按顺序连接 MIDX 链的每个层的伪包顺序来确定的。形式上，两个对象 o1 和 o2 的比较如下：

  1. 如果 o1 出现在 MIDX 链的较早层而不是 o2，则 o1 排在 o2 之前。

  2. 否则，如果 o1 和 o2 出现在同一个 MIDX 层，并且该 MIDX 层没有基础，那么如果 pack(o1) 和 pack(o2) 中的一个被首选而另一个不是，那么首选的排在非首选的前面。如果存在基础层（即 MIDX 层不是链中的第一层），那么如果 pack(o1) 出现在该 MIDX 层的包顺序中更早，则 o1 排在 o2 之前。同样，如果 pack(o2) 出现在更早，则情况相反。

  3. 否则，o1 和 o2 出现在同一个包中，因此在同一个 MIDX 层中。按它们在包含的包文件中的偏移量对 o1 和 o2 进行排序。

请注意，首选包是 MIDX 链的属性，而不是单独的层。从根本上说，我们可以引入每个层的首选包，但这现在不太相关了，因为我们可以跨 MIDX 中的包集执行多包重用。

可达性位图和增量 MIDX

增量 MIDX 链的每一层都可以用自己的 *.bitmap 文件表示其对象（以及同一 MIDX 链中任何先前层的对象）。

属于增量 MIDX 链的 *.bitmap 文件的结构与非增量 MIDX 位图或经典单包位图相同。由于对象被添加到增量 MIDX 的伪包顺序的末尾（见上文），因此可以在 MIDX 链的末尾附加位图。

（注意：也可以将连续的 MIDX 增量层及其 *.bitmap 文件压缩成一个层和 *.bitmap，但这尚未实现。）

使用的对象位置在伪包顺序中是全局的，因此后续层将在其四个类型的位图中具有例如 m->num_objects_in_base 个 0 位。这是因为我们只为位图对应的层中的对象编写类型位图条目）。

另请注意，在可达性查询中，只有增量 MIDX 链中最新层的位图用于存储有趣和不有趣对象的 P 可达性信息。较早的位图层仅用于查找该层中的提交和伪合并位图，以及该层中对象的类型级别位图。

为了简化实现，类型级别位图被同时迭代，并且将它们的结果 OR 起来，以避免递归调用内部位图函数。

未来工作

  • 如果多包索引被扩展以存储“稳定的对象顺序”（一个对于给定哈希来说是常数的函数 Order(hash) = integer，即使多包索引被更新），那么 MIDX 位图可以独立于 MIDX 进行更新。

  • 可以通过空文件将包文件标记为“特殊”，这些文件共享初始名称，但将 ".pack" 替换为 ".keep" 或 ".promisor"。我们可以向多包索引添加一个可选数据块，该数据块记录有关包文件的信息标志。这允许新的状态，例如 repacked 或 redeltified，这有助于在多包环境中进行包维护。按对象类型（提交、树、blob 等）组织包文件并使用这些元数据来帮助维护也可能很有用。

相关链接

[0] https://bugs.chromium.org/p/git/issues/detail?id=6 Chromium 工作项：多包索引 (MIDX)

[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/ 多包索引功能的前期 RFC

[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/ Git Merge 2018 贡献者峰会笔记（包括 MIDX 讨论）