Cloudflare、グローバル合意の実験「Meerkat」を発表

Cloudflare の多くの内部サービスは、330 以上のグローバルデータセンターにまたがる同一のコントロールプレーン状態を読み書きする必要があります。異なる読者が一貫性のない状態を決して見ないこと、および一部のデータセンターやリンクが障害を起こしてもシステムが書き込みに対して利用可能であり続けることを保証する必要があります。

しかし、Cloudflare のネットワークはインターネット全体にわたって展開されており、インターネットは予測不可能な場所です。サーバーやデータセンターがダウンします。キューがいっぱいになります。リンクやケーブルが切断されます。これらの状況は、強力な一貫性（例：すべての読者がすべての先行する書き込みを読み取ることを保証すること）を保証するグローバルに利用可能なデータシステムを運用することを困難にします。なぜなら、敵対的な環境は分散システムレプリカ間のデータの信頼できる同期能力を阻害するためです。

不利なネットワーク条件下でもデータを安全に同期させる一つの方法は、コンセンサスアルゴリズム（consensus algorithm）を利用することです。これにより、過半数のノードが生きていて通信可能である限り、キーバリューストアの put や get 操作などの同一の値シーケンスに対して一組のマシンが合意することができます。

残念ながら、Cloudflare のような広域ネットワークでは、リーダーとタイムアウトに依存する Raft などの一般的に展開されている合意形成アルゴリズムは性能が低下します。リーダーは書き込みを許可される唯一のレプリカであり、クラッシュやネットワークの劣化により失敗した場合、他のレプリカがタイムアウトして新しいリーダーが選出されるまでシステムは利用不能になります。また、予測不可能なレイテンシを持つネットワークでは、これらのタイムアウト値を設定することが困難です。

私たちは、合意形成ベースのシステムにおいて、利用不能なリーダーに起因する複数のインシデントを経験してきました。

そこで過去 1 年間、Cloudflare の研究チームは、EPFL の研究者が 2023 年に発表した QuePaxa という合意形成アルゴリズムを基盤とした新しい分散合意形成サービス「Meerkat」の開発を進めてきました。QuePaxa は Raft と異なり、すべてのレプリカが常に書き込みを実行でき、タイムアウトによって進行が停止することがないため、Cloudflare のネットワークに非常に適しています。私たちは、トランザクション型キーバリューストアやリースシステムなどのアプリケーションを、Meerkat の合意形成ログの上にレイヤーとして構築しました。私たちの知る限り、これは QuePaxa がグローバルスケールで産業利用される初の事例となります。

Meerkat は開発中の実験的な合意形成サービスです。当初は、制御プレーンの状態（例えば、レプリケートされたデータベースのリーダーシップなど）という小さな管理対象を処理するために設計されており、当面の間は社内向けに限定されます。本記事では Meerkat を紹介し、今後予定されている Meerkat 関連のブログ記事のための基盤を整えます。

グローバルな制御プレーンデータシステムに私たちが求めるもの

多くの Cloudflare サービスは、世界中の複数のマシンから分散された制御プレーンデータを参照・書き込みます。これは、これらのサービスが正しく動作するために必要なデータです。制御プレーンデータの一例として、配置情報があります：特定のリソース（AI モデルインスタンスなど）がどこに保存されているかという情報です。もう一つの例はリーダーシップ情報です：現在データベースへの書き込みを許可されているマシンがどれかという情報です。

制御プレーンデータは、特定種類の障害が発生した場合でも、強い整合性を保ちつつアクセス可能でなければなりません。

このセクションでは、Cloudflare の合意形成サービスに対する整合性とフォールトトレランスの要件を正確に記述します。ここでは、合意形成サービス上で動作するアプリケーションの具体例としてキーバリューストアを使用しますが、他のアプリケーション（例えば分散リース/ロック）も可能です。

強い整合性

分散データシステムの整合性レベルは、システムが並行して読み取りと書き込みを受け取った際に、どのような奇妙な挙動を示すことが許容されるかを記述するものです。複数のノードにわたって単一の数値 x = 6 を格納する分散キーバリューストアを想定してください。また、以下の一連の書き込み操作も考慮します。これらの書き込みはベストエフォートに基づいて異なるノードに送信され、到着順序はいかなるものでもあり得ます：

x = x + 1

x = x / 2

