Multi-Pack-Index (MIDX) Design Notes

現在、 インクリメンタル・マルチパック・インデックス機能には以下の 2 つの重要なコンポーネントが欠けています:

単一の multi-pack-index ファイル(オプションで .rev や .bitmap 拡張子付き)を $GIT_DIR/objects/pack に保存する代わりに、 インクリメンタル MIDX は 以下のレイアウトで保存されます:

multi-pack-index-chain ファイルには、 チェーン内のインクリメンタル MIDX ファイルのリストが順番に記載されています。 上の例では、 multi-pack-index-chain ファイルには以下の行が含まれます:

multi-pack-index-$H1.midx ファイルには、 マルチパック・インデックス・チェーンの最初のレイヤーが含まれています。 multi-pack-index-$H2.midx ファイルには、 チェーンの2番目のレイヤーが含まれ、 以降も同様です。

インクリメンタル MIDX と非インクリメンタル MIDX の両方が存在する場合、 常に非インクリメンタルMIDXが最初に読み込まれます。

オリジナルのマルチパック・インデックスの設計では、 リポジトリーの単一のマルチパック・インデックス内で、 オブジェクトIDによる辞書順(lexicographic)の位置を参照してオブジェクトを指定します。 インクリメンタル・マルチパック・インデックスの設計では、 MIDX チェーンの各コンポーネント間で、 連結された辞書順のインデックスを介してオブジェクトを参照します。

objects_nr() が指定された MIDX レイヤーのオブジェクト数を返す関数であるとした場合、 たとえば $H3 内で辞書順の位置 i にあるオブジェクトのインデックスは以下のように定義されます:

(C 言語での実装では、 これは多くの場合 i + m->num_objects_in_base として実装されます)。

The original implementation of multi-pack reachability bitmaps defined the pseudo-pack order in gitformat-pack(5) (see the section titled "multi-pack-index reverse indexes") roughly as follows:

In the incremental MIDX design, we extend this definition to include objects from multiple layers of the MIDX chain. The pseudo-pack order for incremental MIDXs is determined by concatenating the pseudo-pack ordering for each layer of the MIDX chain in order. Formally two objects o1 and o2 are compared as follows:

Note that the preferred pack is a property of the MIDX chain, not the individual layers themselves. Fundamentally we could introduce a per-layer preferred pack, but this is less relevant now that we can perform multi-pack reuse across the set of packs in a MIDX.

Each layer of an incremental MIDX chain may have its objects (and the objects from any previous layer in the same MIDX chain) represented in its own *.bitmap file.

The structure of a *.bitmap file belonging to an incremental MIDX chain is identical to that of a non-incremental MIDX bitmap, or a classic single-pack bitmap. Since objects are added to the end of the incremental MIDX’s pseudo-pack order (see above), it is possible to extend a bitmap when appending to the end of a MIDX chain.

(Note: it is possible likewise to compress a contiguous sequence of MIDX incremental layers, and their *.bitmap files into a single layer and *.bitmap, but this is not yet implemented.)

The object positions used are global within the pseudo-pack order, so subsequent layers will have, for example, m->num_objects_in_base number of 0 bits in each of their four type bitmaps. This follows from the fact that we only write type bitmap entries for objects present in the layer immediately corresponding to the bitmap).

Note also that only the bitmap pertaining to the most recent layer in an incremental MIDX chain is used to store reachability information about the interesting and uninteresting objects in a reachability query. Earlier bitmap layers are only used to look up commit and pseudo-merge bitmaps from that layer, as well as the type-level bitmaps for objects in that layer.

To simplify the implementation, type-level bitmaps are iterated simultaneously, and their results are OR’d together to avoid recursively calling internal bitmap functions.