Raft 合意アルゴリズムを図解：リーダー選出とログ複製

Kubernetes クラスターはどれも状態を etcd に保存し、etcd はその状態について Raft で合意します。Consul、CockroachDB、TiKV、RabbitMQ のクォーラムキューも同じで、Kafka 4.0 が ZooKeeper を廃止してからは Kafka 自身のコントローラーもそうです。これらのどれかを運用しているなら、Raft を知ると、ほかでは恣意的に見える挙動の理由がわかります。3 ノードのクラスターで 2 ノードが故障すると書き込みを受け付けなくなる理由、リーダー交代の間に書き込みが 1 秒止まる理由、そして 4 台目のノードがクラスターを安全にしないまま高くするだけの理由です。

この記事では、5 ノードのクラスターにおけるログ複製の図を使って Raft を解説します。ターム、リーダー選出、AppendEntries、コミット規則、障害、クラスターのサイズ設計、読み取り、メンバーシップ変更を扱います。

モデル：複製されたログ

Raft は複製ステートマシンを構築します。各サーバーはコマンドのログを持ちます。すべてのサーバーが同じコマンドを同じ順序で適用すれば、同じ状態に行き着きます。サーバーがクラッシュし、メッセージが失われたり遅れたりしても、ログを同一に保つことが Raft の仕事です。

各サーバーは、フォロワー、候補者、リーダーの 3 つの状態のいずれかにあります。時間は 1、2、3 と番号が振られたターム（term）に区切られ、各タームは選挙で始まり、リーダーは多くても 1 台です。自分より大きいタームを見たサーバーは自分のタームを更新してフォロワーになるため、古いリーダーは新しいリーダーからの連絡を受けた時点で退きます。

Raft に必要な RPC は 2 つだけで、ほかにスナップショット用が 1 つあります。

この設計は、Diego Ongaro と John Ousterhout が USENIX ATC 2014 で発表した論文 In Search of an Understandable Consensus Algorithm に由来します。

リーダー選出

フォロワーはリーダーから定期的にハートビートが届くことを期待しています。選挙タイムアウトの間に 1 つも届かなければ、リーダーがいなくなったとみなします。

1. タームを 1 つ増やして候補者になり、自分に投票します。
2. 他のすべてのサーバーに、最後のログエントリのインデックスとタームを付けて RequestVote を送ります。
3. 各サーバーが投じる票はタームごとに 1 票までで、投票先は自分と同じかそれ以上に新しいログを持つ候補者に限られます。最後のタームが大きいほうが勝ち、タームが同じなら長いログが勝ちます。
4. 過半数の票を集めた候補者がリーダーになり、ハートビートの送信を始めます。

2 人の候補者が票を分け合うと誰も勝てず、そのタームはリーダー不在のまま終わります。Raft はタイムアウトをランダム化することで、これをまれにしています。論文は 150〜300 ms のような値を提案しており、たいていは 1 台のサーバーが最初にタイムアウトし、ほかが動き出す前に勝ちます。

本番システムはネットワークに合わせてタイムアウトを選びます。etcd のデフォルトはハートビート 100 ms、選挙タイムアウト 1,000 msで、ドキュメントには選挙タイムアウトをメンバー間の往復時間の少なくとも 10 倍にすべきだと書かれています。Kubernetes のコントロールプレーンが etcd のリーダーを失ってから再び書き込みを受け付けるまでに 1 秒以上かかることがあるのは、これらの数値のためです。

ログ複製

選出されたリーダーは、すべての書き込みを処理します。

1. クライアントがリーダーにコマンドを送ります。たとえば SET x=5 です。
2. リーダーはそれを現在のタームを持つ新しいエントリとして自分のログに追加します。たとえばターム 3 のインデックス 7 です。
3. リーダーは各フォロワーに、新しいエントリと、その直前のエントリのインデックスとターム（インデックス 6、ターム 3）を付けて AppendEntries を送ります。
4. フォロワーは、自分のログのインデックス 6 にターム 3 のエントリがある場合にだけ受け入れます。この整合性チェックにより、2 つのログがある位置で一致していれば、それより前のすべてでも一致していることが保証されます。
5. リーダーを含む過半数のサーバーがエントリを保存すると、リーダーはそれをコミット済みとしてマークし、ステートマシンに適用してクライアントに応答します。
6. フォロワーは次の AppendEntries で新しいコミットインデックスを知り、同じくエントリを適用します。

