很久之前研究過raft協(xié)議，最近項目中一直沒有使用，有些生疏了，這次重溫了一下raft，花了兩天的時間，就順便做下筆記。

一致性問題

在分布式系統(tǒng)中,一致性問題(consensus problem)是指對于一組服務(wù)器，給定一組操作，我們需要一個協(xié)議使得最后它們的結(jié)果達(dá)成一致。

由于CAP理論告訴我們對于分布式系統(tǒng)，如果不想犧牲一致性，我們就只能放棄可用性，所以，數(shù)據(jù)一致性模型主要有以下幾種：強(qiáng)一致性、弱一致性和最終一致性等，在本篇章中，我們主要討論的算法Raft，是一種分布式系統(tǒng)中的強(qiáng)一致性的實現(xiàn)算法。

強(qiáng)一致性的一般實現(xiàn)的原理：當(dāng)其中某個服務(wù)器收到客戶端的一組指令時,它必須與其它服務(wù)器交流以保證所有的服務(wù)器都是以同樣的順序收到同樣的指令,這樣的話所有的服務(wù)器會產(chǎn)生一致的結(jié)果,看起來就像是一臺機(jī)器一樣.

Raft算法描述

在Raft被提出來之前，Paxos協(xié)議是第一個被證明的一致性算法，但是Paxos的論文非常難懂，導(dǎo)致基于Paxos的工程實踐和教學(xué)都十分頭疼，于是Raft在設(shè)計的過程中，就從可理解性出發(fā)，使用算法分解和減少狀態(tài)等手段，目前已經(jīng)應(yīng)用非常廣泛。

在Raft中，問題分解為：領(lǐng)導(dǎo)選取、日志復(fù)制、安全和成員變化。

基本概念

復(fù)制狀態(tài)機(jī)（Replicated State Machine）

1.png

• 復(fù)制狀態(tài)機(jī)通過復(fù)制日志來實現(xiàn)：

  • 日志：每臺機(jī)器保存一份日志，日志來自于客戶端的請求，包含一系列的命令
  • 狀態(tài)機(jī)：狀態(tài)機(jī)會按順序執(zhí)行這些命令
  • 一致性模型：分布式環(huán)境下，保證多機(jī)的日志是一致的，這樣回放到狀態(tài)機(jī)中的狀態(tài)是一致的

• 一致性算法作用于一致性模型，一般有以下特性：

  • safety：在非拜占庭問題下（網(wǎng)絡(luò)延時，網(wǎng)絡(luò)分區(qū)，丟包，重復(fù)發(fā)包以及包亂序等），結(jié)果是正確的
  • availability：在半數(shù)以上機(jī)器能正常工作時，則系統(tǒng)可用
  • timing-unindependent：不依賴于時鐘來保證日志一致性，錯誤的時鐘以及極端的消息時延最多會造成可用性問題

注意：
真實的實現(xiàn)中，建議狀態(tài)機(jī)的每個命令操作都采用冪等的，這樣一致性的保證會更容易。

服務(wù)器狀態(tài)

每臺服務(wù)器一定會處于三種狀態(tài)：

1. 領(lǐng)導(dǎo)者
2. 候選人
3. 追隨者

2.png

追隨者只響應(yīng)其他服務(wù)器的請求。如果追隨者沒有收到任何消息，它會成為一個候選人并且開始一次選舉。收到大多數(shù)服務(wù)器投票的候選人會成為新的領(lǐng)導(dǎo)人。領(lǐng)導(dǎo)人在它們宕機(jī)之前會一直保持領(lǐng)導(dǎo)人的狀態(tài)。

任期(Term)

Raft 算法將時間劃分成為任意不同長度的任期（term）。任期用連續(xù)的數(shù)字進(jìn)行表示。每一個任期的開始都是一次選舉（election），一個或多個候選人會試圖成為領(lǐng)導(dǎo)人。如果一個候選人贏得了選舉，它就會在該任期的剩余時間擔(dān)任領(lǐng)導(dǎo)人。在某些情況下，選票會被瓜分，有可能沒有選出領(lǐng)導(dǎo)人，那么，將會開始另一個任期，并且立刻開始下一次選舉。Raft 算法保證在給定的一個任期最多只有一個領(lǐng)導(dǎo)人。

3.png

RPC

