《云計算技術系列叢書 云原生分布式存儲基石： etcd深入解析》—1.4Raft協議：為可理解性而生

1.4　Raft協議：為可理解性而生

測驗總分為60，Raft算法測驗的平均得分是25.7，Paxos算法的平均得分是20.8，Raft比Paxos平均高出4.9分。圖1-6展示了43個學生在Paxos和Raft測驗中的成績，對角線之上的點表示在Raft算法測驗中獲得更高分數的學生。

圖1-6　Paxos與Raft測驗對比

同時在測驗之后采訪參與學生，詢問他們認為哪個算法更容易解釋和實現。壓倒性的結果表明Raft算法更加容易解釋和實現。圖1-7展示了這個采訪結果。

圖1-7　Paxos與Raft算法實現難易程度調查

在圖1-7中，左側柱形圖表示的是哪個算法在工程上更容易實現的統計結果，右邊表示的是哪個算法更容易解釋的統計結果。

Raft算法主要使用兩種方法來提高可理解性。

（1）問題分解

盡可能地將問題分解成為若干個可解決的、更容易理解的小問題—這是眾所周知的簡化問題的方法論。例如，Raft算法把問題分解成了領袖選舉（leader election）、日志復制（log replication）、安全性（safety）和成員關系變化（membership changes）這幾個子問題。

領袖選舉：在一個領袖節點發生故障之后必須重新給出一個新的領袖節點。

日志復制：領袖節點從客戶端接收操作請求，然后將操作日志復制到集群中的其他服務器上，并且強制要求其他服務器的日志必須和自己的保持一致。

安全性：Raft關鍵的安全特性是下文提到的狀態機安全原則（State Machine Safety）—如果一個服務器已經將給定索引位置的日志條目應用到狀態機中，則所有其他服務器不會在該索引位置應用不同的條目。下文將會證明Raft是如何保證這條原則的。

成員關系變化：配置發生變化的時候，集群能夠繼續工作。

（2）減少狀態空間

Raft算法通過減少需要考慮的狀態數量來簡化狀態空間。這將使得整個系統更加一致并且能夠盡可能地消除不確定性。需要特別說明的是，日志條目之間不允許出現空洞，并且還要限制日志出現不一致的可能性。盡管在大多數情況下，Raft都在試圖消除不確定性以減少狀態空間。但在一種場景下（選舉），Raft會用隨機方法來簡化選舉過程中的狀態空間。

Raft算法與現有的一些Paxos協議的變種（主要是Oki和Liskov的Viewsta-mped Replication[6]）存在一些相似的地方，但是Raft還有幾點重要的創新。

強領導人。Raft使用一種比其他算法更強的領導形式。例如，日志條目只從領導人發向其他服務器。這樣就簡化了對日志復制的管理，提高了Raft的可理解性。

領袖選舉。Raft使用隨機定時器來選舉領導者。這種方式僅僅是在所有算法都需要實現的心跳機制上增加了一點變化，就使得沖突解決更加簡單和快速。

成員變化。Raft在調整集群成員關系時使用了新的一致性（joint consensus，聯合一致性）方法。使用這種方法，使得集群配置在發生改變時，集群依舊能夠正常工作。

下文將對Raft算法展開詳細的討論。

1.4.1　Raft一致性算法

Raft算法是基于復制狀態機模型推導的，所以在開始Raft算法的探秘之前，建議大家回顧一下1.2.3節有關復制狀態機的內容。下文將從Raft算法的4個子問題：領袖選舉、日志復制、安全性和成員關系變化出發，采取各個擊破的策略，直擊Raft算法的本質。不過，在此之前，先讓我們簡單了解下Raft算法的幾個基本概念。

當Paxos協議的讀者還在抱怨Lamport沒有給出一個形式化的、可實現的工程方法時，Diego在論文中就已經明確告訴他的讀者只要實現2個遠端過程調用，就能構建一個基于Raft協議的分布式系統。

