最近まで、Gitでの参照の保存方法は、「files」フォーマットだけに限られていましたが、Git 2.45.0の新機能により、Gitでは参照を「reftable」フォーマットで保存できるようになりました。この新しいフォーマットは、バイナリフォーマットで非常に複雑ですが、その複雑さが「files」フォーマットのいくつかの欠点を解決します。「reftable」フォーマットは、次のような目的で設計されました。
- 単一の参照の検索と参照範囲のイテレーションを、可能な限り効率的かつ迅速に行えるようにする。
- 複数の参照が部分的にしか更新されていない中途半端な状態をGitが読み取らないように、一貫した参照の読み取りをサポートする。
- 複数の参照の更新がオールオアナッシング型のオペレーションとして実行される、アトミック書き込みをサポートする。
- 参照および参照ログの効率的な保存。
この記事では、「reftable」フォーマットの仕組みを詳しく見ていきます。
Gitでの参照の保存方法
「reftable」フォーマットについて詳しく掘り下げる前に、まずはGitがこれまで参照をどのように保存してきたのかを簡単に振り返ってみましょう。すでにご存知の方は、このセクションを読み飛ばして構いません。
Gitリポジトリは、次の重要な2つのデータ構造を追跡します。
-
オブジェクト:リポジトリの実際のデータ(コミット、ディレクトリツリー構造、ソースコードを含むblobなど)を格納しています。オブジェクトは互いに参照し合い、オブジェクトグラフを形成します。さらに、各オブジェクトにはオブジェクトIDがあり、そのオブジェクトを一意に識別します。
-
参照:ブランチやタグなどがあります。これらはオブジェクトグラフへのポインタであり、オブジェクトに覚えやすい名前を付けたり、開発履歴の異なるトラックを追跡するのに使われます。たとえば、リポジトリには
main
ブランチが含まれている場合があり、これは特定のコミットを指し示すrefs/heads/main
という名前の参照です。
参照は、参照データベースに保存されます。Git 2.45.0までは、「files」データベースフォーマットのみが存在していました。このフォーマットでは、各参照が通常のファイルとして保存され、そのファイルには次のいずれかが含まれます。
- 通常の参照:指し示すコミットのオブジェクトIDが保存されています。
- シンボリック参照:別の参照の名前が保存されています。これは、シンボリックリンクが別のファイルを指し示すのと似ています。
定期的に、これらの参照は検索を効率化するために1つのpacked-refsファイルにまとめられます。
次の例は、「files」フォーマットがどのように動作するかを示しています。
$ git init .
$ git commit --allow-empty --message "Initial commit"
[main (root-commit) 6917c17] Initial commit
# HEADはrefs/heads/mainを指すシンボリック参照です。
$ cat .git/HEAD
ref: refs/heads/main
# refs/heads/mainはコミットを指す通常の参照です。
$ cat .git/refs/heads/main
6917c178cfc3c50215a82cf959204e9934af24c8
# git-pack-refs(1)はこれらの参照をpacked-refsファイルにパック化します。
$ git pack-refs --all
$ cat .git/packed-refs
# pack-refs with: peeled fully-peeled sorted
reftableフォーマットの構造概要
Git 2.45.0以降がインストールされている場合、--ref-format=reftable
スイッチを使用して「reftable」フォーマットでリポジトリを作成できます。
$ git init --ref-format=reftable .
Initialized empty Git repository in /tmp/repo/.git/
$ git rev-parse --show-ref-format
reftable
# わかりやすくするために不要なファイルを削除しています。
$ tree .git
.git
├── config
├── HEAD
├── index
├── objects
├── refs
│ └── heads
└── reftable
├── 0x000000000001-0x000000000002-40a482a9.ref
└── tables.list
4 directories, 6 files
まず、リポジトリの設定を見ると、それにはextension.refstorage
キーがあります。
$ cat .git/config
[core]
repositoryformatversion = 1
filemode = true
bare = false
logallrefupdates = true
[extensions]
refstorage = reftable
この設定は、リポジトリが「reftable」フォーマットで初期化されており、「reftable」バックエンドを使用してアクセスするようGitに指示するものです。
不思議なことに、このリポジトリにはまだ「files」バックエンドが使われているかのように見えるいくつかのファイルがあります。
-
HEAD
は通常、現在チェックアウト済みのブランチを指すシンボリック参照です。「reftable」バックエンドでは使用されませんが、GitクライアントがディレクトリをGitリポジトリとして検出するために必要です。したがって、「reftable」フォーマットを使用する場合、HEAD
はref: refs/heads/.invalid
という内容のスタブになります。 -
refs/heads
は、this repository uses the reftable format
という内容が書かれているファイルです。「reftable」フォーマットを認識できないGitクライアントは、このパスがディレクトリであると想定します。したがって、このパスをファイルとして作成することで、古いGitクライアントが「files」バックエンドでリポジトリにアクセスしようとすると、意図的に失敗するようになります。
実際の参照は、次のようにreftable/
ディレクトリに保存されます。
$ tree .git/reftable
.git/reftable/
├── 0x000000000001-0x000000000001-794bd722.ref
└── tables.list
$ cat .git/reftable/tables.list
0x000000000001-0x000000000001-794bd722.ref
ここには、次の2つのファイルがあります。
-
0x000000000001-0x000000000001-794bd722.ref
は、参照と参照ログデータをバイナリフォーマットで含むテーブルです。 -
tables.list
は、テーブルのリストです。リポジトリの現在の状態では、このファイルにはテーブルの名前の1行だけが含まれています。このファイルは「reftable」データベースにある現在有効なテーブルをまとめて追跡し、新しいテーブルがリポジトリに追加されるたびに更新されます。
次のように、参照を更新すると、新しいテーブルが作成されます。
$ git commit --allow-empty --message "Initial commit"
[main (root-commit) 1472a58] Initial commit
$ tree .git/reftable
.git/reftable/
├── 0x000000000001-0x000000000002-eb87d12b.ref
└── tables.list
$ cat .git/reftable/tables.list
0x000000000001-0x000000000002-eb87d12b.ref
ご覧のとおり、以前のテーブルは新しいテーブルに置き換えられました。さらに、tables.list
ファイルが更新され、新しいテーブルが取り込まれました。
テーブルの構造
前述のとおり、参照データベースの実際のデータはテーブルに含まれています。テーブルは大まかに次のような複数のセクションに分かれています。
- header:テーブルに関するメタデータが含まれています。これには、フォーマットのバージョン、ブロックサイズ、およびリポジトリで使用されるハッシュ関数(SHA1、SHA256など)が、他の情報と一緒に含まれています。
- ref:参照が含まれています。これらのレコードは参照名と等しいキーを有し、通常の参照の場合はオブジェクトIDを、シンボリック参照の場合は他の参照を指します。
- obj:オブジェクトIDからそれらのオブジェクトIDを指す参照への逆マッピングが含まれています。これにより、Gitは特定のオブジェクトIDを指す参照を効率的に検索できます。
- log:参照ログエントリが含まれています。これらのレコードは、参照名にログエントリの番号を表すインデックスを付け足したものと等しいキーを有し、 さらに、古いオブジェクトIDと新しいオブジェクトID、およびその参照ログエントリのメッセージを含みます。
- footer:各セクションへのオフセットが含まれます。
各セクションのタイプは、似たような構造を持っています。セクションには一連のレコードが含まれており、各レコードのキーでソートされています。たとえば、 refs/heads/aaaaa
と refs/heads/bbb
という2つの参照レコードがある場合、これらの参照名がそれぞれのキーとなり、refs/heads/aaaaa
がrefs/heads/bbb
よりも前に来ます。
さらに、各セクションは固定長のブロックに分割されています。このブロックの長さはヘッダー(header)にエンコードされており、次の2つの目的を果たします。
- セクションの開始位置とブロックサイズに基づき、リーダー(reader)は各ブロックの開始位置を暗に認識します。これにより、Gitは先行するブロックを読み込むことなくセクションの途中に簡単に移動できるため、ブロック上でのバイナリ検索が可能になり、レコードの検索を高速化します。
- 一度に読み込むディスクデータの量をリーダーが認識できるようにします。このために、ブロックサイズはデフォルトで4KiBに設定されており、これはハードディスクのセクターサイズとしては最も一般的です。最大ブロックサイズは16MBです。
たとえば、「ref」セクションを覗いてみると、おおよそ次の図のようになります。ここで留意すべき点は、レコードがブロック内で、そしてブロック間の両方で辞書順に並んでいることです。
現在の情報を基に、次の手順でレコードを検索できます。
-
各ブロックの最初のレコードのキーを確認してバイナリ検索を行い、目的のレコードが含まれているブロックを特定します。
-
特定したブロック内で線形検索を行い、目的のレコードを特定します。
この手順はまだ少し非効率です。多くのブロックがある場合、目的のブロックを特定するためにバイナリ検索で対数的に多くのブロックを読み込むことが必要になる場合があります。また、ブロックに多数のレコードが含まれている場合、線形検索中にすべてのレコードの読み込みが必要になる可能性もあります。
「reftable」フォーマットには、これらのパフォーマンス問題に対処する追加のメカニズムが組み込まれています。後のセクションでこれらについて詳しく説明します。
プレフィックス圧縮
お気づきかもしれませんが、すべてのレコードキーにはrefs/
という共通のプレフィックスがあります。これはGitでは一般的です。
- すべてのブランチは
refs/heads/
で始まります。 - すべてのタグは
refs/tags /
で始まります。
したがって、後続のレコードもキーの大部分で共通のプレフィックスを持つことが予想されます。これを利用して、貴重なディスク容量を節約できます。ほとんどのキーが共通のプレフィックスを持つことがわかっているため、これを最適化するのは理にかなっています。
この最適化にはプレフィックス圧縮を使用します。各レコードは、前のレコードのキーから何バイトを再利用するかを示すプレフィックスの長さがエンコードされています。たとえば、refs/heads/a
とrefs/heads/b
という2つのレコードがある場合、後者はプレフィックスの長さを11バイトとしてエンコードし、サフィックスとしてb
だけを保存します。その後、リーダーはrefs/heads/a
の最初の11バイト(refs/heads/
)を取得し、サフィックスb
を追加します。
再起点
前述のように、現在の「reftable」フォーマットの理解に基づいてブロック内の参照を検索する最適な方法は、線形検索です。これは、レコードが固定長ではないため、ブロックの先頭からスキャンしないとレコードの開始位置を特定できないためです。また、レコードが固定長であったとしても、レフィックス圧縮があるため、先行するレコードを読み込む必要があり、ブロックの途中に直接移動はできません。
しかし、ブロックには数百から数千のレコードが含まれる可能性があり、線形検索は非常に非効率です。この問題に対処するために、「reftable」フォーマットは各ブロックに「再起点」と呼ばれるポイントをエンコードします。再起点は圧縮されていないレコードであり、ここではプレフィックス圧縮がリセットされます。したがって、再起点のレコードは常に完全なキーを含んでおり、先行するレコードをスキップしながら直接移動してレコードを読み込むことが可能になります。これらの再起点は各ブロックのフッターにリストされています。
この情報を用いることで、ブロック全体を線形検索する必要がなくなります。代わりに、再起点のバイナリ検索を行い、目的のキーより大きい最初の再起点を探します。そこから、目的のレコードが_前の_再起点から特定された再起点までのセクションに存在することがわかります。
したがって、レコードを検索する最初の手順(ブロックのバイナリ検索、レコードの線形検索)は次のようになります。
-
ブロックのバイナリ検索を行い、目的のレコードが含まれるブロックを特定します。
-
再起点のバイナリ検索を行い、目的のレコードが含まれるブロックのサブセクションを特定します。
-
特定したサブセクション内でレコードの線形検索を行います。
インデックス
ブロック内のレコードの検索はかなり効率化されましたが、ブロック自体の位置を特定するのはまだ効率的とはいえません。数個のブロックであればバイナリ検索でも十分に効率的です。しかし、数百万もの参照を含むリポジトリには数百から数千のブロックが存在します。この場合、追加のデータ構造がなければ、平均して対数的に多くのディスクアクセスが必要になります。
この問題を避けるために、各セクションの後にブロックを効率的に検索するためのインデックスセクションを追加できます。各インデックスレコードには次の情報が含まれます。
- インデックス化されているブロックの位置。
- インデックス化されているブロックの最後のレコードのキー。
3つ以下のブロックであれば、バイナリ検索は最大2回のディスク読み取りで目的のブロックを特定できます。この読み取り回数は、インデックスを使用する場合も同じです。具体的には、インデックス自体を読み取るための1回と、目的のブロックを読む取るための1回です。したがって、インデックスは実際に読み取り回数を減らす場合、つまりインデックス化されたブロックが4つ以上ある場合にのみ作成されます。
次の疑問は、インデックス自体が複数のブロックにまたがるほど大きくなった場合はどうすべきかという点です。その答えは、そのインデックスをインデックス化するために別のインデックスを作成するというものです。この複数階層のインデックスは、数十万もの参照があるリポジトリでのみ必要となります。
次のインデックスを使用することで、レコードの検索手順をさらに効率化できます。
- テーブルのフッターを見てインデックスがあるかどうかを確認します。
- インデックスがあれば、バイナリ検索を行い、目的のブロックを特定します。このブロックがインデックスブロック自体を指している場合は、目的のレコードタイプに到達するまでこの手順を繰り返します。
- インデックスがなければ、先ほどのようにブロックのバイナリ検索を行います。
- 再起点のバイナリ検索を行い、目的のレコードが含まれているブロックのサブセクションを特定します。
- 特定したサブセクション内でレコードの線形検索を行います。
複数のテーブル
ここまでは、単一のテーブルを読み取る方法について説明してきましたが、tables.list
という名前が示すように、「reftable」データベースには複数のテーブルを格納できます。
リポジトリ内の参照を更新するたびに、新しいテーブルが作成され、tables.list
に追加されます。したがって、最終的には次のように複数のテーブルが存在することになります。
$ tree .git/reftable/
.git/reftable/
├── 0x000000000001-0x000000000007-8dcd8a77.ref
├── 0x000000000008-0x000000000008-30e0f6f6.ref
└── tables.list
$ cat .git/reftable/tables.list
0x000000000001-0x000000000007-8dcd8a77.ref
0x000000000008-0x000000000008-30e0f6f6.ref
リポジトリの実際の状態を読み取るためには、これらの複数のテーブルを単一の仮想テーブルにマージする必要があります。
ここで疑問が生じます。それは、参照が更新されるたびにテーブルが作成され、同じ参照が複数回更新される場合、「reftable」フォーマットは特定の参照の最新の値をどのように把握するのか、ということです。直感的には、最新のテーブルに含まれる参照の値が最新であると仮定できます。
実際には、各レコードには「更新インデックス」と呼ばれるものがあり、これがレコードの「優先度」をエンコードしています。たとえば、同じ名前の2つの参照レコードが存在する場合、更新インデックスが高い方が低い方を上書きします。
これらの更新インデックスは、上のファイル構造で確認できます。長い16進文字列(例:0x000000000001
)が更新インデックスであり、テーブル名の左側がテーブルに含まれる最小の更新インデックス、そして右側が最大の更新インデックスを示しています。
テーブルのマージは、参照レコードのキーと更新インデックスによって順序付けられた優先キューを介して行われます。すべての参照レコードをスキャンする場合、次の手順で行います。
- 各テーブルの最初のレコードを優先キューに追加します。
- 優先キューの先頭を取り出します。このキューは更新インデックス順に並んでいるため、先頭にあるレコードは最新のバージョンでなければなりません。そのテーブルの次の項目を優先キューに追加します。
- 同じ名前を持つすべてのレコードをキューから削除します。これらのレコードは上書きされているため表示されません。レコードを削除した各テーブルについては、その次のレコードを優先キューに追加します。
これを繰り返して、他のキーのレコードを読み取ります。
テーブルには、レコードが削除されたことを示す特殊な「トゥームストーン」レコードが含まれている場合があります。このように、すべてのテーブルを書き換えることなく、レコードを削除できます。
自動圧縮
優先キューの考え方はシンプルですが、このアプローチでは、マージするテーブルの数が数百個、あるいは数十個であっても、非常に非効率になります。参照を更新するたびに新しいテーブルがtables.list
ファイルに付加されるのは事実ですが、他にも重要な特徴があります。
それが、自動圧縮です。新しいテーブルがテーブルリストに付加された後、「reftable」バックエンドは一部のテーブルをマージする必要があるかどうかを確認します。これは、シンプルなルールを使って行われます。具体的には、テーブルのリストがファイルサイズの幾何数列を形成しているかどうかをチェックします。すべてのテーブルn
は、その次に新しいテーブルn+1
の2倍以上のサイズでなければなりません。この幾何数列が維持されなかった場合、バックエンドはテーブルを圧縮して幾何数列を復元します。
時間が経つにつれて、次のような構造になります。
$ du --apparent-size .git/reftable/*
429 .git/reftable/0x000000000001-0x00000000bd7c-d9819000.ref
101 .git/reftable/0x00000000bd7d-0x00000000c5ac-c34b88a4.ref
32 .git/reftable/0x00000000c5ad-0x00000000cc6c-60391f53.ref
8 .git/reftable/0x00000000cc6d-0x00000000cdc1-61c30db1.ref
3 .git/reftable/0x00000000cdc2-0x00000000ce67-d9b55a96.ref
1 .git/reftable/0x00000000ce68-0x00000000ce6b-44721696.ref
1 .git/reftable/tables.list
すべてのテーブルにおいて、size(n) > size(n+1) * 2
という性質が維持されていることに注目してください。
自動圧縮がもたらすメリットのひとつは、「reftable」バックエンドのメンテナンスが自動化されることです。これにより、リポジトリでgit pack-refs
を実行する必要がなくなります。
さらに詳しく知りたい方へ
この記事では、新しい「reftable」フォーマットの仕組みについて解説しました。さらに詳しく知りたい場合は、Gitプロジェクトで提供されるテクニカルドキュメントをご参照ください。
Git 2.45.0の新機能では、このバージョンにおけるその他の変更点をご確認いただけます。
監修:川瀬 洋平 @ykawase
(GitLab合同会社 カスタマーサクセス本部 シニアカスタマーサクセスマネージャー)