想要學(xué)習(xí)Raft算法，最好的方式就是看作者博士論文了，詳細(xì)清晰！我將作者的博士論文翻譯和總結(jié)這篇文檔中了，想要更詳細(xì)了解的可以點(diǎn)開下面鏈接！
【騰訊文檔】Raft論文總結(jié)

再附上本人用Go語言實(shí)現(xiàn)的一個(gè)簡單版的分布式的分片KV存儲(chǔ)，項(xiàng)目中實(shí)現(xiàn)了以上Raft算法的內(nèi)容，注釋詳盡，而且實(shí)現(xiàn)了分片存儲(chǔ)，參考代碼相信可以更好的理解Raft協(xié)議！

https://github.com/LLHFWT/rachegithub.com

LLHFWT/rache原文：

大名鼎鼎的Paxos算法可能不少人都聽說過，幾乎壟斷了一致性算法領(lǐng)域，在Raft協(xié)議誕生之前，Paxos幾乎成了一致性協(xié)議的代名詞。但是對于大多數(shù)人來說，Paxos算法太難以理解了，而且難以實(shí)現(xiàn)。因此斯坦福大學(xué)的兩位教授Diego Ongaro和John Ousterhout決定設(shè)計(jì)一種更容易理解的一致性算法，最終在論文"In search of an Understandable Consensus Algorithm"中提出了Raft算法！論文原文地址：

https://raft.github.io/raft.pdfraft.github.io

這篇文章將盡量以簡單的描述，來解開這篇論文的神秘面紗。

一、復(fù)制狀態(tài)機(jī)(replicated state machine)

Raft協(xié)議可以使得一個(gè)集群的服務(wù)器組成復(fù)制狀態(tài)機(jī)，在詳細(xì)了解Raft算法之前，我們先來了解一下什么是復(fù)制狀態(tài)機(jī)。一個(gè)分布式的復(fù)制狀態(tài)機(jī)系統(tǒng)由多個(gè)復(fù)制單元組成，每個(gè)復(fù)制單元均是一個(gè)狀態(tài)機(jī)，它的狀態(tài)保存在一組狀態(tài)變量中，狀態(tài)機(jī)的變量只能通過外部命令來改變。簡單理解的話，可以想象成是一組服務(wù)器，每個(gè)服務(wù)器是一個(gè)狀態(tài)機(jī)，服務(wù)器的運(yùn)行狀態(tài)只能通過一行行的命令來改變。每一個(gè)狀態(tài)機(jī)存儲(chǔ)一個(gè)包含一系列指令的日志，嚴(yán)格按照順序逐條執(zhí)行日志中的指令，如果所有的狀態(tài)機(jī)都能按照相同的日志執(zhí)行指令，那么它們最終將達(dá)到相同的狀態(tài)。因此，在復(fù)制狀態(tài)機(jī)模型下，只要保證了操作日志的一致性，我們就能保證該分布式系統(tǒng)狀態(tài)的一致性。

image.png

在上圖中，服務(wù)器中的一致性模塊(Consensus Modle)接受來自客戶端的指令，并寫入到自己的日志中，然后通過一致性模塊和其他服務(wù)器交互，確保每一條日志都能以相同順序?qū)懭氲狡渌?wù)器的日志中，即便服務(wù)器宕機(jī)了一段時(shí)間。一旦日志命令都被正確的復(fù)制，每一臺(tái)服務(wù)器就會(huì)順序的處理命令，并向客戶端返回結(jié)果。

為了讓一致性協(xié)議變得簡單可理解，Raft協(xié)議主要使用了兩種策略。一是將復(fù)雜問題進(jìn)行分解，在Raft協(xié)議中，一致性問題被分解為：leader election、log replication、safety三個(gè)簡單問題；二是減少狀態(tài)空間中的狀態(tài)數(shù)目。下面我們詳細(xì)看一下Raft協(xié)議是怎樣設(shè)計(jì)的。

二、Raft一致性算法

在Raft體系中，有一個(gè)強(qiáng)leader，由它全權(quán)負(fù)責(zé)接收客戶端的請求命令，并將命令作為日志條目復(fù)制給其他服務(wù)器，在確認(rèn)安全的時(shí)候，將日志命令提交執(zhí)行。當(dāng)leader故障時(shí)，會(huì)選舉產(chǎn)生一個(gè)新的leader。在強(qiáng)leader的幫助下，Raft將一致性問題分解為了三個(gè)子問題：

