摘要：但是一致性協(xié)議的貢獻(xiàn)在于，定義了可易于實(shí)現(xiàn)的一致性協(xié)議的事實(shí)標(biāo)準(zhǔn)。本文不打算對(duì)一致性協(xié)議的具體內(nèi)容進(jìn)行說(shuō)明，而是介紹記錄一些關(guān)鍵點(diǎn)，因?yàn)榻^大部分內(nèi)容原文已經(jīng)介紹的很詳實(shí)，有意者還可把作者多頁(yè)的博士論文刷一遍鏈接在文末，可自取。

此文已由作者孫建良授權(quán)網(wǎng)易云社區(qū)發(fā)布。

歡迎訪(fǎng)問(wèn)網(wǎng)易云社區(qū)，了解更多網(wǎng)易技術(shù)產(chǎn)品運(yùn)營(yíng)經(jīng)驗(yàn)。

Raft 協(xié)議的發(fā)布，對(duì)分布式行業(yè)是一大福音，雖然在核心協(xié)議上基本都是師繼 Paxos 祖師爺（lamport） 的精髓，基于多數(shù)派的協(xié)議。但是 Raft 一致性協(xié)議的貢獻(xiàn)在于，定義了可易于實(shí)現(xiàn)的一致性協(xié)議的事實(shí)標(biāo)準(zhǔn)。把一致性協(xié)議從 “陽(yáng)春白雪” 變成了讓普通學(xué)生、IT 碼農(nóng)等都可以上手試一試玩一玩的東西，MIT 的分布式教學(xué)課程 6.824 都是直接使用 Raft 來(lái)介紹一致性協(xié)議。

從《In Search of An Understandable Consensus Algorithm (Extend Version)》論文中，我們可以看到，與其他一致性協(xié)議的論文不同的點(diǎn)是，Diego 基本已經(jīng)算是把一個(gè)易于工程實(shí)現(xiàn)的算法講得非常明白了，just do it，沒(méi)有太多爭(zhēng)議和發(fā)揮的空間，即便如此，要實(shí)現(xiàn)一個(gè)工業(yè)級(jí)的靠譜的 Raft 還是要花不少力氣。

Raft 一致性協(xié)議相對(duì)來(lái)說(shuō)易于實(shí)現(xiàn)主要?dú)w結(jié)為以下幾個(gè)原因：

○ 模塊化的拆分：把一致性協(xié)議劃分為 Leader 選舉、MemberShip 變更、日志復(fù)制、SnapShot 等相對(duì)比較解耦的模塊；

○ 設(shè)計(jì)的簡(jiǎn)化：比如不允許類(lèi)似 Paxos 算法的亂序提交、使用 Randomization 算法設(shè)計(jì) Leader Election 算法以簡(jiǎn)化系統(tǒng)的狀態(tài)，只有 Leader、Follower、Candidate 等等。

本文不打算對(duì) Basic Raft 一致性協(xié)議的具體內(nèi)容進(jìn)行說(shuō)明，而是介紹記錄一些關(guān)鍵點(diǎn)，因?yàn)榻^大部分內(nèi)容原文已經(jīng)介紹的很詳實(shí)，有意者還可把 Raft 作者 Diego Ongaro 200 多頁(yè)的博士論文刷一遍（鏈接在文末，可自?。?。

Points

Old Term LogEntry 處理

舊 Term 未提交日志的提交依賴(lài)于新一輪的日志的提交

這個(gè)在原文 “5.4.2 Committing entries from previews terms” 有說(shuō)明，但是在看的時(shí)候可能會(huì)覺(jué)得有點(diǎn)繞。

Raft 協(xié)議約定，Candidate 在使用新的 Term 進(jìn)行選舉的時(shí)候，Candidate 能夠被選舉為 Leader 的條件為：

○ 得到一半以上（包括自己）節(jié)點(diǎn)的投票
○ 得到投票的前提是：Candidate 節(jié)點(diǎn)的最后一個(gè)LogEntry 的 Term 比投票節(jié)點(diǎn)大，或者在 Term 一樣情況下，LogEnry 的 SN (serial number) 必須大于等于投票者。

并且有一個(gè)安全截?cái)鄼C(jī)制：

