分散合意アルゴリズムの仕組み ― 複数サーバーが「1つの答え」に合意する方法

たとえば3台のサーバーでデータベースを動かしてるとき、「この値は42です」って全員が同じ答えを持つ必要があるよね。1台が故障しても残りで正しい値を決められる仕組み、それが分散合意アルゴリズムだよ。

いい質問だね。実はネットワーク遅延やノードの突然のクラッシュがあると、単純な多数決では壊れるんだ。たとえば5台中3台が「値はA」と言ったけど、残り2台はネットワーク分断で別の「値はB」を受け取ってた、なんてことが起きる。これがスプリットブレインと呼ばれる問題で、分散システム最大の難関の一つだよ。

そうだね。Paxosは1989年にLeslie Lamportが考案した古典的なアルゴリズムだよ。提案者（Proposer）が値を提案して、受理者（Acceptor）が過半数で受け入れたら合意成立、学習者（Learner）がその結果を受け取る、という3つの役割で動く。理論的には完璧なんだけど、論文が難解すぎて実装者泣かせとして有名なんだ。

実装できる人はいるけど、バグが混入しやすいんだよね。そこで2014年にDiego OngaroとJohn Ousterhoutが「理解しやすさ」を最優先に設計したのがRaftだよ。Raftはリーダー選出・ログ複製・安全性という3つの部分に明確に分かれていて、各フェーズが独立して理解できるのが強みだね。

Raftでは「ターム（任期）」という概念があって、リーダーは定期的にハートビートを送るんだ。フォロワーが一定時間（選挙タイムアウト）ハートビートを受け取れないと、「リーダーが落ちた！」と判断して自分が候補者になり、他のノードにRequestVote RPCを送る。過半数の票を得たら新リーダーだよ。

それがスプリットボート（票の分裂）だね。たとえば5台中2台が同時に立候補すると、どちらも過半数を取れない場合がある。そのときはタイムアウトをランダムにずらして再選挙するんだ。ランダム化のおかげで、次の選挙ではどちらかが先に過半数を取れる確率が高くなるよ。

リーダーがクライアントからの書き込みを受け取ると、自分のログに追記して、全フォロワーにAppendEntries RPCで送る。過半数のフォロワーが「書き込みました」と返事したら、そのエントリは「コミット済み」になるんだ。過半数でOKだから、少数のノードが落ちてもシステムは止まらないよ。

めちゃくちゃ多いよ。Kubernetesの心臓部であるetcdはRaftで動いてるし、KafkaのメタデータはZooKeeper（ZABプロトコル、Paxos系）が管理してる。HashiCorpのConsulもRaftでサービスディスカバリの一貫性を保ってるし、CockroachDBは分散SQLの一貫性にRaftを使ってるんだ。

実はそう簡単じゃないんだ。CAP定理って知ってる？ ネットワーク分断（Partition）が起きたとき、一貫性（Consistency）と可用性（Availability）を同時に満たせないという定理だよ。合意アルゴリズムはCを選ぶから、分断中は書き込みを受け付けられなくなる。つまり可用性を犠牲にしてるんだね。

鋭いね。PaxosやRaftは参加者が信頼できる前提（クラッシュ故障モデル）だけど、ブロックチェーンは悪意あるノードがいても動く必要がある。これをビザンチン障害耐性（BFT）と呼ぶんだ。さらに面白いのがFLP不可能性定理で、「非同期システムでは1台でもクラッシュする可能性があると、決定的な合意は理論上不可能」と証明されてる。Raftはランダムなタイムアウトで確率的にこの壁を回避してるんだよ。