RAFT(一種分散式一致性算法):簡述,具體內容,一致性算法,

Raft是一種更為簡單方便易於理解的分散式算法，主要解決了分散式中的一致性問題。相比傳統的Paxos算法，Raft將大量的計算問題分解成為了一些簡單的相對獨立的子問題。

簡述,具體內容,一致性算法,

簡述

相比於傳統的一致性算法Paxos，Raft有一些自己的獨特的特性。比如增加了強領導性，最佳化了領導的選舉過程，在成員發生變化之後依然能夠很好的進行工作。

以下是文章部分內容的翻譯，來自Github。由於字數限制只摘取了算法的核心部分。建議閱讀原文。

尋找一種易於理解的一致性算法（擴展版）

具體內容

一致性算法允許一組機器像一個整體一樣工作，即使其中一些機器出現故障也能夠繼續工作下去。正因為如此，一致性算法在構建可信賴的大規模軟體系統中扮演著重要的角色。在過去的 10 年裡，Paxos 算法統治著一致性算法這一領域：絕大多數的實現都是基於 Paxos 或者受其影響。同時 Paxos 也成為了教學領域裡講解一致性問題時的示例。

但是不幸的是，儘管有很多工作都在嘗試降低它的複雜性，但是 Paxos 算法依然十分難以理解。並且，Paxos 自身的算法結構需要進行大幅的修改才能夠套用到實際的系統中。這些都導致了工業界和學術界都對 Paxos 算法感到十分頭疼。

和 Paxos 算法進行過努力之後，我們開始尋找一種新的一致性算法，可以為構建實際的系統和教學提供更好的基礎。我們的做法是不尋常的，我們的首要目標是可理解性：我們是否可以在實際系統中定義一個一致性算法，並且能夠比 Paxos 算法以一種更加容易的方式來學習。此外，我們希望該算法方便系統構建者的直覺的發展。不僅一個算法能夠工作很重要，而且能夠顯而易見的知道為什麼能工作也很重要。

Raft 一致性算法就是這些工作的結果。在設計 Raft 算法的時候，我們使用一些特別的技巧來提升它的可理解性，包括算法分解（Raft 主要被分成了領導人選舉，日誌複製和安全三個模組）和減少狀態機的狀態（相對於 Paxos，Raft 減少了非確定性和伺服器互相處於非一致性的方式）。一份針對兩所大學 43 個學生的研究表明 Raft 明顯比 Paxos 算法更加容易理解。在這些學生同時學習了這兩種算法之後，和 Paxos 比起來，其中 33 個學生能夠回答有關於 Raft 的問題。

Raft 算法在許多方面和現有的一致性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是它也有一些獨特的特性：

強領導者：和其他一致性算法相比，Raft 使用一種更強的領導能力形式。比如，日誌條目只從領導者傳送給其他的伺服器。這種方式簡化了對複製日誌的管理並且使得 Raft 算法更加易於理解。
領導選舉：Raft 算法使用一個隨機計時器來選舉領導者。這種方式只是在任何一致性算法都必須實現的心跳機制上增加了一點機制。在解決衝突的時候會更加簡單快捷。
成員關係調整：Raft 使用一種共同一致的方法來處理集群成員變換的問題，在這種方法下，處於調整過程中的兩種不同的配置集群中大多數機器會有重疊，這就使得集群在成員變換的時候依然可以繼續工作。

我們相信，Raft 算法不論出於教學目的還是作為實踐項目的基礎都是要比 Paxos 或者其他一致性算法要優異的。它比其他算法更加簡單，更加容易理解；它的算法描述足以實現一個現實的系統；它有好多開源的實現並且在很多公司里使用；它的安全性已經被證明；它的效率和其他算法比起來也不相上下。

接下來，這篇論文會介紹以下內容：複製狀態機問題（第 2 節），討論 Paxos 的優點和缺點（第 3 節），討論我們為了理解能力而使用的方法（第 4 節），闡述 Raft 一致性算法（第 5-8 節），評價 Raft 算法（第 9 節），以及一些相關的工作（第 10 節）。

一致性算法

Raft 是一種用來管理章節 2 中描述的複製日誌的算法。圖 2 為了參考之用，總結這個算法的簡略版本，圖 3 列舉了這個算法的一些關鍵特性。圖中的這些元素會在剩下的章節逐一介紹。

Raft 通過選舉一個高貴的領導人，然後給予他全部的管理複製日誌的責任來實現一致性。領導人從客戶端接收日誌條目，把日誌條目複製到其他伺服器上，並且當保證安全性的時候告訴其他的伺服器套用日誌條目到他們的狀態機中。擁有一個領導人大大簡化了對複製日誌的管理。例如，領導人可以決定新的日誌條目需要放在日誌中的什麼位置而不需要和其他伺服器商議，並且數據都從領導人流向其他伺服器。一個領導人可以宕機，可以和其他伺服器失去連線，這時一個新的領導人會被選舉出來。

