TopicBase
Cloudflareは、社内のグローバルな制御基盤を管理する実験的な分散合意サービス「Meerkat」に、2023年に公表された合意アルゴリズム「QuePaxa」を採用しました。大陸をまたぐ通信では遅延や接続状況が変わりやすいため、単一のリーダーの停止や遅延に処理全体が左右されにくい方式を選んでいます。
大陸をまたぐ運用で課題になるリーダーへの依存
分散合意は、複数のコンピューターが、一部の停止や切断があっても共通の値を決めるための仕組みです。Meerkatでは、同じデータを保持する複製先である「レプリカ」が、イベントの順序を記録するログについて合意します。異なるレプリカが矛盾した値を確定しないことで、ログの内容が分岐するのを防ぎます。
Meerkatは、このログを使って、キーと値の組でデータを扱うキーバリューストアなどを提供します。読み取りや書き込みをログに記録し、各レプリカが同じ順序で処理することで、同じデータの状態を構築する仕組みです。
RaftやMulti-Paxosなどの代表的な合意方式では、通常、一つのプロセスがリーダーとして処理を進めます。リーダーが停止したり、通信が遅くなったり、接続を失ったりすると、交代するまでシステム全体が遅延または停止することがあります。Meerkatのクラスタは大陸をまたいで配置される場合があり、大きく変動しやすい通信遅延への対応が採用上の課題になりました。
待ち時間を過ぎても、先行する提案を取り消さない
リーダーを交代させる方式では、応答を待つ上限時間である「タイムアウト」の設定が問題になります。長すぎれば障害後の待ち時間が増え、短すぎれば、単に通信が遅いだけでも交代が起きます。従来方式では、新しいリーダーの動作が先行するリーダーの処理を妨げ、それまでの作業が無駄になる場合があります。
QuePaxaは、通常は一つのリーダーが処理を先導しつつ、別の提案者が同じ合意の処理に加わっても、先行する処理を妨げない構成です。複数の提案者が協力して決定を早めることもでき、短い遅延をきっかけに互いの作業を取り消す必要がありません。
そのために使うのが、後続の提案者の開始を少し遅らせる「ヘッジ遅延」です。先行する提案者が順調なら後続は余分な計算や通信を控え、処理が進まなければ後続も動き始めます。合意を継続する仕組みと、重複作業を抑えるための待ち時間を分けています。
提案の優先順位をランダム化し、通常時は通信1往復で確定
QuePaxaの中核には、通信時間の上限に依存せずに合意を進める非同期の仕組みがあります。提案にランダムな優先順位を付けることで、複数の提案者がいる状況でも、高い確率で数回の通信往復のうちに値を確定できる設計です。
一方、通常のネットワーク条件では、指定されたリーダーの提案の優先順位を調整し、通信1往復で確定する高速経路を使います。研究チームは、この仕組みにより、通常時にはMulti-PaxosやRaftに匹敵する効率を実現するとしています。
リーダーの選択やヘッジ遅延も固定ではありません。QuePaxaは通信遅延を監視し、複数の選択肢を試しながら適したものを選ぶ「多腕バンディット」の考え方を用いて、動作中に調整します。現在のリーダーが停止していなくても、より速いレプリカを選択できる構成です。
EPaxosは要求間の依存関係を使って順序を決める
固定リーダーへの依存を避ける別の方式に「EPaxos」があります。EPaxosでは、要求を受け取ったレプリカがその要求のリーダーとなり、ほかの要求との依存関係を調べます。中央のリーダーがすべてを順序付ける代わりに、必要な要求の間で実行順序を定める仕組みです。
EPaxosの高速経路も通信1往復です。応答したレプリカ間で依存関係の一覧が一致すれば確定へ進み、一致しなければ、依存関係をまとめて受け入れを求める追加の通信往復を行います。例えば、別々のキーへの書き込みのように互いに影響しない処理では、両者の実行順序をそろえる必要がありません。
想定する障害はレプリカの停止
QuePaxaが対象とするのは、レプリカが停止する「クラッシュ停止」型の障害です。公開実装も、停止障害に耐える非同期の合意アルゴリズムとして構成されています。
