日本語 ▾ トピック ▾ 最新バージョン ▾ multi-pack-index は 2.50.0 で最終更新されました

Git オブジェクトディレクトリには、パックファイル (末尾が ".pack") とパックインデックス (末尾が ".idx") を含む pack ディレクトリがあります。パックインデックスはオブジェクトを検索し、パック内のオフセットに移動する方法を提供しますが、これらはパックファイルとペアでなければなりません。このペアリングはファイル名に依存し、パックインデックスはパックファイルと末尾が異なるだけです。パックインデックスはパックファイルごとに高速な検索を提供しますが、パックファイルの数が増加するにつれてこのパフォーマンスは低下します。これは、省略形がすべてのパックファイルを検査する必要があり、最も最近使用したパックファイルでのミスが増える可能性が高いためです。一部の大きなリポジトリでは、単一のパックファイルに再パックすることは、ストレージスペースや過度の再パック時間のために実現不可能です。

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

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

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

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

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

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

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

    • 疑似パック順のオブジェクトのオプションリスト (MIDX ビットマップで使用)。

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

設計の詳細

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

  • MIDX ファイルを利用するには、core.multiPackIndex 設定がオン (デフォルト) である必要があります。これを false に設定すると、MIDX ファイルが存在しても Git が MIDX ファイルを読み込まなくなります。

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

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

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

  • パックインデックス (.idx ファイル) はパックディレクトリに残っているため、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 のオブジェクト位置

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

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

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

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

インクリメンタル MIDX の疑似パック順序

マルチパック到達可能性ビットマップの元の実装は、gitformat-pack[5] (「マルチパックインデックスの逆インデックス」というセクションを参照) で疑似パック順序を概ね次のように定義していました。

要するに、MIDX の擬似パックは、MIDX によって格納されたパック内のオブジェクトをパック順に並べ、パックを MIDX 順 (優先パックが最初) に配置したものを重複排除して連結したものです。

インクリメンタルMIDX設計では、この定義を拡張して、MIDXチェーンの複数のレイヤーからのオブジェクトを含めます。インクリメンタルMIDXの擬似パック順序は、MIDXチェーンの各レイヤーの擬似パック順序を順に連結することによって決定されます。形式的には、2つのオブジェクト o1 と o2 は次のように比較されます。

  1. o1 が o2 より前の MIDX チェーンのレイヤーに現れる場合、o1 は o2 の前にソートされます。

  2. そうでなければ、o1 と o2 が同じ MIDX レイヤーに現れ、その MIDX レイヤーにベースがない場合、pack(o1) と pack(o2) のいずれかが優先され、もう一方が優先されない場合、優先される方が優先されない方の前にソートされます。ベースレイヤーがある場合 (つまり、MIDX レイヤーがチェーンの最初のレイヤーではない場合)、その MIDX レイヤーのパック順で pack(o1) が先に現れる場合、o1 は o2 の前にソートされます。同様に pack(o2) が先に現れる場合、逆が真です。

  3. そうでなければ、o1 と o2 は同じパック、したがって同じ MIDX レイヤーに現れます。含まれるパックファイル内でのオフセットによって o1 と o2 をソートします。

優先パックはMIDXチェーンのプロパティであり、個々のレイヤー自体のプロパティではないことに注意してください。根本的にはレイヤーごとの優先パックを導入することもできますが、MIDX内のパックセット全体でマルチパックの再利用を実行できるようになった現在では、これはあまり関係ありません。

到達可能性ビットマップとインクリメンタル MIDX

インクリメンタル MIDX チェーンの各レイヤーは、そのオブジェクト (および同じ MIDX チェーンの前のレイヤーからのオブジェクト) を、独自の *.bitmap ファイルに表現することができます。

インクリメンタル MIDX チェーンに属する *.bitmap ファイルの構造は、非インクリメンタル MIDX ビットマップ、または古典的な単一パックビットマップの構造と同一です。オブジェクトはインクリメンタル MIDX の疑似パック順序の末尾に追加されるため (上記参照)、MIDX チェーンの末尾に追記するときにビットマップを拡張することが可能です。

(注: MIDX インクリメンタルレイヤーの連続シーケンスとその *.bitmap ファイルを単一のレイヤーと *.bitmap に圧縮することも同様に可能ですが、これはまだ実装されていません。)

使用されるオブジェクト位置は擬似パック順序内でグローバルであるため、後続のレイヤーは、たとえば、4つのタイプビットマップのそれぞれに m->num_objects_in_base 個の 0 ビットを持つことになります。これは、ビットマップに直接対応するレイヤーに存在するオブジェクトについてのみタイプビットマップエントリを書き込むという事実によるものです)。

また、インクリメンタル MIDX チェーン内で最も新しいレイヤーに属するビットマップのみが、到達可能性クエリにおける興味深いオブジェクトと興味のないオブジェクトに関する到達可能性情報を格納するために使用されることにも注意してください。以前のビットマップレイヤーは、そのレイヤーからのコミットおよび擬似マージビットマップ、およびそのレイヤー内のオブジェクトのタイプレベルビットマップを検索するためにのみ使用されます。

実装を簡素化するため、タイプレベルビットマップは同時に反復され、内部ビットマップ関数の再帰呼び出しを避けるために結果は OR されます。

今後の作業

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

  • パックファイルは、初期名は同じだが ".pack" を ".keep" または ".promisor" に置き換える空のファイルを使用して、「特殊」とマークすることができます。パックファイルに関する情報のフラグを記録するデータオプションのチャンクをマルチパックインデックスに追加できます。これにより、マルチパック環境でのパックメンテナンスに役立つ、repacked や redeltified などの新しい状態が可能になります。また、オブジェクトタイプ (コミット、ツリー、ブロブなど) ごとにパックファイルを整理し、このメタデータを使用してメンテナンスを支援することも役立つかもしれません。

関連リンク

[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/ マルチパックインデックス機能の以前の RFC

[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/ Git Merge 2018 貢献者サミットノート (MIDX の議論を含む)

scroll-to-top