RAFT 論文中文翻譯(1)

本篇博客為著名的 RAFT 一致性算法論文的中文翻譯，論文名為《In search of an Understandable Consensus Algorithm (Extended Version)》(尋找一種易于理解的一致性算法)

摘要

Raft 是一種用來管理日志復制的一致性算法。它和 Paxos 的性能和功能是一樣的，但是它和 Paxos 的結構不一樣；這使得 Raft 更容易理解并且更易于建立實際的系統。為了提高理解性，Raft 將一致性算法分為了幾個部分，例如領導選取（leader selection），日志復制（log replication）和安全性（safety），同時它使用了更強的一致性來減少了必須需要考慮的狀態。從用戶學習的結果來看，Raft 比 Paxos 更容易學會。Raft 還包括了一種新的機制來使得動態改變集群成員，它使用重疊大多數（overlapping majorities）來保證安全。

1 引言

一致性算法允許一組機器像一個整體一樣工作，即使其中的一些機器出了錯誤也能正常工作。正因為此，他們扮演著建立大規模可靠的軟件系統的關鍵角色。在過去的十年中 Paxos 一直都主導著有關一致性算法的討論：大多數一致性算法的實現都基于它或者受它影響，并且 Paxos 也成為了教學生關于一致性知識的主要工具。

不幸的是，盡管在降低它的復雜性方面做了許多努力，Paxos 依舊很難理解。并且，Paxos 需要經過復雜的修改才能應用于實際中。這些導致了系統構構建者和學生都十分頭疼。

在被 Paxos 折磨之后，我們開始尋找一種在系統構建和教學上更好的新的一致性算法。我們的首要目標是讓它易于理解：我們能不能定義一種面向實際系統的一致性算法并且比 Paxos 更容易學習呢？并且，我們希望這種算法能憑直覺就能明白，這對于一個系統構建者來說是十分必要的。對于一個算法，不僅僅是讓它工作起來很重要，知道它是如何工作的更重要。

我們工作的結果是一種新的一致性算法，叫做 Raft。在設計 Raft 的過程中我們應用了許多專門的技巧來提升理解性，包括算法分解（分為領導選取（leader selection），日志復制（log replication）和安全性（safety））和減少狀態（state space reduction）（相對于 Paxos，Raft 減少了非確定性的程度和服務器互相不一致的方式）。在兩所學校的43個學生的研究中發現，Raft 比 Paxos 要更容易理解：在學習了兩種算法之后，其中的33個學生回答 Raft 的問題要比回答 Paxos 的問題要好。

Raft 算法和現在一些已經有的算法在一些地方很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication。但是 Raft 有幾個新的特性：

強領導者（Strong Leader）：Raft 使用一種比其他算法更強的領導形式。例如，日志條目只從領導者發送向其他服務器。這樣就簡化了對日志復制的管理，使得 Raft 更易于理解。

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

成員變化（Membership Change）：Raft 為了調整集群中成員關系使用了新的聯合一致性（joint consensus）的方法，這種方法中大多數不同配置的機器在轉換關系的時候會交迭（overlap）。這使得在配置改變的時候，集群能夠繼續操作。

我們認為，Raft 在教學方面和實際實現方面比 Paxos 和其他算法更出眾。它比其他算法更簡單、更容易理解；它能滿足一個實際系統的需求；它擁有許多開源的實現并且被許多公司所使用；它的安全特性已經被證明；并且它的效率和其他算法相比也具有競爭力。

這篇論文剩下的部分會講如下內容：復制狀態機（replicated state machine）問題（第2節），討論 Paxos 的優缺點（第3節），討論我們用的為了達到提升理解性的方法（第4節），陳述 Raft 一致性算法（第5~8節），評價 Raft 算法（第9節），對相關工作的討論（第10節）。

2 復制狀態機（Replicated State Machine）

一致性算法是在復制狀態機的背景下提出來的。在這個方法中，在一組服務器的狀態機產生同樣的狀態的副本因此即使有一些服務器崩潰了這組服務器也還能繼續執行。復制狀態機在分布式系統中被用于解決許多有關容錯的問題。例如，GFS，HDFS還有 RAMCloud 這些大規模的系統都是用一個單獨的集群領導者，使用一個單獨的復制狀態機來進行領導選取和存儲配置信息來應對領導者的崩潰。使用復制狀態機的例子有 Chubby 和 ZooKeeper。

如圖-1所示，復制狀態機是通過復制日志來實現的。每一臺服務器保存著一份日志，日志中包含一系列的命令，狀態機會按順序執行這些命令。因為每一臺計算機的狀態機都是確定的，所以每個狀態機的狀態都是相同的，執行的命令是相同的，最后的執行結果也就是一樣的了。

如何保證復制日志一致就是一致性算法的工作了。在一臺服務器上，一致性模塊接受客戶端的命令并且把命令加入到它的日志中。它和其他服務器上的一致性模塊進行通信來確保每一個日志最終包含相同序列的請求，即使有一些服務器宕機了。一旦這些命令被正確的復制了，每一個服務器的狀態機都會按同樣的順序去執行它們，然后將結果返回給客戶端。最終，這些服務器看起來就像一臺可靠的狀態機。

應用于實際系統的一致性算法一般有以下特性：

確保安全性（從來不會返回一個錯誤的結果），即使在所有的非拜占庭（Non-Byzantine）情況下，包括網絡延遲、分區、丟包、冗余和亂序的情況下。

高可用性，只要集群中的大部分機器都能運行，可以互相通信并且可以和客戶端通信，這個集群就可用。因此，一般來說，一個擁有 5 臺機器的集群可以容忍其中的 2 臺的失敗（fail）。服務器停止工作了我們就認為它失敗（fail）了，沒準一會當它們擁有穩定的存儲時就能從中恢復過來，重新加入到集群中。

不依賴時序保證一致性，時鐘錯誤和極端情況下的消息延遲在最壞的情況下才會引起可用性問題。

通常情況下，一條命令能夠盡可能快的在大多數節點對一輪遠程調用作出相應時完成，一少部分慢的機器不會影響系統的整體性能。

3 Paxos 算法的不足

在過去的10年中，Leslie Lamport 的 Paxos 算法幾乎已經成為了一致性算法的代名詞：它是授課中最常見的算法，同時也是許多一致性算法實現的起點。Paxos 首先定義了一個能夠達成單一決策一致的協議，例如一個單一復制日志條目（single replicated log entry）。我們把這個子集叫做單一決策 Paxos（single-decree Paxos）。之后 Paxos通過組合多個這種協議來完成一系列的決策，例如一個日志（multi-Paxos）。Paxos 確保安全性和活躍性（liveness），并且它支持集群成員的變更。它的正確性已經被證明，通常情況下也很高效。

