リーダーを選ぶルールを自分で書く

目標

3つのプロセスが互いに票を交換して、リーダー1つを選ぶ過程を自分で実装します。終わると、任期(term)、投票、過半数、そしてタイムアウトをなぜランダムにするのかを、手で体験した状態になります。

なぜ重要なのか

合意アルゴリズムが難しい理由は、数式ではなく境界です。任期が同じときと大きいとき、まだ投票していないときとすでにしたとき、票が半分のときと半分を超えたとき。この境界を 1つずれて引くと、システムは普段は問題なく動いているのに、ネットワークが不安定な日に、リーダーを2つ作ってしまいます。そのため、ここでは配線(HTTPサーバー・タイマー・再送)を用意してあり、判断する関数だけをあなたが書きます。判断がそのままアルゴリズムで、残りは配管です。

最後のステップは、Raftの論文がランダムなタイムアウトを導入した理由を、実測で見せてくれます。 3つのノードのタイマーを同じに合わせておくと、3つが同時に候補になり、それぞれ自分に1票ずつ与えて、誰も過半数に届かないまま、任期だけが際限なく上がります。

ステップ

/root/raft/cluster.jsonに、3つのノードのidとポートを書きます。
/opt/lab/raft/node.pyを/root/raft/node.pyにコピーして、1つを起動し、/statusを確認します。
/root/raft/raftrules.pyに、election_timeout_ms(node_id, fixed_ms)を書きます。
同じファイルに、on_timeout(state)を追加します。
同じファイルに、on_request_vote(state, req)を追加します。
同じファイルに、on_append_entries(state, req)を追加します。
同じファイルに、has_majority(votes, total)を追加して、3つのノードを起動し、リーダーが選ばれるのを確認します。
3つのノードを--timeout-ms 900で起動して、結果を/root/raft/split-vote.jsonに書きます。

参考

ノードの起動方法: cd /root/raft && python3 node.py --id 1 --port 5001 --peers 2:5002,3:5003 &
状態の確認: curl -s http://127.0.0.1:5001/status
すべて停止する: pkill -f 'node.py --id'
配線は、ルールファイルにある関数だけを呼び出します。まだ書いていない関数のせいでプロセスが落ちることはありません。
よくあるミス1: 古い任期のリクエストを受け取って、自分の任期をそちらに下げてしまうことです。任期は上がるだけです。
よくあるミス2: 過半数をvotes >= total / 2と書くことです。4ノードで2票が過半数になって、リーダーが2つできます。

3つのノードの配置表

/root/raft/cluster.jsonに、id 1、2、3と、ポート5001、5002、5003を書いてください。

ノードはコンテナではなく、ポートだけが異なるプロセスです。後で3回起動するときに使う配置表を、先に書いておきます。nodesというリストの下に、idとportを持つオブジェクトを3つ置いてください。

配線を所定の場所に置いて起動してみる

/opt/lab/raft/node.pyを/root/raft/node.pyにコピーして、1つを起動し、/statusが応答するかを確認してください。

HTTPサーバーとタイマーのような配線は、すでに作ってあります。あなたが埋めるのは「判断」だけです。python3 /root/raft/node.py --id 1 --port 5001 --peers ''で起動して、別のウィンドウでcurl 127.0.0.1:5001/statusを呼び出してください。ルールファイルがまだないので、何の判断もせずにじっとしているのが正常です。

選挙のタイムアウト

/root/raft/raftrules.pyに、election_timeout_ms(node_id, fixed_ms)を書いてください。fixed_msが0でなければその値をそのまま、0なら800から1500までのランダムな値を返します。

random.randint(a, b)は、両端を含みます。なぜランダムでなければならないのかは、最後のステップで自分の目で見ることになります。fixed_msをそのまま返す道を、必ず残しておいてください。その道がなければ、最後のステップの実験が成り立ちません。

タイムアウトになったら候補になる

raftrules.pyに、on_timeout(state)を追加してください。任期を1上げて、stateをcandidateに、voted_forを自分のidに変えた辞書を返します。

stateは、{'id', 'term', 'state', 'voted_for', 'leader', 'log', 'commit'}を持つ辞書です。変更したいキーだけを入れて返せば、配線が反映します。候補が自分に投票することが、Raftの最初の1票です。これを忘れると、誰も過半数に届きません。

1つの任期に1票

raftrules.pyに、on_request_vote(state, req)を追加してください。term、voted_for、state、grantedを含む辞書を返します。

3つのことを順に見てください。(1)reqの任期が自分の任期より大きければ、自分の任期を上げて退き、今回の任期の投票記録を消します。(2)任期が自分のものより小さければ拒否します。このとき、自分の任期を下げてはいけません。(3)同じ任期では、まだ誰にも与えていないか、同じ候補に与えたときだけ与えます。同じ候補の再送を拒否すると、パケットを1回失っただけで選挙が止まります。

ハートビートを受け取る側

raftrules.pyに、on_append_entries(state, req)を追加してください。term、state、leader、voted_for、okを含む辞書を返します。

リーダーは、話すことがなくても話しかけ続けます。それが「私はまだ生きている」という唯一の合図だからです。reqの任期が自分の任期より小さければ、okをFalseにして返し、自分の任期はそのままにします。それ以外の場合は、フォロワーに戻ってリーダーを記録し、okをTrueにします。候補でいるときに、同じ任期のリーダーを見たら、退かなければなりません。

過半数を数えてリーダーになる

raftrules.pyに、has_majority(votes, total)を追加した後、3つのノードを5001、5002、5003で起動して、リーダーが1つ選ばれることを確認してください。

過半数は、半分「以上」ではなく、半分「超過」です。4ノードで2票は過半数ではありません。整数の割り算で書くと、この境界で間違えやすいので、両辺に2を掛けて比較してください。3つのノードを起動した後、curl 127.0.0.1:5001/statusを3つのポートに対して実行して、stateとtermとleaderを一緒に見てください。

タイマーが同じなら、誰も勝てない

3つのノードをすべて--timeout-ms 900で起動して、9秒後の状態を見て、/root/raft/split-vote.jsonに、fixed_timeout_ms、leader、max_term、statesを書いてください。

--timeout-msを指定すると、配線が3つのノードの目覚める時刻を壁時計に合わせます。タイマーが本当に同じときに何が起きるかを見るための仕組みです。3つが同じ瞬間に候補になると、それぞれ自分に1票ずつ与えて、誰も過半数に届かないまま、任期だけが上がります。leaderはnullと書きます。