通過領導人的方式，Raft 將一致性問題分解成了三個相對獨立的子問題，這些問題會在接下來的子章節中進行討論：

領導選舉：一個新的領導人需要被選舉出來，當現存的領導人宕機的時候（章節 5.2）
日誌複製：領導人必須從客戶端接收日誌然後複製到集群中的其他節點，並且強制要求其他節點的日誌保持和自己相同。
安全性：在 Raft 中安全性的關鍵是在圖 3 中展示的狀態機安全：如果有任何的伺服器節點已經套用了一個確定的日誌條目到它的狀態機中，那么其他伺服器節點不能在同一個日誌索引位置套用一個不同的指令。章節 5.4 闡述了 Raft 算法是如何保證這個特性的；這個解決方案涉及到一個額外的選舉機制（5.2 節）上的限制。

在展示一致性算法之後，這一章節會討論可用性的一些問題和系統中的候選人角色的問題。

狀態：

狀態	所有伺服器上持久存在的
currentTerm	伺服器最後一次知道的任期號（初始化為 0，持續遞增）
votedFor	在當前獲得選票的候選人的 Id
log[]	日誌條目集；每一個條目包含一個用戶狀態機執行的指令，和收到時的任期號

狀態	所有伺服器上經常變的
commitIndex	已知的最大的已經被提交的日誌條目的索引值
lastApplied	最後被套用到狀態機的日誌條目索引值（初始化為 0，持續遞增）

狀態	在領導人里經常改變的（選舉後重新初始化）
nextIndex[]	對於每一個伺服器，需要傳送給他的下一個日誌條目的索引值（初始化為領導人最後索引值加一）
matchIndex[]	對於每一個伺服器，已經複製給他的日誌的最高索引值

附加日誌 RPC：

由領導人負責調用來複製日誌指令；也會用作heartbeat

參數	解釋
term	領導人的任期號
leaderId	領導人的 Id，以便於跟隨者重定向請求
prevLogIndex	新的日誌條目緊隨之前的索引值
prevLogTerm	prevLogIndex 條目的任期號
entries[]	準備存儲的日誌條目（表示心跳時為空；一次性傳送多個是為了提高效率）
leaderCommit	領導人已經提交的日誌的索引值

返回值	解釋
term	當前的任期號，用於領導人去更新自己
success	跟隨者包含了匹配上 prevLogIndex 和 prevLogTerm 的日誌時為真

接收者實現：

如果term < currentTerm就返回 false （5.1 節）
如果日誌在 prevLogIndex 位置處的日誌條目的任期號和 prevLogTerm 不匹配，則返回 false （5.3 節）
如果已經存在的日誌條目和新的產生衝突（索引值相同但是任期號不同），刪除這一條和之後所有的（5.3 節）
附加任何在已有的日誌中不存在的條目
如果leaderCommit > commitIndex，令 commitIndex 等於 leaderCommit 和新日誌條目索引值中較小的一個

請求投票 RPC：

由候選人負責調用用來徵集選票（5.2 節）

參數	解釋
term	候選人的任期號
candidateId	請求選票的候選人的 Id
lastLogIndex	候選人的最後日誌條目的索引值
lastLogTerm	候選人最後日誌條目的任期號

返回值	解釋
term	當前任期號，以便於候選人去更新自己的任期號
voteGranted	候選人贏得了此張選票時為真

接收者實現：

如果term < currentTerm返回 false （5.2 節）
如果 votedFor 為空或者就是 candidateId，並且候選人的日誌至少和自己一樣新，那么就投票給他（5.2 節，5.4 節）

所有伺服器需遵守的規則：

所有伺服器：

如果commitIndex > lastApplied，那么就 lastApplied 加一，並把log[lastApplied]套用到狀態機中（5.3 節）
如果接收到的 RPC 請求或回響中，任期號T > currentTerm，那么就令 currentTerm 等於 T，並切換狀態為跟隨者（5.1 節）

跟隨者（5.2 節）：

回響來自候選人和領導者的請求
如果在超過選舉逾時時間的情況之前都沒有收到領導人的心跳，或者是候選人請求投票的，就自己變成候選人

候選人（5.2 節）：

在轉變成候選人後就立即開始選舉過程
自增當前的任期號（currentTerm）
給自己投票
重置選舉逾時計時器
傳送請求投票的 RPC 給其他所有伺服器

如果接收到大多數伺服器的選票，那么就變成領導人

如果接收到來自新的領導人的附加日誌 RPC，轉變成跟隨者

如果選舉過程逾時，再次發起一輪選舉

領導人：

