HN 日本語サマリー

← 一覧へ戻る
プログラミング

あらゆる規模でのGit

Git at any scale (cursor.com)

325 pointsby meetpateltech102 コメント

要約

この記事は、Gitリポジトリを大規模にホスティングすることの困難さについて論じています。Gitの分散設計は、個々の開発者のワークフローには適していますが、中央集権的なホスティングには課題をもたらします。特に、Gitの基本的なストレージ形式であるpackfileは、スケーラビリティと可用性の両面でボトルネックとなります。記事では、packfileに依存しないアプローチや、GitHubが直面したファイルシステムのスケーリング問題など、過去の試みと課題について解説しています。

全文翻訳

あらゆる規模でのGit

Gitリポジトリを大規模にホストすることは悪夢です。Linus Torvaldsが最初のバージョンの「地獄からの情報マネージャー」(これはGitの実際のタグラインです。調べてみてください)を設計したとき、彼は非常に特定のユースケースを念頭に置いていました。それは彼自身のユースケースです。彼はLinuxカーネルの開発に使用されていた分散バージョン管理システムであるBitKeeperを置き換えたいと考えていました。もちろん、その代替も分散型である必要がありました。カーネルは特殊なソフトウェアプロジェクトです。非常に分散化されており、多くの異なるサブシステムに多くの異なるメンテナーがいます。分散バージョン管理システムは、このワークフローに自然に適合します。

20年後、Gitは業界標準になりましたが、真実はその分散的な性質が利点というよりもむしろ障害となっていることです。平均的なオープンソースソフトウェアプロジェクトは、分散ワークフローで運用されていません。平均的な企業も同様です。それらは分散モデルの多くの利点(オフラインでの作業、プッシュの遅延など)を利用しますが、中央集権的なホストに大きく依存しています。そして、Gitリポジトリのホスティングは、実際には信じられないほど難しいことであることが判明しました。

Gitの何が難しいのか?

Gitリポジトリを大規模にホストする際の課題は、Git自体の設計に固有のものです。分散型バージョン管理システムとは、リポジトリのすべてのインスタンスが同一であることを意味します。Gitサーバー上のリポジトリと開発者のラップトップ上のリポジトリの間には、特別な違いはありません。一見すると、これによりGitリポジトリのホスティングが簡単になるように思えるかもしれませんが(単にリポジトリのディスク上のコピーの前にHTTPデーモンを置けばGitサーバーの完成です!)、実際には多くの困難なスケーラビリティと信頼性の課題があり、これは全く逆のことを意味します。

通常のGitリポジトリでは、コードとメタデータ(ファイル、コミット、ツリー)はパックファイルに圧縮されて保存されます。これはローカルマシンでは扱いやすい単純なバイナリシリアライゼーション形式ですが、サーバー上で大規模に管理するには理想的ではありません。パックファイルは、GitストレージおよびGitネットワーキングの基本的な構成要素です。リポジトリからデータをプッシュまたはフェッチするとき、それはパックファイルとして転送されます。

これはGitが設計上どのように機能するかですが、そうする必要はないと考えるのは公平でしょう。結局のところ、あなたはGitクライアントを制御できません(少なくともユーザーを煩わせたり、多くの摩擦を加えたりすることなく)。しかし、あなた自身のサーバーの壁の中では、何でもできます。パックファイルの使用に縛られるものはありません。Linusが来てチェックすることはありません。唯一の制限は、すべてのGit操作でネットワーク経由でパックファイルを送受信する必要があるということです。

長年にわたり、Gitリポジトリを大規模にホストしようとした企業は、このパックファイルベースの設計が可用性とスケーラビリティの両方における主要な制限であることを発見しました。パックファイルは、Gitがアクセスするためにファイルシステム上に存在する必要がある大きなバイナリファイルです。ディスク上のリポジトリの前にHTTPサーバーを置くという単純なアプローチは、非常に低い天井しかありません。理想的には、リポジトリを多くのディスクと多くのマシンに存在させたいでしょう(これにより、多くのGit操作を並列実行でき、サーバーがクラッシュしてもリポジトリを利用可能に保つことができます)。しかし、どうすればそれができるでしょうか?

これを達成するには、一般的に3つのアプローチがあります。複雑さが増す順に並べると、ファイルシステムを分散させる、パックファイルを分散させる、またはGit自体を分散させる、というものです。

パックファイルなしのGit

Gitはコンテンツアドレス可能なデータストアです。Gitリポジトリ内のすべてのオブジェクト(ブロブ、ツリー、コミットなど)は、そのコンテンツのSHA-1によってキー付けされます。これは、分散キーバリューストア(キーはSHA-1、値は実際のオブジェクト)に非常にうまくマッピングされ、リポジトリのストレージをスケーリングするためのクリーンな方法を提供する可能性があります。しかし、実際にはこれはうまくいきません。

問題は、Gitリポジトリの実際のレイアウトは有向非巡回グラフ(DAG)であるということです。SHAで任意のオブジェクトを検索できますが、リポジトリで最も些細な操作を実行するためでさえ、DAGをステップバイステップで歩く必要があります。

graph TD
    COMMIT[
        COMMIT DAG
    ]
    TREE[
        TREE /main
    ]
    subgraph "c8f3?commit · c8f3"
        direction LR
        NETWORK[
            NETWORK
        ]
        OLDER_COMMITS[
            OLDER COMMITS
        ]
        objects[
            objects 0/54
        ]
        round_trips[
            round-trips 0
        ]
    end
    key_value_store[
        key/value store
    ]

    COMMIT --> TREE
    TREE --> NETWORK
    NETWORK --> OLDER_COMMITS
    NETWORK --> objects
    NETWORK --> round_trips
    objects --> key_value_store

