Git
English ▾ トピック ▾ 最新バージョン ▾ gitpacking 最終更新日 2.46.0

NAME

gitpacking - Gitにおけるパッキングに関する高度な概念

SYNOPSIS

gitpacking

DESCRIPTION

このドキュメントは、Gitにおけるパッキングに関する高度な概念を説明することを目的としています。

多くの概念は現在、git-pack-objects[1]、git-repack[1]などの様々なGitコマンドのマニュアルページ、gitformat-pack[5]、そしてDocumentation/technicalツリーの一部に散らばって記述されています。

このドキュメントでは網羅されていないGitのパッキングの多くの側面は、前述の箇所に存在します。時間の経過とともに、これらの散在する部分は、このドキュメントに統合される可能性があります。

疑似マージビットマップ

注記
 疑似マージビットマップは実験的な機能とみなされているため、設定と多くのアイデアは変更される可能性があります。

背景

到達可能性ビットマップは、トラバーサルの開始点の1つ以上にディスク上に格納されたビットマップがある場合に最も効率的です。このため、Gitはrefsの先端にあるコミットのビットマップを格納することを好みます。なぜなら、トラバーサルはこれらの点から始まる傾向があるからです。

しかし、refsの数が非常に多い場合、すべてのrefの先端にビットマップを格納することは現実的ではありません。スペースを占有し、それらのビットマップをすべてORで結合するだけでもコストがかかります。

これを処理する1つの方法は、refsのグループを表すビットマップを作成することです。トラバーサルがグループ全体について問い合わせる場合、各refを個別に検討する代わりに、この単一のビットマップを使用できます。これらのビットマップは、すべてのコミットの仮説上のマージで到達可能になるオブジェクトの集合を表すため、疑似マージビットマップと呼びます。

概要

"疑似マージビットマップ"は、以下の2つのビットマップのペアを参照するために使用されます。

コミットビットマップ

設定されたビットが、疑似マージの「マージ」ビットマップ（下記）に含まれるコミットの集合を記述するビットマップ。

マージビットマップ

設定されたビットが、疑似マージの「コミット」ビットマップ（上記）内のコミットの集合に対する到達可能性クロージャを記述するビットマップ。コミットビットマップで説明されているのと同じ親の集合を持つタコ型マージについても、同一のビットマップが生成されます。

疑似マージビットマップは、特定の疑似マージのすべてのコミットがトラバーサルの方のどちらかに直接（HAVESまたはWANTSの一部として明示的に要求することによって）、または間接的に（フィルイントラバーサル中に遭遇することによって）一覧表示されている場合、ビットマップトラバーサルを高速化できます。

ユースケース

たとえば、多数のコミットを持つ疑似マージビットマップがあり、それらのすべてが、あるビットマップトラバーサルクエリの一方のセクションに一覧表示されているとします。疑似マージビットマップが有効になっている場合、ビットマップ機構は、クエリの一方のオブジェクトのサブセットを満たす疑似マージがあることを迅速に判断できます。次に、EWAH圧縮ビットマップを展開し、結果のビットマップにORで結合できます。対照的に、疑似マージビットマップがない場合、潜在的に多数の個々のビットマップに対して解凍とOR操作を繰り返す必要があり、それに比例して時間がかかります。

疑似マージのもう1つの利点は、(a)多数の参照、(b) ビットマップの範囲が狭い、(c) 深く入れ子になったツリーがあり、フィルイントラバーサルが比較的コストがかかる場合に生じます。たとえば、各タグを個別にビットマップ化することが非現実的な数のタグがあるとします。疑似マージビットマップがない場合、たとえばgit rev-list --use-bitmap-index --count --objects --tagsの結果を計算するには、大量のフィルイントラバーサルが必要になる可能性があります。しかし、これらのタグの多くが疑似マージビットマップにまとめて格納されている場合、ビットマップ機構は、これらのタグすべてから到達可能なオブジェクトの和集合のみを気にするという事実を利用して、クエリをはるかに高速に回答できます。

設定

参照の先端は、2つの基準に従って異なる疑似マージグループにグループ化されます。参照名は、定義された疑似マージパターンの1つ以上と一致し、オプションで、そのパターン内の1つ以上のキャプチャグループがグループをさらに分割します。

グループ内では、コミットは、その年齢に応じて「安定」または「不安定」と見なされます。これらは、bitmapPseudoMerge.<name>.stableThresholdとbitmapPseudoMerge.<name>.thresholdの設定値を設定することで調整されます。

すべての安定したコミットは、等しいサイズ（bitmapPseudoMerge.<name>.stableSize）の疑似マージにグループ化されます。たとえば、stableSize設定を100に設定した場合、stableThreshold値よりも古い最初の100個のコミット（コミッタ日付順）が1つのグループを形成し、次の100個のコミットが別のグループを形成するなどとなります。

不安定なコミットの中で、疑似マージ機構は、新しいコミットとは対照的に、古いコミットを大きなグループに結合しようとします。これは、先端コミットが古い参照は、先端コミットが新しい参照よりも異なるコミットを指すように変更される可能性が低いというヒューリスティックに基づいています。

グループのサイズはべき乗則減衰関数によって決定され、減衰パラメータは、f(n) = C*n^(-k/100)（ここで、f(n)はn番目の疑似マージグループのサイズを表します）の「k」にほぼ対応します。サンプリングレートは、対象となるコミットの割合を制御します。閾値パラメータは最小年齢を示します（疑似マージグループにあまりにも新しいコミットを含めるのを避けるため、有効になる可能性が低くなります）。"maxMerges"パラメータは、個々のグループの疑似マージコミットの数の上限を設定します。

