Raft

ログの複製とか

ログはコマンド列でもなんでもいい。なんかエントリの列。

主に state machine replication ができるアルゴリズムとして使われることが多い

一貫性重視

いい感じにメッセージが失われてリーダがなかなか決まらないとかのときはアクセスできなくなる

コマンドは必ずリーダを経由するのでそこがボトルネック

KVS みたいなシステムだと、Write はリーダを経由して合意させ、Read は Raft のコマンドにはせず各ノードで閉じて処理する場合が多い

ただしこの場合は古い情報を取得する可能性がある

https://www.youtube.com/watch?v=uXEYuDwm7e4

がコードがフルで書いてあってわかりやすいと思う (論文とは用語が違うけどこっちのほうがわかりやすい気がする)

違い

original

=> Martin Kleppmann さん版

備考

log index が1始まり

=> 0始まり

prevLogIndex

=> prefixLen

インデックスを0始まりにした影響で、なにもログがない場合を数値で表現できなくなった

prevLogTerm

=> prefixTerm

entries

=> suffix

持っているログを prefix、もらうログを suffix としている

nextIndex

=> sentLength

commitIndex

=> commitLength

インデックスを0始まりにした影響

lastApplied

=> なし

follower は AppendEntries を受け取って leaderCommit > commitLength であるときに deliver してそのまま commitLength を更新するので、lastApplied を管理する必要がない

leader は AppendEntries のレスポンスを受け取って ackedLength からそのインデックスを受け取ったフォロワーが過半数を超えたときに deliver して commitLength を更新するので、lastApplied を管理する必要がない

nextIndex

=> sentLength

リーダが、各フォロワーについて、ここまで送ったと思っている値 (持っているかは別で、それは ackedLength で管理)

matchIndex

=> ackedLength

リーダが、各フォロワーについて、ここまでログを受け取ったと知っている値

AppendEntries のレスポンスに、どこまでのログを持っているかの情報がない

=> AppendEntries のレスポンスに、どこまでのログを持っているかの情報がある (ack)

これがないと nextIndex, matchIndex を適切な値にできない

ログの上書きがあってもいいんだっけ

prefixLen と prefixTerm が合致していれば OK？

合致していたらそこまでのログはリーダと同じということになる (Log Matching)

それ以降のログは上書きされている可能性があるが、success=true になるので、上書きしたあとのログの長さを返せば OK

合致していなかったとき ack は何を返せばいいかわからない気がする

動画では success=false のときの ack は 0 を返しているが、false のときリーダは ack を使っていないから OK

実際は最後の State Machine Safety だけが重要で、ほかはその補題的な感じな気がする

Election Safety

タームごとにリーダはたかだかひとり

あるタームでリーダになるためには過半数から承認を得なければいけない、かつそのタームでは他の candidate は承認しない。よってあるノードがリーダになった (過半数のノードがそのノードに投票した) 場合、他のノードは過半数の投票がもらえずにリーダにはなれない

Leader Append-Only

リーダはエントリを上書きしたり消したりしない。新しいエントリを追加するだけ

実装がそうなっているので自明と思う

そうなるように実装しなければならない

上書きしたりするのは follower だけ

Log Matching

2つのログが同じインデックスおよびタームのエントリを持つとき、2つのログのそのインデックスまでのエントリは等しい

なんで？

補題: 最新インデックスが異なるタームのときに同じタームのエントリを追記できない

長さが等しい2つのログ L1, L2 を用意する。L1, L2 の最新インデックスのタームは等しくない、とする。

L1, L2 の長さは異なってなくていいの？=> 同じインデックスのエントリのタームについて着目したいので、(長さが同じになるタイミングが違っていても) 結局長さが同じになるまでログエントリを追記しないといけないので同じにしても一般性を失わない

あるインデックス i は最新インデックスでないといけないの？=> 最新インデックスじゃなくてもいいけど、結局そのインデックスの次のインデックスが同じタームにならなければいけないならそのインデックスを最新インデックスとすればいいし、次のインデックスが異なるタームでいいなら同じタームになる直前は異なるタームになるのでそれを最新インデックスとすればいい。ので一般性を失わない

L1の最新インデックス (i) のタームをT1、L2の最新インデックスのタームをT2 (ただしT1 != T2) とする

L1, L2 に同じターム (Tとする) のログエントリを追記するためには、...T1, T, ...というログを持つリーダと、...T2, T, ...というログを持つリーダがどこかのタームで存在しなければいけない (ログはリーダのログが複製されるため)

タームTにおけるリーダがインデックス i においてT1のエントリを持つとすると、Leader Append-Only なので、そのターム中はそのリーダはインデックス i でT2のログを持てない

また、Election Safety により、同じタームで異なるリーダは選出されない

よってTのエントリを L2 のノードに追記させるためには、ターム T' (T' != T) のリーダが...T2, T, ...というログを持たなければいけない

ターム T' のリーダが ...T2, T, ... というログを持つためにはターム T のリーダによってログを追記させられなければいけないが、ターム T のリーダのインデックス i のエントリのタームは T1 であり、アルゴリズムによると直前のエントリのタームが異なる場合はリーダのものに上書きされるので、ターム T' のリーダは ...T2, T, ... というログを持つことができない

なので「L1, L2 に同じターム (Tとする) のログエントリを追記するためには、...T1, T, ...というログを持つリーダと、...T2, T, ...というログを持つリーダがどこかのタームで存在しなければいけない」を満たすことができないので、最新インデックスが異なるタームのときに同じタームのエントリは追記できない