Raft 算法中服務(wù)器節(jié)點之間通信使用遠(yuǎn)程過程調(diào)用（RPCs），并且基本的一致性算法只需要兩種類型的 RPCs。請求投票（RequestVote） RPCs 由候選人在選舉期間發(fā)起，然后附加條目（AppendEntries）RPCs 由領(lǐng)導(dǎo)人發(fā)起，用來復(fù)制日志和提供一種心跳機(jī)制。為了在服務(wù)器之間傳輸快照增加了第三種 RPC。當(dāng)服務(wù)器沒有及時的收到 RPC 的響應(yīng)時，會進(jìn)行重試， 并且他們能夠并行的發(fā)起 RPCs 來獲得最佳的性能。
RPC有三種：

1. RequestVote RPC：候選人在選舉期間發(fā)起
2. AppendEntries RPC：領(lǐng)導(dǎo)人發(fā)起的一種心跳機(jī)制，復(fù)制日志也在該命令中完成
3. InstallSnapshot RPC: 領(lǐng)導(dǎo)者使用該RPC來發(fā)送快照給太落后的追隨者。

超時設(shè)置：

1. BroadcastTime : 領(lǐng)導(dǎo)者的心跳超時時間
2. Election Timeout: 追隨者設(shè)置的候選超時時間
3. MTBT :指的是單個服務(wù)器發(fā)生故障的間隔時間的平均數(shù)

BroadcastTime << ElectionTimeout << MTBF
兩個原則：

1. BroadcastTime應(yīng)該比ElectionTimeout小一個數(shù)量級，為的是使領(lǐng)導(dǎo)人能夠持續(xù)發(fā)送心跳信息（heartbeat）來阻止追隨者們開始選舉；
2. ElectionTimeout也要比MTBF小幾個數(shù)量級，為的是使得系統(tǒng)穩(wěn)定運(yùn)行。

一般BroadcastTime大約為0.5毫秒到20毫秒，ElectionTimeout一般在10ms到500ms之間。大多數(shù)服務(wù)器的MTBF都在幾個月甚至更長。

領(lǐng)導(dǎo)人選取

• 觸發(fā)條件：

  1. 一般情況下，追隨者接到領(lǐng)導(dǎo)者的心跳時，把ElectionTimeout清零，不會觸發(fā)；
  2. 領(lǐng)導(dǎo)者故障，追隨者的ElectionTimeout超時發(fā)生時，會變成候選者，觸發(fā)領(lǐng)導(dǎo)人選?。?/li>

• 候選操作過程：

追隨者自增當(dāng)前任期，轉(zhuǎn)換為Candidate，對自己投票，并發(fā)起RequestVote RPC，等待下面三種情形發(fā)生；

1. 獲得超過半數(shù)服務(wù)器的投票，贏得選舉，成為領(lǐng)導(dǎo)者；
2. 另一臺服務(wù)器贏得選舉，并接收到對應(yīng)的心跳，成為追隨者；
3. 選舉超時，沒有任何一臺服務(wù)器贏得選舉，自增當(dāng)前任期，重新發(fā)起選舉；

• 注意事項：

  1. 服務(wù)器在一個任期內(nèi)，最多能給一個候選人投票，采用先到先服務(wù)原則；
  2. 候選者等待投票時，可能會接收到來自其它聲明為領(lǐng)導(dǎo)人的的AppendEntries RPC。如果該領(lǐng)導(dǎo)人的任期（RPC中有）比當(dāng)前候選人的當(dāng)前任期要大，則候選人認(rèn)為該領(lǐng)導(dǎo)人合法，并轉(zhuǎn)換成追隨者；如果RPC中的任期小于候選人的當(dāng)前任期，則候選人拒絕此次RPC，繼續(xù)保持候選人狀態(tài)；
  3. 候選人既沒有贏得選舉也沒有輸?shù)暨x舉：如果許多追隨者在同一時刻都成為了候選人，選票會被分散，可能沒有候選人能獲得大多數(shù)的選票。當(dāng)這種情形發(fā)生時，每一個候選人都會超時，并且通過自增任期號和發(fā)起另一輪 RequestVote RPC 來開始新的選舉。然而，如果沒有其它手段來分配選票的話，這種情形可能會無限的重復(fù)下去。所以Raft使用的隨機(jī)的選舉超時時間（150~300ms之間），來避免這種情況發(fā)生。

