學習Raft算法的筆記

Raft是一種為了管理日志複制的一緻性算法。它提供了和Paxos算法相同的功能和性能，但是它的算法結構和Paxos不同，使得Raft算法更加容易了解并且更容易建構實際的系統。為了提升可了解性，Raft将一緻性算法分解成幾個關鍵的子產品，例如上司選舉,日志複制和安全性。同時它通過實施一個更強的一緻性來減少需要考慮的狀态和數量。從一個使用者研究的結果可以證明，對于學生而言，Raft算法比Paxos算法更容易學。Raft算法還包括了新的機制來允許叢集成員的動态改變，讓利用重疊的大多數來保證安全性。

Raft算法概述

Raft算法是從多副本狀态機的角度提出，用于管理多副本狀态機的日志複制，它一緻性分解為多個子問題：上司選舉(Leader election)，日志複制(Log replication),安全性(Safety),日志壓縮(Log compaction),成員變更(Menbership change)等。同時，Raft算法使用了更強的假設來減少需要考慮的狀态，使之變得更加容易了解。

Raft講系統中的角色分為上司者(Leader),跟從者(Follower)和候選人(Candidate)：

Leader: 接收用戶端請求，并向Follower同步請求日志。當日志同步到大都數節點上後告告訴Follower送出日志。

Follower:接收并持久化Leader同步的日志，在Leader告訴它的日志送出之後，送出日志。

Candidate:Leader選舉過程中的臨時角色。

Raft要求系統在任意時刻最多隻有一個Leader,正常工作期間Leader和Followers。

Raft算法角色狀态轉換如下:

跟随者隻響應來自其他伺服器的請求。如果跟随者接收不到消息，那麼它就會變成候選人并發起一次選舉。獲得叢集中大多數選票的候選人将成為上司者。在一個任期内，上司人直到自己當機了。

Raft算法時間被劃分成為一個個的任期(Term)，每個任期(Term)開始都是一次Leader選舉。選舉成功後，上司人會管理整個叢集直到任期(Term)結束。有時候會選舉失敗，那麼任期(Term)就會沒有上司者，而結束。任期(Term)之間的切換可以在不同的時間不同的伺服器上觀察到。

Raft算法中伺服器之間節點通信使用遠端調用(RPCs).而在etcd的實作當中v2版本用的http，而v3版本采用的是grpc(本身是跨平台)。并且基本的一緻性算法隻是用了兩種類型的Rpcs。請求投票(RequestVote)RPCs由候選人發起。然後附加條目數(AppendEntries)由Leader發起。用來複制日志和提供一種心跳機制。為了伺服器之間傳輸快照增加了第三種RPCs。當伺服器沒有及時收到RPC的響應時，會進行重試，并且它們能夠并行發起RPCs來擷取最佳性能。

複制狀态機

一組伺服器上的狀态機産生相同狀态的副本，并且在一些機器宕掉的情況下也可以繼續運作。複制狀态機在分布式系統中被用于解決很多容錯的問題。例如，大規模的系統中通常都有一個叢集上司者，像 GFS、HDFS 和 RAMCloud，典型應用就是一個獨立的的複制狀态機去管理上司選舉和存儲配置資訊并且在上司人當機的情況下也要存活下來。比如 Chubby 和 ZooKeeper。

複制狀态機的結構。一緻性算法管理着來自用戶端指令的複制日志。狀态機從日志中處理相同順序的相同指令，是以産生的結果也是相同的。

複制狀态機通常都是基于複制日志實作的，如圖 1。每一個伺服器存儲一個包含一系列指令的日志，并且按照日志的順序進行執行。每一個日志都按照相同的順序包含相同的指令，是以每一個伺服器都執行相同的指令序列。因為每個狀态機都是确定的，每一次執行操作都産生相同的狀态和同樣的序列。

保證複制日志相同就是一緻性算法的工作了。在一台伺服器上，一緻性子產品接收用戶端發送來的指令然後增加到自己的日志中去。它和其他伺服器上的一緻性子產品進行通信來保證每一個伺服器上的日志最終都以相同的順序包含相同的請求，盡管有些伺服器會當機。一旦指令被正确的複制，每一個伺服器的狀态機按照日志順序處理他們，然後輸出結果被傳回給用戶端。是以，伺服器叢集看起來形成一個高可靠的狀态機。

實際系統中使用的一緻性算法通常含有以下特性：

安全性保證（絕對不會傳回一個錯誤的結果）：在非拜占庭錯誤情況下，包括網絡延遲、分區、丢包、備援和亂序等錯誤都可以保證正确。

