Cloudflare Meerkat - グローバル分散コンセンサス
Cloudflare Meerkat - Globally distributed consensus (blog.cloudflare.com)
要約
Cloudflareは、グローバルに分散されたコンセンサスサービス「Meerkat」を発表しました。これは、EPFLの研究者によって開発されたQuePaxaアルゴリズムを基盤としており、インターネットの不安定な環境下でも、多数のデータセンター間で一貫性を保ちつつ、書き込みの可用性を維持することを目指しています。従来のRaftのようなリーダーとタイムアウトに依存するアルゴリズムの限界を克服し、Cloudflareの広域ネットワークに適した設計となっています。
全文翻訳
Meerkatの紹介:グローバル合意の実験
Cloudflareの多くの内部サービスでは、世界中にある330以上のデータセンター全体で、同じコントロールプレーン状態を読み取り、変更する必要があります。これらのサービスは、異なるリーダーが決して一貫性のない状態を見ないという保証と、一部のデータセンターやリンクが失敗した場合でも書き込みが可能なシステムであり続けることを必要とします。
しかし、Cloudflareのネットワークはインターネット全体にまたがっており、インターネットは予測不能な場所です。サーバーやデータセンターはダウンします。キューは満杯になります。リンクやケーブルは切断されます。これらの条件は、分散システムレプリカがお互いにデータを確実に同期する能力を妨げるため、強力な一貫性(例:すべてのリーダーがすべての先行書き込みを読み取ることが保証されること)を保証するグローバルに利用可能なデータシステムを実行することを困難にします。
ネットワークの悪条件下でも安全にデータを同期する1つの方法は、合意アルゴリズムを経由することです。これは、多数のマシンが生存し、通信可能である限り、キー・バリュー・ストアのPUTおよびGET操作のような同じ値のシーケンスに合意することを可能にします。
残念ながら、Raftのような一般的に展開されている合意アルゴリズムは、Cloudflareのような広域ネットワークでは苦戦します。なぜなら、それらはリーダーとタイムアウトに依存しているからです。リーダーは書き込みを許可される唯一のレプリカであり、クラッシュやネットワーク劣化によりリーダーが失敗した場合、他のレプリカがタイムアウトして新しいリーダーが選出されるまでシステムは利用できなくなります。そして、これらのタイムアウト値は、予測不能な遅延を持つネットワークでは設定が困難です。
私たちは、合意駆動型システムでリーダーが利用できなくなったことによる複数のインシデントを経験してきました。
そこで、過去1年間、Cloudflareの研究チームは、2023年にTennage & Băsescuらによって公開されたQuePaxaと呼ばれる合意アルゴリズムを搭載した、Meerkatという新しい分散合意サービスを構築してきました。QuePaxaはRaftとは異なり、すべてのレプリカが常に書き込みを実行でき、タイムアウトによって進行が停止することはないため、Cloudflareのネットワークに適しています。私たちは、トランザクションキー・バリュー・ストアやリーシングシステムのようなアプリケーションをMeerkatの合意ログの上にレイヤー化します。我々の知る限り、これはQuePaxaのグローバルスケールでの最初の産業展開となります。
Meeerkkatはまだ開発中の実験的な合意サービスです。当初は少量のコントロールプレーン状態(例:レプリケートされたデータベースのリーダーシップ)を管理するために設計されており、当面は内部専用となります。この記事ではMeerkatを紹介し、今後のMeerkat関連のブログ記事の基礎を築きます。
グローバルコントロールプレーンデータシステムに求められるもの
Cloudflareの多くのサービスは、世界中に分散した複数のマシンから、サービスが正しく動作するのを助けるデータであるコントロールプレーンデータを読み書きします。コントロールプレーンデータの1つの例は配置情報です。これは、特定の(AIモデルインスタンスのような)リソースがどこに格納されているかを示します。もう1つの例はリーダーシップ情報です。これは、現在データベースへの書き込みを実行することが許可されているマシンを示します。
コントロールプレーンデータは、強く 一貫性があり、特定の種類の障害にもかかわらずアクセス可能である必要があります。
このセクションでは、Cloudflareの合意サービスに対する一貫性と耐障害性の要件を正確に記述します。ここでは、キー・バリュー・ストアを、私たちの合意サービスの上に実行されるアプリケーションの実行例として使用しますが、他のアプリケーション(例:分散リース/ロック)も可能です。
強力な一貫性
分散データシステムの一貫性レベルは、同時読み書きを受けた場合にシステムがどのような奇妙な動作を許容するかを記述します。複数のノードに単一の数値 x = 6 を格納する分散キー・バリュー・ストアを考えます。また、以下の書き込みシーケンスを考えます。これらの書き込みは、ベストエフォートで異なるノードに送信され、任意の順序で到着する可能性があります。
x = x + 1x = x / 2
システムの整合性レベルは、これらの書き込みの後でクライアントが x を読み取ったときにどのような値を見ることができるかを示します。異なる整合性レベルでのさまざまな操作シーケンスと可能な実行順序を考えます。
[画像: 整合性レベルの例を示す図]
弱い整合性レベルでは、書き込みの順序が入れ替わることがあります。より強い整合性モデルでは、書き込みの順序は入れ替わりませんが、読み取りの順序は入れ替わることがあります。可能な限り最も強い整合性レベルでは、操作は実際に行われた時間順に正確に並べられます。このプロパティは線形化可能性と呼ばれます。
Cloudflareでは、多くのサービスが線形化可能性を求めています。線形化可能性は、弱い形式の一貫性とは異なり、プログラマーにデータシステムが示す可能性のあるすべての奇妙な動作について考えることから解放します。代わりに、単一スレッドマシン上のローカルメモリについて考えるのと同じように、分散システムについて推論できます。つまり、書き込み後のすべての読み取りはその書き込みを反映します。弱い整合性の危険性に関する追加の資料については、Marc Brookerによるこの投稿を参照してください。
(疑問に思っているかもしれませんが、Meerkatのキー・バリュー・ストアは直列化可能性も提供します。これについては将来の投稿で説明します。)
耐障害性
システムの耐障害性レベルは、システムがどのような障害を処理できるかを、破局的な事態が発生する前に記述します。破局的な事態とは、通常、システムが維持しようとするプロパティ(例:同じキーに対する介入的な書き込みなしの連続した2回の読み取りが異なる値を見ることはない、またはシステムが書き込みのために利用可能であり続けること)の違反です。障害には、ネットワーク障害や遅延、マシンのクラッシュ、マシンの再起動が含まれます。システムは通常、一部の障害を明示的に処理しますが、すべてを処理するわけではありません(宇宙が熱的死に達する可能性もあるため、すべての障害を処理することはできません)。たとえば、一部のキー・バリュー・ストアは、システム内の3分の2のマシンが通信可能でクラッシュしていない限り、書き込みのために利用可能であり続けることを保証するかもしれませんが、マシンが侵害されて悪意のあるメッセージを送信し始めた場合は保証しません。
私たちが望む耐障害性のプロパティは以下の通りです。
第一に、以下の条件が満たされている限り、データシステムは、私たちのデータセンターのいずれかにいるクライアントからの書き込みおよび読み取りに対して利用可能であり続ける必要があります。
- システム内のマシンの過半数が生存しており、互いに通信できること。(形式的には、
2f + 1マシンシステムでfの障害を許容します)。 - クライアントは、過半数の生存マシンに接続されているシステム内のいずれかのマシンに連絡できること。
これは、単一のマシン障害や単一リンクのネットワーク劣化がシステム可用性に影響しないことを意味します。このプロパティは、後述するようにRaftベースのシステムでは提供されません。
第二に、システムは、システム内のどの主体も積極的に悪意がない限り(そして、もちろんバグがない限り)、正確であり続けます。ここでは正確性を合意の安全性の観点から定義しますが、緩やかに言えば、これは最新の状態にある2台のマシンが世界について決して意見が一致しない(例:一方が key1=1 と思い、もう一方が key1=2 と思う)ことを意味します。
要約すると、マシンがクラッシュしたり、再起動したり、ネットワークが障害を起こしたり劣化したり、データセンターがダウンしたりしても、システムは正確であり続ける必要があります(ただし、Raftベースのシステムと同様に、私たちはビザンチン障害は処理しません)。
Meerkatの紹介
Meeerkkatは、キー・バリュー(KV)ストアのような、上記のプロパティ(強力な一貫性と耐障害性)を示すアプリケーションを構築できる基盤となる合意サービスです。Meerkatがどのように機能するかを理解するために、まずMeerkatの一般的なアーキテクチャを概説し、次にMeerkatの合意アルゴリズムの選択が一貫性と耐障害性を提供する方法を説明します。
Meeerkkatを使用するサービスの開発者は、Meerkatレプリカのクラスタを要求します。各レプリカは他のすべてのレプリカに接続されています。各レプリカは合意アルゴリズムに参加し、読み取りと書き込みの両方を受け取ることができます。開発者は、どのデータセンターがレプリカをホストできるかを指定でき、Meerkatがそれらを自動的に配置します。
クラスタと対話するために、開発者のクライアントは、クラスタ内の任意のレプリカにアプリケーション固有のリクエストを送信します。単一のレプリカは多くの種類のアプリケーションをホストできますが、最も単純なものはキー・バリュー・ストアです。そのため、最も単純なアプリケーション固有のリクエストタイプはKVのGETまたはPUTです。レプリカは、アプリケーション固有の応答(例:GETで要求されたレコード)でリクエストに応答します。KV読み取り(GET)は、最新の情報を読み取ることが保証されていることに注意してください。
[画像: Meerkatのアーキテクチャ図]
Meerkatのログ
内部的には、レプリカはアプリケーションリクエスト(例:GETおよびPUT)をログイベントに変換します。そのレプリカは、すべてのレプリカがまったく同じイベントログを維持するように(実際には、レプリカは遅延する可能性がありますが、異なるエントリを記録することはありません)、合意アルゴリズムを使用して各ログイベントを他のすべてのレプリカに配布します。これらのイベントは任意です。Meerkatのコアは、それらに何が含まれているかを気にしません。Meerkatアプリケーションは、ログイベントの内容を気にします。各Meerkatレプリカは、ログイベントを読み取り状態を構築する多数のMeerkatアプリケーション(例:キー・バリュー・ストア)を「ホスト」します。(各レプリカは正確に1つのクラスタに属することに注意してください。)
たとえば、KV Meerkatアプリケーションは、ログイベントからインメモリのキー・バリュー・ストアを構築します。したがって、クライアントが put k1 v1 のような書き込みを送信すると、受信したレプリカはその書き込みをログイベントに配置し、すべてのレプリカに配布します。その後、別の誰かが別のレプリカに put k1 v11 を書き込んだ場合、このイベントもすべてのレプリカに配布されます。機能しているすべてのレプリカは同じログを持つため、それらのレプリカはログ内の操作をシーケンスで適用して、まったく同じ状態を構築できます。GETリクエストも分散ログイベントを作成することに注意してください(次のセクションで説明する線形化可能性のため)。
レプリカのKVストアがログイベントを受信するにつれてどのように更新されるかの例を次に示します。
[画像: KVストアの更新例を示す図]
Meerkatのログが強力な一貫性を実現する方法
Meeerkkatは、あるクライアントが put k1 v1 を実行し、次に別のクライアントが put k1 v11 を実行し、さらに別のクライアントが get k1 (一貫性のある読み取りで)を実行した場合、常に v11 を読み取ることを保証します。これは、各リクエストが異なるレプリカに送信され、それらのレプリカが世界中にランダムに分散されている場合でも保証されます。これが線形化可能性です。Meerkatがこれを保証する方法を見るには、Meerkatのログを詳細に調べる必要があります。
Meeerkkatログはイベントのシーケンスです。スロットは、イベントを含むことも含まないこともできるボックスです。イベントを含むスロットは決定済みスロットと呼ばれます。ログ内のすべてのスロットは決定済みですが、現在決定中である最後のスロットは除きます。Meerkatの不変条件の1つは、2つのレプリカがスロットの値について決定した場合、それらの値は同じであるということです。言い換えれば、2つのレプリカが決定済みスロットの値について意見が一致することはありません(ただし、一方のレプリカは最後のスロットが空であると考えているかもしれませんが、もう一方はそうではないかもしれません)。このプロパティは、前のセクションで説明した望ましいプロパティを保証するのに役立ちます。
ログの最後の(空の)スロットの値について決定するために、Meerkatレプリカは分散合意アルゴリズムを実行します。合意アルゴリズムは、ネットワークを介して通信するマシンのセットが決定済みスロット値に合意することを可能にします。私たちの合意アルゴリズムは、過半数(半数より多い)のレプリカが生存している限り機能します。
したがって、ログに2つのエントリが含まれており、クライアントがレプリカに put k1 v11 を送信した場合、そのレプリカはスロット3の合意アルゴリズムをトリガーします。しかし、別のクライアントがスロット3に対して別のレプリカに put k1 v111 を送信した可能性があります。合意アルゴリズムは、スロット3に対するそのような提案のうち、1つだけが勝つことを保証します。具体的には、少なくとも過半数のレプリカが同じ提案に合意し、スロット3の決定済みとすることを保証します。過半数未満のレプリカは決して異なる提案を決定することはできませんが、スロット3が決定済みであるという事実を見逃す可能性があります。
[画像: 合意アルゴリズムの例を示す図]
これがキー・バリュー・ストアの線形化可能性をどのように提供するかを見るために、書き込みとその後の読み取りを考えます。レプリカZが put k1 v11 を提案し、この提案が過半数のレプリカによってスロット3で決定されましたが、レプリカYでは決定されませんでした。その後、リーダーがレプリカYで get k1 を実行します。レプリカYはスロット3が空であると考えているため、スロット3で get k1 を提案します。決定的なことに、過半数のレプリカは、そのスロットが既に決定されているため、そのスロットにそのイベントを配置することに同意しません。それらはレプリカYに、スロット3で put k1 v11 を決定するように強制し、スロット4で get k1 を提案するように強制します。これにより、ログ内の書き込みの後に読み取りが線形化されます。(そして、そのレプリカが過半数と連絡できない場合、読み取りを完了できません。)
Meerkatの合意アルゴリズムがRaftよりも高い可用性を提供する仕組み
ログエントリの決定には分散合意アルゴリズムが必要です。しかし、どれでしょうか?すべての有効な合意アルゴリズムは、要求された一貫性と正確性の保証を提供しますが、すべてが同じ可用性の保証を提供するわけではありません。
特に、権威あるリーダーに依存する多くのアルゴリズムは、単一のマシンに問題が発生した場合に利用できなくなる可能性があるため、望ましい可用性の保証を提供しません。最もよく知られており、おそらく最も実装されている合意アルゴリズムであるRaftを考えてみましょう。Raftは権威あるリーダーに依存しています。これは、クラスタ内で合意を推進できる唯一のレプリカです。その結果、すべての書き込みはリーダーに転送されます。この設計上の選択は、Raftを「理解しやすく」するのに役立ち、リースと組み合わせることで、リーダーが処理する読み取りを自動的に線形化できます(最新であることが保証されているため)。しかし、それは一時的な単一障害点も追加します。
一般的に、権威あるリーダーには2つの問題があります。第一に、リーダーがダウンした場合、新しいリーダーが選出されるまでシステムは利用できなくなります(すべての書き込みがブロックされます)。これはMeerkatにとって許容できません。第二に、リーダーが稼働し続けても、過負荷であったりネットワーク遅延があったりするために遅くなる場合、パフォーマンスが低下します。リーダーは、書き込みを実行する代替手段がないため、ボトルネックとなります。
最初の問題は広域ネットワークでは悪化します。リーダーがダウンした場合、ほとんどのアルゴリズムはタイムアウトを使用して新しいリーダーを選択します。非リーダーレプリカが一定時間リーダーから何も聞いていない場合、自身をリーダーとして提案します。その時点で、古いリーダーは失職し、新しいリーダーが選出されるまでシステムは書き込みを受け付けることができません。問題は、タイムアウトが元のリーダーとそのレプリカ間のネットワーク遅延よりも短い場合、レプリカは常にタイムアウトし、書き込みをブロックすることです。そして、タイムアウトが長すぎると、システムは失敗したリーダーにゆっくりと反応し、その間に書き込みもブロックされます。さらに、複数のレプリカが同時に自身をリーダーとして提案した場合、それらの「キャンペーン」はお互いに干渉し、常に自身をリーダーとして再提案させる可能性があります。その間ずっと書き込みはブロックされます。CloudflareのRaftを使用するシステムでは、広域ネットワークの遅延が大きく変動する可能性があるため、これらの正確な問題を目にしており、タイムアウトの調整は特に困難です。
Meeerkkatには、Raftのようなプロトコルによって課される「タイムアウトの専制」を回避することを目指す、QuePaxaと呼ばれる別の合意アルゴリズムを選択しました。QuePaxaは微妙なプロトコルですが、ハイライトは以下の通りです。クライアントは任意のレプリカに連絡でき、そのレプリカは最新のスロットの合意を推進できます。リーダーは存在しますが、必須ではありません。その唯一の利点は、他のレプリカ(3回以上)よりも少ない往復(1回)で合意を推進できることです。決定的なことに、クライアントは同じ提案に対して同時に複数のレプリカに連絡して、提案が成功する可能性を高めることができます。同時提案は破壊的に干渉しません。レプリカは、提案された値の1つを決定するために協力します。
要するに、QuePaxaは私たちの目的のためにRaftよりも3つの利点があります。
- 必須のリーダーが存在しないため、単一レプリカ(リーダー)がダウン、利用不可、または劣化した場合でも、システムが利用できなくなったり劣化したりすることは決してありません。クライアントは、世界中のどこかの健全なレプリカに連絡できる限り、書き込みを実行できます。
- リーダーが存在しないため、システムを劣化させるリーダー選出はありません。そして、異なるレプリカによって行われた同時提案は、Raftのリーダー選出とは異なり、建設的に干渉します。これは、遅延が大きく変動する可能性のあるCloudflareのネットワークに理想的です。
- QuePaxaは、信頼性の低いネットワーク環境(「非同期」)と、仮想的な敵対者がレプリカ接続に標的攻撃を仕掛けることができるネットワークのために設計されました。著者らは、そのような条件下でRaftやMulti-Paxosよりもはるかに高い(約10倍の)スループットを維持することを発見しました。これらの条件は、他のアルゴリズムが想定する条件よりも、私たちのネットワークにより正確に類似しています。
QuePaxaの完全な説明は別の投稿に譲ります。QuePaxa論文の著者の方々が、彼らの仕事に関するフィードバックや質問に対応してくださったことに、多大な感謝を申し上げます。
Meerkatのパフォーマンス評価
Meeerkkatには制限があります。汎用データシステム(データベースなど)を作成するために設計されているわけではありません。
すべての合意アルゴリズムにはコストが伴います。それは大量の往復です。特にQuePaxaは、提案を決定しログにイベントを追加するために、初期提案者と過半数のレプリカの間で1〜3回の往復(通常は、それ以上かかることもありますが)を必要とします。リーダーとの違いは、リーダーが提案する場合(決定をレプリカに通知するための追加のブロードキャストを伴う)は1回、非リーダーが提案する場合(追加のブロードキャストを伴う)は3回です。複数のレプリカが同時に提案を行う場合、さらに時間がかかることがあります。これらの通信コストは、合意アルゴリズムの一般的な重要なパフォーマンス制限を示しています。提案決定の遅延は、過半数のレプリカ間の遅延に比例します。したがって、レプリカが互いに遠く離れている場合、遅延は増加します。これは避けられません。
一見すると、Meerkatの書き込みおよび読み取りの遅延はかなり悪いように思えます。特に、すべての書き込みと読み取り(一貫性のために)がログを通過する必要があり、それゆえ多くの往復を必要とする場合。
しかし、Meerkatからより良いパフォーマンスを引き出す方法はいくつかあります。
- 開発者はレプリカの配置場所を制御できるため、レプリカを互いに近づけることで往復遅延を減らすことができます(真にグローバルな分散を必要としないサービスにのみ適用可能)。
- 書き込みはバッチ処理できます。したがって、レプリカが10ミリ秒の間に10件の書き込みを受け取った場合、それらをすべて1つの提案にまとめることができ、スループットが向上します。
- すべての読み取りが合意ラウンドをトリガーする必要はありません。開発者が古い(ただし、一貫性のないことはない)データを読み取ることに同意する場合、任意のレプリカのローカルデータから読み取ることができます。
- 複数の操作を単一の合意ラウンドにバンドルできます。たとえば、私たちのキー・バリュー・ストアは、値が読み取られてから変更されていない場合にのみ書き込みが実行される、比較交換スタイルの書き込みをサポートしています。(実際、一般的なトランザクションをサポートしています。)
それでも、Meerkatの基本的な遅延の制限は残ります。特に、設計通りにグローバルスケールで実行される場合です。これらの制限により、短期的には、頻繁には書き込まれないが、一貫性を保つ必要があるコントロールプレーン情報に最適です。
次のステップ
Meeerkkatは本番環境にデプロイされていませんが、世界中に分散した最大50レプリカでの複数の概念実証(Proof-of-Concept)を成功裏に実行しました。概念実証クラスタではリーダーが頻繁に失敗しますが、クラスタはエラー率の増加なしに動作し続けます。
Meeerkkatについては、さらに多くのことをお伝えできます。今後1年間で、QuePaxaが実際にどのように機能するか、Rust実装の一部をどのように形式検証しているか、ブートストラップとクラスタ管理がどのように機能するか、最適なレプリカ配置をどのように見つけるか、決定論的シミュレーションテストを使用してバグをどのように発見するかなど、Meerkatに関する投稿を作成します。査読のための原稿も準備します!
Meeerkkatの進捗をCloudflare Blogでフォローし、Cloudflare Researchで他のプロジェクトもチェックしてください。