Cloudflareは、グローバル規模での内部制御プレーン（Control Plane）の管理を目的とした実験的な分散合意サービス「Meerkat」に関するエンジニアリングの詳細を明らかにしました。このサービスは、2023年に研究者のテナージュとバセスク（Tennage & Băsescu）によって発表された最新の合意アルゴリズム「QuePaxa」を採用しています。この選択は分散システムの分野において常軌を逸したものであり、現在のインフラストラクチャの大半はRaft、Paxos、あるいはViewstamped Replicationといった確立されたアルゴリズムに依存しています。
グローバルネットワークにおける従来の合意アルゴリズムの課題
従来の合意アルゴリズムは、レイテンシ（遅延）の変動や通信の切断が発生しやすい広域ネットワーク（WAN）上で稼働させると、パフォーマンスが急激に低下するか、サービスが完全に停止するという問題に悩まされます。これらのプロトコルは主に、オペレーションの順序付けを保証し、予測可能な時間内にレスポンスを提供するリーダープロセス（Leader Process）の存在に依存しています。リーダーが高レイテンシに見舞われたり、ネットワークとの接続が失われたりすると、障害が検知されて新しいリーダーが選出されるまで、合意プロセスは完全に停止します。
従来のシステムの主な欠点は、次の2つの重要な点に集約されます。
- 破壊的干渉（Destructive Interference）： Paxosプロトコルでは、複数のノードから同時に提案が提出されると、互いの提案が打ち消し合い、システムの進行を妨げる不毛な試みのループに陥ります。Raftプロトコルはこの問題を単一のリーダーを指定することで解決していますが、一時的なネットワークの混乱時には、リーダー選出のプロセスにおいて破壊的干渉が再び発生します。
- 無力な障害検知器（Fault Detectors）： インターネットのような非同期ネットワークでは、ネットワークの低速化とノードの完全な障害を区別することは困難です。障害検知器の誤った見積もりは、不必要なリーダー選出プロセスの発動につながり、システムを準安定障害（Metastable Failure）に似た状態に陥らせ、数時間にわたって書き込みが停止します。
QuePaxaは必須のリーダーなしでどのように障害ポイントに対処するか？
QuePaxaアルゴリズムは、リーダーをオプションにする、障害検知器を完全に排除する、提案者同士の競争ではなく協力を採用するという、3つの本質的な設計上の選択によってこれらの障害を乗り越えます。このアルゴリズムは、プロポーザ（提案者）とレコーダ（記録者）の間で役割を分担することに基づいています。
このアルゴリズムは、提案にランダムな優先順位を割り当てることに依存しています。プロポーザが別の記録者からより高い優先順位を持つ提案を受け取ると、直ちにその新しい提案を採用してブロードキャストを開始します。これにより、すべてのノードが互いをブロックするのではなく、宣言された最高優先度に到達するために協力して動作するようになります。リーダーが存在する場合、それは可能な限り最高の優先順位を与えられ、ネットワークが安定している限り、1回のラウンドトリップ（Single Round-Trip）で合意を完了させることが可能になります。
技術的な仕組み：合意を達成するための4つのフェーズ
QuePaxaは、ログを承認するためにシステムが通過する4つの連続したフェーズを通じて合意ラウンドを実行します。
- フェーズ0（提出と採用）： プロポーザは自身の提案に対してランダムな優先順位を生成します。リーダーが正常に動作しており、そのメッセージが大多数のレコーダに最初に届いた場合、「ファストパス（Fast Path）」を通じて合意が即座に完了します。
- フェーズ1（伝播）： プロポーザは、多数派の交差（Majority Intersection）に基づいて、後から優先順位の高い提案が撤回されるのを防ぐために、採用された提案を大多数のレコーダに伝播します。
- フェーズ2（検査と決定）： プロポーザは前のフェーズで確認された最高優先順位についてレコーダに問い合わせ、それが採用された提案と一致していれば、正式に承認されます。
- フェーズ3（次のラウンドへの引き継ぎ）： 決定に至らなかった場合、ノードは次のラウンドの準備として利用可能な最善の提案を採用し、累積的な合意の可能性を大幅に高めます。
なぜこの技術的移行が重要なのか？
QuePaxaの採用は、大陸間の分散システムの設計方法を変える実践的なステップです。これにより、インターネットの障害時にシステムが可用性（Availability）を犠牲にしたり、完全に停止したりする必要がないことが証明されます。Cloudflareのライブ環境におけるMeerkatの稼働結果では、決定の95%以上がリーダーのファストパスによって解決されることが示されました。また、ネットワークの障害やリーダーのダウンが発生した場合でも、システムは停止せず、リクエストの処理を継続しながらスループットの低下を最大でも3分の1に抑えます。
また、このアルゴリズムはヘッジング（Hedging）技術を可能にします。クライアントは、ネットワークのレイテンシに縛られることなく、ローカルで短い待機タイムアウトを設定しながら、すべてのレプリカに提案を送信できるため、Raftにおける数秒に及ぶ長い選挙タイムアウトに起因する停止期間を排除できます。Cloudflareは現在、クラッシュからのリカバリ時のデータ安全性を確保するため、Rust言語で書かれたアルゴリズムのコードに対して厳密な形式検証（Formal Verification）に取り組んでいます。