不幸的是，Paxos 有兩個致命的缺點。第一個是 Paxos 太難以理解。它的完整的解釋晦澀難懂；很少有人能完全理解，只有少數人成功的讀懂了它。并且大家做了許多努力來用一些簡單的術語來描述它。盡管這些解釋都關注于單一決策子集問題，但仍具有挑戰性。在 NSDI 2012 會議上的一次非正式調查顯示，我們發現大家對 Paxos 都感到不滿意，其中甚至包括一些有經驗的研究員。我們自己也曾深陷其中，我們在讀過幾篇簡化它的文章并且設計了我們自己的算法之后才完全理解了 Paxos，而整個過程花費了將近一年的時間。

我們假定 Paxos 的晦澀來源于它將單決策子集作為它的基礎。單決策（Single-decree）Paxos 是晦澀且微妙的：它被劃分為兩個沒有簡單直觀解釋的階段，并且難以獨立理解。正因為如此，它不能很直觀的讓我們知道為什么單一決策協議能夠工作。為多決策 Paxos 設計的規則又添加了額外的復雜性和精巧性。我們相信多決策問題能夠分解為其它更直觀的方式。

Paxos 的第二個缺點是它難以在實際環境中實現。其中一個原因是，對于多決策 Paxos （multi-Paxos） ，大家還沒有一個一致同意的算法。Lamport 的描述大部分都是有關于單決策 Paxos （single-decree Paxos）；他僅僅描述了實現多決策的可能的方法，缺少許多細節。有許多實現 Paxos 和優化 Paxos 的嘗試，但是他們都和 Lamport 的描述有些出入。例如，Chubby 實現的是一個類似 Paxos 的算法，但是在許多情況下的細節沒有公開。

另外，Paxos 的結構也是不容易在一個實際系統中進行實現的，這是單決策問題分解帶來的又一個問題。例如，從許多日志條目中選出條目然后把它們融合到一個序列化的日志中并沒有帶來什么好處，它僅僅增加了復雜性。圍繞著日志來設計一個系統是更簡單、更高效的：新日志按照嚴格的順序添加到日志中去。另一個問題是，Paxos 使用對等的點對點的實現作為它的核心（盡管它最終提出了一種弱領導者的形式來優化性能）。這種方法在只有一個決策被制定的情況下才顯得有效，但是很少有現實中的系統使用它。如果要做許多的決策，選擇一個領導人，由領帶人來協調是更簡單有效的方法。

因此，在實際的系統應用中和 Paxos 算法都相差很大。所有開始于 Paxos 的實現都會遇到很多問題，然后由此衍生出了許多與 Paxos 有很大不同的架構。這是既費時又容易出錯的，并且理解 Paxos 的難度又非常大。Paxos 算法在它正確性的理論證明上是很好的，但是在實現上的價值就遠遠不足了。來自 Chubby 的實現的一條評論就能夠說明：

Paxos 算法的描述與實際實現之間存在巨大的鴻溝…最終的系統往往建立在一個沒有被證明的算法之上。

正因為存在這些問題，我們認為 Paxos 不僅對于系統的構建者來說不友好，同時也不利于教學。鑒于一致性算法對于大規模軟件系統的重要性，我們決定試著來設計一種另外的比 Paxos 更好的一致性算法。Raft 就是這樣的一個算法。

4 易于理解的設計

設計 Raft 的目標有如下幾個：

它必須提供一個完整的、實際的基礎來進行系統構建，為的是減少開發者的工作；

它必須在所有情況下都能保證安全可用；

它對于常規操作必須高效；

最重要的目標是：易于理解，它必須使得大多數人能夠很容易的理解；

另外，它必須能讓開發者有一個直觀的認識，這樣才能使系統構建者們去對它進行擴展。

在設計 Raft 的過程中，我們不得不在許多種方法中做出選擇。當面臨這種情況時，我們通常會權衡可理解性：每種方法的可理解性是如何的？（例如，它的狀態空間有多復雜？它是不是有很細微的含義？）它的可讀性如何？讀者能不能輕易地理解這個方法和它的含義？

我們意識到對這種可理解性的分析具有高度的主觀性；盡管如此，我們使用了兩種適用的方式。第一種是眾所周知的問題分解：我們盡可能將問題分解成為若干個可解決的、可被理解的小問題。例如，在 Raft 中，我們把問題分解成為了領導選取（leader election）、日志復制（log replication）、安全（safety）和成員變化（membership changes）。

我們采用的第二個方法是通過減少需要考慮的狀態的數量將狀態空間簡化，這能夠使得整個系統更加一致并且盡可能消除不確定性。特別地，日志之間不允許出現空洞，并且 Raft 限制了限制了日志不一致的可能性。盡管在大多數情況下，我們都都在試圖消除不確定性，但是有時候有些情況下，不確定性使得算法更易理解。尤其是，隨機化方法使得不確定性增加，但是它減少了狀態空間。我們使用隨機化來簡化了 Raft 中的領導選取算法。

5 Raft 一致性算法

Raft 是一種用來管理第 2 章中提到的復制日志的算法。表-2 為了方便參考是一個算法的總結版本，表-3 列舉了算法中的關鍵性質；表格中的這些元素將會在這一章剩下的部分中分別進行討論。

狀態：

在所有服務器上持久存在的：（在響應遠程過程調用 RPC 之前穩定存儲的）

在所有服務器上不穩定存在的：

在領導人服務器上不穩定存在的：（在選舉之后初始化的）

附加日志遠程過程調用 （AppendEntries RPC）

由領導人來調用復制日志（5.3節）；也會用作heartbeat

接受者需要實現：

如果 term < currentTerm返回 false（5.1節）

如果在prevLogIndex處的日志的任期號與prevLogTerm不匹配時，返回 false（5.3節）

如果一條已經存在的日志與新的沖突（index 相同但是任期號 term 不同），則刪除已經存在的日志和它之后所有的日志（5.3節）

添加任何在已有的日志中不存在的條目

如果leaderCommit > commitIndex，將commitIndex設置為leaderCommit和最新日志條目索引號中較小的一個

投票請求 RPC（RequestVote RPC）

由候選人發起收集選票（5.2節）

接受者需要實現：

如果term < currentTerm返回 false（5.1節）

如果votedFor為空或者與candidateId相同，并且候選人的日志和自己的日志一樣新，則給該候選人投票（5.2節 和 5.4節）

服務器需要遵守的規則：

所有服務器：

如果commitIndex > lastApplied，lastApplied自增，將log[lastApplied]應用到狀態機（5.3節）

