ハクソク

世界を動かす技術を、日本語で。

GitLabリポジトリのバックアップ時間を48時間から41分に短縮した方法

353日前原文(about.gitlab.com)

概要

  • 大規模リポジトリ のバックアップ時間短縮のため、 Git内部のO(N²)問題 を特定・修正
  • 新アルゴリズム 導入により、バックアップ時間が 48時間から41分 に大幅短縮
  • 運用コスト削減 ・リスク低減・バックアップ戦略の拡張性向上
  • GitLab 18.0 以降、全ユーザーが追加設定なしで恩恵を享受可能
  • Git本体にも貢献 し、全Gitユーザーのスケーラビリティ向上に寄与

大規模リポジトリのバックアップ課題

  • リポジトリの肥大化 に伴い、バックアップ作成が 時間的・資源的に困難
  • バックアップ頻度とシステムパフォーマンス のトレードオフ発生
  • バックアップウィンドウの確保困難、24時間稼働組織での運用障壁
  • 長時間処理による失敗リスク （ネットワーク障害・サーバ再起動など）
  • レースコンディション による不整合なバックアップ発生リスク
    • 作成中にリポジトリ内容が変化する可能性
  • 結果として バックアップ頻度や完全性の妥協、外部ツール依存の増加

技術的ボトルネックの特定

  • GitLabのバックアップ機能 はgit bundle createコマンドを利用
    • 全リファレンス（ブランチ・タグ等）を含むリポジトリスナップショット作成
  • リファレンス数増加 に伴い 処理時間が指数関数的に増加
  • Flame graph解析 により、object_array_remove_duplicates()関数が全体の約80%を占有
    • 2009年コミットで導入、重複リファレンス排除のため O(N²)のネストループ を使用
  • 大規模リポジトリ （リファレンス数100万以上）でバックアップが48時間超に

アルゴリズム改善による解決策

  • ネストループ を マップ構造 へ置換
    • 各リファレンスをマップに追加することで 重複排除を高速化
  • ベンチマーク結果
    • 10,000リファレンスで 6倍以上の性能向上
    • 100,000リファレンスで 14.6秒→2.3秒 に短縮（HEAD基準）
  • パッチはGit本体にマージ済み
    • GitLabでは 即時バックポート し、全顧客が恩恵を受けられるよう対応

効果と顧客へのメリット

  • 最大リポジトリのバックアップ時間 が 48時間→41分 （1.4%）に短縮
  • リポジトリサイズ問わず一貫したパフォーマンス
  • サーバ負荷・運用コストの大幅削減
  • 全てのバンドル操作で恩恵 （バックアップ以外にも適用可能）
  • エンタープライズのバックアップ戦略が劇的に進化
    • 毎晩の定期バックアップが現実的に
    • 復旧ポイント目標（RPO） の大幅短縮、ビジネスリスク低減
    • メンテナンスウィンドウ短縮 によるコスト削減
    • 将来のリポジトリ拡張にも柔軟対応

GitLab 18.0以降の運用

  • 追加設定不要で自動適用
  • 全ライセンスユーザーが即時利用可能
  • 持続的なパフォーマンス改善への取り組み
    • 今後もボトルネック特定・解消を継続

Gitコミュニティへの貢献と今後

  • Git本体への貢献 により、全Gitユーザーのスケーラビリティ向上
  • 継続的なインフラ改善 とエンタープライズ向け機能強化
  • GitLab 18バーチャルローンチイベント で他の改善点も紹介予定
    • 参加登録を推奨

Hackerたちの意見

「アルゴリズムの変更で修正したから、バックアップ時間が指数的に減った」って言ってるけど、バックアップ時間がO(n^2)だったら、今はO(n^2 / 2^n)になったのかな？ さすがにそれはないと思うけど。

└

これは正確な数学的定義の指数関数じゃなくて、一般的な意味で「すごく多い」ってことだね。

└

意味がないし、建設的でもないペダンティックさ。

└

n^2のアルゴリズムをlog(n)のルックアップに置き換えると、指数関数的なスピードアップが得られるよ。ハッシュマップのルックアップは通常O(1)だから、さらに速いんだ。

コミットはここにあるみたいだよ： https://github.com/git/git/commit/a52d459e72b890c192485002ec...

└

ありがとう、これで提出物と関連するディスカッションスレッドを見つけられたよ。- https://lore.kernel.org/git/20250401-488-generating-bundles-...

自分の経験では、書いたものの中でn^2の操作を排除するのが正しい選択だったことが多い。エキゾチックなアルゴリズムは書かないけど、nがどれだけ小さくても問題になることがあるのは驚きだよね。

└

80%から90%の問題に対する自分の経験則は、複雑なアルゴリズムが必要な場合はデータモデルが間違ってるってこと。コンパイラやデータベースの内部処理、ルートプランニングなどには複雑なアルゴリズムが必要だけど、全体的に見るとそれは少数派のユースケースだよね。

└

いい指摘だね。O(N^2)は最悪の時間計算量で、テストでは瞬時に感じるけど、実運用では爆発的に遅くなるから。これまでに何度も見たことがあるし、ここでもまさにそうなったね。

└