ログが食い違っているためにフォロワーがエントリを拒否した場合、リーダーはログが一致するまで 1 インデックスずつ（最適化があればもっと速く）さかのぼり、フォロワーの競合するエントリを自分のエントリで上書きします。上書きされるのは未コミットのエントリだけです。それらが成功したとは誰にも伝えられていないので、これは安全です。

コミット規則と、微妙な点

「過半数が保存したらコミット」には 1 つ例外があり、これは論文で最も有名な詳細です。新しいリーダーは、以前のタームから残ったエントリをコミットするためにレプリカの数を数えてはいけません。それらは、自分のタームのエントリをその上にコミットすることで、間接的にコミットします。この規則がなければ、過半数に保存されたエントリでも、後のリーダーに上書きされるおそれがあります。実際には、新しいリーダーはタームの開始時に空の no-op エントリを追加し、それ以前のすべてを素早くコミットします。

選挙の制約が安全性の議論を完成させます。候補者には過半数の票が必要で、コミット済みのエントリはどれも過半数のサーバーにあるので、勝ちうる候補者はすべてのコミット済みエントリをすでに持っています。

クラスターが耐えられる障害

n 台のサーバーからなるクラスターは、リーダーを選び、書き込みをコミットするために過半数を必要とします。そのため、半数未満の障害に耐えられます。

4 台のサーバーが耐えられる障害は 3 台と同じく 1 台ですが、すべての書き込みが 2 つではなく 3 つの確認応答を待つことになります。クラスターのサイズが奇数なのはこのためです。1 台を計画メンテナンスしている間にもう 1 台の障害に耐えたいなら、5 台が一般的な選択です。

レイテンシも同じ計算に従います。すべての書き込みは、リーダーが最も速い過半数に届き、それらのサーバーがエントリをディスクに永続化するのを待ちます。3 つのリージョンにまたがるクラスターでは、どの書き込みにも、最も近い別のリージョンとの往復が少なくとも 1 回かかります。遅いディスクは遅いネットワークと同じくらい響きます。etcd のドキュメントがタイムアウトと同じくらい fsync のレイテンシに紙幅を割いているのはそのためです。

実際の障害

• リーダーがクラッシュする。 フォロワーがタイムアウトし、1 台が選挙に勝ち、書き込みが再開します。処理中だったリクエストはコミットされたかどうかわからないので、クライアントは再試行する必要があり、再試行するコマンドは冪等であるべきです。
• ネットワーク分断。 過半数がいる側がリーダーを選んで処理を続けます。少数側に残った古いリーダーは何もコミットできません。分断が解消すると、より大きいタームを見て退きます。
• 遅いフォロワー。 コミットはそのフォロワーを待ちません。大きく遅れた場合、リーダーはログ全体を再生する代わりにスナップショットを送ります。
• かく乱するサーバー。 リーダーから切り離されたサーバーはタイムアウトを繰り返してタームを上げ続け、復帰したときに不要な選挙を引き起こすことがあります。Ongaro の博士論文に由来する pre-vote を使うと、候補者はタームを増やす前に勝てるかどうかを確認できます。

読み取りはタダではない

リーダーは自分の状態から無条件に読み取りに答えることはできません。分断の向こう側で新しいリーダーが選ばれているかもしれず、その場合、古いリーダーは古いデータを返してしまいます。線形化可能な読み取りには、応答する前にリーダーであることを確かめるハートビートの 1 往復（Raft の ReadIndex）か、時間ベースのリーダーリースのどちらかが必要です。リースは時計のずれに上限があることを前提にしています。フォロワーも読み取りに応じられますが、リーダーのコミットインデックスを確認したあとか、古い結果を受け入れる場合に限られます。etcd はこれを明示しています。etcdctl get はデフォルトで線形化可能で、--consistency=s は、より速いものの古い可能性がある直列化可能な読み取りを要求します。

メンバーシップの変更

サーバーの追加や削除は過半数の意味を変え、構成を不用意に切り替えると、過半数が同時に 2 つできてしまうことがあります。Raft はこれを joint consensus か、サーバーを 1 台ずつ変更することで扱います。多くの実装では、etcd と同じように新しいサーバーを投票権のない learner として追加し、新しいノードが過半数に数えられる前にログに追いつけるようにしています。