如果 RPC 的請求或者響應中包含一個 term T 大于 currentTerm，則currentTerm賦值為 T，并切換狀態為追隨者（Follower）（5.1節）

追隨者（followers）: 5.2節

響應來自候選人和領導人的 RPC

如果在超過選取領導人時間之前沒有收到來自當前領導人的AppendEntries RPC或者沒有收到候選人的投票請求，則自己轉換狀態為候選人

候選人：5.2節

轉變為選舉人之后開始選舉：

currentTerm自增

給自己投票

重置選舉計時器

向其他服務器發送RequestVote RPC

如果收到了來自大多數服務器的投票：成為領導人

如果收到了來自新領導人的AppendEntries RPC（heartbeat）：轉換狀態為追隨者

如果選舉超時：開始新一輪的選舉

領導人：

一旦成為領導人：向其他所有服務器發送空的AppendEntries RPC（heartbeat）;在空閑時間重復發送以防止選舉超時（5.2節）

如果收到來自客戶端的請求：向本地日志增加條目，在該條目應用到狀態機后響應客戶端（5.3節）

對于一個追隨者來說，如果上一次收到的日志索引大于將要收到的日志索引（nextIndex）：通過AppendEntries RPC將 nextIndex 之后的所有日志條目發送出去

如果發送成功：將該追隨者的 nextIndex和matchIndex更新

如果由于日志不一致導致AppendEntries RPC失敗：nextIndex遞減并且重新發送（5.3節）

如果存在一個滿足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，則將commitIndex賦值為 N

Raft 通過首先選出一個領導人來實現一致性，然后給予領導人完全管理復制日志（replicated log）的責任。領導人接收來自客戶端的日志條目，并把它們復制到其他的服務器上，領帶人還要告訴服務器們什么時候將日志條目應用到它們的狀態機是安全的。通過選出領導人能夠簡化復制日志的管理工作。例如，領導人能夠決定將新的日志條目放到哪，而并不需要和其他的服務器商議，數據流被簡化成從領導人流向其他服務器。如果領導人宕機或者和其他服務器失去連接，就可以選取下一個領導人。

通過選出領導人，Raft 將一致性問題分解成為三個相對獨立的子問題：

領導人選取（Leader election）：在一個領導人宕機之后必須要選取一個新的領導人（5.2節）

日志復制（Log replication）：領導人必須從客戶端接收日志然后復制到集群中的其他服務器，并且強制要求其他服務器的日志保持和自己相同

**安全性（Safety）：**Raft 的關鍵的安全特性是 表-3 中提到的狀態機安全原則（State Machine Safety）:如果一個服務器已經將給定索引位置的日志條目應用到狀態機中，則所有其他服務器不會在該索引位置應用不同的條目。5.4節闡述了 Raft 是如何保證這條原則的，解決方案涉及到一個對于選舉機制另外的限制，這一部分會在 5.2節 中說明。

在說明了一致性算法之后，本章會討論有關可用性（availability）的問題和系統中時序（timing）的問題。

5.1 Raft 基礎

一個 Raft 集群包括若干服務器；對于一個典型的 5 服務器集群，該集群能夠容忍 2 臺機器不能正常工作，而整個系統保持正常。在任意的時間，每一個服務器一定會處于以下三種狀態中的一個：領導人、候選人、追隨者。在正常情況下，只有一個服務器是領導人，剩下的服務器是追隨者。追隨者們是被動的：他們不會發送任何請求，只是響應來自領導人和候選人的請求。領導人來處理所有來自客戶端的請求（如果一個客戶端與追隨者進行通信，追隨者會將信息發送給領導人）。候選人是用來選取一個新的領導人的，這一部分會在 5.2節 進行闡釋。圖-4 闡述了這些狀態，和它們之間的轉換；它們的轉換會在下邊進行討論。

如 圖-5 所示，Raft 算法將時間劃分成為任意不同長度的任期（term）。任期用連續的數字進行表示。每一個任期的開始都是一次選舉（election），就像 5.2節 所描述的那樣，一個或多個候選人會試圖成為領導人。如果一個候選人贏得了選舉，它就會在該任期的剩余時間擔任領導人。在某些情況下，選票會被瓜分，有可能沒有選出領導人，那么，將會開始另一個任期，并且立刻開始下一次選舉。Raft 算法保證在給定的一個任期最少要有一個領導人。

不同的服務器可能會在任期內觀察到多次不同的狀態轉換，在某些情況下，一臺服務器可能看不到一次選舉或者一個完整的任期。任期在 Raft 中充當邏輯時鐘的角色，并且它們允許服務器檢測過期的信息，比如過時的領導人。每一臺服務器都存儲著一個當前任期的數字，這個數字會單調的增加。當服務器之間進行通信時，會互相交換當前任期號；如果一臺服務器的當前任期號比其它服務器的小，則更新為較大的任期號。如果一個候選人或者領導人意識到它的任期號過時了，它會立刻轉換為追隨者狀態。如果一臺服務器收到的請求的任期號是過時的，那么它會拒絕此次請求。

Raft 中的服務器通過遠程過程調用（RPC）來通信，基本的 Raft 一致性算法僅需要 2 種 RPC。RequestVote RPC 是候選人在選舉過程中觸發的（5.2節），AppendEntries RPC 是領導人觸發的，為的是復制日志條目和提供一種心跳（heartbeat）機制（5.3節）。第7章加入了第三種 RPC 來在各個服務器之間傳輸快照（snapshot）。如果服務器沒有及時收到 RPC 的響應，它們會重試，并且它們能夠并行的發出 RPC 來獲得最好的性能。

5.2 領導人選取

Raft 使用一種心跳機制（heartbeat）來觸發領導人的選取。當服務器啟動時，它們會初始化為追隨者。一太服務器會一直保持追隨者的狀態只要它們能夠收到來自領導人或者候選人的有效 RPC。領導人會向所有追隨者周期性發送心跳（heartbeat，不帶有任何日志條目的 AppendEntries RPC）來保證它們的領導人地位。如果一個追隨者在一個周期內沒有收到心跳信息，就叫做選舉超時（election timeout）,然后它就會假定沒有可用的領導人并且開始一次選舉來選出一個新的領導人。

為了開始選舉，一個追隨者會自增它的當前任期并且轉換狀態為候選人。然后，它會給自己投票并且給集群中的其他服務器發送 RequestVote RPC。一個候選人會一直處于該狀態，直到下列三種情形之一發生：

它贏得了選舉；

另一臺服務器贏得了選舉；

一段時間后沒有任何一臺服務器贏得了選舉

