分布式一致性

想象一下，我們有一個(gè)單節(jié)點(diǎn)系統(tǒng)馍悟，且作為數(shù)據(jù)庫(kù)服務(wù)器畔濒，然后存儲(chǔ)了一個(gè)值（假設(shè)為X）。然后锣咒，有一個(gè)客戶(hù)端往服務(wù)器發(fā)送了一個(gè)值（假設(shè)為8）篓冲。只要服務(wù)器接受到這個(gè)值即可，這個(gè)值在單節(jié)點(diǎn)上的一致性非常容易保證：

image

但是宠哄，如果數(shù)據(jù)庫(kù)服務(wù)器有多個(gè)節(jié)點(diǎn)呢？比如嗤攻，如下圖所示毛嫉，有三個(gè)節(jié)點(diǎn)：a，b妇菱，c承粤。這時(shí)候客戶(hù)端對(duì)這個(gè)由3個(gè)節(jié)點(diǎn)組成的數(shù)據(jù)庫(kù)集群進(jìn)行操作時(shí)的值一致性如何保證，這就是分布式一致性問(wèn)題闯团。而Raft就是一種實(shí)現(xiàn)了分布式一致性的協(xié)議（還有其他一些一致性算法辛臊，例如：ZAB、PAXOS等）：

image

一些概念

講解Raft算法之前房交，先普及一些Raft協(xié)議涉及到的概念：
term：任期彻舰，比如新的選舉任期，即整個(gè)集群初始化時(shí)，或者新的Leader選舉就會(huì)開(kāi)始一個(gè)新的選舉任期刃唤。
大多數(shù)：假設(shè)一個(gè)集群由N個(gè)節(jié)點(diǎn)組成隔心，那么大多數(shù)就是至少N/2+1。例如：3個(gè)節(jié)點(diǎn)的集群尚胞，大多數(shù)就是至少2硬霍；5個(gè)節(jié)點(diǎn)的集群，大多數(shù)就是至少3笼裳。
狀態(tài)：每個(gè)節(jié)點(diǎn)有三種狀態(tài)唯卖，且某一時(shí)刻只能是三種狀態(tài)中的一種：Follower（圖左），Candidate（圖中）躬柬，Leader（圖右）拜轨。假設(shè)三種狀態(tài)不同圖案如下所示：

image

初始化狀態(tài)時(shí)，三個(gè)節(jié)點(diǎn)都是Follower狀態(tài)楔脯，并且term為0撩轰，如下圖所示：

image

Leader選舉

Leader選舉需要某個(gè)節(jié)點(diǎn)發(fā)起投票，在確定哪個(gè)節(jié)點(diǎn)向其他節(jié)點(diǎn)發(fā)起投票之前昧廷，每個(gè)節(jié)點(diǎn)會(huì)分配一個(gè)隨機(jī)的選舉超時(shí)時(shí)間（election timeout）堪嫂。在這個(gè)時(shí)間內(nèi)，節(jié)點(diǎn)必須等待木柬，不能成為Candidate狀態(tài)。現(xiàn)在假設(shè)節(jié)點(diǎn)a等待168ms , 節(jié)點(diǎn)b等待210ms , 節(jié)點(diǎn)c等待200ms 恶复。由于a的等待時(shí)間最短谤牡，所以它會(huì)最先成為Candidate，并向另外兩個(gè)節(jié)點(diǎn)發(fā)起投票請(qǐng)求姥宝，希望它們能選舉自己為L(zhǎng)eader：

image

另外兩個(gè)節(jié)點(diǎn)收到請(qǐng)求后翅萤，假設(shè)將它們的投票返回給Candidate狀態(tài)節(jié)點(diǎn)a，節(jié)點(diǎn)a由于得到了大多數(shù)節(jié)點(diǎn)的投票腊满，就會(huì)從Candidate變?yōu)長(zhǎng)eader套么，如下圖所示，這個(gè)過(guò)程就叫做Leader選舉（Leader Election）胚泌。接下來(lái)肃弟，這個(gè)分布式系統(tǒng)所有的改變都要先經(jīng)過(guò)節(jié)點(diǎn)a玷室，即Leader節(jié)點(diǎn)：

