引言：尋求易理解的共識(shí)算法

共識(shí)算法是構(gòu)建可靠的大規(guī)模分布式軟件系統(tǒng)的關(guān)鍵組件。它們?cè)试S多臺(tái)機(jī)器作為一個(gè)高內(nèi)聚的整體協(xié)同工作，即使部分成員發(fā)生故障也能繼續(xù)提供服務(wù)。在過去的十年中，Paxos 算法一直是共識(shí)領(lǐng)域討論的核心，大多數(shù)共識(shí)實(shí)現(xiàn)都基于或受其影響。然而，Paxos 因其難以理解而臭名昭著，并且其架構(gòu)需要復(fù)雜的修改才能應(yīng)用于實(shí)際系統(tǒng)。

正是由于 Paxos 的這些挑戰(zhàn)，斯坦福大學(xué)的 Diego Ongaro 和 John Ousterhout 開始著手設(shè)計(jì)一種新的共識(shí)算法——Raft。Raft 的首要設(shè)計(jì)目標(biāo)是 可理解性 (understandability)：不僅算法要能工作，更重要的是能讓人清楚地理解它為什么能工作。為了實(shí)現(xiàn)這一目標(biāo)，Raft 采用了 問題分解 (problem decomposition) 和 狀態(tài)空間簡化 (state space reduction) 等方法。用戶研究也表明，學(xué)生學(xué)習(xí) Raft 比學(xué)習(xí) Paxos 更容易。

Raft 具備幾個(gè)新穎特性：

• 強(qiáng)領(lǐng)導(dǎo)者 (Strong leader) ：Raft 采用比其他共識(shí)算法更強(qiáng)的領(lǐng)導(dǎo)者模型。例如，日志條目只從領(lǐng)導(dǎo)者單向流向其他服務(wù)器，這簡化了復(fù)制日志的管理。
• 領(lǐng)導(dǎo)者選舉 (Leader election) ：Raft 使用隨機(jī)化定時(shí)器來選舉領(lǐng)導(dǎo)者。這種方式在任何共識(shí)算法都必需的心跳機(jī)制上僅增加了少量開銷，卻能簡單快速地解決沖突。
• 成員變更 (Membership changes) ：Raft 采用一種新的聯(lián)合共識(shí) (joint consensus) 方法進(jìn)行集群成員變更，通過重疊多數(shù) (overlapping majorities) 來保證安全性。

Raft 被認(rèn)為在教學(xué)和實(shí)現(xiàn)兩方面均優(yōu)于 Paxos，它更簡單、描述更完整、已有多種開源實(shí)現(xiàn)并被多家公司采用，同時(shí)其安全性和效率也得到了保證。

復(fù)制狀態(tài)機(jī)

共識(shí)算法通常應(yīng)用于 復(fù)制狀態(tài)機(jī) (replicated state machines, RSMs) 的場(chǎng)景。在 RSM 模型中，一組服務(wù)器上的狀態(tài)機(jī)計(jì)算相同狀態(tài)的相同副本，并且即使某些服務(wù)器宕機(jī)也能繼續(xù)運(yùn)行。例如，GFS、HDFS 和 RAMCloud 等系統(tǒng)使用獨(dú)立的復(fù)制狀態(tài)機(jī)來管理領(lǐng)導(dǎo)者選舉和存儲(chǔ)配置信息。Chubby 和 ZooKeeper 也是復(fù)制狀態(tài)機(jī)的著名例子。

復(fù)制狀態(tài)機(jī)通常通過 復(fù)制日志 (replicated log) 實(shí)現(xiàn)，如圖 1 (論文中的 Figure 1) 所示。每臺(tái)服務(wù)器存儲(chǔ)一個(gè)包含一系列命令的日志，其狀態(tài)機(jī)按順序執(zhí)行這些命令。由于所有日志包含相同順序的相同命令，且狀態(tài)機(jī)是確定性的，因此它們會(huì)計(jì)算出相同的狀態(tài)和輸出序列。

圖片

