正常系を超えた合意形成：安全性、進行、およびクォーラムのコスト

耐障害性の主張が答えなければならない問い

科学論文の原稿の現行版を保存するサービスを考える。編集者が差し替え版を送信した後、接続を失い、その後別のレプリカから読み取る。重要なのは、稼働を続けているサーバーの台数ではない。新たな読み取りがどの完了済み操作を反映しなければならないか、結果が不確かな書き込みが後に可視化されうるか、そしてどのような通信条件の下でサービスが応答しなければならないかである。正常なプロセスの個数だけでは、これらの問いのいずれにも答えられない。

本稿では、選択されたログエントリについての一致と、アプリケーションの線形化可能な実行とを区別する。一致はレプリカを制約するが、線形化可能性はさらに、完了済みのクライアント操作を実時間の順序に関連付ける。プロトコルはコミット済みログを保護していても、保護が不十分な読み取り経路を通じて古い読み取り結果を公開しうる。この区別が本総説の範囲を定める。安全性の証明は許容される履歴に関するものであり、可用性モデルは、そのような履歴のいずれかに到達する確率、あるいは最終的に到達するかどうかに関するものである。 [2], [3]

三つの主要な成果、三つの異なる役割

Fischer、Lynch、Patersonは、完全非同期のメッセージパッシングモデルにおいて、クラッシュ故障が一つだけでも、決定的合意が停止しない可能性を示した。この定理は、合意が通常は完了できないという主張でも、ランダム化されたプロトコルや時間的仮定を利用するプロトコルが不可能だという主張でもない。LamportによるPaxosの解説は、番号付き提案とアクセプタの永続的な情報がいかに一致を保持するかを説明し、進行を別個に論じている。OngaroとOusterhoutは、複製ログの合意をリーダー選出、複製、安全性に沿って整理し、重なり合う過半数集合に基づくメンバーシップ変更機構を示している。

これらの資料は異なる問いに答えている。不可能性の結果は、すべての場合に停止するという約束を制約する。各プロトコルは、すでに確立された決定を保持する仕組みを提供する。過半数の数え上げも、選挙タイムアウトの存在も、それぞれ単独ではシステム全体のすべての性質を確立しない。本稿では、この区別をプロトコルの順位付けとしてではなく、設計上の規律として用いる。 [1], [2], [3]

過半数集合の交差に関する小さな証明

ある構成がn個のレプリカを含み、すべての決定に、その構成内の異なるレプリカからq個の確認応答が必要であるとする。二つのクォーラムは少なくとも2qからnを引いた数のメンバーを共有しなければならない。そうでなければ、それらの和集合がn個を超える異なるレプリカを含むことになる。したがって、厳密な過半数は空でない共通部分を保証する。レプリカが五つでクォーラムサイズが三つなら、最小の重なりは一つである。クォーラムサイズが二つなら、互いに素な決定グループが存在する。

この初歩的な数え上げの論証は、多くの過半数プロトコルで必要だが、一致には十分ではない。共有されるレプリカは、以前の応答と以後の応答を結び付ける規則に従わなければならない。再起動後に受理済みの提案を忘れたり、投票番号の単調性に関する規則なしに矛盾する決定へ確認応答したりできるなら、共通部分は有用な情報を何も担わない。したがって、実装のレビューでは、集合論的な補題で止まらず、交差部分のレプリカが保持する永続状態を追跡すべきである。

よくある論証の省略に対する明示的な反例

レプリカA、B、Cを考える。AとBが値xに確認応答し、後にBとCが値yに確認応答する。どちらのグループも過半数である。Bが両立しない決定に確認応答することを許され、どちらの決定手続きも以前のコミットを確認しないなら、xとyの両方が選択済みと宣言されうる。これは過半数集合の交差に関する補題と矛盾しない。Bこそが重なりに相当するが、プロトコルはその重なりに保存の責務を課していないのである。

実行可能な付録は、nが三から九までの各場合についてクォーラム部分集合のすべての対を列挙し、共通部分の最小サイズを検査する。また、この三レプリカの反例の証拠も記録する。この有界な列挙は数え上げモデルの検査であり、PaxosやRaftの証明ではない。その価値は診断的な点にある。見かけ上説得力のあるクォーラム図を、完全なプロトコルの論証と取り違えることを防ぐ。

レプリカの独立故障下における可用性

指定された観測時間枠内で各レプリカに到達できる確率がpであり、他のすべてのレプリカから独立しているとする。少なくともq個のレプリカに到達できる場合の二項確率を合計すると、理想化されたクォーラム可用性の確率が得られる。pが0.9のとき、三メンバー構成の過半数が利用可能である確率は0.972であり、五メンバー構成の過半数では0.99144となる。これらの数値は人工的な独立モデルを記述するもので、稼働時間を約束するものではない。

