概要

Raft は安全な State Machine Replication (SMR) による分散合意を実装するためのアルゴリズム。分散システムにおいて一貫性 (分散トランザクション) と可用性 (障害耐性) を実装するための基本的な部品として使用することができる。

TL;DR

一貫性のあるレプリケーションや分散実行を行うことができる。
合意に達したデータが破壊されるシナリオが存在しない。
- 長期間の停止や大幅に遅延したノードが Raft クラスタに復帰しても問題ない。
- ノード故障によるリーダー交代が発生しても問題ない。
役割分担もアルゴリズムも構成も簡単 (simplicity) で簡単 (easiness)。
- ノードの役割はリーダー、フォロワー、候補者の 3 つだけ。
- データの流れはリーダー → フォロワー方向だけ。
- SMR の機構を理解するための最小限の範囲はリーダー選挙とログ複製の 2 点のみ。
- この記事ではその 2 つを説明。より実用的な実装にはさらに以下の考慮が必要だが分散合意とはあまり関係ないのでこの記事では省略。
  - スナップショット (ログコンパクション)
  - ノードの追加/削除 (メンバーシップ変更)

前書き

「Raft の名前を知っている、仕組みに興味がある」から「英語の論文を読み解くのは時間コストが…」までの間で悶々としている人向けの記事です。パワー系プログラマであれば少し論文から補足すれば「俺が想像する Raft」の実装はできると思います。

この記事は私が Raft の論文 In Search of an Understandable Consensus Algorithm (Extended Version) を読み、自分の言葉で説明することで理解を進めることを目的としています。また論文にかかれていない考察なども散文的に記述しています。The Raft Consensus Algorithm や Raft - Understandable Distributed Consensus のアニメーション説明と併せて読むと理解の助けになると思います。

元々、HyperLedger Fabric というプライベートブロックチェーンが Raft で合意形成するという話を聞いて「Raft って Byzantine 耐性はないよね?」と論文を読み始めたことがきっかけなのでブロックチェーンの視点を交えています。

State Machine Replication

可用性 (Availability) のある分散システムでは複数のノードがデータのコピーを持ち合うことであるノードが故障したとしても残ったノードでサービスを継続できるように設計します。State Machine Replication (SMR) はそのようなシステムで複数のマシンにデータの複製を作るレプリケーション手法の一つです。可用性ありきの分散システム設計ではまず SMR のようなレプリケーション機構があり、一貫性 (Consistency) に振るのであればトランザクション (強い整合性) を導入し、分断耐性 (Partition Tolerance) に振るのであれば結果整合性を導入します。

Raft は強い整合性を持つ SMR に基づくアーキテクチャです。強い整合性の SMR は同じ初期状態から開始した複数の有限状態機械 (FSM) に同じコマンドを同じ順序で適用することで全てのマシンを同じ状態で遷移させます。Raft ではこのマルチキャストされるコマンドのことをログと読んでいます。

ここで重要になるのが、どのようにしてログの適用順序を決定するかです。非同期ネットワークでは、複数のマシンが同時にログを送信したとき、ネットワーク上でのログの伝播速度によって各 FSM への到着順序は容易に入れ替わります。もし FSM ごとにログの適用順序が異なると、それらの FSM は互いに異なる状態を持ってしまうため強い一貫性が保証できなくなります。Raft ではすべてのログは リーダー と呼ばれる 1 つの FSM に送信され、そのリーダーがログの順序を決定します。

もう一つの重要なことは、すべてのログの適用結果が決定的でなければならないという点です。ノードごとに異なるローカル時刻や OS またはライブラリ依存の動作などはノード間の状態矛盾を引き起こすため使用することはできません。またディスク不足のような実行環境固有の失敗が起きたノードは状態矛盾が発生している可能性があるため意図的にクラスタから離脱させる必要があるかもしれません。

