合意アルゴリズムの系譜

データベースのレプリケーション、マイクロサービス間のトランザクション、ブロックチェーンの台帳管理では、複数のノードが1つの値に合意しなければならない。これが合意（Consensus）問題だ。

Paxos は 2PC と違って単一障害点を持たず、Raft は Paxos と同じ安全性のまま理解しやすさを設計目標にした。PBFT は、嘘のメッセージを送るノードがいても実用的な性能で合意できることを示した。耐える障害が強くなるほど、必要なノード数とメッセージ量は増える。この記事では、各方式がなぜその手順で安全に合意できるのかを説明する。Paxos、Raft、PBFT にはシミュレーターを付けたので、メッセージの流れを1ステップずつ追える。

動画で読む4:31合成音声ナレーション・字幕付き

文字起こしを表示

複数のノードが、ひとつの値に合意する。分散システムでは、この合意問題を避けて通れません。2PCからPaxos、Raft、そしてPBFTへ。合意アルゴリズムが、何を解決するために進化してきたのかを追います。

まずは障害モデルです。クラッシュ障害では、ノードは止まるだけで、嘘はつきません。ビザンチン障害では、嘘のメッセージを送る、改ざんする、無視する。ノードは何をしてもおかしくありません。f台の障害に耐えるには、クラッシュ障害なら2f+1台、ビザンチン障害なら3f+1台が必要です。

1985年のFLP不可能性定理によれば、1台でも止まり得る非同期システムで、安全性・活性・障害耐性を同時に満たす決定性アルゴリズムは作れません。そこで実用的なアルゴリズムは、タイムアウトなどを使い、安全性は常に守り、活性はネットワークが安定すれば保証する、という戦略をとります。

最もシンプルなのが2フェーズコミット、2PCです。コーディネーターが全員にPrepareを送り、全員がYesならCommitします。しかし投票後にコーディネーターがクラッシュすると、Yesと答えた参加者は、その復旧まで、コミットかアボートかの指示を待つしかありません。勝手にタイムアウトすれば、他の参加者と食い違うかもしれません。2PCの障害耐性は、事実上ゼロなのです。

この問題に、過半数という考え方で答えたのが、1989年にランポートが提案したPaxosです。フェーズ1では、Proposerが番号nを付けたPrepareを送り、Acceptorの過半数からPromiseを集めます。フェーズ2でAcceptを送り、過半数が受理すれば、その値で合意が成立します。過半数どうしは必ず重なり、ProposerはPromiseで知った受理済みの値のうち番号最大のものを引き継ぐため、選ばれた値は上書きされません。ただしPaxosは難解で、ログ複製への拡張も自明ではなく、Proposer同士が競合すると、いつまでも決まらないこともあります。

2014年のRaftは、理解しやすさを設計目標にしました。合意を、リーダー選出、ログ複製、安全性に分解します。選挙タイムアウトが切れたノードは、タームを1つ進めて候補者になり、過半数の票を得ればリーダーになります。書き込みはすべてリーダーからAppendEntriesで複製され、現在のタームのエントリは、過半数に届いた時点でコミットされます。さらに、自分以上に新しいログを持つ候補者にしか投票しないので、コミット済みのエントリは、以降のどのリーダーにも必ず残ります。

ノードが嘘をつく環境に、実用的な答えを示したのが、1999年のPBFTです。プライマリが順番を割り当て、PrepareとCommitの2回の全対全通信で、それぞれ2f+1個の一致を集めます。n = 3f+1 なら、2f+1台のクォーラムはどの2つも少なくとも f+1 台で重なり、その中に必ず正直なノードが含まれます。代償は、ノード数の2乗で増えるメッセージです。実用的には、数十ノード程度が限界とされます。

実世界では、GoogleのChubbyやSpannerがPaxosを、etcdやCockroachDB、TiKVがRaftを使っています。ビザンチン耐性の合意は、Hyperledger FabricやTendermintなど、ブロックチェーンの世界で生きています。

