# 分散コンセンサス ## 定義 分散コンセンサス（Distributed Consensus）とは、障害の可能性のある分散システムにおいて、複数のサーバーが同一の値・順序・決定に合意するための問題とその解法アルゴリズムの総称である。サーバーのクラッシュ・ネットワーク遅延・パケット損失・パーティションが発生しても「安全性（正しくない結果を返さない）」と「活性（過半数が稼働すれば前進する）」を保証する。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) **複製ステートマシンの文脈**: 実用的な合意アルゴリズムは複製ログ管理として具現化される。クライアントのコマンドをすべてのサーバーで同一順序で複製・適用することで、決定論的ステートマシンが一貫した状態を保つ。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) **実用的合意アルゴリズムの性質**（Raft 論文 §2 より）: - 非ビザンティン条件下での安全性（ネットワーク遅延・パーティション・パケット損失・重複・再順序付けを含む） - 過半数が稼働し通信できる限り可用性あり（5 サーバーなら 2 障害耐性） - タイミングに依存しない一貫性（故障クロック・極端なメッセージ遅延は可用性問題のみ引き起こす） - マイノリティの低速サーバーが全体性能に影響しない ## 主要アルゴリズムの比較 | 特性 | Paxos | Raft | Viewstamped Replication (VR) | ZooKeeper (ZAB) | |------|-------|------|------|------| | 設計目標 | 正確性・効率 | 理解しやすさ + 正確性 | 実用的一次コピー | 高性能一次バックアップ | | リーダーの強さ | 弱いリーダー（最適化として） | 強いリーダー（コアメカニズム） | リーダーベース | リーダーベース | | ログエントリの流れ | 双方向 | 一方向（リーダー→フォロワー） | 双方向（選挙中も） | 双方向 | | メッセージ型数 | 多数 | 4 種類（最少クラス） | 10 種類以上 | 10 種類以上 | | メンバーシップ変更 | α ベース（リーダーなし前提） | ジョイントコンセンサス | 2 フェーズ（処理停止） | — | | 形式仕様 | あり（TLA+等） | あり（TLA+ 約 400 行 + 非形式証明 3,500 語） | あり | あり | (Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) ## Paxos の問題点（Raft 論文 §3 より） 1. **難解性**: シングルデクリー分解が直感に反する。multi-Paxos の詳細が不足している。NSDI 2012 の非公式調査でも経験豊富な研究者の多くが Paxos に不安を感じると回答 2. **実装基盤の欠如**: Lamport のスケッチから多数の異なる実装が生まれ、相互に大きく異なる。Chubby 実装者の言「Paxos と実世界システムのニーズの間には重大なギャップがある」 ## 横断的知見 - **コンセンサスを「回避する」設計も有力な選択肢**: Amazon Aurora はシングルライター OLTP という制約（LSN 単調増加・書き込み拒否なし）を利用し、2PC/Paxos/Raft を使わずに耐久性・コミット・メンバーシップ変更を達成する。汎用のコンセンサスアルゴリズム（Raft 等）は過剰な機構になりうる。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]], [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **Raft の影響範囲**: CockroachDB は Raft をレンジ（Range）単位の複製に使用する。Amazon MemoryDB はログベースリーダー選出（Raft に類する）でマルチ AZ 耐久性を実現する。Raft 論文草稿の段階から 25 以上の独立実装が存在した。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]], [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]], [[@2024__SIGMOD__Amazon MemoryDB - A Fast and Durable Memory-First Cloud Database]]) - **理解しやすさ設計の方法論**: Raft は「問題分解」と「状態空間削減」という 2 技術だけで一貫して設計された。この方法論の反復適用がランキングシステムではなくランダム化タイムアウトを採用させた。「理解しやすさ」が設計制約として機能したとき、アルゴリズムのコーナーケースを事前に刈り込む効果がある。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) - **実運用での「弱いリーダーシップ」の具体例**: Raft 論文は「Chubby 実装者いわく Paxos と実世界システムのニーズには重大なギャップがある」と引用するが、[[SRE Book]] 第 2 章はその実世界での使われ方を具体的に示す。[[Chubby]] は Paxos による非同期コンセンサスで 5 レプリカを維持しつつ、信頼性のために 5 レプリカを持つジョブの中で「どのレプリカが実処理を担うか」というアプリケーションレベルのマスタ選出にも使われる。これは合意アルゴリズム自体(Paxos)と、それを利用する上位のマスタ選出ロジックが別レイヤーとして実装される事例であり、Raft がリーダー選出をアルゴリズムのコア機構として統合した設計とは対照的である。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]], [[@2016__OReilly__SRE Book - Chapter 2 The Production Environment at Google, from the Viewpoint of an SRE]]) - **コンセンサスの「多くの顔」を等価性で束ねる理論的視点は、Raft/Paxos の実装詳細比較とは異なる抽象レベルの整理を与える**: DDIA 2E 第10章は、単一値コンセンサス・CAS・共有ログ(total order broadcast)・fetch-and-add・アトミックコミットメントが相互に変換可能な等価問題であることを示す(fetch-and-add のみコンセンサス数2に限られ他は無限大)。これは、本ページが蓄積してきた Raft・Paxos・VR・Zab の実装レベルの比較(リーダーの強さ・ログエントリの流れ等)とは異なる、「どの合意アルゴリズムも同じ形式的問題を解いている」という上位の統一視点を与える。実務上は Raft・VR・Zab が共有ログ(total order broadcast)をネイティブに提供し、Paxos は Multi-Paxos 拡張で共有ログに到達する、という実装上の共通点も、この等価性から導かれる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "The Many Faces of Consensus", "Consensus in Practice") - **リーダー選出とログ追記という「2段階の重複クォーラム投票」構造は、Raft の投票制限(Leader Completeness Property)を一般化する**: 本ページはこれまで Raft 固有の「候補者のログが有権者より up-to-date でなければ票を与えない」という投票制限を記録してきたが、DDIA 2E 第10章はこれを Raft・Paxos・VR・Zab に共通する一般原則として位置づけ直す: リーダー選出の投票とログ追記の投票という2つのクォーラムは重複していなければならず(ある提案が承認されるなら、その投票者の少なくとも1人は直近のリーダー選挙にも参加していなければならない)、この重複性こそが「新リーダーが旧リーダーの既承認エントリを見落とさない」という安全性を生む数学的根拠である。Raft の投票制限はこの一般原則をログ長比較という具体的な形で実装した一事例に過ぎない。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "From single-leader replication to consensus") - **DDIA 第9章は「なぜ過半数のクォーラムが安全なのか」という一段手前の認識論的根拠を与え、本ページが蓄積してきたアルゴリズム比較の前提を補強する**: 本ページの「実用的合意アルゴリズムの性質」節は「過半数が稼働し通信できる限り可用性あり」を Raft 論文由来の性質として記録してきたが、DDIA 第9章は過半数クォーラムがなぜ安全なのかを一般原理として説明する——ノードは自身の生死・時間経過についてすら確信を持てないため(認識論的な限界)、単一ノードに意思決定を委ねられず、システムには同時に2つの過半数が存在しえないという数学的事実(重複性)によって過半数の決定は安全になる。DDIA はこの一般原理を「ノードが死んだと判定する」場面で導入するが、これは合意アルゴリズムのクォーラム投票と同じ数学的構造であり、本ページが扱う Raft/Paxos/VR/Zab のクォーラムメカニズムの認識論的な出発点を提供する。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 9 The Trouble with Distributed Systems]] "Knowledge, Truth, and Lies", "The Majority Rules") - **リーダー選出と合意は等価な問題であるという宣言は、本ページが蓄積してきた「リーダー選出はRaftの第一サブ問題」という位置づけを、逆方向から補強する**: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]は「リーダー選出は合意と同じことである。リーダーを選出するには、その存在に関して合意に達する必要がある。リーダーの存在に関して合意に達することができるなら、同じ手段を使用して、他のどのような事柄についても合意に達することが可能である」と述べる。本ページはこれまで「リーダー選出→Raftの第一サブ問題」という部分問題としての位置づけを蓄積してきたが、この宣言は逆方向の包含関係も成り立つことを示す: リーダーの存在について合意する能力があれば、それは任意の値についてのコンセンサス能力と等価である。この等価性は、DDIA 2E 第10章が示す「単一値コンセンサス・CAS・共有ログ・fetch-and-add・アトミックコミットメントの相互変換可能性」という等価問題群に、「リーダーの存在」というもう一つのインスタンスを加えるものである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]] §10.6 まとめ, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "The Many Faces of Consensus") - **単独のリーダー選出アルゴリズム(ブリー系・招待・リング)が安全性を持たない理由は、本ページが記録する「重複クォーラム投票」の欠如として説明できる**: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]は、ブリーアルゴリズム・招待アルゴリズム・リングアルゴリズムのいずれもネットワーク分断時にスプリットブレイン(複数リーダーの並立)を起こしうると明記するが、その理由自体は説明しない。本ページが既に記録している「リーダー選出とログ追記という2段階の重複クォーラム投票」原則(DDIA 2E第10章)を当てはめると、これらの古典的アルゴリズムはランクの比較や招待関係のみでリーダーを決定し、決定した集合を過半数の投票者と重複させる仕組みを持たないため、安全性を欠くと解釈できる。裏を返せば、Raft・Paxos・ZAB のような合意アルゴリズム内蔵型のリーダー選出が安全性を獲得できるのは、過半数クォーラムを要求する一点にある。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]] §10.1, §10.4, §10.5, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "From single-leader replication to consensus") - **[[障害検出器]]は FLP の不可能性を回避してコンセンサスを解決可能にする現実的な補強装置である**: 本ページはこれまで Raft・Paxos・VR・Zab という具体的アルゴリズムの比較を蓄積してきたが、[[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]]は一段抽象度の高い枠組みを提供する——「障害検出機能は必須条件であり、多くの合意アルゴリズムおよびアトミックブロードキャストアルゴリズムにとって、必要不可欠な要素」であり、Chandra と Toueg の研究 [CHANDRA96] は「数えきれないほどの誤りを犯す障害検出機能であっても、合意を解決するのは可能」であることを示した。非同期システムでは FLP の不可能性によりいかなるプロトコルも合意を保証できないが、障害検出機能は「モデルを増強するのに役立ち、精度と完全性の間でトレードオフを行うことによって、合意問題の解決を可能にする」。これは、Raft がタイムアウトベースのリーダー選出(ハートビートの欠落を障害の兆候とみなす仕組み)に依存する設計上の必然性を、より一般的な理論(不完全な障害検出器でも合意は解けるという Chandra-Toueg の結果)から裏付けるものであり、本ページが蓄積してきたアルゴリズム間比較の理論的な土台を補強する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] §9.5, [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) - **[[FLPの不可能性]]の定義そのものは、本ページが依拠する『詳説 データベース』第8章に遡れる**: 上の項目は第9章経由でFLPの不可能性を「障害検出機能が回避する制約」として扱ってきたが、その定理自体の内容(同意性・妥当性・終了性という3特性を、完全に非同期な系で有界時間内に満たす決定論的アルゴリズムは存在しない[FISCHER85])は第8章§8.5で導入される。第8章は同時に「FLPの不可能性は合意が不可能という意味ではなく、非同期システムでは有界時間内の合意到達が常に可能とは限らないことを意味するにすぎない」と釘を刺しており、この釘刺しこそが、第9章の障害検出機能や、Raft論文のランダム化タイムアウトのような「部分同期モデルへの前提の緩和」によって実用的な合意アルゴリズムが成立する理論的な余地を作っている。本ページが冒頭から記録してきた「安全性(いかなる状況でも決定は一致)」と「活性(過半数が稼働すれば前進)」という2性質のうち、FLPが制約するのは主に後者(終了性=活性)である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] §8.5) - **『詳説 データベース』は8章から14章までの5章(基礎・障害検出・リーダー選出・一貫性モデル・合意)を、合意アルゴリズムへ至る単一の入れ子構造として明示的に位置づける**: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]]冒頭は「基礎から始めて分散コンピューティングの問題を取りあげ、続いて障害モデルや障害検出機能、リーダーの選出に話題を広げ、一貫性モデルについても議論した。すべてをまとめ上げて、分散システム探求の頂点を目指す準備がついに整った。その頂点とは、分散合意である」と述べる。これは本ページが[[リーダー選出]]ページと共有してきた「リーダー選出と合意は等価な問題である」という宣言(『詳説 データベース』10章)を、章構成そのものの水準で裏づけるものであり、リーダー選出(10章)・障害検出(9章)は合意(14章)の部分問題として意図的に手前に配置されていることが明示的にわかる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] 冒頭) - **Paxosの5亜種は、クラシックPaxosのどの制約を緩めたかで整理でき、「万能な最適化」は存在しない**: 14章まとめ(§14.6)は、Multi-Paxos(提案フェーズの反復を回避)・Fast Paxos(ラウンドトリップ数を削減する代わりにクォーラムサイズを$f+1$から$2f+1$へ増加)・EPaxos(単一リーダーへの依存を依存関係ベースの順序付けで解消)・Flexible Paxos(クォーラムの過半数性を$Q_1+Q_2>N$へ一般化)という4つの発展形を、それぞれ異なる制約緩和として整理する。本ページが上で記録した「合意アルゴリズムの多くの顔は等価問題である」というDDIA由来の統一的視点と対照的に、14章の整理は「同じPaxosという骨格の中でどの制約をどう緩めるか」という実装レベルの選択肢の見取り図を与える。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.6) - **ZAB・Raft・PBFTはいずれも「エポック番号 + ハートビートベースの障害検出」という同じ骨格を持つが、ビザンチン障害の有無で必要なメッセージ数が桁違いに増える**: 本ページの比較表はZAB・Raft・Paxos・VRの実装レベルの差異(リーダーの強さ・メッセージ型数等)を記録してきたが、14章はこれに加えてPBFTという非ビザンチン前提を外したアルゴリズムを提示する。ZAB・Raftはいずれもリーダー/フォロワー間のハートビートで障害を検出し1ラウンドトリップ級のブロードキャストで合意するのに対し、PBFT はノード間の相互クロスバリデーションを要求し$N^2$のメッセージ数を要する。同じ「エポックで一意なリーダーを立てる」設計から出発しても、ビザンチン障害を許容するかどうかでメッセージ複雑性のオーダーが変わる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.2.2, §14.4, §14.5) ## 未解決の問い - Raft のリーダー選出集中度（すべてのログが必ずリーダーを通過）はスループット上限を決める。マルチリーダー合意（EPaxos・Atlas 等）はどの workload で優位か、Raft の単純性とどうトレードオフするか？ - ジョイントコンセンサスによるメンバーシップ変更は同時メンバーシップ変更を 1 件に制限する。大規模クラスタ（数千ノード）でのメンバーシップ変更嵐への対処は？ - Raft の正式証明は Log Completeness Property の機械的証明を含むが、型安全性不変条件は非機械検証。TLA+ 証明の完全機械検証を達成した実装は？ - Chubby のような「弱いリーダーシップ(Paxos)＋上位のマスタ選出」という 2 層構成は、Raft のような「強いリーダーシップを持つ単一アルゴリズム」構成と比べて、運用上の複雑さと障害時の挙動にどのような違いを生むか。 - コンセンサス問題の等価性(CAS・共有ログ・fetch-and-add・アトミックコミットメントが相互変換可能)は理論的に証明されているが、実装間の変換コスト(性能オーバーヘッド)は DDIA 2E 第10章でも定量化されていない。ある問題の解法を別の問題の解法に変換する実装は、ネイティブ実装と比べてどの程度の性能差を生むか。 - DDIA 第9章の「ノードは自身の判断を信用できない」という認識論的根拠と、第10章の「重複クォーラムの数学的安全性」という形式的根拠は、同じ過半数原則の異なる説明レイヤーである。両者を統一した「なぜ過半数か」の単一の証明構造として提示することは可能か。 - 「リーダー選出と合意は等価」という『詳説 データベース』10章の宣言と、DDIA 2E 第10章のコンセンサス等価問題群(CAS・共有ログ・fetch-and-add・アトミックコミットメント)を、単一の形式的枠組みで統合する証明は存在するか。単独のリーダー選出アルゴリズム(ブリー系等)が安全性を欠くのは、この等価性のどの部分(重複クォーラムの欠如)が壊れているためかを、より厳密に特定できないか。 ## 関連 - [[複製ステートマシン]] — 分散コンセンサスが解決する応用問題の枠組み - [[リーダー選出]] — Raft の第一サブ問題 - [[分散コンセンサス回避]] — 特定ユースケースでのコンセンサス不要設計 - [[分散トランザクション]] — コンセンサスが前提となる分散 ACID トランザクション - [[線形化可能性]] — コンセンサスがフォールトトレラントに実現する一貫性モデル - [[コーディネーションサービス]] — コンセンサスを少数固定ノードに外部化する実用パターン - [[Chubby]] — Paxos ベースのロックサービス・マスタ選出の実例 - [[部分故障]] / [[システムモデルと安全性・活性]] — DDIA 第9章のクォーラムの認識論的根拠 - [[障害検出器]] — 合意アルゴリズムが依拠する障害検出の理論的基盤 - [[FLPの不可能性]] — 非同期モデルでの有界時間内合意が原理的に不可能であることの証明 - [[ビザンチン障害]] — 非ビザンチン前提を外した場合に必要となるPBFT等のクロスバリデーション型合意 ## 出典 - [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]（Raft の設計目標・Paxos 問題点・Raft アルゴリズム詳細・ユーザースタディ） - [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]（コンセンサス回避設計との対比） - [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]]（Raft の実用例） - [[@2024__SIGMOD__Amazon MemoryDB - A Fast and Durable Memory-First Cloud Database]]（ログベースリーダー選出・Raft 類似設計） - [[@2016__OReilly__SRE Book - Chapter 2 The Production Environment at Google, from the Viewpoint of an SRE]]（Chubby のマスタ選出の実運用例） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]]（コンセンサスの形式的定義・等価問題群・エポック番号による2段階クォーラム投票の一般構造） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 9 The Trouble with Distributed Systems]]「The Majority Rules」「Knowledge, Truth, and Lies」（過半数クォーラムの認識論的根拠） - [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]]（§9.5「まとめ」: 障害検出機能と合意アルゴリズムの関係、Chandra-Toueg の結果） - [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]（§10.6「まとめ」: リーダー選出と合意の等価性、古典的アルゴリズムの安全性欠如） - [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]]（§8.5「FLP の不可能性」: 同意性・妥当性・終了性の定義、非同期モデルでの不可能性証明） - [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]]（冒頭: 章構成による入れ子構造の明示、§14.6: Paxos亜種5種の制約緩和の整理、§14.2.2/§14.4/§14.5: ZAB・Raft・PBFTのメッセージ複雑性比較）