可用性：叢集中隻要有大多數的機器可運作并且能夠互相通信、和用戶端通信，就可以保證可用。是以，一個典型的包含 5 個節點的叢集可以容忍兩個節點的失敗。伺服器被停止就認為是失敗。他們當有穩定的存儲的時候可以從狀态中恢複回來并重新加入叢集。

不依賴時序來保證一緻性：實體時鐘錯誤或者極端的消息延遲在可能隻有在最壞情況下才會導緻可用性問題。

通常情況下，一條指令可以盡可能快的在叢集中大多數節點響應一輪遠端過程調用時完成。小部分比較慢的節點不會影響系統整體的性能。

Leader選舉

Raft使用心跳(heartbeat)觸發Leader選舉。當伺服器啟動時，初始化Follower。Leader向所有的Followers周期性的發送heartbeat。如果Follower在選舉逾時時間内沒有收到Leader的heartbeat，就會等待一段随機時間(150ms-300ms)發起一次選舉。

Follower先要增加自己的目前任期号，也就把目前的任期号加一并且轉換到候選人狀态。然後它們會并行的向叢集中的其他伺服器節點發起請求投票的RPCs來給自己投票。結果會有以下三種情況:

1. 它自己赢得了這次選舉
2. 其他的伺服器成為了上司者
3. 一段世家之後沒有人擷取勝利的人。

日志複制

Leader被選舉出來後.它就開始為用戶端提供服務，用戶端每個請求都包含一條被複制狀态機執行的指令。上司人将這條指令作為新的日志條目附加到日志中去。然後并行的發起附加條目RPCs給其他的伺服器，讓它們複制這個日志條目，當這條日志條目被安全的複制。上司人會應用這條日志條目到它的狀态中然後把執行的結果傳回用戶端。如果Follower崩潰或者運作緩慢，再或者網絡丢包，上司人會不斷的嘗試附加日志條目RPCs(盡管已經回複了用戶端)直到所有Follower都最終存儲了所有條目數。

日志由有序編号(log index)的日志組成條目。每個日志條目包含它被建立的任期号(term),和用于狀态機執行的指令。如果一個日志條目被複制到大多數伺服器上,就被認為可以送出了(commit)了。

Raft維護着一下特征:

1.如果在不同的日志中的兩個條目擁有相同的索引和任期号,那麼它們存儲了相同的指令。

2.如果在不同的日志中的兩個條目擁有相同的索引和任期号,那麼他們的之前的所有日志條目也全部相同。

第一個特新來這樣的一個事實,上司人最多在一個任期裡在指定的日志索引位置建立一條日志條目，同時日志條目在日志中的位置也從來不會改變。第二個特性由附加日志RPC的一個簡單一緻性檢查保證。在發送附加日志RPC的時候，上司人會把新的日志條目緊接着之前的條目索引位置和任期号包含在裡面。如果跟随者在它的日志中找不到包含相同的日志索引位置和任期号的條目,那麼他就會拒絕接收新的條目日志。一緻性檢查就像一個歸納步驟:一開始空日志狀态肯定是滿足日志比對特性的，然後一緻性檢查保護了日志比對特性當日志擴充的時候。是以,每當附加日志RPC傳回成功時，上司人就知道跟随着的日志時一樣的了。

當一個上司人成功當選時，跟随者可能是任何情況(a-f)。每一個盒子表示是一個日志條目，裡面的數字表示任期号。跟随者可能缺少一些體制條目(a-b)，可能會有一些未被送出的日志條目(c-d)，或者兩種情況都存在的(e-f)。例如,場景f可能會發生，某些伺服器在任期号2的時候是上司人，已附加了一些日志條目到自己的日志中，但在送出之前就就崩潰了,很快這個機器就被重新開機了,在任期3重新被選為上司人，并且又增加了一些日志條目到自己的日志中,并且又增加了一些日志條目到自己的日志中，在任期2和任期3的日志被送出之前，這個伺服器又當機了，并且在接下來的幾個任期裡一直處于當機狀态。

