過半数が受け取って初めてコミットだ

目標

リーダーが受け取った値が、どのように3つのノードに広がり、どの瞬間に「確定」されるかを、ルールとして書きます。終わると、ログの一致性、上書き、コミットの条件、そして遅れたノードがキャッチアップする過程を、手で体験した状態になります。

なぜ重要なのか

複製は、「値を複数の場所に送る」ことではありません。送ったものと、確定したものを区別することです。リーダーが値を受け取って自分のログに書き込んだという事実は、何も保証しません。そのリーダーが次の瞬間に落ちると、その値はなかったことになるかもしれません。過半数が同じ位置に同じエントリを持っていて初めて、「どんな未来のリーダーも、この位置を変えられない」が成り立ち、そのときになって初めて、クライアントに成功と伝えられます。

コミットの条件には、人がほとんど必ず見落とす但し書きが、もう1つ付きます。リーダーは、自分の任期のエントリが過半数に届いたときだけ、コミット番号を上げます。前の任期のエントリが過半数に届いたという理由でコミットすると、その後に選ばれた別のリーダーが同じ位置を上書きして、すでに確定したと伝えた値が消えることがあります。

ステップ

node.pyとrules-for-replication.pyを所定の場所に置いて、リーダーを選出し、/root/raft/leader.jsonに書きます。
raftrules.pyにup_to_dateを追加して、on_request_voteがその条件も一緒に見るようにします。
/root/raft/raftlog.pyに、append_entry(log, term, value)を書きます。
同じファイルに、log_ok(log, prev_index, prev_term)を追加します。
同じファイルに、apply_entries(log, prev_index, entries)を追加します。
同じファイルに、commit_index(counts, total, log, term)を追加します。
値を3つ書いて、3つのノードがすべてコミットするのを確認し、/root/raft/replicated.jsonに書きます。
フォロワーを1つ落として復活させ、キャッチアップするのを確認して、/root/raft/catchup.jsonに書きます。

参考

このラボは60分前後かかります。セッション時間が足りなければ、画面から延長してください。ラボのPodにはボリュームがないので、セッションが終わると/rootの成果物が消えます。残したいコードは、別にコピーしておいてください。
値の書き込み: curl -s -XPOST -d '{"value":"x"}' 127.0.0.1:5001/client
ログの確認: curl -s 127.0.0.1:5001/log
状態の確認: curl -s 127.0.0.1:5001/status(commitとlog_lenを一緒に見てください)
よくあるミス1: エントリのないハートビートでも、ログを切り落とすことです。食い違うときだけ切り落とします。
よくあるミス2: 渡されたログのリストを、その場で書き換えることです。新しいリストを作って返してください。

前のラボの結果を再び立ち上げる

/opt/lab/raft/node.pyと/opt/lab/raft/rules-for-replication.pyを、/root/raft/node.pyと/root/raft/raftrules.pyとして配置し、3つのノードを起動して、選ばれたリーダーを/root/raft/leader.jsonに書いてください。

ラボは毎回新しいPodで始まるので、前のラボで作ったものは残っていません。選挙のルールは、前のラボの答えをそのまま用意してあります。leader.jsonには、leaderとtermの2つのキーを書いてください。

遅れた候補には票を与えない

raftrules.pyにup_to_date(log, last_index, last_term)を追加し、on_request_voteが票を与える前に、その条件も一緒に見るように修正してください。

ログができると、選挙に条件が1つ加わります。候補のログが自分のものと同じくらい新しくなければ、票を与えません。比較は、長さが先ではありません。最後のエントリの任期をまず見て、それが同じときだけ、長さで決めます。この条件がないと、遅れたノードがリーダーになって、すでにコミットされたエントリを上書きしてしまうことがあります。

クライアントの値がログに付く

/root/raft/raftlog.pyに、append_entry(log, term, value)を書いてください。termとvalueを持つエントリを末尾に付けた新しいリストを返します。

エントリには、値だけでなく、そのときの任期が一緒に付きます。その任期が、後で2つのログを比較する唯一の根拠になります。渡されたリストをその場で書き換えずに、新しいリストを作って返してください。配線が原本を別に持っています。

ログの一致性

raftlog.pyに、log_ok(log, prev_index, prev_term)を追加してください。prev_indexの位置の任期が、prev_termと同じかどうかを判定します。

Raftは、ログ全体を比較しません。1つの位置が合っていれば、その前はすべて同じと見なします。その性質を、ログの一致性(Log Matching)といいます。prev_indexは1から数える位置番号で、0は「直前の位置がない」という意味です。自分のログがprev_indexより短ければ、比較するもの自体がありません。

食い違う位置から切り落とす

raftlog.pyに、apply_entries(log, prev_index, entries)を追加してください。食い違う位置に出会ったら、その位置から切り落として、新しいエントリを付けたリストを返します。

要点は、「いつ切り落とさないか」です。同じ任期の同じエントリがもう一度届いただけなら、後ろに手を触れてはいけません。再送が頻繁な環境で毎回切り落とすと、フォロワーのログが短くなったり長くなったりを繰り返します。エントリが1つもないハートビートも同じです。

コミットの条件

raftlog.pyに、commit_index(counts, total, log, term)を追加してください。countsは各サーバーが持つエントリの数で、過半数が持っていて、かつその位置が現在の任期のエントリである、最も高い番号を返します。

「過半数が複製していればコミット」だけでは足りません。前の任期のエントリが過半数に届いたという理由でコミットすると、その後に選ばれたリーダーが、その位置を別のエントリで上書きすることがあります。論文の図8の事故です。そのため、リーダーは自分の任期のエントリが過半数に届いたときだけ、コミット番号を上げ、そのとき、前のものも一緒に付いてきます。

3つのノードに値を書く

3つのノードを起動し、リーダーに値を3つ書いて、3つのノードすべてでcommitが3になるのを確認した後、/root/raft/replicated.jsonに、values、commit、log_lenを書いてください。

値は、リーダーにだけ書きます: curl -s -XPOST -d '{"value":"x"}' 127.0.0.1:5001/client。フォロワーに送ると、拒否しつつ、リーダーが誰かを教えてくれます。書いた直後は、commitがまだ上がっていないのが正常です。フォロワーの応答が戻って、次のハートビートが出ていって初めて、反映されます。

復活したノードがキャッチアップする

フォロワーを1つ落として復活させ、空のログから3つ分をキャッチアップするのを確認して、/root/raft/catchup.jsonに、node、log_len、commitを書いてください。

この練習用の実装は、ログをディスクに残しません。そのため、復活したノードは何も知らない状態で戻ってきて、リーダーが送る位置番号を1つずつ後ろに戻しながら、合う地点を探して、そこから埋めてくれます。落とす方法は、pkill -f 'node.py --id 2 'のように、番号まで指定すれば済みます。復活させた後、log_lenが上がるのを、自分の目で見てください。