RAFT

RAFT核心思想很容易了解，如果數個資料庫，初始狀态一緻，隻要之後的進行的操作一緻，就能保證之後的資料一緻。由此RAFT使用的是Log進行同步，并且将伺服器分為三中角色：Leader，Follower，Candidate，互相可以互相轉換。 RAFT從大的角度看，分為兩個過程： 1. 選舉Leader 2. Leader生成Log，并與Follower進行Headbeats同步

選舉Leader

Follower自增目前任期，轉換為Candidate，對自己投票，并發起RequestVote RPC，等待下面三種情形發生；

1. 獲得超過半數伺服器的投票，赢得選舉，成為Leader

2. 另一台伺服器赢得選舉，并接收到對應的心跳，成為Follower

3. 選舉逾時，沒有任何一台伺服器赢得選舉，自增目前任期，重新發起選舉

同步日志

Leader接受用戶端請求，Leader更新日志，并向所有Follower發送Heatbeats，同步日志。所有Follwer都有ElectionTimeout，如果在ElectionTimeout時間之内，沒有收到Leader的Headbeats，則認為Leader失效，重新選舉Leader 流程圖示：

安全性保證

1. 日志的流向隻有Leader到Follower，并且Leader不能覆寫日志 2. 日志不是最新者不能成為Candidate 動畫示範RAFT：http://thesecretlivesofdata.com/raft/

1. 在Raft中，問題分解為：上司選取、日志複制、安全和成員變化。

   基本概念

   複制狀态機（Replicated State Machine）

   

   1.png
   • 複制狀态機通過複制日志來實作：
     • 日志：每台機器儲存一份日志，日志來自于用戶端的請求，包含一系列的指令
     • 狀态機：狀态機會按順序執行這些指令
     • 一緻性模型：分布式環境下，保證多機的日志是一緻的，這樣回放到狀态機中的狀态是一緻的
   • 一緻性算法作用于一緻性模型，一般有以下特性：
     • safety：在非拜占庭問題下（網絡延時，網絡分區，丢包，重複發包以及包亂序等），結果是正确的
     • availability：在半數以上機器能正常工作時，則系統可用
     • timing-unindependent：不依賴于時鐘來保證日志一緻性，錯誤的時鐘以及極端的消息時延最多會造成可用性問題

   注意：

   真實的實作中，建議狀态機的每個指令操作都采用幂等的，這樣一緻性的保證會更容易。

   伺服器狀态

   每台伺服器一定會處于三種狀态：
   1. 上司者
   2. 候選人
   3. 追随者

   

   2.png

   追随者隻響應其他伺服器的請求。如果追随者沒有收到任何消息，它會成為一個候選人并且開始一次選舉。收到大多數伺服器投票的候選人會成為新的上司人。上司人在它們當機之前會一直保持上司人的狀态。

   任期(Term)

   Raft 算法将時間劃分成為任意不同長度的任期（term）。任期用連續的數字進行表示。每一個任期的開始都是一次選舉（election），一個或多個候選人會試圖成為上司人。如果一個候選人赢得了選舉，它就會在該任期的剩餘時間擔任上司人。在某些情況下，選票會被瓜分，有可能沒有選出上司人，那麼，将會開始另一個任期，并且立刻開始下一次選舉。Raft 算法保證在給定的一個任期最多隻有一個上司人。

   

   3.png

   RPC

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

   RPC有三種：

   1. RequestVote RPC：候選人在選舉期間發起
   2. AppendEntries RPC：上司人發起的一種心跳機制，複制日志也在該指令中完成
   3. InstallSnapshot RPC: 上司者使用該RPC來發送快照給太落後的追随者。
   逾時設定：
   1. BroadcastTime : 上司者的心跳逾時時間
   2. Election Timeout: 追随者設定的候選逾時時間
   3. MTBT :指的是單個伺服器發生故障的間隔時間的平均數

   BroadcastTime << ElectionTimeout << MTBF

   兩個原則：

   1. BroadcastTime應該比ElectionTimeout小一個數量級，為的是使上司人能夠持續發送心跳資訊（heartbeat）來阻止追随者們開始選舉；
   2. ElectionTimeout也要比MTBF小幾個數量級，為的是使得系統穩定運作。
   一般BroadcastTime大約為0.5毫秒到20毫秒，ElectionTimeout一般在10ms到500ms之間。大多數伺服器的MTBF都在幾個月甚至更長。

