『Paxos vs Raft: Have we reached consensus on distributed consensus?』

Multi-Paxos も Raft も single-leader なアルゴリズム。

Multi-Paxosはリーダになるときに完全なログを要求しないがRaftは完全なログを要求するところが主な違い。これによりリーダのログの復元作業を省略できる Raft のほうが理解しやすくなっている。

Multi-Paxos を Raft の用語を使って再定義している。(Multi-Paxos のオリジナルをあんまり知らないので Multi-Paxos の特徴を保存しているのかわからない)

RequestVote が Multi-Paxos と Raft で異なっている。

Multi-Paxos

RequestVote のレスポンスで、candidate の commitIndex 以降のログをもらう

各ノードから集まったログを見て、各インデックスについて最も大きい term のログエントリを採用

そのログエントリの term を currentTerm で上書きしてログに追加 (入れ替え)

つまり、リーダからくるログエントリは、その Term のものか、コミットされたものになる

以下の場合にどうなるかわからない

3ノードで、ログはそれぞれ以下の状態になっている

[(1, A) | (2, B), (2, C)]

[(1, A) | (3, D)]

[(1, A) | .. ]

2番目のノードが candidate になって、1番目のノードから commitIndex 以降のログをもらったとき、どうなる？以下のうちどれ？

一番長いやつのログ。これは論文の記述の「最も大きい term のログエントリを採用」していることにならないからないはず

一番ありそう

B が消えて C が残るのは、うーん。でも Multi-Paxos なのでいいのか？

このような状態には絶対ならない

これはない。1番目のノードが3番目のノードの vote をもらって leader になり2つのログエントリをクライアントからもらったが複製に至る前に2番目のノードが3番目のノードの vote をもらって leader になり1つのログエントリをクライアントからもらうとこのケースになる

より正確にはログが以下の状態になる

[(1, A) | (4, B), (4, C)]

[(1, A) | (5, D)]

[(1, A) | ]

どれでもいい

ありそう。どれになっても safety は壊れない気がする => さすがに1番目のだと壊れるかも

コミットが遅いやつが candidate になって、そいつがより新しい Term のエントリを持っていたらどうなる？たぶんこのケースはありえないと思うけど。

つまり、

[(1, A) | (2, B)]

[(1, A) | (2, B)]

[ | (3, C)]