合意アルゴリズム

合意アルゴリズムとは

合意アルゴリズム (Consensus Algorithm) は、分散システムで複数のノードが同じ値に合意するためのアルゴリズムである。ノードの障害やネットワーク分断が発生しても、システム全体として一貫した状態を維持する。

なぜ必要か

分散システムでは複数のノードがデータのコピーを保持するが、ノード障害やネットワーク分断が発生すると、各ノードが異なる値を持つ可能性がある。合意アルゴリズムにより、障害が発生しても過半数のノードが同じ値に合意でき、システム全体の一貫性を保てる。

ノード A: 「値は 42」
ノード B: 「値は 42」  ← 全ノードが同じ値に合意
ノード C: 「値は 42」

ノード B が障害で応答しない場合でも、A と C で合意を形成できるか？

主要なアルゴリズム

主要なアルゴリズムを以下にまとめる。

アルゴリズム	提唱者	特徴	採用例
Paxos	Leslie Lamport (1989)	理論的に正しいが実装が複雑	Google Chubby
Raft	Diego Ongaro (2014)	Paxos を理解しやすく再設計	etcd, Consul
PBFT	Castro & Liskov (1999)	ビザンチン障害に対応	ブロックチェーン

Raft の仕組み

Raft の仕組みを図で示す。

リーダー選出:
  [Follower A] [Follower B] [Follower C]
  → タイムアウト → A が Candidate に → 投票 → A が Leader に

ログレプリケーション:
  Client → Leader A → ログに追記 → Follower B, C にレプリケーション
                    → 過半数 (2/3) が確認 → コミット → Client に応答

Raft はリーダー選出 (Follower がタイムアウトすると Candidate になり投票を要求)、ログレプリケーション (Leader がログエントリを Follower に送信)、コミット (過半数が確認したらコミット) の 3 フェーズで動作する。

CAP 定理との関係

CAP 定理により、ネットワーク分断時に Consistency (全ノードが同じデータを返す) と Availability (全リクエストに応答する) を同時に満たすことはできない。Raft は CP (Consistency + Partition Tolerance) を選択する。

AWS での合意

DynamoDB は内部的に Paxos ベースのレプリケーション、Aurora はクォーラムベースの書き込み (6 コピー中 4 に書き込み)、EKS (etcd) は Raft、ElastiCache (Redis Cluster) は Gossip プロトコルを使用する。

詳しくは関連書籍を参照。