振り返ると、耐えるべき障害が強くなるほど、必要なノード数とメッセージ量が増えていきます。Paxosの難解さがRaftを生んだように、理解しやすさも重要な設計指標です。そして、安全性は常に守り、活性はネットワークが安定すれば保証する。これが、現代の合意アルゴリズムに共通する戦略です。

記事では、Paxos、Raft、PBFTの動きを、シミュレーターで一歩ずつ確かめられます。

1978年の 2PC に始まり、1982年にビザンチン将軍問題が定式化され、その後 Paxos、PBFT、Raft が登場した。年表の破線より右の Paxos、PBFT、Raft は障害が起きても合意を続けられるアルゴリズムで、Paxos と Raft はクラッシュ障害に、PBFT はビザンチン障害に耐える。

障害モデル — クラッシュ障害 vs ビザンチン障害

どの合意アルゴリズムも、ノードがどう壊れるかという障害モデルを前提にしている。

クラッシュ障害（Crash Fault）: ノードが突然停止し、以降は応答しない。停止するまでは正しく動作し、嘘のメッセージは送らない。
ビザンチン障害（Byzantine Fault）: ノードが任意の動作をする。嘘のメッセージを送る、メッセージを改ざんする、無視するといった振る舞いをすべて含む。

クラッシュ障害はビザンチン障害の特殊ケースなので、ビザンチン障害に耐えるアルゴリズムはクラッシュ障害にも耐える。その代わり、必要なノード数とメッセージ量が増える。

障害モデル	必要ノード数	ノードの振る舞い
クラッシュ障害	2f + 1（f 台の障害に耐える）	停止するだけ、嘘はつかない
ビザンチン障害	3f + 1（f 台の障害に耐える）	任意の不正動作が可能

FLP 不可能性定理 — 非同期モデルでの合意の限界

1985年、Fischer, Lynch, Paterson は次の定理を証明した。

FLP 不可能性定理: 非同期モデルにおいて、1台でもクラッシュする可能性があるなら、安全性（Safety）・活性（Liveness）・障害耐性（Fault Tolerance）の3つを同時に保証する決定性アルゴリズムは存在しない。

実用的なアルゴリズムは、この定理の前提のどれかを緩めて合意を実現している。

ランダム化: Proposer の選出にランダム性を導入し、活性を確率的に保証する
部分同期モデル: ある時点（GST: Global Stabilization Time）以降はメッセージが一定時間内に届くと仮定する
障害検知器: タイムアウトによる不完全な障害検知を使う

Paxos と Raft は安全性を常に保証し、活性はネットワークが十分な時間安定すれば保証する。

2PC — 最もシンプルな合意

Two-Phase Commit（2PC）は分散トランザクションの基本プロトコルだ。Coordinator が全参加者から Prepare → Commit の2フェーズで合意を取る。

2PC の問題点

2PC は単純だが、Coordinator 1台に依存するため次の弱点がある。

ブロッキング: Coordinator がクラッシュすると、Vote Yes を返した参加者は Commit/Abort の指示をいつまでも待ち続ける。タイムアウトして独自に Abort すると、ほかの参加者と結果が食い違うおそれがある。
障害耐性ゼロ（f=0）: Coordinator が1台クラッシュするだけで全体が止まる。Coordinator が単一障害点（Single Point of Failure）になっている。

Paxos は Acceptor の過半数が動いていれば合意できるので、少数の Acceptor が停止しても処理を続けられる。

Paxos — 「合意」の理論的基盤

Leslie Lamport が1989年に提案した Paxos は、クラッシュ障害に耐える合意アルゴリズムの理論的な土台になった。Google の Chubby ロックサービスや Spanner で使われている。

Paxos の3つの役割

Proposer: 値を提案する。提案には一意の proposal number が付く。
Acceptor: 提案を受理するか判断する。過半数が同じ値を受理すれば合意成立。
Learner: 合意された値を受け取り、State Machine に適用する。以下では Proposer と Acceptor のやり取りを中心に扱う。

