圖片

分布式一致性

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

分布式一致性算法

比較常見的一致性算法包括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選舉和日志復制的機制，確保了分布式系統的共識和一致性。