Raft論文を読む

はじめに

Raftは、ログレプリケーションを管理するための合意アルゴリズムです。合意アルゴリズムは、複数のマシンからなるクラスタで、一部が故障してもサービスを提供し続けるために使われます。信頼性の高い大規模ソフトウェアシステムを作るうえで、重要な役割を担っています。

Raftの主要な論文は『In Search of an Understandable Consensus Algorithm (Extended Version)』で、こちらから読めます。18ページと、それほど長くありません。冒頭からひとしきり苦労話があり、随所でPaxosと比較しながら、Raft最大の長所である「より理解しやすいこと」を強調しています。

この記事は、論文を読みながら取ったメモです。

前提となる話

合意アルゴリズムは、主に複製状態機械（replicated state machines）のモデルで使うために考案されました。複製状態機械は通常、複製されたログで実装します。ログには一連の命令が記録され、クラスタ内の各マシンが同じ順序で実行することで、最終的に同じ状態へ到達します。この「最終的に」に注目です。これは強い整合性ではなく、結果整合性を示しています。

合意アルゴリズムは、クラスタ内で複製されたログの一貫性を保ちます。各マシンの合意モジュールが互いに通信し、一部のマシンが故障しても、最終的に同じ命令を同じ順序で実行できるようにします。こうして複数のマシンが、1台のマシンのようにまとまってサービスを提供します。

ここで扱う合意アルゴリズムは、非ビザンチン障害を前提とします。つまり、ノードが意図的に情報を偽造することは想定しません。

アルゴリズムの説明

Raftは、比較的独立した3つの部分に分けられます。

リーダー選出：現在のリーダーが故障したら、新しいリーダーを選ぶ。
ログレプリケーション：リーダーがクライアントからログを受け取り、クラスタ内に複製して、ほかのマシンのログを自身と一致させる。
安全性の保証：あるマシンが特定の命令を受け入れたら、別のマシンが同じログインデックスで異なる命令を受け入れないようにする。

Raftの基本

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

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

通常、クラスタにはリーダーが1台だけ存在し、残りはすべてフォロワーです。

Raftでは時間を任期に分けます。各任期の開始時には選挙が行われ、1台以上の候補者がリーダーを目指します。候補者が選挙に勝てばリーダーとなり、ほかのマシンはフォロワーになります。

任期は単調増加する整数です。各マシンは現在の任期を保存し、ほかのマシンとの通信にも付加します。相手の任期が自分より大きいと分かったら、自身の任期を更新します。候補者やリーダーが、より新しい任期の存在を知った場合は、ただちにフォロワーへ戻ります。

Raftの基本的な通信に必要なRPCは2種類だけです。RequestVote RPCは選挙中の候補者が送ります。中国語では「票集めのリクエスト」と訳すと、何だか妙な感じがしますね。AppendEntries RPCはリーダーが送り、ログの複製とハートビートに使います。

リーダー選出

マシンはフォロワーとして起動し、適切なRPCを受け取っている限り、その状態を保ちます。リーダーは命令を含まないAppendEntriesを定期的に送り、ハートビートとして自身の役割を維持します。フォロワーが一定時間リクエストを受け取らなければ、選挙を始めます。

選挙を始めるフォロワーは候補者になり、現在の任期を1増やし、自分に投票してから、ほかのマシンへ並列にRequestVoteを送ります。その後は、次のいずれかが起こるまで候補者の状態を保ちます。

クラスタの過半数から票を得ると、選挙に勝ちます。各マシンが1つの任期で投票できる候補者は最大1台で、先着順です。そのため、1つの任期で当選できるのも最大1台です。当選した候補者はリーダーとなり、ほかのマシンへハートビートを送ります。
別のマシンからAppendEntriesを受け取ることもあります。その任期が自分の現在の任期以上なら、フォロワーになります。小さければリクエストを拒否し、候補者のままです。
複数のフォロワーが同時に候補者になると、誰も過半数を取れないことがあります。その場合、候補者はタイムアウト後に任期を1増やし、新たな選挙を始めます。

