[[417323]]

本文轉(zhuǎn)載自微信公眾號「架構(gòu)精進(jìn)之路」，作者張張 。轉(zhuǎn)載本文請聯(lián)系架構(gòu)精進(jìn)之路公眾號。

hello，大家好，我是張張，「架構(gòu)精進(jìn)之路」公號作者。

最近跟團(tuán)隊同學(xué)聊到了一致性算法Raft，于是翻了下之前發(fā)布整理過的文章，重新溫故學(xué)習(xí)之。

一、Raft算法概述

當(dāng)我們只有一個服務(wù)節(jié)點的情況下，是不存在節(jié)點共識的問題的，當(dāng)存在多個不同服務(wù)節(jié)點時，才會引入分布式一致性的問題。

Raft是一種實現(xiàn)分布式共識的協(xié)議。所謂共識，就是多個節(jié)點對某個事情達(dá)成一致的看法，即使是在部分節(jié)點故障、網(wǎng)絡(luò)延時、網(wǎng)絡(luò)分割的情況下。

主要應(yīng)用場景：

• Redis Sentinel的選舉Leader
• Etcd 主要是共享配置和服務(wù)發(fā)現(xiàn)，實現(xiàn)一致性使用了Raft算法
• 加密貨幣(比特幣、區(qū)塊鏈)的共識算法

主要解決什么問題?

分布式存儲系統(tǒng)通常通過維護(hù)多個副本來提高系統(tǒng)的可用性，帶來的代價就是分布式存儲系統(tǒng)的核心問題之一：維護(hù)多個副本的數(shù)據(jù)一致性。

二、Raft算法實現(xiàn)流程

為了提高理解性，Raft將一致性算法分為了幾個部分，包括領(lǐng)導(dǎo)選取(leader selection)、日志復(fù)制(log replication)、安全(safety)，并且使用了更強(qiáng)的一致性來減少了必須需要考慮的狀態(tài)。

本文通過一個小故事做示例，來便于大家快速理解。

2.1 Leader選舉

部門需要成立一個新的服務(wù)小組，現(xiàn)在有三名同學(xué)A，B，C。

為了便于后期統(tǒng)一調(diào)配資源及管理需要，現(xiàn)需要從三名同學(xué)中選舉出一名小組Leader。

A覺得自己有能力做好Leader職務(wù)，就向B、C說“來投票給我，我想當(dāng)Leader”，這時候A成了候選人，并為自己事先投了一票。

1)假如B、C之前都沒有想過要自己當(dāng)Leader，那就說“好吧，投給你” → A獲得3張選票，當(dāng)選Leader

2)假如B之前想過自己當(dāng)Leader，B投了自己一票 而C投了一票給A → A獲得2張選票(3人中已超過半數(shù))，當(dāng)選Leader

3)假如B、C都已經(jīng)把票投給了自己 → A、B、C各獲得自己的一票，選舉失敗重新發(fā)起

4)假如B之前想過自己當(dāng)Leader，而且C已經(jīng)把票投給了B → B獲得2張選票(3人中已超過半數(shù))，當(dāng)選Leader

從以上選舉流程可以發(fā)現(xiàn)，一個節(jié)點任一時刻肯定處于以下三狀態(tài)之一：

• Leader(領(lǐng)導(dǎo)者)
• Follower(跟隨者)
• Candidate(候選人)

這三個狀態(tài)的轉(zhuǎn)移過程如下圖所示：

選舉過程

第一步：Follower成為Candidate

如果Follower聽不到Leader的意見，他們就可以成為Candidate

第二步：候選人爭取票

投自己一票，并發(fā)送投票請求到其他節(jié)點，節(jié)點收到請求后進(jìn)行回應(yīng)

第三步：等待其他節(jié)點回復(fù)

如果候選人得到了超半數(shù)的節(jié)點的投票(包含自己的一票)，它就成為Leader

如果候選人被告知Leader已產(chǎn)生，則自行切換為Follower

一段時間內(nèi)沒有收到超半數(shù)投票，保持候選人狀態(tài)，重新發(fā)起選舉

第四步：候選人 贏得選舉

新Leader會立刻給所有節(jié)點發(fā)消息，避免其他節(jié)點觸發(fā)新的選舉。

2.2 日志同步

在經(jīng)過上述2.1 的Leader選舉之后，已經(jīng)選定了小組Leader，這里我們假定A已當(dāng)選Leader?？梢猿袚?dān)一些對接方同學(xué)(稱為Client 端)提出的操作任務(wù)了。

規(guī)定每次需求對接，必須要經(jīng)過小組Leader才可以。那員工提出操作請求，Leader接收到后記錄下來，同時向組內(nèi)其他同學(xué)進(jìn)行同步，直到其他同學(xué)都確認(rèn)了此需求后Leader才會確認(rèn)操作并同步執(zhí)行結(jié)果到員工(Follower節(jié)點)。