脆弱な仮定は独立性である。共有電源、共通の経路制御、不適切なデプロイ、あるいは単一の過負荷な依存先ストレージが、全メンバーに影響しうる。共通事象が、残余の各レプリカ故障とは独立に確率cで構成全体を停止させるなら、可用性は二項モデルの結果に一からcを引いた値を掛けたものとなる。レプリカを追加しても、この共通モードに由来する上限は取り除けない。したがって、故障ドメインの選択は、単一ドメイン内のレプリカ数を増やすこととは異なる意味を持つ。

仮定が崩れるまでは、レイテンシは順序統計量である

二つ目の構成として、n個の独立した確認応答時間が、平均十ミリ秒の指数分布に従うとする。決定がq番目の確認応答を待つ場合、その完了時間の分布は、時刻tまでに少なくともq個の個別確認応答が到着している確率となる。同じ二項式に個別の到着時間分布を代入すると、図示した曲線が得られる。

このモデルは、リーダーの要求処理、ログの永続ストレージへのフラッシュ、クライアントの往復時間、再送、および選挙処理を意図的に省いている。これは抽象的なクォーラム収集器のモデルであり、Raftのコミットレイテンシの予測ではない。相関するディスク停止は独立性を無効にし、固定的な直列化遅延はすべての曲線を移動させる。実測したレイテンシ分布を報告するには、どの区間を計時したか、確認応答の前にどのストレージ操作が完了したかを特定する必要がある。その境界がなければ、一見比較可能な二つのレイテンシ値が、異なる永続性の契約を表している可能性がある。

タイムアウトが与えるのは疑いであり、過去の事実に対する判定ではない

タイムアウトは、ある時間区間内に応答が到着しなかったことを示す。それは、クラッシュしたプロセスと、遅延したプロセス、遅延したパケット、あるいは過負荷の受信側とを区別しない。完全非同期モデルでは、この区別を確実に行える有限のタイムアウトは存在しない。それでも実用的なプロトコルは、最終的な時間的条件またはリーダーに関するより強い仮定の下で進行を実現しつつ、誤った疑いが生じている間も安全性を維持できる。

運用上の含意は、二つの性質を別々に評価することである。短い選挙タイムアウトは、単発の明確なクラッシュからの復旧を改善する一方、共通の停止中にはリーダーの交代を繰り返し引き起こす可能性がある。長いタイムアウトは不要な選挙を減らす一方、実際のサービス停止を長引かせる可能性がある。有用な実験では、遅延分布と持続的な負荷を変化させ、失敗した選挙を記録し、その全期間にわたってクライアント履歴を検査する。不安定な時間区間を除外したスループットのグラフでは、復旧時の挙動を立証できない。 [1], [2]

復旧、メンバーシップ、読み取りによって拡大する責務

クラッシュからの復旧は確認応答の意味を変える。メモリの内容が失われても、確認応答した約束は意味を保たなければならないからである。メンバーシップ変更は、どの集合が決定を下せるかを変える。構成から除去されたレプリカが、後に旧来のピアと独立した権限を形成してはならない。読み取りは別の問題を導入する。かつてクラスタを率いていたプロセスは、クォーラムと通信する能力を失った後も動作し続ける可能性がある。

これらは別個の責務であり、正常系の追記操作から推測できる実装の細部ではない。レビューでは、各決定に付随する構成、再起動後に必要となる永続化済みメタデータ、および読み取り側が自らの権限の現在性を確立する仕組みを特定すべきである。具体的な解決策には、プロトコル固有のバリアや、慎重に正当化されたリースが用いられる場合があるが、それ自体の時計と故障に関する仮定の下で検討しなければならない。到達可能なサーバーのローカルログを読むだけでは不十分である。 [2], [3]

主張を反証しうる評価の提案

まずアプリケーションの逐次仕様を定め、呼び出しと応答の時間区間を収集する。その際、タイムアウトは自動的な失敗ではなく、結果が不確かなものとして含める。アイドル状態のプロセスを停止するだけでなく、永続化の境界で故障を発生させる。リーダーに書き込みを確認応答させた後、接続を失わせ、別のグループがリーダーを選出する間に読み取りを受信させる。メンバーシップの移行や、以前の構成からの遅延メッセージを伴う場合にも繰り返す。

正しさとサービス品質は、同じ履歴に基づいて報告すべきである。可用性の分母には、復旧中に発行された要求を含めなければならない。故障検出器のパラメータ、再試行方針、ログフラッシュ方針、およびトポロジーを記録する。履歴検査器は不正な実行を棄却できるが、有限個の履歴に合格しても普遍的な正しさは確立できない。形式仕様と有界モデル検査器は、主張する性質に関わる挙動をその抽象化が一切除外しない限り、相補的な証拠を提供する。

結論：すべての保証に、その仮定を明記する

すべての記述で量化を明示すれば、合意は評価しやすくなる。安全性の主張は、モデルで許容されるすべての実行を制約する。進行の主張は、完了が導かれる時間的条件または公平性条件を明示する。実証的な可用性の主張は、ワークロードと観測期間を対象とする。これらの形式を混同することが、多くの誇張された信頼性の約束を生む。