共識(shí)算法的核心任務(wù)是保持復(fù)制日志的一致性。服務(wù)器上的共識(shí)模塊接收來自客戶端的命令并將其添加到本地日志，然后與其他服務(wù)器的共識(shí)模塊通信，以確保即使發(fā)生故障，每個(gè)日志最終都包含相同順序的相同請(qǐng)求。一旦命令被正確復(fù)制，每個(gè)服務(wù)器的狀態(tài)機(jī)就按日志順序處理它們，并將輸出返回給客戶端。

一個(gè)實(shí)用的共識(shí)算法通常具備以下特性：

• 在所有非拜占庭條件下確保 安全性 (Safety)，即永不返回錯(cuò)誤結(jié)果。
• 只要集群中多數(shù)服務(wù)器正常運(yùn)行且能夠相互通信及與客戶端通信，就能保證 可用性 (Availability)。一個(gè)典型的五服務(wù)器集群可以容忍任意兩臺(tái)服務(wù)器的故障。
• 不依賴時(shí)序來保證日志的一致性；錯(cuò)誤的時(shí)鐘或極端的消息延遲最多導(dǎo)致可用性問題。
• 通常情況下，一條命令只需一輪 RPC 從領(lǐng)導(dǎo)者到多數(shù)服務(wù)器即可完成；少數(shù)慢速服務(wù)器不應(yīng)影響整體系統(tǒng)性能。

Paxos 的問題所在

盡管 Paxos 在共識(shí)領(lǐng)域占據(jù)主導(dǎo)地位，但它存在兩個(gè)顯著缺陷。

第一個(gè)缺陷是 Paxos 異常難以理解。其完整解釋晦澀難懂，即使是簡化版本也頗具挑戰(zhàn)性。這種晦澀性可能源于其以 單決策 Paxos (single-decree Paxos) 為基礎(chǔ)的構(gòu)建方式。單決策 Paxos 本身就密集且微妙，其分為兩個(gè)階段，缺乏簡單直觀的解釋且難以獨(dú)立理解。

第二個(gè)缺陷是 Paxos 沒有為構(gòu)建實(shí)際系統(tǒng)提供良好的基礎(chǔ)。沒有一個(gè)被廣泛認(rèn)可的 多決策 Paxos (multi-Paxos) 算法；Lamport 的描述主要集中在單決策上，對(duì)多決策僅給出了大致思路，缺乏許多細(xì)節(jié)。此外，Paxos 的對(duì)等 (peer-to-peer) 核心架構(gòu)不適合需要做出一系列決策的實(shí)際系統(tǒng)；先選舉一個(gè)領(lǐng)導(dǎo)者，再由領(lǐng)導(dǎo)者協(xié)調(diào)決策會(huì)更簡單高效。因此，實(shí)際系統(tǒng)往往與 Paxos 的原始描述相去甚遠(yuǎn)，開發(fā)者需要花費(fèi)大量時(shí)間和精力進(jìn)行修改和擴(kuò)展，這既耗時(shí)又容易出錯(cuò)。正如 Chubby 的實(shí)現(xiàn)者所言：“Paxos 算法的描述與真實(shí)世界系統(tǒng)的需求之間存在巨大鴻溝……最終的系統(tǒng)將基于一個(gè)未經(jīng)證明的協(xié)議?！?/span>

為可理解性而設(shè)計(jì)

Raft 的設(shè)計(jì)將可理解性置于首位。設(shè)計(jì)者不僅希望算法能夠正確、高效地工作，還希望廣大的開發(fā)者和學(xué)生能夠輕松理解它，并建立起對(duì)算法行為的直觀認(rèn)識(shí)。

在設(shè)計(jì)過程中，Raft 采用了兩種主要技術(shù)來增強(qiáng)可理解性：

1. 問題分解 (Problem decomposition) ：將復(fù)雜問題分解為若干個(gè)相對(duì)獨(dú)立的子問題，這些子問題可以被獨(dú)立解決、解釋和理解。Raft 將共識(shí)問題分解為領(lǐng)導(dǎo)者選舉、日志復(fù)制、安全性和成員變更幾個(gè)部分。
2. 狀態(tài)空間簡化 (State space reduction) ：通過減少需要考慮的狀態(tài)數(shù)量，使系統(tǒng)行為更具一致性，并盡可能消除不確定性。例如，Raft 不允許日志中存在空洞，并限制了日志之間可能出現(xiàn)不一致的方式。值得一提的是，Raft 在領(lǐng)導(dǎo)者選舉中引入的隨機(jī)化，雖然是一種不確定性，但它通過以相似方式處理所有可能選擇，反而簡化了狀態(tài)空間，提升了理解性。