システムの整合性レベルは、これらの書き込み後にクライアントが値 x を読み取った際にどのような値の x が見える可能性があるかを示します。異なる整合性レベルにおける以下の操作シーケンスと可能な実行順序を考慮してください:

弱い整合性レベルでは、書き込みの順序が入れ替わることがあります。より強い整合性モデルでは、書き込みの順序は入れ替えられませんが、読み取りの順序は入れ替わる可能性があります。最も強力な整合性レベルでは、操作は現実時間通りに正確に順序付けられます。この性質は線形化可能性（linearizability）と呼ばれます。

Cloudflare では多くのサービスが線形化可能性を必要としています。弱い形式の整合性と異なり、線形化可能性はプログラマーがデータシステムが示すかもしれない奇妙な挙動すべてについて考える必要から解放します。代わりに、彼らはスレッド単一のマシン上のローカルメモリについて推論するのと同じように分散システムについて推論できます：書き込み後のすべての読み取りはその書き込みを見ることになります。弱い整合性の危険性に関する追加の読書資料については、Marc Brooker によるこの投稿をご覧ください。

（ご質問があるかもしれませんが、Meerkat のキーバリューストアは直列化可能性（serializability）も提供しており、これは今後の投稿で詳しく取り上げます。）

耐障害性

システムのフェールトレランス（耐障害性）のレベルは、システムがカストロフィ（大惨事）が発生する前にどのような種類の障害を処理できるかを記述します。カストロフィとは通常、システムが目指して維持すべきプロパティの違反であり、例えば、同じキーに対して連続する 2 回の読み取り操作の間に書き込みがない場合、異なる値が観測されないこと、またはシステムが書き込みに対して利用可能であることが挙げられます。障害には、ネットワークの障害や遅延、マシンのクラッシュ、およびマシンの再起動が含まれます。システムは通常、特定の障害のみを明示的に処理し、他の障害は処理しません（宇宙が熱的死に至る可能性もあるため、すべての障害を処理することは不可能です）。例えば、一部のキーバリューストアでは、システム内のマシンの 3 分の 2 が通信可能でクラッシュしていない限り、書き込みに対して利用可能であることを保証しますが、マシンが侵害されて悪意のあるメッセージの送信を開始した場合については何らの保証も行いません。

私たちが望むフェールトレランスのプロパティは以下の通りです。

第一に、データシステムは、以下の条件が満たされる限り、どのデータセンターに位置するクライアントからの書き込みおよび読み取りに対して利用可能でなければなりません：

システムのマシンの過半数が生きており、互いに通信できること。（形式的には、2f + 1 台のマシンからなるシステムにおいて f 個の障害を許容します）。

クライアントが、生きているマシンの過半数に接続されているシステム内の任意のマシンと連絡を取れること。

これは、単一のマシンの故障や単一のリンクにおけるネットワークの劣化が、システムの可用性に影響しないことを意味します。この特性は、後ほど見るように、Raft ベースのシステムでは提供されません。

第二に、システム内のどのアクターも積極的に悪意を持っていない限り（もちろんバグが存在しない場合）、データシステムは正しく動作し続けます。正しさについては後でコンセンサスの安全性という観点から定義しますが、大まかに言えば、これは最新の情報を保持する2台のマシンが世界について決して不一致を示さないことを意味します（例えば、1 台のマシンが key1=1 と考えている一方で、別のマシンが key1=2 と考えるようなことがない）。

要約すると、システムは、マシンのクラッシュ、マシンの再起動、ネットワークの障害や劣化、データセンターのダウンなど、あらゆる事態が発生しても正しく動作し続ける必要があります（ただし、私たちも Raft ベースのシステムと同様に、ビザンチン故障には対応していません）。

Meerkat の紹介

Meerkat は、上記の特性（強い整合性と耐障害性）を備えたアプリケーションを構築するための基盤となるコンセンサスサービスです。Meerkat がどのように動作するかを理解するために、まず Meerkat の一般的なアーキテクチャを概説し、次に Meerkat が採用するコンセンサスアルゴリズムが、強い整合性と耐障害性をどのように提供するかについて説明します。

Meerkat を利用するサービスの開発者は、Meerkat のレプリカ群を要求します。各レプリカは他のすべてのレプリカと接続されており、各レプリカはコンセンサスアルゴリズムに参加し、読み取りと書き込みの両方を受け取ることができます。開発者はどのデータセンターにレプリカをホストできるかを指定でき、Meerkat が自動的に配置します。