可用性と分断耐性にノードの自立性を加えた設計は非構造型 P2P ネットワークの基盤として利用されています。Bitcoin を始めとするブロックチェーンの実装はトランザクションと呼ばれる不可分取引情報を改ざん不能な鎖状に連結して P2P ネットワークで共有し、それをすべてのノードで同じ順序で適用することで同じ状態を共有できるようにしています。これはまさに SMR と同じ考え方に基づいています。ただし、そのための Proof of Work のような初期の機構はリーダー選出が確定的ではなく、そのため有限時間内に 100% の一貫性を保証することができないという (結果整合性よりさらに緩い確率的整合性とも言うべき) 結果をもたらしています。

障害モデル

Raft の設計は Crash-Recovery 耐性を持ちます。Crash-Recovery とは長時間の停止または大幅に遅延していたノードがクラスタに復帰する状況です。非同期の分散システムでは故障と遅延の区別がつかないことから、Crash-Recovery 耐性は Performance/Timing 耐性、Omission 耐性、Crash-Stop 耐性があることも意味します。

Failure	Raft
Crash-Stop 突然ネットワーク上から消失し二度と復帰しない。	✔
Omission 偶発的なメッセージのロスト。	✔
Performance, Timing 許容時間 $t$ 内での応答の遅れ。	✔
Crash-Recovery 状態遷移シーケンス上の過去の任意の位置からの復帰。	✔
Byzantine, Arbitrary 状態遷移シーケンスから逸脱。任意のタイミングで任意のメッセージ。悪意的行動。

Raft は Byzantine 障害に対する耐性がなく、論文を一見して恒久的なリーダーの乗っ取りからのログの改ざん、リーダー選挙の妨害などが可能であるところを見ても、P2P ではなく完全に管理されたネットワーク向けの合意アルゴリズムです。Byzantine 耐性が必要であれば Raft の代わりにパフォーマンスを犠牲にして pBFT などを使う必要があるでしょう。

論文では Crash-Recovery より深刻な障害耐性には言及していないが (論説の範囲を外れるため当然だが)、もし実際に Raft を実装するなら現実的に想定される障害に対して工夫できる余地もいくつか存在します。例えば「テスト環境で使用していたノードの 1 つが事故で本番クラスタに『も』参加してしまった」といったような運用事故で起きうる障害は (大抵そのようなケースは任意障害の一ケースに分類される挙動を起こす) クラスタ識別子の導入などで回避できるでしょう。

基本的な構成

Raft は定足数 (quorum; Raft では過半数と同義) に基づくアルゴリズムのため実働想定のノード数は奇数構成が推奨されています。これは偶数にしても故障個所と定足数が増えるだけで障害許容ノード数は変わらず障害耐性が下がるためです。一般的に一貫性を提供する分散システムはノード間の通信頻度が非常に高く、特にリーダーが強い役割を持つ Raft ではノード数が増えればリーダーの負荷も大きくなります。このような強い一貫性型の分散システムでは、単独の合意クラスタとして 3、5、多くても 7 ノードが一般的と思います (論文では 5 ノードが最適としている)。それ以上は一貫性を緩和して複数のクラスタ間で協調するような設計が必要となります。

Raft の合意クラスタは選挙によって選ばれた 1 つのリーダーとリーダー以外のフォロワーによって構成されています。これにリーダー選挙時の候補者を加えて、すべてのサーバはこれら 3 つの役割のうちの 1 つの役割が必ず割り当てられています。なお Raft の合意クラスタの初期状態は全てのサーバがフォロワーであり「リーダー選挙待ち」から開始します。

Raft の主要な動作はリーダー選挙とログ複製の 2 つだけです。それぞれに対応する、実装者が用意すべき API は RequestVote RPC と AppendEntries RPC の 2 つです。

論文では Joint Consensus なる方法で新しいノードの追加や離脱 (メンバーシップ変更) のアルゴリズムを紹介していましたが、一見してリーダーが正しく機能している前提 -- つまり定足数以上のノードが故障している状態では機能しない前提があるようで (そりゃ当然か?)、メンバーシップの変更には別に良いアプローチがあるように思えたことから、この記事ではメンバーシップ変更についての説明は行っていません。興味がある人は論文の６章を参照してください。

