# 分散コンセンサス ## 定義 分散コンセンサス（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 のリーダー選出集中度（すべてのログが必ずリーダーを通過）はスループット上限を決める。マルチリーダー合意（EPaxos・Atlas 等）はどの workload で優位か、Raft の単純性とどうトレードオフするか？ - ジョイントコンセンサスによるメンバーシップ変更は同時メンバーシップ変更を 1 件に制限する。大規模クラスタ（数千ノード）でのメンバーシップ変更嵐への対処は？ - Raft の正式証明は Log Completeness Property の機械的証明を含むが、型安全性不変条件は非機械検証。TLA+ 証明の完全機械検証を達成した実装は？ ## 関連 - [[複製ステートマシン]] — 分散コンセンサスが解決する応用問題の枠組み - [[リーダー選出]] — Raft の第一サブ問題 - [[分散コンセンサス回避]] — 特定ユースケースでのコンセンサス不要設計 - [[分散トランザクション]] — コンセンサスが前提となる分散 ACID トランザクション ## 出典 - [[@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 類似設計）