信也のブログ

Raft 論文読解

29 min

はじめに

Raft はログ複製を管理するためのコンセンサスアルゴリズムです。コンセンサスアルゴリズムは複数台のマシンからなるクラスタに適用され、一部のマシンが故障しても正常にサービスを提供し続けることを保証します。したがって、信頼性の高い大規模ソフトウェアシステムの構築において非常に重要です。

Raft アルゴリズムの主要な論文は『In Search of an Understandable Consensus Algorithm (Extended Version)』であり、こちら から読むことができます。論文は 18 ページと長くなく、Raft と Paxos の比較が多く登場します（冒頭から苦労話が始まります）。これにより Raft の最大の強みである「より理解しやすい」点が際立っています。

本記事は論文読解中のメモです。

背景

コンセンサスアルゴリズムは主に複製状態機械（Replicated state machines）モデルに用いられます。複製状態機械は通常、複製ログによって実現され、各ログには一連の指令が含まれています。クラスタ内の各マシンは同じ順序でこの一連の指令を実行し、最終的に同じ状態に到達します。この「最終的に」という点に注意してください。表面上は最終的整合性であり、強整合性ではありません。

コンセンサスアルゴリズムはクラスタ内で複製ログが連続していることを保証し、コンセンサスモジュール同士が通信して、たとえ一部のマシンが故障しても、すべてのマシンが同じ順序で同じ指令を実行することを保証します。これにより、すべてのマシンが単一のマシンのように共同で外部にサービスを提供できます。

コンセンサスアルゴリズムはビザンチン障害を想定しておらず、ノードが意図的に偽情報を作成しない前提です。

アルゴリズムの説明

Raft コンセンサスアルゴリズムは大きく三つの独立したサブモジュールに分かれます：

  • リーダー選出：既存のリーダーが故障した場合、新しいリーダーを選出する必要がある
  • ログ複製：リーダーはクライアントからログを受け取り、クラスタ内に複製し、他のマシンのログと自身のログを一致させる
  • 安全性保証：もしあるマシンが特定の指令を受け入れた場合、他のマシンは同じログインデックス（log index）に異なる指令を受け入れることは不可能であることを保証する

Raft の基本

Raft クラスタ内のマシンは常に三つの状態のいずれかにあります：

  • リーダー：すべてのクライアントリクエストを処理する
  • フォロワー：リクエストを処理せず、リーダーや候補者（Candidate）からの要求を受けて応答する
  • 候補者（Candidate）：リーダーを選出するための状態

正常な動作時、クラスタには一人のリーダーがおり、他のすべてのマシンはフォロワーです。

Raft は時間を複数の任期に分割し、各任期の開始時にクラスタ内で選挙が行われます。複数の候補者がリーダーを目指します。ある候補者が選挙に勝利すると、その候補者はリーダーとなり、他のマシンはフォロワーに戻ります。

任期は単調増加する整数で、各マシンは現在の任期を保持し、通信時に任期を含めます。もしあるマシンが自分の任期が他のマシンより古いと気づいた場合、自分の任期を更新します。候補者やリーダーが自分の任期が他の任期より古いと判明した場合（新しい任期のリーダーが現れた場合）、直ちにフォロワーに変わります。

Raft の基本的な通信は二種類の RPC で行われます。投票要求（RequestVote RPC）は選挙時に候補者が送信し、追加要求（AppendEntries RPC）はリーダーが送信し、ログ複製とハートビートに使われます。

リーダー選出

マシンは起動時にフォロワー状態であり、適切な RPC を受け取る限りフォロワーを維持します。リーダーは定期的にコマンドを含まない追加要求を送信し、ハートビートとしてサーバーの存在を維持します。もしフォロワーが一定期間リクエストを受け取らなければ、選挙を開始します。