3番目の状況が延々と続かないように、選挙のタイムアウトは一定の範囲でランダムに設定し、同時にタイムアウトしにくくします。

ログレプリケーション

クライアントの各リクエストには、複製状態機械に実行させる命令が含まれます。リーダーは命令をログに追加し、クラスタ内のマシンへ並列にAppendEntriesを送って複製します。複製が完了すると、その命令を状態機械にコミットし、クライアントへ成功を返します。

AppendEntriesには、複製する命令に加え、リーダーが命令を受け取ったときの任期と、ログ内の位置を示す整数のインデックスも含まれます。

リーダーが命令を過半数のマシンへ複製できたら、その命令をコミットします。Raftは、コミット済みの命令が永続化され、最終的に利用可能なすべての状態機械で実行されることを保証します。このとき、それ以前のエントリもすべてコミットされます。過去のリーダーが作ったものも含みます。リーダーはコミット位置を記録し、すべてのAppendEntriesにそのインデックスを付けます。フォロワーも、エントリがコミット済みと知ったら、自身の状態機械へ適用します。

また、Raftは次の2つの性質を保証する必要があります。

2つのログエントリの任期とログインデックスが同じなら、同じ命令を保持している。
2つのログエントリの任期とログインデックスが同じなら、それ以前のすべてのログエントリも一致している。

1つ目は比較的簡単なので、主に2つ目の保証を見ます。

リーダーはAppendEntriesを送る際、新しいエントリの直前にあるエントリの任期とインデックスも含めます。フォロワーが自身のログ内にそのエントリを見つけられなければ、リクエストを拒否します。これが整合性チェックです。リクエストが成功すれば、リーダーはフォロワーのログが自身と一致していると分かります。

整合性チェックに失敗した場合、リーダーはフォロワーのログを自身に合わせます。具体的には、両者で一致する最後のエントリを探し、フォロワー側のそれ以降を削除して、自身の後続エントリを送ります。リーダーはフォロワーごとにnextIndexを持ち、次に送るエントリのインデックスを記録します。リーダーになった直後は、自身の最後のログインデックスに1を足した値で、すべてのnextIndexを初期化します。あるフォロワーがチェックに失敗したら、そのnextIndexを1減らしてAppendEntriesを再送します。

この説明は少し曖昧に感じました。おそらく各AppendEntriesでは、nextIndexから最後までのエントリを送るのでしょう。そうでなければ、チェックが通ってもフォロワーのログを一致点まで切り詰めただけで、その後のログが同期されないことになります。

安全性の保証

ここまでの仕組みだけでは、安全性を完全には保証できません。たとえば、あるマシンが到達不能になっている間にリーダーが複数のログをコミットし、その後そのマシンがリーダーに選ばれると、それらのログが上書きされる可能性があります。Raftはこれを防ぐため、選挙に制限を加えます。どの任期のリーダーも、それまでの任期でコミットされたすべてのエントリを保持するという制限です。

まず、RequestVoteには候補者のログ情報を含めます。受信側は、最後のエントリの任期やログインデックスを比較し、自身のログのほうが新しければ投票を拒否します。

現在の任期のエントリが過半数のマシンに受け入れられたら、リーダーはそれをコミットします。コミット中にリーダーが落ちた場合、次のリーダーが複製を続けます。ただし、過去の任期のエントリが過半数のマシンに保存されていても、新しいリーダーはそれだけでコミット済みとは判断できません。ここで論文のFigure 8のような問題が起こり得ます。

そこでRaftは、過去の任期のエントリを複製数だけでコミットしません。複製数でコミットを判断するのは、現在の任期のエントリだけです。現在の任期のエントリがコミットされると、それ以前のエントリも暗黙にコミットされます。

クラスタのメンバー変更

