前言

我們之前講述了 Paxos 一致性算法，雖然樓主嘗試用最簡(jiǎn)單的算法來(lái)闡述，但仍然還是有點(diǎn)繞。樓主最初懷疑自己太笨，后來(lái)才直到，該算法的晦澀難懂不是只有我一個(gè)人這么認(rèn)為，而是國(guó)際公認(rèn)！

所以 Paxos 算法在 1990 就發(fā)表出來(lái)，但卻得不到運(yùn)用。真正的名聲大噪還是在蘭伯特使用 “更簡(jiǎn)單” 的方式重寫(xiě)了一篇論文才開(kāi)始。

這些和今天說(shuō)的 Raft 有什么關(guān)系呢？

答：Raft 也是一個(gè)一致性算法，和 Paxos 目標(biāo)相同。但他還有另一個(gè)名字：易于理解的一致性算法。

也就是說(shuō)，他的目標(biāo)就是成為一個(gè)易于理解的一致性算法。以替代 Paxos 的晦澀難懂。

那我們就開(kāi)始講講 Raft 算法吧！

1. 什么是 Raft 算法

首先說(shuō)什么是 Raft 算法：Raft 是一種為了管理復(fù)制日志的一致性算法。

什么是一致性呢？
Raft 的論文這么說(shuō)的：一致性算法允許一組機(jī)器像一個(gè)整體一樣工作，即使其中一些機(jī)器出現(xiàn)故障也能夠繼續(xù)工作下去。

這里的一致性針對(duì)分布式系統(tǒng)。

什么是管理日志呢？
一致性算法是從復(fù)制狀態(tài)機(jī)的背景下提出的，復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實(shí)現(xiàn)的，這個(gè)日志可以理解為一個(gè)比喻，相當(dāng)于一個(gè)指令。

關(guān)于狀態(tài)機(jī)的描述：

多個(gè)節(jié)點(diǎn)上，從相同的初始狀態(tài)開(kāi)始，執(zhí)行相同的一串命令，產(chǎn)生相同的最終狀態(tài)。實(shí)際上，與其說(shuō)是一致，其實(shí)可以泛化為分布式的兩個(gè)節(jié)點(diǎn)狀態(tài)存在某種約束。
復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實(shí)現(xiàn)的，保證復(fù)制日志相同就是一致性算法的工作了。
典型應(yīng)用就是一個(gè)獨(dú)立的的復(fù)制狀態(tài)機(jī)去管理領(lǐng)導(dǎo)選舉和存儲(chǔ)配置信息并且在領(lǐng)導(dǎo)人宕機(jī)的情況下也要存活下來(lái)。比如 Chubby 和 ZooKeeper。

對(duì)于 Raft 更重要的應(yīng)該是 易于理解。從 Raft 的論文題目就可以看出：In Search of an Understandable Consensus Algorithm (Extended Version)。這里的易于理解是相對(duì)于 Paxos 的，在他的論文中，和 Paxos 做了大量針對(duì) 易于理解 的對(duì)比和統(tǒng)計(jì)測(cè)試。

從樓主閱讀論文的過(guò)程中來(lái)看，Raft 相較于 Paxos 確實(shí)更易于理解。為了提升可理解性，Raft 將一致性算法分解成了幾個(gè)關(guān)鍵模塊，例如領(lǐng)導(dǎo)人選舉、日志復(fù)制和安全性。

而和一致性最相關(guān)的就是前面 2 個(gè)模塊：領(lǐng)導(dǎo)人選舉和日志復(fù)制。

2. 領(lǐng)導(dǎo)人選舉

Raft 通過(guò)選舉一個(gè)高貴的領(lǐng)導(dǎo)人，然后給予他全部的管理復(fù)制日志的責(zé)任來(lái)實(shí)現(xiàn)一致性。

而每個(gè) server 都可能會(huì)在 3 個(gè)身份之間切換：

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

而影響他們身份變化的則是 選舉。
當(dāng)所有服務(wù)器初始化的時(shí)候，都是 跟隨者，這個(gè)時(shí)候需要一個(gè) 領(lǐng)導(dǎo)者，所有人都變成 候選者，直到有人成功當(dāng)選 領(lǐng)導(dǎo)者。

角色輪換如下圖：

角色變化圖

而領(lǐng)導(dǎo)者也有宕機(jī)的時(shí)候，宕機(jī)后引發(fā)新的 選舉，所以，整個(gè)集群在選舉和正常運(yùn)行之間切換，具體如下圖：

image.png

從上圖可以看出，選舉和正常運(yùn)行之間切換，但請(qǐng)注意， 上圖中的 term 3 有一個(gè)地方，后面沒(méi)有跟著 正常運(yùn)行 階段，為什么呢?

答：當(dāng)一次選舉失?。ū热缯擅總€(gè)人都投了自己），就執(zhí)行一次 加時(shí)賽，每個(gè) Server 會(huì)在一個(gè)隨機(jī)的時(shí)間里重新投票，這樣就能保證不沖突了。所以，當(dāng) term 3 選舉失敗，等了幾十毫秒，執(zhí)行 term 4 選舉，并成功選舉出領(lǐng)導(dǎo)人。

