分散合意アルゴリズム(Raft)

複数ノードからなる分散システムが、障害があっても単一の値や操作ログについて合意(consensus)を形成するためのアルゴリズム。

Raft

• Paxos の後継として、わかりやすさ(understandability)を最重視して設計された合意アルゴリズム。
• リーダー選出・ログ複製・安全性という分割されたサブ問題で構成され、リーダーがログエントリを follower に複製して過半数の合意でコミットする。
• Hyperledger Fabric(分散台帳)が順序付けサービスに採用している。

位置づけ

• ノード間の通信は operating-system-kernel のソケット/RPC を土台にする。
• レプリケーションの考え方はストレージ冗長化(RAID、operating-system-kernel)や、複製と耐障害性のトレードオフと通底する。

関連: _moc-systems

CRDT (Conflict-free Replicated Data Type)

複製してもコンフリクトしないデータ型。各レプリカが独立に更新しても、後でマージすると必ず同じ状態に収束する（強い結果整合性）。CAP定理のうち A（可用性）と P（分断耐性） を満たすため、ネットワーク分断下でも書き込み続行できる。

用途

• リアルタイム共同編集（複数クライアントが同時にテキスト編集）
• オフライン優先アプリの状態同期

合意アルゴリズムとの対比

強い一貫性 (C) が必要な場面では合意アルゴリズムを使う:

• Paxos — 分散合意アルゴリズム。正しく完璧に実装できる人がいないと言われるほど難解で、暗黙的な前提も多い。理解しやすさを狙った Raft が後継として広まった。

CRDT は「衝突を起こさせない」設計、Paxos/Raft は「単一の合意値を確定させる」設計、という補完関係にある。

関連: distributed-consensus-raft / database-transaction-theory / _moc-cs