1. Raft 算法簡介

1.1 Raft 背景

在分布式系統(tǒng)中，一致性算法至關(guān)重要。在所有一致性算法中，Paxos 最負盛名，它由萊斯利·蘭伯特（Leslie Lamport）于 1990 年提出，是一種基于消息傳遞的一致性算法，被認為是類似算法中最有效的。

Paxos 算法雖然很有效，但復(fù)雜的原理使它實現(xiàn)起來非常困難，截止目前，實現(xiàn) Paxos 算法的開源軟件很少，比較出名的有 Chubby、LibPaxos。此外，Zookeeper 采用的 ZAB（Zookeeper Atomic Broadcast）協(xié)議也是基于 Paxos 算法實現(xiàn)的，不過 ZAB 對 Paxos 進行了很多改進與優(yōu)化，兩者的設(shè)計目標也存在差異——ZAB 協(xié)議主要用于構(gòu)建一個高可用的分布式數(shù)據(jù)主備系統(tǒng)，而 Paxos 算法則是用于構(gòu)建一個分布式的一致性狀態(tài)機系統(tǒng)。

由于 Paxos 算法過于復(fù)雜、實現(xiàn)困難，極大地制約了其應(yīng)用，而分布式系統(tǒng)領(lǐng)域又亟需一種高效而易于實現(xiàn)的分布式一致性算法，在此背景下，Raft 算法應(yīng)運而生。

Raft 算法在斯坦福 Diego Ongaro 和 John Ousterhout 于 2013 年發(fā)表的《In Search of an Understandable Consensus Algorithm》中提出。相較于 Paxos，Raft 通過邏輯分離使其更容易理解和實現(xiàn)，目前，已經(jīng)有十多種語言的 Raft 算法實現(xiàn)框架，較為出名的有 etcd、Consul 。

1.2 Raft 角色

根據(jù)官方文檔解釋，一個 Raft 集群包含若干節(jié)點，Raft 把這些節(jié)點分為三種狀態(tài)：Leader、 Follower、Candidate，每種狀態(tài)負責(zé)的任務(wù)也是不一樣的。正常情況下，集群中的節(jié)點只存在 Leader 與 Follower 兩種狀態(tài)。

? Leader（領(lǐng)導(dǎo)者） ：負責(zé)日志的同步管理，處理來自客戶端的請求，與Follower保持heartBeat的聯(lián)系；

? Follower（追隨者） ：響應(yīng) Leader 的日志同步請求，響應(yīng)Candidate的邀票請求，以及把客戶端請求到Follower的事務(wù)轉(zhuǎn)發(fā)（重定向）給Leader；

? Candidate（候選者） ：負責(zé)選舉投票，集群剛啟動或者Leader宕機時，狀態(tài)為Follower的節(jié)點將轉(zhuǎn)為Candidate并發(fā)起選舉，選舉勝出（獲得超過半數(shù)節(jié)點的投票）后，從Candidate轉(zhuǎn)為Leader狀態(tài)。

1.3 Raft 三個子問題

通常，Raft 集群中只有一個 Leader，其它節(jié)點都是 Follower。Follower 都是被動的，不會發(fā)送任何請求，只是簡單地響應(yīng)來自 Leader 或者 Candidate 的請求。Leader 負責(zé)處理所有的客戶端請求（如果一個客戶端和 Follower 聯(lián)系，那么 Follower 會把請求重定向給 Leader）。

為簡化邏輯和實現(xiàn)，Raft 將一致性問題分解成了三個相對獨立的子問題。

? 選舉（Leader Election） ：當(dāng) Leader 宕機或者集群初創(chuàng)時，一個新的 Leader 需要被選舉出來；

? 日志復(fù)制（Log Replication） ：Leader 接收來自客戶端的請求并將其以日志條目的形式復(fù)制到集群中的其它節(jié)點，并且強制要求其它節(jié)點的日志和自己保持一致；

? 安全性（Safety） ：如果有任何的服務(wù)器節(jié)點已經(jīng)應(yīng)用了一個確定的日志條目到它的狀態(tài)機中，那么其它服務(wù)器節(jié)點不能在同一個日志索引位置應(yīng)用一個不同的指令。