一旦成為領導人：傳送空的附加日誌 RPC（心跳）給其他所有的伺服器；在一定的空餘時間之後不停的重複傳送，以阻止跟隨者逾時（5.2 節）
如果接收到來自客戶端的請求：附加條目到本地日誌中，在條目被套用到狀態機後回響客戶端（5.3 節）
如果對於一個跟隨者，最後日誌條目的索引值大於等於 nextIndex，那么：傳送從 nextIndex 開始的所有日誌條目：
如果成功：更新相應跟隨者的 nextIndex 和 matchIndex
如果因為日誌不一致而失敗，減少 nextIndex 重試

如果存在一個滿足N > commitIndex的 N，並且大多數的matchIndex[i] ≥ N成立，並且log[N].term == currentTerm成立，那么令 commitIndex 等於這個 N （5.3 和 5.4 節）

圖 2：一個關於 Raft 一致性算法的濃縮總結（不包括成員變換和日誌壓縮）。

特性	解釋
選舉安全特性	對於一個給定的任期號，最多只會有一個領導人被選舉出來（5.2 節）
領導人只附加原則	領導人絕對不會刪除或者覆蓋自己的日誌，只會增加（5.3 節）
日誌匹配原則	如果兩個日誌在相同的索引位置的日誌條目的任期號相同，那么我們就認為這個日誌從頭到這個索引位置之間全部完全相同（5.3 節）
領導人完全特性	如果某個日誌條目在某個任期號中已經被提交，那么這個條目必然出現在更大任期號的所有領導人中（5.4 節）
狀態機安全特性	如果一個領導人已經在給定的索引值位置的日誌條目套用到狀態機中，那么其他任何的伺服器在這個索引位置不會提交一個不同的日誌（5.4.3 節）

圖 3：Raft 在任何時候都保證以上的各個特性。

5.1 Raft 基礎

一個 Raft 集群包含若干個伺服器節點；通常是 5 個，這允許整個系統容忍 2 個節點的失效。在任何時刻，每一個伺服器節點都處於這三個狀態之一：領導人、跟隨者或者候選人。在通常情況下，系統中只有一個領導人並且其他的節點全部都是跟隨者。跟隨者都是被動的：他們不會傳送任何請求，只是簡單的回響來自領導者或者候選人的請求。領導人處理所有的客戶端請求（如果一個客戶端和跟隨者聯繫，那么跟隨者會把請求重定向給領導人）。第三種狀態，候選人，是用來在 5.2 節描述的選舉新領導人時使用。圖 4 展示了這些狀態和他們之間的轉換關係；這些轉換關係會在接下來進行討論。

圖 4：伺服器狀態。跟隨者只回響來自其他伺服器的請求。如果跟隨者接收不到訊息，那么他就會變成候選人並發起一次選舉。獲得集群中大多數選票的候選人將成為領導者。在一個任期內，領導人一直都會是領導人直到自己宕機了。

圖 5：時間被劃分成一個個的任期，每個任期開始都是一次選舉。在選舉成功後，領導人會管理整個集群直到任期結束。有時候選舉會失敗，那么這個任期就會沒有領導人而結束。任期之間的切換可以在不同的時間不同的伺服器上觀察到。

Raft 把時間分割成任意長度的任期，如圖 5。任期用連續的整數標記。每一段任期從一次選舉開始，就像章節 5.2 描述的一樣，一個或者多個候選人嘗試成為領導者。如果一個候選人贏得選舉，然後他就在接下來的任期內充當領導人的職責。在某些情況下，一次選舉過程會造成選票的瓜分。在這種情況下，這一任期會以沒有領導人結束；一個新的任期（和一次新的選舉）會很快重新開始。Raft 保證了在一個給定的任期內，最多只有一個領導者。

不同的伺服器節點可能多次觀察到任期之間的轉換，但在某些情況下，一個節點也可能觀察不到任何一次選舉或者整個任期全程。任期在 Raft 算法中充當邏輯時鐘的作用，這會允許伺服器節點查明一些過期的信息比如陳舊的領導者。每一個節點存儲一個當前任期號，這一編號在整個時期內單調的增長。當伺服器之間通信的時候會交換當前任期號；如果一個伺服器的當前任期號比其他人小，那么他會更新自己的編號到較大的編號值。如果一個候選人或者領導者發現自己的任期號過期了，那么他會立即恢復成跟隨者狀態。如果一個節點接收到一個包含過期的任期號的請求，那么他會直接拒絕這個請求。

Raft 算法中伺服器節點之間通信使用遠程過程調用（RPCs），並且基本的一致性算法只需要兩種類型的 RPCs。請求投票（RequestVote） RPCs 由候選人在選舉期間發起（章節 5.2），然後附加條目（AppendEntries）RPCs 由領導人發起，用來複製日誌和提供一種心跳機制（章節 5.3）。第 7 節為了在伺服器之間傳輸快照增加了第三種 RPC。當伺服器沒有及時的收到 RPC 的回響時，會進行重試，並且他們能夠並行的發起 RPCs 來獲得最佳的性能。

