⑴ Raft演算法
Raft演算法是解決分布式系統共識的問題的演算法，Raft是基於Multi-Paxos的基礎上做了簡化和限制。不同於Paxos的難以理解，Raft設計的首要目的就是可理解性，一個易於理解、實現簡單的分布式一致性協議。
Raft 將一致性演算法分解成了幾個關鍵模塊，例如領導人選舉、日誌復制和安全性，本文將主要基於 raft論文 簡單分析raft演算法。
Raft是強領導(Strong leader)模型，一切以leader為主，比如日誌只能由leader復制到其他伺服器。所以leader的選舉是非常重要的一部分。
首先介紹raft演算法的三個服務狀態：
任意時間集群中只能由一個leader存在。
Raft使用心跳機制實現leader選舉。在服務啟動的時候，處於follower角色，需要注意的是每個服務於leader的心跳超時的時間是隨機的(150-300 毫秒)。
如上圖，集群中有三個幾點A、B、C，超時時間分別為150ms、200ms、300ms剛啟動時任期編號都是0，都處於follower角色。節點A與leader的心跳超時時間最短，最先從follower狀態轉為candidate，並增加自己的任期編號，先給自己投上一張選票，並向集群中其他節點發送投票信息，當B、C節點接受到A的投票請求之後，在任期為1的這個階段沒有給其他節點投過票，便接受A的投票請求。此時節點A接受到了集群中超過一半的節點的投票，便成為任期為1的leader。
上訴是最簡單的選舉流程，裡面有很多概念都需要解釋，比如為什麼超時時間不一樣？任期編號是什麼？投票比較的規則又是什麼？
1. 任期編號
每個leader在當選期間都有一個自己的任期編號，它是全局單調遞增的數字。每個節點都存儲這當前的leader的任期編號，當處於candidate階段的時候，發起投票的時候會把當前任期編號加一。
而且當一個節點接受到比自己任期高的請求時，會將自己的任期編號更新為高的任期編號，如果當前角色是leader，會從leader轉換為follower角色。當接受到任期編號比自己小的請求時，節點會直接拒絕這個請求。
2. 投票比較規則
a. 先到先服務：一個節點在一個任期只能投一票，如果A、B節點都請求C節點投票，C節點如果先投給A之後、就會拒絕B的投票請求。
b.日誌完整性：一個節點接受的投票信息如果它的日誌比自身小，將會拒絕該投票請求。
c.過半策略：當某節點接受到了集群中超過一半的節點投票之後，成為該次任期的leader，向其他節點發送leader心跳。
d. 在等待投票期間，candidate 可能會收到另一個聲稱自己是 leader 的伺服器節點發來的 AppendEntries RPC 。如果這個 leader 的任期號（包含在RPC中）不小於 candidate 當前的任期號，那麼 candidate 會承認該 leader 的合法地位並回到 follower 狀態。
3.隨機超時
前面提高過，每個幾點與leader的心跳超時時間是不同的，這樣的好處在於避免瓜分票數的情況存在，能快速的進行leader選舉。如果各個節點的超時時間都是一樣的，就容易出現瓜分票數的情況存在，每個節點都沒有獲得超過一半的投票，就會開啟下一輪的選舉，選舉時間就會很長。使用隨機超時機制，正常情況下，一個時間段里只有一個節點發起投票請求。
下圖是整個集群中服務角色變化的流程圖。
Leader選舉出來之後為客戶端提供服務，將接受到的指令作為一個新的日誌項追加到日誌中去，然後並行的發起 AppendEntries RPC 給其他的伺服器，讓它們復制該日誌項。當該日誌項被安全地復制（過半的節點已復制完成），leader 會應用該日誌項到它的狀態機中（狀態機執行該指令）然後把執行的結果返回給客戶端。如果 follower 崩潰或者運行緩慢，或者網路丟包，領導人會不斷地重試 AppendEntries RPC（即使已經回復了客戶端）直到所有的 follower 最終都存儲了所有的日誌。
上圖展示了日誌的格式，一個日誌項包含三部分
Leader通過 AppendEntries RPC 將日誌復制到其他節點。
AppendEntries RPC：
接收者實現：
上訴是AppendEntries RPC的參數的接受流程。term與leaderId不用介紹很簡單，而prevLogIndex、prevLogTerm的作用是日誌的一致性檢測，如果 follower 在它的日誌中找不到包含相同索引位置和任期號的條目，那麼他就會拒絕該新的日誌條目。一致性檢查就像一個歸納步驟：一開始空的日誌狀態肯定是滿足 Log Matching Property（日誌匹配特性） 的，然後一致性檢查保證了日誌擴展時的日誌匹配特性。因此，每當 AppendEntries RPC 返回成功時，leader 就知道 follower 的日誌一定和自己相同（從第一個日誌條目到最新條目）。
正常操作期間，leader 和 follower 的日誌保持一致，所以 AppendEntries RPC 的一致性檢查從來不會失敗。然而，leader 崩潰的情況會使日誌處於不一致的狀態（老的 leader 可能還沒有完全復制它日誌里的所有條目）。如下情況：
在 Raft 演算法中，leader 通過強制 follower 復制它的日誌來解決不一致的問題。這意味著 follower 中跟 leader 沖突的日誌條目會被 leader 的日誌條目覆蓋。
Leader 針對每一個 follower 都維護了一個 nextIndex ，表示 leader 要發送給 follower 的下一個日誌條目的索引。當選出一個新 leader 時，該 leader 將所有 nextIndex 的值都初始化為自己最後一個日誌條目的 index 加1。如果 follower 的日誌和 leader 的不一致，那麼下一次 AppendEntries RPC 中的一致性檢查就會失敗。在被 follower 拒絕之後，leaer 就會減小 nextIndex 值並重試 AppendEntries RPC 。最終 nextIndex 會在某個位置使得 leader 和 follower 的日誌達成一致。此時，AppendEntries RPC 就會成功，將 follower 中跟 leader 沖突的日誌條目全部刪除然後追加 leader 中的日誌條目（如果有需要追加的日誌條目的話）。一旦 AppendEntries RPC 成功，follower 的日誌就和 leader 一致，並且在該任期接下來的時間里保持一致。
本機簡單介紹了raft 的leader選舉和日誌復制，當然raft還有其他的特性本文並沒有介紹，推薦去看raft的論文，完整的了解raft。
我之前 ZAB協議 的文章分析了zookeeper的zab協議，這里對比一下兩者的異同。
最後 https://raft.github.io 這個網址詳細介紹了raft協議。
https://time.geekbang.org/column/intro/279
https://raft.github.io/
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
⑵ Raft 演算法（詳細版）
在分布式系統中，一致性演算法至關重要。在所有一致性演算法中，Paxos 最負盛名，它由萊斯利·蘭伯特（Leslie Lamport）於 1990 年提出，是一種基於消息傳遞的一致性演算法，被認為是類似演算法中最有效的。
Paxos 演算法雖然很有效，但復雜的原理使它實現起來非常困難，截止目前，實現 Paxos 演算法的開源軟體很少，比較出名的有 Chubby、LibPaxos。此外，Zookeeper 採用的 ZAB（Zookeeper Atomic Broadcast）協議也是基於 Paxos 演算法實現的，不過 ZAB 對 Paxos 進行了很多改進與優化，兩者的設計目標也存在差異——ZAB 協議主要用於構建一個高可用的分布式數據主備系統，而 Paxos 演算法則是用於構建一個分布式的一致性狀態機系統。
由於 Paxos 演算法過於復雜、實現困難，極大地制約了其應用，而分布式系統領域又亟需一種高效而易於實現的分布式一致性演算法，在此背景下，Raft 演算法應運而生。
Raft 演算法在斯坦福 Diego Ongaro 和 John Ousterhout 於 2013 年發表的《In Search of an Understandable Consensus Algorithm》中提出。相較於 Paxos，Raft 通過邏輯分離使其更容易理解和實現，目前，已經有十多種語言的 Raft 演算法實現框架，較為出名的有 etcd、Consul 。
根據官方文檔解釋，一個 Raft 集群包含若干節點，Raft 把這些節點分為三種狀態：Leader、 Follower、Candidate，每種狀態負責的任務也是不一樣的。正常情況下，集群中的節點只存在 Leader 與 Follower 兩種狀態。
• Leader（領導者） ：負責日誌的同步管理，處理來自客戶端的請求，與Follower保持heartBeat的聯系；
• Follower（追隨者） ：響應 Leader 的日誌同步請求，響應Candidate的邀票請求，以及把客戶端請求到Follower的事務轉發（重定向）給Leader；
• Candidate（候選者） ：負責選舉投票，集群剛啟動或者Leader宕機時，狀態為Follower的節點將轉為Candidate並發起選舉，選舉勝出（獲得超過半數節點的投票）後，從Candidate轉為Leader狀態。
通常，Raft 集群中只有一個 Leader，其它節點都是 Follower。Follower 都是被動的，不會發送任何請求，只是簡單地響應來自 Leader 或者 Candidate 的請求。Leader 負責處理所有的客戶端請求（如果一個客戶端和 Follower 聯系，那麼 Follower 會把請求重定向給 Leader）。
為簡化邏輯和實現，Raft 將一致性問題分解成了三個相對獨立的子問題。
• 選舉（Leader Election） ：當 Leader 宕機或者集群初創時，一個新的 Leader 需要被選舉出來；
• 日誌復制（Log Replication） ：Leader 接收來自客戶端的請求並將其以日誌條目的形式復制到集群中的其它節點，並且強制要求其它節點的日誌和自己保持一致；
• 安全性（Safety） ：如果有任何的伺服器節點已經應用了一個確定的日誌條目到它的狀態機中，那麼其它伺服器節點不能在同一個日誌索引位置應用一個不同的指令。
根據 Raft 協議，一個應用 Raft 協議的集群在剛啟動時，所有節點的狀態都是 Follower。由於沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），因此，Followers 會認為 Leader 已經下線，進而轉為 Candidate 狀態。然後，Candidate 將向集群中其它節點請求投票，同意自己升級為 Leader。如果 Candidate 收到超過半數節點的投票（N/2 + 1），它將獲勝成為 Leader。
第一階段：所有節點都是 Follower。
上面提到，一個應用 Raft 協議的集群在剛啟動（或 Leader 宕機）時，所有節點的狀態都是 Follower，初始 Term（任期）為 0。同時啟動選舉定時器，每個節點的選舉定時器超時時間都在 100~500 毫秒之間且並不一致（避免同時發起選舉）。
第二階段：Follower 轉為 Candidate 並發起投票。
沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），節點啟動後在一個選舉定時器周期內未收到心跳和投票請求，則狀態轉為候選者 Candidate 狀態，且 Term 自增，並向集群中所有節點發送投票請求並且重置選舉定時器。
注意，由於每個節點的選舉定時器超時時間都在 100-500 毫秒之間，且彼此不一樣，以避免所有 Follower 同時轉為 Candidate 並同時發起投票請求。換言之，最先轉為 Candidate 並發起投票請求的節點將具有成為 Leader 的「先發優勢」。
第三階段：投票策略。
節點收到投票請求後會根據以下情況決定是否接受投票請求（每個 follower 剛成為 Candidate 的時候會將票投給自己）：
請求節點的 Term 大於自己的 Term，且自己尚未投票給其它節點，則接受請求，把票投給它；
請求節點的 Term 小於自己的 Term，且自己尚未投票，則拒絕請求，將票投給自己。
第四階段：Candidate 轉為 Leader。
一輪選舉過後，正常情況下，會有一個 Candidate 收到超過半數節點（N/2 + 1）的投票，它將勝出並升級為 Leader。然後定時發送心跳給其它的節點，其它節點會轉為 Follower 並與 Leader 保持同步，到此，本輪選舉結束。
注意：有可能一輪選舉中，沒有 Candidate 收到超過半數節點投票，那麼將進行下一輪選舉。
在一個 Raft 集群中，只有 Leader 節點能夠處理客戶端的請求（如果客戶端的請求發到了 Follower，Follower 將會把請求重定向到 Leader） ，客戶端的每一個請求都包含一條被復制狀態機執行的指令。Leader 把這條指令作為一條新的日誌條目（Entry）附加到日誌中去，然後並行得將附加條目發送給 Followers，讓它們復制這條日誌條目。
當這條日誌條目被 Followers 安全復制，Leader 會將這條日誌條目應用到它的狀態機中，然後把執行的結果返回給客戶端。如果 Follower 崩潰或者運行緩慢，再或者網路丟包，Leader 會不斷得重復嘗試附加日誌條目（盡管已經回復了客戶端）直到所有的 Follower 都最終存儲了所有的日誌條目，確保強一致性。
第一階段：客戶端請求提交到 Leader。
如下圖所示，Leader 收到客戶端的請求，比如存儲數據 5。Leader 在收到請求後，會將它作為日誌條目（Entry）寫入本地日誌中。需要注意的是，此時該 Entry 的狀態是未提交（Uncommitted），Leader 並不會更新本地數據，因此它是不可讀的。
第二階段：Leader 將 Entry 發送到其它 Follower
Leader 與 Followers 之間保持著心跳聯系，隨心跳 Leader 將追加的 Entry（AppendEntries）並行地發送給其它的 Follower，並讓它們復制這條日誌條目，這一過程稱為復制（Replicate）。
有幾點需要注意：
1. 為什麼 Leader 向 Follower 發送的 Entry 是 AppendEntries 呢？
因為 Leader 與 Follower 的心跳是周期性的，而一個周期間 Leader 可能接收到多條客戶端的請求，因此，隨心跳向 Followers 發送的大概率是多個 Entry，即 AppendEntries。當然，在本例中，我們假設只有一條請求，自然也就是一個Entry了。
2. Leader 向 Followers 發送的不僅僅是追加的 Entry（AppendEntries）。
在發送追加日誌條目的時候，Leader 會把新的日誌條目緊接著之前條目的索引位置（prevLogIndex）， Leader 任期號（Term）也包含在其中。如果 Follower 在它的日誌中找不到包含相同索引位置和任期號的條目，那麼它就會拒絕接收新的日誌條目，因為出現這種情況說明 Follower 和 Leader 不一致。
3. 如何解決 Leader 與 Follower 不一致的問題？
在正常情況下，Leader 和 Follower 的日誌保持一致，所以追加日誌的一致性檢查從來不會失敗。然而，Leader 和 Follower 一系列崩潰的情況會使它們的日誌處於不一致狀態。Follower可能會丟失一些在新的 Leader 中有的日誌條目，它也可能擁有一些 Leader 沒有的日誌條目，或者兩者都發生。丟失或者多出日誌條目可能會持續多個任期。
要使 Follower 的日誌與 Leader 恢復一致，Leader 必須找到最後兩者達成一致的地方（說白了就是回溯，找到兩者最近的一致點），然後刪除從那個點之後的所有日誌條目，發送自己的日誌給 Follower。所有的這些操作都在進行附加日誌的一致性檢查時完成。
Leader 為每一個 Follower 維護一個 nextIndex，它表示下一個需要發送給 Follower 的日誌條目的索引地址。當一個 Leader 剛獲得權力的時候，它初始化所有的 nextIndex 值，為自己的最後一條日誌的 index 加 1。如果一個 Follower 的日誌和 Leader 不一致，那麼在下一次附加日誌時一致性檢查就會失敗。在被 Follower 拒絕之後，Leader 就會減小該 Follower 對應的 nextIndex 值並進行重試。最終 nextIndex 會在某個位置使得 Leader 和 Follower 的日誌達成一致。當這種情況發生，附加日誌就會成功，這時就會把 Follower 沖突的日誌條目全部刪除並且加上 Leader 的日誌。一旦附加日誌成功，那麼 Follower 的日誌就會和 Leader 保持一致，並且在接下來的任期繼續保持一致。
第三階段：Leader 等待 Followers 回應。
Followers 接收到 Leader 發來的復制請求後，有兩種可能的回應：
寫入本地日誌中，返回 Success；
一致性檢查失敗，拒絕寫入，返回 False，原因和解決辦法上面已做了詳細說明。
需要注意的是，此時該 Entry 的狀態也是未提交（Uncommitted）。完成上述步驟後，Followers 會向 Leader 發出 Success 的回應，當 Leader 收到大多數 Followers 的回應後，會將第一階段寫入的 Entry 標記為提交狀態（Committed），並把這條日誌條目應用到它的狀態機中。
第四階段：Leader 回應客戶端。
完成前三個階段後，Leader會向客戶端回應 OK，表示寫操作成功。
第五階段，Leader 通知 Followers Entry 已提交
Leader 回應客戶端後，將隨著下一個心跳通知 Followers，Followers 收到通知後也會將 Entry 標記為提交狀態。至此，Raft 集群超過半數節點已經達到一致狀態，可以確保強一致性。
需要注意的是，由於網路、性能、故障等各種原因導致「反應慢」、「不一致」等問題的節點，最終也會與 Leader 達成一致。
前面描述了 Raft 演算法是如何選舉 Leader 和復制日誌的。然而，到目前為止描述的機制並不能充分地保證每一個狀態機會按照相同的順序執行相同的指令。例如，一個 Follower 可能處於不可用狀態，同時 Leader 已經提交了若乾的日誌條目；然後這個 Follower 恢復（尚未與 Leader 達成一致）而 Leader 故障；如果該 Follower 被選舉為 Leader 並且覆蓋這些日誌條目，就會出現問題，即不同的狀態機執行不同的指令序列。
鑒於此，在 Leader 選舉的時候需增加一些限制來完善 Raft 演算法。這些限制可保證任何的 Leader 對於給定的任期號（Term），都擁有之前任期的所有被提交的日誌條目（所謂 Leader 的完整特性）。關於這一選舉時的限制，下文將詳細說明。
在所有基於 Leader 機制的一致性演算法中，Leader 都必須存儲所有已經提交的日誌條目。為了保障這一點，Raft 使用了一種簡單而有效的方法，以保證所有之前的任期號中已經提交的日誌條目在選舉的時候都會出現在新的 Leader 中。換言之，日誌條目的傳送是單向的，只從 Leader 傳給 Follower，並且 Leader 從不會覆蓋自身本地日誌中已經存在的條目。
Raft 使用投票的方式來阻止一個 Candidate 贏得選舉，除非這個 Candidate 包含了所有已經提交的日誌條目。Candidate 為了贏得選舉必須聯系集群中的大部分節點。這意味著每一個已經提交的日誌條目肯定存在於至少一個伺服器節點上。如果 Candidate 的日誌至少和大多數的伺服器節點一樣新（這個新的定義會在下面討論），那麼它一定持有了所有已經提交的日誌條目（多數派的思想）。投票請求的限制中請求中包含了 Candidate 的日誌信息，然後投票人會拒絕那些日誌沒有自己新的投票請求。
Raft 通過比較兩份日誌中最後一條日誌條目的索引值和任期號，確定誰的日誌比較新。如果兩份日誌最後條目的任期號不同，那麼任期號大的日誌更加新。如果兩份日誌最後的條目任期號相同，那麼日誌比較長的那個就更加新。
如同 4.1 節介紹的那樣，Leader 知道一條當前任期內的日誌記錄是可以被提交的，只要它被復制到了大多數的 Follower 上（多數派的思想）。如果一個 Leader 在提交日誌條目之前崩潰了，繼任的 Leader 會繼續嘗試復制這條日誌記錄。然而，一個 Leader 並不能斷定被保存到大多數 Follower 上的一個之前任期里的日誌條目 就一定已經提交了。這很明顯，從日誌復制的過程可以看出。
鑒於上述情況，Raft 演算法不會通過計算副本數目的方式去提交一個之前任期內的日誌條目。只有 Leader 當前任期里的日誌條目通過計算副本數目可以被提交；一旦當前任期的日誌條目以這種方式被提交，那麼由於日誌匹配特性，之前的日誌條目也都會被間接的提交。在某些情況下，Leader 可以安全地知道一個老的日誌條目是否已經被提交（只需判斷該條目是否存儲到所有節點上），但是 Raft 為了簡化問題使用了一種更加保守的方法。
當 Leader 復制之前任期里的日誌時，Raft 會為所有日誌保留原始的任期號，這在提交規則上產生了額外的復雜性。但是，這種策略更加容易辨別出日誌，即使隨著時間和日誌的變化，日誌仍維護著同一個任期編號。此外，該策略使得新 Leader 只需要發送較少日誌條目。
raft 的讀寫都在 leader 節點中進行，它保證了讀的都是最新的值，它是符合強一致性的（線性一致性），raft 除了這個還在【客戶端交互】那塊也做了一些保證，詳情可以參考論文。但是 zookeeper 不同，zookeeper 寫在 leader，讀可以在 follower 進行，可能會讀到了舊值，它不符合強一致性（只考慮寫一致性，不考慮讀一致性），但是 zookeeper 去 follower 讀可以有效提升讀取的效率。
對比於 zab、raft，我們發現他們選舉、setData 都是需要過半機制才行，所以他們針對網路分區的處理方法都是一樣的。
一個集群的節點經過網路分區後，如一共有 A、B、C、D、E 5個節點，如果 A 是 leader，網路分區為 A、B、C 和 D、E，在A、B、C分區還是能正常提供服務的，而在 D、E 分區因為不能得到大多數成員確認（雖然分區了，但是因為配置的原因他們還是能知道所有的成員數量，比如 zk 集群啟動前需要配置所有成員地址，raft 也一樣），是不能進行選舉的，所以保證只會有一個 leader。
如果分區為 A、B 和 C、D、E ，A、B 分區雖然 A 還是 leader，但是卻不能提供事務服務（setData），C、D、E 分區能重新選出 leader，還是能正常向外提供服務。
1）我們所說的日誌（log）與狀態機（state machine）不是一回事，日誌指還沒有提交到狀態機中的數據。
2）新 leader 永遠不會通過計算副本數量提交舊日誌，他只能復制舊日誌都其他 follower 上，對於舊日誌的提交，只能是新 leader 接收新的寫請求寫新日誌，順帶著把舊日誌提交了。