Raft 共識(shí)算法

圖片

Raft 算法用于管理一個(gè)復(fù)制日志，其整體機(jī)制可以參考論文中的圖 2 (Figure 2) 進(jìn)行概覽，關(guān)鍵屬性總結(jié)在圖 3 (Figure 3)。Raft 通過選舉一位唯一的 領(lǐng)導(dǎo)者 (leader)，并賦予其管理復(fù)制日志的全部職責(zé)來實(shí)現(xiàn)共識(shí)。領(lǐng)導(dǎo)者從客戶端接收日志條目，將其復(fù)制到其他服務(wù)器上，并告知服務(wù)器何時(shí)可以安全地將日志條目應(yīng)用于它們的狀態(tài)機(jī)。這種領(lǐng)導(dǎo)者模型簡化了復(fù)制日志的管理。如果當(dāng)前領(lǐng)導(dǎo)者失效，則會(huì)選舉出新的領(lǐng)導(dǎo)者。

圖片

Raft 將共識(shí)問題分解為三個(gè)相對(duì)獨(dú)立的子問題：

• 領(lǐng)導(dǎo)者選舉 (Leader election) ：當(dāng)現(xiàn)有領(lǐng)導(dǎo)者失效時(shí)，必須選舉出新的領(lǐng)導(dǎo)者 (5.2節(jié))。
• 日志復(fù)制 (Log replication) ：領(lǐng)導(dǎo)者必須接受來自客戶端的日志條目，并在集群中進(jìn)行復(fù)制，強(qiáng)制其他服務(wù)器的日志與自己保持一致 (5.3節(jié))。
• 安全性 (Safety) ：Raft 的關(guān)鍵安全屬性是狀態(tài)機(jī)安全屬性 (State Machine Safety Property)：如果任一服務(wù)器已將特定日志條目應(yīng)用于其狀態(tài)機(jī)，則其他服務(wù)器不能對(duì)同一日志索引應(yīng)用不同的命令 (5.4節(jié))。

Raft 基礎(chǔ)

一個(gè) Raft 集群包含若干服務(wù)器，通常是5臺(tái)，這樣可以容忍兩臺(tái)服務(wù)器的故障。在任何時(shí)刻，每臺(tái)服務(wù)器都處于以下三種狀態(tài)之一：領(lǐng)導(dǎo)者 (leader)、跟隨者 (follower) 或 候選人 (candidate)。正常情況下，集群中只有一個(gè)領(lǐng)導(dǎo)者，其余所有服務(wù)器都是跟隨者。跟隨者是被動(dòng)的，它們不主動(dòng)發(fā)起請(qǐng)求，僅響應(yīng)來自領(lǐng)導(dǎo)者和候選人的請(qǐng)求。所有客戶端請(qǐng)求都由領(lǐng)導(dǎo)者處理；如果客戶端聯(lián)系到跟隨者，跟隨者會(huì)將其重定向到領(lǐng)導(dǎo)者。候選人狀態(tài)則用于選舉新的領(lǐng)導(dǎo)者。

Raft 將時(shí)間劃分為連續(xù)的 任期 (terms)，每個(gè)任期用一個(gè)連續(xù)整數(shù)編號(hào)。每個(gè)任期從一次選舉開始，一個(gè)或多個(gè)候選人嘗試成為領(lǐng)導(dǎo)者。如果一個(gè)候選人贏得選舉，它將在該任期的剩余時(shí)間內(nèi)擔(dān)任領(lǐng)導(dǎo)者。有時(shí)選舉可能以選票分裂告終，導(dǎo)致該任期沒有領(lǐng)導(dǎo)者，此時(shí)會(huì)很快開始一個(gè)新的任期（和新一輪選舉）。Raft 保證在一個(gè)給定的任期中最多只有一個(gè)領(lǐng)導(dǎo)者。