image

如果某個(gè)時(shí)刻零蓉，F(xiàn)ollower不再收到Leader的消息，它就會(huì)變成Candidate绅项。然后請(qǐng)求其他節(jié)點(diǎn)給他投票（類(lèi)似拉票一樣）紊册。其他節(jié)點(diǎn)就會(huì)回復(fù)它投票結(jié)果，如果它能得到大多數(shù)節(jié)點(diǎn)的投票快耿，它就能成為新的Leader囊陡。

日志復(fù)制

假設(shè)接下來(lái)客戶(hù)端發(fā)起一個(gè)SET 5的請(qǐng)求，這個(gè)請(qǐng)求會(huì)首先由leader即節(jié)點(diǎn)a接收到掀亥，并且節(jié)點(diǎn)a寫(xiě)入一條日志撞反。由于這條日志還沒(méi)被其他任何節(jié)點(diǎn)接收，所以它的狀態(tài)是uncommitted搪花。

image

為了提交這條日志遏片，Leader會(huì)將這條日志通過(guò)心跳消息復(fù)制給其他的Follower節(jié)點(diǎn)：

image

一旦有大多數(shù)節(jié)點(diǎn)成功寫(xiě)入這條日志，那么Leader節(jié)點(diǎn)的這條日志狀態(tài)就會(huì)更新為committed狀態(tài)撮竿，并且值更新為5：

image

Leader節(jié)點(diǎn)然后通知其他Follower節(jié)點(diǎn)吮便，其他節(jié)點(diǎn)也會(huì)將值更新為5。如下圖所示幢踏，這個(gè)時(shí)候集群的狀態(tài)是完全一致的髓需，這個(gè)過(guò)程就叫做日志復(fù)制（Log Replication）：

image

兩個(gè)超時(shí)

接下來(lái)介紹Raft中兩個(gè)很重要的超時(shí)設(shè)置：選舉超時(shí)和心跳超時(shí)。

• 選舉超時(shí)

為了防止3個(gè)節(jié)點(diǎn)（假設(shè)集群由3個(gè)節(jié)點(diǎn)組成）同時(shí)發(fā)起投票房蝉，會(huì)給每個(gè)節(jié)點(diǎn)分配一個(gè)隨機(jī)的選舉超時(shí)時(shí)間（Election Timeout）僚匆，即從Follower狀態(tài)成為Candidate狀態(tài)需要等待的時(shí)間。在這個(gè)時(shí)間內(nèi)搭幻，節(jié)點(diǎn)必須等待咧擂，不能成為Candidate狀態(tài)。如下圖所示檀蹋，節(jié)點(diǎn)C優(yōu)先成為Candidate松申，而節(jié)點(diǎn)A和B還在等待中：

image

• 心跳超時(shí)

如下圖所示，節(jié)點(diǎn)A和C投票給了B续扔，所以節(jié)點(diǎn)B是leader節(jié)點(diǎn)。節(jié)點(diǎn)B會(huì)固定間隔時(shí)間向兩個(gè)Follower節(jié)點(diǎn)A和C發(fā)送心跳消息焕数，這個(gè)固定間隔時(shí)間被稱(chēng)為heartbeat timeout纱昧。Follower節(jié)點(diǎn)收到每一條日志信息都需要向Leader節(jié)點(diǎn)響應(yīng)這條日志復(fù)制的結(jié)果：

image

重新選舉

選舉過(guò)程中，如果Leader節(jié)點(diǎn)出現(xiàn)故障堡赔，就會(huì)觸發(fā)重新選舉识脆。如下圖所示，Leader節(jié)點(diǎn)B故障（灰色），這時(shí)候節(jié)點(diǎn)A和C就會(huì)等待一個(gè)隨機(jī)時(shí)間（選舉超時(shí)）灼捂，誰(shuí)等待的時(shí)候更短离例，誰(shuí)就先成為Candidate，然后向其他節(jié)點(diǎn)發(fā)送投票請(qǐng)求：

image