例外は、nが約10未満で、ハードウェアに制約のある何かをカウントしている場合だと思う（例えば、OBDIIコネクタにあるすべてのCANインターフェースに対する操作はO(n^(2))になることがある。nは常に1から4の間だから）。nを増やすためにハードウェアを物理的に交換する必要がないなら、n^2の操作は本当に避けるべきだよ。それに、nが大きくなりすぎたら再作業が必要だと気づくために、明示的に失敗させることも考慮した方がいいかも。

└

ブルース・ドーソンが言ってるけど、これを「ドーソンのコンピューティングの第一法則」と呼びたいな：O(n^2)はスケーリングが悪いアルゴリズムのスイートスポットで、プロダクションに入るには十分速いけど、そこに入ったら物事が崩れるほど遅いんだ。 https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

48時間もかけてgitフォルダを圧縮するのはクレイジーだよ。たった数GBなのに。41分でも結構長いと思うけど、なんでフルgitリポジトリをスナップショットしてアーカイブしないの？ git bundleって頻繁なZFSバックアップに何か追加するの？

└

これらの推奨事項があっても、この方法での同期にはリスクがあることに注意してください。Gitの通常のリポジトリの整合性チェックをバイパスするため、バックアップを取ることをお勧めします。同期後に宛先システムでデータの整合性を確認するために、git fsckを実行することも検討してください。 https://git-scm.com/docs/gitfaq#_transfers ただし、安全にバックアップを作成する方法は教えてくれないよ。個人のスケールでは、SyncthingとBtrfsのスナップショットで十分にうまくいくよ。ストレージやネットワークの速度にもよるけどね。

└

ZFSのスナップショットは、非ZFSのレプリカ、例えばS3バケットにオフサイトするのが難しいんだよね。とはいえ、git clone --bundle-uriを使うときに役立つあまり知られていない機能があるんだ。クライアントはバンドルの場所を指定できるし、サーバーがクライアントにクローン結果でバンドルの場所を送信することもできる。そうすると、クライアントはバンドルを取得して展開し、その後Gitサーバーを通じてデルタを更新できるから、大きなリポジトリをクローンする際にサーバーへの負担が軽くなって、クライアントにとっても初回クローンがめちゃくちゃ速くなるんだよね。

GitLabがGitに貢献したパフォーマンス改善がv2.50.0でリリースされる予定だよ。: https://github.com/git/git/commit/bb74c0abbc31da35be52999569...

└

これが徹底的にレビューされたのは確かだと思うけど、新しい実装で壊れる可能性のあるエッジケースはある？「Xを90%効率的にした！」って言う開発者にはちょっと警戒してるんだ。たとえそれがこんな簡単に理解できること（「マップを使うことで！」）でも、以前に間違ったけど一見妥当な仮定がされて、物事が壊れたことを見たことがあるから。

Cでコードを書くことがパフォーマンスに役立たない良い例だね。アルゴリズムやデータ構造がちゃんと考慮されてないときは特に。

└

Cだとこういうことが起こりやすいと思う。適切なコンテナを得るのにすごく手間がかかるから。C++やRustにはunordered_setやHashSetみたいなものがたくさん組み込まれてるから、みんなそれを使う可能性が高いし、「ああ、forループ使うわ」ってならないんだ。この場合、Gitにはすでに文字列のセットがあったけど、まだ標準じゃないから、元の著者がそれを知らなかった可能性が高いね。

O(n^2)は、実際の運用で使えるくらい速いけど、スケールすると問題を引き起こすくらい遅いんだ。効率の悪い運用での最悪のケースはほとんどがO(n^2)だよ。

ここには早すぎる最適化と予測的な最適化のバランスについての教訓があるみたいだね。一般的には早すぎる最適化には注意するように言われるけど、目安としては、頻繁に呼ばれる関数で明らかで実装が負担にならない最適化を探すべきかも。

面白い発見だけど、記事は1/10の長さでも十分伝わったと思う。少なくとも動画じゃなかったから、重要な詳細をサッと読みやすかったね。

なんでブロックレベルのデバイスをスナップショットしないのか、ちょっと混乱してる。情報のプロトコルがこんなに面倒を引き起こすなら、ブロックレベルのアクティビティのためにGitの操作を一時停止するのは簡単じゃないかもしれないけど、解決するのはもっと楽な問題に思える。俺は生産環境でSQLiteにこのアプローチを使ってるし、WALをオンにすれば問題がさらに解決しやすくなる。顧客はVMをX分ごとにスナップショットを取るように設定するし、GitにはWALに近いものがないから、この道を選ぶのに躊躇するのも分かる。でも、全体的な戦略はGitの変な部分に対してもずっと実行可能で頑丈だと思う。

└

Gitlabは単なるマネージドサービスじゃないよ。自己ホスト型のインスタンス用のソフトウェアもリリースしてるし。ユーザーが全員同じファイルシステムでGitlabを運用する保証も、ブロックレベルのスナップショットをサポートするファイルシステムを使う必要もない。おそらく、すべてのGitlabで機能するユニバーサルなバックアップシステムを望んでるんだろうね。

└

生産環境でSQLiteにこのアプローチを使ってる。WALをオンにすれば問題がさらに解決しやすくなる。数ヶ月前にSQLiteからより良い解決策が提供された：sqlite3_rsync https://www.sqlite.org/rsync.html