任期在 Raft 中充當(dāng) 邏輯時(shí)鐘 (logical clock)，允許服務(wù)器檢測(cè)過時(shí)的信息（如陳舊的領(lǐng)導(dǎo)者）。每臺(tái)服務(wù)器都存儲(chǔ)一個(gè)單調(diào)遞增的當(dāng)前任期號(hào) (currentTerm)。服務(wù)器通信時(shí)會(huì)交換 currentTerm；如果一臺(tái)服務(wù)器的 currentTerm 小于另一臺(tái)，它會(huì)將自己的 currentTerm 更新為較大的值。如果候選人或領(lǐng)導(dǎo)者發(fā)現(xiàn)自己的任期已過時(shí)，它會(huì)立即轉(zhuǎn)變?yōu)楦S者狀態(tài)。如果服務(wù)器收到一個(gè)帶有陳舊任期號(hào)的請(qǐng)求，它會(huì)拒絕該請(qǐng)求。

Raft 服務(wù)器之間通過 遠(yuǎn)程過程調(diào)用 (RPCs) 進(jìn)行通信?；镜墓沧R(shí)算法只需要兩種類型的 RPC：

• RequestVote RPC：由候選人在選舉期間發(fā)起 (5.2節(jié))。
• AppendEntries RPC：由領(lǐng)導(dǎo)者發(fā)起，用于復(fù)制日志條目和作為心跳 (5.3節(jié))。

領(lǐng)導(dǎo)者選舉

Raft 使用心跳機(jī)制來觸發(fā)領(lǐng)導(dǎo)者選舉。服務(wù)器啟動(dòng)時(shí)是跟隨者狀態(tài)。只要能從領(lǐng)導(dǎo)者或候選人那里收到有效的 RPC，服務(wù)器就保持跟隨者狀態(tài)。領(lǐng)導(dǎo)者會(huì)向所有跟隨者發(fā)送周期性的心跳（不攜帶日志條目的 AppendEntries RPC）以維持其權(quán)威。如果一個(gè)跟隨者在一段時(shí)間（稱為 選舉超時(shí) (election timeout)）內(nèi)沒有收到任何通信，它就假定當(dāng)前沒有可行的領(lǐng)導(dǎo)者，并開始一次選舉以選出新的領(lǐng)導(dǎo)者。

開始選舉時(shí)，跟隨者會(huì)：

1. 增加其本地的 currentTerm。
2. 轉(zhuǎn)變?yōu)楹蜻x人狀態(tài)。
3. 為自己投票。
4. 并行地向集群中的其他所有服務(wù)器發(fā)送 RequestVote RPC。

候選人會(huì)保持此狀態(tài)，直到發(fā)生以下三種情況之一：(a) 它贏得選舉；(b) 另一臺(tái)服務(wù)器確立自己為領(lǐng)導(dǎo)者；(c) 一段時(shí)間過去后沒有贏家。

• 贏得選舉 ：候選人從整個(gè)集群中超過半數(shù)的服務(wù)器那里獲得了針對(duì)同一任期的選票。每臺(tái)服務(wù)器在給定的任期內(nèi)最多只能為一名候選人投票（基于先到先得的原則，并受5.4節(jié)中額外限制的約束）。多數(shù)決規(guī)則確保了在一個(gè)特定任期內(nèi)最多只能有一個(gè)候選人贏得選舉（即選舉安全屬性）。一旦候選人獲勝，它就成為領(lǐng)導(dǎo)者，并向所有其他服務(wù)器發(fā)送心跳消息以建立其權(quán)威并阻止新的選舉。
• 發(fā)現(xiàn)其他領(lǐng)導(dǎo)者 ：在等待選票期間，候選人可能會(huì)收到來自另一臺(tái)聲稱是領(lǐng)導(dǎo)者的服務(wù)器的 AppendEntries RPC。如果該領(lǐng)導(dǎo)者的任期（包含在其 RPC 中）大于或等于候選人的當(dāng)前任期，則候選人承認(rèn)該領(lǐng)導(dǎo)者的合法性并轉(zhuǎn)換回跟隨者狀態(tài)。如果 RPC 中的任期小于候選人的當(dāng)前任期，則候選人拒絕該 RPC 并繼續(xù)保持候選人狀態(tài)。
• 沒有贏家（選票分裂） ：如果許多跟隨者同時(shí)成為候選人，選票可能會(huì)被瓜分，導(dǎo)致沒有候選人獲得多數(shù)票。發(fā)生這種情況時(shí)，每個(gè)候選人都會(huì)超時(shí)，并通過增加其任期號(hào)和發(fā)起另一輪 RequestVote RPC 來開始新的選舉。

