クラウド・インフラ

Raftの選挙タイムアウトには下限がある——RTTの1.8倍を切ると、クラスタは安定を取り戻せない

イーランサー・ジャパン株式会社
この記事の要点

複数のサーバで同じ記録を持ち合うとき、どれを正とするかを決める仕組みを合意アルゴリズムと呼びます。広く使われている方式では、代表役のサーバが一定時間返事をしないと交代させる、という設計になっています。

この「一定時間」を短くすれば障害に速く気づけそうですが、論文の実測では逆でした。通信の往復時間の1.8倍あたりまで下げると性能が落ち、1.1倍では安定しなくなります。大陸をまたぐ構成では、この下限が障害検知の速さの限界になります。

用語の説明
  • RTT/通信の往復にかかる時間のことで、距離が遠いほど長くなります。
  • リーダー/複数台のうち、書き込みの順番を決める代表役のサーバのことです。
  • スループット/一定時間にどれだけの処理をさばけるかを表す量のことです。

Raftを運用していれば必ず触るノブがあります。選挙タイムアウトです。短くすれば障害検知が速くなる——はずでした。論文の実測では、RTTの約1.8倍を切るとスループットが落ち、1.1倍あたりでは安定そのものを失います。下げると壊れる方向にしか動かないノブだった、という話です。

要点

何が起きたか

著者はCloudflare Researchの3名。Meerkat は7月8日公開の社内コントロールプレーン向けの実験的合意サービスで、replica が get/put の順序付きログに合意します。位置づけは etcd に近く、実装は Rust です。

動機は実際の障害です。2020年、コアスイッチの「部分的な」故障で合意ベースのシステムが劣化し、ダッシュボードが6時間にわたり通常の80倍遅くなりました。データ損失はないものの、書き込みが不能になっています。

選挙タイムアウトの下限

Raft・Multi-Paxos・VSRは、単一リーダーが「生きていて、かつレイテンシが予測可能」であることに依存します。落ちた場合だけでなく遅くなっただけでも系が止まり、非同期ネットワークでは遅いサーバと死んだサーバが区別できません。

記事は etcd のドキュメントを引き「選挙タイムアウトはRTTの5〜10倍が一般的」と書きます。地球の半周は数百msなので検知に約1秒。短くすればよい話でもありません。論文 §7.5 の実測(5 replica、WAN、平均RTT 180ms、t=15sでリーダーをcrash-stop)はこうです。

330 ÷ 180 ≒ 1.8。タイムアウトはRTTの約1.8倍より下げられません。一方QuePaxaはスイープした全ヘッジ遅延(50/100/200/300/500ms)で 25k cmd/sec を維持し、復帰は 303〜473ms。最良は約200ms、RTTの約1.1倍です。

論文の評価数値の大半は図にあり、本記事はテキストに書かれた値のみを使っています。「330ms」「200ms」はテキストから取った値ですが、グラフ上の正確な分岐点は図を読めていないため検証できていません。1.8倍は 330÷180 の本記事による計算です。

差の源——事後的な待ちと事前的な待ち

タイムアウトは事後的で、発火すれば view change を始めます——他の進行を妨げます。ヘッジ遅延は事前的で、発火しても干渉しません。

論文の一文が効いています。「タイムアウトを 0 に設定することは原理的にありえない」が「ヘッジ遅延 0 は普通にありうる」。記事の言い換えでは、Raftで 100ms のRTTに 5ms のタイムアウトを置けば系は完全に凍りますが、QuePaxaの 5ms ヘッジ遅延はアクティブな proposer を増やすだけです。

なぜ干渉しないのか

QuePaxaは役割を proposer とrecorder に分け、proposer 同士も recorder 同士も直接通信しません。proposal には乱数の優先度が付き、リーダーだけが最大優先度を独占します。より高い優先度を知らされた proposer は乗り換えます。