要使得跟随着的日志進入和自己一緻的狀态，上司人必須找到最後兩者達成一緻的地方，然後删除那個點之後的所有日志條目，發送自己的日志給跟随者。所有的這些日志操作都在進行附加日志RPCs的一緻性檢查時完成。上司人針對沒一個維護者維護了一個nextIndex,這表示下一個發送給追随者的日志條目的索引位址。當一個上司人剛獲得上司者的權利的時候，他初始化所有的nextIndex值作為自己的最後一條日志的index加1。如果一個跟随者的日志和上司人不一緻，那麼下一次日志附RPC時的一緻性檢查就會失敗。在被跟随者拒絕之後，上司人就會減少nextIndex值并進行重試。最終nextIndex會在某個位置使得上司人和跟随者的日志達成一緻。當這種情況發生，附加日志RPC就會成功，這時就會把跟随者沖突的日志條目全部删除并且加上上司人的日志。一旦附加日志RPC成功，那麼跟随者的日志就會和上司人保持一直，并且在接下來的任期裡一直繼續保持。

安全性

Raft增加了如下兩條限制以保證安全性:

1>擁有最新的已送出的log entry的Follower才有資格成為Leader。

這個保證是在RequestVote RPC中做的，Candidate在發送RequestVote RPC時。要帶上自己的最後一條日志的term和log Index。其他節點收到消息時，如果發現自己的日志請求中攜帶的更新，則拒絕投票。日志比較的原則是:如果本地的最後一條log entry的term更大，則term大更新，如果term一樣大，則log Index更大的更新。

2.Leader隻能推進commit Index來送出目前term已經複制最到最大伺服器上的日志，舊term日志的日志要等到送出目前的term的日志來間接送出(log Index 小于commit Index的日志被間接送出)

之是以要這樣，是因為可能會出現已送出的日志被覆寫的情況:

如圖的時間序列展示了上司人無法決定對老任期号的日志條目進行送出。在(a)中，S1是Leader，部分的是複制了索引的位置2的條目數目。(b)是時期，S1崩潰了，然後S5在任期3裡通過S3,S4和自己的選票赢得選舉，然後從用戶端接收了一條不一樣的日志條目放在了索引2處。然後到(c),S5崩潰了，S1重新啟動，選舉成功，開始日志複制。在這個時候，來自任期2的那條日志已經被複制到了叢集的大多數機器上，但是還沒有被送出，如果S1在(d)時期中又崩潰了。S5可以重新被選舉成功(通過來自S2,S3,S4的選票)，然後覆寫了他門在索引2處的日志。反之，如果在崩潰之前，S1把自己主導的任期裡産生的日志日條目複制到了大多數機器上，就如(e)中那樣。那麼在後面任期裡面這些新的日志條目會被送出(因為S5就不可能選舉成功)。這牙膏在同一時刻就同時保證了，之前的所有老的日志條目就會被送出。

時間和可用性

Raft的要求之一就是安全性不能依賴時間:整個系統不能因為某些事件運作的比預期快一點或者慢一點産生了錯誤的結果。但是，可用性(系統可以及時的響應用戶端)不可避免的要依賴時間。例如，如果消息交換比伺服器故障間隔時間長，候選人沒有足夠長的時間來赢得選舉，沒有一個穩定的上司人，Raft将無法工作。

上司人選舉時Raft中對時間要求最為關鍵的方面。Raft可以選舉并維持一個穩定的上司人，隻需要滿足下面的時間要求:

廣播時間(broadcastTime) << 選舉時間(election Timeout) << 平均故障時間(MTBF)

在這個不等式中，廣播時間指的時從一個伺服器并行的發送RPCs給叢集中的其他伺服器并接收平均時間，選舉逾時時間（150ms-300ms）選舉逾時時間限制，然後平均故障時間就是對于一台伺服器而言，兩次故障之間的平均時間。廣播時間必須比選舉逾時時間小一個量級，這樣上司人才能發送穩定的心跳消息來阻止跟随者開始進入選舉狀态，通過随機化選舉逾時時間的方法，整個不等式也使得選票瓜分的情況變成不肯能。選舉選舉逾時時間要比平局故障時間間隔小上幾個數量級,這樣系統才能穩定的運作。當上司人崩潰後，整個系統會大約相當于逾時時的時間裡不可用。我們希望這種情況在系統中國運作很少出現。

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

成員變更

成員變更是在叢集運作過程中副本發生變化，如增加/減少副本數，節點替換等。

成員變更也是一個分布式一緻性的問題，既所有伺服器對成員新成員達成一緻。但是成員變更又有其特殊性，因為成員變更的一緻性達成的過程中，參與投票的過程會發生變化。

