Multi-Pack-Index (MIDX) Design Notes

Gitオブジェクトディレクトリには、パックファイル(packfiles)(接尾辞 .pack)とパックインデックス(pack-indexes)(接尾辞 .idx) を含む pack ディレクトリが含まれています。パックインデックスは、オブジェクトを検索し、パック内のオフセットに移動する方法を提供しますが、これらはパックファイルとペアになっている必要があります。パックインデクスはパックファイルの接尾辞のみが異なるため、このペアリングはファイル名によって異なります。パックインデックスはパックファイルごとの高速ルックアップを提供しますが、略語はすべてのパックファイルを検査する必要があり、最近使用されたパックファイルを見逃す可能性が高いため、パックファイルの数が増えるとこのパフォーマンスは低下します。一部の大規模なリポジトリでは、ストレージスペースや過剰な再パック時間のため、単一のパックファイルに再パックすることはできません。

multi-pack-index(略してMIDX)は、オブジェクトとそのオフセットのリストを複数のパックファイルに格納します。以下を含みます:

パックファイル名のリスト。
オブジェクトIDのソートされたリスト。
以下を含むi番目のオブジェクトIDのメタデータのリスト:
- j番目のパックファイルを参照する値 j 。
- オブジェクトのj番目のパックファイル内のオフセット。
巨大なオフセットが必要な場合は、別の、バージョン2のパックインデックスと同様の巨大オフセットリストを使用します。
- オプションの疑似パック順のオブジェクトのリスト(MIDX ビットマップで使用)。

したがって、我々は任意の数のパックファイルに対して O(log N) 回数でルックアップ可能です。

Design Details

MIDXは、 .git/objects/pack ディレクトリの multi-pack-index という名前のファイルに保存されます。これは、代替のパックディレクトリに保存できます。それは同じディレクトリ内のパックファイルのみを参照します。
MIDX ファイルを使用するには、core.multiPackIndex 構成設定をオン (デフォルト) にする必要があります。 false に設定すると、 Git は MIDX ファイルが存在する場合でも読み取れなくなります。
ファイル形式にはオブジェクトIDハッシュ関数のパラメーターが含まれているため、ハッシュアルゴリズムを将来変更しても、形式を変更する必要はありません。
MIDXは、オブジェクトIDごとに1つのレコードのみを保持します。オブジェクトが複数のパックファイルに表示される場合、MIDXは優先パックファイル内のコピーを選択します。それ以外の場合は、最も最近に変更されたパックファイルから選択します。
MIDXに登録されていないpackディレクトリにパックファイルが存在する場合、それらのパックファイルは packed_git リストと packed_git_mru キャッシュにロードされます。
pack-indexes (.idx ファイル) はpackディレクトリに残っているため、MIDXファイルを削除したり、 core.midx を false に設定したり、情報を失うことなくダウングレードしたりできます。
MIDXファイル形式は、オプションのデータを追加できるチャンクベースのアプローチ(commit-graphファイルと同様)を使用します。

Incremental multi-pack indexes

As repositories grow in size, it becomes more expensive to write a multi-pack index (MIDX) that includes all packfiles. To accommodate this, the "incremental multi-pack indexes" feature allows for combining a "chain" of multi-pack indexes.

Each individual component of the chain need only contain a small number of packfiles. Appending to the chain does not invalidate earlier parts of the chain, so repositories can control how much time is spent updating the MIDX chain by determining the number of packs in each layer of the MIDX chain.

Design state

At present, the incremental multi-pack indexes feature is missing two important components:

The ability to rewrite earlier portions of the MIDX chain (i.e., to "compact" some collection of adjacent MIDX layers into a single MIDX). At present the only supported way of shrinking a MIDX chain is to rewrite the entire chain from scratch without the --split flag.

There are no fundamental limitations that stand in the way of being able to implement this feature. It is omitted from the initial implementation in order to reduce the complexity, but will be added later.
Support for reachability bitmaps. The classic single MIDX implementation does support reachability bitmaps (see the section titled "multi-pack-index reverse indexes" in gitformat-pack(5) for more details).

As above, there are no fundamental limitations that stand in the way of extending the incremental MIDX format to support reachability bitmaps. The design below specifically takes this into account, and support for reachability bitmaps will be added in a future patch series. It is omitted from the current implementation for the same reason as above.

In brief, to support reachability bitmaps with the incremental MIDX feature, the concept of the pseudo-pack order is extended across each layer of the incremental MIDX chain to form a concatenated pseudo-pack order. This concatenation takes place in the same order as the chain itself (in other words, the concatenated pseudo-pack order for a chain {$H1, $H2, $H3} would be the pseudo-pack order for $H1, followed by the pseudo-pack order for $H2, followed by the pseudo-pack order for $H3).

The layout will then be extended so that each layer of the incremental MIDX chain can write a *.bitmap. The objects in each layer’s bitmap are offset by the number of objects in the previous layers of the chain.

File layout

Instead of storing a single multi-pack-index file (with an optional .rev and .bitmap extension) in $GIT_DIR/objects/pack, incremental MIDXs are stored in the following layout:

$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

The multi-pack-index-chain file contains a list of the incremental MIDX files in the chain, in order. The above example shows a chain whose multi-pack-index-chain file would contain the following lines:

$H1
$H2
$H3

The multi-pack-index-$H1.midx file contains the first layer of the multi-pack-index chain. The multi-pack-index-$H2.midx file contains the second layer of the chain, and so on.

When both an incremental- and non-incremental MIDX are present, the non-incremental MIDX is always read first.

Object positions for incremental MIDXs

In the original multi-pack-index design, we refer to objects via their lexicographic position (by object IDs) within the repository’s singular multi-pack-index. In the incremental multi-pack-index design, we refer to objects via their index into a concatenated lexicographic ordering among each component in the MIDX chain.

If objects_nr() is a function that returns the number of objects in a given MIDX layer, then the index of an object at lexicographic position i within, say, $H3 is defined as:

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

(in the C implementation, this is often computed as i + m->num_objects_in_base).

Future Work

multi-pack-indexを使用すると、(非常に大きなリポジトリなど、)特に再パックにコストがかかる場合、または(需要の高いビルドマシンなどで、)予期しないメンテナンス時間が許容できない場合に、多くのパックファイルを使用できます。ただし、multi-pack-indexは毎回完全に書き直す必要があります。フォーマットをインクリメンタルに拡張できるため、書き込みが高速になります。大きな「base」MIDXファイルを指す小さな「tip」マルチパックインデックスを保存することで、オブジェクトのルックアップに必要なバイナリ検索の数を減らしながら、書き込みを高速に保つことができます。
multi-pack-indexが拡張されて「安定したオブジェクトの順序」(関数 Order(hash）= multi-pack-indexが更新されても、特定のハッシュに対して定数である整数)を格納する場合、MIDXとは独立して更新されるMIDXビットマップは以下のようになります。
パックファイルは、初期名を共有するが .pack を .keep または .promisor に置き換える空のファイルを使用して「special」としてマークできます。パックファイルに関する情報のフラグを記録するmulti-pack-indexにオプションのデータチャンクを追加できます。これにより、「repacked」(再パック)や「redeltified」(再削除)などの新しいステータスが可能になり、マルチパック環境でのパックのメンテナンスに役立ちます。パックファイルをオブジェクトタイプ(コミット、ツリー、ブロブなど)で整理し、このメタデータを使用してそのメンテナンスを支援することも役立つ場合があります。