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

作者：小許code 2024-01-11 08:13:49

云計(jì)算分布式

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

圖片

分布式一致性

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

分布式一致性算法

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

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

圖片

Raft算法使用場景

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

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

Raft算法基礎(chǔ)

Raft把算法流程分為三個子問題：領(lǐng)導(dǎo)選舉（Leader election）、日志復(fù)制（Log replication）、安全性（Safety）。

角色

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

圖片

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

狀態(tài)轉(zhuǎn)換

圖片

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

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

任期

任期：可以理解為是節(jié)點(diǎn)擔(dān)任Leader職務(wù)的時間期限。

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

?? 任期時間 = 選舉時間 + 正常運(yùn)行時間

圖片

通信

Raft 中服務(wù)器節(jié)點(diǎn)之間通信通過兩個 RPC 調(diào)用：

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

圖片

Leader選舉

初始狀態(tài)

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

圖片

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

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

選舉

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

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

初次啟動時：

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

圖片

Leader故障時：

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

圖片

當(dāng)選條件

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

日志同步

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

OK！我們看下是如何進(jìn)行同步的

日志結(jié)構(gòu)

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

我們先看日志結(jié)構(gòu)和右側(cè)說明：

圖片

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

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

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

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

執(zhí)行流程

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

日志持久化存儲的條件

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

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

流程如下圖：

圖片

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

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