Raft

Motivation

覺得Paxos太難懂，所以提出一個新的consensus algorithm。

Main Features

• Leader-based (strong leader)
• Strong consistent
• Role: leader、follower、candidate
• Unidirection log replicated flow

Algorithm

Communication

node之間的communication 是透過RPC (remote procedure call)。

RequestVote

當某個follower跟leader heartbeat timeout了，就會把自己的term 增加(term是一個遞增的值，每一次選舉， term就會改變)，然後發起投票。

AppendLog

只會由leader發給follower，要在log state machine增加一筆。

InstallSnapshot

如果follower 落後leader太多，或是有新加入的node，如果要求的log已經被compact，leader就會要傳snapshot給它們。

Scenarios

Leader Election

因為是strong leader的設計，所以leader的存在很重要，並且整個cluster的log state machine基本上是由leader決定，所以leader election一定要做好。

每個node在一定時間內如果沒收到leader 的heartbeat，就會把自己的term值增加，然後發起election。

其他node收到投票，如果送過來的term比自己本地的還小或一樣，就會reject，比自己的大就會vote，同一個term值每個node只會投一遍，發起投票的會投給自己。

對發起election的node而言，會有三種結果，a)選上、b)別的node選上、c)這次election沒結果。 如果是c)狀況發生，就會在發起一次投票，為了避免node之間不斷地發起投票，然後conflict，每個node會random的產生election timeout，藉此錯開同時發起投票的頻率。

Log replication

當上leader以後，就要想辦法讓整個cluster的state一致。要做到這點首先必須先定義committed。一個request被視為committed且保證durability，只有在它的log已經被majority nodes accept。

因此，如果有個request在commit(可能有幾個)之前，leader就掛掉，那這個request就不保證被寫入log state machine裡面。

而為了保護log state machine的consistency，Raft對leader election做了一個限制，node有最新一筆committed log才有可能當上leader。

為什麼要有這筆限制是因為選上leader以後，新的leader要跟follower align身上的log，如果follower 身上有not committed的log，這些log就會被drop掉，直到找到leader與follower共同有的log，從此log開始，leader在把自己有而follower沒有的log 傳過去sync。

從反證法可以證明，加上這條限制可以保證所有committed的log最終都會被保存不會lost。

Cluster membership Changes

cluster可能會有移除node或是新增node的狀況，Raft演算法有cover這種情境，可以自動化的完成這過程。

我們把cluster的狀態稱為config，轉移之前為$C_{old}$，轉移後的狀態為$C_{new}$，要保證從$C_{old}$ → $C_{new}$中間資料不能遺失，而且也要保證consistency。

Raft採取2 phase的做法，首先先把狀態從$C_{old}$轉移到$C_{old,new}$，也就是要被移除的node還可以收到log，新的node也可以收到log，而且也保證 $C_{old,new}$已經committed。

當以上滿足以後，在從$C_{old,new}$轉移到$C_{new}$，當$C_{new}$被committed，就代表兩步驟完成，這時候就可以移除要被移除的node。

這邊有幾個edge case：

1. new nodes在跟上目前log 之前不能投票，只能接收log，這時間的能投票的狀態還是 $C_{old}$，避免同時選出兩個leader的問題。
2. leader如果本身是要被移除的node，它會在狀態轉為 $C_{new}$以後step down，並發起leader election，在它step down之前的一段時間，它自己本身不算在majorities。
3. 被移除的node在收到$C_{new}$之前，可能就收不到heartbeat，它們會誤以為leader掛了，所以發起leader election，為了避免發生此狀況，每個node在收到新leader剛被選上的一段時間，會reject leader election投票，讓這些node有時間收到$C_{new}$，然後知道自己下線。

Log compaction

每個node會各自做 snapshot，leader只有在某個follower要求的log已經被compacted，才會丟snapshot過去，snapshot裡面會有term 和 log last index的資訊，follower收到以後，就更新snapshot，然後只留下還沒被compact的logs。

各自做snapshot的好處就是leader不用費心去同步snapshot狀況，降低系統設計的複雜度，所以log state machine的一制性是Raft演算法最重要的部分。

limitation

Raft要能work，必須滿足：

$broadcastTime$ >> $electionTiemout$ >> $MTBF$

broadcastTime: leader broadcast RPC 給整個cluster的平均時間

electionTimeout: leader election 的timeout

MTBF: node平均掛掉的間隔

$broadcastTime$ 至少比 $electionTimeout$ 低一個order以上，$MTBF$ 要比 $electionTimeout$高好幾個order才行。

electionTimeout 比broadcastTime 大一個order以上，才可以保證不會 leader election到一半，又timeout，不斷的在leader election。

實務來說，broadcast time通常都是 0.x ms ~ x ms，而 election timeout是 100ms ~ 300ms，而MTBF是幾個月以上，所以Raft演算法的要求使可以被滿足的。