[[417323]]

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

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

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

一、Raft算法概述

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

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

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

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

主要解決什么問題?

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

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

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

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

2.1 Leader選舉

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

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

A覺得自己有能力做好Leader職務(wù)，就向B、C說“來投票給我，我想當(dāng)Leader”，這時(shí)候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)，一個(gè)節(jié)點(diǎn)任一時(shí)刻肯定處于以下三狀態(tài)之一：

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

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

選舉過程

第一步：Follower成為Candidate

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

第二步：候選人爭取票

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

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

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

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

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

第四步：候選人 贏得選舉

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

2.2 日志同步

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

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

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

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

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

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

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

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

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

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

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

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

log-based replicated state machine示意圖：

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

Q1

假如Client 請(qǐng)求訪問到了Follower節(jié)點(diǎn)怎么辦?

解答：Follower節(jié)點(diǎn)會(huì)轉(zhuǎn)發(fā)請(qǐng)求到Leader節(jié)點(diǎn)。

Q2

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

解答：

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

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

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

2.3 安全性保障

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

2.3.1 選舉安全

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

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

在raft中，兩點(diǎn)保證了這個(gè)屬性：

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

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

2.3.2 Log 匹配完整性

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

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

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

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

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

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

團(tuán)隊(duì)內(nèi)后繼的leader，肯定應(yīng)該知曉這個(gè)團(tuán)隊(duì)之前的工作內(nèi)容，因?yàn)樗蠰eader任期內(nèi)的工作記錄是會(huì)做交接的。

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

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

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

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

三、總結(jié)

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

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

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

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