reftable

Overview

Problem statement

一部のリポジトリにはたくさんの参照が含まれています(例: android の 866k、rails の 31k)。 既存の pack-refs 形式は多くのスペース(たとえば 62M とか)を占有し、追加の参照では拡張できません。 単一の参照を検索するには、ファイルを線形にスキャンする必要があります。

複数の参照を変更するアトミック・プッシュでは、パックされた参照ファイル全体をコピーする必要があります。これは、(2つの参照が変更されただけの、)小さな取引 (transactions)でも、かなりの量のデータが移動される可能性があります(たとえば、62M の入出力)。

各参照は 41 バイトを格納する独自のファイル (および対応する reflog 用の別のファイル) であるため、多くの緩い(loose)参照を含むリポジトリは、ローカル・ファイルシステム上で多数のディスク・ブロックを占有します。 これは、多数のリポジトリが同じファイルシステムに保存されている場合に、利用可能な inode の数に悪影響を及ぼします。 $GIT_DIR/refs ディレクトリをトラバースして読み取るために必要なシステムコールの数がすごくたくさんになるため、読み取り側は不利(penalize)になる可能性があります。

Objectives

  • リポジトリがコールドでプロセスやカーネルキャッシュにない場合でも、単一の参照に対してほぼ一定時間の検索(lookup)を可能にする。

  • オブジェクト名が少なくとも1つの参照によって参照される場合、ほぼ一定時間で検証(verification)を行う(allow-tip-sha1-in-want 用)。

  • refs/tags/ のような名前空間全体の効率的な列挙。

  • O(size_of_update) 操作量によるアトミック(atomic)プッシュをサポートします。

  • 小さな取引(transactions)用に reflog ストレージと ref ストレージを組み合わせます。

  • ベース ref と履歴ログ用の、個別の reflog ストレージ。

Description

reftable ファイルは、参照ストレージ用にカスタマイズされた可搬性(portable)のあるバイナリ・ファイル形式です。 参照は並べ替えられ、線形スキャン、二分木検索検索(binary search lookup)、範囲スキャンが可能になります。

ファイル内のストレージは、可変サイズのブロックに編成されます。 ディスク領域を削減するために、1 つのブロック内でプレフィックス圧縮が使用されます。 ブロックサイズと揃え幅(alignment)は、ライターによって調整可能です。

Performance

使用スペース packed-refs V.S. reftable:

repository packed-refs reftable % original avg ref avg obj

android

62.2 M

36.1 M

58.0%

33 bytes

5 bytes

rails

1.8 M

1.1 M

57.7%

29 bytes

4 bytes

git

78.7 K

48.1 K

61.0%

50 bytes

4 bytes

git (heads)

332 b

269 b

81.0%

33 bytes

0 bytes

スキャン (866k ref の読み取り)と、参照名検索(lookup) (866k refs から 単一 ref を)と、SHA-1 検索(lookup) (866k refs からのその SHA-1 を含む refs):

format cache scan by name by SHA-1

packed-refs

cold

402 ms

409,660.1 usec

412,535.8 usec

packed-refs

hot

6,844.6 usec

20,110.1 usec

reftable

cold

112 ms

33.9 usec

323.2 usec

reftable

hot

20.2 usec

320.8 usec

43,061 refs の 149,932 ログ エントリに使用されるスペース reflog V.S. reftable:

format size avg entry

$GIT_DIR/logs

173 M

1209 bytes

reftable

5 M

37 bytes

Details

Peeling

reftable に格納された参照は皮むき(peel)され、注釈付き (または署名付き) タグのレコードは、タグ オブジェクトとそれが参照するオブジェクトの両方を記録します。 これは、packed-refs 形式のストレージに似ています。

Reference name encoding

参照名は解釈されないバイト列で、有効な参照名としては git-check-ref-format(1) をパス(pass)しなければなりません。

Key unicity

各エントリには一意のキーが必要です。 キーの繰り返しは許可されません。

Network byte order

複数バイトの固定幅フィールドは、全てネットワークバイトオーダーです。

Varint encoding

派生(varint)エンコーディングは、パックファイル内で使用される ofs-delta エンコーディング方法と同じです。

デコーダーは以下のとおり機能します:

val = buf[ptr] & 0x7f
while (buf[ptr] & 0x80) {
  ptr++
  val = ((val + 1) << 7) | (buf[ptr] & 0x7f)
}

Ordering

ブロックは、最初の参照によって辞書順(lexicographically ordered)に並べられます。

Directory/file conflicts

reftable 形式は、refs/heads/foo と refs/heads/foo/bar の両方を別個の参照として受け入れます。

この特性は、reftable にログ レコードを保持するのに役立ちますが、$GIT_DIR/refs ディレクトリ ツリーを使用して参照を維持する Git のバージョンを混乱させる可能性があります。 reftable のユーザーは、ピアの問題を防ぐために、foo および foo/bar タイプの競合を引き続き拒否することを選択できます。

File format

Structure

reftable ファイルには、以下の高レベル構造があります:

first_block {
  header
  first_ref_block
}
ref_block*
ref_index*
obj_block*
obj_index*
log_block*
log_index*
footer

ログのみのファイルでは、ref_block と ref_index と`obj_block` と`obj_index` セクションが省略され、ファイルヘッダーとログブロックのみが含まれます:

first_block {
  header
}
log_block*
log_index*
footer

ログのみのファイルでは、最初のログ ブロックはファイル ヘッダーの直後に続き、ブロック揃え幅へのパディングは行われません。

Block size

ファイルのブロック・サイズはライター(writer)によって任意に決定され、2 のべき乗である必要はありません。参照は複数のブロックにまたがることができないため、ブロック サイズは、リポジトリで使用される最長の参照名またはログ・エントリよりも大きくする必要があります。

仮想メモリ・システムまたはファイル・システム (4k や 8k など) に適した 2 の累乗が推奨されます。 サイズが大きい (64k) ほど圧縮率が高くなりますが、アクセス中にリーダー(readers)が負担するコストが増加する可能性があります。

最大ブロック サイズは「16777215」バイト (15.99 MiB) です。

Block alignment

ライター(writers)は、ブロックの末尾に NUL バイトで満たされた「詰物」(padding)を含めることにより、ブロック・サイズの倍数でブロックを揃えて、選択した揃え幅(alignment)に丸めることができます。 揃えを使用する場合、ライターはファイル・ヘッダーの「block_size」フィールドで揃え幅(alignment)を指定する必要があります。

このファイル形式では、ブロック揃え幅(alignment)は必須ではありません。 揃えない(unaligned)ファイルは、ファイル・ヘッダーで block_size = 0 を設定し、「詰物」(padding)を省略しなければなりません。 複数の ref ブロックを含む揃えないファイルには、 ref index を含めて高速検索をサポートする必要があります。 リーダー(readers)は、揃えるファイルと揃えないファイルの両方を読み取ることができなければなりません。

非常に小さなファイル (単一の ref ブロックなど) では、合計ファイル サイズを減らすために「詰物」(padding)とrefインデックスを省略できます。

Header (version 1)

24バイト。ファイルの先頭に 24 バイトのヘッダーが表れます:

'REFT'
uint8( version_number = 1 )
uint24( block_size )
uint64( min_update_index )
uint64( max_update_index )

揃えるファイルは、予想されるブロック揃え幅(alignment)でリーダーを構成するために、 block_size を指定する必要があります。 揃えないファイルは、block_size = 0 を設定する必要があります。

min_update_index と max_update_index は、このファイル内のすべてのログ・レコードの update_index フィールドの境界を記述します。 transactions のスタックで reftable が使用される場合、これらのフィールドは、前のファイルの max_update_index + 1 が次のファイルの min_update_index になるようにファイルを並べ替えることができます。

Header (version 2)

28バイト。ファイルの先頭には28バイトのヘッダーが表れます:

'REFT'
uint8( version_number = 2 )
uint24( block_size )
uint64( min_update_index )
uint64( max_update_index )
uint32( hash_id )

ヘッダーは「version_number=1」と全く同じで、 4バイトのハッシュID (SHA1 の場合は「sha1」、SHA-256 の場合は「s256」) がヘッダーに追加されます。

下位互換性を最大限に保つために、SHA1 reftable を作成する場合はバージョン 1 を使用することをお勧めします。

First ref block

最初の ref ブロックは、ファイルヘッダーと同一のブロックを共有し、ファイル内の他のすべてのブロックよりも 24 バイト小さくなります。 最初のブロックは、ファイルヘッダーの直後の 24 番目の位置から始まります。

最初のブロックがログ・ブロック (ログのみのファイル) の場合、そのブロック・ヘッダーは位置 24 から直ちに始まります。

Ref block format

ref ブロックは以下のとおり記述されます:

'r'
uint24( block_len )
ref_record+
uint24( restart_offset )+
uint16( restart_count )

padding?

ブロックは block_type = 'r' で始まり、そして 3 バイトの block_len はブロック内のバイト数をエンコードしますが、オプションの「詰物」は含みません。 これは、常にファイルのブロック・イズ以下です。 最初の ref ブロックでは、 block_len にファイル・ヘッダー用の 24 バイトが含まれます。

2 バイトの「restart_count」には、「restart_offset」リストのエントリ数が格納されます。このリストは空であってはなりません。 リーダーは、線形スキャンを開始する前に、「restart_count」を使用して再開区間(between restarts)で二分木検索を行うことができます。

正確に restart_count の 3 バイトの restart_offset 値が restart_count に先行します。 オフセットはブロックの開始からの相対であり、名前がプレフィックス圧縮されていない「ref_record」の最初のバイトを参照します。 restart_offset リストのエントリは、昇順で並べ替える必要があります。 リーダーは、これらのレコードのいずれかから線形スキャンを開始できます。

可変数の「ref_record」がブロックの中央部を埋め、参照名と値を記述します。 形式は下記のとおりです。

最初の ref ブロックは最初のファイル・ブロックをファイル・ヘッダーと共有するため、最初のブロックのすべての restart_offset はファイルの先頭 (位置 0) からの相対であり、ファイル・ヘッダーを含みます。 これにより、最初の「restart_offset」は強制的に「28」になります。

ref record

ref_record は、名前とその値の両方を格納する単一の参照を記述します。各レコードは以下の形式です:

varint( prefix_length )
varint( (suffix_length << 3) | value_type )
suffix
varint( update_index_delta )
value?