Raft集群中的節點通過遠端過程調用（RPC）來進行通信，Raft算法的基本操作只需2種RPC即可完成。RequestVote RPC是在選舉過程中通過舊的Leader觸發的，AppendEntries RPC是領導人觸發的，目的是向其他節點復制日志條目和發送心跳（heartbeat）。下文還會介紹Raft算法的第3種RPC，用于領導人向其他節點傳輸快照（snapshot）。如果節點沒有及時收到RPC的響應，就會重試。而且，RPC可以并行地發出，以獲得最好的性能。

1. Raft算法的基本概念

一般情況下，分布式系統中存在如下兩種節點關系模型。

對稱。所有節點都是平等的，不存在主節點。客戶端可以與任意節點進行交互。

非對稱。基于選主模型，只有主節點擁有決策權。任意時刻有且僅有一個主節點，客戶端只與主節點進行交互。

基于簡化操作和效率等因素考慮，Raft算法采用的是非對稱節點關系模型。

在一個由Raft協議組織的集群中，一共包含如下3類角色。

Leader（領袖）

Candidate（候選人）

Follower（群眾）

聯系實際的民主社會，領袖由群眾投票選舉得出。剛開始時沒有領袖，民主社會的所有參與者都是群眾。首先開啟一輪大選，大選期間所有的群眾都能參與競選，即所有群眾都可以成為候選人。一旦某位候選人得到了半數以上群眾的選票，就出任那一屆的領袖，開始一個新的任期。領袖產生后，將由領袖昭告天下，結束選舉。于是，除領袖之外的所有候選人又都回到了群眾的身份并接受領袖的領導。

上文提到一個概念—“任期”，其在Raft算法中對應一個專門的術語—“Term”。

如圖1-8所示，Raft算法將時間劃分成為任意個不同長度的任期，任期是單調遞增的，用連續的數字（1，2，3……）表示。在Raft的世界里，每一個任期的開始都是一次領導人的選舉。正如上文所描述的那樣，一個或多個候選人會試圖成為領導人。如果一個候選人贏得了選舉，那么它就會在該任期的剩余時間內擔任領導人。在某些情況下，選票會被瓜分，導致沒有哪位候選人能夠得到超過半數的選票，這樣本次任期將以沒有選出領導人而結束。那么，系統就會自動進入下一個任期，開始一次新的選舉。Raft算法保證在給定的一個任期內最多只有一個領導人。某些Term會由于選舉失敗，存在沒有領導人的情況。

圖1-8　Raft算法任期示意圖

眾所周知，分布式環境下的“時間同步”是一個大難題，但是有時為了識別“過期信息”，時間信息又是必不可少的。于是，任期在Raft中起著邏輯時鐘的作用，同時也可用于在Raft節點中檢測過期信息—比如過期的領導人。每個Raft節點各自都在本地維護一個當前任期值，觸發這個數字變化（增加）主要有兩個場景：開始選舉和與其他節點交換信息。當節點之間進行通信時，會相互交換當前的任期號。如果一個節點（包括領導人）的當前任期號比其他節點的任期號小，則將自己本地的任期號自覺地更新為較大的任期號。如果一個候選人或者領導人意識到它的任期號過時了（比別人的小），那么它會立刻切換回群眾狀態；如果一個節點收到的請求所攜帶的任期號是過時的，那么該節點就會拒絕響應本次請求。

需要注意的是，由于分布式系統中節點之間無法做到在任意時刻完全同步，因此不同的Raft節點可能會在不同的時刻感知到任期的切換。甚至在出現網絡分區或節點異常的情況下，某個節點可能會感知不到一次選舉或者一個完整的任期。這也是Raft強制使用較新的Term更新舊的Term的原因。

好了，Raft協議的核心概念和術語就這么多—領袖、候選人、群眾和任期，而且這些術語與現實民主制度也非常匹配，因此也很好理解。下面就開始討論Raft算法的領導人選舉流程。

2.領導人選舉