1. leader選舉：當(dāng)已有的leader故障時(shí)必須選出一個(gè)新的leader。
2. 日志復(fù)制：leader接受來自客戶端的命令，記錄為日志，并復(fù)制給集群中的其他服務(wù)器，并強(qiáng)制其他節(jié)點(diǎn)的日志與leader保持一致。
3. 安全safety措施：通過一些措施確保系統(tǒng)的安全性，如確保所有狀態(tài)機(jī)按照相同順序執(zhí)行相同命令的措施。

1）基本概念

一個(gè)Raft集群擁有多個(gè)服務(wù)器，典型值是5，這樣可以容忍兩臺(tái)服務(wù)器出現(xiàn)故障。服務(wù)器可能會(huì)處于如下三種角色：leader、candidate、follower，正常運(yùn)行的情況下，會(huì)有一個(gè)leader，其他全為follower，follower只會(huì)響應(yīng)leader和candidate的請求，而客戶端的請求則全部由leader處理，即使有客戶端請求了一個(gè)follower也會(huì)將請求重定向到leader。candidate代表候選人，出現(xiàn)在選舉leader階段，選舉成功后candidate將會(huì)成為新的leader。可能出現(xiàn)的狀態(tài)轉(zhuǎn)換關(guān)系如下圖：

image.png

從狀態(tài)轉(zhuǎn)換關(guān)系圖中可以看出，集群剛啟動(dòng)時(shí)，所有節(jié)點(diǎn)都是follower，之后在time out信號(hào)的驅(qū)使下，follower會(huì)轉(zhuǎn)變成candidate去拉取選票，獲得大多數(shù)選票后就會(huì)成為leader，這時(shí)候如果其他候選人發(fā)現(xiàn)了新的leader已經(jīng)誕生，就會(huì)自動(dòng)轉(zhuǎn)變?yōu)閒ollower；而如果另一個(gè)time out信號(hào)發(fā)出時(shí)，還沒有選舉出leader，將會(huì)重新開始一次新的選舉?？梢?，time out信號(hào)是促使角色轉(zhuǎn)換得關(guān)鍵因素，類似于操作系統(tǒng)中得中斷信號(hào)。

在Raft協(xié)議中，將時(shí)間分成了一些任意長度的時(shí)間片，稱為term，term使用連續(xù)遞增的編號(hào)的進(jìn)行識(shí)別，如下圖所示：

image.png

每一個(gè)term都從新的選舉開始，candidate們會(huì)努力爭取稱為leader。一旦獲勝，它就會(huì)在剩余的term時(shí)間內(nèi)保持leader狀態(tài)，在某些情況下(如term3)選票可能被多個(gè)candidate瓜分，形不成多數(shù)派，因此term可能直至結(jié)束都沒有l(wèi)eader，下一個(gè)term很快就會(huì)到來重新發(fā)起選舉。

term也起到了系統(tǒng)中邏輯時(shí)鐘的作用，每一個(gè)server都存儲(chǔ)了當(dāng)前term編號(hào)，在server之間進(jìn)行交流的時(shí)候就會(huì)帶有該編號(hào)，如果一個(gè)server的編號(hào)小于另一個(gè)的，那么它會(huì)將自己的編號(hào)更新為較大的那一個(gè)；如果leader或者candidate發(fā)現(xiàn)自己的編號(hào)不是最新的了，就會(huì)自動(dòng)轉(zhuǎn)變?yōu)閒ollower；如果接收到的請求的term編號(hào)小于自己的當(dāng)前term將會(huì)拒絕執(zhí)行。

server之間的交流是通過RPC進(jìn)行的。只需要實(shí)現(xiàn)兩種RPC就能構(gòu)建一個(gè)基本的Raft集群：

• RequestVote RPC：它由選舉過程中的candidate發(fā)起，用于拉取選票
• AppendEntries RPC：它由leader發(fā)起，用于復(fù)制日志或者發(fā)送心跳信號(hào)。

它們的定義如下圖所示：

image

image.png

2）leader選舉過程