"stable"関連のパラメータは、「stable」疑似マージグループを制御し、これは、設定された「stable threshold」値よりも古い固定数のコミットで構成され、年齢順に「stableSize」のチャンクにまとめてグループ化される場合があります。

疑似マージの正確な設定は以下のとおりです。

注記
 bitmapPseudoMerge.*の設定オプションは実験的と見なされており、将来変更されるか、完全に削除される可能性があります。疑似マージビットマップ機能の詳細については、gitpacking[7]の「疑似マージビットマップ」セクションを参照してください。
bitmapPseudoMerge.<name>.pattern

参照名の一致に使用する正規表現。このパターンに一致する参照（bitmapPseudoMerge.<name>.sampleRateやbitmapPseudoMerge.<name>.thresholdなどの以下の基準を満たす）が指すコミットは、疑似マージビットマップへの含めを検討されます。

コミットは、特定のコミットを指す参照がパターンに一致するかどうかによって、疑似マージグループにグループ化されます。これは拡張正規表現です。

疑似マージグループ内では、パターン内のキャプチャグループに基づいて、コミットをさらにサブグループにグループ化できます。これらのサブグループ化は、正規表現から、正規表現のキャプチャグループをダッシュ（-）で連結することで形成されます。

たとえば、パターンがrefs/tags/の場合、すべてのタグ（以下の基準を満たす場合）が同じ疑似マージグループの候補と見なされます。ただし、パターンがrefs/remotes/([0-9])+/tags/の場合、異なるリモートからのタグは、リモート番号に基づいて個別の疑似マージグループにグループ化されます。

bitmapPseudoMerge.<name>.decay

連続する疑似マージビットマップグループのサイズが減少する速度を決定します。非負でなければなりません。このパラメータは、関数f(n) = C * n^-k（ここで、f(n)はn番目のグループのサイズです）のkと考えることができます。

減衰率を0に設定すると、すべてのグループのサイズが同じになります。減衰率を1に設定すると、n番目のグループのサイズは、最初のグループの1/nになります。減衰率の値が高いほど、連続するグループは増加する速度で縮小します。デフォルトは1です。

すべてのグループのサイズが同じ場合、新しいコミットを含むグループは、古いコミットを参照する参照よりも新しいコミットを参照する参照の方が更新される可能性が高いため、古いグループよりも使用頻度が低くなる可能性があります。

bitmapPseudoMerge.<name>.sampleRate

不安定な疑似マージビットマップに含めるために選択される、（参照先から見た）ビットマップ化されていないコミットの割合を決定します。0から1（を含む）の間でなければなりません。デフォルトは1です。

bitmapPseudoMerge.<name>.threshold

不安定な疑似マージビットマップに含める候補となる、（上記と同様に参照先から見た）ビットマップ化されていないコミットの最小経過時間を決定します。デフォルトは1.week.agoです。

bitmapPseudoMerge.<name>.maxMerges

コミットを分散できる疑似マージコミットの最大数を決定します。

パターンにキャプチャグループが含まれていない疑似マージグループの場合、この設定は正規表現に一致するすべてのコミットに適用されます。1つ以上のキャプチャグループを持つパターンでは、この設定は個々のキャプチャグループに適用されます。

たとえば、キャプチャグループがrefs/tags/の場合、この設定はすべてのタグを最大maxMerges個の疑似マージコミットに分散します。しかし、キャプチャグループがrefs/remotes/([0-9]+)/tags/などである場合、この設定は各リモートのタグセットに個別に適用されます。

0以上の値でなければなりません。デフォルト値は64です。

bitmapPseudoMerge.<name>.stableThreshold

（上記と同様に参照先から見た）安定したコミットはビットマップでカバーされていても候補とみなされますが、安定した疑似マージビットマップの候補となるコミットの最小経過時間を決定します。デフォルトは1.month.agoです。

このしきい値をより小さい値（例：1.week.ago）に設定すると、より多くの安定したグループが生成されます（1回限りの生成コストがかかります）が、それらのグループは時間の経過とともに古くなる可能性が高くなります。より大きな値を使用すると、逆のペナルティ（より少ない安定したグループ、より有用性の低いグループ）が発生します。

bitmapPseudoMerge.<name>.stableSize

安定した疑似マージビットマップのサイズ（コミット数）を決定します。デフォルトは512です。

例

多数の参照を持つリポジトリがあり、refs/名前空間のビットマップカバレッジを向上させる疑似マージビットマップの基本的な構成が必要だとします。次のような構成から始めることができます。

[bitmapPseudoMerge "all"]
	pattern = "refs/"
	threshold = now
	stableThreshold = never
	sampleRate = 100
	maxMerges = 64

これにより、すべての参照について、その経過時間に関わらず、疑似マージビットマップが作成され、64個の疑似マージコミットにグループ化されます。

疑似マージコミットを生成する際にタグとブランチを分離したい場合は、代わりにキャプチャグループを使用してパターンを定義します。

[bitmapPseudoMerge "all"]
	pattern = "refs/(heads/tags)/"

代わりに、各フォークが何らかの数値IDで指定され、その参照がネットワーク内のrefs/virtual/NNN/（NNNはフォークに対応する数値ID）にあるフォークネットワークリポジトリで作業しているとします。この場合、次のように記述できます。

[bitmapPseudoMerge "all"]
	pattern = "refs/virtual/([0-9]+)/(heads|tags)/"
	threshold = now
	stableThreshold = never
	sampleRate = 100
	maxMerges = 64

これにより、「1234-heads」や「5678-tags」のような疑似マージグループ識別子が生成されます（それぞれフォーク「1234」のブランチとリモート「5678」のタグ用）。

参照

git-pack-objects[1] git-repack[1]

Git

git[1] スイートの一部

scroll-to-top