○ Follower 在接收到 logEntry 的時(shí)候，如果發(fā)現(xiàn)發(fā)送者節(jié)點(diǎn)當(dāng)前的 Term 大于等于 Follower 當(dāng)前的 Term；并且發(fā)現(xiàn)相同序號(hào)的（相同 SN）LogEntry 在 Follower 上存在，未 Commit，并且 LogEntry Term 不一致，那么 Follower 直接截?cái)鄰?（SN~文件末尾）的所有內(nèi)容，然后將接收到的 LogEntryAppend 到截?cái)嗪蟮奈募┪病?/p>

在以上條件下，Raft 論文列舉了一個(gè) Corner Case ，如下圖所示：

○ (a)：S1 成為 Leader，Append Term2 的LogEntry（黃色）到 S1、S2 成功；
○ (b)：S1 Crash，S5 使用 Term(3) 成功競(jìng)選為 Term(3) 的 Leader（通過(guò)獲得 S3、S4、S5 的投票），并且將 Term 為 3 的 LogEntry(藍(lán)色) Append 到本地；
○ (c)：S5 Crash， S1 使用 Term(4) 成功競(jìng)選為L(zhǎng)eader（通過(guò)獲得 S1、S2、S3 的投票），將黃色的 LogEntry 復(fù)制到 S3，得到多數(shù)派響應(yīng)（S1、S2、S3) 的響應(yīng)，提交黃色 LogEntry 為 Commit，并將 Term 為 4 的 LogEntry (紅色) Append 到本地；
○ (d) ：S5 使用新的 Term(5) 競(jìng)選為 Leader (得到 S2、S3、S4 的投票)，按照協(xié)議將所有所有節(jié)點(diǎn)上的黃色和紅色的 LogEntry 截?cái)喔采w為自己的 Term 為 3 的 LogEntry。

進(jìn)行到這步的時(shí)候我們已經(jīng)發(fā)現(xiàn)，黃色的 LogEnry(2) 在被設(shè)置為 Commit 之后重新又被否定了。

所以協(xié)議又強(qiáng)化了一個(gè)限制；

○ 只有當(dāng)前 Term 的 LogEntry 提交條件為：滿(mǎn)足多數(shù)派響應(yīng)之后（一半以上節(jié)點(diǎn) Append LogEntry 到日志）設(shè)置為 commit；
○ 前一輪 Term 未 Commit 的 LogEntry 的 Commit 依賴(lài)于高輪 Term LogEntry 的 Commit

如圖所示 (c) 狀態(tài) Term2 的 LogEntry（黃色） 只有在 （e）狀態(tài) Term4 的 LogEntry（紅色）被 commit 才能夠提交。

提交 NO-OP LogEntry 提交系統(tǒng)可用性

在 Leader 通過(guò)競(jìng)選剛剛成為 Leader 的時(shí)候，有一些等待提交的 LogEntry （即 SN > CommitPt 的 LogEntry），有可能是 Commit 的，也有可能是未 Commit 的（PS: 因?yàn)樵?Raft 協(xié)議中 CommitPt 不用實(shí)時(shí)刷盤(pán)）。

所以為了防止出現(xiàn)非線(xiàn)性一致性（Non Linearizable Consistency）；即之前已經(jīng)響應(yīng)客戶(hù)端的已經(jīng) Commit 的請(qǐng)求回退，并且為了避免出現(xiàn)上圖中的 Corner Case，往往我們需要通過(guò)下一個(gè) Term 的 LogEntry 的 Commit 來(lái)實(shí)現(xiàn)之前的 Term 的 LogEntry 的 Commit （隱式commit），才能保障提供線(xiàn)性一致性。

但是有可能接下來(lái)的客戶(hù)端的寫(xiě)請(qǐng)求不能及時(shí)到達(dá)，那么為了保障 Leader 快速提供讀服務(wù)，系統(tǒng)可首先發(fā)送一個(gè) NO-OP LogEntry 來(lái)保障快速進(jìn)入正?？勺x狀態(tài)。

Current Term、VotedFor 持久化

上圖其實(shí)隱含了一些需要持久化的重要信息，即 Current Term、VotedFor！ 為什么(b) 狀態(tài) S5 使用的 Term Number 為 3，而不是 2？

因?yàn)楦?jìng)選為 Leader 就必須是使用新的 Term 發(fā)起選舉，并且得到多數(shù)派階段的同意，同意的操作為將 Current Term、VotedFor 持久化。