Raft通過選舉一個權力至高無上的領導人，并采取賦予他管理復制日志重任的方式來維護節點間復制日志的一致性。領導人從客戶端接收日志條目，再把日志條目復制到其他服務器上，并且在保證安全性的前提下，告訴其他服務器將日志條目應用到它們的狀態機中。強領導人的存在大大簡化了復制日志的管理。例如，領導人可以決定新的日志條目需要放在日志文件的什么位置，而不需要和其他服務器商議，并且數據都是單向地從領導人流向其他服務器。當然，在這種方式下，領導人自身的日志正確性顯得尤為重要，下文的“4.安全性Q & A”一節會著重說明Raft使用怎樣的策略來保證日志的正確性。

Raft集群三類角色的有限狀態機圖如圖1-9所示，后面的具體選舉過程可以結合圖1-9來進行理解。

圖1-9　Raft集群三類角色切換示意圖

觀察圖1-9可以很容易地看出，有一個“times out”（超時）條件，這是觸發圖1-9有限狀態自動機發生狀態遷移的一個重要條件。在Raft的選舉中，有兩個概念非常重要：心跳和選舉定時器。每個Raft節點都有一個選舉定時器，所有的Raft節點最開始以Follower角色運行時，都會啟動這個選舉定時器。不過，每個節點的選舉定時器時長均不相等。

Leader在任期內必須定期向集群內的其他節點廣播心跳包，昭告自己的存在。Follower每次收到心跳包后就會主動將自己的選舉定時器清零重置（reset）。因此如果Follower選舉定時器超時，則意味著在Raft規定的一個選舉超時時間周期內，Leader的心跳包并沒有發給Follower（或者已經發送了但在網絡傳輸過程中發生了延遲或被丟棄了），于是Follower就假定Leader已經不存在或者發生了故障，于是會發起一次新的選舉。

對此，我們可以很形象地理解為每個Raft的Follower都有一顆不安分的“野心”，只是礙于Leader的心跳廣播不敢“造反”。而Follower從最后一次接收到Leader的心跳包算起，最長的“蟄伏”時間就是Raft協議為每個節點規定的選舉超時時間，超過這個時間，大家就都“蠢蠢欲動”了。

因此，要求Leader廣播心跳的周期必須要短于選舉定時器的超時時間，否則會頻繁地發生選舉，切換Leader。

如果一個Follower決定開始參加選舉，那么它會執行如下步驟。

1）將自己本地維護的當前任期號（current_term_id）加1。

2）將自己的狀態切換到候選人（Candidate），并為自己投票。也就是說每個候選人的第一張選票來自于他自己。

3）向其所在集群中的其他節點發送RequestVote RPC（RPC消息會攜帶“current_term_id”值），要求它們投票給自己。

從圖1-9也可以看出，一個候選人有三種狀態遷移的可能性。

1）得到大多數節點的選票（包括自己），成為Leader。

2）發現其他節點贏得了選舉，主動切換回Follower。

3）過了一段時間后，發現沒有人贏得選舉，重新發起一次選舉。

下文將逐一分析這些情形。

第一種場景：一個候選人如果在一個任期內收到了集群中大多數Follower的投票，就算贏得了選舉。在一個任期內，一個Raft節點最多只能為一個候選人投票，按照先到先得的原則，投給最早來拉選票的候選人（注意：下文的“安全性”針對投票添加了一個額外的限制）。“選舉安全性原則”使得在一個任期內最多有一個候選人能夠贏得選舉。一旦某個候選人贏得了選舉，它就會向其他節點發送心跳信息來建立自己的領導地位。

第二種場景：當一個候選人在等待其他人的選票時，它有可能會收到來自其他節點的，聲稱自己是領導人的心跳包（其實就是一個空內容的AppendEntries RPC）或AppendEntries RPC（下文會詳細說明）。此時，這個候選人會將信將疑地檢查包含在這位“領導人”RPC中的任期號：如果比自己本地維護的當前任期要大，則承認該領導人合法，并且主動將自己的狀態切換回Follower；反之，候選人則認為該“領導人”不合法，拒絕此次RPC，并且返回當前較新的那個任期號，以便讓“領導人”意識到自己的任期號已經過時了，該節點將繼續保持候選人狀態不變。