接著，領(lǐng)導(dǎo)者周期性的向所有跟隨者發(fā)送心跳包來(lái)維持自己的權(quán)威。如果一個(gè)跟隨者在一段時(shí)間里沒(méi)有接收到任何消息，也就是選舉超時(shí)，那么他就會(huì)認(rèn)為系統(tǒng)中沒(méi)有可用的領(lǐng)導(dǎo)者,并且發(fā)起選舉以選出新的領(lǐng)導(dǎo)者。

要開(kāi)始一次選舉過(guò)程，跟隨者先要增加自己的當(dāng)前任期號(hào)并且轉(zhuǎn)換到候選人狀態(tài)。然后請(qǐng)求其他服務(wù)器為自己投票。那么會(huì)產(chǎn)生 3 種結(jié)果：

a. 自己成功當(dāng)選
b. 其他的服務(wù)器成為領(lǐng)導(dǎo)者
c. 僵住，沒(méi)有任何一個(gè)人成為領(lǐng)導(dǎo)者

注意：

1. 每一個(gè) server 最多在一個(gè)任期內(nèi)投出一張選票（有任期號(hào)約束），先到先得。
2. 要求最多只能有一個(gè)人贏得選票。
3. 一旦成功，立即成為領(lǐng)導(dǎo)人，然后廣播所有服務(wù)器停止投票阻止新得領(lǐng)導(dǎo)產(chǎn)生。

僵住怎么辦？ Raft 通過(guò)使用隨機(jī)選舉超時(shí)時(shí)間（例如 150 - 300 毫秒）的方法將服務(wù)器打散投票。每個(gè)候選人在僵住的時(shí)候會(huì)隨機(jī)從一個(gè)時(shí)間開(kāi)始重新選舉。

以上，就是 Raft 所有關(guān)于領(lǐng)導(dǎo)選舉的策略。

3. 日志復(fù)制

一旦一個(gè)領(lǐng)導(dǎo)人被選舉出來(lái)，他就開(kāi)始為客戶端提供服務(wù)。

客戶端發(fā)送日志給領(lǐng)導(dǎo)者，隨后領(lǐng)導(dǎo)者將日志復(fù)制到其他的服務(wù)器。如果跟隨者故障，領(lǐng)導(dǎo)者將會(huì)嘗試重試。直到所有的跟隨者都成功存儲(chǔ)了所有日志。

下圖表示了當(dāng)一個(gè)客戶端發(fā)送一個(gè)日志給領(lǐng)導(dǎo)者，隨后領(lǐng)導(dǎo)者復(fù)制給跟隨者的整個(gè)過(guò)程。

image.png

4 個(gè)步驟：

1. 客戶端提交
2. 復(fù)制數(shù)據(jù)到所有跟隨者
3. 跟隨者回復(fù) 確認(rèn)收到
4. 領(lǐng)導(dǎo)者回復(fù)客戶端和所有跟隨者 確認(rèn)提交。

可以看到，直到第四步驟，整個(gè)事務(wù)才會(huì)達(dá)成。中間任何一個(gè)步驟發(fā)生故障，都不會(huì)影響日志一致性。

4. 總結(jié)

總結(jié)一下本文吧：

Raft 算法如同他的論文名字一樣：尋找一種易于理解的一致性算法，這里的 易于理解 是相對(duì)于 Paxos 的，的確，Paxos 實(shí)在過(guò)于復(fù)雜了。

而如何實(shí)現(xiàn)易于理解？

答：Raft 將一致性算法分成了2部分：領(lǐng)導(dǎo)選舉，日志復(fù)制。

領(lǐng)導(dǎo)選舉基于一個(gè)隨機(jī)的時(shí)間來(lái)保證不會(huì)沖突（如果沖突的話）。
而日志復(fù)制則類似于 2PC。

通常 5 個(gè)節(jié)點(diǎn)，只要不超過(guò) 2 個(gè)節(jié)點(diǎn)死亡都不會(huì)影響系統(tǒng)的運(yùn)行。保證了系統(tǒng)的可用性，通過(guò)領(lǐng)導(dǎo)者的日志復(fù)制，實(shí)現(xiàn)了系統(tǒng)的一致性。

似乎 CAP 定理已經(jīng)不起作用了，當(dāng)然這又是一個(gè)重大的話題。

最后，以 Raft 論文的結(jié)尾結(jié)束本位：

算法的設(shè)計(jì)通常會(huì)把正確性，效率或者簡(jiǎn)潔作為主要的目標(biāo)。盡管這些都是很有意義的目標(biāo)，但是我們相信，可理解性也是一樣的重要。在開(kāi)發(fā)者把算法應(yīng)用到實(shí)際的系統(tǒng)中之前，這些目標(biāo)沒(méi)有一個(gè)會(huì)被實(shí)現(xiàn)，這些都會(huì)必然的偏離發(fā)表時(shí)的形式。除非開(kāi)發(fā)人員對(duì)這個(gè)算法有著很深的理解并且有著直觀的感覺(jué)，否則將會(huì)對(duì)他們而言很難在實(shí)現(xiàn)的時(shí)候保持原有期望的特性。

引用

尋找一種易于理解的一致性算法（擴(kuò)展版）Raft 中文翻譯
Raft 英文原文
Raft 為什么是更易理解的分布式一致性算法