クラスターと対話するためには、開発者のクライアントがクラスター内の任意のレプリカに対してアプリケーション固有のリクエストを送信します。単一のレプリカは多数種類のアプリケーションをホストできますが、最も単純なものはキーバリューストアであり、したがって最も単純なアプリケーション固有リクエストタイプは KV get または put です。レプリカはアプリケーション固有のレスポンス（例：get で要求されたレコード）で応答します。KV 読み取り（gets）は常に最新の情報を読み取るよう保証されている点に注意してください。

Meerkat のログ

内部では、レプリカはアプリケーションからのリクエスト（例：get や put）をログイベントに変換します。このレプリカは、コンセンサスアルゴリズムを用いて各ログイベントを他のすべてのレプリカに配布し、すべてのレプリカが正確に同じイベントのログを維持するようにします（実際には、あるレプリカが遅れることはあり得ますが、異なるエントリを記録することは決してありません）。これらのイベントは任意のものであり、Meerkat のコア部分はその内容に関心を持ちません。Meerkat アプリケーション側がログイベントの内容に注目します。各 Meerkat レプリカは、多くの Meerkat アプリケーション（例：キーバリューストア）を「ホスト」しており、それらはログイベントを読み込んで状態を構築します（注：各レプリカはちょうど 1 つのクラスタにのみ所属します）。

例えば、KV Meerkat アプリケーションは、ログイベントからメモリ上のキーバリューストアを構築します。したがって、クライアントが put k1 v1 のような書き込みを送信すると、受信したレプリカはその書き込みをログイベントとして記録し、すべてのレプリカに配布します。その後、別のレプリカに対して誰かが put k1 v11 と書き込んだ場合、このイベントもすべてのレプリカに配布されます。機能しているすべてのレプリカが同じログを持っているため、それらのレプリカはログ内の操作を順次適用して、正確に同一の状態を構築することができます。なお、get リクエストも分散ログイベントを作成します（線形化可能性のためであり、次のセクションで説明します）。

レプリカの KV ストアがログイベントを受信する際にどのように更新されるかの例を示します：

Meerkat のログがどのように強整合性を可能にするか

Meerkat は、あるクライアントが put k1 v1 を実行し、その後別のクライアントが put k1 v11 を実行し、さらにその後に一貫性のある読み取りを行う get k1 を実行した場合、常に v11 が読み取られることを保証します。これは、各リクエストが異なるレプリカに送信され、それらのレプリカが世界中にランダムに分散されている場合でも保証されます。これを線形化可能性（linearizability）と呼びます。Meerkat がどのようにしてこの保証を実現するかを理解するためには、Meerkat のログをより詳細に検討する必要があります。

Meerkat のログはスロットの連続した列です。スロットとは、イベントを含むか含まないかの箱のようなものです。イベントを含むスロットは「決定済みスロット」と呼ばれます。ログ内のすべてのスロットは決定済みですが、現在決定が行われている最後のスロットのみが例外です。Meerkat の不変条件の一つに、任意の 2 つのレプリカが同じスロットの値について合意した場合、その値は必ず一致するというものがあります。つまり、決定済みのスロットの値について、2 つのレプリカが異なる見解を持つことは決してありません（ただし、あるレプリカが最後のスロットを空と認識している一方で、別のレプリカは空でないと考えているという状況はあり得ます）。この性質は、前節で説明した望ましい特性を保証するのに役立ちます。

ログ内の最後の（空の）スロットの値を決定するために、Meerkat のレプリカは分散合意アルゴリズムを実行します。合意アルゴリズムとは、ネットワーク上で通信する一連のマシンが、決定されたスロットの値について合意することを可能にするものです。私たちの合意アルゴリズムは、過半数（半数より多い数）のレプリカが生きている限り機能します。

したがって、現在ログに 2 つのエントリが含まれており、クライアントがあるレプリカに対して put k1 v11 を送信した場合、そのレプリカはスロット 3 に対する合意アルゴリズムを開始します。しかし、別のクライアントが異なるレプリカに対してスロット 3 のために put k1 v111 を送信している可能性もあります。合意アルゴリズムは、スロット 3 に関するそのような提案のうち、ただ一つだけが勝利することを保証します。具体的には、少なくとも過半数のレプリカが同じ提案に同意し、それをスロット 3 の決定事項とすることを保証します。過半数に満たない側は決して異なる提案を決定することはできませんが、スロット 3 がすでに決定されたという事実を見逃す可能性があります。

