SYNOPSIS

gitpacking

DESCRIPTION

この文書は、 Git のパッキングに関連するいくつかの高度な概念に焦点を当てて説明します。

現在、 多くの概念は、 git-pack-objects(1) や git-repack(1) などのさまざまな Git コマンドのマニュアル・ページや、 gitformat-pack(5) や、 technical ドキュメント群の一部に分散して説明されています。

Git のパッキングに関しては、 このドキュメントでは取り上げられていない多くの側面がありますが、 それらは上記の文書に散在しています。 しかし、 そのうち、 これらの散在した部分がこの文書に合流するかもしれません。

Pseudo-merge bitmaps

Note
 疑似マージ・ビットマップ(Pseudo-merge bitmaps)は実験的な機能とみなされているため、 構成やアイデアの多くは変更される可能性があります。

Background

到達可能性ビットマップは、 走査(traversal)の 1 つ以上の開始点のビットマップがディスク上に保存されている場合に最も効率的です。 このため、 Git はコミットのビットマップを参照の先端に保存することを好みます。 これは、 走査(traversal)がそれらのポイントから開始される傾向があるためです。

しかし、 非常に多数の refs がある場合、 すべての ref 先端のビットマップを保存することは現実的ではありません。 これにはスペースが必要で、 かつ、 これらすべてのビットマップを OR 演算するだけでも高価なコストがかかります。

これに対処可能な方法の一つは、 refs の「グループ」を表すビットマップを作成することです。 走査(traversal)でグループ全体について尋ねる場合、 各 ref を個別に考慮する代わりに、 この単一のビットマップを使用できます。 これらのビットマップは、 すべてのコミットをマージしたと仮定(hypothetical)すると到達可能なオブジェクトのセットを表すため、 これらを擬似マージ・ビットマップ(pseudo-merge bitmaps)と呼びます。

Overview

「疑似マージ・ビットマップ」(pseudo-merge bitmap)は、 以下のようなビットマップのペアを参照するために使用されます:

Commit bitmap

擬似マージ(pseudo-merge)の「マージ」ビットマップ(merge bitmap;下記)に含まれるコミットのセットを記述するセット・ビット群があるビットマップ。

Merge bitmap

(上記のように)擬似マージ(pseudo-merge)の「コミット」ビットマップ内のコミットのセットに対する到達可能性終端(reachability closure)を記述するセット・ビットを持つビットマップ。 コミット・ビットマップで説明されているように、 同一の親セットを持つ octopus マージに対して全く同じビットマップが生成されます。

擬似マージ・ビットマップ(pseudo-merge bitmaps)は、 特定の擬似マージのすべてのコミットが走査(traversal)のいずれかの側にリストされている場合に、 (「HAVES」または「WANTS」の一部として明示的に要求することによって)直接、 または(全体に渡る走査中にそれらに出くわす事によって)間接的に、 ビットマップ走査(traversal)を高速化できます。

Use-cases

たとえば、 非常に多数のコミットを含む疑似マージ・ビットマップが存在し、 その全てがビットマップ走査クエリー(bitmap traversal query)の「WANTS」セクションにリストされているとします。 擬似マージ・ビットマップが有効になっている場合、 ビットマップ機構は、 クエリーのいずれかの側に必要なオブジェクトの一部を満たす擬似マージが存在することを迅速に判断できます。 次に、 EWAH 圧縮ビットマップ(EWAH-compressed bitmap)を解凍し、 それを結果のビットマップと「OR」演算します。 対照的に、 擬似マージ・ビットマップがなければ、 潜在的に多数の個々のビットマップに対して解凍と「OR」演算ステップを繰り返す必要があり、 それに比例して時間がかかる可能性があります。

疑似マージのもう 1 つの利点は、 (a)多数の参照や、 (b)ビットマップ・カバレッジが不十分や、 (c)深くネストされたツリー、 が組み合わさり、 全体に渡る走査(traversal)が比較的高価になる場合に生じます。 たとえば、 非常にたくさんの数のタグがあり、 各タグを個別にビットマップすることが不可能であるとしましょう。 このとき、 疑似マージ・ビットマップがなければ、 たとえば git rev-list --use-bitmap-index --count --objects --tags の結果を計算するには、 大量の、 全体に渡る走査が必要になる可能性があります。 しかし、 これら大量のタグが擬似マージ・ビットマップにまとめて保存されている場合、 ビットマップ機構は、 それらすべてのタグから到達可能なオブジェクトの結合のみを考慮するという事実を利用することで、 クエリーにはるかに速く応答できます。

Configuration

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

グループ内では、 コミットはその年齢(age)に応じて「安定」(stable)または「不安定」(unstable)とみなされる場合があります。 これらは、それぞれ bitmapPseudoMerge.<name>.stableThreshold や bitmapPseudoMerge.<name>.threshold 構成値を設定することによって調整します。

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

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