また論文では全てのログをそのまま保持するのではなく、ログを適用した状態のスナップショットを作成することでデータ容量を削減する「ログコンパクション」も提案していますが、トピックとしては分散合意とは性質が異なるためこの記事では扱っていません。

死活監視

死活監視はリーダー役が機能していることを確認する動作です。合意クラスタ内のフォロワーはリーダーが機能していないことを検知すると速やかにリーダー選挙を開始します。

Raft ではリーダーから全てのフォロワーに対して定期的に Heartbeat を送信することでリーダーが故障していないことを知らせています。

Heartbeat の実体は、リーダーからフォロワーに向けてログ複製のための AppendEntries RPC を複製ログ 0 件で呼び出しているだけです。AppendEntries RPC には選挙やログの世代がどこまで進んでいるかの情報も含まれていることから、長期間停止していたフォロワーが突然復帰したとしても、AppendEntries RPC のやりとりがあった時点で自分の状態が古くなっていることを認識することができます。

フォロワーはリーダーから一定時間 Heartbeat や通常のログ複製が到達しなければリーダーが故障したものとして新しい選挙を開始してリーダーに立候補します (この間隔を選挙タイムアウトと呼びます)。ここで、複数のフォロワーが同時に立候補してしまうと選挙を失敗させる split vote (後述) が発生しやすくなるため、Raft ではフォロワーごとの乱数で選挙タイムアウトを調整してます。例えば Heartbeat 間隔が 1 秒、Heartbeat 到達の最大許容遅延を 0.5 秒として選挙タイムアウトを 1 + 0.5 + 1.5 × rand() とすれば、同時の立候補者が出る確率を減らしつつ最悪でも 3 秒以内にリーダーの故障を検知できます。

論文では選挙タイムアウトは Heartbeat 間隔より一桁大きい程度の見積もりを推奨しています。最短の選挙タイムアウトは、Heartbeat の現実的な平均ブロードキャスト応答時間 (RTT) を $t_{b}$ = 0.5～20ms と想定すると $t_{e}$ = 10～500ms 程度となり、これにサーバごとの乱数調整分が加算したあたりとなるでしょう。

ところで、乱数調整分をサーバごとの優先順位値 × $t_{b}$ のように設計すれば split vote も発生しづらく (確定的ではないが) リーダーの順序を方針づけることもできます。分散環境でのサーバの順位付けには起動タイムスタンプの古さなどいくつかの方法があります。

さて、リーダーの故障を検知したら次はリーダー選挙です。

リーダー選挙

Raft には選挙が行われるたびに単純増加するタームと呼ばれる数値があります。ある時点のタームを担当するリーダーは 1 つないしは 0 (選挙失敗時) であり、2 つ以上のリーダーが同一のタームに発生することはありません。

さて、合意クラスタ内のリーダー不在を検知したフォロワーはリーダーに立候補し候補者となります。候補者は自分の認識しているタームを一つ進め、自分に投票し、クラスタ内の他のサーバの RequestVote RPC (投票要求) を呼び出します。

RequestVote RPC を呼び出されたサーバは、自分がまだそのタームに投票しておらず、候補者の持つログが自分と同じかそれより新しければ投票を行います。さもなくば投票を拒否します。候補者がクラスタ内のサーバの定足数票を獲得すると新しいリーダーとなり Heartbeat をブロードキャストして自分が新しいタームのリーダーとなったことをクラスタの全サーバに通達します。

全てのフォロワーは、受信した Heartbeat (AppendEntries RPC) のタームが自分の認識しているタームより進んでいた場合、自分がそのタームの投票にどう関与したかにかかわらずその送信元のサーバを最新のリーダーと認識します (従ってもしクラスタ内に Byzantine ノードが存在した場合は選挙を行わずに容易にリーダーとなることができます)。