這些情形會在下面的章節中分別討論。

一個候選人如果在一個任期內收到了來自集群中大多數服務器的投票就會贏得選舉。在一個任期內，一臺服務器最多能給一個候選人投票，按照先到先服務原則（first-come-first-served）（注意：在 5.4節 針對投票添加了一個額外的限制）。大多數原則使得在一個任期內最多有一個候選人能贏得選舉（表-3 中提到的選舉安全原則）。一旦有一個候選人贏得了選舉，它就會成為領導人。然后它會像其他服務器發送心跳信息來建立自己的領導地位并且組織新的選舉。

當一個候選人等待別人的選票時，它有可能會收到來自其他服務器發來的聲明其為領導人的 AppendEntries RPC。如果這個領導人的任期（包含在它的 RPC 中）比當前候選人的當前任期要大，則候選人認為該領導人合法，并且轉換自己的狀態為追隨者。如果在這個 RPC 中的任期小于候選人的當前任期，則候選人會拒絕此次 RPC， 繼續保持候選人狀態。

第三種情形是一個候選人既沒有贏得選舉也沒有輸掉選舉：如果許多追隨者在同一時刻都成為了候選人，選票會被分散，可能沒有候選人能獲得大多數的選票。當這種情形發生時，每一個候選人都會超時，并且通過自增任期號和發起另一輪 RequestVote RPC 來開始新的選舉。然而，如果沒有其它手段來分配選票的話，這種情形可能會無限的重復下去。

Raft 使用隨機的選舉超時時間來確保第三種情形很少發生，并且能夠快速解決。為了防止在一開始是選票就被瓜分，選舉超時時間是在一個固定的間隔內隨機選出來的（例如，150~300ms）。這種機制使得在大多數情況下只有一個服務器會率先超時，它會在其它服務器超時之前贏得選舉并且向其它服務器發送心跳信息。同樣的機制被用于選票一開始被瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個隨機的選舉超時時間，在超時進行下一次選舉之前一直等待。這能夠減小在新的選舉中一開始選票就被瓜分的可能性。9.3節 展示了這種方法能夠快速的選出一個領導人。

選舉是一個理解性引導我們設計替代算法的一個例子。最開始時，我們計劃使用一種排名系統：給每一個候選人分配一個唯一的排名，用于在競爭的候選人之中選擇領導人。如果一個候選人發現了另一個比它排名高的候選人，那么它會回到追隨者的狀態，這樣排名高的候選人會很容易地贏得選舉。但是我們發現這種方法在可用性方面有一點問題（一個低排名的服務器在高排名的服務器宕機后，需要等待超時才能再次成為候選人，但是如果它這么做的太快，它能重置選舉領帶人的過程）。我們對這個算法做了多次調整，但是每次調整后都會出現一些新的問題。最終我們認為隨機重試的方法是更明確并且更易于理解的。

5.3 日志復制

一旦選出了領導人，它就開始接收客戶端的請求。每一個客戶端請求都包含一條需要被復制狀態機（replicated state machine）執行的命令。領導人把這條命令作為新的日志條目加入到它的日志中去，然后并行的向其他服務器發起 AppendEntries RPC ，要求其它服務器復制這個條目。當這個條目被安全的復制之后（下面的部分會詳細闡述），領導人會將這個條目應用到它的狀態機中并且會向客戶端返回執行結果。如果追隨者崩潰了或者運行緩慢或者是網絡丟包了，領導人會無限的重試 AppendEntries RPC（甚至在它向客戶端響應之后）知道所有的追隨者最終存儲了所有的日志條目。

日志就像 圖-6 所示那樣組織的。每個日志條目存儲著一條被狀態機執行的命令和當這條日志條目被領導人接收時的任期號。日志條目中的任期號用來檢測在不同服務器上日志的不一致性，并且能確保 圖-3 中的一些特性。每個日志條目也包含一個整數索引來表示它在日志中的位置。

領導人決定什么時候將日志條目應用到狀態機是安全的；這種條目被稱為可被提交（commited）。Raft 保證可被提交（commited）的日志條目是持久化的并且最終會被所有可用的狀態機執行。一旦被領導人創建的條目已經復制到了大多數的服務器上，這個條目就稱為可被提交的（例如，圖-6中的7號條目）。領導人日志中之前的條目都是可被提交的（commited），包括由之前的領導人創建的條目。5.4節將會討論當領導人更替之后這條規則的應用問題的細節，并且也討論了這種提交方式是安全的。領導人跟蹤記錄它所知道的被提交條目的最大索引值，并且這個索引值會包含在之后的 AppendEntries RPC 中（包括心跳 heartbeat 中），為的是讓其他服務器都知道這條條目已經提交。一旦一個追隨者知道了一個日志條目已經被提交，它會將該條目應用至本地的狀態機（按照日志順序）。

我們設計了 Raft 日志機制來保證不同服務器上日志的一致性。這樣做不僅簡化了系統的行為使得它更可預測，并且也是保證安全性不可或缺的一部分。Raft 保證以下特性，并且也保證了 表-3 中的日志匹配原則（Log Matching Property）:

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

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

第一條特性源于領導人在一個任期里在給定的一個日志索引位置最多創建一條日志條目，同時該條目在日志中的位置也從來不會改變。第二條特性源于 AppendEntries 的一個簡單的一致性檢查。當發送一個 AppendEntries RPC 時，領導人會把新日志條目緊接著之前的條目的索引位置和任期號都包含在里面。如果追隨者沒有在它的日志中找到相同索引和任期號的日志，它就會拒絕新的日志條目。這個一致性檢查就像一個歸納步驟：一開始空的日志的狀態一定是滿足日志匹配原則的，一致性檢查保證了當日志添加時的日志匹配原則。因此，只要 AppendEntries 返回成功的時候，領導人就知道追隨者們的日志和它的是一致的了。

在一般情況下，領導人和追隨者們的日志保持一致，因此 AppendEntries 一致性檢查通常不會失敗。然而，領導人的崩潰會導致日志不一致（舊的領導人可能沒有完全復制完日志中的所有條目）。這些不一致會導致一系列領導人和追隨者崩潰。圖-7 闡述了一些追隨者可能和新的領導人日志不同的情況。一個追隨者可能會丟失掉領導人上的一些條目，也有可能包含一些領導人沒有的條目，也有可能兩者都會發生。丟失的或者多出來的條目可能會持續多個任期。

在 Raft 算法中，領導人通過強制追隨者們復制它的日志來處理日志的不一致。這就意味著，在追隨者上的沖突日志會被領導者的日志覆蓋。5.4節會說明當添加了一個額外的限制之后這是安全的。

