摘要：但是一致性協(xié)議的貢獻在于，定義了可易于實現(xiàn)的一致性協(xié)議的事實標準。本文不打算對一致性協(xié)議的具體內容進行說明，而是介紹記錄一些關鍵點，因為絕大部分內容原文已經介紹的很詳實，有意者還可把作者多頁的博士論文刷一遍鏈接在文末，可自取。

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

歡迎訪問網易云社區(qū)，了解更多網易技術產品運營經驗。

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

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

Raft 一致性協(xié)議相對來說易于實現(xiàn)主要歸結為以下幾個原因：

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

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

本文不打算對 Basic Raft 一致性協(xié)議的具體內容進行說明，而是介紹記錄一些關鍵點，因為絕大部分內容原文已經介紹的很詳實，有意者還可把 Raft 作者 Diego Ongaro 200 多頁的博士論文刷一遍（鏈接在文末，可自取）。

Points

Old Term LogEntry 處理

舊 Term 未提交日志的提交依賴于新一輪的日志的提交

這個在原文 “5.4.2 Committing entries from previews terms” 有說明，但是在看的時候可能會覺得有點繞。

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

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

并且有一個安全截斷機制：

○ Follower 在接收到 logEntry 的時候，如果發(fā)現(xiàn)發(fā)送者節(jié)點當前的 Term 大于等于 Follower 當前的 Term；并且發(fā)現(xiàn)相同序號的（相同 SN）LogEntry 在 Follower 上存在，未 Commit，并且 LogEntry Term 不一致，那么 Follower 直接截斷從 （SN~文件末尾）的所有內容，然后將接收到的 LogEntryAppend 到截斷后的文件末尾。

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

○ (a)：S1 成為 Leader，Append Term2 的LogEntry（黃色）到 S1、S2 成功；
○ (b)：S1 Crash，S5 使用 Term(3) 成功競選為 Term(3) 的 Leader（通過獲得 S3、S4、S5 的投票），并且將 Term 為 3 的 LogEntry(藍色) Append 到本地；
○ (c)：S5 Crash， S1 使用 Term(4) 成功競選為Leader（通過獲得 S1、S2、S3 的投票），將黃色的 LogEntry 復制到 S3，得到多數(shù)派響應（S1、S2、S3) 的響應，提交黃色 LogEntry 為 Commit，并將 Term 為 4 的 LogEntry (紅色) Append 到本地；
○ (d) ：S5 使用新的 Term(5) 競選為 Leader (得到 S2、S3、S4 的投票)，按照協(xié)議將所有所有節(jié)點上的黃色和紅色的 LogEntry 截斷覆蓋為自己的 Term 為 3 的 LogEntry。

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

所以協(xié)議又強化了一個限制；

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

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

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

在 Leader 通過競選剛剛成為 Leader 的時候，有一些等待提交的 LogEntry （即 SN > CommitPt 的 LogEntry），有可能是 Commit 的，也有可能是未 Commit 的（PS: 因為在 Raft 協(xié)議中 CommitPt 不用實時刷盤）。

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

但是有可能接下來的客戶端的寫請求不能及時到達，那么為了保障 Leader 快速提供讀服務，系統(tǒng)可首先發(fā)送一個 NO-OP LogEntry 來保障快速進入正常可讀狀態(tài)。

Current Term、VotedFor 持久化

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

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

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

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()

簡單的方法，只需要保存在一個多帶帶的文件，如上為簡單的 go 語言示例；其他簡單的方式比如在設計 Log File 的時候，Log File Header 中包含 Current Term 以及 VotedFor 的位置。

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

Cluser Membership 變更

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

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

當然 single cluser MemberShip 并非 Etcd 自創(chuàng)，其實 Raft 協(xié)議作者 Diego 在其博士論文中已經詳細介紹了 Single Cluser MemberShip Change 機制，包括 Security、Avaliable 方面的詳細說明，并且作者也說明了在實際工程實現(xiàn)過程中更加推薦 Single 方式，首先因為簡單，再則所有的集群變更方式都可以通過 Single 一次一個節(jié)點的方式達到任何想要的 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

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

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

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

當然這就導致了 Safty 沒法保證；核心原因是對于 Cold 和 CNew 不存在交集，不存在一個公共的交集節(jié)點充當仲裁者的角色。

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

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

論文中提以下幾個關鍵點：

○ 由于 Single 方式無論如何 Cold 和 CNew 都會相交，所以 raft 采用了直接提交一個特殊的 replicated LogEntry 的方式來進行 single 集群關系變更。

○ 跟普通的 LogEntry 提交的不同點，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 的開始必須在前一輪 MemberShip Change Commit 之后進行，以避免出現(xiàn)多個 Leader 的問題。

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

關注點 2
跟其他客戶端的請求不一樣的，Single MemberShip Change LogEntry 只需要 Append 持久化到 Log（而不需要 commit）就可以應用。

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

另一方面，即使沒有提交到一個多數(shù)派，也可以截斷，沒什么問題。(這里不多做展開)

另一方面可靠性&正確性

Raft 協(xié)議 Configuration 請求和普通的用戶寫請求是可以并行的，所以在并發(fā)進行的時候，用戶寫請求提交的備份數(shù)是無法確保是在 Configuration Change 之前的備份數(shù)還是備份之后的備份數(shù)。但是這個沒有辦法，因為在并發(fā)情況下本來就沒法保證，這是保證 Configuration 截斷系統(tǒng)持續(xù)可用帶來的代價。(只要確保在多數(shù)派存活情況下不丟失即可（PS：一次變更一個節(jié)點情況下，返回客戶端成功，其中必然存在一個提交了客戶端節(jié)點的 Server 被選舉為Leader）。

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

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

比如如何進入3副本的集群狀態(tài)。可以使用系統(tǒng)元素的 Single MemberShip 變更算法實現(xiàn)。

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

其他需要關注的事項

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

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

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

參考文獻：

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

文章來源： 網易云社區(qū)