複数 proposer の同時進行は異常ではなく設計上の通常状態で、リーダーは「完全にオプション」になります。

  1. Phase 0:提案し最高優先度を採用(初回にリーダーの proposal が先に過半数へ届けば即決定=1 RTT の fast path)
  2. Phase 1:拡散
  3. Phase 2:過半数に問い合わせ、採用分と一致すれば決定
  4. Phase 3:未決定分を次ラウンドへ繰り越す

各フェーズは過半数の応答で前進します。安全性は過半数の交差で担保され、liveness 定理は「期待2ラウンド未満で確率1で終了」。

Cloudflareは論文から1点ずらし、ヘッジ遅延を replica 側ではなくクライアント側に待たせています(メッセージ数削減のため、結果は同じだとしています)。

自社評価の数字

「95%以上」「約65%」「最大1/3」は本番実績ではなく自社評価の数字です。Cloudflare記事のグラフ2枚は画像で読めておらず、これらは本文とキャプションのテキストから取得しました。またByzantine障害は論文の対象外で、きっかけになった2020年の障害は同社が「Byzantine failure」と呼んだ事象です。QuePaxaが守る範囲と、きっかけの障害の種類は一致していません。

なぜ日本でまだ語られていないのか

一次情報が3層に割れ、肝心の数値は最下層にしかありません。Cloudflareの11月11日記事(選定理由)、7月8日の Meerkat 発表、SOSP 2023 の論文PDF(実測値のほぼ全て)。タイムアウト下限 330ms/RTT 1.8倍はCloudflareの記事には書かれておらず、論文 §7.5 を開かないと出てきません。その評価も大半が図にあるため、翻訳も検索も拾いません。

日本語の到達点はPaxosとRaftまでです。Raftまでの解説は整備されていますが、QuePaxa ないし Meerkat を扱った日本語記事は本記事が確認した範囲で見つかりませんでした。英語でも紹介記事が並ぶだけです。

エンジニアにとって何が変わるか

設計。単一リージョン内ならRaftのままでよい。RTTが小さければ下限も小さく、1.8倍の制約は実害になりません。効くのは大陸をまたぐ構成で、RTTが数百msかつ変動する環境では、タイムアウトを下げられないことが障害検知時間の床になります。

運用。既存のRaftクラスタで今日できる確認があります。実測RTTに対し選挙タイムアウトが何倍か。5〜10倍なら余裕がありますが、tail latency を気にして下げてきた現場では、1.8倍の床にどれだけ近いかが見るべき数字になります。

採用判断。本番採用の時期ではありません。論文プロトタイプはGo 4,368行・crash-stopのみ・再構成未実装で、形式検証も安全性のみです(論文自身「ラウンド成功の確率的性質は検証できない」と書いています)。Cloudflareはこれを Rust で書き直し、crash-recovery拡張と形式検証を進行中です。

今は「2023年の論文が本番化されるまでに何が足りないか」が公開されていく段階だと見ておけばよいでしょう。Cloudflareは後続記事で検証・障害試験・ベンチマーク・本番化の知見を予告しています。

キャリア。合意アルゴリズムの選定は、長く「RaftかPaxosか」の二択でした。そこに「タイムアウトという前提自体を外す」選択肢が実装付きで現れたということです。論文を読んで数値を取り出し、自社のRTTと突き合わせる作業は、記事を待っていては間に合いません。

出典

PROJECTS

クラウド・インフラやデータ基盤の領域では、こうした案件を扱っています。

掲載は案件の一例です。単価・稼働条件・技術要件を含む詳細はご登録後にご覧いただけます。

CONSULTATION

案件をお探しの方へ

イーランサーでは、専任担当がご経歴と希望条件を整理したうえで案件をご提案し、条件面の調整もお手伝いしています。すぐに稼働できる状態でなくても、情報収集としてご相談いただけます。

ご登録いただいた情報が企業に公開されることはありません。氏名・連絡先を伏せたスキルシートを使用します。登録から案件のご紹介、契約手続きまで費用は一切かかりません。

案件を見る
案件をお探しの方 人材をお探しの方