Gitでのリファレンス削除の最適化

Japanese Translation:

サマリー：

Git は、従来のファイルベースのバックエンドが困難に直面する巨大リポジトリにおける深刻なパフォーマンスのボトルネックを解消するために、参照管理システムを大幅に最適化しました。最も重要な改善点は、反復処理の遅延およびインノードコストの高さへの対応であり、これは GitLab などの企業環境において 1500 万件以上の参照を管理するよう拡張性を確保します。ベンチマーク結果によると、単一の参照を削除する操作は以前には非効率なテキストベースの出力関数によるものや全ファイルの書き換えペナルティにより 2 秒以上かかるものでしたが、C コードにおける高速なブロック書込み手法（fprintf の代わりに fwrite を使用）への切り替えによって著しく削減されました。これらのパッチは Git 2.98 に含まれる移行期向けの修正であり、Rust の必須化への道筋を築くとともに、Git 3.0 では reftable バックエンドをデフォルトのストレージメカニズムとして導入する方向性を橋渡しします。このアップデートにより、大規模な Git ワークフローが効率的に維持され、既存の利用者の運用やインフラストラクチャに対する即時の中断を必要としなくなります。

Git の参照管理：ファイルベースから reftable へ、そして C の最適化

参照（References） と オブジェクト は、Git のストレージ機構の中核を担います。端的に言えば、参照はリポジトリ内の特定のオブジェクトへの命名ポインタです。

ファイルベース・バックエンド: Git 2.45 までの間、参照保存の唯一の手段でした（Git 2.56 でもデフォルト）。
reftable バックエンド: より優れている新方式で、Git 3.0 でデフォルトに切り替わる予定。

詳細は reftable バックエンドをご覧ください。

ファイルベース（Files backend）による管理

ファイルベースでは、新しい参照ごとに個別のファイルを作成します。これを**ローザーフ（Loose refs）**と呼びます。

ローザーフ（Loose refs）

各参照が個別のファイルとして存在します。ブランチ作成時の例：

❯ git init --quiet --ref-format=files repo; cd repo
❯ git commit --allow-empty -m "new commit"
[main (root-commit) 66b401c] new commit
❯ git branch shiny-new-branch
❯ eza --tree .git/refs/
.git/refs
├── heads
│   ├── main
│   └── shiny-new-branch
└── tags
❯ cat .git/refs/heads/shiny-new-branch
66b401c8c91c975f9f126bc85d9b2eba54828d86

課題

ローザーフはシンプルですが、スケーラビリティに以下の課題があります：

巨大な inode コスト: 参照ごとに個別のファイルが必要なため。
更新時の負荷: 各更新で対応する
```
.lock
```
ファイルを扱う必要があるため。
原子性の欠如: 複数参照の更新において発生しやすい問題。
ファイルシステムへの依存: 文字ケース感度（case sensitivity）などの制約。
名前衝突:
```
refs/heads/foo
```
と
```
refs/heads/foo/bar
```
を共存させることができない。

さらに、何百万もの参照を順列（iterate）するのは非効率です。大規模モノレポ（例：GitLab のリポジトリには 1,500 万以上の参照あり）では深刻な問題となります。

パックド・レフ（Packed refs）

これらの課題を軽減するために、Git は「packed-refs」形式を導入しました。これは参照とオブジェクト ID のソート済みマッピングが格納された単一ファイルです。

仕組みの確認

5 つのブランチを作成し、ローザーフを

packed-ref

ファイルにまとめ込む操作：

# ブランチ作成
❯ for i in $(seq 1 5); do git update-ref refs/heads/branch-$i HEAD; done

# ローダーフをパック化する
❯ git refs optimize --all

# 結果を確認
❯ cat .git/packed-refs
# pack-refs with: peeled fully-peeled sorted
ec4aecaa91db6da8a280368110866935080f231c refs/heads/branch-1
...

ハイブリッド構造と削除の課題

Git の参照データストアは、ローザーフとパックド・レフのハイブリッド構造となりました。

作成: 新しい参照は常にローザーフとして作成（読み取り時にもローザーフが優先）。
最適化: ローザーフが蓄積されると、
```
git refs optimize
```
により
```
packed-refs
```
にまとめ込まれます。

しかし、削除操作には課題があります。参照がパックド形式の場合、

packed-refs

ファイルそのものを書き換える必要があり、非効率です。

# 100 万個の参照を含む packed-ref を作成（700MB）
❯ begin
      printf '# pack-refs with: peeled fully-peeled sorted \n'
      awk -v o=$oid 'BEGIN { for (i = 1; i <= 10000000; i++) printf "%s refs/heads/branch-%010d\n", o, i }'
  end  > .git/packed-refs

❯ eza -l .git/packed-refs
-rw-r--r-- 700M karthik  8 Nov 15:16 .git/packed-refs

# 単一の参照を削除するベンチマーク
❯ time git update-ref -d refs/heads/branch-0000499999
Executed in    2.14 secs    fish           external
   usr time    1.28 secs    0.00 millis    1.28 secs
   sys time    0.85 secs    2.06 millis    0.85 secs

