Git
英语 ▾ 主题 ▾ 最新版本 ▾ 多包索引 最后更新于 2.47.0

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

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

  • pack 文件名列表。

  • 排序后的对象 ID 列表。

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

    • 一个值 j，引用第 j 个 pack 文件。

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

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

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

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

设计细节

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

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

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

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

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

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

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

增量多包索引

随着存储库规模的增长，编写包含所有 pack 文件的多包索引 (MIDX) 的成本会越来越高。为了解决这个问题，“增量多包索引”功能允许组合多包索引的“链”。

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

设计状态

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

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

    从根本上讲，没有任何限制阻止实现此功能。为了降低复杂性，它在初始实现中被省略，但将在以后添加。

  • 对可达性位图的支持。经典的单个 MIDX 实现确实支持可达性位图（有关更多详细信息，请参阅 gitformat-pack[5] 中标题为“多包索引反向索引”的部分）。

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

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

    然后扩展布局，以便增量 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 层中对象数量的函数，那么例如在 $H3 中词法位置为 i 的对象的索引定义为：

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

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

未来工作

  • 多包索引允许许多 pack 文件，尤其是在重新打包成本很高（例如非常大的存储库）或无法接受意外的维护时间（例如高需求的构建机器）的情况下。但是，多包索引每次都需要完全重写。我们可以扩展格式使其成为增量的，这样写入速度很快。通过存储一个指向大型“基础”MIDX 文件的小型“提示”多包索引，我们可以保持写入速度快，同时仍然减少查找对象所需的二进制搜索次数。

  • 如果多包索引扩展为存储“稳定对象顺序”（一个函数 Order(hash) = 整数，对于给定的哈希值是恒定的，即使多包索引更新也是如此），那么 MIDX 位图可以独立于 MIDX 更新。

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

相关链接

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

[1] https://lore.kernel.org/git/[email protected]/ 多包索引功能的早期 RFC

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

scroll-to-top