• 問題探討：為什么這里沒有談收到其他候選者的RequestVote RPC請求？
  可能的解釋：

  1. 候選者已經(jīng)給自己投票了，一個候選者在一個任期只會給一個人投票，不會給其他人再投票了；
  2. 也有可能算法本身設(shè)定候選者就拒絕所有的其他服務(wù)器的請求。

日志復(fù)制

4.png

接受命令的過程：

1. 領(lǐng)導(dǎo)者接受客戶端請求；
2. 領(lǐng)導(dǎo)者把指令追加到日志；
3. 發(fā)送AppendEntries RPC到追隨者；
4. 領(lǐng)導(dǎo)者收到大多數(shù)追隨者的確認(rèn)后，領(lǐng)導(dǎo)者Commit該日志，把日志在狀態(tài)機(jī)中回放，并返回結(jié)果給客戶端；

提交過程：

1. 在下一個心跳階段，領(lǐng)導(dǎo)者再次發(fā)送AppendEntries RPC給追隨者，日志已經(jīng)commited；
2. 追隨者收到Commited日志后，將日志在狀態(tài)機(jī)中回放。

安全性

到目前為止描述的機(jī)制并不能充分的保證每一個狀態(tài)機(jī)會按照相同的順序執(zhí)行相同的指令，例如：一個跟隨者可能會進(jìn)入不可用狀態(tài)同時領(lǐng)導(dǎo)人已經(jīng)提交了若干的日志條目，然后這個跟隨者可能會被選舉為領(lǐng)導(dǎo)人并且覆蓋這些日志條目；因此，不同的狀態(tài)機(jī)可能會執(zhí)行不同的指令序列。

1. 領(lǐng)導(dǎo)者追加日志（Append-Only)

領(lǐng)導(dǎo)者永遠(yuǎn)不會覆蓋已經(jīng)存在的日志條目；
日志永遠(yuǎn)只有一個流向：從領(lǐng)導(dǎo)者到追隨者；

2. 選舉限制：投票阻止沒有全部日志條目的服務(wù)器贏得選舉

如果投票者的日志比候選人的新，拒絕投票請求；
這意味著要贏得選舉，候選者的日志至少和大多數(shù)服務(wù)器的日志一樣新，那么它一定包含全部的已經(jīng)提交的日志條目。

3. 永遠(yuǎn)不提交任期之前的日志條目（只提交任期內(nèi)的日志條目）

在Raft算法中，當(dāng)一個日志被安全的復(fù)制到絕大多數(shù)的機(jī)器上面，即AppendEntries RPC在絕大多數(shù)服務(wù)器正確返回了，那么這個日志就是被提交了，然后領(lǐng)導(dǎo)者會更新commit index。

5.png

如果允許提交任期之前的日志條目，那么在步驟c中，我們就會把之前任期為2的日志提交到其他服務(wù)器中去，并造成了大多數(shù)機(jī)器存在了日志為2的情況。所以造成了d中S5中任期為3的日志條目會覆蓋掉已經(jīng)提交的日志的情況。

Raft 從來不會通過計算復(fù)制的數(shù)目來提交之前人氣的日志條目。只有領(lǐng)導(dǎo)人當(dāng)前任期的日志條目才能通過計算數(shù)目來進(jìn)行提交。一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配原則（Log Matching Property），之前的日志條目也都會被間接的提交。

論文中的這段話比較難理解，更加直觀的說：由于Raft不會提交任期之前的日志條目，那么就不會從b過渡到c的情況，只能從b發(fā)生S5down機(jī)的情況下直接過渡到e，這樣就產(chǎn)生的更新的任期，這樣S5就沒有機(jī)會被選為領(lǐng)導(dǎo)者了。

4. 候選者和追隨者崩潰

候選者和追隨者崩潰的情況處理要簡單的多。如果這類角色崩潰了，那么后續(xù)發(fā)送給他們的 RequestVote和AppendEntries的所有RCP都會失敗，Raft算法中處理這類失敗就是簡單的無限重試的方式。
　　如果這些服務(wù)器重新可用，那么這些RPC就會成功返回。如果一個服務(wù)器完成了一個RPC，但是在響應(yīng)Leader前崩潰了，那么當(dāng)他再次可用的時候還會收到相同的RPC請求，此時接收服務(wù)器負(fù)責(zé)檢查，比如如果收到了已經(jīng)包含該條日志的RPC請求，可以直接忽略這個請求，確保對系統(tǒng)是無害的。

