八分鐘瞭解一致性算法 - Raft 算法

分佈式一致性

在分佈式環境中，一致性是指數據在多個副本之間是否能夠保持一致的特性。

分佈式一致性算法

比較常見的一致性算法包括 Paxos 算法，Raft 算法，ZAB 算法等

• • Paxos 是 Leslie Lamport 提出的一種基於消息傳遞的分佈式一致性算法。很多分佈式一致性算法都由 Paxos 演變而來，但是最大特點就是難，不僅難以理解，更難以實現。

• • Raft 是一種相對較新的分佈式一致性算法，是一種更易於理解和實現的算法，在選主的衝突處理等方式上它都選擇了非常簡單明瞭的解決方案。

• • ZAB 協議全稱：Zookeeper Atomic Broadcast（Zookeeper 原子廣播協議）, 是爲 Zookeeper 設計的分佈式一致性協議！

Raft 算法使用場景

一般用作兩種場景：
元數據管理：比如 etcd，特點是數據規模小，主要保證數據一致性和集羣的高可用（raft 選主）, 所以一套 raft 集羣就夠了。
分佈式數據庫：這種會用 partition group，每個 group 有一個 raft 集羣，當數據變大的時候會做擴展。

🚩 Raft 只是個共識算法來保證數據的一致性，與數據庫、客戶端、事務沒有關係

Raft 算法基礎

Raft 把算法流程分爲三個子問題：領導選舉（Leader election）、日誌複製（Log replication）、安全性（Safety）。

角色

• • 領導者 Leader：接收處理客戶端請求、向 Follower 進行日誌同步、同一時刻最多隻能有一個可行的 Leader

• • 追隨者 Follower：接受並持久化 Leader 同步的日誌，在 Leader 告之日誌可以提交之後，提交日誌，處在完全被動狀態

• • 候選人 Candidate：臨時角色，處於 Leader 和 Follower 之間的暫時狀態

Raft 算法中在任意時刻最多隻有一個 Leader，正常工作期間只有 Leader 和 Followers。

狀態轉換

狀態切換流程：

1. 1. Raft 剛啓動的時候，所有節點初始狀態都是 Follower

2. 2. 超時時間內如果沒有收到 Leader 的請求則轉換爲 Candidate 角色併發起 Leader 選舉

3. 3. 如果 Candidate 收到了多數節點的選票則轉換爲 Leader

4. 4. 如果在發起選舉期間發現已經有 Leader 了，或者收到更高任期的請求則轉換爲 Follower

5. 5. Leader 在收到更高任期的請求後轉換爲 Follower

任期

任期：可以理解爲是節點擔任 Leader 職務的時間期限。

Raft 將時間劃分爲一個一個的任期（term），每個任期由單調遞增的數字（任期編號）標識，工作期可長可短也可能不存在

🚩 任期時間 = 選舉時間 + 正常運行時間

通信

Raft 中服務器節點之間通信通過兩個 RPC 調用：

• • 請求投票 RequestVote：候選人 (Candidate) 選舉期間發起

• • 日誌複製 AppendEntries：領導人 (Leader) 發起，用於複製 log 和發送心跳

Leader 選舉

初始狀態

初始狀態時，每個節點的角色都是 Follower(跟隨者)，Term 任期編號爲 1(假設任期編號從 1 開始)

不過這兩種情況會觸發選舉：

• • Raft 初次啓動時，不存在 Leader，這時候會觸發 Leader 選舉

• • Follower 在自己的超時時間內沒有接收到 Leader 的心跳 heartBeat，觸發選舉超時，從而 Follower 的角色切換成 Candidate，Candidate 會發起選舉

選舉

既然有兩種情況下會觸發選舉，一個是初次啓動，一個是 Leader 故障未發送心跳給 Follower，那麼我們假設有五個節點，然後分別用圖來看下是如何選舉的！