第三種場景：一個候選人既沒有贏得選舉也沒有輸掉選舉。如果多個Follower在同一時刻都成了候選人，那么選票可能會被多個候選人平分，這就使得沒有哪個候選人能夠獲得超過半數的選票。當這種情形發生時，顯然不能一直這樣“僵持下去”，于是Raft的每一個候選人又都設置了超時時間（類似于選舉超時時間，區別是選舉超時時間是針對Follower的），發生超時后，每個候選人自增任期號（Term++）并且發起新一輪的拉選票活動。然而，如果沒有其他手段來分配選票的話，選票均分的情況可能會無限循環下去（理論上存在這種可能性，還記得FLP不可能性定理嗎）。為了避免發生這種問題，Raft采用了一種非常簡單的方法—隨機重試。例如，設置一個區間（150～300ms），超時時間將從這個區間內隨機選擇。錯開發起競選的時間窗口，可以使得在大多數情況下只有一個節點會率先超時，該節點會在其他節點超時之前贏得選舉，并且向其他節點發送心跳信息。要知道，在每次選票打平時都會采用這種隨機的方式，因此連續發生選票被均分的概率非常小。1.4.5節將展示通過這種方法如何才能夠快速、有效地選出一個領導人。

以上“拉票”過程使用Raft算法預定義的RPC—RequestVote RPC就能描述。RequestVote RPC的發起/調用方是候選人，接收方是集群內所有的其他節點（包括Leader、Follower和Candidate）。RequestVote RPC有4個參數，2個返回值，具體如表1-1和表1-2所示。

RPC接收方需要實現的邏輯具體如下。

1）如果term < currentTerm，即RPC的第一個參數term的值小于接收方本地維護的term（currentTerm）值，則返回（currentTerm, false），以提醒調用方其term過時了，并且明確地告訴這位候選人這張選票不會投給他；否則執行步驟2。

2）如果之前沒把選票投給任何人（包括自己）或者已經把選票投給當前候選人了，并且候選人的日志和自己的日志一樣新，則返回（term, true），表示在這個任期，選票都投給這位候選人。如果之前已經把選票投給其他人了，那么很遺憾，這張選票還是不能投給他，這時就會返回（term, false）。

3.日志復制

一旦某個領導人贏得了選舉，那么它就會開始接收客戶端的請求。每一個客戶端請求都將被解析成一條需要復制狀態機執行的指令。領導人將把這條指令作為一條新的日志條目加入它的日志文件中，然后并行地向其他Raft節點發起AppendEntries RPC，要求其他節點復制這個日志條目。當這個日志條目被“安全”地復制之后（下文會詳細論述符合什么樣的條件才算安全），Leader會將這條日志應用（apply，即執行該指令）到它的狀態機中，并且向客戶端返回執行結果。如果Follower發生錯誤，運行緩慢沒有及時響應AppendEntries RPC，或者發生了網絡丟包的問題，那么領導人會無限地重試AppendEntries RPC（甚至在它響應了客戶端之后），直到所有的追隨者最終存儲了和Leader一樣的日志條目。

在圖1-10中，日志由有序編號的日志條目組成。每一個日志條目一般均包含三個屬性：整數索引（log index）、任期號（term）和指令（command）。每個條目所包含的整數索引即該條目在日志文件中的槽位。term是指其被領導人創建時所在的任期號，對應到圖1-10中就是每個方塊中的數字，用于檢測在不同的服務器上日志的不一致性問題。指令即用于被狀態機執行的外部命令（對應到圖1-10中就是x←3，y←1等）。如果某個日志條目能夠被狀態機安全執行，就認為是可以被提交（committed）了。

圖1-10　Raft協議追加日志示意圖