リポジトリの最近の変更をリストするなどの操作を行いたい場合、コミットを処理する必要があります。コミットを処理すると、そのツリーのルートへのポインタが得られます。そのツリーから、各ファイルと各サブツリーへのポインタが得られます。元のコミットから、その親(履歴の中でその前に来るもの)へのポインタが得られます。重要なのは、このウォークの各ステップで、前のポインタを取得するまで次のポインタの値がわからないことです。各フェッチで分散ストアへのラウンドトリップが必要な場合、物事は非常に速く非常に高価になります。

オブジェクトレベルでGitを分散させるこのアプローチは、以前にも何度も試みられてきましたが、多くの場合、大規模では失敗します。最も有望な実装は、私の元メンターであるShawn PearceがGoogleのバージョン管理システムチームで働いていたときに試みたものです。彼の方法は分散ハッシュテーブルにオブジェクトを保存することでした。これは、Javaで書かれたカスタムGit実装であるJGitのおかげで可能になりました。あらゆる優れたJavaライブラリと同様に、JGitは通常のGitリポジトリのすべての詳細を抽象化するための十分なインターフェイスとファクトリを提供しており、オンディスクのパックファイルをDHTに置き換えることも含まれます。システムは機能し、通常のGit操作に対しては十分な結果が得られましたが、Gitプロトコルの制限(サーバー上のデータの保存方法に関係なく、ネットワーク経由でパックファイルを送信する必要があること)により、git cloneのパフォーマンスが悪すぎて設計を完全に破棄することになりました。

GitHubとファイルシステム

GitがLinuxカーネルのバブルを脱してから数年後、サンフランシスコで新興企業が誕生しました。GitHubは2008年に、非常に先見の明のあるタグライン「Gitリポジトリホスティング:もう面倒なことはありません」とともに、ソーシャルコーディングプラットフォームとして設立されました。これも冗談ではありません。調べてみてください。2008年当時、Gitの分散設計にもかかわらず(あるいはそれゆえに)、ユーザーフレンドリーにするためにはGitリポジトリをホストする中央集権的な方法が必要であり、それを行うことは非常に困難であるという広範なコンセンサスがありました。GitHubはその変更に乗り出しました。

そのプラットフォームは、Railsモノリスとして(そしてほとんどの場合今も)始まりました。最初のバージョンは、単一の、しかし強力なマシンで、Rubyサーバーとそれに隣接するリポジトリのコピーを実行していました。Railsアプリのスケーリングは簡単です。インスタンスをさらにデプロイするだけです。しかし、この特定のケースでは、Gitが関与しているため、彼らはすぐにここで解決しようとしている繰り返しの問題に直面しました。Railsアプリがディスク上のGitリポジトリにアクセスする必要がある場合、それらのコピーをさらにデプロイするにはどうすればよいでしょうか?

倹約家の寄せ集めであった初期のGitHubのシステムエンジニアは、スケーリングの問題を解決できる可能性のある最も単純なアプローチを試しました。彼らの考えは、ファイルシステムを分散させることに焦点を当てる(パックファイルやGit自体ではなく)ことで、Railsアプリを変更せずに済み、奇妙なことをする時間ではなく、増え続けるユーザーベースのためにさらに多くの機能をリリースすることに時間を費やすことができるということでした。非常に実用的でした。しかし、うまくいきませんでした。

チームはGitデータ用の分散ファイルシステムについて多くのアプローチを試しました。最も明白なアプローチである、すべてのリポジトリを中央集権的なサーバーに保存するためにNFSを使用するという方法は、すぐに破棄されました。Gitのデフォルト実装は、ファイルシステムのセマンティクス(ロック、ティア、読み取り、同期など)について多くの仮定をしており、遅い開発者のラップトップのローカルファイルシステムで良好なパフォーマンスを保証しますが、ネットワークファイルシステムでの動作には全く配慮していません。それは遅く、バグがありました。

(率直に言って、後から考えると恐ろしい)ブロックレベルでファイルシステムをレプリケートするテクノロジーで、さらなる試みが行われました。GFS(GFS2)を使用した短命のデプロイメント。DRBD(DRBD)に基づいた長命のデプロイメント。すべてが壁にぶつかりました。それらは日常的に運用するのがひどく困難であり、良好なパフォーマンスでそれを補うことはありませんでした。すべては、ディスク上のパックファイルの設計に帰着します。

Gitのグラフのようなデータ構造がラウンドトリップを法外に高価にする理由をすでに見てきました。残念ながら、ディスク上の基盤となるデータにも非常に似た原則が適用されます。DAG内のオブジェクトのレイアウトと、パックファイル内の配置方法との間には相関関係がありません。パックファイルを生成する際に使用される主要なヒューリスティックは、サイズを最小化することです。オブジェクトはパック内にランダムに配置され、圧縮され、そして決定的に、ほとんどの場合全体として保存されません。ほとんどのオブジェクトは、同じパックファイル内の別のオブジェクトに対するデルタとして保存されます。グラフデータ構造内の多くの論理的なホップをたどった後、個々のオブジェクトを読み取ることは、ディスク上の形式での物理的なホップをたどることも含みます。

