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

リポジトリーのサイズが大きくなると、全てのパックファイルを包含するマルチパック・インデックス(MIDX)へ書き込みコストが増大します。これに対応するため、「インクリメンタル・マルチパック・インデックス」機能により、マルチパック・インデックスのチェーン(chain;連なり)を結合することが可能になります。

チェーンの各個別のコンポーネントは、少数のパックファイルのみを含む必要があります。チェーンに追加しても、チェーンの以前の部分が無効になることはありません。そのため、リポジトリーは、 MIDX チェーンの各レイヤーに含まれるパックファイルの数を決めることで、 MIDXチェーンの更新に費やす時間を制御できます。

Design state

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

MIDX チェーンで初期に作られた部分を書き直す能力(つまり、隣接する MIDX レイヤーの一部を単一のMIDXに「圧縮」する能力)。現在のところ、 MIDX チェーンを縮小する唯一のサポートされている方法は、 --split フラグなしでチェーン全体をイチから書き直すことです。

この機能を導入する上で根本的な制限は存在しません。初期の実装では複雑さを軽減するために省略されていますが、今後追加される予定です。
到達可能性ビットマップ(reachability bitmaps)のサポート。従来の単一の MIDX 実装では到達可能性ビットマップをサポートしています(詳細は gitformat-pack(5) の「multi-pack-index reverse indexes」セクション参照)。

上記と同様に、インクリメンタルMIDX形式を拡張して到達可能性ビットマップをサポートする上で、根本的な制限は存在しません。以下の設計ではこの点を特に考慮しており、到達可能性ビットマップのサポートは将来のパッチ・シリーズで追加される予定です。現在の実装では、上記と同じ理由で省略されています。

簡潔に言うと、インクリメンタルMIDX機能で到達可能性ビットマップをサポートするために、疑似パック順序の概念をインクリメンタルMIDXチェーンの各レイヤーに拡張し、連結された疑似パック順序を形成します。この連結はチェーン自体の順序と同じ順で行われます(言い換えると、チェーン {$H1, $H2, $H3} の連結された疑似パック順序は、 $H1 の疑似パック順序に続き、 $H2の疑似パック順序、そして$H3の疑似パック順序、となります)。

レイアウトは、インクリメンタルMIDXチェーンの各レイヤーが *.bitmap へ書き込みできるように拡張されます。各レイヤーのビットマップに含まれるオブジェクトは、そのチェーンの前のレイヤーにあるオブジェクトの数だけオフセットされます。

File layout

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

$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 ファイルには、チェーンの2番目のレイヤーが含まれ、以降も同様です。

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

Object positions for incremental MIDXs

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

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

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

(C 言語での実装では、これは多くの場合 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」(再削除)などの新しいステータスが可能になり、マルチパック環境でのパックのメンテナンスに役立ちます。パックファイルをオブジェクトタイプ(コミット、ツリー、ブロブなど)で整理し、このメタデータを使用してそのメンテナンスを支援することも役立つ場合があります。