前言

Raft 也是一個(gè) 一致性算法沫勿，和 Paxos 目標(biāo)相同筒繁。但它還有另一個(gè)名字 - 易于理解的一致性算法噩斟。Paxos 和 Raft 都是為了實(shí)現(xiàn) 一致性 產(chǎn)生的库倘。這個(gè)過(guò)程如同選舉一樣临扮，參選者 需要說(shuō)服 大多數(shù)選民 (服務(wù)器) 投票給他，一旦選定后就跟隨其操作教翩。Paxos 和 Raft 的區(qū)別在于選舉的 具體過(guò)程 不同杆勇。

正文

小試牛刀

在進(jìn)入正題前，給大家分享一個(gè)《數(shù)學(xué)發(fā)散思維》中的一個(gè)故事饱亿，站在不同思維角度上靶橱，了解對(duì)一個(gè)問(wèn)題理解的差異性。

問(wèn)題: 甲乙兩人輪流在一張圓桌上平放黑白圍棋子路捧，每次放一子，棋子不許重疊传黄，誰(shuí)先沒(méi)有地方放就輸杰扫。請(qǐng)問(wèn)怎樣放才能贏？

這個(gè)問(wèn)題有兩層意思膘掰，第一章姓，有沒(méi)有一種放法保證必贏佳遣？第二，如果有怎么證明凡伊？

image

上圖回答了這個(gè)問(wèn)題零渐，那就是先行者必勝，這里使用了三種不同的思維方式來(lái)闡述:

1. 假如桌子只有一個(gè)圍棋子那么大系忙。

2. 假如桌子無(wú)限大诵盼，先行者先占住圓心。由于圓是對(duì)稱圖形银还，所以只要對(duì)手還能找到位置放风宁，你總能在對(duì)稱的另一面找到位置放。

3. 一個(gè)圓中可畫(huà)單數(shù)個(gè)直徑相等且互切的小圓蛹疯。

三種不同的思維方式在可理解性難度上逐漸加深戒财。

1. 第一種是 極簡(jiǎn)化思維，但數(shù)學(xué)上是 不嚴(yán)謹(jǐn) 的捺弦。

2. 第二種是 極限思維饮寞，和第一種結(jié)合起來(lái)就是 數(shù)學(xué)歸納法，在數(shù)學(xué)上是 嚴(yán)謹(jǐn) 的列吼。

3. 第三種是 形象思維幽崩，使用了 幾何學(xué)概念，但對(duì)于沒(méi)有幾何學(xué)基礎(chǔ)知識(shí)的人就很難理解了冈欢。

什么是Raft協(xié)議

Raft 協(xié)議將 Server 進(jìn)程分成三類歉铝，分別是 Leader，Candidate凑耻，Follower太示。一個(gè) Server 進(jìn)程在某一時(shí)刻，只能是其中 一種類型香浩，但這不是固定的类缤。不同的時(shí)刻，它可能擁有不同的類型邻吭，一個(gè) Server 進(jìn)程的類型是如何改變的餐弱，后面會(huì)有解釋。

在一個(gè)由 Raft 協(xié)議組織的集群中有三類角色：

• Leader（領(lǐng)袖）
• Follower（群眾）
• Candidate（候選人）

就像一個(gè)民主社會(huì)囱晴，領(lǐng)袖由民眾投票選出膏蚓。剛開(kāi)始沒(méi)有 領(lǐng)袖，所有集群中的 參與者 都是 群眾畸写，那么首先開(kāi)啟一輪大選驮瞧。在大選期間 所有群眾 都能參與競(jìng)選，這時(shí)所有群眾的角色就變成了 候選人枯芬，民主投票選出領(lǐng)袖后就開(kāi)始了這屆領(lǐng)袖的任期论笔，然后選舉結(jié)束采郎，所有除 領(lǐng)袖 的 候選人 又變回 群眾角色 服從領(lǐng)袖領(lǐng)導(dǎo)。

這里提到一個(gè)概念 「任期」狂魔，用術(shù)語(yǔ) Term 表達(dá)蒜埋。關(guān)于 Raft 協(xié)議的核心概念和術(shù)語(yǔ)就這么多，而且和現(xiàn)實(shí)民主制度非常匹配最楷，所以很容易理解整份。

三類角色的變遷圖如下，結(jié)合后面的選舉過(guò)程來(lái)看很容易理解管嬉。

image

Leader選舉過(guò)程

在極簡(jiǎn)的思維下皂林，一個(gè)最小的 Raft 民主集群需要 三個(gè)參與者（如下圖：A、B蚯撩、C）础倍，這樣才可能投出多數(shù)票。