比如（a） 狀態(tài) S1 為什么能競(jìng)選為 Leader？首先 S1 滿(mǎn)足成為 Leader 的條件，S2～S5 都可以接受 S1 成為發(fā)起 Term 為 2 的 Leader 選舉。S2～S5 同意 S1 成為 Leader 的操作為：將 Current Term 設(shè)置為 2、VotedFor 設(shè)置為 S2 并且持久化，然后返回 S1。即 S1 成功成為 Term 為 2 的 Leader 的前提是一個(gè)多數(shù)派已經(jīng)記錄 Current Term 為 2 ，并且 VotedFor 為 S2。那么 (b) 狀態(tài) S5 如使用 Term 為 2 進(jìn)行 Leader 選舉，必然得不到多數(shù)派同意，因?yàn)?Term 2 已經(jīng)投給 S1，S5 只能 將 Term++ 使用Term 為3 進(jìn)行重新發(fā)起請(qǐng)求。

Current Term、VotedFor 如何持久化?
type CurrentTermAndVotedFor {
Term int64 json:"Term"
VotedFor int64 json:"Votedfor"
Crc int32
}
//current state
var currentState CurrentTermAndVotedFor
.. set value and calculate crc ...
content, err := json.Marshal(currentState)

//flush to disk
f, err := os.Create("/dist/currentState.txt")
f.Write(content)
f.Sync()

簡(jiǎn)單的方法，只需要保存在一個(gè)多帶帶的文件，如上為簡(jiǎn)單的 go 語(yǔ)言示例；其他簡(jiǎn)單的方式比如在設(shè)計(jì) Log File 的時(shí)候，Log File Header 中包含 Current Term 以及 VotedFor 的位置。

如果再深入思考一層，其實(shí)這里頭有一個(gè)疑問(wèn)？如何保證寫(xiě)了一半（寫(xiě)入一半然后掛了）的問(wèn)題？寫(xiě)了 Term、沒(méi)寫(xiě) VoteFor？或者只寫(xiě)了 Term 的高 32 位？
可以看到磁盤(pán)能夠保證 512 Byte 的寫(xiě)入原子性，這個(gè)在知乎事務(wù)性 （Transactional）存儲(chǔ)需要硬件參與嗎？（鏈接見(jiàn)文末） 這個(gè)問(wèn)答上就能找到答案。所以最簡(jiǎn)單的方法是直接寫(xiě)入一個(gè) tmpfile，寫(xiě)入完成之后，將 tmpfile mv 成CurrentTermAndVotedFor 文件，基本可保障更新的原子性。其他方式比如采用 Append Entry 的方式也可以實(shí)現(xiàn)。

Cluser Membership 變更

在 raft 的 Paper 中，簡(jiǎn)要說(shuō)明了一種一次變更多個(gè)節(jié)點(diǎn)的 Cluser Membership 變更方式。但是沒(méi)有給出更多的在 Security 以及 Avaliable 上的更多的說(shuō)明。

其實(shí)現(xiàn)在開(kāi)源的 Raft 實(shí)現(xiàn)一般都不會(huì)使用這種方式，比如 Etcd raft 都是采用了更加簡(jiǎn)潔的一次只能變更一個(gè)節(jié)點(diǎn)的 “single Cluser MemberShip Change” 算法。

當(dāng)然 single cluser MemberShip 并非 Etcd 自創(chuàng)，其實(shí) Raft 協(xié)議作者 Diego 在其博士論文中已經(jīng)詳細(xì)介紹了 Single Cluser MemberShip Change 機(jī)制，包括 Security、Avaliable 方面的詳細(xì)說(shuō)明，并且作者也說(shuō)明了在實(shí)際工程實(shí)現(xiàn)過(guò)程中更加推薦 Single 方式，首先因?yàn)楹?jiǎn)單，再則所有的集群變更方式都可以通過(guò) Single 一次一個(gè)節(jié)點(diǎn)的方式達(dá)到任何想要的 Cluster 狀態(tài)。

原文：“Raft restrict the types of change that allowed： only one server can be added or removed from the cluster at once. More complex changes in membership are implemented as a series of single-server-change”.

Safty

回到問(wèn)題的第一大核心要點(diǎn)：Safety，membership 變更必須保持 raft 協(xié)議的約束：同一時(shí)間（同一個(gè) Term）只能存在一個(gè)有效的 Leader。