為了確保選票分裂很少發(fā)生并且能夠迅速解決，Raft 使用了 隨機(jī)化選舉超時(shí) (randomized election timeouts)。選舉超時(shí)時(shí)間從一個(gè)固定的區(qū)間內(nèi)隨機(jī)選擇（例如 150-300 毫秒）。這使得服務(wù)器的超時(shí)時(shí)間分散開，在大多數(shù)情況下，只有一個(gè)服務(wù)器會(huì)首先超時(shí)并發(fā)起選舉；它贏得選舉并在其他服務(wù)器超時(shí)之前發(fā)送心跳。處理選票分裂也使用相同的機(jī)制：每個(gè)候選人在開始選舉時(shí)重新啟動(dòng)其隨機(jī)化選舉超時(shí)，并等待該超時(shí)結(jié)束后才開始下一次選舉，這減少了在新選舉中再次發(fā)生選票分裂的可能性。

日志復(fù)制

一旦選出領(lǐng)導(dǎo)者，它就開始處理客戶端請(qǐng)求。每個(gè)客戶端請(qǐng)求都包含一個(gè)由復(fù)制狀態(tài)機(jī)執(zhí)行的命令。領(lǐng)導(dǎo)者將該命令作為新條目追加到其日志中，然后并行地向其他所有服務(wù)器發(fā)送 AppendEntries RPC 以復(fù)制該條目。當(dāng)條目被安全復(fù)制后（如下所述），領(lǐng)導(dǎo)者將該條目應(yīng)用于其狀態(tài)機(jī)，并將執(zhí)行結(jié)果返回給客戶端。如果跟隨者崩潰、運(yùn)行緩慢或網(wǎng)絡(luò)丟包，領(lǐng)導(dǎo)者會(huì)無限期地重試 AppendEntries RPC（即使在響應(yīng)客戶端之后），直到所有跟隨者最終都存儲(chǔ)了所有日志條目。

日志條目 (log entries) 包含狀態(tài)機(jī)命令以及領(lǐng)導(dǎo)者收到該條目時(shí)的任期號(hào)。每個(gè)日志條目還有一個(gè)整數(shù)索引，標(biāo)識(shí)其在日志中的位置。

圖片

一個(gè)日志條目被認(rèn)為是 已提交的 (committed) 時(shí)，意味著它可以安全地應(yīng)用于狀態(tài)機(jī)了。Raft 保證已提交的條目是持久的，并且最終會(huì)被所有可用的狀態(tài)機(jī)執(zhí)行。當(dāng)創(chuàng)建條目的領(lǐng)導(dǎo)者已在多數(shù)服務(wù)器上復(fù)制了該條目時(shí)，該條目即被提交（例如論文圖 6 中的條目 7）。這也同時(shí)提交了領(lǐng)導(dǎo)者日志中所有在它之前的條目，包括由先前領(lǐng)導(dǎo)者創(chuàng)建的條目。領(lǐng)導(dǎo)者會(huì)跟蹤它所知道的最高已提交條目的索引 (commitIndex)，并在未來的 AppendEntries RPC（包括心跳）中包含該索引，以便其他服務(wù)器最終得知。一旦跟隨者得知某個(gè)日志條目已提交，它就會(huì)按日志順序?qū)⒃摋l目應(yīng)用于其本地狀態(tài)機(jī)。

Raft 的日志機(jī)制旨在維護(hù)不同服務(wù)器日志之間的高度一致性，這構(gòu)成了 日志匹配特性 (Log Matching Property)：