🚩爲了畫圖是不會顯得很佔空間，暫時用三個節點表示， 並且用 ‘...’表示剩餘節點

初次啓動時：

初次啓動節點都是正常流程如下：

Leader 故障時：

Node2 此時是 Leader 節點，結果故障了，剩下四個節點參與選舉。

當選條件

在一個任期（Term）內只可以投票給一個結點，得到超過半數的投票纔可成爲 Leader，從而保證了一個任期內只會有一個 Leader 產生。

日誌同步

概括成一句話就是：保證 Leader 上日誌能完全相同地複製到多臺 Follower 服務器上。

OK！我們看下是如何進行同步的

日誌結構

Raft 算法中，每個節點維護着一份日誌，其中包含了系統中所有狀態變更的記錄，每一次狀態變更被稱爲一個日誌條目。

我們先看日誌結構和右側說明：

圖中每個節點存儲自己的日誌副本 (log)，每條日誌記錄包含：

• • 索引 (log index)：記錄在日誌中的位置，是一個連續單調遞增整數

• • 任期號 (term)：日誌記錄被創建時 Leader 的任期號，上圖中有三個任期

• • 命令 (command)：客戶端請求指定的、狀態機需要執行的指令

執行流程

瞭解完日誌結構後，我們來看日誌是如何發起同步的。

日誌持久化存儲的條件

Follower 節點必須先將記錄安全寫到磁盤，才能向 Leader 節點返回寫入成功響應。

如果一條日誌記錄被存儲在超過半數的節點上，我們認爲該記錄已提交 (committed)——這是 Raft 非常重要的特性！如果一條記錄已提交，意味着狀態機可以安全地執行該記錄

流程如下圖：

1. 1. 客戶端向 Leader 發送命令，希望該命令被所有狀態機執行；
2. 2. Leader 先將該命令追加到自己的日誌中；
3. 3. Leader 並行地向其它節點發送 AppendEntries RPC，等待響應；
4. 4. 收到超過半數節點的響應，則認爲新的日誌記錄是被提交的：

5. 5. Leader 將命令傳給自己的狀態機，然後向客戶端返回響應

6. 6. 此外，一旦 Leader 知道一條記錄被提交了，將在後續的 AppendEntries RPC 中通知已經提交記錄的 Followers

7. 7. Follower 將已提交的命令傳給自己的狀態機

8. 8. 如果 Follower 宕機 / 超時：Leader 將反覆嘗試發送 RPC；

🚩 注：Leader 不必等待每個 Follower 做出響應，只需要超過半數的成功響應（確保日誌記錄已經存儲在超過半數的節點上），一個很慢的節點不會使系統變慢，因爲 Leader 不必等待

一致性檢查

Raft 通過 AppendEntries RPC 消息來檢測。

• • 每個 AppendEntries RPC 包含新日誌記錄之前那條記錄的索引 (prevLogIndex) 和任期 (prevTerm)；

• • Follower 接收到消息後檢查自己的 log index 、 term 與 prevLogIndex 、 prevTerm 進行匹配

• • 匹配成功則接收該記錄，添加最新 log，匹配失敗則拒絕該消息

日誌一致性

Raft 算法的目的是保證所有節點的一致性，即一個日誌條目在某個節點被提交，那麼這個日誌條目也必須在所有節點上被提交。

🚩 通過【一致性檢查】就保證了日誌一致性的這兩點內容。

• • 如果兩個節點的日誌在相同的索引位置上的任期號相同，則認爲他們具有一樣的命令，從頭到這個索引位置之間的日誌完全相同

• • 如果給定的記錄已提交，那麼所有前面的記錄也已提交

總結

Raft 算法是一種簡潔而高效的分佈式一致性算法，通過引入 Leader 選舉和日誌複製的機制，確保了分佈式系統的共識和一致性。

歡迎朋友們關注我的公衆號📢📢：【小許 code】！🤣🤣

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/iZLKntKlG9847fglMt2A7w