前言
- 常在各家產品看到他們對於 cluster 的資訊同步作法，都有提到 Raft；一方面也聽說是因爲 Paxos 太複雜，所以有一個精簡版的做法稱作 Raft。剛好記錄他的相關概念。
Raft 是什麼
- 一種在 Cluster 內同步資訊、凝聚共識 (Distributed Consensus) 的演算法。
目的
所謂共識 Consensus，
是要讓「外部請求達成的狀態 (State) 在 Cluster 內一致 (Consistency)」。
例如，電商後端 Cluster 保存了目前某商品存貨的狀態，
當不同來源的客戶下單後，要能持續讓 Cluster 內的存貨同步更新到正確的數值，
才不會有「客戶順利下訂，結果卻早就沒有存貨」的情況發生。
Raft 共識演算法，就是為了要為了兼顧「一致性」、「HA」 同時還要「單純易懂」
(兼顧？)
Consistency Model 一致性模型
一致性究竟是什麼？
怎樣算是夠一致？
| Model | 說明 |
|---|---|
Strong Consistency |
保證系統都能提供最新、一致的資料 |
Eventual Consistency |
遲早系統會提供最新的資料、但不保證時序與正確性 |
Consistent Prefix |
不一定是最新的資料， 但對於舊資料一定是一致、已 committed 的 (snapshot、isolation 的概念) |
Bounded Staleness |
參數化舊版本資料的容許範圍 bounded = ∞ → 退化成 Eventual Consistencybounded = 0 → 進化成 Strong Consistency |
Monotonic Reads |
會讀到舊資料，但保證只會越來越新 |
Read My Writes |
Client 一定會讀到自己寫入的值、不關心系統如何彼此同步 |
以球賽結果舉例，假設目前進度與比分如下：
| Team \ Round | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Total |
|---|---|---|---|---|---|---|---|---|---|---|
| Team A | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 2 | ||
| Team B | 1 | 0 | 1 | 1 | 0 | 2 | 5 |
各個不同的「聽眾」（透過收音機) 或是「觀眾」(透過電視、網路平台)，
如同 clients，不斷從這個「球賽 Cluster」獲得最新比分的狀態。
所以以各個 Model 來說：
| Model | 說明 |
|---|---|
Strong Consistency |
所有球迷 (client) 都能得到最新比分 |
Eventual Consistency |
遲早所有球迷都能得到最新比分，不保證時序與正確性 |
Consistent Prefix |
得到正確比分，但時序每個球迷接收到的不一定一樣 |
Bounded Staleness |
參數化「所有球迷所能得到比分的老舊版本」程度 |
Monotonic Reads |
會讀到舊比分，但保證越來越新 (保證時序) |
Read My Writes |
計分員視角 |
可以大概想像一些模型的差異：
Monotonic Reads：就如同直播延遲的情況，比分一定正確且照順序，但時間會比較延遲。Eventual Consistency: 就像是搶新聞的記者，相對獲得的資訊會快一些，但有可能須要事後修正。
Raft 的一些性質
-
可以做到 Strong Consistency：也就是以這個演算法同步資訊的 Cluster，
都可以快速獲得最新、最正確的狀態。 -
狀態 (State) 統一由 Cluster 內唯一 Leader 為準，且為 Append Only，
代表資料更新是單向的：Leader 也不能刪除、或去更新原有資料。 -
假設 Cluster 中沒有叛徒 (Non-Byzantine system)
-
提供一個大致的架構 (protocol)，細節可以依需求調整實作方式，
例如實作 timeout 的方式、請求與回傳的資料結構等等
Raft 的 3 個角色、2 個階段
3 個角色：Leader、Follower、Candidate
-
Leader：
- 要求 Follower 更新資料
- Cluster 中會只有一個 Leader
-
Follower：
- 可以對 Candidate 投票，並同意 Candidate 的 ACK
- Cluster 中會有多個 Follower
-
Candidate:
- 接收 Follower 投票、並送出 ACK
2 個階段：Election、Log Replication
- Election：沒有 Leader 時會進入 Election 階段、部分 Follower 會成為 Candidate
- Log Replication：平時溝通、平時的資料更新；不會有 Candidate
一般情況
平時彼此溝通的 Heartbeat：AppendEntries RPC
每一小段時間 (~50ms) Leader 會發送 Heartbeat 給 Follower。
Heartbeat 可包含資料 (Log)，要求 Follower 更新資料狀態，
此動作實際稱為 AppendEntries RPC (Remote Procedure Call)
- 如果有帶資料，就是要求 Follower 要同步 meta 狀態、以及同步資料狀態
- 如果沒有資料就是 Heartbeat，只同步 meta 狀態
如果沒有 Leader … 進入 Election！
如果沒有 Leader，就進入 Election 階段，選出 Leader。
有參選資格的稱作 Candidate；
Candidate 會要求其他 Follower 投票，送出稱為 RequestVote RPC 的請求，
Follower 會回傳投票結果。
但 … 成員要怎麼知道沒有 Leader？
- 當 Follower 超過一定時間 (timeout) 沒收到「來自 Leader 的 Heartbeat」，
就認定現在 Cluster 內部失去了 Leader。
沒有收到 Heartbeat 可能是因為：
- Leader Crash
- 網路出現問題
每個 Follower 會有隨機的 timeout 門檻，範圍大約是 150ms ~ 300ms，
超時之後稱為 electionTimeout。
electionTimeout 後的 Follower 隨即成為 Candidate
所以整個 State 大概如下圖
- 平時只有 Leader 與 Follower 更新訊息
- Leader 不見時會進入 Election，此時才會有 Candidate
Note
- 上面的圖中有提到 new
term、higherterm，稍後會說明
下節詳細說明 Election
Election 階段
當 Follower 觸發 electionTimeout，就會轉為 Candidate。
Candidate 送出稱為 RequestVote RPC 的請求，給各個 Follower 要求投票；
當 Candidate 獲得過半數 cluster 中的投票，就會廣播宣告自己成為 Leader。
在選舉過程中，大家都會記錄一個數值 term，
這是「Cluster 中已選舉的次數」，可以理解為任期編號； term 是單向遞增的數字。
Candidate 角度
當每次 electionTimeout、Follower 成為 Candidate 時，這個 term 就會 +1。
目的是在 Candidate 收到來自其他 Candidate 的 RequestVote 時，
能夠比對誰才是更新的 Candidate。
可以想像一種狀況，某 Candidate A 曾經在某次 Election 時 (例如 term = 10) 壞掉了；
剩下的成員相繼無事，完成選舉選出 Leader。
過一陣子剛好 Leader 失效，在進入下一輪選舉 (term = 11) 時，
A 此時才回來，這時候比對 term 就知道他是先前已過期的 Candidate。
這時候 A 就會放棄 Candidate 的角色。
總而言之，對於某 Candidate 來說，
如果收到對方的 term 「大於等於」 自己的 term，
自己就會放棄選舉，成為 Follower。
Follower 角度
而對其他 Follower 來說，在自己的 term 時，
最多只會投出一票，給第一個向自己拉票的 Candidate。
不過 Follower 會拒絕以下不合條件的 RequestVote：
- 對方
term低於自身term - 如果
term相同但是身上的資料長度比自身短 (代表狀態比較老舊) - 本輪已經同意過一次
一輪選舉結果
一個 Candidate 只會有以下三種情況：
- 要麻獲得過半投票，成為 Leader，然後廣播通知其他 Follower
- 要麻收到新的 Leader 廣播，自己轉為 Follower
- 要麻未能收到任何訊息，然後再觸發一次
electionTimeout，繼續當 Candidate
所以理論上，一個失效的 cluster 是有可能無限等待：
Candidate 會一直在觸發 electionTimeout，卡在選舉循環中。
Note
- 關於
electionTimeout的時間尺度，一般情況大概會是：
| 溝通平均傳遞時間 | electionTimeout |
平均故障間隔 (MTBF) |
|---|---|---|
| 0.5ms ~ 20ms | 10ms ~ 500ms | Days ~ Months |
平時溝通階段：Log Replication
前面提到，Leader 會發送 AppendEntries RPC 給所有的 Follower。
AppendEntries 包含
- metadata：
terms,index(標示手上已 committed 資料的進度) - log entries：實際的資料
如果沒有 log entries (資料)，還是會發送 AppendEntries 給各個 Follower，
當作 Heartbeat，以讓各個 Follower 知道目前 Leader 狀態正常 (約 50ms 一次）。
如果有 log entries 的話，Leader 跟 Follower 可能資料版本不一致，要怎麼同步呢？
Follower 角度
收到來自 Leader 的 AppendEntries，
比對自己手上的與 Leader 傳來的 terms 與 index：
- 如果都一致：則直接更新 (append) 資料
- 如果不一致：則拒絕更新，然後回傳更之前的
index，
來跟 Leader 多次比對「最近一次同步的資料版本」是在哪一個 index；
然後從該版本之後都直接用 Leader 的資料覆蓋。
Leader 角度
Leader 發出 AppendEntries RPC，
並向 Follower 收集 ACK，確認「本次 term」 中、「本次更新」的資料，
都已被多數 (majority) Follower 確認儲存，
本次更新的資料才能算是 Committed。
前面提過，一份資料包含
- metadata (
term,index…) - log entries
一次 term 中 (時間內都沒有發生 electionTimeout 進入選舉階段)，
會有多次資料更新，各個 Follower 會用 index 變數來確認目前儲存進度。
另外，值得注意的是：
- 完成 Commit 的資料才會回傳給 client。
也就是還在確認狀態、未被多數 Follower commit 的資料，
在外部 client 發出請求的時候，cluster 的回應不會包含這些資料。
Log Replication 時各種狀況
在同步資料的過程中，可能會遇到不同的狀況、不同的 Follower 的狀態：
- 方格裡面的數字是
term，代表對應的資料是在哪一輪選舉時更新的。 - 最上方的一排數字是 log
index，代表不同時序的資料 append 的順序 - 左邊
(a)~(f)是不同情況的 Follower，以下分別說明
(a) Follower 資料落後一版
Follower 與 Leader 都是在同一輪選舉中 (term = 6)。
Follower 在收到來自 Leader 的 AppendEntries 時，
會發現自己少了 index = 10 的資料，隨即補上 Leader 的新資料。
(b) Follower 資料嚴重落後
Follower 在先前的選舉 term = 4 時就失效了，現在才回來。
在收到來自 Leader 的 AppendEntries 後，
會發現自己的 log index 停留在 4，
隨即補上 Leader 的新資料：index 5~10。
(c) Follower 超前資料
與 Leader term 相同；
資料狀態必須以 Leader 為準，超出的資料就直接丟棄。
所以此 Follower 必須捨棄 index = 11 的資料。
(d) Follower 的 term 比 Leader 還更新
代表現在的 Leader 是過時的 Leader，
此時用有更新的 term (= 7) 的 Follower，
會取而代之，直接變成新的 Leader。
原有的 Leader 轉為 Follower，
然後要把落後的 term = 7 的資料補足。
(e) Follower 的資料落後，而且版本不一致
此 Follower index = 6 & 7 的資料跟 Leader 不一致，
還停留在該 term = 4 的階段。
當接收到 Leader 的 AppendEntries RPC 後，
就會發現狀態在 index = 6 開始不一致。
此時就要捨棄原本 index = 6 以後的資料，
跟 Leader 的資料對齊。
(f) Follower 身上有很多過時資料
這有可能是先前已經失效的 Leader，身上有 term = 2 & 3 的資料。
一加入這個 cluster，馬上就會發現 index 從 4 ~ 11 都是過時的，
因為與 Leader 相比，term 完全不同。
此時就會在 AppendEntries RPC 之後把跟現在 Leader 不同的資料都捨棄，
以 Leader 的資料為準。
也就是 index = 4 ~ 11 的資料都替換成 Leader 身上的版本。
補充
當資料增長 … Snapshot
當資料大到一定程度時，
可用 Snapshot 將舊資料另外保存，以縮小現有的 Log Entries。
當成員需要更新 … Joint Consensus
Cluster 的成員如果需要更新，例如更新版本、或更新設定檔等，
需要使用兩階段 commit 的方法來確保系統的安全性、與資料正確性。
這兩階段可以有多種實作方式：
例如，某些系統會在第一階段禁用舊設定，停止處理 client 的請求，
然後在第二階段啟用新設定。
而在 Raft 中，系統先切換到一個稱為 Joint Consensus 的過渡性狀態，
當該所有成員的設定都換成新設定後，再恢復原本的同步流程。
這樣的做法是為了避免中斷服務。
Joint Consensus 簡單來說是：
將新舊版的 Server 都納入當前的運作；並且 log entries 會同時紀錄新舊的版本狀態，
方便 cluster 辨識不同狀態的成員，以及同步資料。
在過程中，只有同時具備新舊資料狀態的成員才有可能被選為 Leader。
動畫幫助理解
可以參考這兩個站，
第一個可以依照自己想看的情境去測試 Raft 的運作；
第二個是一個教學流程，看完可以先有比較直觀的理解。
CAP 定理？
CAP 定理是指 ：
一個分散式系統不可能同時滿足以下三點：
- 一致性（Consistency）：所有節點訪問同一份最新的資料副本
- 可用性（Availability）：每次請求都能獲取到非錯的響應——但是不保證獲取的資料為最新資料
- 分區容錯性（Partition tolerance）：以實際效果而言，分區相當於對通訊的時限要求。系統如果不能在時限內達成資料一致性，就代表著發生了分區的情況，必須就當前操作在 C 和 A 之間做出選擇。
(wiki，經調整用詞)
Raft 保證了 C、P；
而 A 的部分乍看也有被保證？
但從定理得知，這是不可能兼顧的。
實際上 A 是犧牲了一部分的機率，
也就是沒辦法達成 100% 的 A：
在選舉的過程中，理論上是有可能無限等待的；
等於是用一部分機率的 A 來保證 100% 的 C、P。