Meerkatの紹介：グローバルコンセンサスの実験

2026-07-08 • James Larisch • Bob Halley • João Pedro Leite • 12 min read

Cloudflare内の多くの内部サービスは、330以上のグローバルなデータセンター全体から同じ制御プレーンの状態を読み書きする必要があります。これらのサービスは、異なるリーダーが矛盾した状態を決して見ないという保証と、一部のデータセンターやリンクが障害を起こしても書き込みを可能にする可用性を必要とします。しかし、Cloudflareのネットワークはインターネット全体にまたがっており、インターネットは予測不可能な環境です。サーバーやデータセンターは落ちます。キューは溢れます。リンクやケーブルは切断されます。こうした条件は、分散システムのレプリカ同士が確実に同期する能力を阻害するため、強い整合性（例：すべてのリーダーがすべての以前の書き込みを確実に読むことが保証される）を保証するグローバルに可用なデータシステムを運用するのを困難にします。

悪条件下でも安全にデータを同期する方法の一つはコンセンサスアルゴリズムです。コンセンサスアルゴリズムは、過半数が生存して通信可能である限り、一連の値（キー・バリュー型ストアのputやget操作など）に対して複数のマシンが同意することを可能にします。残念ながら、一般的に用いられているRaftのようなコンセンサスアルゴリズムは、リーダーとタイムアウトに依存するため、Cloudflareのような広域ネットワークでは性能が落ちます。リーダーは書き込みを行える唯一のレプリカであり、クラッシュやネットワーク劣化でリーダーが失われると、別のレプリカがタイムアウトして新しいリーダーが選出されるまでシステムは利用不能になります。しかも、タイムアウト値は遅延が予測できないネットワークでは設定が難しいです。

私たちはコンセンサス駆動システムでリーダーが利用不能になったことが原因のインシデントを複数経験してきました。そこで、過去1年にわたりCloudflareのResearchチームは新しい分散コンセンサスサービス「Meerkat」を構築してきました。Meerkatは、EPFLの研究者らが2023年に発表したコンセンサスアルゴリズムであるQuePaxaによって動作します。QuePaxaはRaftと異なり、すべてのレプリカが常に書き込みを行うことができ、進行がタイムアウトによって止まることがないため、Cloudflareのネットワークに適しています。Meerkatのコンセンサスログの上に、トランザクショナルなキー・バリュー・ストアやリーシングシステムのようなアプリケーションを重ねています。私たちの知る限り、これはグローバルスケールでのQuePaxaの最初の実用的デプロイになるでしょう。

Meerkatはまだ開発中の実験的なコンセンサスサービスです。まずは小さな制御プレーン状態（例：レプリケートされたデータベースのリーダーシップ）を管理するように設計しており、当面は社内限定で運用されます。本稿ではMeerkatを紹介し、今後のMeerkat関連ブログ記事の基礎を説明します。

グローバル制御プレーンデータシステムに必要なもの

多くのCloudflareサービスは、世界中に分散された複数のマシンから制御プレーンデータを読み書きします。制御プレーンデータの例としては、あるリソース（例えばAIモデルのインスタンス）がどこに配置されているかという配置情報や、どのマシンが現在データベースへの書き込みを許可されているかというリーダーシップ情報などがあります。

制御プレーンデータは、特定の種類の障害が発生してもアクセス可能であり、かつ強い整合性を満たす必要があります。本節ではCloudflareのコンセンサスサービスに対する整合性とフォールトトレランス要件を厳密に説明します。例として、コンセンサスサービス上で動作するアプリケーションとしてキー・バリュー・ストアを用いますが、分散リーシング／ロックなど他のアプリケーションも可能です。

強い整合性

分散データシステムの整合性レベルは、同時に行われる読み書きに対してシステムがどのような奇妙な挙動を許容するかを示します。例えば、単一の数値 x = 6 を複数ノードで保持する分散キー・バリュー・ストアを考え、次の書き込み列を考えます。これらの書き込みはベストエフォートで異なるノードに送られ、任意の順序で到着し得ます:

• x = x + 1
• x = x / 2

システムの整合性レベルは、これらの書き込みの後にクライアントが x を読んだときにどのような値を見得るかを示します。以下のように、操作と可能な実行順序を整合性レベル別に考えることができます。

• 弱い整合性レベルでは、書き込みが再順序される可能性があります。
• より強い整合性モデルでは書き込みは再順序されませんが、読み取りは再順序され得ます。
• 最も強い整合性レベルでは、操作は実際の実行時刻どおりに正確に順序付けられます。

この性質はlinearizability（線形化可能性）と呼ばれます。Cloudflareでは多くのサービスがlinearizabilityを望みます。弱い整合性とは異なり、linearizabilityはプログラマがデータシステムの全ての奇妙な振る舞いを考慮する必要をなくします。代わりに、単一スレッド上のローカルメモリのようにシステムを考えることができ、書き込みの後のすべての読み取りはその書き込みを必ず見ると仮定できます。弱い整合性の危険性についてはMarc Brookerの投稿が参考になります（参考にどうぞ）。

（参考までに、Meerkatのキー・バリュー・ストアは将来の投稿で扱う予定ですが、serializabilityも提供します。）

フォールトトレランス

システムのフォールトトレランスレベルは、どのような障害までシステムが耐えられるかを示します。大惨事とは通常、システムが守ろうとする性質の違反を指します。例えば、同一キーに対して間に書き込みがない2回の連続した読み取りが異なる値を返す、あるいはシステムが書き込みに対して利用不能になる、などです。障害にはネットワークの故障や遅延、マシンのクラッシュ、再起動などが含まれます。システムは通常、全ての障害を扱えるわけではなく、扱う障害の範囲を明示します（宇宙が熱的死に到達する可能性を除いてすべてを扱うことはできません）。例えば、あるキー・バリューストアはシステム内の3分の2のマシンが通信可能でクラッシュしていない限り書き込みに対して可用であることを保証するかもしれませんが、マシンが乗っ取られて悪意あるメッセージを送る場合には保証しない、という具合です。