<一>：為什么不能直接變更多個(gè)節(jié)點(diǎn)，直接從 Old 變?yōu)?New 有問(wèn)題? for example change from 3 Node to 5 Node？

如上圖所示，在集群狀態(tài)變更過(guò)程中，在紅色箭頭處出現(xiàn)了兩個(gè)不相交的多數(shù)派（Server3、Server4、Server 5 認(rèn)知到新的 5 Node 集群；而 1、2 Server 的認(rèn)知還是處在老的 3 Node 狀態(tài)）。在網(wǎng)絡(luò)分區(qū)情況下（比如 S1、S2 作為一個(gè)分區(qū)；S3、S4、S5 作為一個(gè)分區(qū)），2個(gè)分區(qū)分別可以選舉產(chǎn)生2個(gè)新的 Leader（屬于configuration< Cold>的 Leader 以及 屬于 new configuration < Cnew > 的 Leader） 。

當(dāng)然這就導(dǎo)致了 Safty 沒(méi)法保證；核心原因是對(duì)于 Cold 和 CNew 不存在交集，不存在一個(gè)公共的交集節(jié)點(diǎn)充當(dāng)仲裁者的角色。

但是如果每次只允許出現(xiàn)一個(gè)節(jié)點(diǎn)變更(增加 or 減小)，那么 Cold 和 CNew 總會(huì)相交。 如下圖所示：

<二>： 如何實(shí)現(xiàn) Single membership change

論文中提以下幾個(gè)關(guān)鍵點(diǎn)：

○ 由于 Single 方式無(wú)論如何 Cold 和 CNew 都會(huì)相交，所以 raft 采用了直接提交一個(gè)特殊的 replicated LogEntry 的方式來(lái)進(jìn)行 single 集群關(guān)系變更。

○ 跟普通的 LogEntry 提交的不同點(diǎn)，configuration LogEntry 不需要 commit 就生效，只需要 append 到 Log 中即可。( PS： 原文 “The New configuration takes effect on each server as soon as it is added to the server’s log”)。

○ 后一輪 MemberShip Change 的開(kāi)始必須在前一輪 MemberShip Change Commit 之后進(jìn)行，以避免出現(xiàn)多個(gè) Leader 的問(wèn)題。

關(guān)注點(diǎn) 1
如圖所示，如在前一輪 membership configure Change 未完成之前，又進(jìn)行下一次 membership change 會(huì)導(dǎo)致問(wèn)題，所以外部系統(tǒng)需要確保不會(huì)在第一次 Configuration 為成功情況下，發(fā)起另外一個(gè)不同的 Configuration 請(qǐng)求。( PS：由于增加副本、節(jié)點(diǎn)宕機(jī)丟失節(jié)點(diǎn)進(jìn)行數(shù)據(jù)恢復(fù)的情況都是由外部觸發(fā)進(jìn)行的，只要外部節(jié)點(diǎn)能夠確保在前一輪未完成之前發(fā)起新一輪請(qǐng)求，即可保障。)

關(guān)注點(diǎn) 2
跟其他客戶(hù)端的請(qǐng)求不一樣的，Single MemberShip Change LogEntry 只需要 Append 持久化到 Log（而不需要 commit）就可以應(yīng)用。

一方面是可用性方面的考慮，如下所示：Leader S1 接收到集群變更請(qǐng)求將集群狀態(tài)從（S1、S2、S3、S4）變更為 （S2、S3、S4）；提交到所有節(jié)點(diǎn)之后 commit 之后，返回客戶(hù)端集群狀態(tài)變更完成（如下?tīng)顟B(tài) a），S1 退出（如下?tīng)顟B(tài)b）；由于 Basic Raft 并不需要 commit 消息實(shí)施傳遞到其他 S1、S2、S3 節(jié)點(diǎn)，S1 退出之后，S1、S2、S3 由于沒(méi)有接收到 Leader S1 的心跳，導(dǎo)致進(jìn)行選舉，但是不幸的是 S4 故障退出。假設(shè)這個(gè)時(shí)候 S2、S3 由于 Single MemberShip Change LogEntry 沒(méi)有 Commit 還是以（S1、S2、S3、S4）作為集群狀態(tài)，那么集群沒(méi)法繼續(xù)工作。但是實(shí)質(zhì)上在（b）狀態(tài) S1 返回客戶(hù)端集群狀態(tài)變更請(qǐng)求完成之后，實(shí)質(zhì)上是認(rèn)為可獨(dú)立進(jìn)入正常狀態(tài)。