2. Raft 算法之 Leader Election 原理

根據(jù) Raft 協(xié)議，一個應(yīng)用 Raft 協(xié)議的集群在剛啟動時，所有節(jié)點的狀態(tài)都是 Follower。由于沒有 Leader，F(xiàn)ollowers 無法與 Leader 保持心跳（Heart Beat），因此，F(xiàn)ollowers 會認為 Leader 已經(jīng)下線，進而轉(zhuǎn)為 Candidate 狀態(tài)。然后，Candidate 將向集群中其它節(jié)點請求投票，同意自己升級為 Leader。如果 Candidate 收到超過半數(shù)節(jié)點的投票（N/2 + 1），它將獲勝成為 Leader。

第一階段：所有節(jié)點都是 Follower。

上面提到，一個應(yīng)用 Raft 協(xié)議的集群在剛啟動（或 Leader 宕機）時，所有節(jié)點的狀態(tài)都是 Follower，初始 Term（任期）為 0。同時啟動選舉定時器，每個節(jié)點的選舉定時器超時時間都在 100~500 毫秒之間且并不一致（避免同時發(fā)起選舉）。

所有節(jié)點都是 Follower

第二階段：Follower 轉(zhuǎn)為 Candidate 并發(fā)起投票。

沒有 Leader，F(xiàn)ollowers 無法與 Leader 保持心跳（Heart Beat），節(jié)點啟動后在一個選舉定時器周期內(nèi)未收到心跳和投票請求，則狀態(tài)轉(zhuǎn)為候選者 Candidate 狀態(tài)，且 Term 自增，并向集群中所有節(jié)點發(fā)送投票請求并且重置選舉定時器。

注意，由于每個節(jié)點的選舉定時器超時時間都在 100-500 毫秒之間，且彼此不一樣，以避免所有 Follower 同時轉(zhuǎn)為 Candidate 并同時發(fā)起投票請求。換言之，最先轉(zhuǎn)為 Candidate 并發(fā)起投票請求的節(jié)點將具有成為 Leader 的“先發(fā)優(yōu)勢”。

Follower 轉(zhuǎn)為 Candidate 并發(fā)起投票

第三階段：投票策略。

節(jié)點收到投票請求后會根據(jù)以下情況決定是否接受投票請求（每個 follower 剛成為 Candidate 的時候會將票投給自己）：

請求節(jié)點的 Term 大于自己的 Term，且自己尚未投票給其它節(jié)點，則接受請求，把票投給它；

請求節(jié)點的 Term 小于自己的 Term，且自己尚未投票，則拒絕請求，將票投給自己。

投票策略

第四階段：Candidate 轉(zhuǎn)為 Leader。

一輪選舉過后，正常情況下，會有一個 Candidate 收到超過半數(shù)節(jié)點（N/2 + 1）的投票，它將勝出并升級為 Leader。然后定時發(fā)送心跳給其它的節(jié)點，其它節(jié)點會轉(zhuǎn)為 Follower 并與 Leader 保持同步，到此，本輪選舉結(jié)束。

注意：有可能一輪選舉中，沒有 Candidate 收到超過半數(shù)節(jié)點投票，那么將進行下一輪選舉。

Candidate 轉(zhuǎn)為 Leader

3. Raft 算法之 Log Replication 原理

在一個 Raft 集群中，只有 Leader 節(jié)點能夠處理客戶端的請求（如果客戶端的請求發(fā)到了 Follower，F(xiàn)ollower 將會把請求重定向到 Leader），客戶端的每一個請求都包含一條被復(fù)制狀態(tài)機執(zhí)行的指令。Leader 把這條指令作為一條新的日志條目（Entry）附加到日志中去，然后并行得將附加條目發(fā)送給 Followers，讓它們復(fù)制這條日志條目。

當(dāng)這條日志條目被 Followers 安全復(fù)制，Leader 會將這條日志條目應(yīng)用到它的狀態(tài)機中，然后把執(zhí)行的結(jié)果返回給客戶端。如果 Follower 崩潰或者運行緩慢，再或者網(wǎng)絡(luò)丟包，Leader 會不斷得重復(fù)嘗試附加日志條目（盡管已經(jīng)回復(fù)了客戶端）直到所有的 Follower 都最終存儲了所有的日志條目，確保強一致性。