Single-Decree Paxos のプロトコル

Paxos は2フェーズで動作する。フェーズの数は 2PC と同じだが、全員ではなく過半数の応答で次へ進む。

Phase 1 — Prepare/Promise:

Proposer が proposal number n を選び、全 Acceptor に Prepare(n) を送信する
Acceptor は n が今まで見た最大なら Promise(n, 過去に受理した値) を返す

Phase 2 — Accept/Accepted:

Proposer は過半数の Promise を受信後、Accept(n, v) を送信する
- Promise に過去の受理値があれば、最大の proposal number に対応する値を選ぶ
- なければ自分の値を提案する
Acceptor は n より大きい Promise をしていなければ Accepted(n, v) を返す

Paxos シミュレーター

Single-Decree Paxos をシナリオごとにステップ実行する。

シナリオ:

PreparePromiseAcceptAccepted

初期状態: N1 が Proposer、N2〜N5 が Acceptor。N1 が proposal number n=1 で合意を始める。

[1] N1 が Proposer として合意プロセスを開始

ステップ 1 / 51 / 5

なぜ Paxos は安全なのか

Paxos の安全性は proposal number による順序付けに基づく。

Acceptor は、Promise した最大の proposal number より小さい number の Accept を拒否する
Proposer は、Promise に含まれる過去の受理値を引き継ぐ

この2つの制約により、ある値を過半数が受理すると、以降のどの proposal もその値を上書きできない。これが Paxos の安全性定理だ。

Paxos の課題

Paxos は正しいが、理解と実装が難しい。

理解困難: Lamport の最初の論文 "The Part-Time Parliament" は古代ギリシャの議会にたとえた独特の文体で書かれ、多くの研究者が理解に苦労した。Lamport は後に "Paxos Made Simple" で説明し直した。
Multi-Paxos への拡張が自明でない: Single-Decree Paxos が決めるのは1つの値だけだ。実用的なログ複製（Multi-Paxos）への拡張方法は論文に明記されておらず、各実装が独自に最適化した。
活性の問題（Livelock）: 2つの Proposer が交互により大きな proposal number を出し合うと、いつまでも合意できない（シミュレーターの「Proposer 競合」シナリオでは、大きな proposal number の Prepare が先行する提案を退ける1回分を追える）。

Raft — 理解しやすさのための再設計

Diego Ongaro と John Ousterhout が2014年に発表した Raft は、Paxos と同等の安全性を保ちながら、はるかに理解しやすくすることを設計目標にした合意アルゴリズムだ。

Raft の設計方針

Raft は理解しやすさのために、次の2つの方針を取った。

問題の分解: 合意問題を Leader 選出、ログ複製、安全性の3つに分けて扱う。
Strong Leader: すべての書き込みが Leader を経由し、ログは Leader から Follower へ一方向に複製される。

Raft の状態遷移

各ノードは Follower、Candidate、Leader の3状態を持つ。

Leader 選出

全ノードが Follower として起動
election timeout が切れたノードが Candidate に遷移し、term をインクリメント
自分自身に投票し、他のノードに RequestVote RPC を送信
過半数の票を得たら Leader に就任
Leader は定期的に heartbeat（空の AppendEntries）を送信して election timeout をリセット

Election Restriction: ノードは、Candidate のログが自分のログと同じかそれより新しい場合にだけ投票する（まず最後のログエントリーの term を比べ、同じなら index を比べる）。この制約と次に説明するコミット規則により、コミット済みエントリーを欠いたノードは後の term で Leader になれない。

ログ複製

Leader がクライアントからの書き込みをログに追記
AppendEntries RPC で全 Follower にログエントリーを送信
Leader の現在 term のエントリーは、過半数が応答した時点でコミット（State Machine に適用）

