分布式共識(shí)算法

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

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

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

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

順序一致性

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

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

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

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

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

線性一致性

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

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

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

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

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

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

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

因果一致性

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

Raft 算法

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

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

原理概覽

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

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

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

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

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

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

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

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

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

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

選舉機(jī)制

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

• 新加入節(jié)點(diǎn)
• leader 掉線
• 多個(gè)follower同時(shí)超時(shí)

新節(jié)點(diǎn)加入

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

leader 掉線處理

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

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

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

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

多個(gè) follower 同時(shí)掉線

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

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

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

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

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

之后A、B、D 因?yàn)楫?dāng)前的B也沒有支持者，所以就會(huì)支持B，B順利成為leader。

日志復(fù)制

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

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

1、follower 會(huì)使用前一個(gè)日志的任期號(hào)和日志索引來對(duì)比自己的數(shù)據(jù)：

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

2、leader 收到拒絕復(fù)制的回復(fù)后，繼續(xù)發(fā)送節(jié)點(diǎn)日志復(fù)制請(qǐng)求，不過這次會(huì)帶上更前面的一個(gè)日志任期號(hào)和索引；

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

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

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