第一階段：客戶端請求提交到 Leader。

如下圖所示，Leader 收到客戶端的請求，比如存儲數(shù)據(jù) 5。Leader 在收到請求后，會將它作為日志條目（Entry）寫入本地日志中。需要注意的是，此時該 Entry 的狀態(tài)是未提交（Uncommitted），Leader 并不會更新本地數(shù)據(jù)，因此它是不可讀的。

客戶端請求提交到 Leader

第二階段：Leader 將 Entry 發(fā)送到其它 Follower

Leader 與 Followers 之間保持著心跳聯(lián)系，隨心跳 Leader 將追加的 Entry（AppendEntries）并行地發(fā)送給其它的 Follower，并讓它們復(fù)制這條日志條目，這一過程稱為復(fù)制（Replicate）。

有幾點需要注意：

1. 為什么 Leader 向 Follower 發(fā)送的 Entry 是 AppendEntries 呢？

因為 Leader 與 Follower 的心跳是周期性的，而一個周期間 Leader 可能接收到多條客戶端的請求，因此，隨心跳向 Followers 發(fā)送的大概率是多個 Entry，即 AppendEntries。當(dāng)然，在本例中，我們假設(shè)只有一條請求，自然也就是一個Entry了。

2. Leader 向 Followers 發(fā)送的不僅僅是追加的 Entry（AppendEntries）。

在發(fā)送追加日志條目的時候，Leader 會把新的日志條目緊接著之前條目的索引位置（prevLogIndex）， Leader 任期號（Term）也包含在其中。如果 Follower 在它的日志中找不到包含相同索引位置和任期號的條目，那么它就會拒絕接收新的日志條目，因為出現(xiàn)這種情況說明 Follower 和 Leader 不一致。

3. 如何解決 Leader 與 Follower 不一致的問題？

在正常情況下，Leader 和 Follower 的日志保持一致，所以追加日志的一致性檢查從來不會失敗。然而，Leader 和 Follower 一系列崩潰的情況會使它們的日志處于不一致狀態(tài)。Follower可能會丟失一些在新的 Leader 中有的日志條目，它也可能擁有一些 Leader 沒有的日志條目，或者兩者都發(fā)生。丟失或者多出日志條目可能會持續(xù)多個任期。

要使 Follower 的日志與 Leader 恢復(fù)一致，Leader 必須找到最后兩者達成一致的地方（說白了就是回溯，找到兩者最近的一致點），然后刪除從那個點之后的所有日志條目，發(fā)送自己的日志給 Follower。所有的這些操作都在進行附加日志的一致性檢查時完成。

Leader 為每一個 Follower 維護一個 nextIndex，它表示下一個需要發(fā)送給 Follower 的日志條目的索引地址。當(dāng)一個 Leader 剛獲得權(quán)力的時候，它初始化所有的 nextIndex 值，為自己的最后一條日志的 index 加 1。如果一個 Follower 的日志和 Leader 不一致，那么在下一次附加日志時一致性檢查就會失敗。在被 Follower 拒絕之后，Leader 就會減小該 Follower 對應(yīng)的 nextIndex 值并進行重試。最終 nextIndex 會在某個位置使得 Leader 和 Follower 的日志達成一致。當(dāng)這種情況發(fā)生，附加日志就會成功，這時就會把 Follower 沖突的日志條目全部刪除并且加上 Leader 的日志。一旦附加日志成功，那么 Follower 的日志就會和 Leader 保持一致，并且在接下來的任期繼續(xù)保持一致。

如何解決 Leader 與 Follower 不一致的問題

第三階段：Leader 等待 Followers 回應(yīng)。

Followers 接收到 Leader 發(fā)來的復(fù)制請求后，有兩種可能的回應(yīng)：

寫入本地日志中，返回 Success；

一致性檢查失敗，拒絕寫入，返回 False，原因和解決辦法上面已做了詳細說明。

