[超初心者向け！] 分散アルゴリズム Raft の Safety を図でわかりやすく解説[その4]
はじめに
recovery phase における Raft プロトコルを解説してみようと思います！
この記事の対象者
・分散トランザクションに興味がある人
・分散アルゴリズムに興味がある人
紹介する論文 / 参考文献
Diego Ongaro, John Ousterhout (2014) "In Search of an Understandable Consensus Algorithm (Extended Version)",https://raft.github.io/raft.pdf
最初から読みたい方はこちらから：
目次
5.0 Raftとは？
5.1 基本情報
5.2 Election
5.3 Log Replication
5.4 Safety
5.4 Safty
今回は Election において、どのフォロワーがリーダーになれるのかについて解説します！
リーダーは committed entries を全て持っている人
committed entries とは？
Election において、過半数のフォロワーのログに反映できたインデックスについては、データベースに保存することができます
この中で、赤枠で囲まれたところは過半数(4 / 7つ中)のログが複製できているため、committed entries であるということができます
リーダーは committed entries を全て持っている人でないといけない
そのため、上から１、２、４、５番目がリーダーになることができます
フォロワーはどうやって票を入れるか否かを判別するか
ここでは2つの例を挙げて、どうやってフォロワーが Candidate からの RequestVoteRPC に対して票を入れるか否かを判別するかを説明します
ここでは、フォロワーと Candidate のログを比較します
Candidate の方が最新であった場合に票を入れますが、フォロワーの方が最新であった場合は票を入れません
Case1: 票を入れる場合
1. Candidate がフォロワーに RequestVoteRPC を送る
Candidate はフォロワーに RequestVoteRPC を送ります
この RPC には最新のログの term数 とインデックスが含まれています
2. フォロワーはリーダーの term 数を比較し票を入れる
フォロワーは自分のターム数とリーダーのターム数を比較します
フォロワーのターム数(river) ＜ Candidateのターム数(risa)なので river は risa に票を入れます
このフォロワー(river)は Candidate(risa) に票を入れる
Case2: 票を入れない場合
1. Candidate がフォロワーに RequestVoteRPC を送る
Candidate はフォロワーに RequestVoteRPC を送ります
この RPC には最新のログの term数 とインデックスが含まれています
2. フォロワーはリーダーの term 数を比較した後、ログの数を確認
フォロワーは自分のターム数とリーダーのターム数を比較します
フォロワーのターム数(tony)＝Candidateのターム数(risa)なので、今度はログの数を確認します
フォロワーのログ数(tony) ＞ Candidateのログ数(risa)となるため、フォロワーの方が最新であると言えます
このフォロワー(tony)は Candidate(risa) に票を入れません
リーダーになれる人
上記を踏まえ、committed entries を全て持ってる Candidate だけが過半数の票を獲得できます
まとめ
・リーダーは全ての committed entries を持っているデータベースから選出される必要がある
・フォロワーは candidate より最新のログを保持していた場合、candidate からの RequestVoteRPC に対して票を入れない
これで Raft の範囲は以上です！
最後まで読んでくださりありがとうございました！
Discussion