集群成員變更

集群成員的變更和成員的宕機(jī)與重啟不同，因為前者會修改成員個數(shù)進(jìn)而影響到領(lǐng)導(dǎo)者的選取和決議過程，因為在分布式系統(tǒng)這對于majority這個集群中成員大多數(shù)的概念是極為重要的。

簡單的做法是，運(yùn)維人員將系統(tǒng)臨時下線，修改配置，重新上線。但是這種做法存在兩個缺點：

1. 更改時集群不可用
2. 人為操作失誤風(fēng)險

直接從一種配置轉(zhuǎn)到新的配置是十分不安全的

如下圖所示：

6.png

因為各個機(jī)器可能在任何的時候進(jìn)行轉(zhuǎn)換。在這個例子中，集群配額從 3 臺機(jī)器變成了 5 臺。不幸的是，存在這樣的一個時間點，兩個不同的領(lǐng)導(dǎo)人在同一個任期里都可以被選舉成功。一個是通過舊的配置，一個通過新的配置。

兩階段方法保證安全性：

為了保證安全性，配置更改必須使用兩階段方法。在 Raft 中，集群先切換到一個過渡的配置，我們稱之為共同一致；一旦共同一致已經(jīng)被提交了，那么系統(tǒng)就切換到新的配置上。共同一致是老配置和新配置的結(jié)合。

共同一致允許獨立的服務(wù)器在不影響安全性的前提下，在不同的時間進(jìn)行配置轉(zhuǎn)換過程。此外，共同一致可以讓集群在配置轉(zhuǎn)換的過程人依然響應(yīng)服務(wù)器請求。

一個領(lǐng)導(dǎo)人接收到一個改變配置從 C-old 到 C-new 的請求，他會為了共同一致存儲配置（圖中的 C-old,new），以前面描述的日志條目和副本的形式。一旦一個服務(wù)器將新的配置日志條目增加到它的日志中，他就會用這個配置來做出未來所有的決定。領(lǐng)導(dǎo)人完全特性保證了只有擁有 C-old,new 日志條目的服務(wù)器才有可能被選舉為領(lǐng)導(dǎo)人。當(dāng)C-old,new日志條目被提交以后，領(lǐng)導(dǎo)人在使用相同的策略提交C-new，如下圖所示，C-old 和 C-new 沒有任何機(jī)會同時做出單方面的決定，這就保證了安全性。

7.png

一個配置切換的時間線。虛線表示已經(jīng)被創(chuàng)建但是還沒有被提交的條目，實線表示最后被提交的日志條目。領(lǐng)導(dǎo)人首先創(chuàng)建了 C-old,new 的配置條目在自己的日志中，并提交到 C-old,new 中（C-old,new 的大多數(shù)和 C-new 的大多數(shù)）。然后他創(chuàng)建 C-new 條目并提交到 C-new 中的大多數(shù)。這樣就不存在 C-new 和 C-old 可以同時做出決定的時間點。

日志壓縮

日志會隨著系統(tǒng)的不斷運(yùn)行會無限制的增長，這會給存儲帶來壓力，幾乎所有的分布式系統(tǒng)(Chubby、ZooKeeper)都采用快照的方式進(jìn)行日志壓縮，做完快照之后快照會在穩(wěn)定持久存儲中保存，而快照之前的日志和快照就可以丟棄掉。

Raft的具體做法如下圖所示：

8.png

與Raft其它操作Leader-Based不同，snapshot是由各個節(jié)點獨立生成的。除了日志壓縮這一個作用之外，snapshot還可以用于同步狀態(tài)：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成該過程，不再贅述。

Client交互

1. Client只向領(lǐng)導(dǎo)者發(fā)送請求；
2. Client開始會向追隨者發(fā)送請求，追隨者拒絕Client的請求，并重定向到領(lǐng)導(dǎo)者；
3. Client請求失敗，會超時重新發(fā)送請求；

Raft算法要求Client的請求線性化，防止請求被多次執(zhí)行。有兩個解決方案：

1. Raft算法提出要求每個請求有個唯一標(biāo)識；
2. Raft的請求保持冪等性；