為了使得追隨者的日志同自己的一致，領導人需要找到追隨者同它的日志一致的地方，然后刪除追隨者在該位置之后的條目，然后將自己在該位置之后的條目發送給追隨者。這些操作都在 AppendEntries RPC 進行一致性檢查時完成。領導人給每一個追隨者維護了一個nextIndex，它表示領導人將要發送給該追隨者的下一條日志條目的索引。當一個領導人開始掌權時，它會將nextIndex初始化為它的最新的日志條目索引數+1（圖-7 中的 11）。如果一個追隨者的日志和領導者的不一致，AppendEntries 一致性檢查會在下一次 AppendEntries RPC 時返回失敗。在失敗之后，領導人會將nextIndex遞減然后重試 AppendEntries RPC。最終nextIndex會達到一個領導人和追隨者日志一致的地方。這時，AppendEntries 會返回成功，追隨者中沖突的日志條目都被移除了，并且添加所缺少的上了領導人的日志條目。一旦 AppendEntries 返回成功，追隨者和領導人的日志就一致了，這樣的狀態會保持到該任期結束。

如果需要的話，算法還可以進行優化來減少 AppendEntries RPC 失敗的次數。例如，當拒絕了一個 AppendEntries 請求，追隨者可以記錄下沖突日志條目的任期號和自己存儲那個任期的最早的索引。通過這些信息，領導人能夠直接遞減nextIndex跨過那個任期內所有的沖突條目；這樣的話，一個沖突的任期需要一次 AppendEntries RPC，而不是每一個沖突條目需要一次 AppendEntries RPC。在實踐中，我們懷疑這種優化是否是必要的，因為AppendEntries 一致性檢查很少失敗并且也不太可能出現大量的日志條目不一致的情況。

通過這種機制，一個領導人在掌權時不需要采取另外特殊的方式來恢復日志的一致性。它只需要使用一些常規的操作，通過響應 AppendEntries 一致性檢查的失敗能使得日志自動的趨于一致。一個領導人從來不會覆蓋或者刪除自己的日志（表-3 中的領導人只增加原則）。

這個日志復制機制展示了在第2章中闡述的所希望的一致性特性：Raft 能夠接受，復制并且應用新的日志條目只要大部分的服務器是正常的。在通常情況下，一條新的日志條目可以在一輪 RPC 內完成在集群的大多數服務器上的復制；并且一個速度很慢的追隨者并不會影響整體的性能。

5.4 安全性

之前的章節中討論了 Raft 算法是如何進行領導選取和復制日志的。然而，到目前為止這個機制還不能保證每一個狀態機能按照相同的順序執行同樣的指令。例如，當領導人提交了若干日志條目的同時一個追隨者可能宕機了，之后它又被選為了領導人然后用新的日志條目覆蓋掉了舊的那些，最后，不同的狀態機可能執行不同的命令序列。

這一節通過在領帶人選取部分加入了一個限制來完善了 Raft 算法。這個限制能夠保證對于固定的任期，任何的領導人都擁有之前任期提交的全部日志條目（表-3 中的領導人完全原則）。有了這一限制，日志提交的規則就更清晰了。最后，我們提出了對于領導人完全原則的簡單證明并且展示了它是如何修正復制狀態機的行為的。

5.4.1 選舉限制

在所有的以領導人為基礎的一致性算法中，領導人最終必須要存儲全部已經提交的日志條目。在一些一致性算法中，例如：Viewstamped Replication，即使一開始沒有包含全部已提交的條目也可以被選為領導人。這些算法都有一些另外的機制來保證找到丟失的條目并將它們傳輸給新的領導人，這個過程要么在選舉過程中完成，要么在選舉之后立即開始。不幸的是，這種方式大大增加了復雜性。Raft 使用了一種更簡單的方式來保證在新的領導人開始選舉的時候在之前任期的所有已提交的日志條目都會出現在上邊，而不需要將這些條目傳送給領導人。這就意味著日志條目只有一個流向：從領導人流向追隨者。領導人永遠不會覆蓋已經存在的日志條目。

Raft 使用投票的方式來阻止沒有包含全部日志條目的服務器贏得選舉。一個候選人為了贏得選舉必須要和集群中的大多數進行通信，這就意味著每一條已經提交的日志條目最少在其中一臺服務器上出現。如果候選人的日志至少和大多數服務器上的日志一樣新（up-to-date，這個概念會在下邊有詳細介紹），那么它一定包含有全部的已經提交的日志條目。RequestVote RPC 實現了這個限制：這個 RPC（遠程過程調用）包括候選人的日志信息，如果它自己的日志比候選人的日志要新，那么它會拒絕候選人的投票請求。

Raft 通過比較日志中最后一個條目的索引和任期號來決定兩個日志哪一個更新。如果兩個日志的任期號不同，任期號大的更新；如果任期號相同，更長的日志更新。

5.4.1 提交之前任期的日志條目

正如 5.3節 中描述的那樣，只要一個日志條目被存在了在多數的服務器上，領導人就知道當前任期就可以提交該條目了。如果領導人在提交之前就崩潰了，之后的領導人會試著繼續完成對日志的復制。然而，領導人并不能斷定存儲在大多數服務器上的日志條目一定在之前的任期中被提交了。圖-8 說明了一種情況，一條存儲在了大多數服務器上的日志條目仍然被新上任的領導人覆蓋了。

為了消除 圖-8 中描述的問題，Raft 從來不會通過計算復制的數目來提交之前人氣的日志條目。只有領導人當前任期的日志條目才能通過計算數目來進行提交。一旦當前任期的日志條目以這種方式被提交，那么由于日志匹配原則（Log Matching Property），之前的日志條目也都會被間接的提交。在某些情況下，領導人可以安全的知道一個老的日志條目是否已經被提交（例如，通過觀察該條目是否存儲到所有服務器上），但是 Raft 為了簡化問題使用了一種更加保守的方法。

因為當領導人從之前任期復制日志條目時日志條目保留了它們最開始的任期號，所以這使得 Raft 在提交規則中增加了額外的復雜性。在其他的一致性算法中，如果一個新的領導人要從之前的任期中復制日志條目，它必須要使用當前的新任期號。Raft 的方法使得判斷日志更加容易，因為它們全程都保持著同樣的任期號。另外，和其它的一致性算法相比，Raft 算法中的新領導人會發送更少的之前任期的日志條目（其他算法必須要發送冗余的日志條目并且在它們被提交之前來重新排序）。

5.4.3 安全性論證