1. 如果在不同日志中的兩個(gè)條目具有相同的索引和任期，那么它們存儲(chǔ)相同的命令。這是因?yàn)轭I(lǐng)導(dǎo)者在給定的任期內(nèi)，對(duì)于一個(gè)給定的日志索引最多只創(chuàng)建一個(gè)條目，并且日志條目在日志中的位置永遠(yuǎn)不會(huì)改變。
2. 如果在不同日志中的兩個(gè)條目具有相同的索引和任期，那么這些日志在直到該索引（包括該索引）之前的所有條目上都是相同的。這通過 AppendEntries RPC 執(zhí)行的一個(gè)簡單的一致性檢查來保證：領(lǐng)導(dǎo)者在發(fā)送 AppendEntries RPC 時(shí)，會(huì)包含其日志中緊接在新條目之前的那個(gè)條目的索引和任期。如果跟隨者在其日志中找不到具有相同索引和任期的條目，它就會(huì)拒絕新的條目。

圖片

正常操作期間，領(lǐng)導(dǎo)者和跟隨者的日志保持一致，因此 AppendEntries 的一致性檢查永遠(yuǎn)不會(huì)失敗。然而，領(lǐng)導(dǎo)者崩潰可能會(huì)導(dǎo)致日志不一致（舊領(lǐng)導(dǎo)者可能沒有完全復(fù)制其日志中的所有條目）。這些不一致性可能在一系列領(lǐng)導(dǎo)者和跟隨者崩潰中累積（如論文圖 7 所示）。

Raft 中，領(lǐng)導(dǎo)者通過強(qiáng)制跟隨者的日志復(fù)制自己的日志來處理不一致性。這意味著跟隨者日志中沖突的條目將被領(lǐng)導(dǎo)者日志中的條目覆蓋。為了使跟隨者的日志與自己的日志一致，領(lǐng)導(dǎo)者必須找到兩個(gè)日志一致的最新日志條目，刪除該點(diǎn)之后跟隨者日志中的所有條目，并向跟隨者發(fā)送該點(diǎn)之后領(lǐng)導(dǎo)者日志中的所有條目。這些操作都是響應(yīng) AppendEntries RPC 的一致性檢查而發(fā)生的。

領(lǐng)導(dǎo)者為每個(gè)跟隨者維護(hù)一個(gè) nextIndex，即領(lǐng)導(dǎo)者將要發(fā)送給該跟隨者的下一個(gè)日志條目的索引。當(dāng)領(lǐng)導(dǎo)者剛上任時(shí)，它會(huì)將所有 nextIndex 值初始化為其日志中最后一個(gè)條目之后的索引。如果跟隨者的日志與領(lǐng)導(dǎo)者的不一致，下一次 AppendEntries RPC 中的一致性檢查將會(huì)失敗。在被拒絕后，領(lǐng)導(dǎo)者會(huì)遞減 nextIndex 并重試 AppendEntries RPC。最終 nextIndex 會(huì)達(dá)到一個(gè)領(lǐng)導(dǎo)者和跟隨者日志匹配的點(diǎn)。此時(shí) AppendEntries 將成功，它會(huì)移除跟隨者日志中任何沖突的條目，并追加來自領(lǐng)導(dǎo)者日志的條目（如果有）。一旦 AppendEntries 成功，跟隨者的日志就與領(lǐng)導(dǎo)者的日志一致了，并且在該任期的剩余時(shí)間里都將保持這種狀態(tài)。

通過這種機(jī)制，領(lǐng)導(dǎo)者上任時(shí)無需采取任何特殊操作來恢復(fù)日志一致性。它只需開始正常操作，日志就會(huì)在 AppendEntries 一致性檢查失敗時(shí)自動(dòng)趨于一致。領(lǐng)導(dǎo)者從不覆蓋或刪除其自身日志中的條目（領(lǐng)導(dǎo)者只追加屬性）。

安全性