5.2 領導人選舉

Raft 使用一種心跳機制來觸發領導人選舉。當伺服器程式啟動時，他們都是跟隨者身份。一個伺服器節點繼續保持著跟隨者狀態只要他從領導人或者候選者處接收到有效的 RPCs。領導者周期性的向所有跟隨者傳送心跳包（即不包含日誌項內容的附加日誌項 RPCs）來維持自己的權威。如果一個跟隨者在一段時間裡沒有接收到任何訊息，也就是選舉逾時，那么他就會認為系統中沒有可用的領導者,並且發起選舉以選出新的領導者。

要開始一次選舉過程，跟隨者先要增加自己的當前任期號並且轉換到候選人狀態。然後他會並行的向集群中的其他伺服器節點傳送請求投票的 RPCs 來給自己投票。候選人會繼續保持著當前狀態直到以下三件事情之一發生：(a) 他自己贏得了這次的選舉，(b) 其他的伺服器成為領導者，(c) 一段時間之後沒有任何一個獲勝的人。這些結果會分別的在下面的段落里進行討論。

當一個候選人從整個集群的大多數伺服器節點獲得了針對同一個任期號的選票，那么他就贏得了這次選舉並成為領導人。每一個伺服器最多會對一個任期號投出一張選票，按照先來先服務的原則（注意：5.4 節在投票上增加了一點額外的限制）。要求大多數選票的規則確保了最多只會有一個候選人贏得此次選舉（圖 3 中的選舉安全性）。一旦候選人贏得選舉，他就立即成為領導人。然後他會向其他的伺服器傳送心跳訊息來建立自己的權威並且阻止新的領導人的產生。

在等待投票的時候，候選人可能會從其他的伺服器接收到聲明它是領導人的附加日誌項 RPC。如果這個領導人的任期號（包含在此次的 RPC中）不小於候選人當前的任期號，那么候選人會承認領導人合法並回到跟隨者狀態。如果此次 RPC 中的任期號比自己小，那么候選人就會拒絕這次的 RPC 並且繼續保持候選人狀態。

第三種可能的結果是候選人既沒有贏得選舉也沒有輸：如果有多個跟隨者同時成為候選人，那么選票可能會被瓜分以至於沒有候選人可以贏得大多數人的支持。當這種情況發生的時候，每一個候選人都會逾時，然後通過增加當前任期號來開始一輪新的選舉。然而，沒有其他機制的話，選票可能會被無限的重複瓜分。

Raft 算法使用隨機選舉逾時時間的方法來確保很少會發生選票瓜分的情況，就算發生也能很快的解決。為了阻止選票起初就被瓜分，選舉逾時時間是從一個固定的區間（例如 150-300 毫秒）隨機選擇。這樣可以把伺服器都分散開以至於在大多數情況下只有一個伺服器會選舉逾時；然後他贏得選舉並在其他伺服器逾時之前傳送心跳包。同樣的機制被用在選票瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個隨機的選舉逾時時間，然後在逾時時間內等待投票的結果；這樣減少了在新的選舉中另外的選票瓜分的可能性。9.3 節展示了這種方案能夠快速的選出一個領導人。

領導人選舉這個例子，體現了可理解性原則是如何指導我們進行方案設計的。起初我們計畫使用一種排名系統：每一個候選人都被賦予一個唯一的排名，供候選人之間競爭時進行選擇。如果一個候選人發現另一個候選人擁有更高的排名，那么他就會回到跟隨者狀態，這樣高排名的候選人能夠更加容易的贏得下一次選舉。但是我們發現這種方法在可用性方面會有一點問題（如果高排名的伺服器宕機了，那么低排名的伺服器可能會逾時並再次進入候選人狀態。而且如果這個行為發生得足夠快，則可能會導致整個選舉過程都被重置掉）。我們針對算法進行了多次調整，但是每次調整之後都會有新的問題。最終我們認為隨機重試的方法是更加明顯和易於理解的。

5.3 日誌複製

一旦一個領導人被選舉出來，他就開始為客戶端提供服務。客戶端的每一個請求都包含一條被複製狀態機執行的指令。領導人把這條指令作為一條新的日誌條目附加到日誌中去，然後並行的發起附加條目 RPCs 給其他的伺服器，讓他們複製這條日誌條目。當這條日誌條目被安全的複製（下面會介紹），領導人會套用這條日誌條目到它的狀態機中然後把執行的結果返回給客戶端。如果跟隨者崩潰或者運行緩慢，再或者網路丟包，領導人會不斷的重複嘗試附加日誌條目 RPCs （儘管已經回復了客戶端）直到所有的跟隨者都最終存儲了所有的日誌條目。

圖 6：日誌由有序序號標記的條目組成。每個條目都包含創建時的任期號（圖中框中的數字），和一個狀態機需要執行的指令。一個條目當可以安全的被套用到狀態機中去的時候，就認為是可以提交了。