graph TD
    COMMIT[
        COMMIT DAG
    ]
    subgraph "c8f3"
        direction LR
        TREE[
            TREE /HEAD·merge
        ]
        commit[
            commit · c8f3
        ]
        root[
            root /tree · f021
        ]
        server_ts[
            server.ts
        ]
        pack_ts[
            pack.ts
        ]
        readme[
            README.m
        ]
        cargo[
            Cargo.toml
        ]
        main[
            main
        ]
    end
    subgraph "9d2a"
        direction LR
        feature_commit[
            feature
        ]
        feature_root[
            root /tree · e8c4
        ]
        server_ts2[
            server.ts
        ]
        pack_ts2[
            pack.ts
        ]
        readme2[
            README.m
        ]
        cargo2[
            Cargo.toml
        ]
        feature_main[
            main~1
        ]
    end
    subgraph "74b1"
        direction LR
        refactor_commit[
            refactor
        ]
        refactor_root[
            root /tree · 7a19
        ]
        server_ts3[
            server.ts
        ]
        pack_ts3[
            pack.ts
        ]
        readme3[
            README.m
        ]
        cargo3[
            Cargo.toml
        ]
        refactor_main[
            main
        ]
    end
    subgraph "3f7d"
        direction LR
        merge_base_commit[
            merge base
        ]
        merge_base_root[
            root /tree · 5ac0
        ]
        server_ts4[
            server.ts
        ]
        pack_ts4[
            pack.ts
        ]
        readme4[
            README.m
        ]
        cargo4[
            Cargo.toml
        ]
        merge_base_main[
            main
        ]
    end
    subgraph "aa42"
        direction LR
        parser_commit[
            parser
        ]
        parser_root[
            root /tree · 2d6e
        ]
        server_ts5[
            server.ts
        ]
        pack_ts5[
            pack.ts
        ]
        readme5[
            README.m
        ]
        cargo5[
            Cargo.toml
        ]
        parser_main[
            main
        ]
    end
    subgraph "ce19"
        direction LR
        docs_commit[
            docs
        ]
        docs_root[
            root /tree · 91fe
        ]
        server_ts6[
            server.ts
        ]
        pack_ts6[
            pack.ts
        ]
        readme6[
            README.m
        ]
        cargo6[
            Cargo.toml
        ]
        docs_main[
            main
        ]
    end
    subgraph "87ab"
        direction LR
        bootstrap_commit[
            bootstrap
        ]
        bootstrap_root[
            root /tree · 40c2
        ]
        server_ts7[
            server.ts
        ]
        pack_ts7[
            pack.ts
        ]
        readme7[
            README.m
        ]
        cargo7[
            Cargo.toml
        ]
        bootstrap_main[
            main
        ]
    end
    subgraph "2ee4"
        direction LR
        initial_commit[
            initial
        ]
        initial_root[
            root /tree · b908
        ]
        server_ts8[
            server.ts
        ]
        pack_ts8[
            pack.ts
        ]
        readme8[
            README.m
        ]
        cargo8[
            Cargo.toml
        ]
        initial_main[
            main
        ]
    end
    subgraph "OLDER COMMITS"
        direction LR
        pack_file[
            pack-7d9a.pack
        ]
        pack_data[
            00005041434B00000002000000369667706B001087CB98F791BBB1A90DFB95AEA39C9096002008C2A7180F97ACF200DBBC9098D5BBD10030B5A94CB2E61004EC96B098E17C9BE5B700404A19E5C49FA44FE62B3225C446E744410050C5EB8990E84A607C5C5A3D9996324D5F0060633898968A2B4DF3066395013955B4960070A15A6898EA976BE046C3ACDE98A86F5E00803BE84A97E68450D47936985069F5B25F00902FBDE5D4C28ECFE63DB350B871E7F33A00A0BAF109D0E8F7FF556E74DAB7E6E2E71E00B058DD984BFA29344429F2E52F415382E600C0C71AD04782E703FECCE51940E862FA0600D004826A0596C94054F246984BD218C3AC00E04B2C9506ED4A02967A5071F17D9793A000F01B73670B98B79D58807A0B14E6DC5E5301002FEF9814BBB9A6E8617EE5D4B43D5AE601108478CF63F0E7F3D8BA541492E8E8FCF701205929E078E6629739693698F03127F80B0130295BE516B79BE8E68A9D1BCD23E744210140B1A5543CE88D7CD27941A14CE6C614EB0150F0E1982CE621266DD61CE5CECCF7DEE60160212997678DE7FD3C7B66EFF2E85F579E0170C2D51BAEE51554918799BF9B3F89732901808F7ED201FA87C2FD
        ]
    end

    COMMIT --> commit
    commit --> feature_commit
    feature_commit --> refactor_commit
    refactor_commit --> merge_base_commit
    merge_base_commit --> parser_commit
    parser_commit --> docs_commit
    docs_commit --> bootstrap_commit
    bootstrap_commit --> initial_commit

    commit --> root
    feature_commit --> feature_root
    refactor_commit --> refactor_root
    merge_base_commit --> merge_base_root
    parser_commit --> parser_root
    docs_commit --> docs_root
    bootstrap_commit --> bootstrap_root
    initial_commit --> initial_root

    root --> server_ts
    feature_root --> server_ts2
    refactor_root --> server_ts3
    merge_base_root --> server_ts4
    parser_root --> server_ts5
    docs_root --> server_ts6
    bootstrap_root --> server_ts7
    initial_root --> server_ts8

    server_ts --> pack_ts
    server_ts2 --> pack_ts2
    server_ts3 --> pack_ts3
    server_ts4 --> pack_ts4
    server_ts5 --> pack_ts5
    server_ts6 --> pack_ts6
    server_ts7 --> pack_ts7
    server_ts8 --> pack_ts8

    pack_ts --> readme
    pack_ts2 --> readme2
    pack_ts3 --> readme3
    pack_ts4 --> readme4
    pack_ts5 --> readme5
    pack_ts6 --> readme6
    pack_ts7 --> readme7
    pack_ts8 --> readme8

    readme --> cargo
    readme2 --> cargo2
    readme3 --> cargo3
    readme4 --> cargo4
    readme5 --> cargo5
    readme6 --> cargo6
    readme7 --> cargo7
    readme8 --> cargo8

    cargo --> main
    cargo2 --> feature_main
    cargo3 --> refactor_main
    cargo4 --> merge_base_main
    cargo5 --> parser_main
    cargo6 --> docs_main
    cargo7 --> bootstrap_main
    cargo8 --> initial_main

    main --> OLDER_COMMITS
    feature_main --> OLDER_COMMITS
    refactor_main --> OLDER_COMMITS
    merge_base_main --> OLDER_COMMITS
    parser_main --> OLDER_COMMITS
    docs_main --> OLDER_COMMITS
    bootstrap_main --> OLDER_COMMITS
    initial_main --> OLDER_COMMITS

    OLDER_COMMITS --> pack_file
    pack_file --> pack_data