❯ eza -l .git/packed-refs # ファイルサイズとタイムスタンプが変更されている
-rw-r--r-- 700M karthik  8 Nov 15:28 .git/packed-refs

reftable バックエンドへの移行

ファイルベースの設計上の限界を明確にするため、リポジトリを新しい reftable バックエンドへ移行する考えがあります。reftable はバイナリテーブルを使用し、削除操作も単なる「トモストーン（marker）」として軽量に実装しています。

最適化への挑戦：Rust で C を置き換える

ファイルベースバックエンドには約 20 年の最適化歴史があり、新たな発見は困難です。GitLab では reftable 移行が優先課題ですが、C の非効率性を明らかにするため、Rustを用いてゼロから実装し比較することにしました。

ベンチマーク設定

C と Rust の ABI ブーダーコストを測定するためにベンチマークを実施：

❯ ./delete-ref/run --revisions ~/code/git v2.56.0,rust-packed-refs --build-system meson --parameter-list refformat files --parameter-list refcount 100000

ベンチマーク結果（削除時：refformat = files, refcount = 100000）

パターン	実行回数	平均時間	メモリ	改善率
v2.56.0 (C)	32	37.1 ms	11.8 MiB	-
rust-packed-refs	39	30.6 ms	11.8 MiB	-17.7%

Rust バージョンの方が約 17.7% 高速でした。なぜでしょうか？

コード分析：C vs Rust

Rust の実装

参照を順列して更新を適用する際、既存レコードと完全一致するかチェックし、そのまま書き込むかスキップします。

let (rec_name, rec_start, rec_end) = match existing_rec {
    Some(r) => r,
    None => break, // 無ければ破棄
};

// この既存レコードと完全に一致する更新があるか確認する
if ui < updates.len() {
    let u_name = unsafe { CStr::from_ptr(updates[ui].refname).to_bytes() };
    if u_name == rec_name {
        if !updates[ui].oid_hex.is_null() {
            // 置換処理
            unsafe { write_update_line(&mut out, &updates[ui])? };
        }
        // それ以外：削除 – 既存レコードをスキップ
        ui += 1;
        continue;
    }
}

// 更新なしなのでそのままコピー
out.write_all(&records[rec_start..rec_end])?;

C の実装（非効率な部分）

C のバージョンでは、参照を順列した上で、変更されていなくても

write_packed_entry()

を呼び出し、

fprintf()

で情報を再構築しています。これは単なる無駄作業です。

if (cmp < 0) {
    // 古い参照をそのまま渡す（ただし書き込み関数を呼ぶ）
    if (write_packed_entry(out, iter->ref.name,
                           iter->ref.oid, iter->ref.peeled_oid))
        goto write_error;

    if ((ok = ref_iterator_advance(iter)) != ITER_OK) {
        ref_iterator_free(iter);
        iter = NULL;
    }
}

解決策：fwrite を使用して最適化

問題:

write_packed_entry()

が

fprintf()

でデータを書き直しているため、変更がない場合も無駄な処理が発生。

解決策: データを追跡し、変更がない場合はそのままバイナリとして書き込む（

fwrite

を使用）ように修正しました。

@@ -1530,9 +1534,15 @@ static enum ref_transaction_error write_with_updates(struct packed_ref_store *re
 		}
 
 		if (cmp < 0) {
-			/* Pass the old reference through. */
-			if (write_packed_entry(out, iter->ref.name,
-					       iter->ref.oid, iter->ref.peeled_oid))
+			const struct packed_ref_iterator *packed_iter =
+				(const struct packed_ref_iterator *)iter;
+			size_t len = packed_iter->pos - packed_iter->record_start;
+
+			/*
+			 * リファレンスの削除時や、残りのリファレンスをそのまま書き込む際、
+			 * 何らかのフォーマット処理をスキップし、packed-refs ファイルへ直接書き込む。
+			 */
+			if (fwrite(packed_iter->record_start, len, 1, out) != 1)
 				goto write_error;
 
 			if ((ok = ref_iterator_advance(iter)) != ITER_OK) {

再ベンチマーク結果

パッチ適用後の結果：

パターン	実行回数	平均時間	メモリ	改善率
v2.56.0 (C)	19	66.5 ms	11.7 MiB	-
fix (最適化 C)	23	54.9 ms	11.8 MiB	-17.4%
rust-packed-refs	23	55.2 ms	11.8 MiB	-17.0%

成果: C のバージョンでも、Rust と同等のパフォーマンス（約 18% の高速化）を達成しました。

このパッチは現在メーリングリストに送信されており、マスターブランチへのマージが完了しました（コミット:

fc70f528aa1927012538052014d7ea784b5a38fa

）。

バージョン: Git v2.98 に組み込まれます。
注釈: v2.56 から v2.98 への番号変更は、Git 3.0 への移行準備としてリリース間隔を空けるためです。