給出了完整的 Raft 算法，現在我們能夠更精確的論證領導人完全原則（Leader Completeness)（這基于 9.2節 提出的安全性證明）。我們假定領導人完全原則是不成立的，然后推導出矛盾。假定任期 T 的領導人 leaderT在它的任期提交了一個日志條目，但是這條日志條目并沒有存儲在之后的任期中的領導人上。我們設大于 T 的最小的任期 U 的領導人（leaderU） 沒有存儲這條日志條目。

在 leaderU 選舉時一定沒有那條被提交的日志條目（領導人從來不會刪除或者覆蓋日志條目）。

leaderT 復制了這個條目到集群的大多數的服務器上。因此，只是有一臺服務器（投票者）即接收了來自 leaderT 的日志條目并且給 leaderU 投票，就像 圖-9 中所示那樣。這個投票者是產生矛盾的關鍵。

投票者必須在給 leaderU 投票之前接收來自 leaderT 的日志條目；否則它會拒絕來自 leaderT 的 AppendEntries 請求（它的當前任期會比 T 要大）。

投票者會在它給 leaderU 投票時存儲那個條目，因為任何中間的領導人都保有該條目（基于假設），領導人從來不會移除這個條目，并且追隨者也只會在和領導人沖突時才會移除日志條目。

投票者給 leaderU 投票了，所以 leaderU 的日志必須和投票者的一樣新。這就導致了一個矛盾。

首先，如果投票者和 leaderU 最后一條日志條目的任期號相同，那么 leaderU 的日志一定和投票者的一樣長，因此它的日志包含全部投票者的日志條目。這是矛盾的，因為在假設中投票者和 leaderU 包含的已提交條目是不同的。

除此之外， leaderU 的最后一條日志的任期號一定比投票者的大。另外，它也比 T 要大，因為投票者的最后一條日志條目的任期號最小也要是 T（它包含了所有任期 T 提交的日志條目）。創建 leaderU 最后一條日志條目的上一任領導人必須包含已經提交的日志條目（基于假設）。那么，根據日志匹配原則（Log Matching），leaderU 也一定包含那條提交的日志條目，這也是矛盾的。

這時就完成了矛盾推導。因此，所有比任期 T 大的領導人一定包含所有在任期 T 提交的日志條目。

日志匹配原則（Log Matching）保證了未來的領導人也會包含被間接提交的日志條目，就像 圖-8 中（d）時刻索引為2的條目。

通過給出了 領導人完全原則（Leader Completeness)，我們能夠證明 表-3 中的狀態機安全原則（State Machine Safety），狀態機安全原則（State Machine Safety）講的是如果一臺服務器將給定索引上的日志條目應用到了它自己的狀態機上，其它服務器的同一索引位置不可能應用的是其它條目。在一個服務器應用一條日志條目到它自己的狀態機中時，它的日志必須和領導人的日志在該條目和之前的條目上相同，并且已經被提交。現在我們來考慮在任何一個服務器應用一個指定索引位置的日志的最小任期；日志完全特性（Log Completeness Property）保證擁有更高任期號的領導人會存儲相同的日志條目，所以之后的任期里應用某個索引位置的日志條目也會是相同的值。因此，狀態機安全特性是成立的。

最后，Raft 算法需要服務器按照日志中索引位置順序應用日志條目。和狀態機安全特性結合起來看，這就意味著所有的服務器會應用相同的日志序列集到自己的狀態機中，并且是按照相同的順序。

5.5 追隨者和候選人崩潰

截止到目前，我們只討論了領導人崩潰的問題。追隨者和候選人崩潰的問題解決起來要比領導人崩潰要簡單得多，這兩者崩潰的處理方式是一樣的。如果一個追隨者或者候選人崩潰了，那么之后的發送給它的 RequestVote RPC 和 AppendEntries RPC 會失敗。Raft 通過無限的重試來處理這些失敗；如果崩潰的服務器重啟了，RPC 就會成功完成。如果一個服務器在收到了 RPC 之后但是在響應之前崩潰了，那么它會在重啟之后再次收到同一個 RPC。因為 Raft 中的 RPC 都是冪等的，因此不會有什么問題。例如，如果一個追隨者收到了一個已經包含在它的日志中的 AppendEntries 請求，它會忽視這個新的請求。

5.6 時序和可用性

我們對于 Raft 的要求之一就是安全性不依賴于時序（timing）：系統不能僅僅因為一些事件發生的比預想的快一些或慢一些就產生錯誤。然而，可用性（系統可以及時響應客戶端的特性）不可避免的要依賴時序。例如，如果消息交換在服務器崩潰時花費更多的時間，候選人不會等待太長的時間來贏得選舉；沒有一個穩定的領導人，Raft 將無法工作。

領導人選取是 Raft 中對時序要求最關鍵的地方。Raft 會選出并且保持一個穩定的領導人只有系統滿足下列時序要求（timing requirement）：

在這個不等式中，broadcastTime指的是一臺服務器并行的向集群中的其他服務器發送 RPC 并且收到它們的響應的平均時間；electionTimeout指的就是在 5.2節 描述的選舉超時時間；MTBF指的是單個服務器發生故障的間隔時間的平均數。broadcastTime應該比electionTimeout小一個數量級，為的是使領導人能夠持續發送心跳信息（heartbeat）來阻止追隨者們開始選舉；根據已經給出的隨機化選舉超時時間方法，這個不等式也使得瓜分選票的情況變成不可能。electionTimeout也要比MTBF小幾個數量級，為的是使得系統穩定運行。當領導人崩潰時，整個大約會在electionTimeout的時間內不可用；我們希望這種情況僅占全部時間的很小的一部分。

broadcastTime和MTBF是由系統決定的性質，但是electionTimeout是我們必須做出選擇的。Raft 的 RPC 需要接收方將信息持久化的保存到穩定存儲中去，所以廣播時間大約是 0.5 毫秒到 20 毫秒，這取決于存儲的技術。因此，electionTimeout一般在 10ms 到 500ms 之間。大多數的服務器的MTBF都在幾個月甚至更長，很容易滿足這個時序需求。

6 集群成員變化

截止到目前，我們都假定集群的配置（加入到一致性算法的服務器集合）是固定的。在實際中，我們會經常更改配置，例如，替換掉那些崩潰的機器或者更改復制級別。雖然通過關閉整個集群，升級配置文件，然后重啟整個集群也可以解決這個問題，但是這回導致在更改配置的過程中，整個集群不可用。另外，如果存在需要手工操作，那么就會有操作失誤的風險。為了避免這些問題，我們決定采用自動改變配置并且把這部分加入到了 Raft 一致性算法中。

