分布式共識算法

首先我們先明確這個問題：為什么需要分布式共識算法？

這就要從當前的分布式系統設計的缺陷來看了，假設我們的集群現在有兩個客戶端和三個服務端，如下圖：

在這個分布式系統的設計中，往往要滿足CAP理論，而分布式共識算法解決的就是CAP理論中的一致性問題。整個一致性問題分為三種問題：

• 順序一致性
• 線性一致性
• 因果一致性

順序一致性

順序一致性是1979年Lamport 在論文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 》中提出：：假設執行結果與這些處理器以某一串行順序執行的結果相同，同時每個處理器內部操作的執行看起來又與程序描述的順序一致。滿足該條件的多處理器系統我們就認為是順序一致的。實際上，處理器可以看做一個進程或者一個線程，甚至是一個分布式系統。

這句話并不是很好理解，我們看一下分布式系統中順序一致性的一個例子：

假設客戶端A有兩條命令：

客戶端B有一下兩條命令：

那么如果服務端那邊收到的節點只要滿足command2在command1后面執行并且comand4在command3后面執行我們就認為其滿足順序一致性。

線性一致性

線性一致性或稱原子一致性或嚴格一致性，指的是程序在執行順序組合中存在可線性化點P的執行模型，這意味著一個操作將在程序的調用和返回之間的某個點P生效，之后被系統中并發運行的所有其他線程所感知。線性一致性概念是1990年 Maurice Herlihy · Jeannette M Wing 在論文《Linearizability: A Correctness Condition for Concurrent Objects》中提出。

通俗來講，線性一致性可以說是順序一致性的升級版。其會有一個全局時鐘，假設還是上面發送的命令，只不過加上了時間信息：

客戶端A發送的命令如下：

客戶端B發送的命令如下：

注：這里假設時延可能是幾分鐘級別的，所以有可能是command3在command1之前到

所以，假設初始值x = 0，而我們到達的順序如下：

這個順序確實是滿足順序一致性，但是我們get(x)獲得的值可謂是千奇百怪，可能是0，1，3 。為了解決順序一致性的不足，所以才提出的線性一致性。其要求命令滿足全局時鐘的時序性。所以很容易就知道，滿足線性一致性的一定滿足順序一致性；相反，滿足順序一致性的不一定會滿足線性一致性。

因果一致性

線性一致性要求所有線程的操作按照一個絕對的時鐘順序執行，這意味著線性一致性是限制并發的，否則這種順序性就無法保證。由于在真實環境中很難保證絕對時鐘同步，因此線性一致性是一種理論。實現線性一致性的代價也最高，但是實戰中可以弱化部分線性一致性：只保證有因果關系的事件的順序，沒有因果關系的事件可以并發執行，其指的是假設有兩個事件：A事件和B事件，如果A發生在B后面，那么就稱A和B具有因果關系。

Raft 算法

Paxos和Raft這些分布式共識算法就是用來多個節點之間達成共識的，其可以解決一定的一致性問題。其中Paxos難以理解，所以這篇博客以介紹Raft算法為主。

Raft是工程上使用較為廣泛的強一致性、去中心化、高可用的分布式協議。遵從此協議的分布式集群會對某個事情達成一致的看法，即使是在部分節點故障、網絡延時、網絡分割的情況下。

原理概覽

遵循Raft算法的分布式集群中每個節點扮演以下三種角色之一：

• leader：領導者，其負責和客戶端通信，接收來自客戶端的命令并將其轉發給follower
• follower：跟隨者，其一絲不茍的執行來自leader的命令
• candidate：候選者，當follower長時間沒收到 leader的消息就會揭竿而起成為候選者，搶奪成為leader的資格

從上面的描述我們可以看到節點的角色不是固定的，其會在三個角色中轉換。我們舉個例子來說，假設我們有三個節點A、B、C，它們的基本信息如下圖中。一開始所有的節點都是follower狀態，并且處于時期0這個狀態。

注：在Raft算法中，所有節點會被分配不同的超時時間，時間限定在150ms~300ms之間。為什么這么設置是因為如果設置相同的超時時間就會導致所有節點同時過期會導致遲遲選不出leader，看到后面就會明白。

