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

 (about.gitlab.com)
5 ポイント 投稿者 GN⁺ 2025-06-07 | 1件のコメント | WhatsAppで共有
  • GitLabは、大規模リポジトリのバックアップに長時間かかる問題を発見し、改善に取り組んだ
  • 主な原因は、15年前に作られたGit関数の O(N²) 計算量 にあり、アルゴリズム最適化によって性能を大幅に向上させた
  • 最適化の結果、最大のリポジトリでは バックアップ時間が48時間から41分 に短縮された
  • 改善された方式は、リソース効率と信頼性を提供すると同時に、他の Gitベースのツールやコミュニティ にも好影響を与える
  • GitLab 18.0 から、すべてのユーザーが追加設定なしでこれらの利点を享受できるようになった

リポジトリバックアップの重要性と課題

  • リポジトリのバックアップは、災害復旧戦略 の中核要素である
  • リポジトリの規模が大きくなるほど、信頼できるバックアッププロセス の複雑さも増していく
  • GitLab自身のRailsリポジトリではバックアップに48時間を要し、バックアップ頻度とシステム性能 の間で難しい選択を迫られていた
  • 大規模リポジトリでは、時間、リソース、失敗リスク、レースコンディション など多様な問題が存在する
    • その結果、定期バックアップが難しくなったり、外部ツールへの依存やバックアップ回数の削減など、組織ごとに一貫性のない戦略が生まれがちだった

性能ボトルネックの分析と原因特定

  • GitLabのバックアップ機能は、git bundle create コマンドを使ってリポジトリのスナップショットを生成する
  • このコマンドの実装過程で、reference（リファレンス）数の増加 に応じて性能ボトルネックが発生していた
  • 数百万件のリファレンスを持つ大規模リポジトリでは、バックアップに 48時間以上 かかることがあった

原因分析

  • コマンド実行中に Flame Graph で分析した結果、ボトルネック区間が特定された
  • リファレンスが10,000件のとき、実行時間の約80%が object_array_remove_duplicates() 関数で消費されていた
  • この関数は、2009年に 該当コミット で重複リファレンス処理のために導入されたものだった
    • git bundle create の利用時に重複リファレンスが含まれる場合の問題を防ぐため
    • しかし、重複検出が 入れ子のforループ で実装されていたため、O(N²) の計算量が発生していた
    • リファレンス数が増えるほど ボトルネック が深刻化する構造だった

O(N²)から効率的なマッピングへの移行

  • GitLabは、入れ子ループ の代わりに マップデータ構造 を使う方式のパッチをGitに提供した
    • 各リファレンスをマップに追加することで自動的に重複を除去し、効率よく処理する
  • この変更により git bundle create の性能が 大幅に向上 し、大量のリファレンスを持つ環境でもスケール可能になった
  • ベンチマークでは、リファレンス10万件を基準に 6倍以上 の性能改善が確認された

大幅に短縮されたバックアップ時間と効果

  • 最大リポジトリのバックアップ所要時間は 48時間から41分（1.4%水準）へと減少した
  • リポジトリ規模に左右されない 一貫した性能 の提供が可能になった
  • サーバー負荷の低減、バックアップに基づくGitコマンド全般の 性能向上 などの副次的な利点も得られた
  • このパッチは upstream Git に取り込まれ、GitLabでは顧客がすぐに恩恵を受けられるよう即座に適用された

GitLabユーザーにとっての実際の変化

  • 大企業の顧客は、連夜のバックアップ を開発ワークフローと衝突させることなく実行できるようになった
  • 復旧時点目標（RPO） が短縮されたことで、災害時のデータ損失リスクが大幅に減少した
  • リソース消費や保守時間、クラウドコスト など運用オーバーヘッドも削減された
  • リポジトリ規模が拡大しても、バックアップ頻度とシステム性能 の間で悩む必要がなくなった
  • これで、すべてのGitLabユーザーが 構成変更なしで これらの利点を享受できる