如果将成員變更當成一般的一緻性問題，直接向Leader發送成員變更請求，Leader複制成員變更日志，達成多數之後送出，各個伺服器送出成員變更日志後從日志成員(Cold)切換到最新成員配置(Cnew的時刻不同.

成員變更不能影響服務的可用性，但是成員變更過程的某一時刻，可能出現Cold和Cnew中同時存在兩個不相交的多數派，進而可能選出兩個Leader，形成不同的決議，破壞安全性。

由于成員變更的這一特殊性，成員變更不能當成一般的一緻性問題去解決。

為了解決這一問題.Raft提出了兩段的成員變更方法。叢集先成舊成員配置Cold切換到一個過度的配置，稱為共同一緻(joint consensus),共同一緻時舊成員配置Cold和新成員配置Cnew的組合Cold U Cnew，一旦共同一緻Cold U Cnew被送出，系統在切換到新成員配置Cnew。

一個配置切換的時間線。虛線表示已經被建立但是還沒有被送出的條目，實線表示最後被送出的日志條目。上司人首先建立了C-old

,new的配置條目在自己的日志中，并送出到C-old,new中(C-old的大多數和c-new的大多數)。然後他建立C-new條目并且送出到C-new的大多數。這樣就不存在C-new和C-old同時做出決定的時間點。

在關于重新配置還有三個問題需要提出,第一個問題是，新的伺服器額能初始化沒有存儲任何的日志條目。當這些伺服器以這種狀态加入到叢集中，那麼它們需要一段時間來更新追趕。這時還不能送出新的日志條目。為了避免這種可用性的間隔時間Raft在配置更新的時候用了一種額外的階段，在這種階段，新的伺服器以沒有投票權的身份加入叢集中來(上司人複制日志給它們。但是不考慮它們是大多數)。一旦新的伺服器追趕上了叢集中的叢集，重新配置可以向上面描述一樣處理。

第二個問題，叢集的上司人可能不是新配置的一員。在這種情況下，上司人就會在送出了C-new日志後退位(回到追随者狀态)。這意味着有這樣一段時間，上司人管理着叢集，但是不包括他自己，他複制日志但是不把他自己算作大多數之一。當C-new被送出時，會發生上司人過度。因為這時時最新的配置可以獨立工作時間點(将總是能夠在C-new配置下選出新的Leader)。再此之前，可能隻從C-old中選出上司人。

第三個問題是:移除不再C-new中的伺服器可能會擾亂叢集。這些伺服器将不會再接收心跳。當選舉逾時時，它們就會進行新的選舉過程。它們會發送擁有新的任期号的請求投票RPCs，這樣會導緻目前的上司人退回成跟随者狀态。新的上司人最終被選出來，但是被移除的伺服器将會再次逾時，然後這種過程再次重複，導緻整體可用性大幅度下降。

為了避免這個問題，當伺服器确認目前上司人存在時，伺服器會忽略投票RPCs。特别的，當伺服器再目前最小選舉逾時時間内收到一個請求投票的RPC。他不會更新目前的任期号和投票号。這不會影響正常的選舉，每個伺服器在開始一次選舉之前，至少等待一個最小選舉逾時時間。然後這有利于避免被移除的伺服器的擾亂。如果上司人能夠發送心跳給叢集，那麼他就不會更大的任期号廢黜。

日志壓縮

在實際系統中，不能讓日志無限增長，否則系統重新開機時需要花很長的時間回放，進而影響可用性。Raft采用對整個系統進行snapshot來解決，snapshot之前的日志都可以抛棄。

每個副本獨立的對自己系統狀态進行snapshot，并且隻能對已經送出的日志進行snapshot。

Snapshot中包含以下内容:

1>日志中繼資料:最後送出的log entry的log index和term。這兩個值在snapshot之後的第一條log entry的AppendEntriesRPC的完整性檢查的時候會被用上。

2> 系統目前狀态。

當Leader要發給某個日志落後太多的Follower的log entry被丢棄，Leader會将snapshot發給Follower。或者新加入一台機器時，也會發送snapshot給它。發送snapshot使用InstalledSnapshot RPC。

一個伺服器用新的快照替換了從1到5的條目數，快照存儲了目前的狀态。快照中包含了最後的索引位置和任期号

做snapshot不要做的太頻繁，否則消耗磁盤帶寬，也不要做的太平凡，否則一點節點重新開機要回放大量日志，影響可用性。推薦當日組織達到某個固定的大小做一次snapshot。

做一次snapshot可能耗時過長，會影響正常日志同步。可以通過使用copy-on-write技術避免snapshot過程影響正常的日志同步過程。

一個關于 Raft 一緻性算法的濃縮總結（不包括成員變換和日志壓縮）。

參考：

http://thesecretlivesofdata.com/raft/(Raft動畫)

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md(Raft論文翻譯)