日誌以圖 6 展示的方式組織。每一個日誌條目存儲一條狀態機指令和從領導人收到這條指令時的任期號。日誌中的任期號用來檢查是否出現不一致的情況，同時也用來保證圖 3 中的某些性質。每一條日誌條目同時也都有一個整數索引值來表明它在日誌中的位置。

領導人來決定什麼時候把日誌條目套用到狀態機中是安全的；這種日誌條目被稱為已提交。Raft 算法保證所有已提交的日誌條目都是持久化的並且最終會被所有可用的狀態機執行。在領導人將創建的日誌條目複製到大多數的伺服器上的時候，日誌條目就會被提交（例如在圖 6 中的條目 7）。同時，領導人的日誌中之前的所有日誌條目也都會被提交，包括由其他領導人創建的條目。5.4 節會討論某些當在領導人改變之後套用這條規則的隱晦內容，同時他也展示了這種提交的定義是安全的。領導人跟蹤了最大的將會被提交的日誌項的索引，並且索引值會被包含在未來的所有附加日誌 RPCs （包括心跳包），這樣其他的伺服器才能最終知道領導人的提交位置。一旦跟隨者知道一條日誌條目已經被提交，那么他也會將這個日誌條目套用到本地的狀態機中（按照日誌的順序）。

我們設計了 Raft 的日誌機制來維護一個不同伺服器的日誌之間的高層次的一致性。這么做不僅簡化了系統的行為也使得更加可預計，同時他也是安全性保證的一個重要組件。Raft 維護著以下的特性，這些同時也組成了圖 3 中的日誌匹配特性：

如果在不同的日誌中的兩個條目擁有相同的索引和任期號，那么他們存儲了相同的指令。
如果在不同的日誌中的兩個條目擁有相同的索引和任期號，那么他們之前的所有日誌條目也全部相同。

第一個特性來自這樣的一個事實，領導人最多在一個任期里在指定的一個日誌索引位置創建一條日誌條目，同時日誌條目在日誌中的位置也從來不會改變。第二個特性由附加日誌 RPC 的一個簡單的一致性檢查所保證。在傳送附加日誌 RPC 的時候，領導人會把新的日誌條目緊接著之前的條目的索引位置和任期號包含在裡面。如果跟隨者在它的日誌中找不到包含相同索引位置和任期號的條目，那么他就會拒絕接收新的日誌條目。一致性檢查就像一個歸納步驟：一開始空的日誌狀態肯定是滿足日誌匹配特性的，然後一致性檢查保護了日誌匹配特性當日誌擴展的時候。因此，每當附加日誌 RPC 返回成功時，領導人就知道跟隨者的日誌一定是和自己相同的了。

在正常的操作中，領導人和跟隨者的日誌保持一致性，所以附加日誌 RPC 的一致性檢查從來不會失敗。然而，領導人崩潰的情況會使得日誌處於不一致的狀態（老的領導人可能還沒有完全複製所有的日誌條目）。這種不一致問題會在領導人和跟隨者的一系列崩潰下加劇。圖 7 展示了跟隨者的日誌可能和新的領導人不同的方式。跟隨者可能會丟失一些在新的領導人中有的日誌條目，他也可能擁有一些領導人沒有的日誌條目，或者兩者都發生。丟失或者多出日誌條目可能會持續多個任期。

圖 7：當一個領導人成功當選時，跟隨者可能是任何情況（a-f）。每一個盒子表示是一個日誌條目；裡面的數字表示任期號。跟隨者可能會缺少一些日誌條目（a-b），可能會有一些未被提交的日誌條目（c-d），或者兩種情況都存在（e-f）。例如，場景 f 可能會這樣發生，某伺服器在任期 2 的時候是領導人，已附加了一些日誌條目到自己的日誌中，但在提交之前就崩潰了；很快這個機器就被重啟了，在任期 3 重新被選為領導人，並且又增加了一些日誌條目到自己的日誌中；在任期 2 和任期 3 的日誌被提交之前，這個伺服器又宕機了，並且在接下來的幾個任期里一直處於宕機狀態。

在 Raft 算法中，領導人處理不一致是通過強制跟隨者直接複製自己的日誌來解決了。這意味著在跟隨者中的衝突的日誌條目會被領導人的日誌覆蓋。5.4 節會闡述如何通過增加一些限制來使得這樣的操作是安全的。