反対に、受信した Heartbeat が自分の認識しているタームより小さい場合、長期間故障停止していた古いリーダーが復帰して何も知らずに送信したものと推測できます。この時フォロワーは自分の認識している最新のターム付きで失敗応答を返すため、旧リーダーは自分がすでにリーダーではない事を知ることができます。

選挙の失敗

リーダー選挙はいくつかの理由で失敗することがあります。一つの例は合意クラスタ内の応答可能なサーバが定足数を下回っているケースです。このような状況ではどの候補者もリーダーになることはできません (これは Raft で Split Brain が発生した時に片方のクラスタがサービスを継続できない = 分断耐性がないことも意味しています)。

もう一つの例は Split Vote です。これは複数の候補者がほぼ同時に RequestVote RPC をブロードキャストし、クラスタ内のサーバの票が割れてどの候補者も定足数票を獲得できないケースです。

Split Vote に対処するため Raft は Heartbeat と全く同じタイムアウト機構を選挙時にも機能させています。つまり、RequestVote RPC で投票してから選挙タイムアウトの時間が経過しても新しいリーダーからの Heartbeat が到達しなかったサーバ (定足数を獲得できていない候補者も含む) は、そのタームの選挙が失敗したものとみなして、自分のタームを一つ進め、新しい選挙を開始して自分が立候補します。

機能回復時間

リーダーが故障してからクラスタが機能を回復するまでの時間を考えてみよう。Heartbeat の平均ブロードキャスト応答時間 (RTT) を $t_{b}$ 、選挙タイムアウトを $t_{e}$ とすると、リーダー故障からクラスタ機能回復までの各ステップに要する時間は以下のようになります。

例えば $t_{b}$ = 20ms、 $t_{e}$ = 500ms の環境では (リーダー以外の故障や split vote が発生しなければ) 最大 540ms 程度でクラスタ機能を回復することができるだろう。split vote が発生するケースでは選挙に失敗した回数だけ $t_{e}$ を繰り返します。つまり split vote のような選挙失敗の発生回数を $n_{f}$ とした場合 $t_{e} + n_{f} \times t_{e} + 2 t_{b}$ 程度で回復します。

分散システムでのリーダー選挙という手法は split vote のような失敗状況が連続して発生することを完全に阻止することはできないことがよく知られています。言い換えると、Raft において一度リーダー選挙が発生すると機能回復が有限時間内に終わることを保証することはできません。これは安全性/障害耐性 (≒一貫性/可用性) を実装している非同期システムは有限時間内に処理を終了することを保証できないという FLP Impossibility が意味するところです。例えば合意クラスタ内にフォロワーが 20 ノードも存在すれば複数の立候補者が同時に立候補する確率も高くなり選挙失敗が連続する頻度は現実的に非常に高くなります。

クライアント

クライアントはどのようにしてリーダーを知ればよいでしょうか? すべてのフォロワーは現在のリーダーを知っているます。合意クラスタ内のいずれかのサーバと接続し、もしそのサーバがリーダーでなければリーダーのアドレス付きで失敗応答するのは一つの方法となります (HTTP の 302 Found リダイレクト相当の動き)。あるいはそのサーバが代理となってリーダーにリクエストを転送することもできます。

ログ複製

全てのログは AppendEntries RPC を使ってリーダーからフォロワー方向にのみ伝達されます。リーダーは自分を含めて定足数のサーバがログを保存できたことを確認するとログの複製を完了したとみなしてローカルの状態にログを適用し(commit) クライアントに成功応答します。少し遅れて、フォロワーが次の Heartbeat もしくはログ複製を受信したときにリーダーがどこまで commit したかが分かるため、その時点までのログをローカルの状態に適用します。

一貫性レベル

上記のシーケンス図が示すように、リーダーがどの時点を完了とみなしてクライアントに応答するかには考慮の余地があるように思います。いくつかの分散データベースではこれらを一貫性レベルとしてパラメータ化しクライアント要求ごとに指定が可能になっています。