「prefix_length」フィールドは、この参照の名前を取得するために、前の参照レコードの名前の先頭の何バイトをコピーする必要があるかを指定します。 これは、任意のブロックの最初の参照では 0 でなければならず、ブロックの最後の restart_offset テーブルにオフセットがリストされているすべての ref_record についても 0 でなければなりません。

任意の ref_record から参照名を復元するのは単純な連結です:

this_name = prior_name[0..prefix_length] + suffix

suffix_length 値は、参照名を完成させるために suffix からコピーするために suffix で利用可能なバイト数を提供します。

参照を最後に変更した update_index は、ファイル・ヘッダーの min_update_index に update_index_delta を追加することで取得できます: min_update_index + update_index_delta

「値」が続きます。 その形式は、以下のいずれかの「value_type」によって決まります:

  • 0x0: 削除。値データ無し(下記 transactions 参照)

  • 0x1: 1つのオブジェクト名。refの値

  • 0x2: 2つのオブジェクト名。refの値と皮むきされた(peeled)ターゲット

  • 0x3: シンボリック参照。 varint( target_len ) target

シンボリック参照は 0x3 を使用し、その後に参照ターゲットの完全な名前が続きます。 ターゲット名に圧縮は適用されません。

0x4〜0x7 将来の為に予約。

Ref index

ref インデックスは、ファイル内のすべての ref ブロックからの最後の参照の名前を格納し、検索(lookup)のためのディスク・シークを削減します。 インデックスを検索(search)し、それを含むブロックを特定し、そのブロック内を検索(search)することで、すべての参照を見つける(find)ことができます。

インデックスは、マルチレベル・インデックスに編成することができます。この場合、第 1 レベルのインデックス・ブロックが追加の参照インデックス・ブロック(第2レベル)を指し、さらに追加のインデックス・ブロック (たとえば 第 3 レベル) または参照ブロック (リーフ レベル) を指す場合があります。 ref にアクセスするために必要なディスク読み取りの必要性は、インデックス・レベルが高いほど高くなります。 単一のインデックス・ブロックがファイル形式の最大ブロック サイズ「16777215」バイト (15.99 MiB) を超えないようにするために、複数レベルのインデックスが必要になる場合があります。 検索(lookup)のために一定の O(1) ディスク・シークを実現するには、インデックスは単一レベルである必要があります。これは、ファイルの構成されたブロック・サイズを超えることは許可されていますが、フォーマットの最大ブロック・サイズである 15.99 MiB を超えることは許可されていません。

もしあれば、refインデックス・ブロック(達)は最後のrefブロックの後に表れます。

少なくとも 4 つの ref ブロックがある場合は、検索(lookup)時間を改善するために ref インデックス・ブロックを書き込む必要があります。 インデックスを使用したコールド読み取りには 2 つのディスク読み取り (インデックス読み取りとブロック読み取り) が必要であり、また、4ブロック未満のバイナリ検索でもディスク読み取りが2回以下必要です。 小さいファイルからインデックス・ブロックを省略すると、スペースが節約されます。

ファイルが揃えられておらず、複数の ref ブロックが含まれている場合は、ref インデックスを書き込む必要があります。

インデックス・ブロック形式:

'i'
uint24( block_len )
index_record+
uint24( restart_offset )+
uint16( restart_count )

padding?

インデックス・ブロックは、block_type = 'i' で始まり、そして、ブロック内のバイト数をエンコードする 3 バイトの block_len は、オプションの「詰物」を含みません。

restart_offset および restart_count フィールドの形式と意味と使用法は、 ref ブロックの場合と全く同じです。

非常に大きなファイルのランダム・アクセスに必要な読み取り回数を減らすために、インデックス・ブロックは他のブロックよりも大きくなる場合があります。 ただし、これを利用するには、リーダーはインデックス全体をメモリに保持する必要があるため、ファイル・サイズとリーダー・メモリの両方で時間と空間のトレードオフになります。

ファイルのブロック・サイズを大きくすると、インデックス・サイズが小さくなります。 別の方法として、複数レベルのインデックスを使用して、インデックス・ブロックをファイルのブロック・サイズ内に保ちながら、アクセスする必要があるブロックの数を増やすこともできます。

index record

インデックス・レコードは、別のブロックの最後のエントリを記述します。 インデックス・レコードは以下のとおり記述されます:

varint( prefix_length )
varint( (suffix_length << 3) | 0 )
suffix
varint( block_position )

インデックス・レコードは、ref_record と正確に同様にプレフィックス圧縮を使用します。

インデックス・レコードは、サフィックスの後に「block_position」を格納し、この参照で終了するブロックの (ファイルの先頭からの) 絶対位置をバイト単位で指定します。 リーダーは「block_position」へシークして、ブロック・ヘッダーの読み取りを開始できます。

リーダーは、block_position のブロック・ヘッダーを調べて、次のブロックが別のレベルのインデックス・ブロックであるか、枝葉レベル(leaf-level)の ref ブロックであるかを判断する必要があります。

Reading the index

ref インデックスをロードするリーダーは、最初にフッター (下記) を読んで ref_index_position を取得する必要があります。 存在しない場合、位置は 0 になります。 ref_index_position は、ref インデックスの第 1 レベルのルート(root)用です。

Obj block format