Raft通過心跳機(jī)制發(fā)起leader選舉。節(jié)點(diǎn)都是從follower狀態(tài)開始的，如果收到了來自leader或candidate的RPC，那它就保持follower狀態(tài)，避免爭搶成為candidate。Leader會(huì)發(fā)送空的AppendEntries RPC作為心跳信號(hào)來確立自己的地位，如果follower一段時(shí)間(election timeout)沒有收到心跳，它就會(huì)認(rèn)為leader已經(jīng)掛了，發(fā)起新的一輪選舉。

選舉發(fā)起后，一個(gè)follower會(huì)增加自己的當(dāng)前term編號(hào)并轉(zhuǎn)變?yōu)閏andidate。它會(huì)首先投自己一票，然后向其他所有節(jié)點(diǎn)并行發(fā)起RequestVote RPC，之后candidate狀態(tài)將可能發(fā)生如下三種變化:

• 贏得選舉,成為leader: 如果它在一個(gè)term內(nèi)收到了大多數(shù)的選票，將會(huì)在接下的剩余term時(shí)間內(nèi)稱為leader，然后就可以通過發(fā)送心跳確立自己的地位。(每一個(gè)server在一個(gè)term內(nèi)只能投一張選票，并且按照先到先得的原則投出)
• 其他server成為leader：在等待投票時(shí)，可能會(huì)收到其他server發(fā)出AppendEntries RPC心跳信號(hào)，說明其他leader已經(jīng)產(chǎn)生了。這時(shí)通過比較自己的term編號(hào)和RPC過來的term編號(hào)，如果比對方大，說明leader的term過期了，就會(huì)拒絕該RPC,并繼續(xù)保持候選人身份; 如果對方編號(hào)不比自己小,則承認(rèn)對方的地位,轉(zhuǎn)為follower.
• 選票被瓜分,選舉失敗: 如果沒有candidate獲取大多數(shù)選票, 則沒有l(wèi)eader產(chǎn)生, candidate們等待超時(shí)后發(fā)起另一輪選舉. 為了防止下一次選票還被瓜分,必須采取一些額外的措施, raft采用隨機(jī)election timeout的機(jī)制防止選票被持續(xù)瓜分。通過將timeout隨機(jī)設(shè)為一段區(qū)間上的某個(gè)值, 因此很大概率會(huì)有某個(gè)candidate率先超時(shí)然后贏得大部分選票.

3) 日志復(fù)制過程

一旦leader被選舉成功，就可以對客戶端提供服務(wù)了。客戶端提交每一條命令都會(huì)被按順序記錄到leader的日志中，每一條命令都包含term編號(hào)和順序索引，然后向其他節(jié)點(diǎn)并行發(fā)送AppendEntries RPC用以復(fù)制命令(如果命令丟失會(huì)不斷重發(fā))，當(dāng)復(fù)制成功也就是大多數(shù)節(jié)點(diǎn)成功復(fù)制后，leader就會(huì)提交命令，即執(zhí)行該命令并且將執(zhí)行結(jié)果返回客戶端，raft保證已經(jīng)提交的命令最終也會(huì)被其他節(jié)點(diǎn)成功執(zhí)行。leader會(huì)保存有當(dāng)前已經(jīng)提交的最高日志編號(hào)。順序性確保了相同日志索引處的命令是相同的，而且之前的命令也是相同的。當(dāng)發(fā)送AppendEntries RPC時(shí)，會(huì)包含leader上一條剛處理過的命令，接收節(jié)點(diǎn)如果發(fā)現(xiàn)上一條命令不匹配，就會(huì)拒絕執(zhí)行。

在這個(gè)過程中可能會(huì)出現(xiàn)一種特殊故障：如果leader崩潰了，它所記錄的日志沒有完全被復(fù)制，會(huì)造成日志不一致的情況，follower相比于當(dāng)前的leader可能會(huì)丟失幾條日志，也可能會(huì)額外多出幾條日志，這種情況可能會(huì)持續(xù)幾個(gè)term。如下圖所示：

image.png