需要注意的是，此時該 Entry 的狀態(tài)也是未提交（Uncommitted）。完成上述步驟后，F(xiàn)ollowers 會向 Leader 發(fā)出 Success 的回應(yīng)，當(dāng) Leader 收到大多數(shù) Followers 的回應(yīng)后，會將第一階段寫入的 Entry 標記為提交狀態(tài)（Committed），并把這條日志條目應(yīng)用到它的狀態(tài)機中。

Leader 等待 Followers 回應(yīng)

第四階段：Leader 回應(yīng)客戶端。

完成前三個階段后，Leader會向客戶端回應(yīng) OK，表示寫操作成功。

Leader 回應(yīng)客戶端

第五階段，Leader 通知 Followers Entry 已提交

Leader 回應(yīng)客戶端后，將隨著下一個心跳通知 Followers，F(xiàn)ollowers 收到通知后也會將 Entry 標記為提交狀態(tài)。至此，Raft 集群超過半數(shù)節(jié)點已經(jīng)達到一致狀態(tài)，可以確保強一致性。

需要注意的是，由于網(wǎng)絡(luò)、性能、故障等各種原因?qū)е隆胺磻?yīng)慢”、“不一致”等問題的節(jié)點，最終也會與 Leader 達成一致。

Leader 通知 Followers Entry 已提交

4. Raft 算法之安全性

前面描述了 Raft 算法是如何選舉 Leader 和復(fù)制日志的。然而，到目前為止描述的機制并不能充分地保證每一個狀態(tài)機會按照相同的順序執(zhí)行相同的指令。例如，一個 Follower 可能處于不可用狀態(tài)，同時 Leader 已經(jīng)提交了若干的日志條目；然后這個 Follower 恢復(fù)（尚未與 Leader 達成一致）而 Leader 故障；如果該 Follower 被選舉為 Leader 并且覆蓋這些日志條目，就會出現(xiàn)問題，即不同的狀態(tài)機執(zhí)行不同的指令序列。

鑒于此，在 Leader 選舉的時候需增加一些限制來完善 Raft 算法。這些限制可保證任何的 Leader 對于給定的任期號（Term），都擁有之前任期的所有被提交的日志條目（所謂 Leader 的完整特性）。關(guān)于這一選舉時的限制，下文將詳細說明。

4.1 選舉限制

在所有基于 Leader 機制的一致性算法中，Leader 都必須存儲所有已經(jīng)提交的日志條目。為了保障這一點，Raft 使用了一種簡單而有效的方法，以保證所有之前的任期號中已經(jīng)提交的日志條目在選舉的時候都會出現(xiàn)在新的 Leader 中。換言之，日志條目的傳送是單向的，只從 Leader 傳給 Follower，并且 Leader 從不會覆蓋自身本地日志中已經(jīng)存在的條目。

Raft 使用投票的方式來阻止一個 Candidate 贏得選舉，除非這個 Candidate 包含了所有已經(jīng)提交的日志條目。Candidate 為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點。這意味著每一個已經(jīng)提交的日志條目肯定存在于至少一個服務(wù)器節(jié)點上。如果 Candidate 的日志至少和大多數(shù)的服務(wù)器節(jié)點一樣新（這個新的定義會在下面討論），那么它一定持有了所有已經(jīng)提交的日志條目（多數(shù)派的思想）。投票請求的限制中請求中包含了 Candidate 的日志信息，然后投票人會拒絕那些日志沒有自己新的投票請求。

Raft 通過比較兩份日志中最后一條日志條目的索引值和任期號，確定誰的日志比較新。如果兩份日志最后條目的任期號不同，那么任期號大的日志更加新。如果兩份日志最后的條目任期號相同，那么日志比較長的那個就更加新。

4.2 提交之前任期內(nèi)的日志條目

如同 4.1 節(jié)介紹的那樣，Leader 知道一條當(dāng)前任期內(nèi)的日志記錄是可以被提交的，只要它被復(fù)制到了大多數(shù)的 Follower 上（多數(shù)派的思想）。如果一個 Leader 在提交日志條目之前崩潰了，繼任的 Leader 會繼續(xù)嘗試復(fù)制這條日志記錄。然而，一個 Leader 并不能斷定被保存到大多數(shù) Follower 上的一個之前任期里的日志條目 就一定已經(jīng)提交了。這很明顯，從日志復(fù)制的過程可以看出。