このグラフのようなデータ構造を何ギガバイトにもわたってランダムにウォークする必要があり、リポジトリに対して実行されるすべてのGit操作で発生するため、ネットワークファイルシステム(ファイルまたはブロックレベルでレプリケートされるかどうかにかかわらず)とはうまく連携しません。これがクロールするほど遅くならずに機能する唯一の方法は、ファイル全体をローカルにキャッシュできる場合です。しかし、同じファイルシステムに何十万ものリポジトリがある場合、キャッシュはオプションではありません。

最終的に、GitHubのシステムエンジニアは苦渋の決断を下し、ファイルシステムの分散化を断念しました。彼らは、リポジトリが専用ファイルサーバー上に存在できるようにするRPCシステムを開発し、すべての操作をリモートで行うようにRailsアプリを更新しました。これにより、水平スケーラビリティのかなりの部分が提供されましたが、可用性や最もビジーなリポジトリのパフォーマンスは改善されませんでした。結局のところ、各リポジトリは依然として単一のマシンにのみ保存されていました。

Spokesと一貫性

Spokesは元々2013年頃にGitHubで開発され、以来業界標準となっています。ほとんどのGitホスティングサービスは、そのアーキテクチャでSpokesのアプローチ(Gitリポジトリのアプリケーションレベルレプリケーション)のバリアントを使用しています。Spokesが長年うまく機能してきた主な理由は、時間の経過とともに最適であることが証明された3つの基本的な選択をしたことです。

  1. Git自体を分散させない。パックファイルレベルで動作する。
  2. すべてのデータをローカルNVMeディスク上の実際のGitリポジトリとして保存する。
  3. Gitデータをレプリケートするが、すべてのコピーを一貫して同期させ続ける。

前述のパックファイル全体にわたるランダムな読み取りパターンにより、基本的なGit操作を高速に保つためには、プレーンなGitリポジトリをNVMeドライブに保存することが基本的に必要です。また、データをGitクライアントが期待するものに変換する必要がないため、クローンも効率的になります。また、Gitのフォークを自分で維持するのではなく、Gitの上に製品を構築することに集中することもできます。

データのすべてのコピーを一貫して同期させ続けることも、極めて重要です。これは苦労して学ぶことですが、Gitクライアントは最終的な一貫性とあまりうまく連携しません。ローカルのGitクライアントがコミットをプッシュし、その直後にフェッチしたときにそれを読み取れなかった場合、それは悪いニュースです。Gitはそれを非常に混乱させます。100台のランナーでCIパイプラインを実行していて、そのうち3台がリポジトリをクローンした後にテストすべきコミットを見つけられない場合、それは悪いニュースです。それはまた、非常に悪いユーザーエクスペリエンスでもあります。

Gitリポジトリの最終的に一貫したビューを扱うことには、クライアント側でもバックエンド側でも、多くの鋭いエッジがあります。したがって、Spokesはシステムが常に完全に一貫していることを保証するために非常に高い複雑性のコストを支払います。これが具体的に何を意味するか見てみましょう。

Spokesはコンセンサスベースの分散システムです。これは、Gitリポジトリの複数のコピーを異なるサーバーに保存することで機能します。新しいデータがプッシュされるたびに、オーケストレーターがプッシュをファンアウトし、リポジトリのすべてのインスタンスがコピーを受け取るようにします。「ファンアウト」は、3PC(3相コミット)と呼ばれる古典的なコンセンサスアルゴリズムで同期され、多数のノードがそれを承認した場合にのみプッシュが受け入れられます。

graph TD
    QUORUM[
        QUORUM · 4/5
    ]
    tx[
        tx #42
    ]
    subgraph "RESTORE ALL"
        direction LR
        COORDINATOR[
            COORDINATOR
        ]
        PARTICIPANT_1[
            PARTICIPANT 1
        ]
        PARTICIPANT_2[
            PARTICIPANT 2
        ]
        PARTICIPANT_3[
            PARTICIPANT 3
        ]
        PARTICIPANT_4[
            PARTICIPANT 4
        ]
        PARTICIPANT_5[
            PARTICIPANT 5
        ]
    end
    subgraph ""
        direction LR
        VOTING[
            1 · VOTING
        ]
        PRE_COMMIT[
            2 · PRE-COMMIT
        ]
        DO_COMMIT[
            3 · DO COMMIT
        ]
    end

    QUORUM --> tx
    tx --> COORDINATOR
    COORDINATOR --> PARTICIPANT_1
    COORDINATOR --> PARTICIPANT_2
    COORDINATOR --> PARTICIPANT_3
    COORDINATOR --> PARTICIPANT_4
    COORDINATOR --> PARTICIPANT_5

    PARTICIPANT_1 --> VOTING
    PARTICIPANT_2 --> VOTING
    PARTICIPANT_3 --> VOTING
    PARTICIPANT_4 --> VOTING
    PARTICIPANT_5 --> VOTING

    VOTING --> PRE_COMMIT
    PRE_COMMIT --> DO_COMMIT