選挙を開始したフォロワーは候補者に変わり、現在の任期に 1 を加え、自分に投票した後、クラスタ内の他のマシンに並行して投票要求を送ります。候補者は以下の三つのいずれかが起こるまでその状態を維持します：

  1. ある候補者がクラスタの過半数の票を獲得した場合、その候補者が選挙に勝利します。各マシンは任期中に一人の候補者にしか投票しないため、任期中に複数の候補者が勝つことはありません。勝利した候補者はリーダーに変わり、他のマシンにハートビートを送ってリーダーの地位を維持します。
  2. 候補者が他のマシンから追加要求を受け取った場合、その要求の任期が候補者の任期以上なら候補者はフォロワーに戻ります。そうでなければ要求を拒否し候補者状態を維持します。
  3. 多数のフォロワーが同時に候補者になった場合、過半数の票を得られない可能性があります。この場合、候補者はタイムアウトし、任期を 1 増やして新たな選挙を開始します。

この無限ループを防ぐために、候補者のタイムアウトはランダムな範囲内で設定され、同時タイムアウトを避けます。

ログ複製

各クライアントリクエストはログ複製状態機械で実行する指令を含みます。リーダーはリクエストを受け取ると、その指令をログに追加し、並行してクラスタ内の他マシンに追加要求を送信し指令を複製します。指令の複製が完了すると、リーダーはその指令をコミットし状態機械に適用し、クライアントに成功を返します。

各追加要求には複製すべき指令の他に、リーダーが指令を受け取った時の任期と、ログ内の位置を示す整数インデックスが含まれます。

リーダーが指令を過半数のマシンに複製できた時点で、その指令はリーダーによってコミットされます。Raft はコミットされた指令が永続化され、最終的にすべての利用可能な状態機械で実行されることを保証します。このコミットは前のすべての指令も同時にコミットします。リーダーはコミット予定のログインデックスを記録し、すべての追加要求に含めます。フォロワーはログ条目がコミットされたことを知ると、その条目を自身の状態機械にコミットします。

さらに Raft は以下の二つのルールを保証します：

  • 同じ任期とログインデックスを持つ二つのログ条目は同じ指令を保持する
  • 同じ任期とログインデックスを持つ二つのログ条目は、それ以前のすべてのログも同じである

一つ目の保証は比較的簡単で、二つ目の保証が重要です。

追加要求送信時、リーダーは新しいログ条目前のログ条目の任期とログインデックスを含めます。フォロワーがそのログを持っていなければ要求を拒否します。これが連続性チェックです。要求が成功すれば、フォロワーのログはリーダーと一致していることが分かります。

連続性チェックに失敗した場合、リーダーはフォロワーのログを自身と一致させる必要があります。具体的には、リーダーはフォロワーと一致する最後のログを見つけ、フォロワーのログからそのログ以降を削除し、自身の後続ログを送信します。リーダーは各フォロワーごとに nextIndex を管理し、次に送るログインデックスを保持します。リーダー起動時、すべてのフォロワーの nextIndex はリーダーの最後のログインデックス＋1 に初期化されます。フォロワーが拒否した場合、リーダーはそのフォロワーの nextIndex を 1 減らし、再度追加要求を送ります。

ここは少し曖昧ですが、おそらく各追加要求は nextIndex から後続のログ条目を送信し、連続性チェックが通るとフォロワーのログはリーダーと一致し、その後のログも同期されるということです。

安全性保証

上記の仕組みだけでは安全性が完全に保証されません。例えば、あるマシンが突然通信不能になり、その間にリーダーが複数のログをコミットした場合、そのマシンがリーダーに選出されてしまうと、これらのログが上書きされる可能性があります。本節では選挙時の制約を追加し、Raft アルゴリズムを完成させます。この制約は任意の任期のリーダーが前任期のすべてのコミット済みログを必ず含むことを保証します。

まず、投票要求には候補者のログ情報が含まれます。もし他のマシンが自分のログの方が候補者より新しい（最後のログ条目の任期やインデックスが大きい）と判断した場合、そのマシンは投票を拒否します。

さらに、ある任期のログ条目が過半数のマシンに受け入れられたら、リーダーはそれをコミットします。もしリーダーがコミット時に故障しても、次のリーダーはそのログの複製を続けます。しかし、リーダーはすぐに前任期のログがコミット済みかどうかを確定できません。これが論文の図 8 の問題です。