オブジェクト・ブロックはオプションです。 ライターは、特にリーダーがrefマッピングにオブジェクト名を使用しない場合は、オブジェクト・ブロックを省略することを選択できます。

オブジェクト・ブロックは、 2 ～ 31 個の一意の短縮オブジェクト名キーを使用し、そのオブジェクトを直接指す参照を含む ref ブロックにマッピングするか、注釈付きタグの皮むきされた値(peeled value)としてマッピングします。 ref ブロックと同様に、オブジェクト・ブロックはファイルの標準ブロック・サイズを使用します。 省略形の長さは、フッターで obj_id_len として利用できます。

小さなファイルのスペースを節約するために、ref インデックスが存在しない場合はオブジェクト・ブロックを省略できます。力づくで検索(brute force search)を行う場合はいくつかの ref ブロックを読み取るだけでよいためです。 欠落がある場合、リーダーは、オブジェクト名で検索(lookup)するすべての参照の線形検索を力ずくで実行する必要があります。

オブジェクト・ブロックは以下のとおり記述されます:

'o'
uint24( block_len )
obj_record+
uint24( restart_offset )+
uint16( restart_count )

padding?

フィールドは ref ブロックの場合と全く同じです。 再開表(restart table)を使用した二分木探索は、参照ブロックの場合と全く同一に機能します。

オブジェクト名はライターによって reftable 内の最も短い一意の略語に省略されるため、オブジェクト・キーの長さは可変長になります。 それらの長さは少なくとも 2 バイトでなければなりません。 リーダーは、オブジェクト・ブロックまたはオブジェクト・インデックス内の一般的なプレフィックスの一致についてのみ比較する必要があります。

obj record

obj_record は、単一のオブジェクトの略語と、その一意の略語を使用する参照を含むブロックを記述します:

varint( prefix_length )
varint( (suffix_length << 3) | cnt_3 )
suffix
varint( cnt_large )?
varint( position_delta )*

参照ブロックと同様に、省略形はオブジェクト・ブロック内でプレフィックス圧縮されます。 多くの一意のオブジェクトや、より大きなブロック・サイズ (64k)や、より長い再開間隔 (128) を持つ大きな reftable では、オブジェクト・レコード内では prefix_length の値は2または3で suffix_length の値は3が一般的です(5～6バイトである10～12桁の16進数の一意の省略形)。

各レコードには、一致する参照ブロックの位置の「position_count」数が含まれます。 1 ～ 7 の位置の場合、カウントは「cnt_3」に格納されます。 cnt_3 = 0 の場合、実際のカウントは派生(varint) の cnt_large に続きます。

cnt_3 の使用は、ほとんどのオブジェクトが 1 つの参照のみによって指されていること、いくつかのオブジェクトは 2 つの参照によって指されていること、および 7 つ以上の参照によって指されているオブジェクトは (存在するとしても) 非常に少ないことに賭けます。

cnt_3 = 0 かつ cnt_large = 0 である特殊なケースがあります: 「position_delta」はありませんが、少なくとも 1 つの参照がこの省略形で始まります。 正確な参照名が必要なリーダーは、すべての参照をスキャンして、目的のオブジェクトを持つ特定の参照を見つける必要があります。 ライターは、同じオブジェクトを指している多数の参照が原因で「position_delta」リストがファイルのブロック・サイズをオーバーフローした場合に、この形式を使用する必要があります。

最初の position_delta は、ファイルの先頭からの位置です。 追加の「position_delta」エントリは昇順で、前のエントリに対して相対的にソートされます。 リーダーは以下のことを実行します:

pos = position_delta[0]
prior = pos
for (j = 1; j < position_count; j++) {
  pos = prior + position_delta[j]
  prior = pos
}

位置を取得したら、リーダーは最初の ref_record から開始して ref ブロックを直線的にスキャンし、各参照のオブジェクト名 ( value_type = 0x1 または 0x2 ) が完全に等しいかどうかをテストする必要があります。 単一の ref ブロック内のオブジェクト名による高速検索(searching)は、reftable 形式ではサポートされていません。 ブロック・サイズが小さいほど、このステップで考慮する必要がある候補の数が減ります。

Obj index

オブジェクト・インデックスには、ファイル内のすべてのオブジェクト・ブロックの最後のエントリの省略形が格納され、すべての検索(lookup)でのディスク・シークが削減されます。それは ref インデックスと正確に同じフォーマットがなされますが、オブジェクト・ブロックを参照します。

オブジェクト・ブロックはより大きなファイルにのみ書き込む必要があるため、オブジェクト・ブロックが存在する場合は、オブジェクト・インデックスが存在する必要があります。

オブジェクト・インデックスをロードするリーダーは、最初にフッター (下記) を読んで obj_index_position を取得する必要があります。 存在しない場合、位置は 0 になります。

Log block format

ref ブロックや obj ブロックとは異なり、ログ ブロックは常に揃えられていません。

ログ・ブロックのサイズは可変であり、ファイル・ヘッダーまたはフッターで指定された「block_size」と一致しません。 ライターは、「2 * block_size」などの適切なバッファ・サイズを選択して、圧縮用のログ・ブロックを準備する必要があります。

ログ・ブロックは以下のとおり記述されます:

'g'
uint24( block_len )
zlib_deflate {
  log_record+
  uint24( restart_offset )+
  uint16( restart_count )
}

