概要

• Cloudflareは 330以上のグローバルデータセンター で制御プレーン状態を一貫して管理する必要
• 従来の Raftなどの合意アルゴリズム は広域ネットワーク環境で可用性に課題
• Cloudflareは QuePaxa という新しい合意アルゴリズムを採用した Meerkat を開発中
• Meerkatは 全レプリカが常時書き込み可能 で、リーダー不在による停止がない特長
• 本記事はMeerkatの概要と今後の技術記事への導入を目的とする

Cloudflareのグローバル制御プレーンデータシステムの課題

• Cloudflareの多くの内部サービスは 全世界のデータセンター から同じ制御プレーンデータの読み書きが必要
• 一貫性の保証 と、ネットワーク障害やデータセンター障害時でも 書き込み可用性の維持 が重要
• インターネット上のネットワークは 不安定 であり、サーバーダウンやリンク切断が頻発
• 強い一貫性（例：全てのリーダーが過去の書き込みを必ず読める）を保証する分散データシステムの運用は困難

合意アルゴリズムと既存手法の課題

• 合意アルゴリズムは 複数マシン間で値の順序に合意 するための方式
  • 例：Raftでは リーダーが唯一書き込み可能、リーダー障害時はタイムアウト後リーダー選出
• 広域ネットワーク ではタイムアウトの調整が難しく、リーダー不在によるシステム停止が発生しやすい
• Cloudflareでも リーダー不在による障害 が実際に発生

MeerkatとQuePaxaによる新しいアプローチ

• Cloudflare Researchは QuePaxa （EPFLが2023年発表）を用いた Meerkat を開発
  • 全レプリカが常時書き込み可能 で、タイムアウトによる進行停止がない
  • グローバル規模での初の産業利用 を目指す
• Meerkatはまず 内部利用限定 で、制御プレーンの小規模データ管理用途に設計

制御プレーンデータシステムへの要件

• 制御プレーンデータ例： リーダーシップ情報 や リソース配置情報
• 必要要件
  • 強い一貫性（Linearizability）
    • 全ての読み込みは最新の書き込みを必ず反映
    • プログラマは シングルスレッドのローカルメモリのように分散システムを扱える
  • 高いフォールトトレランス
    • システムの過半数が生存し通信可能 であれば書き込み・読み込みが常に可能
    • 単一ノードやリンク障害で可用性に影響しない
    • Byzantine障害 （悪意あるノード）は未対応だが、クラッシュや再起動、ネットワーク障害には対応

Meerkatのアーキテクチャ

• サービス開発者は Meerkatレプリカクラスタ を要求
  • 各レプリカは 全ての他レプリカと接続
  • レプリカは 読み書き両方を受け付け可能
  • どのデータセンターに配置するか指定可能
• クライアントは 任意のレプリカにリクエスト送信、レスポンスを受け取る
  • 例：Key-Valueストアのget/putリクエスト
• 全レプリカが同一のログ（イベント列）を維持
  • 各リクエストは ログイベント に変換され、合意アルゴリズムで全レプリカに分配
  • 各アプリケーションは ログを順次適用 して状態を構築
  • getリクエストもログイベント化 （Linearizability維持のため）

Meerkatログによる強い一貫性の実現

• ログは スロットの連なり で構成、各スロットは1つのイベントを保持
• 決定済みスロット は全レプリカで必ず同一内容
• 最後のスロットのみ決定中、他は全て決定済み
• 合意アルゴリズムにより 過半数の合意でスロットの内容が決定
• 例：異なるレプリカで同時に異なるputリクエストが出ても、 1つの提案だけが採用される
• Linearizability ：書き込み→別レプリカで読み込みでも、必ず最新値を返す

今後の展望

• Meerkatは 実験的サービス として開発中
• 分散トランザクション や 分散リース・ロック など多様なアプリケーションへの応用を想定
• 今後のブログ記事で 技術詳細や実装例 を解説予定