Leader は過去 term のエントリーを、複製できたレプリカの数だけを根拠にコミットしてはならない。過去 term のエントリーは、Leader が現在 term のエントリーを少なくとも1つ過半数に複製してコミットしたときに、間接的にコミット済みになる。

ログの一貫性は AppendEntries の prevLogIndex / prevLogTerm 検査で保たれる（Log Matching）。2つのログが同じ index・term のエントリーを含むなら、それより前のエントリーもすべて同一になる。

これらの規則で守られるのが Leader Completeness Property だ。コミットされたエントリーは、以降のすべての Leader のログに必ず含まれる。

メンバーシップ変更では、旧構成と新構成で別々の Leader が選ばれないよう、両構成の過半数が重なるようにする。論文は joint consensus を使い、実装によっては後に提案された one-server-at-a-time 方式を使う。

Raft シミュレーター

Raft の Leader 選出・ログ複製・障害耐性をステップ実行で可視化する。

シナリオ:

複製ログ

空

RequestVoteVote / OKAppendEntries

初期状態: 全ノードが Follower で term=0。Leader はまだいない。各ノードは election timeout を持ち、それが切れると Candidate に遷移する。

[1] 全ノードが Follower として起動

ステップ 1 / 51 / 5

Raft vs Paxos

観点	Paxos	Raft
Leader の扱い	Leader は最適化	Leader は必須
ログの流れ	任意の Proposer → Acceptor	Leader → Follower（一方向）
理解のしやすさ	難解	設計目標として重視
安全性の証明	同等	同等
採用例	Chubby, Spanner	etcd, CockroachDB, TiKV

PBFT — ビザンチン障害への耐性

Paxos と Raft が扱うのはクラッシュ障害だけだ。ノードが嘘のメッセージを送りうる環境では、ビザンチン障害に耐えるプロトコルが必要になる。

1999年に Miguel Castro と Barbara Liskov が提案した PBFT（Practical Byzantine Fault Tolerance）は、ビザンチン障害に耐える合意を実用的な性能で動かせることを示したアルゴリズムだ。

PBFT のプロトコル

PBFT は3フェーズで動作する。

Pre-prepare: Primary（リーダーに相当）がリクエストにシーケンス番号を割り当て、他の全ノードに送信
Prepare: Pre-Prepare を受け取った各バックアップ（Primary 以外のノード）が、他の全ノードに Prepare メッセージを送信（全対全通信）
Commit: Primary を含む各ノードは、Pre-Prepare と、それに一致する Prepare を $2f$ 個（合わせて $2f+1$ 個）そろえると、他の全ノードに Commit メッセージを送信

Prepare フェーズ（Pre-Prepare を含む）と Commit フェーズでは、それぞれ一致するメッセージを $2f+1$ 個集める。 $n = 3f + 1$ なら任意の2つのクォーラムは少なくとも $f+1$ 台で重なるので、 $f$ 台がビザンチンでも、重なりには正しいノードが少なくとも1台含まれる。

なぜ 3f+1 が必要なのか

$n$ 台中 $f$ 台がビザンチンのとき、正直なノードは $n - f$ 台だ。ビザンチンなノードが応答しなくても先へ進むには、正直なノードだけで $2f+1$ 個のメッセージを集められなければならない。

$n - f \geq 2f + 1 \implies n \geq 3f + 1$

4ノードなら $f=1$ 、7ノードなら $f=2$ のビザンチン障害に耐えられる。

PBFT シミュレーター

PBFT の3フェーズを、ビザンチンノードが0台・1台・2台の場合についてステップ実行する。

シナリオ:

Pre-preparePrepareCommit不正メッセージ

PBFT 正常系: 4ノード（n=3f+1, f=1）。N0 が Primary、N1〜N3 が Backup（Primary 以外のノード）。クライアントからリクエストが届く。

[1] 4ノード PBFT (f=1): 1台までのビザンチン障害に耐える

ステップ 1 / 41 / 4

PBFT の課題