ログ・ブロックは、block_type = 'g' を除いて、refブロックと似ています。

4バイトのブロック・ヘッダーの後に、zlib圧縮を使用して圧縮されたブロックの内容が続きます。 ヘッダーの「block_len」は膨張したサイズ (4 バイトのブロック・ヘッダーを含む) であり、解凍出力バッファーを事前に割り当てるためにリーダーで使用する必要があります。 ログ・ブロックの「block_len」がファイルのブロック・サイズを超える場合があります。

ログ・ブロック内のオフセット (「restart_offset」など) には、4 バイトのヘッダーがまだ含まれています。 リーダーは、解凍出力バッファーの前に 4 バイトのヘッダーをプレフィックスすることを好むかもしれません。

圧縮コンテナー内では、可変数の「log_record」が参照の変更を記述します。 ログの記録形式は以下のとおりです。 restart_offset と restart_count の説明については、「ref block format」(ref ブロック形式)(上述) を参照してください。

ログ・ブロックにはブロック間の揃え幅(alignment)や詰物(padding)がないため、リーダーは次のログ・ブロックの開始位置を知るために、インフレータによって消費されるバイトを追跡する必要があります。

log record

ログ・レコード・キーは以下のように構成(structure)されます:

ref_name '\0' reverse_int64( update_index )

ここで、「update_index」は一意の取引(transaction)IDです。 update_index フィールドは、 ref_name のスコープ内で一意である必要があります。 詳細については、下記「update transactions」(取引更新)セクションを参照してください。

reverse_int64 関数は値を反転するので、ネットワーク・バイト・オーダー・エンコーディングの辞書式順序付けは、より高い update_index 値を持つ新しいレコードが最初になるように並べ替えます:

reverse_int64(int64 t) {
  return 0xffffffffffffffff - t;
}

ログ・レコードは、上記のログ・レコード・キーに適用されるのと同じプレフィックス圧縮方式を利用して、ref および index レコードと同様の開始構造(starting structure)を持っています。

    varint( prefix_length )
    varint( (suffix_length << 3) | log_type )
    suffix
    log_data {
      old_id
      new_id
      varint( name_length    )  name
      varint( email_length   )  email
      varint( time_seconds )
      sint16( tz_offset )
      varint( message_length )  message
    }?

ログ・レコード・エントリでは、 log_type を使用して、以下のことを示します:

  • 0x0: 削除。ログデータ無し。

  • 0x1: 上記 log_data を使用した標準の git reflog データ。

log_type = 0x0 は、より大きなファイルを書き換える必要なく、取引ファイル(transaction file)(下記) の refs/stash の reflog からエントリを削除して、 git stash drop に最も役立ちます。 reflog のスタックを読み取るリーダーは、これを削除として扱う必要があります。

「log_type = 0x1」の場合、「log_data」セクションは git-update-ref(1) ロギングに従い、以下が含まれます:

  • 2つのオブジェクト名(old id, new id)

  • コミッター名の派生文字列(varint string)

  • コミッターメールアドレスの派生文字列(varint string)

  • エポック(Jan 1, 1970)からの経過秒数による派生時間(varint time)

  • 2バイト。分単位のタイムゾーン・オフセット(signed)

  • メッセージの派生文字列(varint string)

tz_offset は、更新時にコミッターがいたタイムゾーンです(GMT からのオフセットで表される)。 たとえば、GMT-0800 は reftable で sint16(-480) としてエンコードされ、GMT+0230 は sint16(150) としてエンコードされます。

コミッターの電子メールアドレスには < または > は含まれません。これは通常、git commit オブジェクト ヘッダーの <> の間にある値です。

message_length は 0 の場合があります。この場合、更新用のメッセージは提供されていません。

従来の reflog (ファイル) とは対照的に、名前の変更は ref 削除と ref 作成の組み合わせとしてエンコードされます。 削除は new_id がゼロのログ・レコードであり、作成は old_id がゼロのログ・レコードです。

Reading the log

ログにアクセスするリーダーは、最初にフッター (下記) を読んで log_position を判断する必要があります。 ログの最初のブロックは、ファイルの先頭から log_position バイトで始まります。 log_position はブロック揃えになっていません。

Importing logs

$GIT_DIR/logs からインポートする場合、ライターは、ファイルの順序を維持しながら、すべてのログ・レコードを大まかにタイムスタンプで並べ替え、ログ行ごとに一意の、増加する update_index 値を割り当てる必要があります。 新しいログ・レコードほど、「update_index」の値が大きくなります。

インポートは 1 つの reftable ファイルのみを書き込むことができますが、セマンティクスを維持するために各ログ行には独自の update_index が必要であるため、 reftable ファイルは多くの一意の update_index にまたがる必要があります。

Log index

ログ・インデックスは、ファイル内のすべてのログ・ブロックの最後のログ・レコードのログ・キー (refname \0 reverse_int64(update_index)) を格納し、制限時間検索(bounded-time lookup)をサポートします。

2 つ以上のログ・ブロックがファイルに書き込まれる場合は、ログ・インデックス・ブロックを書き込む必要があります。 存在する場合、ログ・インデックスは最後のログ・ブロックの後に表れます。 ログ・インデックスをブロック揃え幅(alignment)に揃える(align)ために使用される詰物(padding)はありません。

