分布式共識算法

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

這就要從當(dāng)前的分布式系統(tǒng)設(shè)計的缺陷來看了，假設(shè)我們的集群現(xiàn)在有兩個客戶端和三個服務(wù)端，如下圖：

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

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

順序一致性

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

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

假設(shè)客戶端A有兩條命令：

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

那么如果服務(wù)端那邊收到的節(jié)點只要滿足command2在command1后面執(zhí)行并且comand4在command3后面執(zhí)行我們就認(rèn)為其滿足順序一致性。

線性一致性

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

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

客戶端A發(fā)送的命令如下：

客戶端B發(fā)送的命令如下：

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

所以，假設(shè)初始值x = 0，而我們到達(dá)的順序如下：

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

因果一致性

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

Raft 算法

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

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

原理概覽

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

• leader：領(lǐng)導(dǎo)者，其負(fù)責(zé)和客戶端通信，接收來自客戶端的命令并將其轉(zhuǎn)發(fā)給follower
• follower：跟隨者，其一絲不茍的執(zhí)行來自leader的命令
• candidate：候選者，當(dāng)follower長時間沒收到 leader的消息就會揭竿而起成為候選者，搶奪成為leader的資格

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

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

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

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

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

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

但是這只是個概況，我們還缺了億點點細(xì)節(jié)：

• 選舉機制
• 日志復(fù)制

選舉機制

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

• 新加入節(jié)點
• leader 掉線
• 多個follower同時超時

新節(jié)點加入

當(dāng)有一個節(jié)點加入當(dāng)前的分布式集群的時候，leader會檢測并發(fā)現(xiàn)它并給他發(fā)送消息。使其加入此分布式集群。

leader 掉線處理

假設(shè)我們現(xiàn)在的服務(wù)器A掉線，由于沒有l(wèi)eader維持心跳消息，這個時候服務(wù)器B和C會進入超時倒計時的狀態(tài)。

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

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

之后節(jié)點B順利成為leader。

多個 follower 同時掉線

現(xiàn)在假設(shè)有4個節(jié)點：A、B、C、D。其中A和D的超時時間是相同的。

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

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

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

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

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

日志復(fù)制

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

而當(dāng)follower 收到日志復(fù)制命令會執(zhí)行處理流程：

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

1. 如果相同，接收復(fù)制請求，回復(fù) ok；
2. 否則回拒絕復(fù)制當(dāng)前日志，回復(fù) error；

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

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

日志復(fù)制過程中，Leader 會無限重試直到成功。如果超過半數(shù)的節(jié)點復(fù)制日志成功，就可以任務(wù)當(dāng)前數(shù)據(jù)請求達(dá)成了共識，即日志可以 commite 提交了；

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