150ms過去之后，A發現怎么leader沒跟我聯絡聯絡感情，是不是leader已經寄了？王侯將相寧有種乎！于是A成為候選人給自己投了一票并開創自己的時代時期 1，并給其他還沒過期的follower發送信息請求它們支持自己當leader。

節點B和C在收到來自A的消息之后，又沒有收到其他要求稱王者的信息，于是就選擇支持A節點，加入A的時代并刷新自己的剩余時間。

之后 A得到了超過一半的節點支持，成為leader，并定時給B和C聯絡聯絡感情（心跳信息）目的是防止有節點因為長時間收不到開始反叛成candidate。

之后整個分布式集群就可以和客戶端開始通信了，客戶端會發送消息給leader，之后leader會保證集群的一致性并且當整個集群中的一半節點都完成客戶端發送的命令之后才會真正的返回給客戶端，表示完成此次命令。

但是這只是個概況，我們還缺了億點點細節：

• 選舉機制
• 日志復制

選舉機制

剛剛我們講了最普通的一個選舉過程，但是我們可能還會遇到一些特殊情況：

• 新加入節點
• leader 掉線
• 多個follower同時超時

新節點加入

當有一個節點加入當前的分布式集群的時候，leader會檢測并發現它并給他發送消息。使其加入此分布式集群。

leader 掉線處理

假設我們現在的服務器A掉線，由于沒有leader維持心跳消息，這個時候服務器B和C會進入超時倒計時的狀態。

200ms過去，服務器B開始超時了，這個時候它揭竿而起成為candidate，并向節點C發送消息請求其支持自己成為leader。

之后，在一系列判斷條件之后（后面會講），節點C會回復節點B的請求信息。插句題外話哈，在B還沒收到C的回復消息之前，假設A只是剛剛網絡不通暢，現在死而復生，給B發送消息了。那么B發現A的時期比自己落后了，這還等什么？！蒼天已死，黃天當立，之后反手將其收為小弟。

之后節點B順利成為leader。

多個 follower 同時掉線

現在假設有4個節點：A、B、C、D。其中A和D的超時時間是相同的。

150ms過后，A和D同時成為candidate，爭相為了成為leader給B和C發消息。

這個時候有對于B和C有兩個選擇，一個是它們一起支持兩個中的一次，也就是要么支持A要么支持D，這樣這樣其中一個就會成為leader，我們假設它們兩個都支持A。

另外一種選擇就是，A和D各的一票支持，它們的支持者跟進它們各自的leader的時期，然后本輪選舉結束。

之后50ms過去之后，B的超時時間過期了，其獲得candiate的資格，這個時候其會向其他follower發送消息請求支持。

之后A、B、D 因為當前的B也沒有支持者，所以就會支持B，B順利成為leader。

日志復制

當我們的集群leader 選舉之后。Leader 接收所有客戶端請求，然后轉化為 log 復制命令，發送通知其他節點完成日志復制請求。每個日志復制請求包括狀態機命令 & 任期號，同時還有前一個日志的任期號和日志索引。狀態機命令表示客戶端請求的數據操作指令，任期號表示 leader 的當前任期，任期也就是上圖中的時期。

而當follower 收到日志復制命令會執行處理流程：

1、follower 會使用前一個日志的任期號和日志索引來對比自己的數據：

1. 如果相同，接收復制請求，回復 ok；
2. 否則回拒絕復制當前日志，回復 error；

2、leader 收到拒絕復制的回復后，繼續發送節點日志復制請求，不過這次會帶上更前面的一個日志任期號和索引；

3、如此循環往復，直到找到一個共同的任期號&日志索引。此時 follower 從這個索引值開始復制，最終和 leader 節點日志保持一致；

日志復制過程中，Leader 會無限重試直到成功。如果超過半數的節點復制日志成功，就可以任務當前數據請求達成了共識，即日志可以 commite 提交了；

注：這里要提到的一點就是，如果follower發現canidate的日志還沒有自己的新（索引號沒自己大），其是不會支持其成為leader的。