ログ・インデックスの形式は ref インデックスと同じですが、'\0' と 8 バイトの reverse_int64(update_index) を含めるためにキーが 9 バイト長くなります。 レコードは「block_position」を使用してログ・ブロック開始を参照します。

Reading the index

ログ・インデックスをロードするリーダーは、最初にフッター (下記) を読んで log_index_position を取得する必要があります。 存在しない場合、位置は 0 になります。

Footer

ファイルの最後のブロックの後ろに、ファイル・フッターが書き込まれます。 ファイル・ヘッダーのように始まりますが、追加のデータで拡張されています。

    HEADER

    uint64( ref_index_position )
    uint64( (obj_position << 5) | obj_id_len )
    uint64( obj_index_position )

    uint64( log_position )
    uint64( log_index_position )

    uint32( CRC-32 of above )

セクションが欠落している場合 (たとえば ref インデックス)、対応する位置フィールド (たとえば ref_index_position) は 0 になります。

  • obj_position: 最初のオブジェクト・ブロックのバイト位置。

  • obj_id_len: オブジェクト・ブロック内の短縮オブジェクト名のために使用されるバイト数。

  • log_position: 最初のログ・ブロックのバイト位置。

  • ref_index_position: refインデクス開始のバイト位置。

  • obj_index_position: オブジェクト・インデックス開始のバイト位置。

  • log_index_position: ログ・インデックス開始のバイト位置。

フッターのサイズは、バージョン 1 で 68 バイト、バージョン 2 で 72 バイトです。

Reading the footer

リーダーは、最初にファイルの先頭を読んでバージョン番号を確認する必要があります。 次に、フッターにアクセスするために「file_length - FOOTER_LENGTH」を探します。 「file_length」を取得するには、信頼できる外部ソース (「stat(2)」など) が必要です。 フッターを読むとき、リーダー以下のことを確認する必要があります:

  • 4バイトのマジックが正しい

  • 1バイトのバージョン番号を認識

  • 4バイトのCRC-32 は他の 64 バイトと一致します(マジックとバージョンを含む)

検証が完了すると、フッターの他のフィールドにアクセスできるようになります。

Empty tables

reftable は空である可能性があります。 この場合、ファイルはヘッダーで始まり、すぐにフッターが続きます。

Binary search

ブロック内の二分木検索は、ブロックの末尾にある「restart_offset」フィールドによってサポートされています。 リーダーは、再開表(restart table)を二分木検索して、探している参照またはキーがどの 2 つの再開点(restart points)の間に現れるかどうかを特定できます。

restart_offset によって識別される各レコードは、レコードの suffix フィールドに完全なキーを格納し、バイナリ検索中の比較操作を簡単にします。

求められる参照より辞書的に前の再開点(restart point)が特定されると、リーダーは求められるレコードを見つけるために次のレコードエントリを線形にスキャンすることができ、現在のレコードがソート後であれば（したがって、求められるキーが存在しなければ）終了する。

Restart point selection

ライターは、ファイルの作成時に再開ポイントを決定します。 処理方法は任意ですが、16 または 64 レコードごとをお勧めします。 小さいブロック・サイズ (4k または 8k) には 16 ごと、大きいブロック・サイズ (64k) には 64 ごとが適している場合があります。

再開点(restart points)の頻度が高くなると、プレフィックス圧縮が減少し、再開表(restart table)によって消費される領域が増加します。どちらもファイル・サイズが増加します。

再スタート・ポイントの頻度が低いと、プレフィックスの圧縮がより効果的になり、全体的なファイル・サイズが小さくなり、二分探索ステップの後でより多くのレコードを参照するリーダーのペナルティが増加します。

ブロックごとに最大「65535」の再スタート点がサポートされています。

Considerations

Lightweight refs dominate

reftable 形式は、参照の大部分が、 Gerrit Code Review の refs/changes/ 名前空間、または GitHub の refs/pulls/ 名前空間、または refs/tags/ 名前空間です。

皮剥きされた(peeled)オブジェクトを格納する注釈付きタグには、参照ごとに追加のオブジェクト名が必要です。

Low overhead

参照がほとんどない reftable (例: 5 つのヘッドを持つ git.git) は、reftable で 269 バイト、packed-ref で 332 バイトです。 これにより、取引ログの参照可能なスケール・ダウンがサポートされます(下記参照)。

Block size

多くの変更refがある Gerrit Code Review タイプのリポジトリの場合、ブロック・サイズが大きく (64 KiB)、再開点(restart points)再起動ポイントの頻度が低い (64 KiB ごと) ほどで、ブロック内の参照が前の参照に対して圧縮されるため、圧縮率が向上します。

reftable が同じ数の参照を格納するために必要なブロックが少なくなるため、ブロック・サイズが大きくなるとインデックス・サイズが小さくなります。

Minimal disk seeks

インデックス・ブロックがメモリに読み込まれていると仮定すると、任意の単一参照のバイナリ検索では、包含ブロックを読み込むためにちょうど 1 回のディスク・シークが必要です。

Scans and lookups dominate

すべての参照を走査(scan)し、名前 (または「refs/heads/」などの名前空間) で検索(lookup)することは、リポジトリで実行される最も一般的なアクティビティです。 このユースケースを最適化するために、オブジェクト名は参照とともに直接保存されます。

