Raftの選挙タイムアウトには下限がある——RTTの1.8倍を切ると、クラスタは安定を取り戻せない
複数の
この
- RTT/通信の
往復に かかる 時間の ことで、 距離が 遠い ほど 長くなります。 - リーダー/複数台の
うち、 書き込みの 順番を 決める 代表役の サーバの ことです。 - スループット/
一定 時間に どれだけの 処理を さばけるかを 表す量の ことです。
Raftを
要点
- 記事/Cloudflareが11月11日、
実験中の 合意サービス Meerkat にQuePaxa(SOSP 2023)を 選んだ 理由を 公開した。 同社は QuePaxaを「これまで デプロイされた とことの ない」アルゴリズム 書いている - 下限/原論文の
実測:平均RTT 180ms の WANで、 Raftと Multi-Paxosは 選挙タイムアウトが330ms以上 (RTTの でないと約1.8倍) 25k cmd/sec を 出せず、200msを 切ると 安定しない - 対比/QuePaxaはヘッジ遅延を
どの 、値に しても 25k cmd/sec リーダー障害からの 復帰は 303〜473ms - 前提/ただし Meerkat は
本番投入されていない。 同社自身「Raftや Paxosほど 実戦で 叩かれていない」と 書く
何が起きたか
著者はget/put の
動機は
選挙タイムアウトの下限
Raft・Multi-Paxos・VSRは、
記事は
- 330ms以上/Multi-Paxos/Raftは
25k cmd/sec を 出せる - 330ms未満/スループットが
落ち、 やがて liveness を 失う - 200ms未満/そもそも
安定しない
330 ÷ 180 ≒ 1.8。
論文の
差の源——事後的な待ちと事前的な待ち
タイムアウトは事後的で、
論文の
なぜ干渉しないのか
QuePaxaは
複数 proposer の
- Phase 0:提案し最高優先度を
採用 (初回に リーダーの proposal が 先に 過半数へ 届けば即決定=1 RTT の fast path) - Phase 1:拡散
- Phase 2:過半数に
問い合わせ、 採用分と 一致すれば 決定 - Phase 3:未決定分を
次ラウンドへ 繰り越す
各フェーズは過半数の
Cloudflareは
自社評価の数字
- 通常時/
ほぼ 全大陸に サーバを 分散した 構成で、決定の 95%以上が 。リーダーの Phase 0で 完了 遅い 経路では 3 RTTを 要し通常の 最大1/3 まで落ちる - リーダー障害時/決定レート約65%まで
下がり、 交代後に 100%へ 復帰。どの 時点でも 停止していない - 敵対条件下
(論文側) /少数ノードの送信遅延を 最大500msに すると、 QuePaxaは 75k cmd/sec以上、 Multi-Paxosと Raftは 2.5k で 飽和 - 万能ではない/LANの
コミットスループットではEPaxosが QuePaxaを (699k 対 584k)16.5% 上回る
「95%以上」
なぜ日本でまだ語られていないのか
一次情報が
日本語の
エンジニアにとって何が変わるか
設計。
運用。
採用判断。
今は
キャリア。合意アルゴリズムの
出典
- 一次/João Pedro Leite・Bob Halley・James Larisch
「Choosing QuePaxa, an unusual consensus algorithm」 (2026年11月11日、 The Cloudflare Blog) /Meerkatの 位置づけ、 2020年の 障害 (6時間・通常の 80倍)、 選挙タイムアウトは RTTの 5〜10倍が 一般的 (etcdドキュメント参照)、 proposer/recorderの 2役割と 4フェーズ、論文と 異なりクライアント側に 、ヘッジ遅延を 待たせる 自社評価の 95%以上 ・約65%・最大1/3、 Rust実装、 crash recoveryへの 拡張と 形式検証が 進行中、 「Raftや Paxosほど 実戦で 叩かれていない」 - 一次/Pasindu Tennage・Cristina Basescu・Bryan Ford ほか
「QuePaxa: Escaping the Tyranny of Timeouts in Consensus」 (SOSP '23、 DOI 10.1145/3600006.3613150) /本記事の 数値の 。大半の 出所 §7.5 の 330ms/200ms/RTTの 約1.8倍、 QuePaxaの 全ヘッジ遅延で 25k・復帰 303〜473ms・ 最良約200ms、 §7.4 の 敵対条件 (75k以上 対 2.5k)、 LANで 584k (EPaxos 699k)、 「タイムアウト 0 は ありえないが ヘッジ遅延 0 は ありうる」、 liveness定理、 Go 4,368行・crash-stopのみ・再構成未実装、 Promela/SPINの 検証は 安全性のみ。評価数値は ほぼ 全て 図に あり、 本記事は 図を 読めていない - 一次/dedis/quepaxa
(GitHub、 BSD-3-Clause) /論文プロトタイプの 所在確認。 replica と submitter は Go実装。最終コミット日は ページ上に 表示なし - 一次/James Larisch・Bob Halley・João Pedro Leite
「Introducing Meerkat: an experiment in global consensus」 (2026年7月8日、 The Cloudflare Blog) /Meerkatの 位置づけ確認用。本記事は 本文の 逐語取得に 失敗し要約経由の ため 未検証 - 参考/Cloudflare
「A Byzantine failure in the real world」/2020年障害の 一次記録。本記事は 未読 - 参考/etcd
「Tuning — Time parameters」/選挙タイムアウトの 根拠と して Cloudflare記事が リンク。本記事は 未読 - 参考/Fischer・Lynch・Paterson
「Impossibility of Distributed Consensus with One Faulty Process」/FLP不 可能性 - 参考/InfoQ
(2026年8月) /英語での 到達点の 確認。本文未読 - 参考/Hacker News
(2026年11月11日) /巡回に 使用
クラウド・インフラや
掲載は
案件をお探しの方へ
イーランサーでは、
ご登録いただいた