グループのサイズはべき乗則の減衰関数(power-law decay function)によって決定され、 減衰パラメーターは f(n) = C*n^(-k/100) の k にほぼ対応します(ここで f(n) は n 番目の擬似マージ・グループのサイズを示します。 サンプル・レートは、 適格なコミットの何パーセントが候補として考慮されるかを制御します。 しきい値パラメーターは、 最小経過期間を示します(擬似マージ・グループに最近すぎるコミットが含まれ、 擬似マージ・グループが有効である可能性が低くなるのを避けるため)。 maxMerges パラメータは、 個々のグループの疑似マージ・コミット数の上限を設定します。

「安定」関連パラメータ(stable-related parameters)は、「安定」疑似マージ・グループを制御します。 このグループは、 設定された「安定しきい値」(stable threshold value)よりも古い、 固定数のコミットで構成され、 古い順に stableSize のサイズのチャンクにグループ化されます。

疑似マージ( pseudo-merges)の構成(configuration)は以下のとおりです:

Note
 設定オプション bitmapPseudoMerge.* は「実験的」(EXPERIMENTAL)なものとみなされ、 将来変更されるか完全に削除される可能性があります。 擬似マージ・ビットマップ(pseudo-merge bitmap)機能の詳細については、 gitpacking(7) の「Pseudo-merge bitmaps」セクションを参照してください。
bitmapPseudoMerge.<name>.pattern

参照名にマッチさせるために使用される正規表現。このパターンに一致するコミット(および下記の bitmapPseudoMerge.<name>.sampleRate や bitmapPseudoMerge.<name>.threshold などの基準を満たすコミット)は、 擬似マージ・ビットマップ(pseudo-merge bitmap)に含めることができるとみなされます。

コミット達は、 特定のコミットを指す参照がパターン(拡張正規表現)にマッチするかどうかに基づいて、 擬似マージ・グループにグループ化されます。

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

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

bitmapPseudoMerge.<name>.decay

連続する擬似マージ・ビットマップ・グループのサイズが減少する速度を決定します。 負ではない必要があります。 このパラメータは、関数 f(n) = C * n^-k の k と考えることができます。 ここで、 f(n) は n 番目のグループのサイズです。

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

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

bitmapPseudoMerge.<name>.sampleRate

不安定(unstable)な疑似マージ・ビットマップに含めるために選択される、(参照先端のうち)ビットマップ化されていないコミットの割合を決定します。 0 と 1 の間 (両端を含む) でなければなりません。デフォルトは 1 です。

bitmapPseudoMerge.<name>.threshold

不安定(unstable)な疑似マージ・ビットマップに含める候補となる、 ビットマップ化されていないコミット(上記の参照先端のうち)の最小経過期間を決定します。 デフォルトは 1.week.ago です。

bitmapPseudoMerge.<name>.maxMerges

コミットを分散させる擬似マージ・コミットの最大数を決定します。

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

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

値は負ではない必要があります。 デフォルト値は 64 です。

bitmapPseudoMerge.<name>.stableThreshold

安定(stable)した疑似マージ・ビットマップの候補であるコミットの最小経過期間を決定します(上記の参照先端の中で。 ただし、 安定した(stable)コミットは既にビットマップでカバーされている場合でも候補とみなされます)。 デフォルトは 1.month.ago です。

このしきい値をより小さい値(1.week.ago など)に設定すると、 より安定したグループ(more stable groups)が生成されますが(毎回の生成コストがかかります)、 それらのグループは時間の経過とともに古くなってしまう可能性があります。 より大きな値を使用すると、 逆のペナルティが発生します(安定したグループが少なくなり、 より役に立つようになります)。

bitmapPseudoMerge.<name>.stableSize

安定(stable)した疑似マージ・ビットマップ(psuedo-merge bitmap)のサイズ(コミット数)を指定します。 デフォルトは 512 です。

Examples

多数の参照を含むリポジトリがあり、 あなたは refs/ 名前空間のビットマップ・カバレッジを強化する疑似マージ・ビットマップ(pseudo-merge bitmaps)のたたき台な構成が必要だとすると、 あなたは以下のような構成から始めることができます:

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

これにより、 その履歴の古さに関係なく、 すべての参照のための疑似マージ・ビットマップ(pseudo-merge bitmaps)が生成され、 それらは 64 個の疑似マージ コミットにグループ化されます。

疑似マージ・コミット(pseudo-merge commits)を生成するときにブランチからタグを分離したい場合は、 上記の代わりに以下のようにキャプチャ・グループ(capture group)を使用してパターンを定義します:

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

上記と異なり、 フォーク・ネットワーク・リポジトリ(fork-network repository)で作業しており、 各フォークが数値 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 へのタグ)などの疑似マージ・グループIDが生成されます。

SEE ALSO

git-pack-objects(1) git-repack(1)

GIT

Part of the git(1) suite