領導人決定什么時候將日志條目應用到狀態機是安全的，即可被提交的。Raft算法保證可被提交的日志條目是持久化的，并且最終是會被所有狀態機執行的。一旦領導人創建的條目已經被復制到半數以上的節點上了，那么這個條目就稱為可被提交的。例如，圖1-10中的7號條目在其中3個節點（一共是5個節點）上均有復制，所以7號條目是可被提交的；但條目8只在其中2個節點上有復制，因此8號條目不是可被提交的。

領導人日志中的所有條目都是可被提交的，包括之前的領導人創建的日志條目。這種提交方式是安全的—我們將會在下文詳細討論領導人更替之后這條規則應用的細節。領導人跟蹤記錄他所知道的被提交日志條目的最大索引值，并且這個索引值會包含在他向其他節點發送的AppendEntries RPC中，目的就是讓其他節點知道該索引值對應的日志條目已經被提交。由于領導人廣播的心跳包就是一個內容為空的AppendEntries RPC，因此其他節點也能通過領導人的心跳包獲悉某個日志條目的提交情況。一旦Follower得知某個日志條目已經被提交，那么它會將該條日志應用至本地的狀態機（按照日志順序）。

Raft算法設計了以下日志機制來保證不同節點上日志的一致性。

1）如果在不同的日志中兩個條目有著相同的索引和任期號，則它們所存儲的命令是相同的。

2）如果在不同的日志中兩個條目有著相同的索引和任期號，則它們之前的所有條目都是完全一樣的。

第一條特性的滿足條件在于，領導人在一個任期里在給定的一個日志索引位置上最多創建一條日志條目，同時該條目在日志文件中的槽位永遠也不會改變。

第二條特性的滿足條件在于，AppendEntries RPC有一個簡單的一致性檢查。領導人在發送一個AppendEntries RPC消息試圖向其他節點追加新的日志條目時，會把這些新日志條目之前一個槽位的日志條目的任期號和索引位置包含在消息體中。如果Follower在它的日志文件中沒有找到相同的任期號和索引的日志，它就會拒絕該AppendEntries RPC，即拒絕在自己的狀態機中追加新日志條目。

用歸納法證明：初始化時空日志文件一定是滿足日志匹配原則的，一致性檢查保證了向日志文件追加新日志條目時的日志匹配原則。因此，只要某個Follower成功返回AppendEntries RPC，那么領導人就能放心地認為他的日志與該Follower的已經保持一致了。

當一個新的Leader被選舉出來時，它的日志與其他的Follower的日志可能是不一樣的。這時就需要一個機制來保證日志是一致的。產生一個新Leader時，集群狀態可能如圖1-11所示。

圖1-11　新Leader產生時集群可能的一個狀態圖

在圖1-11所示的例子中，一個格子代表一個日志條目，格子中的數字是它對應的任期號。假設最上面的那個是領導人，a～f是可能出現的Follower的日志，那么a～f 所代表的場景分別如下。

a和b表示Follower丟失一些日志條目的場景。

c和d表示Follower可能多出來一些未提交的條目的場景。

e和f表示上述兩種情況都有的場景。

丟失的或者多出來的條目可能會持續多個任期。舉個例子，場景f會在如下情況下發生：如果一臺服務器在任期2時是領導人，并且其向他自己的日志文件中追加了一些日志條目，然而在將這些日志條目提交之前系統出現了故障。但是他很快又重啟了，選舉成功繼續成為任期3的領導人，而且又向他自己的日志文件中追加了一些日志條目。但是很不幸的是，在任期2和任期3中創建的日志條目在被提交之前又出現了故障，并且在后面幾個任期內也一直處于故障狀態。

一般情況下，Leader和Follower的日志都是保持一致的，因此Append-Entries RPC的一致性檢查通常不會失敗。然而，如果領袖節點在故障之前沒有向其他節點完全復制日志文件中的所有條目，則會導致日志不一致的問題。在Raft算法中，Leader通過強制Follower復制它的日志來處理日志不一致的問題。這就意味著，Follower上與Leader的沖突日志會被領導者的日志強制覆寫。這在添加了一個額外的限制之后其實是安全的，下文會詳細說明其中的原因。

