Git
English ▾ トピック ▾ 最新バージョン ▾ マルチパックインデックスは2.47.0で最後に更新されました

Gitオブジェクトディレクトリには、パックファイル（接尾辞「.pack」）とパックインデックス（接尾辞「.idx」）を含むpackディレクトリが含まれています。パックインデックスは、オブジェクトを検索し、パック内のオフセットに移動する方法を提供しますが、これらはパックファイルとペアでなければなりません。このペアリングはファイル名に依存しており、パックインデックスはパックファイルとの接尾辞のみが異なります。パックインデックスはパックファイルごとに高速な検索を提供しますが、パックファイルの数が増えるにつれてこのパフォーマンスは低下します。なぜなら、省略形はすべてのパックファイルを検査する必要があり、最近使用したパックファイルでミスが発生する可能性が高くなるからです。大規模なリポジトリの場合、ストレージ容量または過剰な再パック時間のために、単一のパックファイルに再パックすることは実行不可能です。

マルチパックインデックス（略してMIDX）は、オブジェクトのリストとその複数のパックファイルへのオフセットを格納します。これには以下が含まれます。

  • パックファイル名のリスト。

  • ソートされたオブジェクトIDのリスト。

  • i番目のオブジェクトIDのメタデータのリスト（以下を含む）。

    • j番目のパックファイルを指す値j。

    • オブジェクトのj番目のパックファイル内のオフセット。

  • 大きなオフセットが必要な場合は、バージョン2のパックインデックスと同様の大きなオフセットの別のリストを使用します。

    • 擬似パック順序のオブジェクトのオプションのリスト（MIDXビットマップで使用）。

したがって、任意の数のパックファイルに対してO(log N)の検索時間を提供できます。

設計の詳細

  • MIDXは、.git/objects/packディレクトリにあるmulti-pack-indexという名前のファイルに格納されます。これは代替のpackディレクトリに格納することもできます。これは、同じディレクトリ内のパックファイルのみを参照します。

  • MIDXファイルを使用するには、core.multiPackIndex設定をオンにする必要があります（デフォルト）。これをfalseに設定すると、MIDXファイルが存在していても、GitはMIDXファイルを読み取りません。

  • ファイル形式にはオブジェクトIDハッシュ関数のパラメータが含まれているため、ハッシュアルゴリズムの将来の変更で形式を変更する必要はありません。

  • MIDXはオブジェクトIDごとに1つのレコードのみ保持します。オブジェクトが複数のパックファイルに表示される場合、MIDXは優先されるパックファイルのコピーを選択し、そうでない場合は、最後に変更されたパックファイルから選択します。

  • MIDXに登録されていないパックファイルがpackディレクトリに存在する場合は、それらのパックファイルがpacked_gitリストとpacked_git_mruキャッシュにロードされます。

  • パックインデックス（.idxファイル）はpackディレクトリに残っているため、MIDXファイルを削除したり、core.midxをfalseに設定したり、情報損失なしでダウングレードできます。

  • MIDXファイル形式はチャンクベースのアプローチ（コミットグラフファイルと同様）を使用しており、オプションのデータを追加できます。

増分マルチパックインデックス

リポジトリのサイズが増加するにつれて、すべてのパックファイルを含むマルチパックインデックス（MIDX）の書き込みがより高価になります。「増分マルチパックインデックス」機能により、マルチパックインデックスの「チェーン」を組み合わせることができます。

チェーンの個々のコンポーネントは、少数のパックファイルのみを含める必要があります。チェーンへの追加はチェーンの以前の部分を無効にしないため、リポジトリはMIDXチェーンのレイヤー数によってMIDXチェーンの更新に費やす時間を制御できます。

設計の状態