次のステップと意義

  • 今回の改善は、高いスケーラビリティを備えたエンタープライズ級Gitインフラ の構築に向けたGitLabの継続的な取り組みの一部である
  • GitLabが貢献した変更はupstream Gitプロジェクトにも反映され、業界全体とオープンソースコミュニティ に前向きな波及効果をもたらしている
  • このようなインフラ改善の取り組みは、他の 中核的な性能改善作業 のモデルにもなっている

GitLabの性能アプローチについてさらに深く知りたい場合は、GitLab 18バーチャルローンチイベントで確認できる

関連記事

1件のコメント

 
GN⁺ 2025-06-07
Hacker Newsの意見

  • GitLabがGitに貢献した性能向上コードはv2.50.0でリリース予定との情報共有。関連コミットリンク

  • 実体験から、自分が書いたコードでn^2演算を取り除くことは常に正しい選択だったと強調。特別なアルゴリズムを書かなくても、ごく小さなnの値でも問題が簡単に表面化する点に驚いたという感想

    • Bruce Dawsonの第一コンピューティング法則を引用。O(n^2)は最悪のスケーラビリティ問題を引き起こす地点であり、本番前は十分速く見えても、いざデプロイされると致命的な性能低下が発生する部分だという話。関連投稿リンク

    • O(N^2)の時間計算量はテストでは速く見える一方で、本番では深刻な問題を引き起こす状況を何度も目撃したという個人的経験の共有

    • 自分の経験では、問題の大半（80〜90%）で複雑なアルゴリズムが必要になるなら、データモデル自体が正しくないことの兆候だという意見。コンパイラ、DB内部、経路計画など一部の特別なケースでのみ、複雑なアルゴリズムが本質的に必要だと考えている

    • nが10未満の小規模ハードウェア限定ケースだけが例外だと言及（CANインターフェースなど）。ハードウェア交換なしにnが増えうるなら、必ずn^2演算を避けるべきで、設計上の制限や事前検知を通じて再設計の必要性を認識すべきだと勧めている

    • 自分はn^3演算のせいで、わずか10,000要素でボトルネックが発生しているのに、まだ解決方法を見つけられず困っていると吐露

  • 面白い発見だと評価しつつ、本文は1/10の長さでも十分に効果的なコミュニケーションができただろうという惜しさも共有。それでも動画コンテンツではなく、流し読みしやすかったのはよかったという肯定的な面にも言及

    • 記事をまだ読んでいない人向けに、flame graphの後、バックポートへの言及の前まで読んで止めるのが要点把握には最も効率的だというコツ

    • 記事全体の文体が、LLM（大規模言語モデル）が生成したかのように感じられるほど長く、その点が印象に残ったという感想

    • 記事がもっと長くても構わなかったと思う一方で、バックアップバンドルをなぜ2つのrefで作ったのかはいまだに疑問だという意見

  • gitフォルダ（数GB）の圧縮に48時間もかかること、そして41分でさえ長いと受け止めている。git repo全体をそのままスナップショット／アーカイブせず、なぜわざわざgit bundleを使うのか、特別な理由があるのか疑問。git bundleに、頻繁に行われるZFSバックアップよりどんな利点があるのか気になる

    • git公式FAQでは、この方式はGitの通常の整合性チェック手順を迂回するため危険性があるとされている。このような場合、コレクションの整合性検証のためにgit fsckが推奨される。個人用途なら、SyncthingやBtrfsスナップショットだけでも十分に高速かつ安定している。関連文書

    • ZFSスナップショットをS3のような非ZFSベースへオフサイトバックアップするには制約があると言及。git bundleのあまり知られていない機能として、git clone --bundle-uriで場所を指定でき、サーバーがクライアントにバンドルの場所を知らせれば、クライアントはそのバンドルを受け取ってすばやく展開し、差分更新だけをサーバーから受け取ればよいため、大規模repoの複製負荷を大きく減らせる

    • 結局、キャッシュが必要な箇所にキャッシュを追加したようなものだという評価。通常、git repoは分散システムという性質上、別のリポジトリへミラーリングし、ファイルシステムのスナップショット／バックアップツールで管理すればよいのではないかという疑問。重要なのは、重要なバージョン管理情報そのものが分散されているべきだという点を強調

  • gitバックアップの経験はあまりないが、ローカルrepoから直接バックアップを作るとレースコンディションが起きる理由が不思議だという疑問の共有

  • 上位層のデータプロトコルのせいでここまで厄介なら、むしろブロックレベルのスナップショットを使わない理由が気になる。GitのようにWAL（Write Ahead Logging）がないことが障害ではあるが、SQLiteはWALモードを追加するだけで手軽にブロックスナップショットを取る戦略を実運用で活用している。Gitにもこうしたアーキテクチャが適用されれば、はるかに安定したバックアップ戦略が可能になるはずだという考え

    • GitにWALに似たメカニズムがないことで起きる問題に共感し、スナップショットだけを頼りにバックアップすると、復元時にリポジトリが壊れる致命的な問題を経験したと共有。復旧は可能だが非常に面倒な問題だと付け加えている

    • SQLiteでは最近さらに良い案としてsqlite3_rsyncというソリューションが登場したという豆知識の共有

    • GitLabは単なるマネージドサービスではなく、自前でインストールしてさまざまな環境で使える製品なので、ユーザーごとにファイルシステムやスナップショット対応の有無、OS条件が異なる。つまり、あらゆる環境で普遍的に動作する独立したバックアップシステムを求めているというGitLab側の事情の説明

  • 「アルゴリズムの変更でバックアップ時間を指数関数的に（Exponentially）短縮した」という表現を見て、O(n^2)からO(n^2/2^n)に減ったという意味なのかと疑問。実際にはそんなはずはないだろうとの推測

    • 修正された関数のアルゴリズム計算量自体は実際に6倍速くなり、その他の使用文脈では全体の実行時間が1%にまで減るという劇的な結果だったため、この場合「指数的改善」という表現はマーケティング的には妥当だと解釈できる。厳密な計算量の定義には大きな意味はないという説明

    • 日常会話での「exponential」は数学的に厳密な意味ではなく、「ものすごく改善した」程度の比喩的意味で使われることを明確にしている

    • 自分の解釈では、nがlog(n)まで減った可能性もあると思う。量子フーリエ変換が従来のDFTより指数関数的に速いとよく表現される背景と似ており、計算量がn^2からnlognに変わる状況に言及

    • n^2アルゴリズムをlog(n)探索方式に置き換えれば速度は指数関数的に向上すると言ってよいが、実際にはハッシュマップ参照のようにO(1)まで行く場合が多く、それ以上に速い

    • こうした議論自体が非生産的な揚げ足取りだと思う

  • Cで書いたからといって性能が必ず高いわけではなく、データ構造とアルゴリズムの方が重要だと示す良い例だという意見

    • Cは適切なコンテナを実装するのがあまりに難しいため、この種の性能問題がより頻繁に起きる。C++やRustはunordered_set/HashSetのような組み込みデータ構造のおかげで、開発者がforループ1本で雑に済ませず、自然に最適化する傾向がある。今回のケースでもGitにはstring setがあるが標準的ではないため、元の作者が知らなかった可能性が高いという分析

  • 早すぎる最適化と予測的（anticipatory）最適化の間にはバランスが必要だという教訓に言及。一般には早すぎる最適化を戒めるが、非常に頻繁に呼ばれる関数における明白で簡単な最適化は、あらかじめ適用しておくのがよいというルールの提案

    • 実装当時、使用言語にset-of-stringsが組み込みで存在していたなら、元の開発者もこうした最適化を容易に適用できただろうという推測。結局、この問題はCのようにコンテナが貧弱な言語の構造的な限界に由来するという意見

  • 関連コミット（アルゴリズム改善内容）へのリンクを直接共有。関連コミットリンク

    • おかげで関連サブミッションとカーネルメーリングリストの議論スレッドを見つけられたという情報共有。関連議論リンク