クラスタ全体を停止せずに構成を変えようとすると、独立した2つの過半数が生まれ、リーダーが2台選ばれる可能性があります。

Raftは安全なメンバー変更のために、2段階の方法を採ります。まずクラスタを共同合意（joint consensus）の状態へ移し、それがコミットされたら新しい構成に切り替えます。共同合意の間もサービスは継続できます。この状態では、次のように動作します。

ログは新旧両方の構成に含まれるすべてのマシンへ複製する。
どちらの構成のマシンもリーダーになれる。
選挙とログの追加には、新旧それぞれの構成で過半数の同意が必要になる。

クラスタ構成は、特別なログエントリとして保存・転送します。流れは次のとおりです。

リーダーが、構成をC_oldからC_newへ変更するリクエストを受け取る。
C_oldとC_newをまとめ、共同構成C_old,newとして1つのログエントリに記録する。
そのエントリを新旧両方の構成のマシンへ追加する。
マシンはそのエントリをログに追加した時点で、コミット前でも以後の操作に新しい構成を使う。
C_old,newが必要な過半数に受け入れられたら、リーダーがコミットする。この時点で、C_oldまたはC_newだけに基づいてリーダーを選ぶことはできなくなる。
リーダーがC_newのログエントリを作り、各マシンへ複製してコミットする。

メンバー変更には、さらに3つの問題があります。

新しく加わるマシンはログを持っておらず、追いつくまで時間がかかるため、一時的に可用性を下げるおそれがあります。Raftでは、その前に新しい段階を設けます。新規マシンはAppendEntriesを受信しますが、投票権は持たず、その同意がなくても合意できます。ログが既存マシンに追いついたら、前述の変更処理へ進みます。
現在のリーダーが、新構成に含まれない場合があります。その場合、C_newをコミットした時点で退任します。つまり一時的に、自身を含まないクラスタを管理し、ログは複製するものの、自分を過半数の計算には入れない状態になります。
除外されたサーバーがクラスタを妨害することがあります。ハートビートを受け取れなくなったサーバーが選挙を始め、新しい任期のRequestVoteを送ると、現リーダーがフォロワーに戻ってしまいます。その選挙は成功せず、新しいリーダーも新クラスタから選ばれますが、除外されたマシンが繰り返しタイムアウトすることで可用性が下がります。

3番目を防ぐため、Raftはもう1つ制限を加えます。現リーダーからのハートビートを受けてからタイムアウトするまでの間にRequestVoteを受け取っても、任期を更新せず、投票もしません。現リーダーがクラスタとのハートビートを維持できている限り、より大きい任期の投票要求だけでは退任させられなくなります。

ログの圧縮

ログが増え続けると、すべてをメモリに保持できなくなります。そこでスナップショットを導入し、システムの状態を定期的に永続ストレージへ保存します。これにより、先頭からスナップショット時点までのログを安全にメモリから削除できます。

各マシンは独立して自身のスナップショットを管理します。対象はコミット済みのエントリだけです。状態機械の現在の状態に加え、次のメタデータも保存します。

スナップショットに含まれる最後のエントリのログインデックス。
そのエントリの任期。

このメタデータは、主にAppendEntriesの整合性チェックで使います。直前のエントリを比較する必要があるためです。前述のメンバー変更にも対応するなら、スナップショット時点の最新構成も含めます。書き込みが終わったら、その時点までのログと古いスナップショットを削除できます。

新しく参加したノードや遅れているノードへ同期するとき、リーダーが自身のスナップショットを送る必要がある場合があります。このために使う新しいRPCがInstallSnapshotです。

type InstallSnapshotRequest struct {
    // Term Leader 的任期
    Term              int64
    // LeaderID Follower 可以将客户端请求重定向到 Leader
    LeaderID          int64
    // LastIncludedIndex 快照包含的最后一个条目的索引
    LastIncludedIndex int64
    // LastIncludedTerm 快照包含的最后一个条目的任期
    LastIncludedTerm  int64
    // Offset 快照文件中的该快照块的偏移
    Offset            int64
    // Data 快照块数据
    Data              []byte
    // Done 是否是最后一个快照块
    Done              bool
}