在上圖中，框內(nèi)的數(shù)字是term編號(hào)，a、b丟失了一些命令，c、d多出來了一些命令，e、f既有丟失也有增多，這些情況都有可能發(fā)生。比如f可能發(fā)生在這樣的情況下：f節(jié)點(diǎn)在term2時(shí)是leader，在此期間寫入了幾條命令，然后在提交之前崩潰了，在之后的term3中它很快重啟并再次成為leader，又寫入了幾條日志，在提交之前又崩潰了，等他蘇醒過來時(shí)新的leader來了，就形成了上圖情形。在Raft中，leader通過強(qiáng)制follower復(fù)制自己的日志來解決上述日志不一致的情形，那么沖突的日志將會(huì)被重寫。為了讓日志一致，先找到最新的一致的那條日志(如f中索引為3的日志條目)，然后把follower之后的日志全部刪除，leader再把自己在那之后的日志一股腦推送給follower，這樣就實(shí)現(xiàn)了一致。而尋找該條日志，可以通過AppendEntries RPC，該RPC中包含著下一次要執(zhí)行的命令索引，如果能和follower的當(dāng)前索引對上，那就執(zhí)行，否則拒絕，然后leader將會(huì)逐次遞減索引，直到找到相同的那條日志。

然而這樣也還是會(huì)有問題，比如某個(gè)follower在leader提交時(shí)宕機(jī)了，也就是少了幾條命令，然后它又經(jīng)過選舉成了新的leader，這樣它就會(huì)強(qiáng)制其他follower跟自己一樣，使得其他節(jié)點(diǎn)上剛剛提交的命令被刪除，導(dǎo)致客戶端提交的一些命令被丟失了，下面一節(jié)內(nèi)容將會(huì)解決這個(gè)問題。Raft通過為選舉過程添加一個(gè)限制條件，解決了上面提出的問題，該限制確保leader包含之前term已經(jīng)提交過的所有命令。Raft通過投票過程確保只有擁有全部已提交日志的candidate能成為leader。由于candidate為了拉選票需要通過RequestVote RPC聯(lián)系其他節(jié)點(diǎn)，而之前提交的命令至少會(huì)存在于其中某一個(gè)節(jié)點(diǎn)上,因此只要candidate的日志至少和其他大部分節(jié)點(diǎn)的一樣新就可以了, follower如果收到了不如自己新的candidate的RPC,就會(huì)將其丟棄.

還可能會(huì)出現(xiàn)另外一個(gè)問題, 如果命令已經(jīng)被復(fù)制到了大部分節(jié)點(diǎn)上,但是還沒來的及提交就崩潰了,這樣后來的leader應(yīng)該完成之前term未完成的提交. Raft通過讓leader統(tǒng)計(jì)當(dāng)前term內(nèi)還未提交的命令已經(jīng)被復(fù)制的數(shù)量是否半數(shù)以上, 然后進(jìn)行提交.

4）日志壓縮

隨著日志大小的增長，會(huì)占用更多的內(nèi)存空間，處理起來也會(huì)耗費(fèi)更多的時(shí)間，對系統(tǒng)的可用性造成影響，因此必須想辦法壓縮日志大小。Snapshotting是最簡單的壓縮方法，系統(tǒng)的全部狀態(tài)會(huì)寫入一個(gè)snapshot保存起來，然后丟棄截止到snapshot時(shí)間點(diǎn)之前的所有日志。Raft中的snapshot內(nèi)容如下圖所示：

image.png

每一個(gè)server都有自己的snapshot，它只保存當(dāng)前狀態(tài)，如上圖中的當(dāng)前狀態(tài)為x=0,y=9，而last included index和last included term代表snapshot之前最新的命令，用于AppendEntries的狀態(tài)檢查。

雖然每一個(gè)server都保存有自己的snapshot，但是當(dāng)follower嚴(yán)重落后于leader時(shí)，leader需要把自己的snapshot發(fā)送給follower加快同步，此時(shí)用到了一個(gè)新的RPC：InstallSnapshot RPC。follower收到snapshot時(shí)，需要決定如何處理自己的日志，如果收到的snapshot包含有更新的信息，它將丟棄自己已有的日志，按snapshot更新自己的狀態(tài)，如果snapshot包含的信息更少，那么它會(huì)丟棄snapshot中的內(nèi)容，但是自己之后的內(nèi)容會(huì)保存下來。RPC的定義如下：

image

到此為止，Raft協(xié)議的主要內(nèi)容我們就介紹完了，希望此文可以幫助大家理解Raft協(xié)議！

原文鏈接 <<<===