圖片

分布式一致性

在分布式環(huán)境中，一致性是指數(shù)據(jù)在多個副本之間是否能夠保持一致的特性。

分布式一致性算法

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

• ? Paxos是Leslie Lamport提出的一種基于消息傳遞的分布式一致性算法。很多分布式一致性算法都由Paxos演變而來，但是最大特點就是難，不僅難以理解，更難以實現(xiàn)。
• ? Raft 是一種相對較新的分布式一致性算法，是一種更易于理解和實現(xiàn)的算法，在選主的沖突處理等方式上它都選擇了非常簡單明了的解決方案。
• ? ZAB 協(xié)議全稱：Zookeeper Atomic Broadcast（Zookeeper 原子廣播協(xié)議）,是為 Zookeeper 設計的分布式一致性協(xié)議！

圖片

Raft算法使用場景

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

?? Raft只是個共識算法來保證數(shù)據(jù)的一致性，與數(shù)據(jù)庫、客戶端、事務沒有關系

Raft算法基礎

Raft把算法流程分為三個子問題：領導選舉（Leader election）、日志復制（Log replication）、安全性（Safety）。

角色

• ? 領導者 Leader：接收處理客戶端請求、向Follower進行日志同步、同一時刻最多只能有一個可行的 Leader
• ? 追隨者 Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志，處在完全被動狀態(tài)
• ? 候選人 Candidate：臨時角色，處于 Leader 和 Follower 之間的暫時狀態(tài)

圖片

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

狀態(tài)轉換

圖片

狀態(tài)切換流程：

1. 1. Raft剛啟動的時候，所有節(jié)點初始狀態(tài)都是Follower
2. 2. 超時時間內如果沒有收到Leader的請求則轉換為Candidate角色并發(fā)起Leader選舉
3. 3. 如果Candidate收到了多數(shù)節(jié)點的選票則轉換為Leader
4. 4. 如果在發(fā)起選舉期間發(fā)現(xiàn)已經(jīng)有Leader了，或者收到更高任期的請求則轉換為Follower
5. 5. Leader在收到更高任期的請求后轉換為Follower

任期

任期：可以理解為是節(jié)點擔任Leader職務的時間期限。

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

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

圖片

通信

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

• ? 請求投票 RequestVote：候選人(Candidate) 選舉期間發(fā)起
• ? 日志復制 AppendEntries：領導人(Leader)發(fā)起，用于復制 log 和發(fā)送心跳

圖片

Leader選舉

初始狀態(tài)

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

圖片

不過這兩種情況會觸發(fā)選舉：

• ? Raft 初次啟動時，不存在Leader，這時候會觸發(fā)Leader選舉
• ? Follower在自己的超時時間內沒有接收到Leader的心跳heartBeat，觸發(fā)選舉超時，從而Follower的角色切換成Candidate，Candidate會發(fā)起選舉

選舉

既然有兩種情況下會觸發(fā)選舉，一個是初次啟動，一個是Leader故障未發(fā)送心跳給Follower，那么我們假設有五個節(jié)點，然后分別用圖來看下是如何選舉的！

??為了畫圖是不會顯得很占空間，暫時用三個節(jié)點表示， 并且用 ‘...’表示剩余節(jié)點

初次啟動時：

初次啟動節(jié)點都是正常流程如下：

圖片

Leader故障時：

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

圖片

當選條件

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

日志同步

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

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

日志結構

Raft算法中，每個節(jié)點維護著一份日志，其中包含了系統(tǒng)中所有狀態(tài)變更的記錄，每一次狀態(tài)變更被稱為一個日志條目。

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

圖片

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

? 索引 (log index)：記錄在日志中的位置，是一個連續(xù)單調遞增整數(shù)

? 任期號 (term)：日志記錄被創(chuàng)建時Leader的任期號，上圖中有三個任期

? 命令 (command)：客戶端請求指定的、狀態(tài)機需要執(zhí)行的指令

執(zhí)行流程

了解完日志結構后，我們來看日志是如何發(fā)起同步的。

日志持久化存儲的條件

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

如果一條日志記錄被存儲在超過半數(shù)的節(jié)點上，我們認為該記錄已提交(committed)——這是 Raft 非常重要的特性！如果一條記錄已提交，意味著狀態(tài)機可以安全地執(zhí)行該記錄

流程如下圖：

圖片

1. 1. 客戶端向 Leader 發(fā)送命令，希望該命令被所有狀態(tài)機執(zhí)行；
2. 2. Leader 先將該命令追加到自己的日志中；
3. 3. Leader 并行地向其它節(jié)點發(fā)送AppendEntries RPC，等待響應；
4. 4. 收到超過半數(shù)節(jié)點的響應，則認為新的日志記錄是被提交的：
5. 5. Leader 將命令傳給自己的狀態(tài)機，然后向客戶端返回響應
6. 6. 此外，一旦 Leader 知道一條記錄被提交了，將在后續(xù)的AppendEntries RPC中通知已經(jīng)提交記錄的 Followers
7. 7. Follower 將已提交的命令傳給自己的狀態(tài)機
8. 8. 如果 Follower 宕機/超時：Leader 將反復嘗試發(fā)送 RPC；

?? 注：Leader 不必等待每個 Follower 做出響應，只需要超過半數(shù)的成功響應（確保日志記錄已經(jīng)存儲在超過半數(shù)的節(jié)點上），一個很慢的節(jié)點不會使系統(tǒng)變慢，因為 Leader 不必等待

一致性檢查

Raft 通過 AppendEntries RPC 消息來檢測。

• ? 每個AppendEntries RPC包含新日志記錄之前那條記錄的索引 (prevLogIndex) 和任期 (prevTerm)；
• ? Follower接收到消息后檢查自己的 log index 、 term 與 prevLogIndex 、 prevTerm 進行匹配
• ? 匹配成功則接收該記錄，添加最新log，匹配失敗則拒絕該消息

圖片

圖片

日志一致性

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

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

• ? 如果兩個節(jié)點的日志在相同的索引位置上的任期號相同，則認為他們具有一樣的命令，從頭到這個索引位置之間的日志完全相同
• ? 如果給定的記錄已提交，那么所有前面的記錄也已提交

總結

Raft算法是一種簡潔而高效的分布式一致性算法，通過引入Leader選舉和日志復制的機制，確保了分布式系統(tǒng)的共識和一致性。