type InstallSnapshotResponse struct {
    // Term Follower 当前任期
    Term    int64
}

受信側の処理は次のとおりです。

TermがCurrentTermより小さければ、ただちに戻る。
最初のチャンク、つまりOffset = 0なら、スナップショットファイルを作る。
指定されたオフセットにデータを書き込む。
Doneがfalseなら、戻って次のInstallSnapshotを待つ。
LastIncludedIndexとLastIncludedTermに一致するエントリがログにあれば、その後のエントリをすべて残して戻る。
ログをすべて破棄する。
スナップショットで状態機械をリセットし、保存されているクラスタ構成を使う。

通常、スナップショットには受信側がまだ持っていないログが含まれます。その場合、受信側はログをすべて破棄し、スナップショットを使います。一方、対象のログをすべて持っている場合は、その部分をスナップショットで置き換え、以後のエントリを残します。

最後に、スナップショットが性能へ与える影響です。ログが一定のバイト数に達したらスナップショットを作る方式にできますが、しきい値は大きすぎても小さすぎてもいけません。大きすぎると書き込みに時間がかかり、小さすぎると頻繁に作ることになります。また、ディスクI/Oは遅いため、書き込み自体が通常の処理を妨げるおそれがあります。Raftはコピーオンライトを勧めており、スナップショットをディスクへ書く間もログの追加やリクエスト処理を続けられるようにします。

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

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

Raftが目指すのは、各操作が瞬時に完了し、1度だけ実行されるとみなせる線形化可能な意味論です。ただし、リーダーが命令を実行した後、応答を返す前に落ちることがあります。クライアントが別のリーダーへ再送すると、命令が2回実行される可能性があります。対策として、各クライアントが命令に単調増加する一意の識別子を付け、状態機械は最後に実行した命令の識別子を記録します。実行済みの命令を受け取ったら、再実行せず成功を返します。

読み取り専用リクエストはログへの書き込みが不要なので、毎回クラスタの合意を取らずに処理できます。しかし、合意を取らない間に、自身が気づかないうちに新しい任期のリーダーに交代している可能性があります。その場合、古いデータを返してしまいます。Raftは次の2つでこれを防ぎます。

リーダーは、コミット済みエントリの最新情報を持つ必要があります。リーダー完全性によってエントリ自体の保持は保証されますが、任期の開始時点ではどれがコミット済みか分かりません。そのため、任期の最初に何もしないno-opエントリをコミットして、最新のコミット情報を確定します。
読み取り専用リクエストを処理する前に、自分が今もリーダーであると確認する必要があります。処理前にクラスタの過半数とハートビートをやり取りすれば確認できます。

アルゴリズムの実装

論文のFigure 2には、とても詳しい実装の指針があります。こういうところがRaftのいいところです！なお、メンバー変更とログ圧縮は含まれません。

サーバーの状態

type ServerState struct {
    /***** 所有 Server 都包含的持久状态 *****/
    // CurrentTerm 机器遇到的最大的任期，启动时初始化为 0，单调递增
    CurrentTerm int64;
    // VotedFor 当前任期内投票的 Candidate ID，未投票则为 nil
    VotedFor    *int64;
    // Logs 日志条目，每个条目都包含了一条状态机指令和 Leader 接收该条目时的任期，index 从 1 开始
    Logs        []*Log;

    /***** 所有 Server 都包含的可变状态 *****/
    // CommitIndex 已知的最大的即将提交的日志索引，启动时初始化为 0，单调递增
    CommitIndex int64;
    // LastApplied 最大的已提交的日志索引，启动时初始化为 0，单调递增
    LastApplied int64;

    /******* Leader 包含的可变状态，选举后初始化 *******/
    // NextIndex 每台机器下一个要发送的日志条目的索引，初始化为 Leader 最后一个日志索引 +1
    NextIndex  []int64;
    // MatchIndex 每台机器已知复制的最高的日志条目，初始化为 0，单调递增
    MatchIndex []int64;
}

