硬核演算法丨raft演算法簡介

raft演算法是Paxos演算法的工程實現,主要特點就是透過較為簡單的演算法實現分散式系統的資料一致性和高可用,Raft透過選舉一個領導人,然後給予他全部的管理複製日誌的責任來實現一致性。

Raft演算法中,任何伺服器都可以扮演下面的角色之一:

1、領導者(leader):

處理客戶端互動,日誌複製等動作,一般一次只有一個領導者。

2、候選者(candidate):

候選者就是在選舉過程中提名自己的實體,一旦選舉成功,則成為領導者。

3、跟隨者(follower):類似選民,完全被動的角色,這樣的伺服器等待被通知投票。

他們之間的身份變化如下圖:

硬核演算法丨raft演算法簡介

【leader選舉】

1、初始狀態下叢集中的所有節點都處於 follower 狀態。

硬核演算法丨raft演算法簡介

2、某一時刻,其中的一個人 follower 由於沒有收到 leader 的 heartbeat 率先發聲 election timeout 進而發起選舉。

硬核演算法丨raft演算法簡介

3、只要叢集中超過半數的節點接受投票,candidate 即將成為切換點 leader 狀態。

硬核演算法丨raft演算法簡介

4、成為 leader 節點之後,leader 將定時向 follower 節點同步日誌併發送 heartbeat。

硬核演算法丨raft演算法簡介

【日誌複製】

raft協議的 log replication 有點類似 2PC ,但是不同的是raft只要求大多數節點的回覆即可,raft保證的是最終一致性。

leader會不斷嘗試給follower發log entries,直到所有節點的log entries都相同。

Raft 協議要求投票只能投給擁有最新資料的節點, 保證了在同步log的時候leader掛掉,重新選舉leader的時候,資料不丟失。

硬核演算法丨raft演算法簡介

主要步驟如下:

1)客戶端的每一個請求都包含被複制狀態機執行的指令。

2)leader把這個指令作為一條新的日誌條目新增到日誌中,然後並行發起 RPC 給其他的伺服器,讓他們複製這 條資訊。

3)跟隨者響應ACK,如果 follower 宕機或者執行緩慢或者丟包,leader會不斷地重試,直到所有的 follower 最終 都複製了所有的日誌條目。

4)通知所有的Follower提交日誌,同時領導人提交這條日誌到自己的狀態機中,並返回給客戶端。

5)如果committed狀態後client未收到leader響應,則client會重新發送請求,需要做冪等保證一致性。

6)如果leader在傳送commit給從節點之前掛掉,就會導致從節點存在uncommitted log,這時候會重新選舉,按照raft協議,新leader會包含之前leader的最新log,並且在新的term下,commit新的entry時,就會一併把前leader前term的前entry也提交了,於是所有狀態機就一致了。

【腦裂情況】

raft也可以保證在腦裂情況保證資料的一致性。

硬核演算法丨raft演算法簡介

頂部