Cloudflare Meerkat: QuePaxa によるグローバル分散合意

Cloudflare Meerkat は、リーダーベースのプロトコルに見られる「タイムアウトの暴政」を排除することで、高可用性のグローバル合意を提供します。

Cloudflare は、330 以上のグローバルデータセンターにわたる重要なコントロールプレーンの状態を管理するために設計された実験的な分散合意サービスである Meerkat を導入しました。単一の権威あるリーダーに依存する従来の合意システムとは異なり、Meerkat は QuePaxa アルゴリズムを利用しており、どのレプリカでも合意を推進することができます。このアーキテクチャにより、現在のリーダーが故障したりネットワークのレイテンシが激しく変動したりしても、システムが読み取りと書き込みに対して可用性を維持できることが保証され、Cloudflare が以前 Raft ベースのシステムで経験したサービスの中断を防ぐことができます。

グローバル コントロールプレーン データの要件

リソース配置情報やデータベースのリーダーシップ状態などのコントロールプレーン データは、広域ネットワーク (WAN) 全体で信頼性高く動作するために、強力な一貫性と高い耐故障性の組み合わせを必要とします。

線形化可能性 (強一貫性)

Meerkat は、最も強力な一貫性モデルである 線形化可能性 (linearizability) を目指しています。線形化可能なシステムでは、すべての操作は現実の時間に発生した通りに正確に順序付けられます。これにより、書き込みが行われた後に実行される読み取りは、クライアントがどのグローバルレプリカに接続しても、その書き込みを確実に確認できることが保証されます。このモデルは、プログラマーが分散状態を単一スレッドのマシンのローカルメモリのように扱えるようにすることで、開発を簡素化します。

耐故障性と正確性

Meerkat は、以下の条件下で正確性と可用性を維持するように設計されています：

• 過半数の可用性: システムは、過半数のマシン (2f+1 のシステムにおける f+1) が生存し、通信可能である限り、読み取りと書き込みに対して可用性を維持します。
• クライアント アクセス: クライアントは、生存しているマシンの過半数に接続されている任意のマシンとやり取りできます。
• 非 Byzantine 故障: システムは、いかなるアクターも積極的に悪意を持っていない限り、正確性を維持します。ただし、マシンのクラッシュ、再起動、およびネットワークの劣化は処理します。

アーキテクチャ: Meerkat ログと QuePaxa

Meerkat は、トランザクション型キーバリュー (KV) ストアやリーシングシステムなどのアプリケーションが構築される基盤として機能します。

分散ログ

Meerkat の核となる部分は、一連の「スロット」を維持することです。各スロットは、空であるか、決定されたイベントを含むかのいずれかです。

• スロットによる一貫性: 2 つのレプリカが特定のスロットに対して値を決定した場合、それらの値は同一でなければなりません。
• 読み取りの線形化: 線形化可能性を確保するため、get リクエストでさえもログイベントを作成します。レプリカが空であると信じているスロットから読み取ろうとした場合、しかし過半数がすでにそのスロットに対して値を決定している場合、そのレプリカは読み取りを完了する前に過半数と同期することを強制され、前の書き込みの後に読み取りを効果的に線形化します。

なぜ Raft ではなく QuePaxa なのか？

Cloudflare は、広域ネットワーク (WAN) 特有の可用性問題を解決するために、Raft から QuePaxa へ移行しました：

1. リーダーのボトルネックの排除: Raft では、すべての書き込みは単一のリーダーを経由する必要があります。リーダーが故障したり速度が低下したりすると、システム全体がブロックされます。QuePaxa では、どのレプリカも最新のスロットに対して合意を推進できます。
2. タイムアウト問題の回避: Raft は、新しいリーダー選挙のトリガーとしてタイムアウトに依存しています。予測不可能な WAN では、タイムアウト設定が短すぎると不必要な選挙が頻繁に発生し、タイム、アウト設定が長すぎるとダウンタイムが増加します。QuePaxa は、タイムアウトによって進行を停止させません。
3. 建設的干渉: Raft のリーダーシップ選挙キャンペーンは干渉し、書き込みをブロックすることがありますが、QuePaxa は複数のレプリカが並行して値を提案できることを可能にします。これらの提案は、破壊的な干渉ではなく、価値を決定するために協力的に働きます。

パフォーマンス トレードオフと最適化

合意形成には複数のネットワーク・ラウンドトリップが必要となるため、Meerkat は汎用的なデータベースではなく、書き込み頻度の低いコントロールプレーン データのために設計されています。

レイテンシ 制約

決定レイテンシは、過半数のレプリカ間のネットワークレイテンシに比例します。提案は、リーダーが推進する場合、通常 1 回のラウンドトリップで済み、リーダーではないレプリカが推進する場合、3 回以上のラウンドトリップが必要です。

パフォーマンス の緩和策

スループットを向上させ、知覚されるレイテンシを減少させるために、Meerkat はいくつかの戦略を採用しています：

• バッチ処理: レプリカは複数の書き込みを複数の単一の提案にグループ化できます。

• レプリカの配置: 開発者は、完全なグローバル分散を必要としないサービスのために、レプリカをより近くに配置してラウンドトリップ時間を短縮できます。

• Stale Reads (古いデータの読み取り): 強力な線形化可能性を必要としないアプリケーションの場合、読み取りは合意ラウンドをトリガーせずに、レプリカのローカルデータから提供できます。

• Bundled Operations (一括操作): KV ストアは、単一の合意ラウンド内で、一般的なトランザクションと compare-and-swap (CAS) 書き込みをサポートしています。

現在のステータス

Meerkat は現在、内部的な実験的サービスです。最大 50 個のグローバルレプリカを使用した概念実証 (PoC) の展開では、リーダーが頻繁に故障しても、クラスターがエラー率の増加なしに動作を続けることが実跡証されています。