要使得跟隨者的日誌進入和自己一致的狀態，領導人必須找到最後兩者達成一致的地方，然後刪除從那個點之後的所有日誌條目，傳送自己的日誌給跟隨者。所有的這些操作都在進行附加日誌 RPCs 的一致性檢查時完成。領導人針對每一個跟隨者維護了一個nextIndex，這表示下一個需要傳送給跟隨者的日誌條目的索引地址。當一個領導人剛獲得權力的時候，他初始化所有的 nextIndex 值為自己的最後一條日誌的index加1（圖 7 中的 11）。如果一個跟隨者的日誌和領導人不一致，那么在下一次的附加日誌 RPC 時的一致性檢查就會失敗。在被跟隨者拒絕之後，領導人就會減小 nextIndex 值並進行重試。最終 nextIndex 會在某個位置使得領導人和跟隨者的日誌達成一致。當這種情況發生，附加日誌 RPC 就會成功，這時就會把跟隨者衝突的日誌條目全部刪除並且加上領導人的日誌。一旦附加日誌 RPC 成功，那么跟隨者的日誌就會和領導人保持一致，並且在接下來的任期里一直繼續保持。

如果需要的話，算法可以通過減少被拒絕的附加日誌 RPCs 的次數來最佳化。例如，當附加日誌 RPC 的請求被拒絕的時候，跟隨者可以包含衝突的條目的任期號和自己存儲的那個任期的最早的索引地址。藉助這些信息，領導人可以減小 nextIndex 越過所有那個任期衝突的所有日誌條目；這樣就變成每個任期需要一次附加條目 RPC 而不是每個條目一次。在實踐中，我們十分懷疑這種最佳化是否是必要的，因為失敗是很少發生的並且也不大可能會有這么多不一致的日誌。

通過這種機制，領導人在獲得權力的時候就不需要任何特殊的操作來恢復一致性。他只需要進行正常的操作，然後日誌就能自動的在回復附加日誌 RPC 的一致性檢查失敗的時候自動趨於一致。領導人從來不會覆蓋或者刪除自己的日誌（圖 3 的領導人只附加特性）。

日誌複製機制展示出了第 2 節中形容的一致性特性：Raft 能夠接受，複製並套用新的日誌條目只要大部分的機器是工作的；在通常的情況下，新的日誌條目可以在一次 RPC 中被複製給集群中的大多數機器；並且單個的緩慢的跟隨者不會影響整體的性能。

5.4 安全性

前面的章節里描述了 Raft 算法是如何選舉和複製日誌的。然而，到目前為止描述的機制並不能充分的保證每一個狀態機會按照相同的順序執行相同的指令。例如，一個跟隨者可能會進入不可用狀態同時領導人已經提交了若干的日誌條目，然後這個跟隨者可能會被選舉為領導人並且覆蓋這些日誌條目；因此，不同的狀態機可能會執行不同的指令序列。

這一節通過在領導選舉的時候增加一些限制來完善 Raft 算法。這一限制保證了任何的領導人對於給定的任期號，都擁有了之前任期的所有被提交的日誌條目（圖 3 中的領導人完整特性）。增加這一選舉時的限制，我們對於提交時的規則也更加清晰。最終，我們將展示對於領導人完整特性的簡要證明，並且說明領導人是如何領導複製狀態機的做出正確行為的。

5.4.1 選舉限制

在任何基於領導人的一致性算法中，領導人都必須存儲所有已經提交的日誌條目。在某些一致性算法中，例如 Viewstamped Replication，某個節點即使是一開始並沒有包含所有已經提交的日誌條目，它也能被選為領導者。這些算法都包含一些額外的機制來識別丟失的日誌條目並把他們傳送給新的領導人，要么是在選舉階段要么在之後很快進行。不幸的是，這種方法會導致相當大的額外的機制和複雜性。Raft 使用了一種更加簡單的方法，它可以保證所有之前的任期號中已經提交的日誌條目在選舉的時候都會出現在新的領導人中，不需要傳送這些日誌條目給領導人。這意味著日誌條目的傳送是單向的，只從領導人傳給跟隨者，並且領導人從不會覆蓋自身本地日誌中已經存在的條目。

Raft 使用投票的方式來阻止一個候選人贏得選舉除非這個候選人包含了所有已經提交的日誌條目。候選人為了贏得選舉必須聯繫集群中的大部分節點，這意味著每一個已經提交的日誌條目在這些伺服器節點中肯定存在於至少一個節點上。如果候選人的日誌至少和大多數的伺服器節點一樣新（這個新的定義會在下面討論），那么他一定持有了所有已經提交的日誌條目。請求投票 RPC 實現了這樣的限制： RPC 中包含了候選人的日誌信息，然後投票人會拒絕掉那些日誌沒有自己新的投票請求。

Raft 通過比較兩份日誌中最後一條日誌條目的索引值和任期號定義誰的日誌比較新。如果兩份日誌最後的條目的任期號不同，那么任期號大的日誌更加新。如果兩份日誌最後的條目任期號相同，那么日誌比較長的那個就更加新。

5.4.2 提交之前任期內的日誌條目