Spokesが3PCをどのように使用するかについてさらに話す前に、Gitのプッシュがどのように機能するかを理解する必要があります。Gitプッシュには2つのコンポーネントがあります。1つは、前述したパックファイルで、リポジトリにプッシュするオブジェクト(ブロブ、ツリー、コミットなど)が含まれています。もう1つは、参照トランザクションで、これは、プッシュしたコミットを指すように1つ以上の参照(作業中のブランチなど)を更新することによって、変更を実際にリポジトリに公開するものです。

この分離はここで非常に便利です。なぜなら、プッシュされたコミットは、それを指す参照が更新されるまで(Gitの用語では「到達可能」)、表示されないからです。これは、パックファイルをすべてのホストに同時にファンアウトし(ここで同期する必要はありません)、その後、パックファイルよりもはるかに小さく同期が速い参照トランザクションで3相コミットを実行することによって、プッシュのコンセンサスを実装できることを意味します。Git自体は、参照トランザクションを準備するためのサポートを持っています。参照のロックを取得し、既存の値が期待どおりであることを確認し、トランザクションのコミットまたは中止コマンドを受け取るまでロックを保持できます。

graph TD
    playback_speed[
        Playback speed
    ]
    speed_control[
        **0.010x**
    ]
    replicas[
        Replicas
    ]
    replicas_count[
        **5**
    ]
    one_way_latency[
        One-way latency
    ]
    latency_value[
        **20ms**
    ]
    elapsed[
        elapsed
    ]
    time_value[
        **0ms**
    ]
    SPOKES[
        SPOKES
    ]
    coordinator[
        coordinator
    ]
    needs_acks[
        needs 5 / 5 acks
    ]

    playback_speed --> speed_control
    replicas --> replicas_count
    one_way_latency --> latency_value
    elapsed --> time_value
    coordinator --> needs_acks

この設計により、すべてのプッシュがすべてのレプリカ間で完全に同期されることを保証します。読み取り(フェッチ、クローン)は、すべてのレプリカが常に最新であるため、いずれか1つのレプリカに安全にルーティングできます。

これがSpokesの基本的な仕組みであり、過去13年間うまく機能してきました。もちろん、Spokesは完璧ではありません。どのシステムも完璧ではありません。2026年、人々がGitリポジトリを使用する方法は劇的に変化し、分散システム構築に関して多くの重要な教訓を学びました。時間と経験は、Spokesのどの選択が最適であり、どれがそうではなかったかを示してきました。

決定的な欠点となった1つは、3PCの制約された水平スケーラビリティです。Spokesが最初にリリースされたとき、リポジトリあたりの3つのレプリカがスイートスポットでした。3つのコピーから平均的なリポジトリを提供でき、容量に余裕があり、1台のマシンがダウンしてもプッシュを受け付け続けるのに十分な冗長性がありました。

2026年、状況は大きく異なります。平均的な企業の平均的なリポジトリは、現在巨大なモノレポです。特にCIに関しては、そのようなリポジトリのトラフィックを処理するには3つのレプリカでは不十分です。もちろん、Spokesが3つ以上のレプリカで実行されるのを妨げるものはありません。恐ろしいテイルアットスケールを除けば。3相コミットはGitトランザクションモデルに非常にエレガントにマッピングされますが、コンセンサスアルゴリズムとしては根本的な制限があります。各ステップのレイテンシは、クラスター内のすべてのサーバーの中で最も遅いものに束縛されます。クラスターにレプリカを追加するほど、プッシュのスループットは悪化します。

このスケーラビリティの制約は逆方向にも適用されます。エージェントが大規模なGitリポジトリを扱うとき、それらはしばしばモノレポの外で、大量の小さなリポジトリ、その多くは使い捨てで、ほとんどがほとんど触れられていないものを作成することによって操作します。Spokesは、これらのリポジトリのそれぞれに依然として3つのレプリカが必要であるため、ここで苦労します。ほとんどアイドル状態の3つのレプリカは、システムが完全に一貫しなくなり、データ損失の可能性があるため、削減できません。3相コミットでは、フロアは常に高すぎ、天井は低すぎます。

もう1つの欠点は、最初から見えにくかったが、苦しんだ後では痛いほど明白になったことですが、Spokesは大規模で運用するのが荒いことがあります。ディスク上のリポジトリは常にコンセンサスのソースであるため、各リポジトリの各コピーは非常に重要です。リポジトリを家畜ではなくペットとして扱う必要があります。

これは、まず、各リポジトリがどこにあるかを正確に知る必要があることを意味します。これは、すべてのリポジトリをそれにレプリケートされたすべてのマシンにマッピングする非常に大きなルーティングテーブルを保持する必要がある外部データベースへの依存(および潜在的な可用性の問題)を追加します。各リポジトリはチェックサムされ、リポジトリがディスク上で有効であることを保証するために、そのチェックサムは常にそのテーブルに更新される必要があります。リポジトリに何か悪いことが発生すると(そして信じてください、悪いことは常に起こります。Gitは実際には非常に気まぐれになる可能性があります)、それを検出し、修復ジョブをスケジュールして健全な状態に戻す必要があります。そして、それを非常に速く行う必要があります!なぜなら、繰り返しになりますが、ディスク上のリポジトリがソースオブトゥルースだからです。破損したコピーは、欠落したコピーと同じくらい悪いです。3つのコピーのうち2つが破損した場合、システムはプッシュを受け入れることができなくなります。クォーラムがありません。

Continuity

Continuityは、Cursorで開発したGitストレージシステムで、非常に明確なアプローチを取っています。Spokesがうまくいったすべてのことから学び、長年経ってから問題であることがわかったことを修正することです。

Continuityはシンプルなシステムです(シンプルでないシステムは運用が容易ではありません)。その背後にあるコアプリミティブはライトアヘッドログ(WAL)であり、S3互換オブジェクトストレージに保存します。本番環境ではS3で直接実行しますが、任意のクラウドにデプロイできるように設計しました。