したがって、Raft は前任期のログ条目のコミットをレプリカ数で判断せず、現在の任期のログ条目のみをレプリカ数でコミットします。現在の任期のログ条目がコミットされると、その前のすべてのログ条目は暗黙的にコミットされたとみなされます。

クラスタノードの変更

クラスタノードの変更中に、クラスタ全体を停止せずに設定を変更したい場合、二つの独立した「主体」が存在する可能性、つまり二人のリーダーが選出される可能性があります。

ノード変更の安全性を確保するため、Raft は二段階の方法を採用します。まずクラスタは合意状態（joint consensus）に切り替わり、合意がコミットされた後に新しい設定に移行します。合意状態でもクラスタは正常にサービスを提供します。合意状態では：

  • ログは新旧両方の設定のすべてのマシンに複製される
  • 両方の設定の各マシンはリーダーになれる
  • 選挙と追加は新旧両方の設定で過半数の同意を得なければならない

クラスタ設定は特別なログ条目として保存・伝搬されます。手順は以下の通りです：

  1. リーダーがクラスタ設定を C_old から C_new に変更するリクエストを受け取る
  2. リーダーは C_old と C_new を合意状態 C_old,new として一つのログ条目に保存する
  3. そのログ条目を新旧設定のすべてのマシンに追加する
  4. あるマシンがそのログ条目を受け取ると（コミットは不要）、以降の操作はその設定を基準に行う
  5. C_old,new が過半数に受け入れられるとリーダーはそれをコミットし、これ以降 C_old または C_new のマシンはリーダーになれなくなる
  6. リーダーは C_new のログ条目を作成し、すべてのマシンに追加してコミットする

クラスタノード変更には以下の三つの問題があります：

  1. 新規ノードはログを持たず、追いつくまで時間がかかるため、一時的にクラスタの可用性が低下する可能性がある。Raft は新規ノードを投票権のない状態で追加し、ログが追いついたら正式に扱う段階を設けている。
  2. クラスタのリーダーが新設定に含まれない場合、リーダーが C_new をコミットすると自分自身がクラスタから外される。この間、リーダーは自分を主体としないクラスタを管理し、ログを複製するが自分をリーダーとみなさない。
  3. 外されたサーバーはハートビートを受け取れず、選挙を行い、新しい任期の投票要求を送るため、クラスタのリーダーがフォロワーに降格する可能性がある。これにより可用性が低下する。

問題 3 を防ぐため、Raft は次の制約を追加します：サーバーは現在のリーダーからのハートビートのタイムアウト内に投票要求を受けても任期や投票を更新しません。これにより、リーダーがクラスタのハートビートを維持できる限り、より大きな任期の投票で追い出されません。

ログ圧縮

ログが増大すると、マシンはすべてのログをメモリに保持できなくなるため、スナップショットを導入し、定期的にシステム状態を永続化ストレージに保存し、スナップショットまでのログを安全にメモリから削除します。

クラスタ内の各マシンは独自にスナップショットを管理し、スナップショットはコミット済みログ条目のみを含みます。状態機械の現在の状態に加え、以下のメタデータも保存します：

  • スナップショットに含まれる最後のログ条目のインデックス
  • スナップショットに含まれる最後のログ条目の任期

これらは追加要求時の連続性チェックに用いられます。クラスタノード変更をサポートする場合、スナップショットには最新のクラスタ設定も含める必要があります。スナップショット作成後、スナップショット以前のすべてのログと古いスナップショットは削除されます。

時折、リーダーは新規参加ノードや遅れているノードにログを同期するためにスナップショットを送る必要があります。リーダーは新しい RPC、スナップショット同期要求（InstallSnapshot RPC）を使ってフォロワーにスナップショットを送ります。

type InstallSnapshotRequest struct {
    // Term リーダーの任期
    Term              int64
    // LeaderID フォロワーはクライアントリクエストをリーダーにリダイレクト可能
    LeaderID          int64
    // LastIncludedIndex スナップショットに含まれる最後のログ条目のインデックス
    LastIncludedIndex int64
    // LastIncludedTerm スナップショットに含まれる最後のログ条目の任期
    LastIncludedTerm  int64
    // Offset スナップショットファイル内のこのチャンクのオフセット
    Offset            int64
    // Data スナップショットチャンクのデータ
    Data              []byte
    // Done 最後のチャンクかどうか
    Done              bool
}

