Git Commit-Graph Design Notes

Git は、以下のような多くの理由でコミットグラフをたどります:

コミット履歴の一覧表示とフィルタリング。
マージベースの計算。

これらの操作は、コミット数が増えるにつれて遅くなる可能性があります。マージベースの計算は、「merge-base」や「status」などの多くのユーザー向けコマンドに表れ、履歴の形状によっては計算に数分かかる場合があります。

ここでは主に2つのコストが発生します。

コミットの解凍(decompressing)と解析(parsing)。
トポロジー順序の制約を満たすためのグラフ全体のウォーク。

The commit-graph file is a supplemental data structure that accelerates commit graph walks. If a user downgrades or disables the core.commitGraph config setting, then the existing object database is sufficient. The file is stored as "commit-graph" either in the .git/objects/info directory or in the info directory of an alternate.

コミットグラフファイルには、コミットグラフの構造と、グラフウォークを高速化するための追加のメタデータが格納されます。コミットOIDを辞書順でリストすることにより、各コミットの整数位置を識別し、それらの整数位置を使用してコミットの親を参照できます。私達は二分探索を使用して最初のコミットを見つけ、ウォーク中の高速ルックアップのために整数位置を使用します。

利用者は、グラフからコミットに関する以下の情報を取得できます:

コミットOID。
親達のリストとその整数位置。
コミット日付。
ルートツリーのOID。
世代番号(定義は下記参照)。

値 1 ～ 4 は、 parse_commit_gently() の要件を満たします。

世代番号には以下の2つの定義があります: 1. 修正コミッター日付(世代番号 v2) 2. トポロジーレベル(世代番号 v1)

以下のように、コミットの「修正コミッター日付」を再帰的に定義します:

親のないコミット(ルートコミット)には、そのコミッター日付に等しい修正コミッター日付があります。
少なくとも1つの親を持つコミットは、そのコミットのコミッター日付の最大値に等しく、かつ、そのコミットの親の間で最大の修正コミッター日付より大きい、修正コミッター日付を持っています。
特殊な場合として、タイムスタンプがゼロのルートコミットは、GENERATION_NUMBER_ZERO (つまり、計算されていない修正コミット日付) と区別できるように、修正コミット日は 1 に設定されています。

以下のようにコミットの「トポロジーレベル」を再帰的に定義します:

親のないコミット(ルートコミット)のトポロジーレベルは 1 です。
少なくとも1つの親を持つコミットは、そのコミットの親の間で最大のトポロジーレベルよりも1つ高いトポロジーレベルを持ちます。

同様に、コミット A のトポロジーレベルは、A からルートコミットまでの最長パスの長さよりも 1 つ長くなります。再帰的な定義は、計算と以下の特徴の観察を利用するのが簡単です:

A と B がそれぞれ世代番号 N と M のコミットであり、N ⇐ M の場合、A は B に到達できません。つまり、B は A よりもルートコミットから離れているため、B が A の祖先ではないことが検索せずにわかります。
逆に、A が B の祖先であるかどうかを確認する場合、ウォーク境界上のすべてのコミットの世代番号が最大で N になるまで、コミットをウォークするだけで済みます。世代番号でシードされた優先キュー(priority queue seeded by generation numbers)を使用してコミットをウォークすると、常に最大の世代番号で境界コミットを展開し、停止条件を簡単に検出できます。

特徴は世代番号の両方のバージョンに適用されます。つまり、修正されたコミッターの日付とトポロジーレベルの両方です。

この特徴を使用すると、コミットをたどってトポロジー関係を決定するのにかかる時間を大幅に短縮できます。世代番号がない場合、一般的なヒューリスティックは以下のようになります:

A と B がそれぞれコミット時間 X と Y でコミットされており、X < Y の場合、A は「おそらく」 B に到達できません。

修正コミット日付がない場合(Git の古いバージョンや世代混合のグラフチェーンなど)、現在、このヒューリスティックは、計算がクロックスキューのためにトポロジー関係に違反することが許可されている場合に常に使用されます (デフォルトの順序での「git log」など)。ただし、トポロジーの順序が必要な場合は使用されません (マージベース計算、「git log --graph」など)。

In practice, we expect some commits to be created recently and not stored in the commit-graph. We can treat these commits as having "infinite" generation number and walk until reaching commits with known generation number.