Logs are infrequently read

ログはめったにアクセスされませんが、サイズが大きくなる可能性があります。 ログ・ブロックを圧縮すると、ディスク・スペースが節約されますが、読み取り時のペナルティがいくらか増加します。

ログは ref から分離されたセクションに保存されるため、ログを無視したい参照リーダーの負担が軽減されます。 さらに、履歴ログをログのみのファイルに分離できます。

Logs are read backwards

ログは頻繁に逆方向にアクセスされるため (master が master@{4} に応答する最新の N レコード)、ログ・レコードは参照によってグループ化され、更新インデックスによって降順に並べ替えられます。

Repository format

Version 1

reftable を設定するには、リポジトリで $GIT_DIR/config を設定する必要があります:

[core]
    repositoryformatversion = 1
[extensions]
    refStorage = reftable

Layout

reftable ファイルのコレクションは $GIT_DIR/reftable/ ディレクトリに保存されます。 それらの名前には、各ファイル名がグローバルに一意になるように、ランダムな要素を含める必要があります。 これにより、開いているファイルを削除または上書きできない Windows での誤ったエラーを回避できます。 その命名規則として ${min_update_index}-${max_update_index}-${random}.ref を使用することが提案されました。

ログのみのファイルは .log 拡張子を使用しますが、 ref のみのファイルや ref とログの混合ファイルは .ref 拡張子を使用します。

スタック順序付けファイルは $GIT_DIR/reftable/tables.list で、現在のファイルを 1 行に 1 つずつ、もっとも古いの (ベース) から最新 (最新) の順にリストします。

$ cat .git/reftable/tables.list
00000001-00000001-RANDOM1.log
00000002-00000002-RANDOM2.ref
00000003-00000003-RANDOM3.ref

リーダーは $GIT_DIR/reftable/tables.list を読んで現在どのファイルが関連しているかを判断し、逆の順序でスタックを検索(search)する必要があります (最後の reftable が最初に調べられます)。

tables.list にリストされていない reftable ファイルは、新しい (そして、アクティブなライターによってスタックに追加されようとしている) か、古くて刈り込みされる準備ができている可能性があります。

Backward compatibility

古いクライアントは、ディレクトリを git リポジトリとして認識し続ける必要があるため、親ディレクトリ内のエンクロージング・リポジトリを検索しません。 このため、reftable 対応のリポジトリには以下のダミー・ファイルが含まれている必要があります。

  • .git/HEAD は、 ref: refs/heads/.invalid を含む通常のファイルです。

  • .git/refs/ はディレクトリです

  • .git/refs/heads は通常ファイルです

Readers

リーダー(readers)は、以下の方法で参照空間(the reference space)の一貫したスナップショットを取得できます:

  1. tables.list ファイルをオープンして読みとります。

  2. 言及されている各reftableファイルをオープンします。

  3. いずれかのファイルが欠落している場合は、 goto 1

  4. 現在開いているファイル群から必要なだけ読み取ります。

Update transactions

reftable は不変ですが、新しい reftable を作成し、アトミックにスタックに追加することで変更(mutation)がサポートされます:

  1. tables.list.lock を取得します。

  2. 現在の reftable を確認するには、 tables.list を読み取ります。

  3. 最新のファイルの「max_update_index + 1」になるように「update_index」を選択します。

  4. ログ・エントリを含む一時 reftable tmp_XXXXXX を準備します。

  5. tmp_XXXXXX を ${update_index}-${update_index}-${random}.ref に名前変更します。

  6. tables.list を tables.list.lock にコピーし、(5) のファイルを追加します。

  7. tables.list.lock を tables.list に名前変更します。

ステップ 4 では、新しいファイルの min_update_index と max_update_index は両方とも、ステップ 3 で選択された update_index に設定されます。取引のすべてのログ・レコードは、それらのキーで同一の update_index を使用します。 これにより、同じ取引によってどの参照が更新されたかを後で関連付けることができます。

単一の tables.list.lock ファイルがロックの管理に使用されるため、リポジトリはライター用のシングルスレッドです。 ライターは、許容可能な待機期間まで、 tables.list.lock の作成中に (バックオフを伴って) ビジースピンする必要がある場合があり、リポジトリが忙しすぎて変更できない場合は中止します。 リポジトリにラップされたアプリケーション・サーバー (Gerrit Code Review など) は、独自の ロック/待機 キューをレイヤー化して、ライターへの公平性を向上させることができます。

Reference deletions

type を 0x0 に設定し、 ref_record の value フィールドを省略することにより、任意の参照の削除を明示的に保存できます。 これは、スタック内の以前のファイルからの参照の存在に関するアサーションをオーバーライドして、墓標(tombstone)として機能します。

Compaction

reftable の部分的なスタックは、reftable 間で単純なマージ結合を使用して参照をマージし、出力用に最新の値を選択し、残りの下位の reftable に表示されない削除された参照を省略することで圧縮できます。

圧縮された reftable は、その min_update_index を入力ファイル達の最小の min_update_index に設定し、同様にその max_update_index を入力ファイル達の最大の max_update_index に設定する必要があります。