AppendEntries

type AppendEntriesRequest struct {
    // Term Leader 的任期
    Term         int64
    // LeaderID Follower 可以将客户端请求重定向到 Leader
    LeaderID     int64
    // PrevLogIndex 新日志条目前一个日志条目的日志索引
    PrevLogIndex int64
    // PrevLogTerm 前一个日志条目的任期
    PrevLogTerm  int64
    // Entries 需要保存的日志条目，心跳包为空
    Entries      []*Log
    // LeaderCommit Leader 的 CommitIndex
    LeaderCommit int64
}
 
type AppendEntriesResponse struct {
    // Term Follower 当前任期
    Term    int64
    // Success Follower 包含 PrevLogIndex 和 PrevLogTerm 的日志条目为 true
    Success bool
}

受信側の処理です。

TermがCurrentTermより小さければfalseを返す。
PrevLogIndexとPrevLogTermに一致するエントリがなければfalseを返す。
既存エントリと新しいエントリのインデックスが同じで任期が異なる場合、そのエントリと後続のすべてを削除する。
まだログにないエントリを追加する。
LeaderCommitがCommitIndexより大きければ、LeaderCommitと新しいエントリの最後のインデックスのうち、小さいほうをCommitIndexに設定する。

RequestVote

type RequestVoteRequest struct {
    // Term Candidate 的任期
    Term         int64
    // CandidateId 拉票的 Candidate 的 ID
    CandidateId  int64
    // LastLogIndex Candidate 最后一条日志序列的索引
    LastLogIndex int64
    // LastLogTerm Candidate 最后一条日志序列的任期
    LastLogTerm  int64
}

type RequestVoteResponse struct {
    // Term 当前任期
    Term        int64
    // VoteGranted true 则拉票成功
    VoteGranted bool
}

受信側の処理です。

TermがCurrentTermより小さければfalseを返す。
VotedForがnilまたはCandidateIdで、候補者のログが受信側と同じかそれ以上に新しければtrueを返す。

サーバーの動作規則

すべてのマシンに共通する規則です。

CommitIndexがLastAppliedより大きければ、LastAppliedを1増やし、logLastAppliedを状態機械へ適用する。
RPCのリクエストまたは応答のTermがCurrentTermより大きければ、CurrentTermを更新してフォロワーになる。

フォロワーの規則です。

候補者とリーダーからのRPCに応答する。
現リーダーからAppendEntriesを受け取らず、候補者への投票も行わないまま選挙タイムアウトを迎えたら、候補者になる。投票要求を受け取ることではなく、実際に投票することが条件です。

候補者の規則です。

候補者になったら選挙を始める。任期を1増やし、自分に投票し、選挙タイマーをリセットして、ほかの全マシンへRequestVoteを送る。
過半数の票を得たらリーダーになる。
新しいリーダーからAppendEntriesを受け取ったらフォロワーになる。
選挙がタイムアウトしたら次の選挙を始める。

リーダーの規則です。

リーダーになったら、ほかの全マシンへ空のAppendEntriesを送る。処理がない間も繰り返し送り、選挙タイムアウトを防ぐ。
クライアントから命令を受け取ったらログに追加し、状態機械へ適用してから応答する。
最後のログインデックスがフォロワーのNextIndexより大きければ、NextIndex以降の全エントリを含むAppendEntriesを送る。成功したら、そのフォロワーのNextIndexとMatchIndexを更新する。ログの不整合で失敗したら、NextIndexを1減らして再試行する。
CommitIndexより大きいNがあり、過半数のMatchIndexがN以上で、第Nエントリが現在の任期のものなら、CommitIndexをNに設定する。