私たちが望むフォールトトレランスの性質は次のとおりです。

• 第一に、システムは次が成り立つ限り、任意のデータセンターにいるクライアントからの読み書きに対して可用であるべきです:

  • システム内のマシンの過半数が生存して相互に通信できること。（形式的には、2f + 1台のシステムでf個の故障を許容します。）
  • クライアントが過半数の生存マシンに接続されている任意のマシンに接触できること。

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

• 第二に、システムはシステム内の何者も積極的に悪意を持っていない限り（もちろんバグがないことも前提として）正しくあるべきです。正しさは後でコンセンサスの安全性という観点で定義しますが、緩やかに言えば、最新の状態に追いついている2つのマシンが世界について矛盾することが決してない（例：一方のマシンはkey1=1だと考え、もう一方のマシンはkey1=2だと考えることがない）ことを意味します。

要約すると、マシンのクラッシュ、マシンの再起動、ネットワークの故障や劣化、データセンターのダウンなどが起きてもシステムは正しくあるべきです（ただし、Raftベースのシステム同様、ビザンチン故障は扱いません）。

Meerkatの紹介

Meerkatは、上記の性質（強い整合性とフォールトトレランス）を満たすアプリケーション（例：キー・バリュー（KV）ストア）を構築できるコンセンサスサービスです。Meerkatの動作を理解するために、まず全体アーキテクチャの概略を示し、次にMeerkatが採用するコンセンサスアルゴリズムがどのように強い整合性とフォールトトレランスに寄与するかを説明します。

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

クライアントがクラスタとやり取りするには、アプリケーション固有のリクエストをクラスタ内の任意のレプリカに送信します。単一のレプリカは多くの種類のアプリケーションをホストする可能性がありますが、最も単純なものはキー・バリュー・ストアなので、最も単純なアプリケーション固有のリクエストはKV getやputです。レプリカはアプリケーション固有のレスポンス（例：getで要求されたレコード）で応答します。getによるKV読み取りは最新の情報を読むことが保証されます。

Meerkatのログ

内部では、レプリカはアプリケーションリクエスト（例：getやput）をログイベントに変換します。そのレプリカは各ログイベントをコンセンサスアルゴリズムを用いて他のすべてのレプリカに配布し、すべてのレプリカが同一のイベントログを保持するようにします（実際にはレプリカが遅れることはありますが、異なるエントリを記録することは決してありません）。これらのイベントの中身は任意で、Meerkatのコアはその内容を気にしません。Meerkat上の各アプリケーションがログイベントの内容を解釈します。各Meerkatレプリカは多数のMeerkatアプリケーション（例：キー・バリュー・ストア）を「ホスト」し、ログイベントを読み取って状態を構築します。（各レプリカは正確に一つのクラスタに属します。）

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

以下は、レプリカがログイベントを受け取るにつれてKVストアがどのように更新されるかの例です。

Meerkatのログが強い整合性を可能にする仕組み

Meerkatは、あるクライアントがput k1 v1を実行し、別のクライアントがその後にput k1 v11を実行し、さらに別のクライアントがその後にget k1（一貫した読み取り）を実行した場合、常にv11が読まれることを保証します。これは各リクエストが異なるレプリカに送られ、かつそれらのレプリカが世界中に分散していたとしても成り立ちます。これが線形化可能性です。

Meerkatがこれを保証する仕組みを理解するには、Meerkatのログをもう少し詳しく見る必要があります。Meerkatのログはスロットの列です。スロットはイベントを含むことも含まないこともある箱です。イベントを含むスロットを「decided slot（決定済みスロット）」と呼びます。ログ内のすべてのスロットは最後の1つを除いて決定済みです。最後のスロットだけが現在決定中の状態にあります。Meerkatの不変条件の一つは、もし任意の2つのレプリカがあるスロットの値を決定したならば、それらの値は同じである、ということです。言い換えれば、決定済みスロットの値について2つのレプリカが意見を食い違わせることは決してありません（ただし、一方のレプリカは最後のスロットを空だと考え、もう一方は空でないと考えることはあり得ます）。この性質が前節で述べた望ましい性質の保証に寄与します。

ログの最後の（空の）スロットの値を決定するために、Meerkatレプリカは分散コンセンサスアルゴリズムを実行します。コンセンサスアルゴリズムは、ネットワークを介して通信するマシン群がある値に合意することを可能にします。私たちのコンセンサスアルゴリズムは、過半数のレプリカ（半数より多い）が生存している限り動作します。したがって、ログに現在2つのエントリがあり、クライアントがput k1 v11をあるレプリカに送ると、そのレプリカはスロット3のためにコンセンサスアルゴリズムを起動します。しかし別のクライアントは別のレプリカに対してスロット3のput k1 v111を送っているかもしれません。コンセンサスアルゴリズムは、スロット3に対する提案のうち一つだけが勝つことを保証します。具体的には、少なくとも過半数のレプリカが同じ提案に同意してスロット3を決定することを保証します。過半数に入らないレプリカは異なる提案を決定することは決してできませんが、スロット3が決定済みであることに気づかない可能性があります。

このことがキー・バリューストアに対してどのように線形化可能性を提供するかを見るために、書き込みの後に読み取りが行われるケースを考えます。あるレプリカZがput k1 v11を提案し、この提案が過半数のレプリカによってスロット3に決定されたが、レプリカYは決定に参加していなかったとします。その後、リーダーがget k1をレプリカYで実行します。レプリカY beli