📑

[超初心者向け！] 分散アルゴリズム Raft の Election を図でわかりやすく解説[その2]

2024/06/24に公開

はじめに

recovery phase における Raft プロトコルを解説してみようと思います！

この記事の対象者

・分散トランザクションに興味がある人
・分散アルゴリズムに興味がある人

紹介する論文 / 参考文献

Diego Ongaro, John Ousterhout (2014) "In Search of an Understandable Consensus Algorithm (Extended Version)",https://raft.github.io/raft.pdf

最初から読みたい方はこちらから：

5.2 Election

今回扱うところは Election の範囲です！(オレンジの矢印)

具体的な流れ

以下の3つのいずれかの状態になることで Election が終了します

Case1. 自分が選挙で勝利
Case2. 他のサーバが勝利
Case3. 勝利が確定しないまま期間が過ぎた

Case1&2 自分が選挙で勝利 / 他のサーバが勝利

0. いつ Election が始まるか

Operation 時にリーダーのデータベースが壊れてしまい RPC が途絶えた時

残りのフォロワーからリーダーを選ぶ Election が開催されます

リーダーがいなくなることで Election が開催される

1. フォロワーが立候補

フォロワーが立候補し、 Candidate になります
Candidate は自分自身に1票入れます

Candidate は自分自身に1票入れる

2. Candidate が他のフォロワーに RequestVoteRPC を送る

Candidate はフォロワーに RequestVoteRPC を送り、投票のリクエストをします
フォロワーは状況に応じて投票します

Candidate は自分の票も含め過半数となる 3票を得たためリーダーとなる
過半数の票を得ることにより Candidate はリーダーになることができます

Case3. 勝利が確定しないまま期間が過ぎた

例えば候補者が多過ぎた場合、リーダーが決まらない可能性があります

リーダーが決まらない例
無限に Election を繰り返さないために Raft には timeout という仕組みがあります

timeout って何？

フォロワーがリーダーの死を認識するまでの時間で、それぞれランダムに割り当てられます
例えばフォロワーの timeout が 200ms と設定されていてリーダーからの RPC が 200ms こなかったら、リーダーはいないと認識し Candidate になるということです

リーダーは timeout までに RPC を送る必要がある

1.リーダーが死ぬ

リーダーが死ぬことによって RPCが途絶えます
フォロワーが timeout することでリーダーの死を認識し、Election が開催されます

2. 2人のCandidate の誕生

timeout までにリーダーからの RPC がないため Candidate となり、自分自身に1票入れます
そして Candidiate はフォロワーに RequestVoteRPC を送ります

まず river → tony に、jo → Tom に RequestVoteRPC を送信

3. 2人とも 2票ずつ得る

tony → river に、Tom → jo に vote します
これにより river, jo は2票ずつ得るため、過半数とならずリーダーが決まらないまま Election が終了します

river: 2票、jo: 2票となるためリーダーが決まらない

4. 再度 Election を行う

Election を新しく行うため、term数を1つ増やし更新します (term2 → term3)
この際 timeout も再度ランダムに割り当て、全員フォロワーに戻ります

timeout は再度ランダムに割り当てられる
リーダーが決まるまで Election が開催されます

このように timeout を Election 毎にランダムに割り当てることにより Election が無限に開催されることを防ぎます

まとめ

・リーダーはフォロワーに RPC を送り続ける
・フォロワーが Election timeout の間にRPCを受け取らない場合、Candidate になる
・過半数を集めたらリーダーになる
・リーダーが決まらない場合、再度 Election を行う

最後まで見てくださりありがとうございました！
次回は 5.3 Log Replication です！