リーダーがローカルのエントリにログを保存できた時点で
クラスタ内の定足数以上がログの複製できた時点で (クラスタとして確定)
クラスタ内のすべてがログを複製できた時点で
リーダーが定足数のログ複製を確認しローカルの状態を更新した時点で (論文はここを示している)
クラスタ内の定足数以上が状態を更新できた時点で
クラスタ内のすべてが状態を更新できた時点で

上記の 1. は故障によるログ喪失の可能性がありますが重要なデータでなく高速な応答が求められるときに有用かもしれません。Raft の設計では 2. 以上であれば成功応答後すぐにリーダーが故障しても合意クラスタからログが消えることはありませんが、2. では成功応答直後のリクエストでまだログの適用結果が見えない可能性があります。成功応答=適用結果の参照可能を保証するのであれば 4. が必要だし (一般に一貫性と言えばここを意味する)、負荷分散のためにフォロワーを Read Only ノードとして利用しているのであれば 6. が必要な場面もあるかもしれません (通常は READ 処理もリーダーが担当する)。他にも地理分散を想定して「1つのデータセンターが喪失しても残ったデータセンターで定足数を確保できるようになった時点で」といった方針も考えられます (強い一貫性の分散システムがデータセンターで分離されるケースはあまり見ないですが)。

障害時の復旧動作

停止したフォロワーの復帰

リーダーは AppendEntries RPC に応答のないフォロワーを検出すると、比較的短時間で復帰することを期待して定期的に同じ RPC を実行します。ただしこれは単なる投機的行動です。

リーダー交代前にフォロワーが復帰した場合、リトライしていたログから順に再送信されフォロワーの状態は復元します。停止中にリーダー交代があった場合、新しいリーダーも停止を検知して同じように送信を繰り返しますが、新しいリーダーが送っているログは復旧に必要なログの正しいインデックスではない可能性があります。この場合、フォロワーが復帰してもログ複製は拒否され、応答で正しいログのインデックスを返します。リーダーはその正しいインデックスから再送信します。

Heartbeat がログ複製と同じ AppendEntiries RPC であることを考えれば、この再送信処理はなくても Heartbeat が到達した時点で再送信処理が開始します。

リーダー停止からの復旧

フォロワーがリーダーの停止を検出すると新しい選挙が始まり次のリーダーが選出されます。ではこのとき処理中のログはどうなるだろうか?

前提として、Raft の投票条件は自分より確定済みログの複製が進んでいない候補者を拒否します。つまり定足数に複製されている最新ログを持っていない候補者は定足数票を取り得ない仕組みになっています。さらに言い換えると、定足数票を得た新リーダーは、少なくとも最新の確定済みログの複製を持っていることを意味しています (Leader Completeness Property)。

クライアントに応答する前にリーダーがクラッシュした場合、その処理はどうなるだろうか? ログ複製の進行状況によっていくつかのシナリオが考えられます。

ログが定足数のサーバに複製されていれば、ログは確定しており新リーダーもそのログを持っている。
ログが定足数のサーバに複製されなければ:
1. 新リーダーが(たまたま)そのログを持っていれば:
  1. 新リーダーがそのログを複製/確定した時点でログは確定する (旧リーダーの処理を引き継ぐ挙動)。このとき、すでに旧リーダーから複製したログを持っているフォローワーは同じ内容のログで上書きする動作になる。
  2. 新リーダーがそのログを複製/確定する前に停止すれば、新しいリーダー選挙後に 2. へ戻る。
2. 新リーダーがそのログを持っていなければ:
  1. 新リーダーが別の新しいログを受信/複製した時点で、一部のフォロワーに残っていたそのログは上書き/無効化される。
  2. 新リーダーが別の新しいログを受信/複製する前に停止すれば、新しいリーダー選挙後に 2. へ戻る。
旧リーダーのローカルエントリに保存される前であれば、クラスタ内には物理的に存在せず無効。

