極客們，請收下2021 微軟 x 英特爾黑客松大賽英雄帖！>>>
一、 Raft簡介
1.1 Raft簡介
Raft 是一種為了管理日志複制的分布式一緻性算法。Raft 出現之前，Paxos 一直是分布式一緻性算法的标準。Paxos 難以了解，更難以實作。Raft 的設計目标是簡化 Paxos，使得算法既容易了解，也容易實作。
Paxos 和 Raft 都是分布式一緻性算法，這個過程如同投票選舉領袖（Leader），參選者（Candidate）需要說服大多數投票者（Follower）投票給他，一旦選舉出領袖，就由領袖發号施令。Paxos 和 Raft 的差別在于選舉的具體過程不同。
Raft 可以解決分布式 CAP 理論中的 CP，即 一緻性（C：Consistency） 和 分區容忍性（P：Partition Tolerance），并不能解決 可用性（A：Availability） 的問題。
1.2 分布一緻性
分布式一緻性 (distributed consensus) 是分布式系統中最基本的問題，用來保證一個分布式系統的可靠性以及容錯能力。簡單來說，分布式一緻性是指多個伺服器的保持狀态一緻。
在分布式系統中，可能出現各種意外（斷電、網絡擁塞、CPU/記憶體耗盡等等），使得伺服器當機或無法通路，最終導緻無法和其他伺服器保持狀态一緻。為了應對這種情況，就需要有一種一緻性協定來進行容錯，使得分布式系統中即使有部分伺服器當機或無法通路，整體依然可以對外提供服務。
以容錯方式達成一緻，自然不能要求所有伺服器都達成一緻狀态，隻要超過半數以上的伺服器達成一緻就可以了。假設有 N 台伺服器， 大于等于 N / 2 + 1 台伺服器就算是半數以上了 。
1.3 複制狀态機
複制狀态機（Replicated State Machines） 是指一組伺服器上的狀态機産生相同狀态的副本，并且在一些機器宕掉的情況下也可以繼續運作。一緻性算法管理着來自用戶端指令的複制日志。狀态機從日志中處理相同順序的相同指令，是以産生的結果也是相同的。
複制狀态機通常都是基于複制日志實作的，如上圖。每一個伺服器存儲一個包含一系列指令的日志，并且按照日志的順序進行執行。每一個日志都按照相同的順序包含相同的指令，是以每一個伺服器都執行相同的指令序列。因為每個狀态機都是确定的，每一次執行操作都産生相同的狀态和同樣的序列。
保證複制日志相同就是一緻性算法的工作了。在一台伺服器上，一緻性子產品接收用戶端發送來的指令然後增加到自己的日志中去。它和其他伺服器上的一緻性子產品進行通信來保證每一個伺服器上的日志最終都以相同的順序包含相同的請求，盡管有些伺服器會當機。一旦指令被正确的複制，每一個伺服器的狀态機按照日志順序處理他們，然後輸出結果被傳回給用戶端。是以，伺服器叢集看起來形成一個高可靠的狀态機。
實際系統中使用的一緻性算法通常含有以下特性：
安全性保證（絕對不會傳回一個錯誤的結果）：在非拜占庭錯誤情況下，包括網絡延遲、分區、丢包、備援和亂序等錯誤都可以保證正确。
可用性：叢集中隻要有大多數的機器可運作并且能夠互相通信、和用戶端通信，就可以保證可用。是以，一個典型的包含 5 個節點的叢集可以容忍兩個節點的失敗。伺服器被停止就認為是失敗。他們當有穩定的存儲的時候可以從狀态中恢複回來并重新加入叢集。
不依賴時序來保證一緻性：實體時鐘錯誤或者極端的消息延遲隻有在最壞情況下才會導緻可用性問題。
通常情況下，一條指令可以盡可能快的在叢集中大多數節點響應一輪遠端過程調用時完成。小部分比較慢的節點不會影響系統整體的性能。
1.4 RAFT應用
通過 RAFT 提供的複制狀态機，可以解決分布式系統的複制、修複、節點管理等問題。Raft 極大的簡化目前分布式系統的設計與實作，讓開發者隻關注于業務邏輯，将其抽象實作成對應的狀态機即可。基于這套架構，可以建構很多分布式應用：
分布式鎖服務
分布式存儲系統，比如分布式消息隊列、分布式塊系統、分布式檔案系統、分布式表格系統等，比如大名鼎鼎的 Redis 就是基于 Raft 實作分布式一緻性
高可靠元資訊管理，比如各類 Master 子產品的 HA
二、 Raft基礎
Raft 将一緻性問題分解成了三個子問題：選舉 Leader、日志複制、安全性。
在後續章節，會詳細講解這個子問題。現在，先了解一下 Raft 的一些核心概念。
2.1 伺服器角色
在 Raft 中，任何時刻，每個伺服器都處于這三個角色之一 ：
Leader - 上司者，通常一個系統中是一主（Leader）多從（Follower）。Leader 負責處理所有的用戶端請求。
Follower - 跟随者，不會發送任何請求，隻是簡單的** 響應來自 Leader 或者 Candidate 的請求**。
Candidate - 參選者，選舉新 Leader 時的臨時角色。
圖示說明：
- Follower 隻響應來自其他伺服器的請求。在一定時限内，如果 Follower 接收不到消息，就會轉變成 Candidate，并發起選舉。
- Candidate 向 Follower 發起投票請求，如果獲得叢集中半數以上的選票，就會轉變為 Leader。
- 在一個 Term 内，Leader 始終保持不變，直到下線了。Leader 需要周期性向所有 Follower 發送心跳消息，以阻止 Follower 轉變為 Candidate。
2.2 任期
Raft 把時間分割成任意長度的 任期（Term），任期用連續的整數标記。每一段任期從一次選舉開始。Raft 保證了在一個給定的任期内，最多隻有一個上司者。
如果選舉成功，Leader 會管理整個叢集直到任期結束。
如果選舉失敗，那麼這個任期就會因為沒有 Leader 而結束。
不同伺服器節點觀察到的任期轉換狀态可能不一樣：
伺服器節點可能觀察到多次的任期轉換。
伺服器節點也可能觀察不到任何一次任期轉換。
任期在 Raft 算法中充當邏輯時鐘的作用，使得伺服器節點可以查明一些過期的資訊（比如過期的 Leader）。每個伺服器節點都會存儲一個目前任期号，這一編号在整個時期内單調的增長。當伺服器之間通信的時候會交換目前任期号。
如果一個伺服器的目前任期号比其他人小，那麼他會更新自己的編号到較大的編号值。
如果一個 Candidate 或者 Leader 發現自己的任期号過期了，那麼他會立即恢複成跟随者狀态。
如果一個節點接收到一個包含過期的任期号的請求，那麼他會直接拒絕這個請求。
資料可視化的應用場景越來越廣泛，資料可以呈現為更多豐富的可視化形式，使使用者能夠更加輕易、便捷的擷取并了解資料傳達的資訊。
2.3 RPC
Raft 算法中伺服器節點之間的通信使用 遠端過程調用（RPC）。基本的一緻性算法隻需要兩種 RPC：
RequestVote RPC - 請求投票 RPC，由 Candidate 在選舉期間發起。
AppendEntries RPC - 附加條目 RPC，由 Leader 發起，用來複制日志和提供一種心跳機制。
三、選舉Leader
3.1 選舉規則
Raft 使用一種心跳機制來觸發 Leader 選舉。Leader 需要周期性的向所有 Follower 發送心跳消息，以此維持自己的權威并阻止新 Leader 的産生。
每個 Follower 都設定了一個随機的競選逾時時間，一般為 150ms ~ 300ms，如果在競選逾時時間内沒有收到 Leader 的心跳消息，就會認為目前 Term 沒有可用的 Leader，并發起選舉來選出新的 Leader。開始一次選舉過程，Follower 先要增加自己的目前 Term 号，并轉換為 Candidate。
Candidate 會并行的向叢集中的所有伺服器節點發送投票請求（RequestVote RPC），它會保持目前狀态直到以下三件事情之一發生：
自己成為 Leader
其他的伺服器成為 Leader
沒有任何伺服器成為 Leader
3.1.1自己成為 Leader
當一個 Candidate 從整個叢集半數以上的伺服器節點獲得了針對同一個 Term 的選票，那麼它就赢得了這次選舉并成為 Leader。每個伺服器最多會對一個 Term 投出一張選票，按照先來先服務（FIFO）的原則。要求半數以上選票的規則確定了最多隻會有一個 Candidate 赢得此次選舉。
一旦 Candidate 赢得選舉，就立即成為 Leader。然後它會向其他的伺服器發送心跳消息來建立自己的權威并且阻止新的上司人的産生。
3.1.2 其他的伺服器成為 Leader
等待投票期間，Candidate 可能會從其他的伺服器接收到聲明它是 Leader 的 AppendEntries RPC。
如果這個 Leader 的 Term 号（包含在此次的 RPC 中）不小于 Candidate 目前的 Term，那麼 Candidate 會承認 Leader 合法并回到 Follower 狀态。
如果此次 RPC 中的 Term 号比自己小，那麼 Candidate 就會拒絕這個消息并繼續保持 Candidate 狀态。
3.1.3 沒有任何伺服器成為 Leader
如果有多個 Follower 同時成為 Candidate，那麼選票可能會被瓜分以至于沒有 Candidate 可以赢得半數以上的投票。當這種情況發生的時候，每一個 Candidate 都會競選逾時，然後通過增加目前 Term 号來開始一輪新的選舉。然而，沒有其他機制的話，選票可能會被無限的重複瓜分。
Raft 算法使用随機選舉逾時時間的方法來確定很少會發生選票瓜分的情況，就算發生也能很快的解決。為了阻止選票起初就被瓜分，競選逾時時間是一個随機的時間，在一個固定的區間（例如 150-300 毫秒）随機選擇，這樣可以把選舉都分散開。
以至于在大多數情況下，隻有一個伺服器會逾時，然後它赢得選舉，成為 Leader，并在其他伺服器逾時之前發送心跳包。
同樣的機制也被用在選票瓜分的情況下：每一個 Candidate 在開始一次選舉的時候會重置一個随機的選舉逾時時間，然後在逾時時間内等待投票的結果；這樣減少了在新的選舉中另外的選票瓜分的可能性。
了解了上面的選舉規則後，我們通過動圖來加深認識。
3.2 單Candidate選舉
- 下圖表示一個分布式系統的最初階段，此時隻有 Follower，沒有 Leader。Follower A 等待一個随機的選舉逾時時間之後，沒收到 Leader 發來的心跳消息。是以，将 Term 由 0 增加為 1，轉換為 Candidate，進入選舉狀态。
2)此時，A 向所有其他節點發送投票請求。
- 其它節點會對投票請求進行回複，如果超過半數以上的節點投票了，那麼該 Candidate 就會立即變成 Term 為 1 的 Leader。
- Leader 會周期性地發送心跳消息給所有 Follower，Follower 接收到心跳包，會重新開始計時。
3.3 多 Candidate 選舉
- 1如果有多個 Follower 成為 Candidate，并且所獲得票數相同，那麼就需要重新開始投票。例如下圖中 Candidate B 和 Candidate D 都發起 Term 為 4 的選舉，且都獲得兩票，是以需要重新開始投票。
2) 當重新開始投票時，由于每個節點設定的随機競選逾時時間不同，是以能下一次再次出現多個 Candidate 并獲得同樣票數的機率很低。
四、日志複制
4.1 日志格式
**日志由含日志索引（log index）**的日志條目（log entry）組成。每個日志條目包含它被建立時的 Term 号（下圖中方框中的數字），和一個複制狀态機需要執行的指令。如果一個日志條目被複制到半數以上的伺服器上，就被認為可以送出（Commit）了。
日志條目中的 Term 号被用來檢查是否出現不一緻的情況。
日志條目中的日志索引（一個整數值）用來表明它在日志中的位置。
Raft 日志同步保證如下兩點；圖示說明：
如果不同日志中的兩個日志條目有着相同的日志索引和 Term，則它們所存儲的指令是相同的。
這個特性基于這條原則：Leader 最多在一個 Term 内、在指定的一個日志索引上建立一條日志條目，同時日志條目在日志中的位置也從來不會改變。
如果不同日志中的兩個日志條目有着相同的日志索引和 Term，則它們之前的所有條目都是完全一樣的。
這個特性由 AppendEntries RPC 的一個簡單的一緻性檢查所保證。在發送 AppendEntries RPC 時，Leader 會把新日志條目之前的日志條目的日志索引和 Term 号一起發送。如果 Follower 在它的日志中找不到包含相同日志索引和 Term 号的日志條目，它就會拒絕接收新的日志條目。
4.2 日志複制流程
Leader 負責處理所有用戶端的請求。
Leader 把請求作為日志條目加入到它的日志中，然後并行的向其他伺服器發送 AppendEntries RPC 請求，要求 Follower 複制日志條目。
Follower 複制成功後，傳回确認消息。
當這個日志條目被半數以上的伺服器複制後，Leader 送出這個日志條目到它的複制狀态機，并向用戶端傳回執行結果。
注意：如果 Follower 崩潰或者運作緩慢，再或者網絡丢包，Leader 會不斷的重複嘗試發送 AppendEntries RPC 請求 （盡管已經回複了用戶端），直到所有的跟随者都最終複制了所有的日志條目。
下面，通過一組動圖來加深認識：
1)來自用戶端的修改都會被傳入 Leader。注意該修改還未被送出，隻是寫入日志中。
2)Leader 會把修改複制到所有 Follower。
3)Leader 會等待大多數的 Follower 也進行了修改，然後才将修改送出。
4)此時 Leader 會通知的所有 Follower 讓它們也送出修改，此時所有節點的值達成一緻。
4.3 日志一緻性
一般情況下，Leader 和 Followers 的日志保持一緻，是以日志條目一緻性檢查通常不會失敗。然而，Leader 崩潰可能會導緻日志不一緻：舊的 Leader 可能沒有完全複制完日志中的所有條目。
4.3.1 Leader 和 Follower 日志不一緻的可能
Leader 和 Follower 可能存在多種日志不一緻的可能。
圖示說明：上圖闡述了 Leader 和 Follower 可能存在多種日志不一緻的可能，每一個方框表示一個日志條目，裡面的數字表示任期号 。
當一個 Leader 成功當選時，Follower 可能出現以下情況（a-f）：
存在未更新日志條目，如（a、b）。
存在未送出日志條目，如（c、d）。
或兩種情況都存在，如（e、f）。
例如，場景 f 可能會這樣發生，某伺服器在 Term2 的時候是 Leader，已附加了一些日志條目到自己的日志中，但在送出之前就崩潰了；很快這個機器就被重新開機了，在 Term3 重新被選為 Leader，并且又增加了一些日志條目到自己的日志中；在 Term 2 和 Term 3 的日志被送出之前，這個伺服器又當機了，并且在接下來的幾個任期裡一直處于當機狀态。
4.3.2 Leader 和 Follower 日志一緻的保證
Leader 通過強制 Followers 複制它的日志來處理日志的不一緻，Followers 上的不一緻的日志會被 Leader 的日志覆寫。
Leader 為了使 Followers 的日志同自己的一緻，Leader 需要找到 Followers 同它的日志一緻的地方，然後覆寫 Followers 在該位置之後的條目。
Leader 會從後往前試，每次日志條目失敗後嘗試前一個日志條目，直到成功找到每個 Follower 的日志一緻位點，然後向後逐條覆寫 Followers 在該位置之後的條目。
五、安全性
前面描述了 Raft 算法是如何選舉 Leader 和複制日志的。
Raft 還增加了一些限制來完善 Raft 算法，以保證安全性：保證了任意 Leader 對于給定的 Term，都擁有了之前 Term 的所有被送出的日志條目。
5.1 選舉限制
擁有最新的已送出的日志條目的 Follower 才有資格成為 Leader。
Raft 使用投票的方式來阻止一個 Candidate 赢得選舉除非這個 Candidate 包含了所有已經送出的日志條目。Candidate 為了赢得選舉必須聯系叢集中的大部分節點，這意味着每一個已經送出的日志條目在這些伺服器節點中肯定存在于至少一個節點上。如果 Candidate 的日志至少和大多數的伺服器節點一樣新（這個新的定義會在下面讨論），那麼他一定持有了所有已經送出的日志條目。
RequestVote RPC 實作了這樣的限制：RequestVote RPC 中包含了 Candidate 的日志資訊， Follower 會拒絕掉那些日志沒有自己新的投票請求。
5.1.1 場如何判斷哪個日志條目比較新？
Raft 通過比較兩份日志中最後一條日志條目的日志索引和 Term 來判斷哪個日志比較新。
先判斷 Term，哪個數值大即代表哪個日志比較新。
如果 Term 相同，再比較 日志索引，哪個數值大即代表哪個日志比較新。
5.1.2 送出舊任期的日志條目
一個目前 Term 的日志條目被複制到了半數以上的伺服器上，Leader 就認為它是可以被送出的。如果這個 Leader 在送出日志條目前就下線了，後續的 Leader 可能會覆寫掉這個日志條目。
**圖示說明：**上圖解釋了為什麼 Leader 無法對舊 Term 的日志條目進行送出。
- 階段 (a) ，S1 是 Leader，且 S1 寫入日志條目為 (Term 2，日志索引 2），隻有 S2 複制了這個日志條目。
- 階段 (b)，S1 下線，S5 被選舉為 Term3 的 Leader。S5 寫入日志條目為 (Term 3，日志索引 2）。
- 階段 (c)，S5 下線，S1 重新上線，并被選舉為 Term4 的 Leader。此時，Term 2 的那條日志條目已經被複制到了叢集中的大多數節點上，但是還沒有被送出。
- 階段 (d)，S1 再次下線，S5 重新上線，并被重新選舉為 Term3 的 Leader。然後 S5 覆寫了日志索引 2 處的日志。
- 階段 (e)，如果階段 (d) 還未發生，即 S1 再次下線之前，S1 把自己主導的日志條目複制到了大多數節點上，那麼在後續 Term 裡面這些新日志條目就會被送出。這樣在同一時刻就同時保證了，之前的所有舊日志條目就會被送出。
Raft 永遠不會通過計算副本數目的方式去送出一個之前 Term 内的日志條目。隻有 Leader 目前 Term 裡的日志條目通過計算副本數目可以被送出；一旦目前 Term 的日志條目以這種方式被送出，那麼由于日志比對特性，之前的日志條目也都會被間接的送出。
當 Leader 複制之前任期裡的日志時，Raft 會為所有日志保留原始的 Term，這在送出規則上産生了額外的複雜性。在其他的一緻性算法中，如果一個新的上司人要重新複制之前的任期裡的日志時，它必須使用目前新的任期号。
Raft 使用的方法更加容易辨識出日志，因為它可以随着時間和日志的變化對日志維護着同一個任期編号。另外，和其他的算法相比，Raft 中的新上司人隻需要發送更少日志條目（其他算法中必須在他們被送出之前發送更多的備援日志條目來為他們重新編号）。
六、日志壓縮
在實際的系統中，不能讓日志無限膨脹，否則系統重新開機時需要花很長的時間進行恢複，進而影響可用性。Raft 采用對整個系統進行快照來解決，快照之前的日志都可以丢棄。
每個副本獨立的對自己的系統狀态生成快照，并且隻能對已經送出的日志條目生成快照。快照包含以下内容：
日志中繼資料。最後一條已送出的日志條目的日志索引和 Term。這兩個值在快照之後的第一條日志條目的 AppendEntries RPC 的完整性檢查的時候會被用上。
系統目前狀态。
當 Leader 要發送某個日志條目，落後太多的 Follower 的日志條目會被丢棄，Leader 會将快照發給 Follower。或者新上線一台機器時，也會發送快照給它。
生成快照的頻率要适中，頻率過高會消耗大量 I/O 帶寬；頻率過低，一旦需要執行恢複操作，會丢失大量資料，影響可用性。推薦當日志達到某個固定的大小時生成快照。生成一次快照可能耗時過長，影響正常日志同步。可以通過使用 copy-on-write 技術避免快照過程影響正常日志同步。
說明：本文僅闡述 Raft 算法的核心内容，不包括算法論證、評估等
七、參考資料
1.Raft 一緻性算法論文原文
2.Raft 一緻性算法論文譯文
3.Raft 作者講解視訊
4.Raft 作者講解視訊對應的 PPT
5.分布式系統的 Raft 算法
6.Raft 算法詳解