この仕組みが、キーバリューストアに対して線形化可能性（linearizability）をどのように提供するかを確認するために、書き込みに続く読み取りの例を考えてみましょう。あるレプリカ Z が「put k1 v11」を提案し、この提案はレプリカ Y を除く過半数のレプリカによってスロット 3 で決定されます。その後、リーダーがレプリカ Y 上で「get k1」を実行します。レプリカ Y はスロット 3 が空であると信じているため、スロット 3 に「get k1」を提案します。しかし、決定的に重要なのは、過半数のレプリカがそのイベントをスロット 3 に配置することに同意しない点です。なぜなら、そのスロットはすでに決定済みだからです。彼らは、レプリカ Y が古い決定を受け取ることでスロット 3 で「put k1 v11」を決定し、スロット 4 で「get k1」を提案するよう強制します。これにより、ログ上で読み取りが書き込みの後に線形化されます。（なお、そのレプリカが過半数と通信できない場合、読み取りを完了することはできません。）

Meerkat のコンセンサスアルゴリズムが Raft よりも高い可用性を提供する仕組み

ログエントリの決定には、分散合意形成アルゴリズム（distributed consensus algorithm）が必要です。では、どのアルゴリズムを選ぶべきでしょうか？ 有効なすべてのコンセンサスアルゴリズムは、必要な整合性と正しさの保証を提供しますが、すべてが同じ可用性の保証を提供するわけではありません。

具体的には、権威あるリーダーに依存する多くのアルゴリズムは、単一のマシンに問題が発生した際に利用できなくなる可能性があるため、私たちが求める可用性の保証を提供しません。最もよく知られ、おそらく最も実装されている合意形成アルゴリズムの一つである Raft を考えてみましょう。Raft は権威あるリーダーに依存しており、クラスター内で合意を推進できる唯一のレプリカです。その結果、すべての書き込みはリーダーに転送されます。この設計選択により Raft が「理解しやすい」ものとなり、リース（lease）と組み合わせることで、リーダーが提供する読み取り操作も自動的に線形可能（linearizable）になります（最新の状態であることが保証されるため）。しかし、これには一時的な単一障害点（single point of failure）という欠点も生じます。

一般的に、権威あるリーダーには二つの問題があります。第一に、リーダーがダウンすると、新しいリーダーが選出されるまでシステムが利用できなくなります（すべての書き込みがブロックされます）。これは Meerkat にとっては許容できません。第二に、リーダーが稼働していても、過負荷やネットワークの遅延のために速度が遅くなると、パフォーマンスが低下します。書き込みを行う代替手段がないため、リーダーがボトルネックとなります。

最初の課題は広域ネットワークにおいて悪化します。リーダーがダウンした際、多くのアルゴリズムではタイムアウトを用いて新しいリーダーを選出します：非リーダーレプリカが一定時間リーダーからの連絡を受けない場合、自らをリーダーとして提案するのです。その時点で旧リーダーは罷免され、新しいリーダーが選出されるまでシステムは書き込みを受け付けられなくなります。問題は、タイムアウト時間が元のリーダーとレプリカ間のネットワーク遅延より短い場合、レプリカが常にタイムアウトしてしまい結果として書き込みがブロックされてしまう点です。逆に、タイムアウト時間が長すぎると、システムの失敗したリーダーへの反応が遅くなり、その間も書き込みはブロックされます。さらに、複数のレプリカが同時に自らをリーダーとして提案した場合、それらの「キャンペーン」が互いに干渉し合い、結果として常に再提案を繰り返す状態になり、その間も書き込みはブロックされ続けます。Cloudflare のシステムでも Raft を使用しているため、広域ネットワークの遅延が激しく変動することがあり、タイムアウトの調整が特に困難であることから、まさにこれらの問題に直面しています。