Log Replication(日志復(fù)制)

經(jīng)過Leader選舉流程，產(chǎn)生了新的Leader節(jié)點，系統(tǒng)的所有變更都要通過Leader節(jié)點來實現(xiàn)。

第一步：Leader追加日志項(append log entry)

系統(tǒng)的每個更改都作為一個entry 添加到節(jié)點的日志中

第二步：Leader并行發(fā)出Append Entries RPC，并等待響應(yīng)

Leader會一直等到超半數(shù)節(jié)點都寫入entry，Leader節(jié)點提交，然后Leader通知Follower entry已提交。

第三步：Leader得到大多數(shù)回應(yīng)，向狀態(tài)機(jī)應(yīng)用entry

狀態(tài)機(jī)：可理解為一個確定的應(yīng)用程序，所謂確定是指只要是相同的輸入，那么任何狀態(tài)機(jī)都會計算出相同地輸出。

第四步：Leader回復(fù)Client，同時通知Follower應(yīng)用log

目前集群已就系統(tǒng)狀態(tài)達(dá)成了共識

log-based replicated state machine示意圖：

關(guān)于應(yīng)用過程中的幾個問題

Q1

假如Client 請求訪問到了Follower節(jié)點怎么辦?

解答：Follower節(jié)點會轉(zhuǎn)發(fā)請求到Leader節(jié)點。

Q2

當(dāng)Leader與Follower的日志不一致，需要如何處理?

解答：

1)Leader通過強(qiáng)制Followers復(fù)制它的日志來處理日志的不一致，F(xiàn)ollowers上的不一致的日志會被Leader的日志覆蓋。

2)Leader為了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆蓋Followers在該位置之后的條目。

3)Leader會從后往前試，每次AppendEntries失敗后嘗試前一個日志條目，直到成功找到每個Follower的日志一致位點，然后向后逐條覆蓋Followers在該位置之后的條目。

2.3 安全性保障

為了保證團(tuán)隊運(yùn)行的穩(wěn)定，有幾個默認(rèn)的要求：

2.3.1 選舉安全

即任一任期內(nèi)最多一個leader被選出。假如系統(tǒng)中同時有多于一個leader，被稱之為腦裂(brain split)，這會導(dǎo)致數(shù)據(jù)的覆蓋丟失。

一個團(tuán)隊某個時期內(nèi)僅允許存在一個Leader(選舉失敗情況特殊情況除外)，否則多個Leader同時處理需求發(fā)號施令，容易造成團(tuán)隊內(nèi)步調(diào)不一致情況。

在raft中，兩點保證了這個屬性：

1)一個節(jié)點某一任期內(nèi)最多只能投一票;

2)只有獲得majority投票的節(jié)點才會成為leader。

2.3.2 Log 匹配完整性

同一團(tuán)隊內(nèi)兩名同學(xué)假如目前手頭負(fù)責(zé)的事務(wù)是一致的，那之前他們的工作記錄應(yīng)該也是一致的。即：相同的初始狀態(tài)+相同的操作=相同的結(jié)束狀態(tài)

Leader將客戶端請求封裝到一個個的log entry，將這些log entries復(fù)制到其他Follower節(jié)點，大家按順序應(yīng)用這些請求，那最終狀態(tài)肯定是一致的。

Raft日志同步結(jié)論：

1)如果不同日志中的兩個條目有著相同的索引和任期號(term)，則它們所存儲的命令是相同的。

2)如果不同日志中的兩個條目有著相同的索引和任期號(term)，則它們之前的所有條目都是完全一樣的。

2.3.3 leader數(shù)據(jù)完整性

團(tuán)隊內(nèi)后繼的leader，肯定應(yīng)該知曉這個團(tuán)隊之前的工作內(nèi)容，因為所有Leader任期內(nèi)的工作記錄是會做交接的。

如果一個log entry 在某個任期被提交，那么這條log一定會出現(xiàn)在所有更高term的leader的日志里面。

Raft日志覆蓋規(guī)則：

1)一個日志被復(fù)制到majority節(jié)點才算committed

2)一個節(jié)點得到majority的投票才能成為leader，而節(jié)點A給節(jié)點B投票的其中一個前提是，B的日志不能比A的日志舊。

三、總結(jié)

所有的算法實現(xiàn)原理，其實都是真實社會工作模式的影射，聯(lián)系生活中的實際案例來理解復(fù)雜的一致性算法，可以讓我們達(dá)到事半功倍的效果。

本文旨在讓大家對raft協(xié)議有一個簡單了解入門，如有興趣去更深入了解，推薦給大家兩個不錯的鏈接：

1)Raft可視化測試以及各語言版本實現(xiàn)的Raft：https://raft.github.io/

2)Raft算法-動畫演示(很好的入門教程)：http://thesecretlivesofdata.com/raft/