リポジトリがプッシュを受信すると、プッシュをS3のWALエントリとして保存します。プッシュが完全に永続化されるまで、決して確認しません。各プッシュは個別のオブジェクトとして保存されます。プッシュされたパックファイルをディスクに書き込み、同時にS3にアップロードします。ただし、WALエントリのアップロードは公開しません。プッシュは、ローカルリポジトリコピーで参照トランザクションを正常に準備し、WALエントリへのポインタをWALインデックスファイル(ストア内の独自のオブジェクト)に記録した場合にのみ表示されます。これにより、すべてのプッシュが線形化されることが強制されます。

1回のS3書き込みでプッシュを処理しようとしないのは、ビジーなリポジトリでは、S3 PUT操作のレイテンシに基づいてプッシュスループットにハードキャップがかかるためです。注意深く調整されたバッチ処理実装と、クォーラムではなく単一のローカルリポジトリと参照トランザクションを同期させるだけでよいという要件により、ディスクが許す限り速くプッシュを取り込めるシステムを実現しています。

ローカルリポジトリコピーは、もちろん、非常に高速なNVMeドライブに保存された通常のGitリポジトリです。Spokesと同じことを行っています。なぜなら、Spokesがそれを完全に正しく行ったと思うからです。これにより、Gitコミュニティの素晴らしいOSS作業(アップストリームGitクライアントとその多くのパフォーマンス最適化を含む)を再利用できます。Gitの奇妙なことを行うのではなく、新機能のリリースに集中できます。

コンセンサス

Spokesクラスターの運用を難しくしていることの1つは、各サーバー上の各リポジトリの場所を追跡することが非常に重要であることです。Continuityはこれを非常に異なって行います。各リポジトリはどこにありますか?答えは「どこでも」です。関係ありません!リポジトリをディスク上のウォームキャッシュのように扱いますが、ソースオブトゥルースは常にS3のライトアヘッドログです。システムはステートレスであり、ルーティングテーブルはありません(そして運用するリレーショナルデータベースもありません - ハッシュタグ祝福)。ホストでアクセスしたときにリポジトリがローカルディスクにない場合、WALからマテリアライズするだけです。これは非常に効率的に行うことができますが、もちろん、無駄なので常に行うわけではありません。本番環境では、リポジトリIDを期待されるノードのリストにマッピングするためにランデブーハッシュを使用します。ルーティングに必要なすべての状態は、リポジトリIDとクラスターの現在の正常なノードセットです。しかし、この状態が同期から外れた場合(たとえば、ノードが非正常になった場合)、それも全く問題ありません。次のノードでリポジトリをマテリアライズするだけです。

コンセンサスについてはどうでしょうか?選挙は?特定のリポジトリのプライマリサーバーはどれですか?それも関係ありません!状態もコンセンサスもありません。どのサーバーでもプライマリになれます。ライトアヘッドログへのすべての更新は、S3でのアトミックな比較・交換(CAS)操作で同期されるため、任意のリポジトリインスタンスがプッシュを受信しても常に安全です。ここでも、ルーティングと同様に、任意のサーバーをプライマリとして扱うことは最も効率的なことではありません(CASリトライにつながり、プッシュが遅延する可能性があります)。そのため、実際には常に同じサーバーをプライマリとして選択します。ランデブーハッシュからのランク付けリストの最初のサーバーです。しかし、コーナーケース(デプロイ、フェイルオーバー、ネットワークのちらつき)では、どのサーバーがプライマリであるかは実際には気にしません。システムは、劣化時でも常に正しく、正常時でも常に高速になるように設計されています。

レプリケーション

S3のライトアヘッドログを持つことは、スケーリングに関して多くの可能性を開きます。S3のスケーラビリティは比類のないものであり、すべてのレプリカはそこから直接キャッチアップするため、文字通り任意の数のレプリカを持つことができます。楽観的なレプリケーションを実行し、クラスター内でゴシップUDPパケットを送信します。パケットには、各レプリカがS3から直接キャッチアップするために必要なすべてのメタデータが含まれています。画面の後ろから「それは狂っている」とあなたは時空を超えてつぶやきます。「UDPは信頼性の高いトランスポートではない」。もちろんそうではありません。分散システムでは何も信頼できるものではありません!ワイヤは信頼できません、ルーティングは信頼できません、トポロジーも信頼できません。しかし、それは大丈夫です。関係ありません。各レプリカは、キャッチアップしたWALインデックスの最後のバージョンのETagを知っています。レプリカで読み取り操作を実行するときは、期待するETagで条件付きGETをS3に実行します。ボディなしの304応答(便利に、ほとんど瞬時の操作 - メタデータのみのS3操作であるため平均10ms未満)は、最新の状態であり、フェッチまたはクローンをすぐに提供できることを意味します。200応答には最新バージョンのWALインデックスが付属しており、これを使用して読み取りを提供する前にキャッチアップします。