結局のところ、適用されるケースも破棄されるケースもあり合意クラスタが復旧してみないと分からないという結論になります。また 2.2.1 で新しいログを受信しないケースや、2.1.2 や 2.2.2 を繰り返すケースがあるため、有限時間内にどちらかに定まる保証もありません。論文では、クライアントがログにユニークな番号をつけ、サーバ側でそのログが確定済みかを検査することで、失敗時にクライアントがリトライしても安全な設計を提案しています。

実装イメージ

以下は覚え書き程度に書き起こしただけなので詳細は論文の 5 章あたりを参照。この章はしばらくしたら更新するかもしれない。

ステートマシンの内部状態

Raft ステートマシンは以下のような内部状態で選挙とログ複製を実行するだろう。

Leader State は自分がリーダーの場合に使用する。サーバごとに次に送るべきログインデックスと、そのサーバと自分とで (タームも含めて) 一致している最も大きいログインデックスを保持している。

AppendEntries RPC

以下に AppendEntiries RPC の処理説明を擬似コードで記述する。

def AppendEntries(
  term:Long,          // リーダーのターム (0,1,2,...)
  leaderId:Int,       // このタームのリーダー
  prevLogIndex:Long,  // このリクエストのログエントリの直前のログインデックス (0,1,2,...)
  prevLogTerm:Long,   // prevLogIndex のターム (0,1,2,...)
  entries:Array[Log], // 複製するログ (効率のため複数可; Heartbeat の場合は空)
  leaderCommit:Long   // リーダーが確定と認識しているログインデックス (0,1,2,...)
):(
  term:Long,          // フォロワーが認識している現在のターム (0,1,2,...)
  success:Boolean     // ログを複製した場合 true
) = {
  if(term < this.currentTerm ||                     // 旧世代のリーダーが Crash-Recovery した可能性
     this.entries.length <= prevLogIndex ||         // 自分が Crash-Recovery した可能性
     this.entries[prevLogIndex].term != prevLogTerm // 自分が Crash-Recovery した可能性
  ){
    return (this.currentTerm, false)
  }

  // ログを複製する
  for(i = 0; i < entries.length; i++){
    this.entries[prevLogIndex + i].term = term
    this.entries[prevLogIndex + i].log = entries[i]
  }

  // リーダーが確定と認識しているログの位置を合わせる
  if(leaderCommit > this.commitIndex){
    this.commitIndex = min(leaderCommit, prevLogIndex + entries.length)
  }
  this.currentTerm = term
  return (this.currentTerm, true)
}

RequestVote RPC

以下に RequestVote RPC の処理説明を擬似コードで記述する。

def RequestVote(
  term:Long,         // 候補者のターム (0,1,2,...)
  candidateId:Int,   // 候補者ID
  lastLogIndex:Long, // 候補者の持つ最新のログインデックス (0,1,2,...)
  lastLogTerm:Long   // 候補者の持つ最新のターム (0,1,2,...)
):(
  term:Long,           // 投票者が認識している現在のターム (0,1,2,...)
  voteGranted:Boolean  // 候補者に投票した場合 true
) = {
  if(
    term < this.currentTerm ||  // 旧世代のリーダー/候補者が Crash-Recovery した可能性
    (this.votedFor != null && this.votedFor != candidateId) || // 別の候補者に投票済み
    (論文参照)  // 候補者の持つログが自分より古い
  ){
    return (this.currentTerm, false)
  }
  this.votedFor = candidateId
  return (this.currentTerm, true)
}

まとめ

この記事では Raft がどのようにして一貫性のある SMR を設計しているかについて説明しました。この記事は元の論文のみならず一部私見も交えています。動作の詳細な条件などは省略しているためプロダクション向けの分散データベースを実装しようとしている人には情報不足だと思いますが、勉強目的で Raft の動きを理解したい人や実装してみたい人、あるいは etcd のような Raft 実装の API の意味や内部動作を理解したい人の参考になればよいと思います。

❏

分散合意アルゴリズム Raft を理解する

概要