同じ順序で命令を適用する
Raftは、複数ノードが同じ順序のログを合意し、状態機械へ命令を適用するための合意アルゴリズムです。leaderが命令を受け付け、followerへログを複製します。termは選挙などで進む論理的な番号で、実時間の秒数ではありません。各entryには位置であるindexとtermがあり、どの履歴に属するかを判断する材料になります。ここでは故障して停止・復帰するノードを想定し、相手が意図的に偽のデータを送るビザンチン故障の解決策として説明しません。
複製ログは、ノードごとに都合のよい順番で同じ命令を実行する仕組みではありません。例えば残高へ10を加える命令と、残高を2倍する命令は、適用順で結果が変わります。同じ初期状態から同じ順番で決定的な命令を適用することが、状態機械をそろえる前提です。外部APIの現在時刻や乱数を各ノードが勝手に読むなら、ログが同じでも同じ結果になるとは限りません。非決定性をどの段階で確定するかもアプリが設計します。
5台なら3台が過半数
5台のクラスタでは、過半数は3台です。現termのentryをleader自身と2台のfollowerが所定の条件で保持すれば、そのentryをコミットできる段階へ進めます。leaderと1台だけでは過半数に達しません。また「どこか3台にある」だけで、以前のtermの任意のentryを単純にコミットしてよいという規則ではありません。Raftは現termのentryとログの性質を組み合わせて安全性を保ちます。保存した事実、コミットした事実、アプリの状態へ適用した事実を同じ時点として扱わないようにします。
応答するノードは、Raftが要求する永続状態を適切に保存する必要があります。受信したentryが一瞬メモリに存在しただけで、再起動後にも必ず残るとは言えません。またleaderがcommitIndexを進めた後でも、followerが新しいコミット位置を知り、状態機械へ適用するまでには差があります。利用者へ成功を返す時点は、その状態機械の契約と合わせて決めます。通信の往復、保存、コミット、適用の四つを時系列上で分けて描きます。
食い違う末尾を直す
leaderはAppendEntriesで、直前のindexとtermがfollower側と一致するかを確認します。対応する位置の履歴が合わなければ、共通の部分まで戻って整合するログを送ります。未コミットの末尾が残っていたノードが復帰しても、その末尾が必ず最終結果になるわけではありません。新しいleaderの選挙にはログの新しさに関する条件があり、単に最も早く立候補したノードへ全履歴を任せる方式ではありません。時刻が大きい端末ほど正しい、という説明でもなく、termとログの規則で考えます。
ログの新しさを比較するときは、まず最後のentryのtermを比べ、同じならindexを比べます。単にentryの個数が多い候補者なら誰でもよいわけではありません。過去のleaderが残した長い未コミットの末尾より、新しいtermの適切な履歴を持つ候補者を優先する場面があります。投票先を制限する規則と、各termで一票という永続的な記録が、選挙とログの安全性を結び付けます。投票だけを別の多数決として切り離さないことが大切です。
合意があっても待ちと再試行は残る
過半数と通信できない側は、新しい書込みを安全にコミットし続けられるとは扱いません。可用性と安全性を切り分けます。またleaderと名乗るノードから読むだけで、常に線形化可能な最新値を得られるとは限らず、現在の権限やコミット・適用の進捗を確認する読取り手順が必要です。クライアント応答が失われる場合は、同じ命令の再送を重複実行しないための要求識別もアプリ側に必要になります。Raftがログを合意することと、業務処理の全障害を自動で解決することは別です。
古いleaderは、他のノードで新しい選挙が起きたことを通信なしにはすぐに知れません。したがって「自分はleaderだと思っている」というローカル状態だけで読み取りを返すと、古い状態を最新として返す可能性があります。線形化可能な読み取りには、現時点での権限の確認と必要なコミット位置までの適用など、採用方式の手順を満たす必要があります。リースを使う方式なら時計や時間に関する追加の前提も確認し、基本のログ複製だけの保証と混同しません。
任期と位置を分けた小さなログ例
5台の構成で、Aをterm4のleaderとします。Aがindex8、term4の命令を自分とB、Cへ所定の永続化条件で複製し、Raftの条件に従ってコミットしたとします。このときDとEへまだ届いていなくても、現termのentryを過半数が保持する条件を満たせます。Dが後から復帰したら、直前のindexとtermを照合しながら必要なログを受け取ります。一方、index8のtermが過去のterm3だった場合に、「3台に保存した」という理由だけで同じコミット規則を適用してはいけません。現termのentryをコミットすることで以前のentryを間接的に確定する扱いを含め、論文の条件を追います。番号が大きいことと、安全にコミットできることは別です。この例は規則の説明であり、本番クラスタの障害実験の結果ではありません。
障害後の再試行を業務へ接続する
利用者が「残高へ10を加える」という命令を送り、適用後に応答だけが失われた場合を考えます。利用者は失敗と判断して同じ要求を再送するかもしれません。Raftはログの順序を合意できますが、その再送が同じ業務要求か、新しく10を加える依頼かを自動では決めません。クライアントIDと要求番号などを命令に含め、処理済みの番号と結果を状態機械の一部として管理すれば、再送へ同じ結果を返す設計を検討できます。ただし記録をいつ削除するか、クライアントが番号を再利用しないかも条件です。ログ圧縮やスナップショットにも必要な重複排除状態を含めます。合意の正しさと、外部APIに対する一回限りの副作用の実現を、それぞれの境界で説明します。
状態機械と再送の演習
全て適切な条件でcommit済みの三命令を、残高5の同じ初期状態へ順に適用する課題です。位置1は(client-A, request-1)の加算10、位置2は同じIDと内容の再送、位置3は(client-A, request-2)の2倍です。処理済みIDと結果も状態の一部として保持すると、残高は15、15、30と進みます。位置2を別の加算として実行して25へ進めると、再送の業務効果を二重にしています。
解答ではログへ命令が三つあることと、業務の加算を二度行うことを区別します。全レプリカが同じ処理済み記録と決定的な適用規則を使う必要があります。snapshotへ残高30だけを入れ、IDの記録を失った後にrequest-1が再送されたら、過去の加算を再実行する危険があります。残す記録の期間と再送の契約を合わせてください。この演習は合意済み入力から状態を計算する模型で、選挙や実クラスタの障害を試したものではありません。
| 位置 | 命令 | 適用後の残高 |
|---|---|---|
| 1 | request-1: +10 | 15 |
| 2 | request-1: 同じ再送 | 15 |
| 3 | request-2: ×2 | 30 |