graph TD
    S3[
        S3 · OBJECT STORE
    ]
    wal_40[
        #40.wal
    ]
    wal_41[
        #41.wal
    ]
    wal_40_b8ab[
        #40b8ab.wal
    ]
    wal_41_56e2[
        #4156e2.wal
    ]
    gitwal_pb[
        gitwal.pb
    ]
    etag_e1[
        etag e1
    ]
    subgraph "GIT CLIENT"
        direction LR
        git_push[
            git push
        ]
        git_fetch[
            git fetch
        ]
    end
    WAL[
        WAL
    ]
    subgraph "GIT · PRIMARY"
        direction LR
        receive_pack[
            receive-pack
        ]
    end
    subgraph "GIT · REPLICA"
        direction LR
        current[
            current · e1
        ]
        wal_40_b8ab_rep[
            #40b8ab.wal
        ]
        wal_41_56e2_rep[
            #4156e2.wal
        ]
        gitwal_pb_rep[
            gitwal.pb
        ]
        etag_e1_rep[
            etag e1
        ]
    end
    drop_udp[
        Drop the UDP gossip datagram
    ]

    S3 --> wal_40
    S3 --> wal_41
    S3 --> wal_40_b8ab
    S3 --> wal_41_56e2
    S3 --> gitwal_pb
    gitwal_pb --> etag_e1

    git_push --> WAL
    git_fetch --> WAL
    WAL --> receive_pack
    receive_pack --> WAL

    WAL --> current
    current --> wal_40_b8ab_rep
    current --> wal_41_56e2_rep
    current --> gitwal_pb_rep
    gitwal_pb_rep --> etag_e1_rep

    drop_udp

レプリケーションUDPデータグラムが失われたり、トポロジーが変更されたために間違ったサーバーに到着したりしても問題ありません。すべてのレプリカでのすべての読み取りは、ソースオブトゥルースであるS3に対して検証されるため、完全に一貫しています。システムは、劣化時でも常に正しく、正常時でも常に高速になるように設計されています。

このことの含意は2つあります。第一に、システムは常に一貫しているため、その上にインフラストラクチャを構築するのは簡単です。私たち(エージェント、Webインターフェイス、クライアント)は、常にリポジトリのグローバルに一貫したビューを見ています。そして、システムが両方向にスケーリングするため、各リポジトリは適切な数のレプリカを取得します。大規模なモノレポは、CIジョブからのすべての負荷を処理するために数百のレプリカにデプロイできます。エージェントによって作成された何百万もの小さなリポジトリは、それぞれ1つのレプリカで提供できます。可用性を確保するために1つ以上のレプリカは必要ありません。なぜなら、S3がソースオブトゥルースだからです。実際、アイドル状態のリポジトリはそれさえ必要としません。レプリカがしばらくトラフィックを受信しなかった場合、ディスクからガベージコレクションし、次にフェッチが来たときにWALから再度マテリアライズするだけです。

コンパクション

ライトアヘッドログには定期的なコンパクションが必要です。ログを際限なく成長させることはできません。完全なリストアはすべてのエントリを再生するため、エントリが多いほど高価になります。

偶然にも、通常のGitリポジトリも定期的なコンパクションを必要とします。GitはWALに基づいているわけではありませんが。Gitリポジトリにおけるストレージの基本単位はパックファイルであることをすでに見てきました。リモートリポジトリのコピーにプッシュするたびに、またはローカルコピーにフェッチするたびに、新しいパックファイルが作成されます。これは無限にはスケーリングしません。各パックファイルには独自のインデックスが付随しており、Gitは含まれるオブジェクトを効率的に検索できます。しかし、この検索はパックファイルあたりでのみ効率的です。特定のオブジェクトを探していて、リポジトリに100個のパックファイルがある場合、それらの各パックファイルのインデックスを開き、それらのうちの1つで見つけるまでオブジェクトを検索する必要があります。効率的な操作は、数百回または数千回実行する必要がある場合、効率的ではありません。

最新のGitはこの問題を回避するのに非常に優れています。多重パックインデックスと増分幾何学的コンパクションをサポートしています。しかし、最終的にはディスク上のGitリポジトリを再パックするという苦渋の決断を下す必要があります。歴史的に、これはSpokesのようなシステムにとって常に可用性の問題でした。なぜなら、再パックは非常にCPU負荷の高い操作であり、増分的に行われる場合でも、システム内のすべてのレプリカで実行する必要があるからです。同じリポジトリに対して2つ以上のSpokesノードでメンテナンス操作を誤ってトリガーすると、リポジトリがフェイルオーバーする可能性が非常に高くなります。

ここでは、コンパクションのコストを償却します。プライマリのみがコンパクションを実行し、コンパクションの結果はオンディスクリポジトリとWALの両方に適用されます。すべてのレプリカはWALに従うため、コンパクションイベントも従います。レプリカは再パックせず、単にS3から既にコンパクションされたパックをダウンロードするだけで、帯域幅とCPUを交換します。

graph TD
    WAL[
        WAL
    ]
    subgraph "GIT · LOCAL PACKS"
        direction LR
        geometric_compaction[
            geometric compaction
        ]
        pack_0ec8f61e8f28979dbe0e6db3[
            0ec8f61e8f28979dbe0e6db3
        ]
        compaction_frontier[
            COMPACTION FRONTIER
        ]
        packs_arrives[
            PACKS ARRIVES
        ]
    end
    S3_SOURCE[
        S3 · SOURCE OF TRUTH
    ]
    subgraph "5 packs"
        direction LR
        pack_126db3[
            #126db3.wal
        ]
        pack_40be0e[
            #40be0e.wal
        ]
        pack_970ec8[
            #970ec8.wal
        ]
        pack_98f61e[
            #98f61e.wal
        ]
        pack_998f28[
            #998f28.wal
        ]
        gitwal_pb[
            gitwal.pb
        ]
    end

    WAL --> geometric_compaction
    geometric_compaction --> pack_0ec8f61e8f28979dbe0e6db3
    pack_0ec8f61e8f28979dbe0e6db3 --> compaction_frontier
    compaction_frontier --> packs_arrives

    S3_SOURCE --> pack_126db3
    S3_SOURCE --> pack_40be0e
    S3_SOURCE --> pack_970ec8
    S3_SOURCE --> pack_98f61e
    S3_SOURCE --> pack_998f28
    S3_SOURCE --> gitwal_pb
スケール