如同 5.3 節介紹的那樣，領導人知道一條當前任期內的日誌記錄是可以被提交的，只要它被存儲到了大多數的伺服器上。如果一個領導人在提交日誌條目之前崩潰了，未來後續的領導人會繼續嘗試複製這條日誌記錄。然而，一個領導人不能斷定一個之前任期里的日誌條目被保存到大多數伺服器上的時候就一定已經提交了。圖 8 展示了一種情況，一條已經被存儲到大多數節點上的老日誌條目，也依然有可能會被未來的領導人覆蓋掉。

圖 8：如圖的時間序列展示了為什麼領導人無法決定對老任期號的日誌條目進行提交。在 (a) 中，S1 是領導者，部分的複製了索引位置 2 的日誌條目。在 (b) 中，S1 崩潰了，然後 S5 在任期 3 里通過 S3、S4 和自己的選票贏得選舉，然後從客戶端接收了一條不一樣的日誌條目放在了索引 2 處。然後到 (c)，S5 又崩潰了；S1 重新啟動，選舉成功，開始複製日誌。在這時，來自任期 2 的那條日誌已經被複製到了集群中的大多數機器上，但是還沒有被提交。如果 S1 在 (d) 中又崩潰了，S5 可以重新被選舉成功（通過來自 S2，S3 和 S4 的選票），然後覆蓋了他們在索引 2 處的日誌。反之，如果在崩潰之前，S1 把自己主導的新任期里產生的日誌條目複製到了大多數機器上，就如 (e) 中那樣，那么在後面任期裡面這些新的日誌條目就會被提交（因為S5 就不可能選舉成功）。這樣在同一時刻就同時保證了，之前的所有老的日誌條目就會被提交。

為了消除圖 8 里描述的情況，Raft 永遠不會通過計算副本數目的方式去提交一個之前任期內的日誌條目。只有領導人當前任期里的日誌條目通過計算副本數目可以被提交；一旦當前任期的日誌條目以這種方式被提交，那么由於日誌匹配特性，之前的日誌條目也都會被間接的提交。在某些情況下，領導人可以安全的知道一個老的日誌條目是否已經被提交（例如，該條目是否存儲到所有伺服器上），但是 Raft 為了簡化問題使用一種更加保守的方法。

當領導人複製之前任期里的日誌時，Raft 會為所有日誌保留原始的任期號, 這在提交規則上產生了額外的複雜性。在其他的一致性算法中，如果一個新的領導人要重新複製之前的任期里的日誌時，它必須使用當前新的任期號。Raft 使用的方法更加容易辨別出日誌，因為它可以隨著時間和日誌的變化對日誌維護著同一個任期編號。另外，和其他的算法相比，Raft 中的新領導人只需要傳送更少日誌條目（其他算法中必須在他們被提交之前傳送更多的冗餘日誌條目來為他們重新編號）。

5.4.3 安全性論證

在給定了完整的 Raft 算法之後，我們現在可以更加精確的討論領導人完整性特性（這一討論基於 9.2 節的安全性證明）。我們假設領導人完全性特性是不存在的，然後我們推出矛盾來。假設任期 T 的領導人（領導人 T）在任期內提交了一條日誌條目，但是這條日誌條目沒有被存儲到未來某個任期的領導人的日誌中。設大於 T 的最小任期 U 的領導人 U 沒有這條日誌條目。

圖 9：如果 S1 （任期 T 的領導者）提交了一條新的日誌在它的任期里，然後 S5 在之後的任期 U 里被選舉為領導人，然後至少會有一個機器，如 S3，既擁有來自 S1 的日誌，也給 S5 投票了。

在領導人 U 選舉的時候一定沒有那條被提交的日誌條目（領導人從不會刪除或者覆蓋任何條目）。
領導人 T 複製這條日誌條目給集群中的大多數節點，同時，領導人U 從集群中的大多數節點贏得了選票。因此，至少有一個節點（投票者、選民）同時接受了來自領導人T 的日誌條目，並且給領導人U 投票了，如圖 9。這個投票者是產生這個矛盾的關鍵。
這個投票者必須在給領導人 U 投票之前先接受了從領導人 T 發來的已經被提交的日誌條目；否則他就會拒絕來自領導人 T 的附加日誌請求（因為此時他的任期號會比 T 大）。
投票者在給領導人 U 投票時依然保有這條日誌條目，因為任何中間的領導人都包含該日誌條目（根據上述的假設），領導人從不會刪除條目，並且跟隨者只有和領導人衝突的時候才會刪除條目。
投票者把自己選票投給領導人 U 時，領導人 U 的日誌必須和投票者自己一樣新。這就導致了兩者矛盾之一。
首先，如果投票者和領導人 U 的最後一條日誌的任期號相同，那么領導人 U 的日誌至少和投票者一樣長，所以領導人 U 的日誌一定包含所有投票者的日誌。這是另一處矛盾，因為投票者包含了那條已經被提交的日誌條目，但是在上述的假設里，領導人 U 是不包含的。
除此之外，領導人 U 的最後一條日誌的任期號就必須比投票人大了。此外，他也比 T 大，因為投票人的最後一條日誌的任期號至少和 T 一樣大（他包含了來自任期 T 的已提交的日誌）。創建了領導人 U 最後一條日誌的之前領導人一定已經包含了那條被提交的日誌（根據上述假設，領導人 U 是第一個不包含該日誌條目的領導人）。所以，根據日誌匹配特性，領導人 U 一定也包含那條被提交當然日誌，這裡產生矛盾。
這裡完成了矛盾。因此，所有比 T 大的領導人一定包含了所有來自 T 的已經被提交的日誌。
日誌匹配原則保證了未來的領導人也同時會包含被間接提交的條目，例如圖 8 (d) 中的索引 2。

