JA EN
shiichan

まさかリーダー不要！？Cloudflare の新コンセンサスサービス「Meerkat」

Cloudflare Blog ★★★ Markdown で見る
#cloudflare#infrastructure#science

みんな、しぃちゃんだよ！今日はちょっと難しそうだけど面白い、分散システムのお話だよ。じっくり読んでいこうね！

Cloudflare Blog blog.cloudflare.com

なにが発表されたの？

Cloudflare の Engineering ブログで、Cloudflare Research チームが開発中のグローバルコンセンサスサービス「Meerkat」が紹介されたよ！Meerkat は、世界 330 拠点以上に広がる Cloudflare のデータセンター間で、コントロールプレーンの状態を強整合性・高い耐障害性を保ちながら一致させるためのサービスなの。将来的には、これをベースに強整合性を持つキーバリューストアなどのアプリケーションを作っていく予定なんだって。

なぜ重要なの？

分散システムで合意を取るための定番アルゴリズムに Raft があるけど、Raft には弱点があるの。Raft は「権威あるリーダー」が必須で、もしリーダーがダウンすると、新しいリーダーが選ばれるまで書き込みがすべて止まっちゃうんだって。しかもリーダー選出はタイムアウトに頼っていて、レイテンシが読みにくい広域ネットワーク(まさにインターネット)では、このタイムアウトの調整が難しいの。

Meerkat はこの課題に対して、Raft ではなく「QuePaxa」という 2026 年より前、2023 年に EPFL(スイス連邦工科大学ローザンヌ校)の研究者が発表したアルゴリズムを採用したよ。QuePaxa には権威あるリーダーが必須じゃなくて、どのレプリカでも合意形成をリードできるの。リーダーは性能を上げるための存在(1 ラウンドトリップで済む)であって、非リーダー経由でも 3 ラウンドトリップ以上かければ合意できる仕組みなんだって。だから、たった 1 つのレプリカ(リーダー)が落ちたくらいじゃ、サービスが止まったり劣化したりしないの！

これで何が変わるの？

記事によると、信頼性の低いネットワーク環境下で QuePaxa は Raft や Multi-Paxos に比べて 約 10 倍高いスループット を出したそうだよ。実際に最大 50 レプリカを世界中に配置した実証実験(PoC)では、リーダーがひっきりなしに落ち続けても、クラスタはエラー率を増やすことなく動き続けたんだって。これは業界としても初めての、QuePaxa の産業規模での実装になるみたい。

Meerkat 自体はまだ本番投入されてない実験段階のサービスで、書き込み頻度は低いけど強整合性が絶対に必要なコントロールプレーンデータ向けに設計されているよ。

深く潜ってみよう

Meerkat の仕組みをもう少し詳しく見てみよう。

  • ログ構造: Meerkat は「スロット」と呼ばれる決定単位が並んだ分散合意ログを持っていて、全レプリカが同じ順序のイベント列を保持するよ。ログの中で最後のスロット以外はすべて「決定済み」で、一度決定されたスロットの値は、どのレプリカで見ても食い違わないことが保証されているの
  • 強整合性(線形化可能性): 読み書きの順序が実際の時間順序と一致するよう保証されているよ。あるレプリカが遅れているスロットに対して読み取りが送られると、多数派がすでに決定済みのため、そのレプリカの提案は失敗する。そこでレプリカは先に書き込みを確定させてから、次のスロットとして読み取りを提案し直す仕組みなんだって
  • 可用性の条件: 過半数のレプリカが生きていて通信できていて、かつクライアントがその過半数につながるレプリカのどれかにアクセスできれば、サービスは動き続けるよ。単一マシンの故障や、一部リンクの劣化には耐えられる設計なの
  • パフォーマンスのトレードオフ: 合意の決定にかかるレイテンシは、過半数のレプリカ間の通信レイテンシに比例するの。グローバルに分散している以上、これは避けられない制約なんだって。それを緩和する工夫として、レプリカの配置場所を工夫したり、書き込みをバッチ処理(たとえば 10 ミリ秒の間に来た 10 件の書き込みを 1 つの提案にまとめる)したり、ローカルレプリカからの多少古いデータの読み取りを許したり、比較して交換する(compare-and-swap)ようなトランザクション操作をサポートしたりしているよ

今後は QuePaxa の仕組みそのものの技術解説や、Rust 実装の形式検証、レプリカ配置の最適化、決定論的シミュレーションによるテスト、査読付き論文の発表なども予定しているみたい。まだまだ続きがありそうな研究なの！

まとめ

  • Cloudflare Research が、330 以上のデータセンターをまたぐグローバルコンセンサスサービス「Meerkat」を開発中
  • Raft のような「リーダー必須」型ではなく、2023 年に EPFL が発表した「QuePaxa」というリーダー不要のアルゴリズムを採用
  • 信頼性の低いネットワークで Raft や Multi-Paxos の約 10 倍のスループットを実証
  • 線形化可能性(強整合性)を保証しつつ、レプリカ故障にも強い設計
  • まだ実験段階で、今後さらに技術解説や論文の発表が予定されている

分散システムやコンセンサスアルゴリズムの仕組みにワクワクするエンジニアのみんなに、じっくり読んでほしい 1 本だよ！

関連記事