type InstallSnapshotResponse struct {
    // Term フォロワーの現在の任期
    Term    int64
}

受信側の実装：

  1. Term が CurrentTerm より小さい場合、即座に返す
  2. 最初のチャンク（Offset = 0）ならスナップショットファイルを作成
  3. データをスナップショットファイルの該当オフセットに書き込む
  4. Done が false なら返して次のチャンクを待つ
  5. ログに LastIncludedIndex と LastIncludedTerm に一致するログ条目があれば、それ以降のログを保持して返す
  6. それ以外はすべてのログを破棄
  7. スナップショット情報で状態機械をリセットし、スナップショット内のクラスタ設定を適用

通常、スナップショットには受信側が持たないログが含まれるため、受信側はすべてのログを破棄しスナップショット情報を使用します。もしスナップショットのログ条目が受信側にすべて含まれていれば、その部分のログはスナップショットに置き換えられますが、その後のログは保持されます。

最後に、スナップショットはクラスタの性能に影響を与える可能性があります。マシンは固定サイズのバイト数を設定し、そのサイズに達したらスナップショットを作成します。サイズが大きすぎると作成に時間がかかり、小さすぎると頻繁に作成されます。また、スナップショット作成はディスク IO が遅いため長時間かかることがあり、正常な処理に影響を与える可能性があります。Raft はコピーオンライト技術を推奨し、スナップショット作成中もログ追加やリクエスト処理を継続可能にします。

クライアントとのやりとり

クライアントのすべてのリクエストは Raft クラスタのリーダーが処理します。クライアントは起動時にクラスタ内の任意のマシンにリクエストを送りますが、そのマシンがリーダーでなければ拒否され、最後に受け取ったハートビートのリーダーのアドレスが返されます。リーダーが故障するとクライアントはタイムアウトし、再度任意のマシンにリクエストを送ります。

Raft の目標は線形化可能な意味論を実現することで、各操作は瞬時に完了し一度だけ実行されるように見えます。しかし、リーダーが指令を実行後クライアントに応答する前に故障し、クライアントが別のリーダーに同じ指令を再送すると、指令が二重に実行される可能性があります。これを防ぐため、クライアントは各指令に単調増加する一意の識別子を付与し、状態機械は最後に実行した指令の識別子を記録します。もしすでに実行済みの指令が来たら、即座に成功を返し再実行しません。

読み取り専用リクエストはログに書き込む必要がないため、コンセンサスを得ずに処理できます。しかし、この場合リーダーがすでに新しい任期のリーダーに置き換わっている可能性があり、古いデータを返す恐れがあります。Raft は以下の二つの対策でこれを防ぎます：

  1. リーダーはすべてのコミット済みログ条目を持っている必要がある。リーダーの完全性によりこれが保証されますが、任期開始時はどれがコミット済みか分かりません。そこで任期開始時に無操作のログ条目をコミットし、最新のコミット情報を取得します。
  2. リーダーは読み取り専用リクエスト処理前に自分がまだリーダーであることを確認します。これはクラスタの過半数とハートビートを交換するだけで実現できます。

アルゴリズム実装

論文の図 2 には非常に詳細な実装が示されています（これが Raft の素晴らしいところ！）。ノード変更とログ圧縮は含まれていません。

サーバー状態

type ServerState struct {
    /***** すべてのサーバーが持つ永続状態 *****/
    // CurrentTerm マシンが遭遇した最大の任期。起動時は 0、単調増加
    CurrentTerm int64;
    // VotedFor 現任期内に投票した候補者の ID。未投票なら nil
    VotedFor    *int64;
    // Logs ログ条目。各条目は状態機械の指令とリーダーが受け取った時の任期を含む。インデックスは 1 始まり
    Logs        []*Log;

    /***** すべてのサーバーが持つ可変状態 *****/
    // CommitIndex 知られている最大のコミット予定ログインデックス。起動時は 0、単調増加
    CommitIndex int64;
    // LastApplied 最大のコミット済みログインデックス。起動時は 0、単調増加
    LastApplied int64;

    /******* リーダーが持つ可変状態。選出時に初期化 *******/
    // NextIndex 各マシンに次に送るべきログ条目のインデックス。リーダーの最後のログインデックス +1 で初期化
    NextIndex  []int64;
    // MatchIndex 各マシンが複製済みの最大ログインデックス。0 で初期化、単調増加
    MatchIndex []int64;
}