$O(n^2)$ のメッセージ量: 全対全通信のため、メッセージ量はノード数の2乗で増える
スケーラビリティー: 実用上は数十ノード程度が限界
View Change の複雑さ: 不正な Primary を切り替えるプロトコルが複雑

アルゴリズム比較

アルゴリズム	障害モデル	障害耐性	メッセージ量	レイテンシー（コミットまでの通信ステップ数）	用途
2PC	クラッシュ	0	O(n)	2（Prepare → Vote）	データベース
Paxos	クラッシュ	f < n/2	O(n)	4（Prepare → Promise → Accept → Accepted）。Leader が安定した Multi-Paxos では Phase 2 だけを実行するので2	Chubby, Spanner
Raft	クラッシュ	f < n/2	O(n)	2（AppendEntries → 応答）	etcd, CockroachDB
PBFT	ビザンチン	f < n/3	O(n²)	3（Pre-prepare → Prepare → Commit）	ブロックチェーン

1ステップは片道のメッセージ1回分の遅延で、並行して送るメッセージはまとめて1ステップと数えます。障害がない場合に、Coordinator（2PC）・Proposer（Paxos）・Leader（Raft）・Primary（PBFT）が最初のメッセージを送ってから、そのノードがコミットの確定を知るまでを数えます。クライアントとのやり取りは含めず、Raft と PBFT は Leader・Primary が選出済みの状態を仮定しています。

実世界での採用

Paxos 系

Google Chubby: 分散ロックサービス。Multi-Paxos を使用。
Google Spanner: グローバル分散データベース。Paxos でレプリケーション。
Apache ZooKeeper: Zab プロトコル（Paxos の変種）を使用。

Raft 系

etcd: Kubernetes のバックエンドストア。Raft で一貫性を保証。
CockroachDB: 分散 SQL データベース。各 Range が Raft グループ。
TiKV: 分散 KV ストア（TiDB のストレージ層）。Raft を使用。
Consul: サービスメッシュのコントロールプレーン。Raft で合意。

PBFT 系

Hyperledger Fabric: 企業向けブロックチェーン。v0.6 までは PBFT で合意していた。v1.0 からはクラッシュ障害に耐える Kafka ベースのオーダリングサービスに移り、v1.4.1 で Raft が加わった。v3.0 では Raft に加えて、BFT-SMaRt に基づく SmartBFT ライブラリーを使った BFT のオーダリングサービスも選べる。
Tendermint: ブロックチェーン合意エンジン。PBFT の変種。

まとめ

2PC から PBFT までをたどると、耐える障害が強くなるほど必要なノード数とメッセージ量が増えることが分かる。クラッシュ障害なら $2f+1$ 台で済むが、ビザンチン障害では $3f+1$ 台と全対全通信が必要になる。

Raft は、Paxos が難解だったことを受けて、同じ安全性を保ちながら理解と実装のしやすさを設計目標にした。現在は etcd、CockroachDB、TiKV などで使われている。

FLP 不可能性定理は、非同期モデルでは安全性・活性・障害耐性を同時に保証する決定性アルゴリズムが存在しないことを示した。実用システムはタイムアウトやランダム化でこの制約を回避しており、Paxos、Raft、PBFT はいずれも安全性を常に守り、活性はネットワークが十分な時間安定したときに保証する。

参考文献

Lamport, L. "The Part-Time Parliament". ACM TOCS, 1998.
Lamport, L. "Paxos Made Simple". 2001.
Ongaro, D. and Ousterhout, J. "In Search of an Understandable Consensus Algorithm". USENIX ATC, 2014.
Castro, M. and Liskov, B. "Practical Byzantine Fault Tolerance". OSDI, 1999.
Fischer, M., Lynch, N., and Paterson, M. "Impossibility of Distributed Consensus with One Faulty Process". JACM, 1985.
Lamport, L., Shostak, R., and Pease, M. "The Byzantine Generals Problem". ACM TOPLAS, 1982.