前面描述的領(lǐng)導(dǎo)者選舉和日志復(fù)制機(jī)制尚不足以確保每個(gè)狀態(tài)機(jī)以完全相同的順序執(zhí)行完全相同的命令。例如，一個(gè)跟隨者可能在領(lǐng)導(dǎo)者提交若干日志條目時(shí)不可用，然后它可能被選為領(lǐng)導(dǎo)者并用新的條目覆蓋這些已提交的條目。本節(jié)通過增加一個(gè)關(guān)于哪些服務(wù)器可以被選舉為領(lǐng)導(dǎo)者的限制來完善 Raft 算法。這個(gè)限制確保了任何給定任期的領(lǐng)導(dǎo)者都包含先前任期中所有已提交的條目（領(lǐng)導(dǎo)者完整性屬性）。

選舉限制 (Election restriction)

在任何基于領(lǐng)導(dǎo)者的共識(shí)算法中，領(lǐng)導(dǎo)者最終必須存儲(chǔ)所有已提交的日志條目。Raft 采用一種更簡單的方法，它保證從選舉的那一刻起，每個(gè)新領(lǐng)導(dǎo)者都擁有先前任期中所有已提交的條目，而無需將這些條目傳輸給領(lǐng)導(dǎo)者。這意味著日志條目只從領(lǐng)導(dǎo)者單向流向跟隨者，并且領(lǐng)導(dǎo)者從不覆蓋其日志中的現(xiàn)有條目。

Raft 利用投票過程來阻止一個(gè)候選人贏得選舉，除非其日志包含了所有已提交的條目。候選人為了當(dāng)選必須聯(lián)系集群中的多數(shù)服務(wù)器，這意味著每個(gè)已提交的條目必須存在于該多數(shù)服務(wù)器中的至少一個(gè)服務(wù)器上。如果候選人的日志至少與該多數(shù)服務(wù)器中任何其他日志一樣“最新”（“最新”的定義如下），那么它將持有所有已提交的條目。RequestVote RPC 實(shí)現(xiàn)了這一限制：RPC 中包含了關(guān)于候選人日志的信息，如果投票者自己的日志比候選人的日志更新，則它會(huì)拒絕投票。

Raft 通過比較日志中最后條目的索引和任期來判斷兩個(gè)日志哪個(gè)更新：

• 如果日志的最后條目具有不同的任期，則具有較晚任期的日志更新。
• 如果日志以相同的任期結(jié)束，則較長的日志更新。

提交先前任期的條目 (Committing entries from previous terms)

如 5.3 節(jié)所述，領(lǐng)導(dǎo)者知道其當(dāng)前任期的一個(gè)條目一旦存儲(chǔ)在多數(shù)服務(wù)器上就被提交了。如果領(lǐng)導(dǎo)者在提交一個(gè)條目之前崩潰，未來的領(lǐng)導(dǎo)者將嘗試完成該條目的復(fù)制。然而，領(lǐng)導(dǎo)者不能僅僅因?yàn)橐粋€(gè)先前任期的條目存儲(chǔ)在多數(shù)服務(wù)器上，就立即斷定該條目已提交。論文中的圖 8 展示了一種情況：一個(gè)舊的日志條目存儲(chǔ)在多數(shù)服務(wù)器上，但仍可能被未來的領(lǐng)導(dǎo)者覆蓋。

圖片

為了消除如圖 8 所示的問題，Raft 規(guī)定：從不通過計(jì)算副本數(shù)來提交先前任期的日志條目 。只有領(lǐng)導(dǎo)者當(dāng)前任期的日志條目才通過計(jì)算副本數(shù)來提交。一旦當(dāng)前任期的某個(gè)條目以這種方式提交，那么所有先前的條目都會(huì)因?yàn)槿罩酒ヅ涮匦远g接提交。Raft 采取這種更保守的方法是為了簡化設(shè)計(jì)。

這種提交規(guī)則的復(fù)雜性源于當(dāng)領(lǐng)導(dǎo)者復(fù)制先前任期的條目時(shí)，日志條目會(huì)保留其原始任期號(hào)。Raft 的這種方法使得推理日志條目更容易，因?yàn)樗鼈冊(cè)诓煌瑫r(shí)間和不同日志中保持相同的任期號(hào)。此外，與其他算法相比，Raft 中的新領(lǐng)導(dǎo)者發(fā)送的先前任期的日志條目更少。

安全性論證 (Safety argument)