初始狀態(tài) ABC 都是 Follower胎挎，然后發(fā)起選舉這時(shí)有 三種 可能的情形發(fā)生沟启。下圖中前二種都能選出 Leader，第三種則表明 本輪投票無(wú)效（Split Votes）犹菇。對(duì)于第三種德迹，每方都投給了自己，結(jié)果沒(méi)有任何一方獲得多數(shù)票揭芍。之后 每個(gè)參與方 隨機(jī)休息一陣（Election Timeout）重新發(fā)起投票直到一方獲得多數(shù)票胳搞。這里的關(guān)鍵就是隨機(jī) timeout，最先從 timeout 中恢復(fù)發(fā)起投票的一方称杨，向還在 timeout 中的另外兩方 請(qǐng)求投票肌毅，這時(shí)它就只能投給自己，導(dǎo)致很快達(dá)成一致姑原。

image

選出 Leader 后悬而，Leader 通過(guò) 定期 向所有 Follower 發(fā)送 心跳信息 維持其統(tǒng)治。若 Follower 一段時(shí)間未收到 Leader 的 心跳锭汛，則認(rèn)為 Leader 可能已經(jīng)掛了笨奠，然后再次發(fā)起 選舉 過(guò)程。

Leader對(duì)一致性的影響

Raft 協(xié)議 強(qiáng)依賴 Leader 節(jié)點(diǎn)的 可用性唤殴，以確保集群 數(shù)據(jù)的一致性般婆。數(shù)據(jù)的流向 只能從 Leader 節(jié)點(diǎn)向 Follower 節(jié)點(diǎn)轉(zhuǎn)移。具體過(guò)程如下：

image

1. 當(dāng) Client 向集群 Leader 節(jié)點(diǎn) 提交數(shù)據(jù) 后朵逝，Leader 節(jié)點(diǎn) 接收到的數(shù)據(jù) 處于 未提交狀態(tài)（Uncommitted）蔚袍。

2. 接著 Leader 節(jié)點(diǎn)會(huì) 并發(fā)地 向所有 Follower 節(jié)點(diǎn) 復(fù)制數(shù)據(jù) 并 等待接收響應(yīng)。

3. 集群中至少 超過(guò)半數(shù) 的節(jié)點(diǎn) 已接收 到數(shù)據(jù)后廉侧， Leader 再向 Client 確認(rèn)數(shù)據(jù) 已接收页响。

4. 一旦向 Client 發(fā)出數(shù)據(jù)接收 Ack 響應(yīng)后，表明此時(shí) 數(shù)據(jù)狀態(tài) 進(jìn)入 已提交（Committed）段誊，Leader 節(jié)點(diǎn)再向 Follower 節(jié)點(diǎn)發(fā)通知告知該 數(shù)據(jù)狀態(tài)已提交闰蚕。

在這個(gè)過(guò)程中，主節(jié)點(diǎn) 可能在 任意階段 掛掉连舍，看下 Raft 協(xié)議如何針對(duì)不同階段保障 數(shù)據(jù)一致性 的没陡。

1. 情形1

數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)前，這個(gè)階段 Leader 掛掉不影響一致性索赏，不用多說(shuō)盼玄。

image

2. 情形2

數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，但未復(fù)制到 Follower 節(jié)點(diǎn)潜腻。

這個(gè)階段 Leader 掛掉埃儿，數(shù)據(jù)屬于 未提交狀態(tài)，Client 不會(huì)收到 Ack 會(huì)認(rèn)為 超時(shí)失敗 可安全發(fā)起 重試融涣。

image

Follower 節(jié)點(diǎn)上沒(méi)有該數(shù)據(jù)童番，重新選主 后 Client 重試 重新提交 可成功。原來(lái)的 Leader 節(jié)點(diǎn) 恢復(fù) 后作為 Follower 加入集群威鹿，重新從 當(dāng)前任期 的新 Leader 處 同步數(shù)據(jù)剃斧，強(qiáng)制保持和 Leader 數(shù)據(jù)一致。

3. 情形3

數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)忽你，成功復(fù)制到 Follower 所有節(jié)點(diǎn)幼东，但 Follower 還未向 Leader 響應(yīng)接收。

這個(gè)階段 Leader 掛掉科雳，雖然數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于 未提交狀態(tài)（Uncommitted）根蟹，但是 保持一致 的。重新選出 Leader 后可完成 數(shù)據(jù)提交炸渡。

image