為了讓Follower的日志同自己的保持一致，Leader需要找到第一個Follower與它的日志條目不一致的位置，然后讓Follower連續刪除該位置之后（包括該位置）所有的日志條目，并且將自己在該位置（包括該位置）之后的日志條目發送給Follower。

那么，Leader是如何精準地找到每個Follower與其日志條目不一致的那個槽位的呢？這些操作都會在AppendEntries RPC進行一致性檢查時完成。Leader為每一個Follower維護了一個nextIndex，它表示領導人將要發送給該追隨者的下一條日志條目的索引。當一個Leader贏得選舉時，它會假設每個Follower上的日志都與自己的保持一致，于是先將nextIndex初始化為它最新的日志條目索引數+1。在圖1-11所示的例子中，由于Leader最新的日志條目index為10，所以nextIndex的初始值是11。

當Leader向Follower發送AppendEntries RPC時，它攜帶了（term_id, next-Index-1）二元組信息，term_id即nextIndex-1這個槽位的日志條目的term。Follower接收到AppendEntries RPC消息后，會進行一致性檢查，即搜索自己的日志文件中是否存在這樣的日志條目，如果不存在，就向Leader返回AppendEntries RPC失敗。如果返回失敗信息，就意味著Follower發現自己的日志與領導人的不一致。在失敗之后，領導人會將nextIndex遞減（nextIndex--），然后重試AppendEntries RPC，直到AppendEntries RPC返回成功為止。這才表明在nextIndex位置的日志條目中領導人與追隨者的保持一致。這時，Follower上nextIndex位置之前的日志條目將全部保留，在此之后（與Leader有沖突）的日志條目將被Follower全部刪除，并且從該位置起追加Leader上在nextIndex位置之后的所有日志條目。因此，一旦AppendEntries RPC返回成功，Leader和Follower的日志就可以保持一致了。

以上即Raft日志的一致性檢查的全過程，下面將以圖1-11中的Leader和b節點為例，舉例說明日志一致性檢查Leader和Follower之間的交互過程。

首先，Leader的nextIndex的初始值為11，Leader向b發送AppendEntries RPC(6,10)。然而，b在自己日志文件的10號位置沒有找到term為6的日志記錄（因為b根本就沒有10號日志項），于是b向Leader返回了一個拒絕消息。接著，Leader將nextIndex減1，變成10，然后繼續向b發送AppendEntries RPC(6,9)，b在自己日志文件的9號位置同樣沒有找到term為6的日志記錄。(6,8)，(5,7)，(5,6)，(4,5)這樣依次循環下去都沒有找到相應的日志記錄，直到發送了(4,4)，b才在自己日志文件的第4號位置找到了term為4的日志記錄，于是接受了Leader的AppendEntries RPC請求，并將自己的日志文件中從5號位置開始的日志記錄全部刪除。隨后，Leader就從5號位置開始把余下的所有日志條目一次性推送給b（5~10）。

如果需要的話，在Raft算法的實現上還可以優化AppendEntries RPC失敗的次數。例如，當Follower拒絕了一個AppendEntries RPC時，Follower可以在自己本地的日志文件中找到該任期號內所有日志條目索引（index）值最小的那個，然后反饋給Leader。于是，領導人就可以跳躍式遞減nextIndex，跨過那個任期內所有的沖突條目。通過這種方式，一個沖突的任期只需要一次Append-Entries RPC檢查，而無須為每個沖突條目都做一次AppendEntries RPC檢查。

Raft算法的日志復制機制，使得Leader和Follower只需要調用和響應AppendEntries RPC即可讓集群內節點的各復制狀態機的日志逐漸地趨于一致，而無須再采取額外的措施。一個領導人從來不會刪除自己的日志（包括前任領導人創建的日志），也不會被別人覆蓋日志。

Raft算法的日志復制機制表明：只要集群中的大部分節點是正常的，那么Raft算法就能接受客戶端復制日志的請求，并將其復制到各節點上且應用（Apply）到各節點的復制狀態機上。通常情況下，一次AppendEntries RPC就能完成一條新的日志條目在集群內的大多數節點上的復制。而且Raft只要求日志條目在大多數節點上完成復制就算提交成功，因此速度較慢的Follower并不會影響整體的日志復制性能。

