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

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

multi-pack-index（简称 MIDX）存储对象列表及其到多个 packfile 中的偏移量。它包含

  • packfile 名称的列表。

  • 对象 ID 的排序列表。

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

    • 一个指向第 j 个 packfile 的值 j。

    • 对象在第 j 个 packfile 中的偏移量。

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

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

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

设计细节

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

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

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

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

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

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

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

增量 multi-pack index

随着存储库大小的增长，编写包含所有 packfile 的 multi-pack index (MIDX) 的成本变得更高。 为了解决这个问题，“增量 multi-pack index”功能允许组合 multi-pack index 的“链”。

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

设计状态

目前，增量 multi-pack index 功能缺少两个重要组件

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

    没有任何基本限制可以阻止实现此功能。 为了降低复杂性，该功能从初始实现中省略，但稍后会添加。

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

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

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

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

文件布局

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

$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 链的第一层。 multi-pack-index-$H2.midx文件包含链的第二层，依此类推。

当增量和非增量 MIDX 都存在时，始终首先读取非增量 MIDX。

增量 MIDX 的对象位置

在原始 multi-pack-index 设计中，我们通过它们在存储库的单个 multi-pack-index 中的字典位置（按对象 ID）来引用对象。 在增量 multi-pack-index 设计中，我们通过它们在 MIDX 链中每个组件之间连接的字典顺序中的索引来引用对象。

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

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

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

未来工作

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

  • 如果 multi-pack-index 扩展为存储“稳定的对象顺序”（对于给定的哈希，即使 multi-pack-index 更新，函数 Order(hash) = integer 也保持不变），则 MIDX 位图可以独立于 MIDX 进行更新。

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

相关链接

[0] https://bugs.chromium.org/p/git/issues/detail?id=6 Chromium 工作项：Multi-Pack Index (MIDX)

[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/ multi-pack-index 功能的早期 RFC

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

scroll-to-top