此時(shí) Client 由于不知到底提交成功沒(méi)有娜亿，可重試提交。針對(duì)這種情況 Raft 要求 RPC 請(qǐng)求實(shí)現(xiàn) 冪等性蚌堵，也就是要實(shí)現(xiàn) 內(nèi)部去重機(jī)制买决。

4. 情形4

數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 的部分節(jié)點(diǎn)吼畏，但這部分 Follower 節(jié)點(diǎn)還未向 Leader 響應(yīng)接收督赤。

這個(gè)階段 Leader 掛掉，數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于 未提交狀態(tài)（Uncommitted）且 不一致泻蚊。

image

Raft 協(xié)議要求投票只能投給擁有 最新數(shù)據(jù) 的節(jié)點(diǎn)躲舌。所以擁有最新數(shù)據(jù)的節(jié)點(diǎn)會(huì)被選為 Leader，然后再 強(qiáng)制同步數(shù)據(jù) 到其他 Follower性雄，保證 數(shù)據(jù)不會(huì)丟失并 最終一致没卸。

5. 情形5

數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)羹奉，成功復(fù)制到 Follower 所有或多數(shù)節(jié)點(diǎn)，數(shù)據(jù)在 Leader 處于已提交狀態(tài)约计，但在 Follower 處于未提交狀態(tài)诀拭。

這個(gè)階段 Leader 掛掉蝗拿，重新選出 新的 Leader 后的處理流程和階段 3 一樣捺信。

image

6. 情形6

數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有或多數(shù)節(jié)點(diǎn)鹃彻，數(shù)據(jù)在所有節(jié)點(diǎn)都處于已提交狀態(tài)尉桩，但還未響應(yīng) Client筒占。

這個(gè)階段 Leader 掛掉，集群內(nèi)部數(shù)據(jù)其實(shí)已經(jīng)是 一致的蜘犁，Client 重復(fù)重試基于冪等策略對(duì) 一致性無(wú)影響翰苫。

image

7. 情形7

網(wǎng)絡(luò)分區(qū)導(dǎo)致的腦裂情況，出現(xiàn)雙 Leader 的現(xiàn)象沽瘦。

網(wǎng)絡(luò)分區(qū) 將原先的 Leader 節(jié)點(diǎn)和 Follower 節(jié)點(diǎn)分隔開(kāi)革骨，Follower 收不到 Leader 的 心跳 將 重新 發(fā)起選舉產(chǎn)生新的 Leader，這時(shí)就產(chǎn)生了 雙Leader 現(xiàn)象析恋。

image

原先的 Leader 獨(dú)自在一個(gè)區(qū)良哲，向它提交數(shù)據(jù)不可能復(fù)制到多數(shù)節(jié)點(diǎn)所以永遠(yuǎn)提交不成功。向新的 Leader 提交數(shù)據(jù)可以提交成功助隧。

網(wǎng)絡(luò)恢復(fù) 后筑凫，舊的 Leader 發(fā)現(xiàn)集群中有 更新任期（Term）的新 Leader ，則 自動(dòng)降級(jí) 為 Follower 并從新 Leader 處 同步數(shù)據(jù) 達(dá)成集群 數(shù)據(jù)一致并村。

驗(yàn)證結(jié)果

綜上窮舉分析了 最小集群（3 節(jié)點(diǎn)）面臨的所有情況巍实，可以看出 Raft 協(xié)議都能很好的應(yīng)對(duì) 一致性問(wèn)題，并且很容易理解哩牍。

小結(jié)

Paxos 算法是 Leslie Lamport 在 1990 年就公開(kāi)發(fā)表在了自己的網(wǎng)站上棚潦，想想我們是什么時(shí)候才聽(tīng)說(shuō)的？什么時(shí)候才有一個(gè)可用的實(shí)現(xiàn)膝昆？而 Raft 算法是 2013 年發(fā)表的丸边，大家在參考 Raft開(kāi)源實(shí)現(xiàn)庫(kù)，可以看到有很多基于不同語(yǔ)言的 開(kāi)源實(shí)現(xiàn)庫(kù)荚孵，這就是 可理解性 的重要性妹窖。

歡迎關(guān)注技術(shù)公眾號(hào)： 零壹技術(shù)棧

零壹技術(shù)棧

本帳號(hào)將持續(xù)分享后端技術(shù)干貨，包括虛擬機(jī)基礎(chǔ)收叶，多線程編程骄呼，高性能框架，異步、緩存和消息中間件蜓萄，分布式和微服務(wù)隅茎，架構(gòu)學(xué)習(xí)和進(jìn)階等學(xué)習(xí)資料和文章。