以下步驟總結了一次正常的Raft日志的復制流程。

1）客戶端向Leader發送寫請求。

2）Leader將寫請求解析成操作指令追加到本地日志文件中。

3）Leader為每個Follower廣播AppendEntries RPC。

4）Follower通過一致性檢查，選擇從哪個位置開始追加Leader的日志條目。

5）一旦日志項提交成功，Leader就將該日志條目對應的指令應用（apply）到本地狀態機，并向客戶端返回操作結果。

6）Leader后續通過AppendEntries RPC將已經成功（在大多數節點上）提交的日志項告知Follower。

7）Follower收到提交的日志項之后，將其應用至本地狀態機。

從上面的步驟可以看出，針對Raft日志條目有兩個操作，提交（commit）和應用（apply），應用必須發生在提交之后，即某個日志條目只有被提交之后才能被應用到本地狀態機上。

RPC接收者需要實現如下操作步驟。

1）如果term < currentTerm，即領導人的任期號小于Follower本地維護的當前任期號，則返回(currentTerm, false)；否則繼續步驟2）。

2）如果Follower在prevLogIndex位置的日志的任期號與prevLogTerm不匹配，則返回(term, false)；否則繼續步驟3）。

3）Follower進行日志一致性檢查。

4）添加任何在已有的日志中不存在的條目，刪除多余的條目。

5）如果leaderCommit > commitIndex，則將commitIndex（Follower自己維護的本地已提交的日志條目索引值）更新為min{leaderCommit, Follower本地最新日志條目索引}。即信任Leader的數據，樂觀地將本地已提交日志的索引值“躍進”到領導人為該Follower跟蹤記錄的那個值（除非leaderCommit比本地最新的日志條目索引值還要大）。這種場景通常發生在Follower剛從故障中恢復過來的場景。

4.安全性Q&A

Raft算法是強領導人模型，一旦Follower與Leader發生了沖突，就將無條件服從Leader。因此，Leader選舉是Raft算法中非常重要的一環，如果選舉出來的Leader其自身的日志就是不正確的，那么將會直接影響到Raft算法正確穩定的運行。

之前的章節討論了Raft算法是如何進行領導選舉和日志復制的。然而，到目前為止這個機制還不能保證每一個狀態機都能夠按照相同的順序執行同樣的指令。例如，當領導人正在復制日志條目時一個Follower發生了故障，且故障發生之前沒有復制領導人的日志，之后該Follower重啟并且當選為領導人，那么它在產生了一些新的日志條目后，會用自己的日志覆蓋掉其他節點的日志。這就會導致不同的狀態機可能執行不同的指令序列。

下文將介紹如何在領導人選舉部分加入一個限制規則來保證—任何的領導人都擁有之前任期提交的全部日志條目。有了這一限制，就不會發生上面例子所描述的情形了。

Q：怎樣才能具有成為領導人的資格？

A：在所有以領導人選舉為基礎的一致性算法中，領導人最終必須要存儲全部已經提交的日志條目。在一些一致性算法中，例如，Viewstamped Replication中，即使一開始沒有包含全部已提交的條目也可以當選為領導人。這些算法都包含一些另外的機制來保證找到丟失的條目并將它們傳輸給新的領導人，這個過程要么在選舉過程中完成，要么在選舉之后立即開始。毫無疑問的是，這種方式顯著增加了算法的復雜性。

Raft算法使用的是一種更簡單的方式來保證新當選的領導人，之前任期已提交的所有日志條目都已經出現在了上面，而不需要將這些條目傳送給***人。這種方式隱含了以下兩點內容。

沒有包含所有已提交日志條目的節點成為不了領導人。

日志條目只有一個流向：從Leader流向Follower。領導人永遠不會覆蓋已經存在的日志條目。