着目するインデックスについての数学的帰納法で証明する

(i=0) ログエントリは1つしかないのでそこまでの2つのログは等しい (空リスト)

(i=k+1) 帰納法の原理から、i=k について成り立つと仮定できる (i=k でタームが等しいなら i=0~k-1 のログエントリは等しい)

インデックス k でログエントリのタームが等しくない場合、補題よりインデックス k+1 において等しいタームのエントリを追記できないので、前提 (インデックス k+1 においてログエントリが等しい) と矛盾する

インデックス k でログエントリのタームが等しい場合、

ログエントリの中身が等しい場合、仮定から i=0~kまでのログエントリは等しいので、i=0~k+1 までのログエントリは等しくなり主題は成り立つ

ログエントリの中身が等しくない場合

アルゴリズムから、リーダからの AppendEntries 時にエントリはインデックスが指定されて Append されるので、同じタームのエントリなのにインデックスがずれるなどは起こらない (ログエントリのインデックスは、ターム T のリーダがログに追記した時点でのインデックスに固定される)。ので矛盾

自信なし

Leader Completeness

リーダとして選出された候補者は、コミットされたすべてのログエントリを持つ

<=> コミットされたログエントリをすべて持っていないとリーダになることができない

リーダになるためには、リーダが持っているログの最新エントリのインデックスとタームについて過半数のノードから承認を得なければいけない

インデックスとタームが、RequestVote を受け取ったノードのログの最新のエントリのものかより新しいものであるならOK

RequestVote を受け取ったノードの最新エントリのタームとインデックスと candidate のものを比較して、タームが新しいか、同じタームならインデックスが同じか新しい、ならOK、ということ

ログエントリがコミットされているということは、そのログエントリは過半数のノードから Ack をもらっているということ

コミットされたログエントリを少なくとも1つ持っていないということは、最も進んでいるコミットインデックス (i_max) を持つノードのログの部分列 (i=0..k) を持ち、i=k+1..i_max はログエントリがないかコミットされていないエントリ (タームが異なるエントリ) になっている、ということ

ログの途中でコミットされていないエントリを持つことはない。そのようなエントリがあったとすると、その次のエントリもコミットされていない状況でないと Log Matching に矛盾するが、そうするとログの途中だけコミットされていない (その次はコミットされている) ということと矛盾する。

最も進んでいるコミットインデックスを持つノードのコミットインデックスを i+k として、コミットインデックスが i であるようなノードがリーダになれないことを示す

(候補者が i+1 のログエントリを持っていない場合)

最新エントリのインデックスが i でタームが T である

コミットが進んでいるノードがあるということは、そのノードが持っているログエントリが過半数のノードに配られたということ

ということは、それらのノードのインデックスは進んでいて、かつそれらのノードの最新エントリのタームは T と同じかより進んでいるものになる

なので、候補者には投票しない

過半数のノードが投票しないので、リーダにはなれない

(候補者の i+n のログエントリがコミットされていないものである場合)

最新エントリのインデックスが i+n でタームが T である

i+n まで進んでいるということは、n 個分のエントリを、k 個のコミットされたログエントリを持つノードには配らずに配ったリーダがいたということになる (あるいは k 個のコミットされたログエントリで上書きされた)

(T がコミットされたログエントリのタームよりも新しい場合)

コミットされたログエントリを持つノードがいる状態で n 個分の AppendEntries をするリーダがいたということ

しかし、その状態で古いエントリしか持たない状態でリーダになることはできない (候補者が i+1 のログエントリを持っていない場合を参照) ので、この場合はありえない

(T がコミットされたログエントリのタームと同じ場合)

Log Matching により、n 個分のエントリはコミットされたエントリと等しいはずなので矛盾

(T がコミットされたログエントリのタームよりも古い場合)

T が古い場合は、T が古いのでコミットされたログエントリを持つ過半数のノードから承認を得ることができないのでリーダにはなれない

上の証明にはこの補題が必要: 過半数のノードから Ack をもらったログエントリは削除されたり上書きされたりしない (リーダによりコミットされていなくても)

過半数のノードから Ack をもらったログエントリを上書きするためには、そのインデックスのエントリを持っていないノードが新しくリーダになって、新しいエントリで上書きする必要がある

しかし、そのインデックスのエントリを持っていないノードは、そのエントリを持っている過半数のノードから承認をもらえないので、リーダにはなれない

候補者の最新エントリのタームが過半数のノードから承認をもらったエントリのタームよりも新しくはない、ということを言わないといけない

タームが新しいということはリーダになったノードがいるということだがそのようなノードはリーダになれない

…ということを繰り返す

たぶん帰納法 (逆向きっぽいので余帰納法？終わりあるけど)

Crash-Recovery モデルだとして、ログが追記されたら即永続化しないといけない

コミットするまで永続化しないとすると、コミットするまでにログが失われるとすべてのコミットされたエントリを持たないノードでもリーダになることができてしまう

State Machine Safety

Raft の各ノードは同じコマンド列を同じ順番で実行する

ノード内でのログエントリの状態

ログエントリがない

ログエントリがあるがコミットはされていない

この状態のログエントリは破棄されうる

リーダがコミットしたら、次の AppendEntries でフォロワーに通知されてコミットできるようになる

リーダは過半数のノードにログエントリが追記されたということがわかったらコミットできる

コミットはされているがアプリケーションに deliver されていない (状態機械に適用されていない)

ここまでいったらログエントリは破棄されない

アプリケーションに deliver されている