コミットグラフファイルにないコミットをマークするには、マクロ GENERATION_NUMBER_INFINITY を使用します。世代番号を計算しないバージョンの Git によってコミットグラフファイルが書き込まれた場合、それらのコミットには、マクロ GENERATION_NUMBER_ZERO = 0 で表される世代番号が含まれます。

コミットグラフファイルは到達可能な状態で閉じられているため、すべてのコミットで以下のより弱い条件を保証できます:

A と B がそれぞれ世代番号 N と M のコミットであり、N < M の場合、A は B に到達できません。

注意: 完全に計算された世代番号がある場合、厳密な不等式(the strict inequality)が不等式(the inequality)とどのように異なるかに注意してください。厳密な不等式(the strict inequality)を使用すると、いくつかの余分なコミットが実行される可能性がありますが、世代番号 *_INFINITY または世代番号 *_ZERO のコミットを扱える単純さは価値があります。

マクロ GENERATION_NUMBER_V1_MAX = 0x3FFFFFFF は、トポロジーレベル (世代番号 v1) が少なくともこの値になるように計算されるコミットに使用します。この値は、トポロジーレベルで使用できる 30 ビットを使用してコミットグラフファイルに保存できる最大値であるため、この値に制限します。これは、コミットが親の世代番号と同じ世代番号を持つことができるもう一つのケースを示しています。

Design Details

コミットグラフファイルは、.git/objects/info ディレクトリの「commit-graph」という名前のファイルに保存されます。これは、代替の info ディレクトリに保存できます。
グラフファイルを使用するには、 core.commitGraph 構成設定をオンにする必要があります。
ファイル形式には、オブジェクトIDハッシュ関数のパラメーターが含まれているため、今後ハッシュアルゴリズムを変更しても、形式を変更する必要はありません。
コミットグラフト(grafts;接ぎ木)と置換オブジェクト(replace objects)は、コミット履歴の形状を変更することができます。置換オブジェクトは、 --no-replace-objects を使用してリアルタイム(on the fly)で有効/無効にすることもできます。これにより、特に世代番号を計算するときに、コミット ID の可能な両方の解釈を保存することが難しくなります。コミットグラフは、置換オブジェクト(replace-objects)またはグラフト(grafts;接ぎ木)が存在する場合、読み書きされません。
浅いクローン(shallow clones)は、親を削除することでコミットのグラフト(grafts;接ぎ木)を作成します。これにより、コミットグラフは、これらのコミットの世代番号が 1 であると考えるようになります。これらのコミットが浅くされていない場合(unshallow)、それらの世代番号は無効になります。浅いクローンはコミット履歴を非常に小さなコミットのセットに制限することを目的としているため、コミットグラフ機能はこれらのクローンにはあまり役に立ちません。浅いコミットが存在する場合、コミットグラフは読み書きされません。

Commit Graphs Chains

通常、リポジトリはほぼ一定の速度(velocity)(1日あたりnコミット)で成長します。時間の経過とともに、フェッチ操作によって追加されるコミットの数は、完全な履歴のコミットの数よりもはるかに少なくなります。コミットグラフの「チェーン」を作成することで、コミット履歴全体を書き換えることなく、新しいコミットデータを高速に書き込むことができます — 少なくともほとんどの場合はそうです。

File Layout

コミットグラフチェーンは複数のファイルを使用し、固定の命名規則を使用してこれらのファイルを整理します。各コミットグラフファイルには、 $OBJDIR/info/commit-graphs/graph-{hash}.graph という名前があります。ここで、{hash} は、そのファイルのフッターに格納されている16進数値のハッシュです(これは、そのハッシュの前のファイルの内容のハッシュです)。コミットグラフファイルのチェーンの場合、$OBJDIR/info/commit-graphs/commit-graph-chain にあるプレーンテキストファイルには、ファイルのハッシュが「最低」(lowest)から「最高」(highest)の順に含まれています。

例えば、 commit-graph-chain ファイルが以下の行達を含んでいるのならば

``` ```

コミットグラフチェインは以下の図のようになります:

+-----------------------+
|  graph-{hash2}.graph  |
+-----------------------+
         |
+-----------------------+
|                       |
|  graph-{hash1}.graph  |
|                       |
+-----------------------+
         |