另一方面，即使沒(méi)有提交到一個(gè)多數(shù)派，也可以截?cái)啵瑳](méi)什么問(wèn)題。(這里不多做展開(kāi))

另一方面可靠性&正確性

Raft 協(xié)議 Configuration 請(qǐng)求和普通的用戶(hù)寫(xiě)請(qǐng)求是可以并行的，所以在并發(fā)進(jìn)行的時(shí)候，用戶(hù)寫(xiě)請(qǐng)求提交的備份數(shù)是無(wú)法確保是在 Configuration Change 之前的備份數(shù)還是備份之后的備份數(shù)。但是這個(gè)沒(méi)有辦法，因?yàn)樵诓l(fā)情況下本來(lái)就沒(méi)法保證，這是保證 Configuration 截?cái)嘞到y(tǒng)持續(xù)可用帶來(lái)的代價(jià)。(只要確保在多數(shù)派存活情況下不丟失即可（PS：一次變更一個(gè)節(jié)點(diǎn)情況下，返回客戶(hù)端成功，其中必然存在一個(gè)提交了客戶(hù)端節(jié)點(diǎn)的 Server 被選舉為L(zhǎng)eader）。

關(guān)注點(diǎn) 3
Single membership change 其他方面的 safty 保障是跟原始的 Basic Raft 是一樣的（在各個(gè)協(xié)議處理細(xì)節(jié)上對(duì)此類(lèi)請(qǐng)求未有任何特殊待遇），即只要一個(gè)多數(shù)派（不管是新的還是老的）將 single membership change 提交并返回給客戶(hù)端成功之后，接下來(lái)無(wú)論節(jié)點(diǎn)怎么重啟，都會(huì)確保新的 Leader 將會(huì)在已經(jīng)知曉（應(yīng)用）新的，前一輪變更成功的基礎(chǔ)上處理接下來(lái)的請(qǐng)求：可以是讀寫(xiě)請(qǐng)求、當(dāng)然也可以是新的一輪 Configuration 請(qǐng)求。

初始狀態(tài)如何進(jìn)入最小備份狀態(tài)

比如如何進(jìn)入3副本的集群狀態(tài)?？梢允褂孟到y(tǒng)元素的 Single MemberShip 變更算法實(shí)現(xiàn)。

剛開(kāi)始節(jié)點(diǎn)的副本狀態(tài)最簡(jiǎn)單為一個(gè)節(jié)點(diǎn) 1（自己同意自己非常簡(jiǎn)單），得到返回之后，再選擇添加一個(gè)副本，達(dá)到 2個(gè)副本的狀態(tài)。然后再添加一個(gè)副本，變成三副本狀態(tài)，滿(mǎn)足對(duì)系統(tǒng)可用性和可靠性的要求，此時(shí)該 raft 實(shí)例可對(duì)外提供服務(wù)。

其他需要關(guān)注的事項(xiàng)

○ servers process incoming RPC requests without consulting their current configurations. server 處理在 AppendEntries & Voting Request 的時(shí)候不用考慮本地的 configuration 信息。

○ CatchUp：為了保障系統(tǒng)的可靠性和可用性，加入 no-voting membership 狀態(tài)，進(jìn)行 CatchUp，需要加入的節(jié)點(diǎn)將歷史 LogEntry 基本全部 Get 到之后再發(fā)送 Configuration。

○ Disruptive serves：為了防止移除的節(jié)點(diǎn)由于沒(méi)有接收到新的 Leader 的心跳，而發(fā)起 Leader 選舉而擾繞當(dāng)前正在進(jìn)行的集群狀態(tài)。集群中節(jié)點(diǎn)在 Leader 心跳租約期間內(nèi)收到 Leader 選舉請(qǐng)求可以直接 Deny。(PS：當(dāng)然對(duì)于一些確定性的事情，比如發(fā)現(xiàn) Leader listen port reset，那么可以發(fā)起強(qiáng)制 Leader 選舉的請(qǐng)求)。

參考文獻(xiàn)：

Raft Paper：
https://raft.github.io/raft.pdf
Raft 博士論文：
https://web.stanford.edu/~ous...
事務(wù)性(Transactional)存儲(chǔ)需要硬件參與嗎？
https://www.zhihu.com/questio...

文章來(lái)源： 網(wǎng)易云社區(qū)