如果節(jié)點(diǎn)A能得得到節(jié)點(diǎn)C的投票悉稠，加上自己的投票宫蛆，就有大多數(shù)選票。那么節(jié)點(diǎn)A將成為新的Leader節(jié)點(diǎn)的猛，并且Term即任期的值加1更新到2：

image

需要說(shuō)明的是耀盗，每個(gè)選舉期只會(huì)選出一個(gè)Leader。假設(shè)同一時(shí)間有兩個(gè)節(jié)點(diǎn)成為Candidate（它們隨機(jī)等待選舉超時(shí)時(shí)間剛好一樣）卦尊，如下圖所示叛拷，并且假設(shè)節(jié)點(diǎn)A收到了節(jié)點(diǎn)B的投票，而節(jié)點(diǎn)C收到了節(jié)點(diǎn)D的投票：

image

這種情況下岂却，就會(huì)觸發(fā)一次新的選舉忿薇，節(jié)點(diǎn)A和節(jié)點(diǎn)B又等待一個(gè)隨機(jī)的選舉超時(shí)時(shí)間，直到一方勝出：

image

我們假設(shè)節(jié)點(diǎn)A能得到大多數(shù)投票躏哩，那么接下來(lái)節(jié)點(diǎn)A就會(huì)成為新的Leader節(jié)點(diǎn)署浩，并且任期term加1：

image

網(wǎng)絡(luò)分區(qū)

在發(fā)生網(wǎng)絡(luò)分區(qū)的時(shí)候，Raft一樣能保持一致性震庭。如下圖所示瑰抵，假設(shè)我們的集群由5個(gè)節(jié)點(diǎn)組成，且節(jié)點(diǎn)B是Leader節(jié)點(diǎn)：

image

我們假設(shè)發(fā)生了網(wǎng)絡(luò)分區(qū)：節(jié)點(diǎn)A和B在一個(gè)網(wǎng)絡(luò)分區(qū)器联，節(jié)點(diǎn)C二汛、D和E在另一個(gè)網(wǎng)絡(luò)分區(qū)，如下圖所示拨拓，且節(jié)點(diǎn)B和節(jié)點(diǎn)C分別是兩個(gè)網(wǎng)絡(luò)分區(qū)中的Leader節(jié)點(diǎn)：

image

我們假設(shè)還有一個(gè)客戶(hù)端肴颊，并且往節(jié)點(diǎn)B上發(fā)送了一個(gè)SET 3，由于網(wǎng)絡(luò)分區(qū)的原因渣磷，這個(gè)值不能被另一個(gè)網(wǎng)絡(luò)分區(qū)中的Leader即節(jié)點(diǎn)C拿到婿着，它最多只能被兩個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)B和C）感知到，所以它的狀態(tài)是uncomitted（紅色）：

image

另一個(gè)客戶(hù)端準(zhǔn)備執(zhí)行SET 8的操作醋界，由于可以被同一個(gè)分區(qū)下總計(jì)三個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)C竟宋、D和E）感知到，3個(gè)節(jié)點(diǎn)已經(jīng)符合大多數(shù)節(jié)點(diǎn)的條件形纺。所以丘侠，這個(gè)值的狀態(tài)就是committed：

image

接下來(lái)，我們假設(shè)網(wǎng)絡(luò)恢復(fù)正常逐样，如下圖所示蜗字。節(jié)點(diǎn)B能感知到C節(jié)點(diǎn)這個(gè)Leader的存在打肝，它就會(huì)從Leader狀態(tài)退回到Follower狀態(tài)，并且節(jié)點(diǎn)A和B會(huì)回滾之前沒(méi)有提交的日志（SET 3產(chǎn)生的uncommitted日志）挪捕。同時(shí)粗梭，節(jié)點(diǎn)A和B會(huì)從新的Leader節(jié)點(diǎn)即C節(jié)點(diǎn)獲取最新的日志（SET 8產(chǎn)生的日志），從而將它們的值更新為8级零。如此以來(lái)断医，整個(gè)集群的5個(gè)節(jié)點(diǎn)數(shù)據(jù)完全一致了：

image