鑒于上述情況，Raft 算法不會通過計算副本數(shù)目的方式去提交一個之前任期內(nèi)的日志條目。只有 Leader 當(dāng)前任期里的日志條目通過計算副本數(shù)目可以被提交；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性，之前的日志條目也都會被間接的提交。在某些情況下，Leader 可以安全地知道一個老的日志條目是否已經(jīng)被提交（只需判斷該條目是否存儲到所有節(jié)點上），但是 Raft 為了簡化問題使用了一種更加保守的方法。

當(dāng) Leader 復(fù)制之前任期里的日志時，Raft 會為所有日志保留原始的任期號，這在提交規(guī)則上產(chǎn)生了額外的復(fù)雜性。但是，這種策略更加容易辨別出日志，即使隨著時間和日志的變化，日志仍維護著同一個任期編號。此外，該策略使得新 Leader 只需要發(fā)送較少日志條目。

5、線性化語義

raft 的讀寫都在 leader 節(jié)點中進行，它保證了讀的都是最新的值，它是符合強一致性的（線性一致性），raft 除了這個還在【客戶端交互】那塊也做了一些保證，詳情可以參考論文。但是 zookeeper 不同，zookeeper 寫在 leader，讀可以在 follower 進行，可能會讀到了舊值，它不符合強一致性（只考慮寫一致性，不考慮讀一致性），但是 zookeeper 去 follower 讀可以有效提升讀取的效率。

6、后記

對比于 zab、raft，我們發(fā)現(xiàn)他們選舉、setData 都是需要過半機制才行，所以他們針對網(wǎng)絡(luò)分區(qū)的處理方法都是一樣的。

一個集群的節(jié)點經(jīng)過網(wǎng)絡(luò)分區(qū)后，如一共有 A、B、C、D、E 5個節(jié)點，如果 A 是 leader，網(wǎng)絡(luò)分區(qū)為 A、B、C 和 D、E，在A、B、C分區(qū)還是能正常提供服務(wù)的，而在 D、E 分區(qū)因為不能得到大多數(shù)成員確認（雖然分區(qū)了，但是因為配置的原因他們還是能知道所有的成員數(shù)量，比如 zk 集群啟動前需要配置所有成員地址，raft 也一樣），是不能進行選舉的，所以保證只會有一個 leader。

如果分區(qū)為 A、B 和 C、D、E ，A、B 分區(qū)雖然 A 還是 leader，但是卻不能提供事務(wù)服務(wù)（setData），C、D、E 分區(qū)能重新選出 leader，還是能正常向外提供服務(wù)。

7、后記2

1）我們所說的日志（log）與狀態(tài)機（state machine）不是一回事，日志指還沒有提交到狀態(tài)機中的數(shù)據(jù)。
2）新 leader 永遠不會通過計算副本數(shù)量提交舊日志，他只能復(fù)制舊日志都其他 follower 上，對于舊日志的提交，只能是新 leader 接收新的寫請求寫新日志，順帶著把舊日志提交了。

8、后記3

為什么采取隨機超時時間變成 candidate 獲取選票，是為了防止導(dǎo)致沒有任何一個 Candidate 選票數(shù)超過一半的情況重復(fù)循環(huán)發(fā)生。比如有 3 個 Candidate ，都得不到多數(shù)選票，指的是都同時變成 candidate 然后都投給自己，然后都不會投給別人（如果日志都相同的情況下，如果自己日志落后于別人或者任期落后于別人，自己就會 stepDown，選票清空角色變成 follower）。然而其中某個 Candidate C1 超時短，立刻重新開始新的選舉，那么基本上就可以平定局勢了。注意，此時另外兩個 Candidate C2 和 Candidate C3 雖然也處于 Candidate 狀態(tài)，但是收到了 Candidate C1 的競選請求，并且發(fā)現(xiàn) C1 的任期號比自己大，會立刻變?yōu)?Follower ，并且投票給 C1 。