レプリケーションとコンパクションは、Gitストレージシステムが負荷下でどの程度うまく動作するかを決定する2つの主要な要因です。前述のように、それらは本質的にリンクされています。リポジトリが1秒あたりに取り込むプッシュが多いほど、読み取りパフォーマンスは低下します。なぜなら、Git操作が効率的であり続けるためには、すべてのプッシュのパックファイルをコンパクションする必要があるからです。これらをレプリケートする場合、コンパクションはレプリケートされるか、各レプリカで個別に実行される必要があります。

ContinuityのWALファースト設計は、完全に一貫した水平スケーラビリティを提供します。任意の数のレプリカをデプロイでき、読み取り専用Git操作のスループットはそれらと線形に増加します。クラスター内のすべてのレプリカは完全に一貫しているため、Gitプロトコル(クローン、フェッチ)とOriginがリポジトリの上に実行するすべてのRPC操作(Web UIインタラクション、REST API、すべてのエージェントインターフェイスなど)をスケーリングできます。

100レプリカまでの合成ストレステストを実行し、読み取りで一貫した線形スケーリングを確認しました。プッシュスループットの低下はありませんでした。

クラスターのプッシュスループットは、S3でWALを更新できるレイテンシに依存します。S3 Standardを使用すると、コンパクションとコンパクションされたデータの他のすべてのノードへのレプリケーションを行いながら、最大120プッシュ/秒を維持できます。また、PUT操作のレイテンシがはるかに低い高性能クラスターをS3 Express One Zoneにデプロイしました。そこでは、300プッシュ/秒以上を取り込むことができ、実質的にGitがオンディスクデータをコンパクションする速度によってボトルネックになります。ディスク上のデータのレイアウトを最適化してコンパクションの影響を減らすための革新的な方法に取り組んでいます。私たちの目標は、ハードな耐久性と一貫性の保証を緩和することなく、Gitリポジトリがコードを取り込む速度を継続的に最適化することです。

WALを真実として

S3は素晴らしいテクノロジーです。S3 APIで開拓されたブロブストレージの概念全体は、大規模データストレージシステムのための非常に強力なビルディングブロックであることが判明しました。これは、Gitリポジトリのホスティングにも間違いなく当てはまります。ここで提示された設計は多くの点で新しいですが、パックファイルをブロブとして保存した最初のものではありません。Azure DevOps(Microsoft自身のGitHubに対するMicrosoft自身の競合他社)は、パックファイルをブロブストレージに保存し、その参照をリレーショナルデータベース(MS SQL Server)に保存する非常に成功したGitストレージシステムを持っています。このようなシステムには多くのトレードオフがあります。リレーショナルデータベースは、大規模な参照トランザクションでうまくスケーリングします。しかし、リレーショナルデータベースを運用する必要があります。Gitデータの整合性が他のどの考慮事項よりも重要であると強く信じています。これが、外部データベースに依存しないWALベースのシステムを設計する上で、私たちの決定を大きく左右した理由です。

本番環境のGitリポジトリでは、多くのことが起こり得ます。データの静止時の破損、再パック中のバグ、プッシュ中の競合。それはコーナーケースの大きなコレクションです。これらのほとんどはGitアップストリームで解決されています。しかし、すべてではありません。OSSで広くデプロイされているシステムでさえ、バグのないシステムはありません。私たちの整合性モデルは、リポジトリに対して発生するすべての基本的な操作を追跡していることを保証します。WALに完全に永続化されるまで、プッシュを絶対に確認しません。すべてのプッシュを線形化します。アクセスするすべてのリポジトリのすべてのビューは、常に完全に一貫しています。すべてのプッシュがWALにあるため、リポジトリが過去に取ったすべての状態を確認できます。すべてのプッシュ、およびすべての再パックについて、完全な来歴データがあります。すべてのレプリカを巻き戻したり、早送りしたりできます。参照のみを格納するデータベースであっても、すべてのオブジェクトデータを格納するデータベースであっても、参照データベースと同期する必要はありません。Gitにバグが発生した場合(そして発生しない場合ではなく)、何が起こったのかを正確に特定し、それを元に戻すことができます。そして、Gitに既に存在するバグに加えて、ディスク上の通常のGitリポジトリで、市販のツールを使用してすべてのGit操作が実行されるため、非常に少ない新しいバグしか導入しません。

Origin

誰かのソースコードをホストすることの重要性は十分に認識しています。このブログ投稿を読んで理解している誰もがそれを同様に認識していると思います。会社の開発者がGitリポジトリにプッシュまたはプルできない場合、会社は停止する可能性があります。CIシステムで5分間のダウンタイムが発生した場合の生産性コストをドルで定量化するのは困難ですが、どのような尺度であっても、それは途方もない量です。

エージェントは、ソフトウェアとの作業方法を根本的に変え、多くの点で状況を悪化させました。より多くのコード、より多くのPR、より多くのCI実行。バージョン管理はこれらすべての中核であり、おそらく一夜にして変更するのが最も難しいことです。

私たちはCursorで内部的にこれらの困難に数ヶ月間直面しており、私たち自身のためにそれらを解決し、そしておそらく顧客のためにも解決できるプラットフォームを構築するために、かなりの思考と注意を払ってきました。現在の私たちの焦点は、より高い信頼性、より高いパフォーマンス、より高いスケーラビリティへの可能な限りスムーズなオフランプを提供し、移行を可能な限り痛みのないものにすることです。

Originは実験ではありません。それは、これらの同じシステムを構築してきた数十年にわたる経験の集大成であり、関与する課題の大きさを深く理解している人々からのものです。私たちは、機能することが証明されているエンジニアリングおよび運用の哲学と、バージョン管理の状況が進化するにつれてそれを進化させ続けるという強いコミットメントを持っています。

私たちと私たちのプラットフォームに信頼を寄せていただければ幸いです。