圖片

分布式一致性

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

分布式一致性算法

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

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

圖片

Raft算法使用場(chǎng)景

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

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

Raft算法基礎(chǔ)

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

角色

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

圖片

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

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

圖片

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

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

任期

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

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

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

圖片

通信

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

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

圖片

Leader選舉

初始狀態(tài)

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

圖片

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

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

選舉

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

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

初次啟動(dòng)時(shí)：

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

圖片

Leader故障時(shí)：

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

圖片

當(dāng)選條件

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

日志同步

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

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

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

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

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

圖片

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

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

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

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

執(zhí)行流程

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

日志持久化存儲(chǔ)的條件

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

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

流程如下圖：

圖片

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

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

一致性檢查

Raft 通過 AppendEntries RPC 消息來檢測(cè)。

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

圖片

圖片

日志一致性

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

?? 通過【一致性檢查】就保證了日志一致性的這兩點(diǎn)內(nèi)容。

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

總結(jié)

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