為了讓配置修改機制能夠安全，那么在轉換的過程中在任何時間點兩個領導人不能再同一個任期被同時選為領導人。不幸的是，服務器集群從舊的配置直接升級到新的配置的任何方法都是不安全的，一次性自動的轉換所有服務器是不可能的，所以集群可以在轉換的過程中劃分成兩個單獨的組（如 圖-10 所示）。

為了保證安全性，集群配置的調整必須使用兩階段（two-phase）方法。有許多種實現兩階段方法的實現。例如，一些系統在第一個階段先把舊的配置設為無效使得它無法處理客戶端請求，然后在第二階段啟用新的配置。在 Raft 中，集群先切換到一個過渡配置，我們稱其為共同一致（joint consensus）；一旦共同一致被提交了，然后系統再切換到新的配置。共同一致是舊的配置和新的配置的組合：

日志條目被復制給集群中新、老配置的所有服務器。

新、老配置的服務器都能成為領導人。

需要分別在兩種配置上獲得大多數的支持才能達成一致（針對選舉和提交）

共同一致允許獨立的服務器在不影響安全性的前提下，在不同的時間進行配置轉換過程。此外，共同一致可以讓集群在配置轉換的過程中依然能夠響應服務器請求。

集群配置在復制日志中用特殊的日志條目來存儲和通信；圖-11 展示了配置變更的過程。當一個領導人接收到一個改變配置 Cold 為 Cnew 的請求，它會為了共同一致以前面描述的日志條目和副本的形式將配置存儲起來（圖中的 Cold,new）。一旦一個服務器將新的配置日志條目增加到它的日志中，它就會用這個配置來做出未來所有的決定（服務器總是使用最新的配置，無論它是否已經被提交）。這意味著領導人要使用 Cold,new 的規則來決定日志條目 Cold,new 什么時候需要被提交。如果領導人崩潰了，被選出來的新領導人可能是使用 Cold 配置也可能是 Cold,new 配置，這取決于贏得選舉的候選人是否已經接收到了 Cold,new 配置。在任何情況下， Cnew 配置在這一時期都不會單方面的做出決定。

一旦 Cold,new 被提交，那么無論是 Cold 還是 Cnew，在沒有經過他人批準的情況下都不可能做出決定，并且領導人完全特性（Leader Completeness Property）保證了只有擁有 Cold,new 日志條目的服務器才有可能被選舉為領導人。這個時候，領導人創建一條關于 Cnew 配置的日志條目并復制給集群就是安全的了。另外，每個服務器在收到新的配置的時候就會立即生效。當新的配置在 Cnew 的規則下被提交，舊的配置就變得無關緊要，同時不使用新的配置的服務器就可以被關閉了。如 圖-11，Cold 和 Cnew 沒有任何機會同時做出單方面的決定；這就保證了安全性。

針對重新配置提出了三個問題。第一個問題是一開始的時候新的服務器可能沒有任何日志條目。如果它們在這個狀態下加入到集群中，那么它們需要一段時間來更新追趕，在這個階段它們還不能提交新的日志條目。為了避免這種可用性的間隔時間，Raft 在配置更新的時候使用了一種額外的階段，在這個階段，新的服務器以沒有投票權的身份加入到集群中來（領導人復制日志給他們，但是不把它們考慮到大多數中）。一旦新的服務器追趕上了集群中的其它機器，重新配置可以像上面描述的一樣處理。

第二個問題是，集群的領導人可能不是新配置的一員。在這種情況下，領導人就會在提交了 Cnew 日志之后退位（回到跟隨者狀態）。這意味著有這樣的一段時間，領導人管理著集群，但是不包括自己；它復制日志但是不把它自己看作是大多數之一。當 Cnew 被提交時，會發生領導人過渡，因為這時是新的配置可以獨立工作的最早的時間點（總是能夠在 Cnew 配置下選出新的領導人）。在此之前，可能只能從 Cold 中選出領導人。

第三個問題是，移除不在 Cnew 中的服務器可能會擾亂集群。這些服務器將不會再接收到心跳（heartbeat），所以當選舉超時時，它們就會進行新的選舉過程。它們會發送帶有新的任期號的 RequestVote RPC，這樣會導致當前的領導人回退成跟隨者狀態。新的領導人最終會被選出來，但是被移除的服務器將會再次超時，然后這個過程會再次重復，導致整體可用性大幅降低。

為了避免這個問題，當服務器確認當前領導人存在時，服務器會忽略 RequestVote RPC。特別的，當服務器在當前最小選舉超時時間內收到一個 RequestVote RPC，它不會更新當前的任期號或者投出選票。這不會影響正常的選舉，每個服務器在開始一次選舉之前，至少等待一個最小選舉超時時間。然而，這有利于避免被移除的服務器擾亂：如果領導人能夠發送心跳給集群，那么它就不會被更大的任期號廢除。

7 日志壓縮

Raft 產生的日志在持續的正常操作中不斷增長，但是在實際的系統中，它不會無限的增長下去。隨著日志的不斷增長，它會占據越來越多的空間并且花費更多的時間重置。如果沒有一個機制使得它能夠廢棄在日志中不斷累積的過時的信息就會引起可用性問題。

快照（snapshot）是最簡單的壓縮方式。在快照中，全部的當前系統狀態都被寫入到快照中，存儲到持久化的存儲中，然后在那個時刻之前的全部日志都可以被丟棄。在 Chubby 和 ZooKeeper 中都使用了快照技術，這一章的剩下的部分會介紹 Raft 中使用的快照技術。

增量壓縮（incremental approaches）的方法，例如日志清理（log cleaning）或者日志結構合并樹（log-structured merge trees），都是可行的。這些方法每次只對一小部分數據進行操作，這樣就分散了壓縮的負載壓力。首先，他們先選擇一個已經積累的大量已經被刪除或者被覆蓋對象的區域，然后重寫那個區域還活躍的對象，之后釋放那個區域。和簡單操作整個數據集合的快照相比，需要增加復雜的機制來實現。狀態機可以使用和快照相同的接口來實現 LSM tree ，但是日志清除方法就需要修改 Raft 了。

圖-12 展示了 Raft 中快照的基礎思想。每個服務器獨立的創建快照，只包括已經被提交的日志。主要的工作包括將狀態機的狀態寫入到快照中。Raft 也將一些少量的元數據包含到快照中：最后被包含的索引（last included index）指的是被快照取代的最后的條目在日志中的索引值（狀態機最后應用的日志），最后被包含的任期（last included term）指的是該條目的任期號。保留這些數據是為了支持快照前的第一個條目的附加日志請求時的一致性檢查，因為這個條目需要最后的索引值和任期號。為了支持集群成員更新（第 6 章），快照中也將最后的一次配置作為最后一個條目存下來。一旦服務器完成一次快照，他就可以刪除最后索引位置之前的所有日志和快照了。