2. 上司人選取

   • 觸發條件：
     1. 一般情況下，追随者接到上司者的心跳時，把ElectionTimeout清零，不會觸發；
     2. 上司者故障，追随者的ElectionTimeout逾時發生時，會變成候選者，觸發上司人選取；
   • 候選操作過程：

   追随者自增目前任期，轉換為Candidate，對自己投票，并發起RequestVote RPC，等待下面三種情形發生；

   1. 獲得超過半數伺服器的投票，赢得選舉，成為上司者；
   2. 另一台伺服器赢得選舉，并接收到對應的心跳，成為追随者；
   3. 選舉逾時，沒有任何一台伺服器赢得選舉，自增目前任期，重新發起選舉；
   • 注意事項：
     1. 伺服器在一個任期内，最多能給一個候選人投票，采用先到先服務原則；
     2. 候選者等待投票時，可能會接收到來自其它聲明為上司人的的AppendEntries RPC。如果該上司人的任期（RPC中有）比目前候選人的目前任期要大，則候選人認為該上司人合法，并轉換成追随者；如果RPC中的任期小于候選人的目前任期，則候選人拒絕此次RPC，繼續保持候選人狀态；
     3. 候選人既沒有赢得選舉也沒有輸掉選舉：如果許多追随者在同一時刻都成為了候選人，選票會被分散，可能沒有候選人能獲得大多數的選票。當這種情形發生時，每一個候選人都會逾時，并且通過自增任期号和發起另一輪 RequestVote RPC 來開始新的選舉。然而，如果沒有其它手段來配置設定選票的話，這種情形可能會無限的重複下去。是以Raft使用的随機的選舉逾時時間（150~300ms之間），來避免這種情況發生。

   • 問題探讨：為什麼這裡沒有談收到其他候選者的RequestVote RPC請求？

     可能的解釋：

     1. 候選者已經給自己投票了，一個候選者在一個任期隻會給一個人投票，不會給其他人再投票了；
     2. 也有可能算法本身設定候選者就拒絕所有的其他伺服器的請求。

3. 日志複制

   

   4.png

   接受指令的過程：

   1. 上司者接受用戶端請求；
   2. 上司者把指令追加到日志；
   3. 發送AppendEntries RPC到追随者；
   4. 上司者收到大多數追随者的确認後，上司者Commit該日志，把日志在狀态機中回放，并傳回結果給用戶端；
   送出過程：
   1. 在下一個心跳階段，上司者再次發送AppendEntries RPC給追随者，日志已經commited；
   2. 追随者收到Commited日志後，将日志在狀态機中回放。

安全性

到目前為止描述的機制并不能充分的保證每一個狀态機會按照相同的順序執行相同的指令，例如：一個跟随者可能會進入不可用狀态同時上司人已經送出了若幹的日志條目，然後這個跟随者可能會被選舉為上司人并且覆寫這些日志條目；是以，不同的狀态機可能會執行不同的指令序列。

1. 上司者追加日志（Append-Only)

上司者永遠不會覆寫已經存在的日志條目；

日志永遠隻有一個流向：從上司者到追随者；

2. 選舉限制：投票阻止沒有全部日志條目的伺服器赢得選舉

如果投票者的日志比候選人的新，拒絕投票請求；

這意味着要赢得選舉，候選者的日志至少和大多數伺服器的日志一樣新，那麼它一定包含全部的已經送出的日志條目。

3. 永遠不送出任期之前的日志條目（隻送出任期内的日志條目）

在Raft算法中，當一個日志被安全的複制到絕大多數的機器上面，即AppendEntries RPC在絕大多數伺服器正确傳回了，那麼這個日志就是被送出了，然後上司者會更新commit index。

5.png

如果允許送出任期之前的日志條目，那麼在步驟c中，我們就會把之前任期為2的日志送出到其他伺服器中去，并造成了大多數機器存在了日志為2的情況。是以造成了d中S5中任期為3的日志條目會覆寫掉已經送出的日志的情況。

Raft 從來不會通過計算複制的數目來送出之前人氣的日志條目。隻有上司人目前任期的日志條目才能通過計算數目來進行送出。一旦目前任期的日志條目以這種方式被送出，那麼由于日志比對原則（Log Matching Property），之前的日志條目也都會被間接的送出。

