Raft：理解しやすさを設計目標にした合意アルゴリズム

この論文が解いた問題

横にスクロール

分散システムでは、何台ものサーバーが協調しながらも、外からは一台のように振る舞わなければならない。そのために欠かせないのが合意（consensus）である。複数のサーバーが、記録すべき操作の並び（ログ）について同じ結論に達し、途中で一部が故障しても矛盾のない状態を保ち続ける——これが合意アルゴリズムの役割だ。分散データベースの複製、リーダー選出、ロックサービスなど、堅牢な分散システムの中心にはほぼ例外なく合意が座っている。合意は多くの場合、同じコマンド列を各サーバーの状態機械に同じ順で適用する「複製状態機械」という形で使われる。全サーバーが同一の入力列に合意できれば出力も一致し、一部が倒れても生き残りが同じ状態を再現できる。

長らくこの分野の事実上の標準は、Leslie Lamportが示したPaxosだった。Paxosは正しさが厳密に証明された偉大な成果である一方、「理解しがたい」という評判が絶えなかった。論文は難解で、標準的なPaxosは単一の値への合意しか語らず、実システムに必要な連続したログの合意（multi-Paxos）は論文の外の空白として残されている。この空白が実装ごとの解釈のばらつきと難しさをさらに増した。Ongaroらは、大学院の講義でPaxosを教える難しさを目の当たりにし、そもそも理解しにくいアルゴリズムは正しく実装することも、現場で運用することもできないと考えた。Paxos自体の解説はPaxos論文を参照してほしい。

そこで2014年、スタンフォードのDiego OngaroとJohn Ousterhoutは「In Search of an Understandable Consensus Algorithm」という論文でRaftを提案した。目を引くのは、性能でも新規性でもなく「理解しやすさ（understandability）」を第一の設計目標に掲げたことだ。彼らは設計上の選択肢を、どちらが学生に説明しやすいかという基準で選び、ユーザー調査で理解度を実際に測定してまで、その目標を追求した。その結果、同じ内容を学んだ被験者はPaxosよりRaftのほうを有意に正しく理解できたと報告され、彼らの主張は感覚論ではなく計測に裏づけられた。

核心アイデア

Raftが理解しやすさを実現した最大の工夫は、合意という一枚岩の難問を、独立した三つの部分問題に分解したことだ。すなわち、リーダー選出・ログ複製・安全性の三つである。順に見ていく。

一つ目のリーダー選出。Raftは強いリーダー制を採る。ある時点でリーダーは一台だけ存在し、すべてのログはリーダーからフォロワーへ一方向にのみ流れる。ここで鍵になるのが任期（term）だ。termは単調増加する整数で、論理時計として働く。各サーバーはリーダーからの定期的な通信（ハートビート）を待ち、一定の選挙タイムアウトの間それが届かなければ、自分のtermを一つ進めて候補者となり、他のサーバーに投票を求める。過半数の票を集めたサーバーが、そのtermのリーダーになる。タイムアウトをサーバーごとにランダムにずらすことで、複数の候補者が同時に立って票が割れる事態を避けている。それでも票が割れて誰も過半数に届かなければ、そのtermは指導者不在のまま終わり、各サーバーは新しいtermで選挙をやり直す。ランダム化のおかげで、やり直しは通常ごく短時間で収束する。

二つ目のログ複製。クライアントの要求を受けたリーダーは、それを新しいエントリとして自分のログに追記し、フォロワーへ配る。フォロワーは自分のログとリーダーの主張が食い違えば追記を拒み、リーダーは一つ前へ遡って送り直す。この整合性チェックの繰り返しで、フォロワーのログは最終的にリーダーのログへ収束する。あるエントリが過半数のサーバーに複製されると、リーダーはそれをコミット済みとみなし、状態機械に適用して結果をクライアントへ返す。過半数さえ揃えばよいので、少数のサーバーが遅延・故障しても全体は前進できる。たとえばサーバーが五台なら、三台に複製できた時点でコミットでき、残る二台がダウンしていても書き込みは受け付けられる。この多数決が可用性と一貫性を同時に成立させる肝である。

三つ目の安全性。ここがRaftの正しさを支える。単に多数決するだけでは、古いログしか持たないサーバーがリーダーになり、コミット済みのエントリを上書きしてしまう危険がある。Raftは選挙に制約を課し、投票する側は「自分より新しいログを持たない候補者」には票を投じない。結果として、コミット済みエントリをすべて含むサーバーだけがリーダーになれる。さらにリーダーは、過半数に届いていても過去のtermのエントリを単独ではコミット済みと宣言しない。自分のtermの新しいエントリがコミットされるのに便乗させることで、いったん見えたエントリが後から消える事故を防ぐ。ネットワークが分断された場合も、より新しいtermを掲げた側が最終的に勝ち、古いリーダーは復帰時に自分が少数派だったと悟ってフォロワーへ降りる。

PaxosとRaftの設計思想の違いは、次の対比に集約される。

言葉で追うだけでは、選挙タイムアウトやログの巻き戻りといった動きは掴みにくい。実際にサーバーを落とし、分断を起こし、リーダーが入れ替わる様子を手で動かせるRaft合意シミュレータを試すと、この三分割が体で理解できるはずだ。

その後の影響

Raftは、狙いどおり「理解しやすい合意」の代名詞になった。論文公開後まもなく多くの言語で実装が現れ、現代の分散システムの土台に広く採り入れられている。分散KVSのetcdはRaftでログを複製し、そのetcdはKubernetesがクラスタ状態を保存する心臓部として動いている。サービスディスカバリのConsul、分散ストレージのTiKV、分散SQLのCockroachDBなども、合意層にRaftまたはその変種を据える。性能面でもRaftはPaxos系に引けを取らず、理解しやすさと引き換えに実用性を犠牲にしていない点が採用を後押しした。論文がメンバーシップ変更やログ圧縮まで一つの完全なシステムとして提示したことも、実装者が迷わず作り切れる後押しになった。

教育面での影響も大きい。かつて「合意といえばPaxos、ただし難解」だった状況は、「まずRaftで直感を掴む」へと変わった。大学の講義や技術書、オンライン教材でRaftが標準的に取り上げられ、多くのエンジニアにとって合意アルゴリズムへの入口になっている。

まとめ

Raftは、合意という難問に「理解しやすさ」という新しい物差しを持ち込んだ論文だ。問題をリーダー選出・ログ複製・安全性に分け、強いリーダー制と任期という単純な道具立てで、Paxosと同じ安全性をより見通しよく実現した。その明快さがetcdをはじめとする実装の波を生み、いまや分散合意を学ぶ最初の一歩になっている。難しさを認めたうえで、それでも学べる形に翻訳したこと——Raftの功績はその一点に尽きる。ほかの重要論文は論文で辿る分散システムから辿れる。