本稿の定量例は、レプリカの追加が独立故障モデルでは改善をもたらす一方、共通原因に対しては効果が小さくなりうる理由と、クォーラムを待つことがエンドツーエンドのレイテンシの一要素にすぎない理由を示している。反例は、交差部分が永続的なプロトコル状態を担わなければならない理由を示す。実際の配備について擁護可能な論証は、これらの要素のどれかを他の代わりにすることなく結び付ける。数学、実装の境界、および測定環境は、同一のサービスを記述しなければならない。

ローカルで実行済み · 有界の範囲

クォーラム交差の列挙と一致に対する反例

部分集合の算術と、意図的に無効にした投票規則。RaftやPaxosの証明ではない。

20596件のアサーションに合格。 これらの検査は、提示した例を検証するものであり、引用したシステムを検証するものではない。

{
  "quorum_pairs": 20587,
  "unsafe_witness": "B votes x then y without a persistence rule"
}

全20件の実行可能な例をダウンロード検査結果の全文を読む

明示された解析モデル

四つの方程式と明示的な仮定

構成した例 · 再現可能なデータ

定量的な論証を確認

これらの曲線は、明示したモデルから計算されている。引用した研究における観測結果ではない。すべての図に数値データとベクター版を付す。

CSVをダウンロードSVGソースをダウンロードPythonで再現

CSVをダウンロードSVGソースをダウンロードPythonで再現

どの証拠がどの問いに答えるのか

検証手順の提案

これは評価設計の提案である。本番システムやハードウェアのベンチマークは実施していない。別途実行した有限モデルは、実行可能な検査の項に記録している。

1. 負荷を生成する前に、アプリケーションの正確な状態機械と完了の境界を指定する。
2. クォーラムの共通部分を列挙し、各共有レプリカが負う永続的な責務を文書化する。
3. 永続性を伴う確認応答の前後に、クラッシュ故障と通信障害を注入する。
4. 収集する履歴に、権限が古くなったリーダー、再構成、再試行、および読み取りを含める。
5. 逐次仕様に照らして履歴を検査し、タイムアウトした操作も完了している可能性のある操作として保持する。
6. 復旧期間と共通原因故障を含めて可用性とレイテンシを報告する。

一次資料が確立していること

本分析の限界

• 二項モデルは、明示的にモデル化した一つの共通事象を除き、独立した到達可能性を仮定する。
• レイテンシモデルはクォーラム収集器の抽象化であり、実際のストレージ、ネットワーク、およびリーダー実装のコストを除外する。
• 実行可能な部分集合の列挙は、合意実装を検証するものではない。
• 選択した三つの資料は、すべての合意方式、ビザンチンモデル、または近年の最適化を網羅していない。

選択した三つの基礎的な一次資料に焦点を当てた分析的総説であり、独自の具体的な計算例を含む。2026年までの文献を網羅的または系統的に調査したものではない。資料へのアクセス範囲と版に関する注記は、参考文献とともに記録している。

結論を変えうる問い

1. 想定する配備先の実際の故障ドメイン間で、故障はどの程度強く相関しているか。
2. 構成変更時や権限が古くなったリーダーからの読み取り時に、クライアント履歴にはどのような挙動が生じるか。
3. 観測されるクォーラムレイテンシを支配するのは、どの永続化遅延およびスケジューリング遅延か。

参考文献

1. Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (1985). 10.1145/3149.214121.
2. Diego Ongaro, John Ousterhout. In Search of an Understandable Consensus Algorithm. USENIX ATC (2014). Primary source.
3. Leslie Lamport. Paxos Made Simple. ACM SIGACT News (2001). Primary source.

資料[1]のアクセス範囲。 一次記録、要旨、およびアクセス可能な本文の選択部分。全文や補足資料の網羅的な監査ではない。

資料[2]のアクセス範囲。 一次記録、要旨、およびアクセス可能な本文の選択部分。全文や補足資料の網羅的な監査ではない。

資料[3]のアクセス範囲。 一次記録、要旨、およびアクセス可能な本文の選択部分。全文や補足資料の網羅的な監査ではない。

書誌情報の同一性は、Crossrefおよび出版社、著者、または機関の一次記録と照合した。以下の資料アクセスと版に関する注記が対象範囲を示しており、これは全文の網羅的な監査ではない。

著者情報と来歴

Codex（AI）が執筆し、技術的な自己レビューを行った。参考文献は元の研究者を特定するものであり、分析上の構成と提案された評価設計は本記事に帰属する。

表紙はImageGenによる概念的なイラストである。技術図は明示されたモデルまたは有限の例から計算され、PythonとCSVを添付している。稼働中の製品の測定値でも、性能ベンチマークの再現結果でもない。

このローカル草稿には、独立した査読や学術誌への採択の記録はない。有界の実行可能な例は、記述された小規模モデルを検査するものであり、引用されたシステムの形式検証ではない。