Meerkat では、Raft などのプロトコルによって課される「タイムアウトの専制」を回避することを目指した、QuePaxa と呼ばれる異なる合意形成アルゴリズムを採用しました。QuePaxa は微妙なプロトコルですが、その要点は以下の通りです。クライアントはどのレプリカにも連絡でき、そのレプリカが最新のスロットに対する合意形成を主導できます。リーダーが存在しますが、必須ではありません。その唯一の利点は、他のレプリカ（3 回以上のラウンドトリップが必要）に比べて、より少ないラウンドトリップ数（1 回）で合意形成を主導できる点です。極めて重要なのは、クライアントが同じ提案に対して複数のレプリカに並行して連絡でき、提案が成功する確率を高められることです。並行した提案は破壊的な干渉を起こしません。レプリカたちは協力して、提案された値のいずれかを決定します。

要約すると、QuePaxa は私たちの目的において Raft に対して以下の 3 つの利点を持っています：

必須のリーダーが存在しないため、システムが単一のレプリカ（リーダー）がダウンしたり、利用不可になったり、性能が低下したりすることによって利用不能になったり、劣化したりすることは決してありません。クライアントは、世界中のどこかにある健全なレプリカに 1 つでも連絡できれば、書き込みを実行できます。

リーダーが存在しないため、システムを劣化させるリーダー選出が行われません。また、異なるレプリカによって行われる並行した提案は、Raft のリーダー選出とは異なり、建設的な干渉を起こします。これはレイテンシが劇的に変動する可能性がある Cloudflare のネットワークにとって理想的です。

QuePaxa は、より信頼性の低いネットワーク環境（非同期）や、架空の敵対者がレプリカ接続に対して標的型攻撃を仕掛ける可能性のあるネットワークのために設計されました。著者らは、このような条件下において、Raft や Multi-Paxos に比べてはるかに高い（約 10 倍）スループットを維持できることを発見しました。これらの条件は、他のアルゴリズムが想定する環境よりも、私たちが実際に直面しているネットワーク状況をより正確に反映しています。

QuePaxa の完全な説明については別の投稿で取り上げます。EPFL から QuePaxa 論文の著者の方々に対し、彼らの研究に関するフィードバックや質問に応じていただいたことに、大きな感謝を申し上げます。

Meerkat のパフォーマンス評価

Meerkat には限界があります。データベースのような汎用データシステムを構築するために設計されたものではありません。

すべての合意形成アルゴリズムにはコストが伴います：多くの往復通信が必要です。特に QuePaxa では、初期提案者とレプリカの過半数の間で、提案の決定とログへのイベント追加を行うために通常 1〜3 回の往復通信（場合によってはそれ以上）を要します。違いはリーダーにあります。リーダーが提案する場合は 1 回（+ 決定内容をレプリカに通知するための追加ブロードキャスト）、非リーダーが提案する場合は 3 回（+ 追加ブロードキャスト）です。複数のレプリカが同時に提案を行う場合、さらに多くの通信が必要になることもあります。これらの通信コストは、合意形成アルゴリズム全般における重要な性能限界を示しています：提案決定の遅延は、過半数のレプリカ間の遅延に比例します。つまり、レプリカ同士が遠く離れている場合、遅延は増加する一方です—これを回避する方法はありません。

一見すると、Meerkat の書き込みおよび読み取りの遅延は非常に悪くなるように思えます。特に、整合性を保つためにすべての書き込みと読み取りがログを経由し、結果として多くの往復通信を必要とする場合です。

しかし、Meerkat からより良い性能を引き出すためのいくつかの方法があります：

開発者はレプリカの配置場所を制御できるため、レプリカ同士を近づけて配置することで、往復遅延を削減できます（ただし、真のグローバル分散を必要としないサービスにのみ適用可能です）。

書き込みはバッチ処理できます。つまり、あるレプリカが 10 ミリ秒の間に 10 件の書き込みを受け取った場合、それらすべてを単一の提案にまとめることができ、スループットを向上させることができます。

すべての読み込みが合意形成ラウンドをトリガーする必要はありません。開発者が、古くても（決して不整合ではない）データを読むことに問題がある場合、任意のレプリカのローカルデータから読み込むことができます。

複数の操作を単一の合意形成ラウンドにバンドルできます。例えば、キーバリューストアは、値が読み込まれて以来変更されていない場合にのみ書き込みが実行される比較・スワップスタイルの書き込みをサポートしています。（実際には、一般的なトランザクションもサポートしています。）

それでも、Meerkat の根本的なレイテンシ制限は残っており、特に設計された通りグローバルスケールで実行される場合は顕著です。これらの制限により、短期的には制御プレーンの情報管理に完璧に適しています。