Raft算法使用投票的方式來阻止那些沒有包含所有已提交日志條目的節點贏得選舉。一個候選人為了贏得選舉必須要與集群中的大多數節點進行通信，這就意味著每一條已經提交的日志條目都會出現在至少其中一個與之通信的節點上（可以用反證法證明）。如果候選人的日志比集群內的大多數節點上的日志更加新（或至少一樣新），那么它一定包含所有已經提交的日志條目。因此，RequestVote RPC的接收方有一個檢查：如果他自己的日志比RPC調用方（候選人）的日志更加新，就會拒絕候選人的投票請求。

那么，如何比較兩份日志哪個更加新呢？比較的依據是日志文件中最后一個條目的索引和任期號：如果兩個日志條目的任期號不同，則任期號大的更加新；如果任期號相同，則索引值更大（即日志文件條目更多）的日志更加新。

Q：如何判斷日志已經提交？

A：上文在“選舉機制”中已經談到過，領導人當前任期的某條日志條目只要存儲在大多數節點上，就認為該日志記錄已經被提交（committed）了。如果領導人在提交某個日志條目之前崩潰了，那么未來后繼的領導人會讓其他節點繼續復制這條日志條目。

然而，一個領導人不能因為由之前領導人創建（即之前任期）的某條日志存儲在大多數節點上了，就篤定該日志條目已經被提交了。圖1-12中的時序a～d展示了這種情況，一條已經被存儲到大多數節點上的日志條目，也依然有可能會被未來的領導人覆蓋掉。

圖1-12　Raft算法某一時刻日志狀態圖

時刻a，S1是任期2的領導人并且向部分節點（S1和S2）復制了2號位置的日志條目，然后宕機。

時刻b，S5獲得了S3、S4（S5的日志與S3和S4的一樣新，最新的日志的任期號都是1）和自己的選票贏得了選舉，成了3號任期的領導人，并且在2號位置上寫入了一條任期號為3的日志條目。在新日志條目復制到其他節點之前，S5宕機了。

時刻c，S1重啟，并且通過S2、S3、S4和自己的選票贏得了選舉，成了4號任期的領導人，并且繼續向S3復制2號位置的日志。此時，任期2的日志條目已經在大多數節點上完成了復制。

時刻d，S1發生故障，S5通過S2、S3、S4的選票再次成為領導人（因為S5最后一條日志條目的任期號是3，比S2、S3、S4中任意一個節點上的日志都更加新），任期號為5。然后S5用自己的本地日志覆寫了其他節點上的日志。

上面這個例子生動地說明了，即使日志條目被半數以上的節點寫盤（復制）了，也并不代表它已經被提交（commited）到Raft集群了—因為一旦某條日志被提交，那么它將永遠沒法被刪除或修改。這個例子同時也說明了，領導人無法單純地依靠之前任期的日志條目信息判斷它的提交狀態。

因此，針對以上場景，Raft算法對日志提交條件增加了一個額外的限制：要求Leader在當前任期至少有一條日志被提交，即被超過半數的節點寫盤。

正如圖1-12中e描述的那樣，S1作為Leader，在崩潰之前，將3號位置的日志（任期號為4）在大多數節點上復制了一條日志條目（指的是條目3，term? ? ? ? ?4），那么即使這時S1宕機了，S5也不可能贏得選舉—因為S2和S3的最新日志條目的任期號為4，比S5的3要大，S3無法獲得超過半數的選票。S5無法贏得選舉，這就意味著2號位置的日志條目不會被覆寫。

將上面的描述歸納一下，可以總結為如下幾點。

1）只要一個日志條目被存在了大多數的服務器上，領導人就知道當前任期可以提交該條目了。

2）如果領導人在提交日志之前就崩潰了，之后的領導人會試著繼續完成對日志的復制。但是，新任領導人無法斷定存儲在大多數服務器上的日志條目一定在之前的任期中被提交了（即使日志保存在大部分的服務器上，也有可能沒來得及提交）。

TCP/IP 專屬分布式存儲服務 分布式

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。