追加要求

type AppendEntriesRequest struct {
    // Term リーダーの任期
    Term         int64
    // LeaderID フォロワーはクライアントリクエストをリーダーにリダイレクト可能
    LeaderID     int64
    // PrevLogIndex 新しいログ条目前のログインデックス
    PrevLogIndex int64
    // PrevLogTerm 前のログ条目の任期
    PrevLogTerm  int64
    // Entries 保存すべきログ条目。ハートビートは空
    Entries      []*Log
    // LeaderCommit リーダーの CommitIndex
    LeaderCommit int64
}
 
type AppendEntriesResponse struct {
    // Term フォロワーの現在の任期
    Term    int64
    // Success フォロワーが PrevLogIndex と PrevLogTerm を含むログ条目を持つなら true
    Success bool
}

受信側の実装：

  1. Term が CurrentTerm より小さければ false を返す
  2. ログに PrevLogIndex と PrevLogTerm に対応するログ条目がなければ false を返す
  3. 既存のログ条目と新規ログ条目が同じログインデックスだが任期が異なる場合、その条目以降のログを削除する
  4. ログに存在しないログ条目をすべて追加する
  5. LeaderCommit が CommitIndex より大きければ、CommitIndex を LeaderCommit と新規ログの最後のインデックスの小さい方に設定する

投票要求

type RequestVoteRequest struct {
    // Term 候補者の任期
    Term         int64
    // CandidateId 投票を求める候補者の ID
    CandidateId  int64
    // LastLogIndex 候補者の最後のログインデックス
    LastLogIndex int64
    // LastLogTerm 候補者の最後のログ任期
    LastLogTerm  int64
}

type RequestVoteResponse struct {
    // Term 現在の任期
    Term        int64
    // VoteGranted true なら投票成功
    VoteGranted bool
}

受信側の実装：

  1. Term が CurrentTerm より小さければ false を返す
  2. VotedFor が nil または CandidateId であり、かつ候補者のログが同等か新しい場合 true を返す

サーバールール

すべてのマシンに対して：

  • CommitIndex が LastApplied より大きければ、LastApplied を 1 増やし、ログ log[LastApplied] を状態機械にコミットする
  • RPC リクエストや応答の Term が CurrentTerm より大きければ、CurrentTerm を更新しフォロワーに変わる

フォロワーに対して：

  • 候補者やリーダーからの RPC に応答する
  • 選挙タイムアウトまでリーダーからの追加要求や投票を受けなければ、候補者に変わる

候補者に対して：

  • 候補者に変わると選挙を開始する：
    • 現任期を 1 増やす
    • 自分に投票する
    • 選挙タイムアウトをリセットする
    • 他のすべてのマシンに投票要求を送る
  • 過半数の票を得たらリーダーに変わる
  • 新しいリーダーから追加要求を受けたらフォロワーに戻る
  • 選挙タイムアウトで再度選挙を開始する

リーダーに対して：

  • リーダーに変わるとすべてのマシンに空の追加要求を送る。アイドル時も空追加要求を繰り返し送信し選挙タイムアウトを防ぐ
  • クライアントから指令を受けたらログに追加し、コミット後に応答を返す
  • 最後のログインデックスがクライアントの NextIndex より大きければ、その NextIndex 以降のログ条目を含む追加要求を送る
  • 成功したらフォロワーの NextIndex と MatchIndex を更新する
  • 連続性チェックに失敗したら NextIndex を 1 減らして再送する
  • N が CommitIndex より大きく、過半数の MatchIndex が N 以上で、かつ第 N 条ログの任期が現在の任期なら CommitIndex を N に設定する
raft 6.5840 6.824