現在、増分マルチパックインデックス機能には2つの重要なコンポーネントがありません。

  • MIDXチェーンの以前の部分を書き直す機能（つまり、隣接するMIDXレイヤーのいくつかのコレクションを単一のMIDXに「圧縮」する機能）。現在、MIDXチェーンを縮小する唯一サポートされている方法は、--splitフラグなしでチェーン全体を最初から書き直すことです。

    この機能を実装する妨げとなる根本的な制限はありません。複雑さを軽減するために最初のインプリメンテーションから省略されていますが、後で追加されます。

  • 到達可能性ビットマップのサポート。従来の単一MIDX実装は到達可能性ビットマップをサポートしています（詳細については、gitformat-pack[5]の「マルチパックインデックス逆インデックス」というセクションを参照してください）。

    上記のように、増分MIDX形式を到達可能性ビットマップをサポートするように拡張する妨げとなる根本的な制限はありません。以下の設計では、これを特に考慮しており、到達可能性ビットマップのサポートは将来のパッチシリーズで追加されます。上記と同じ理由で、現在のインプリメンテーションから省略されています。

    簡単に言うと、増分MIDX機能で到達可能性ビットマップをサポートするには、擬似パック順序の概念が増分MIDXチェーンの各レイヤーに拡張され、連結された擬似パック順序を形成します。この連結はチェーン自体と同じ順序で行われます（つまり、{$H1, $H2, $H3}チェーンの連結された擬似パック順序は、$H1の擬似パック順序、続いて$H2の擬似パック順序、続いて$H3の擬似パック順序になります）。

    その後、レイアウトが拡張され、増分MIDXチェーンの各レイヤーが*.bitmapを書き込めるようになります。各レイヤーのビットマップのオブジェクトは、チェーンの前のレイヤーのオブジェクト数だけオフセットされます。

ファイルレイアウト

$GIT_DIR/objects/packに単一のmulti-pack-indexファイル（オプションの.revおよび.bitmap拡張子付き）を格納する代わりに、増分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が最初に読み取られます。

増分MIDXのオブジェクトの位置

元のマルチパックインデックス設計では、リポジトリの単一のマルチパックインデックス内の辞書順の位置（オブジェクトIDによる）を介してオブジェクトを参照します。増分マルチパックインデックス設計では、MIDXチェーンの各コンポーネント間の連結された辞書順へのインデックスを介してオブジェクトを参照します。

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

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

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

今後の作業

  • マルチパックインデックスは、特に再パックがコストの高い（非常に大きなリポジトリなど）場合、または予期しないメンテナンス時間が許容できない（需要の高いビルドマシンなど）コンテキストで、多くのパックファイルを許可します。ただし、マルチパックインデックスは毎回完全に書き直す必要があります。形式を増分的に拡張して、書き込みを高速化できます。大きな「基本」MIDXファイルを指す小さな「先端」マルチパックインデックスを格納することにより、オブジェクトルックアップに必要なバイナリ検索の数を減らしながら、書き込みを高速に保つことができます。

  • マルチパックインデックスが「安定したオブジェクト順序」（マルチパックインデックスが更新されても、特定のハッシュに対して一定の関数Order(hash) = integer）を格納するように拡張された場合、MIDXビットマップはMIDXとは独立して更新できます。

  • パックファイルは、同じ名前を共有しているが「.pack」を「.keep」または「.promisor」に置き換えた空のファイルを使用して、「特殊」なものとしてマークできます。パックファイルに関する情報のフラグを記録するオプションのデータチャンクをマルチパックインデックスに追加できます。これにより、再パックまたは再デルタ化など、マルチパック環境でのパックメンテナンスに役立つ新しい状態が許可されます。オブジェクトの種類（コミット、ツリー、ブロブなど）別にパックファイルを整理し、このメタデータを使用してメンテナンスを支援することも役立つ場合があります。

関連リンク

[0] https://bugs.chromium.org/p/git/issues/detail?id=6 マルチパックインデックス（MIDX）に関するChromium作業項目

[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/ マルチパックインデックス機能の以前のRFC

[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/ Git Merge 2018 参加者サミットノート（MIDXに関する議論を含む）

scroll-to-top