ログ複製の図

図の読み方は次のとおりです。

• クライアントはコマンドを 1 つ、ターム 3 のリーダー S1 に送ります。リーダーはそれをインデックス 7 に書き込みます。
• 各表は 1 台のサーバーのログで、インデックス、ターム、コマンドを示します。表をまたいで一致する行は同じエントリです。
• AppendEntries のエッジはリーダーから 4 台のフォロワーに向かいます。S2 と S3 はインデックス 7 の確認応答を返します。
• S4 は遅れていてインデックス 6 にあり、S5 は到達不能でインデックス 5 にあります。どちらもコミットを妨げません。
• メモはコミット規則を示しています。5 台中 3 台のサーバーがエントリ 7 を保存しているので、エントリはコミット済みになり、クライアントは応答を受け取ります。

教えるための合意アルゴリズム図の描き方

• サーバーだけでなくログを描きます。 Raft の保証はログについての命題です。5 つの箱と矢印だけの図では、面白いところがすべて隠れてしまいます。
• すべてのエントリの横にタームを書きます。 タームは選挙、競合、コミット規則を説明します。
• 不健全なクラスターを描きます。 遅れているフォロワーや分断されたフォロワーは、完璧なクラスターよりも、過半数がなぜ重要かをよく示します。
• シナリオごとに 1 枚の図を使います。 選挙、通常の複製、フェイルオーバー後の競合修復は、それぞれ独立した図にする価値があります。

レプリケーションがデータベースアーキテクチャ全般にどう組み込まれるかは、データベースレプリケーション図を参照してください。Kubernetes アーキテクチャ図はコントロールプレーンのどこに etcd があるかを示し、Kafka アーキテクチャ図は KRaft コントローラーを扱っています。CockroachDB のようなシステムはデータの範囲ごとに 1 つの Raft グループを動かしており、これが合意をデータベースシャーディング図の考え方につなげます。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. クラスター用に基本パックの フレーム を追加し、現在のタームをラベルとして付けます。
3. その中に、サーバーごとに 1 つずつ、インデックス、ターム、コマンドの列を持つ基本パックの 表 ノードを 5 つ追加します。リーダーは中央に置きます。
4. フレームの外にクライアント用の基本パックの ボックス を追加し、コマンドを付けてリーダーにつなぎます。
5. リーダーから各フォロワーへ AppendEntries のエッジを引き、エントリを保存したフォロワーからは確認応答の破線エッジを戻します。到達不能なフォロワーは警告色の破線エッジで示します。
6. 基本パックの Markdown ブロックでコミット規則を書き、リーダーの横にコミットインデックスを記した メモ を追加します。

この例で使うダイアグラムノードは 8 個で、Free プランの範囲に収まります。

よくある質問

Raft クラスターのノード数が奇数なのはなぜですか？ クラスターが動くには過半数が必要です。3 ノードに 4 台目を加えると、耐えられる障害は増えないまま過半数が 2 から 3 に上がります。そのため、偶数のサイズは耐障害性を高めずにレイテンシとコストだけを増やします。

リーダー選出の間、書き込みはどうなりますか？ 新しいリーダーが選ばれるまで、書き込みは待たされるか失敗します。通常は選挙タイムアウト 1〜2 回分のうちに選ばれます。タイムアウトした書き込みがコミットされている可能性もあるので、クライアントは冪等なリクエストで再試行するべきです。

Raft と Paxos の違いは何ですか？ どちらも同じ問題を、同じような保証で解決します。Raft は理解しやすく実装しやすいように設計されました。強いリーダーを使い、選挙と複製を分離し、メンバーシップ変更を規定しています。

Raft ではフォロワーが読み取りに応じられますか？ はい。先にリーダーのコミットインデックスを確認するか、アプリケーションが古い可能性のあるデータを受け入れるなら可能です。確認せずにフォロワーのローカル状態を読むと、古い値が返ることがあります。

Raft は悪意のあるノードから守ってくれますか？ いいえ。Raft はクラッシュ、再起動、失われたり遅れたりするメッセージには耐えますが、サーバーがプロトコルに従うことを前提にしています。ビザンチン障害耐性には、別のアルゴリズムとより多くのレプリカが必要です。

無料で始める — 1 シート、クレジットカード不要。