論文中的這段話比較難了解，更加直覺的說：由于Raft不會送出任期之前的日志條目，那麼就不會從b過渡到c的情況，隻能從b發生S5down機的情況下直接過渡到e，這樣就産生的更新的任期，這樣S5就沒有機會被選為上司者了。

4. 候選者和追随者崩潰

候選者和追随者崩潰的情況處理要簡單的多。如果這類角色崩潰了，那麼後續發送給他們的 RequestVote和AppendEntries的所有RCP都會失敗，Raft算法中處理這類失敗就是簡單的無限重試的方式。

　　如果這些伺服器重新可用，那麼這些RPC就會成功傳回。如果一個伺服器完成了一個RPC，但是在響應Leader前崩潰了，那麼當他再次可用的時候還會收到相同的RPC請求，此時接收伺服器負責檢查，比如如果收到了已經包含該條日志的RPC請求，可以直接忽略這個請求，確定對系統是無害的。

叢集成員變更

叢集成員的變更和成員的當機與重新開機不同，因為前者會修改成員個數進而影響到上司者的選取和決議過程，因為在分布式系統這對于majority這個叢集中成員大多數的概念是極為重要的。

簡單的做法是，運維人員将系統臨時下線，修改配置，重新上線。但是這種做法存在兩個缺點：

1. 更改時叢集不可用
2. 人為操作失誤風險

直接從一種配置轉到新的配置是十分不安全的

如下圖所示：

6.png

因為各個機器可能在任何的時候進行轉換。在這個例子中，叢集配額從 3 台機器變成了 5 台。不幸的是，存在這樣的一個時間點，兩個不同的上司人在同一個任期裡都可以被選舉成功。一個是通過舊的配置，一個通過新的配置。

兩階段方法保證安全性：

為了保證安全性，配置更改必須使用兩階段方法。在 Raft 中，叢集先切換到一個過渡的配置，我們稱之為共同一緻；一旦共同一緻已經被送出了，那麼系統就切換到新的配置上。共同一緻是老配置和新配置的結合。

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

一個上司人接收到一個改變配置從 C-old 到 C-new 的請求，他會為了共同一緻存儲配置（圖中的 C-old,new），以前面描述的日志條目和副本的形式。一旦一個伺服器将新的配置日志條目增加到它的日志中，他就會用這個配置來做出未來所有的決定。上司人完全特性保證了隻有擁有 C-old,new 日志條目的伺服器才有可能被選舉為上司人。當C-old,new日志條目被送出以後，上司人在使用相同的政策送出C-new，如下圖所示，C-old 和 C-new 沒有任何機會同時做出單方面的決定，這就保證了安全性。

一個配置切換的時間線。虛線表示已經被建立但是還沒有被送出的條目，實線表示最後被送出的日志條目。上司人首先建立了 C-old,new 的配置條目在自己的日志中，并送出到 C-old,new 中（C-old,new 的大多數和 C-new 的大多數）。然後他建立 C-new 條目并送出到 C-new 中的大多數。這樣就不存在 C-new 和 C-old 可以同時做出決定的時間點。

日志壓縮

日志會随着系統的不斷運作會無限制的增長，這會給存儲帶來壓力，幾乎所有的分布式系統(Chubby、ZooKeeper)都采用快照的方式進行日志壓縮，做完快照之後快照會在穩定持久存儲中儲存，而快照之前的日志和快照就可以丢棄掉。

Raft的具體做法如下圖所示：

8.png

與Raft其它操作Leader-Based不同，snapshot是由各個節點獨立生成的。除了日志壓縮這一個作用之外，snapshot還可以用于同步狀态：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成該過程，不再贅述。

Client互動

1. Client隻向上司者發送請求；
2. Client開始會向追随者發送請求，追随者拒絕Client的請求，并重定向到上司者；
3. Client請求失敗，會逾時重新發送請求；

Raft算法要求Client的請求線性化，防止請求被多次執行。有兩個解決方案：

1. Raft算法提出要求每個請求有個唯一辨別；
2. Raft的請求保持幂等性；

   自增目前任期?目前任期結束，新的任期開始。

    當投票被瓜分後，所有的candidate同時逾時，然後有可能進入新一輪的票數被瓜分，為了避免這個問題。每個candidate的election timeout從150ms-300ms之間随機取。這樣candidate發起新一輪的leader election的時間就會相同，誰的election timeout小誰成為leader的幾率就大。