説明のために、スタックが現在 reftable ファイル達 (古いものから新しいものへ) で構成されていると仮定します: A、B、C、および D です。圧縮器(compactor)は B と C を圧縮し、A と D だけを残します。

  1. ロック tables.list.lock を取得し、そして、 tables.list ファイルを読み取ります。

  2. ロック「B.lock」と「C.lock」を取得します。 これらのロックの所有権により、他のプロセスがこれらのファイルを圧縮しようとするのを防ぎます。

  3. tables.list.lock を開放(release)します。

  4. B と C を一時ファイル ${min_update_index}-${max_update_index}_XXXXXX に圧縮します。

  5. tables.list.lock のロックを取得します。

  6. B と C がこの順序でまだスタックにあることを確認(verify)します。 他のプロセスがロック・プロトコルに従っていると仮定すると、これは常に当てはまるはずです。

  7. ${min_update_index}-${max_update_index}_XXXXXX を ${min_update_index}-${max_update_index}-${random}.ref に名前変更します。

  8. 新しいスタックを「tables.list.lock」に書き込み、「B」と「C」を (4) のファイルに置き換えます。

  9. tables.list.lock を tables.list に名前変更します。

  10. リーダーがバックトラック(backtrack)を強いられるのを避けるために、おそらく短いsleepの後、 B と C を削除します。

この戦略により、更新とは無関係に圧縮を進めることができます。

各 reftable (圧縮されているかどうかに関係なく) はその名前で一意に識別されるため、開いている reftable はその名前でキャッシュできます。

Windows

Windows や、ファイルを開くための削除や名前変更を許可しないその他のシステムでは、圧縮は成功する可能性がありますが、他のリーダーでは古いテーブルの削除が妨げられる場合があります。

これらのプラットフォームでは、次の戦略に従うことができます: reftable スタックを閉じて、 tables.list をリロードし、 tables.list で言及されなくなったテーブルを削除します。

イレギュラーなプログラムの終了により、未使用のファイルが残る場合があります。 この場合、クリーンアップ操作は以下のように進める必要があります:

  • 並列変更を防ぐためにロック tables.list.lock を取得します

  • tables.list を読み取って、reftable スタックを更新(refresh)します

  • 各 *.ref ファイルごとに、以下の場合は削除します

    • それは tables.list に記載されておらず、

    • かつ、その最大 update_index は、スタックの最大 update_index を超えていません

Alternatives considered

bzip packed-refs

bzip2 は、大きなパックされた参照ファイルを大幅に圧縮できます (たとえば、62 MiB は 23 MiB と、37% に圧縮されます)。 ただし、bzip 形式は、単一の参照へのランダム・アクセスをサポートしていません。 リーダーは、リニア・スキャン実行中、解凍と破棄を行う必要があります。

パックされた参照をチャンクに分割する (各チャンクを個別に圧縮する) と、リーダーが解凍しなければならないデータの量が減りますが、正しいチャンクを効率的に見つけるリーダーをサポートするために、チャンクにインデックスを付けるという問題が残ります。

reftable のエンコーディングによって達成される圧縮を考えると、 bzip/gzip/zlib の複雑さを追加する必要はないようです。

Michael Haggerty’s alternate format

Michael Haggerty は、Git メーリング リストで an alternate 形式を reftable に提案しました。 この形式は、再開表(restart table)なしでより小さいチャンクを使用し、詰物によるブロック揃えを回避します。 reflog エントリは各 ref の直後に続くため、ref 間に差し挟まれます。

性能テストでは、reftable の方が検索(lookup)より高速であることが示されています (51% 高速、11.2 usec 対 5.4 usec)。ただし、reftable はわずかに大きなファイルを生成します (+ ~3.2%、28.3M 対 29.2M):

format size seek cold seek hot

mh-alt

28.3 M

23.4 usec

11.2 usec

reftable

29.2 M

19.9 usec

5.4 usec

JGit Ketch RefTree

JGit Ketch は RefTree を提案しました。 これは、リポジトリのオブジェクト・データベースの一部として格納された Git ツリー・オブジェクト内の参照のエンコーディングです。

RefTree 形式は、オブジェクト・データベース・ストレージ層に追加の負荷を加え (より多くの緩いオブジェクト、より多くのパック内のオブジェクト)、スペースを節約するためにパッカーのデルタ圧縮に大きく依存しています。 フラットな名前空間 (例: refs/tags 内の数千のタグ) は、最初は非常に大きな緩いオブジェクトを作成するため、RefTree は多くの参照をコピーして一部を変更するという問題に対処しません。

フラットな名前空間は、RefTree では効率的に検索できません。標準的な形式のツリー・オブジェクトは二分木検索できないためです。 これは、GitHubの refs/pulls のような単一の名前空間で多数の参照を処理する必要性や、多くのタグを持つプロジェクトで失敗します。

LMDB

David Turner は using LMDB を提案しました。これは、LMDB が軽量 (64k のランタイム コード) で、かつ、 GPL互換ライセンス であるためです。

LMDB の欠点は、単一の C 実装に依存していることです。 これにより、JGit (Git の一般的な再実装) 内への組み込みが困難になり、仮想ストレージ (JGit DFS 用) へのホスティングが事実上不可能になります。

すべての主要な Git 実装 (git-core、JGit、libgit2) でサポートできる共通の形式が強く推奨されます。