+-----------------------+
|                       |
|                       |
|                       |
|  graph-{hash0}.graph  |
|                       |
|                       |
|                       |
+-----------------------+

X0 を graph-{hash0}.graph のコミット数、 X1 を graph-{hash1}.graph のコミット数、 X2 を graph-{hash2}.graph のコミット数とします。あるコミットが graph-{hash2}.graph の i 番目の位置にある場合、私達はこれをコミット位置 (X0 + X1 + i) であると解釈し、それを「グラフの位置」(graph position)として使用します。 graph-{hash2}.graph のコミットは、これらの位置を使用して、 graph-{hash1}.graph または graph-{hash0}.graph にある親を参照します。半開間隔 [0, X0), [X0, X0 + X1), [X0 + X1, X0 + X1 + X2) の区間に含まれることを確認することにより、位置 j の任意のコミットに移動できます(訳注: 半開区間 [a, b) は {x: a ≦ x < b} を表す)。

各コミットグラフファイル(ベースの graph-{hash0}.graph を除く)には、下位層のすべてのファイルのハッシュを指定するデータが含まれています。上記の例では、graph-{hash1}.graph には {hash0} が含まれ、 graph-{hash2}.graph には {hash0} と {hash1} が含まれます。

Merging commit-graph files

書き込みのたびに新しいコミットグラフファイルを追加しただけでは、多数のコミットグラフファイルを介して線形検索を実行するという問題が発生します。代わりに、私達はマージ戦略を使用して、スタック(the stack)が何時に幾つのレベルを折りたたむ必要があるかを決定します。

下の図は、そのような折りたたみを示しています。新しいコミットのセットが追加されると、ファイルが graph-{hash1} に折りたたまれるべきかどうかがマージ戦略によって決定されます。したがって、新しいコミット、graph-{hash2} のコミット、および graph-{hash1} のコミットは、新しい graph-{hash3} ファイルに結合する必要があります。

                            +---------------------+
                            |                     |
                            |    (new commits)    |
                            |                     |
                            +---------------------+
                            |                     |
 +-----------------------+  +---------------------+
 |  graph-{hash2}        |->|                     |
 +-----------------------+  +---------------------+
          |                 |                     |
 +-----------------------+  +---------------------+
 |                       |  |                     |
 |  graph-{hash1}        |->|                     |
 |                       |  |                     |
 +-----------------------+  +---------------------+
|                  tmp_graphXXX
+-----------------------+
|                       |
|                       |
|                       |
|  graph-{hash0}        |
|                       |
|                       |
|                       |
+-----------------------+

この処理中に、書き込みコミットが結合、ソートされ、内容が一時ファイルに書き込まれますが、すべて commit-graph-chain.lock ロックファイルが保持されます。ファイルがフラッシュされると、計算された {hash3} に従って名前を graph-{hash3} に変更します。最後に、新しいチェーンデータを commit-graph-chain.lock に書き込みます:

``` ```

そして、ロックファイルをクローズします。

Merge Strategy

高さ N のコミットグラフスタックに存在しない一連のコミットを書き込む場合、デフォルトでレベル N + 1 で新しいファイルを作成します。次に、2 つの条件のいずれかが保持される場合、 N 番目のレベルとマージすることを決定します:

--size-multiple=<X> が指定されているかまたは X = 2 であり、かつ、レベル N のコミット数がレベル N + 1 のコミット数の X 倍未満です。
--max-commits=<C> の C がゼロ以外で指定されており、かつ、レベル N+1 のコミット数が C コミットより多い。

この決定はレベルをカスケードします。レベルをマージすると、次のレベルと比較する新しいコミットのセットが作成されます。

最初の条件として、レベルの数がコミットの総数に対して対数になるように制限します。 2番目の条件は、 commit-graph ファイルではなく graph-{hashN} ファイル内のコミットの総数を制限し、スタックがマージされ、別のプロセスが前のスタックを部分的にしか読み取らない場合の重大なパフォーマンスの問題を防ぎます。

マージ戦略の値 (サイズ倍数の場合は 2、コミットの最大数の場合は 64,000) を構成設定に抽出して、完全な柔軟性を得ることができます。

Handling Mixed Generation Number Chains

世代番号 v2 と世代データチャンクの導入により、以下のシナリオが可能になります:

「新しい」Git は、修正されたコミット日付でコミットグラフを書き込みます。
「古い」Git は、修正されたコミット日付無しに分割コミットグラフを一番上に書き込みます。

各レイヤーから利用可能な最新の世代番号を使用するという素朴なアプローチは、期待に反することにつながります。下位レイヤーは、上位レイヤーのトポロジーレベルよりもはるかに長い修正されたコミット日付を使用します。このため、Git は最上位レイヤーを検査して、レイヤーに修正されたコミット日付がないかどうかを確認します。このような場合、Git は世代番号にトポロジーレベルのみを使用します。

分割コミットグラフに新しいレイヤーを書き込むとき、最上位レイヤーに修正されたコミット日付が書き込まれている場合は、修正コミット日付を書き込みます。これにより、レイヤーが修正コミット日付を持っている場合、下位のすべてのレイヤーも修正コミット日付を持っている必要があります。

レイヤーのマージ時に、マージされたレイヤーが修正コミット日付を持っているかどうかは考慮しません。代わりに、新しいレイヤーの下のレイヤーが修正コミット日付を持っている場合、新しいレイヤーも修正コミット日付を持ちます。

レイヤーの書き込みまたはマージ時に、新しいレイヤーが唯一のレイヤーである場合、互換性のあるバージョンの Git によって書き込まれると、修正コミット日付を持ちます。したがって、分割コミットフラフを単一のファイルとして書き換え(--split=replace)すると、修正コミット日付を持つ単一のレイヤーが作成されます。

新しい先端ファイル(tip file)が書き込まれた後、いくつかの graph-{hash} ファイルがチェーンの一部でなくなる可能性があります。最終的には、これらのファイルをディスクから削除することが重要です。削除が遅れる主な理由は、別のプロセスが commit-graph-chain ファイルを書き換える前に読み取り、削除後に graph-{hash} ファイルを探す可能性があるためです。

古い分割コミットグラフが参照されなくなった後もしばらく保持できるようにするために、参照されなくなったときにファイルの変更時刻を更新します。次に、$OBJDIR/info/commit-graphs/ ディレクトリをスキャンして、変更時刻が所定の有効期限よりも古い graph-{hash} ファイルを探します。この期限のデフォルトはゼロですが、コマンドライン引数または構成設定を使用して変更できます。

Chains across multiple object directories

代替(alternates)を伴うリポジトリでは、ローカルオブジェクトディレクトリから始めて各代替(alternate)で commit-graph-chain ファイルを探します。存在する最初のファイルは、チェーンを定義します。チェーンファイル内の各 {hash} に対して graph-{hash} ファイルを探すとき、ホストディレクトリに対して同一パターンに従います。

これにより、コミットグラフをフォークネットワーク(a fork network)内の複数のフォークに分割できます。典型的なケースは、多くの小さなフォークを持つ大きな「ベース」レポジトリです。

ベースリポジトリが利用されていくつれて、コミットグラフチェーンはフォークよりも頻繁に更新およびマージされる可能性があります。フォークがベースリポジトリの後にコミットグラフを更新する場合は、コミットグラフチェーンをベースリポジトリの新しいチェーンに「育て直し」(reparent)する必要があります。各 graph-{hash} ファイルを読み取るとき、それを含むオブジェクトディレクトリを追跡します。新しいコミットフラフファイルの書き込み中に、ソースオブジェクトディレクトリの変更を確認し、そのソースの commit-graph-chain ファイルを読み取り、それらのファイルに基づいて新しいファイルを作成します。この「育て直し」操作では、新しいベースファイルに対してすべてのファイルが無効であるため、必然的にフォークのすべてのレベルを折りたたむ必要があります。

このシナリオで「参照されていない」(unreferenced) graph-{hash}.graph ファイルをクリーンアップするときは注意が必要です。カスタム環境に適切な設定を定義するのは、ユーザーの責任です:

ベースリポジトリでマージをならす時、参照されていないファイルがフォークリポジトリからのチェーンによって参照されたままになるかもしれません。
有効期限は、すべてのフォークでコミットグラフチェーンを再計算して新しいベースファイルに「育て直し」をする時期になるような時間の長さに設定する必要があります。
コミットグラフチェーンがベースで更新された場合、フォークはそのチェーンが更新されてそれらのファイルを参照するまで、新しいチェーンにアクセスできません。 (これは将来変更される可能性があります。[5] )