盡管通常服務器都是獨立的創建快照，但是領導人必須偶爾的發送快照給一些落后的跟隨者。這通常發生在當領導人已經丟棄了下一條需要發送給跟隨者的日志條目的時候。幸運的是這種情況不是常規操作：一個與領導人保持同步的跟隨者通常都會有這個條目。然而一個運行非常緩慢的跟隨者或者新加入集群的服務器（第 6 章）將不會有這個條目。這時讓這個跟隨者更新到最新的狀態的方式就是通過網絡把快照發送給它們。

安裝快照 RPC（InstallSnapshot RPC）

在領導人發送快照給跟隨者時使用調用。領導人總是按順序發送。

接受者需要實現：

如果term < currentTerm立刻回復

如果是第一個分塊（offset 為 0）則創建新的快照

在指定的偏移量寫入數據

如果 done為 false，則回復并繼續等待之后的數據

保存快照文件，丟棄所有存在的或者部分有著更小索引號的快照

如果現存的日志擁有相同的最后任期號和索引值，則后面的數據繼續保留并且回復

丟棄全部日志

能夠使用快照來恢復狀態機（并且裝載快照中的集群配置）

在這種情況下領導人使用一種叫做安裝快照（InstallSnapshot）的新的 RPC 來發送快照給太落后的跟隨者；見 表-13。當跟隨者通過這種 RPC 接收到快照時，它必須自己決定對于已經存在的日志該如何處理。通常快照會包含沒有在接收者日志中存在的信息。在這種情況下，跟隨者直接丟棄它所有的日志；這些會被快照所取代，但是可能會和沒有提交的日志產生沖突。如果接收到的快照是自己日志的前面部分（由于網絡重傳或者錯誤），那么被快照包含的條目將會被全部刪除，但是快照之后的條目必須是正確的和并且被保留下來。

這種快照的方式背離了 Raft 的強領導人原則（strong leader principle），因為跟隨者可以在不知道領導人情況下創建快照。但是我們認為這種背離是值得的。領導人的存在，是為了解決在達成一致性的時候的沖突，但是在創建快照的時候，一致性已經達成，這時不存在沖突了，所以沒有領導人也是可以的。數據依然是從領導人傳給跟隨者，只是跟隨者可以重新組織它們的數據了。

我們考慮過一種替代的基于領導人的快照方案，即只有領導人創建快照，然后發送給所有的跟隨者。但是這樣做有兩個缺點。第一，發送快照會浪費網絡帶寬并且延緩了快照處理的時間。每個跟隨者都已經擁有了所有產生快照需要的信息，而且很顯然，自己從本地的狀態中創建快照比通過網絡接收別人發來的要經濟。第二，領導人的實現會更加復雜。例如，領導人需要發送快照的同時并行的將新的日志條目發送給跟隨者，這樣才不會阻塞新的客戶端請求。

還有兩個問題影響了快照的性能。首先，服務器必須決定什么時候應該創建快照。如果快照創建的過于頻繁，那么就會浪費大量的磁盤帶寬和其他資源；如果創建快照頻率太低，它就要承受耗盡存儲容量的風險，同時也增加了從日志重建的時間。一個簡單的策略就是當日志大小達到一個固定大小的時候就創建一次快照。如果這個閾值設置的顯著大于期望的快照的大小，那么快照對磁盤壓力的影響就會很小了。

第二個影響性能的問題就是寫入快照需要花費顯著的一段時間，并且我們還不希望影響到正常操作。解決方案是通過寫時復制（copy-on-write）的技術，這樣新的更新就可以被接收而不影響到快照。例如，具有函數式數據結構的狀態機天然支持這樣的功能。另外，操作系統的寫時復制技術的支持（如 Linux 上的 fork）可以被用來創建完整的狀態機的內存快照（我們的實現就是這樣的）。

8 客戶端交互

這一節將介紹客戶端是如何和 Raft 進行交互的，包括客戶端是如何發現領導人的和 Raft 是如何支持線性化語義（linearizable semantics）的。這些問題對于所有基于一致性的系統都存在，并且 Raft 的解決方案和其他的也差不多。

Raft 中的客戶端將所有請求發送給領導人。當客戶端啟動的時候，它會隨機挑選一個服務器進行通信。如果客戶端第一次挑選的服務器不是領導人，那么那個服務器會拒絕客戶端的請求并且提供它最近接收到的領導人的信息（附加條目請求包含了領導人的網絡地址）。如果領導人已經崩潰了，那么客戶端的請求就會超時；客戶端之后會再次重試隨機挑選服務器的過程。

我們 Raft 的目標是要實現線性化語義（linearizable semantics）（每一次操作立即執行，在它調用和收到回復之間只執行一次）。但是，如上述所說，Raft 是可以多次執行同一條命令的：例如，如果領導人在提交了這條日志之后，但是在響應客戶端之前崩潰了，那么客戶端會和新的領導人重試這條指令，導致這條命令就被再次執行了。解決方案就是客戶端對于每一條指令都賦予一個唯一的序列號。然后，狀態機跟蹤每條指令最新的序列號和相應的響應。如果接收到一條指令，它的序列號已經被執行了，那么就立即返回結果，而不重新執行指令。

只讀（read-only）的操作可以直接處理而不需要記錄日志。但是，在不增加任何限制的情況下，這么做可能會冒著返回過期數據(stale data)的風險，因為領導人響應客戶端請求時可能已經被新的領導人作廢了，但是它還不知道。線性化的讀操作必須不能返回過期數據，Raft 需要使用兩個額外的措施在不使用日志的情況下保證這一點。首先，領導人必須有關于被提交日志的最新信息。領導人完全原則（Leader Completeness Property）保證了領導人一定擁有所有已經被提交的日志條目，但是在它任期開始的時候，它可能不知道哪些是已經被提交的。為了知道這些信息，它需要在它的任期里提交一條日志條目。Raft 中通過領導人在任期開始的時候提交一個空白的沒有任何操作的日志條目到日志中去來進行實現。第二，領導人在處理只讀的請求之前必須檢查自己是否已經被廢除了（如果一個更新的領導人被選舉出來，它自己的信息就已經過期了）。Raft 中通過讓領導人在響應只讀請求之前，先和集群中的大多數節點交換一次心跳（heartbeat）信息來處理這個問題。另外，領導人可以依賴心跳機制來實現一種租約的機制，但是這種方法依賴時序來保證安全性（它假設時間誤差是有界的）。

AI 機器翻譯

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