通過領導人完全特性，我們就能證明圖 3 中的狀態機安全特性，即如果已經伺服器已經在某個給定的索引值套用了日誌條目到自己的狀態機里，那么其他的伺服器不會套用一個不一樣的日誌到同一個索引值上。在一個伺服器套用一條日誌條目到他自己的狀態機中時，他的日誌必須和領導人的日誌，在該條目和之前的條目上相同，並且已經被提交。現在我們來考慮在任何一個伺服器套用一個指定索引位置的日誌的最小任期；日誌完全特性保證擁有更高任期號的領導人會存儲相同的日誌條目，所以之後的任期里套用某個索引位置的日誌條目也會是相同的值。因此，狀態機安全特性是成立的。

最後，Raft 要求伺服器按照日誌中索引位置順序套用日誌條目。和狀態機安全特性結合起來看，這就意味著所有的伺服器會套用相同的日誌序列集到自己的狀態機中，並且是按照相同的順序。

5.5 跟隨者和候選人崩潰

到目前為止，我們都只關注了領導人崩潰的情況。跟隨者和候選人崩潰後的處理方式比領導人要簡單的多，並且他們的處理方式是相同的。如果跟隨者或者候選人崩潰了，那么後續傳送給他們的 RPCs 都會失敗。Raft 中處理這種失敗就是簡單的通過無限的重試；如果崩潰的機器重啟了，那么這些 RPC 就會完整的成功。如果一個伺服器在完成了一個 RPC，但是還沒有回響的時候崩潰了，那么在他重新啟動之後就會再次收到同樣的請求。Raft 的 RPCs 都是冪等的，所以這樣重試不會造成任何問題。例如一個跟隨者如果收到附加日誌請求但是他已經包含了這一日誌，那么他就會直接忽略這個新的請求。

5.6 時間和可用性

Raft 的要求之一就是安全性不能依賴時間：整個系統不能因為某些事件運行的比預期快一點或者慢一點就產生了錯誤的結果。但是，可用性（系統可以及時的回響客戶端）不可避免的要依賴於時間。例如，如果訊息交換比伺服器故障間隔時間長，候選人將沒有足夠長的時間來贏得選舉；沒有一個穩定的領導人，Raft 將無法工作。

領導人選舉是 Raft 中對時間要求最為關鍵的方面。Raft 可以選舉並維持一個穩定的領導人,只要系統滿足下面的時間要求：

廣播時間（broadcastTime） << 選舉逾時時間（electionTimeout） << 平均故障間隔時間（MTBF）

在這個不等式中，廣播時間指的是從一個伺服器並行的傳送 RPCs 給集群中的其他伺服器並接收回響的平均時間；選舉逾時時間就是在 5.2 節中介紹的選舉的逾時時間限制；然後平均故障間隔時間就是對於一台伺服器而言，兩次故障之間的平均時間。廣播時間必須比選舉逾時時間小一個量級，這樣領導人才能夠傳送穩定的心跳訊息來阻止跟隨者開始進入選舉狀態；通過隨機化選舉逾時時間的方法，這個不等式也使得選票瓜分的情況變得不可能。選舉逾時時間應該要比平均故障間隔時間小上幾個數量級，這樣整個系統才能穩定的運行。當領導人崩潰後，整個系統會大約相當於選舉逾時的時間裡不可用；我們希望這種情況在整個系統的運行中很少出現。

廣播時間和平均故障間隔時間是由系統決定的，但是選舉逾時時間是我們自己選擇的。Raft 的 RPCs 需要接收方將信息持久化的保存到穩定存儲中去，所以廣播時間大約是 0.5 毫秒到 20 毫秒，取決於存儲的技術。因此，選舉逾時時間可能需要在 10 毫秒到 500 毫秒之間。大多數的伺服器的平均故障間隔時間都在幾個月甚至更長，很容易滿足時間的需求。

RAFT(一種分散式一致性算法)

簡述

具體內容

一致性算法

相關詞條

熱門詞條