有了完整的 Raft 算法，現(xiàn)在可以更精確地論證 領(lǐng)導(dǎo)者完整性屬性 (Leader Completeness Property) 成立。該論證采用反證法。

假設(shè) T 任期的領(lǐng)導(dǎo)者 leaderT 提交了其任期內(nèi)的一個(gè)日志條目，但該條目未被某個(gè)未來任期 U (U > T) 的領(lǐng)導(dǎo)者 leaderU 存儲(chǔ)。

圖片

1. 該已提交條目在 leaderU 當(dāng)選時(shí)必然不在其日志中（領(lǐng)導(dǎo)者從不刪除或覆蓋條目）。
2. leaderT 在集群的多數(shù)服務(wù)器上復(fù)制了該條目，而 leaderU 從集群的多數(shù)服務(wù)器獲得了選票。因此，至少有一個(gè)服務(wù)器（稱為“投票者”）既接受了來自 leaderT 的條目，也投票給了 leaderU （如圖 9 所示）。
3. 投票者必須在投票給 leaderU 之前就接受了來自 leaderT 的已提交條目；否則，它會(huì)拒絕來自 leaderT 的 AppendEntries 請(qǐng)求（因?yàn)樗漠?dāng)前任期會(huì)高于 T）。
4. 投票者在投票給 leaderU 時(shí)仍然存儲(chǔ)著該條目，因?yàn)樗兄虚g的領(lǐng)導(dǎo)者都包含該條目（根據(jù)假設(shè)），領(lǐng)導(dǎo)者從不移除條目，而跟隨者只有在與領(lǐng)導(dǎo)者沖突時(shí)才移除條目。
5. 投票者將選票投給了 leaderU，因此 leaderU 的日志必須至少與投票者的日志一樣新。這將導(dǎo)致以下兩種矛盾之一：

如果投票者和 leaderU 的最后日志任期相同，那么 leaderU 的日志必須至少與投票者的日志一樣長，因此其日志包含了投票者日志中的每個(gè)條目。這與假設(shè)（leaderU 不包含該已提交條目，而投票者包含）相矛盾。

否則，leaderU 的最后日志任期必須大于投票者的最后日志任期。而且，它也大于 T，因?yàn)橥镀闭叩淖詈笕罩救纹谥辽偈?T（它包含來自 T 任期的已提交條目）。創(chuàng)建 leaderU 最后日志條目的先前領(lǐng)導(dǎo)者在其日志中必須包含該已提交條目（根據(jù)假設(shè)）。那么，根據(jù)日志匹配特性，leaderU 的日志也必須包含該已提交條目，這又是一個(gè)矛盾。

6. 至此，矛盾論證完畢。因此，所有大于 T 的任期的領(lǐng)導(dǎo)者都必須包含 T 任期中在該任期提交的所有條目。

圖片

有了領(lǐng)導(dǎo)者完整性屬性，就可以證明論文圖 3 中的 狀態(tài)機(jī)安全屬性 (State Machine Safety Property)：如果一臺(tái)服務(wù)器已將某個(gè)給定索引的日志條目應(yīng)用于其狀態(tài)機(jī)，則其他服務(wù)器永遠(yuǎn)不會(huì)對(duì)同一索引應(yīng)用不同的日志條目。當(dāng)服務(wù)器將日志條目應(yīng)用于其狀態(tài)機(jī)時(shí)，其日志必須與領(lǐng)導(dǎo)者的日志在該條目之前（包括該條目）完全相同，并且該條目必須是已提交的?，F(xiàn)在考慮任何服務(wù)器應(yīng)用給定日志索引的最低任期；領(lǐng)導(dǎo)者完整性屬性保證所有更高任期的領(lǐng)導(dǎo)者都將存儲(chǔ)相同的日志條目，因此在后續(xù)任期中應(yīng)用該索引的服務(wù)器將應(yīng)用相同的值。

最后，Raft 要求服務(wù)器按日志索引順序應(yīng)用條目。結(jié)合狀態(tài)機(jī)安全屬性，這意味著所有服務(wù)器都將以相同的順序?qū)⑼耆嗤娜罩緱l目集應(yīng)用于其狀態(tài)機(jī)。