Raft算法介紹

raft是一個(gè)協(xié)議请垛，可以用來(lái)實(shí)現(xiàn)分布式系統(tǒng)的一致性。

raft算法中節(jié)點(diǎn)的三種狀態(tài)

Leader：處理所有客戶端交互蹬碧，日志復(fù)制等色鸳，一般一次只有一個(gè)Leader

Follower：隨從，完全被動(dòng)

Candidate：候選者

一個(gè)簡(jiǎn)單的工作流程

1.領(lǐng)導(dǎo)的選舉過(guò)程

這三種狀態(tài)可以通過(guò)選舉機(jī)制互相轉(zhuǎn)換坠七。所有節(jié)點(diǎn)在初始狀態(tài)下都是以隨從份出現(xiàn)水醋，如果follower沒(méi)有聽(tīng)到領(lǐng)導(dǎo)者的指令，他就會(huì)變成候選者彪置，給所有的其他節(jié)點(diǎn)發(fā)送投票拄踪，其他節(jié)點(diǎn)回復(fù)候選者的投票，如果一個(gè)節(jié)點(diǎn)受到大多數(shù)節(jié)點(diǎn)（包括自己投自己）的投票拳魁，那么該節(jié)點(diǎn)從候選者變成領(lǐng)導(dǎo)者惶桐。

初始狀態(tài)

image.png

候選者狀態(tài)，并給所有節(jié)點(diǎn)發(fā)送投票請(qǐng)求

image.png

變成領(lǐng)導(dǎo)者

image.png

2.主節(jié)點(diǎn)數(shù)據(jù)同步過(guò)程（日志復(fù)制）

客戶端數(shù)據(jù)提交

所有對(duì)于系統(tǒng)的改變都必須通過(guò)領(lǐng)導(dǎo)潘懊。

客戶端更新數(shù)據(jù)5耀盗，發(fā)送給領(lǐng)導(dǎo)

image.png

每一個(gè)改變命令都會(huì)變?yōu)楣?jié)點(diǎn)日志，此時(shí)領(lǐng)導(dǎo)者沒(méi)有提交數(shù)據(jù)5卦尊。

主節(jié)點(diǎn)復(fù)制數(shù)據(jù)發(fā)給隨從節(jié)點(diǎn)

image.png

隨從節(jié)點(diǎn)收到數(shù)據(jù)后，響應(yīng)領(lǐng)導(dǎo)舌厨，同時(shí)領(lǐng)導(dǎo)節(jié)點(diǎn)等待大多數(shù)節(jié)點(diǎn)的響應(yīng)岂却，如果領(lǐng)導(dǎo)節(jié)點(diǎn)受到大多數(shù)節(jié)點(diǎn)的響應(yīng)，就提交數(shù)據(jù)

領(lǐng)導(dǎo)提交數(shù)據(jù)，提交成功后躏哩，通知隨從節(jié)點(diǎn)提交數(shù)據(jù)

image.png

隨從節(jié)點(diǎn)提交數(shù)據(jù)

image.png

主節(jié)點(diǎn)響應(yīng)客戶端數(shù)據(jù)提交成功署浩。

Raft算法包括兩個(gè)部分

Leader Election & Log Replication

Leader Election

選舉超時(shí)(Election timeout)

隨從變?yōu)楹蜻x者的過(guò)程，這個(gè)時(shí)間一般為150ms到300ms扫尺。

image.png

先結(jié)束自旋的節(jié)點(diǎn)變成候選人筋栋。

image.png

term:1 第一輪

vote count : 1 首先自己投自己一票

發(fā)起投票請(qǐng)求

image.png

其他節(jié)點(diǎn)收到投票請(qǐng)求，進(jìn)行投票

image.png

在同一輪中正驻，如果收到投票請(qǐng)求的節(jié)點(diǎn)弊攘，還沒(méi)有投票則可以允許他進(jìn)行投票，但是如果他已經(jīng)投過(guò)票了姑曙，則不允許繼續(xù)投票襟交，即同一輪中同一個(gè)節(jié)點(diǎn)只能投一票。

同時(shí)投完票的節(jié)點(diǎn)重新進(jìn)入自旋狀態(tài)

重新進(jìn)入選舉超時(shí)伤靠，防止領(lǐng)導(dǎo)節(jié)點(diǎn)掛了

image.png

領(lǐng)導(dǎo)為隨從發(fā)送日志

image.png

heartbeat timeout

消息發(fā)送也有超時(shí)時(shí)間即心跳超時(shí)捣域。

領(lǐng)導(dǎo)者和隨從維持心跳檢查，如果超時(shí)則隨從節(jié)點(diǎn)滿足選舉超時(shí)宴合，重新進(jìn)入選舉過(guò)程焕梅。

所以heartbeat timeout<vote timeout

image.png

這一屆領(lǐng)導(dǎo)班子一直會(huì)維系到一個(gè)隨從節(jié)點(diǎn)停止接收心跳并且成為了一個(gè)候選者。

領(lǐng)導(dǎo)節(jié)點(diǎn)故障

其中一個(gè)節(jié)目率先變成候選者

image.png

進(jìn)行第二輪投票

image.png

自己一票卦洽，B節(jié)點(diǎn)一票贞言，雖然受不到節(jié)點(diǎn)A的投票，但是期已經(jīng)獲得了大多數(shù)投票逐样，所以此時(shí)C勝利當(dāng)選蜗字。一輪投票只能產(chǎn)生一個(gè)領(lǐng)導(dǎo)。

投票分離

某一輪選舉過(guò)程中出現(xiàn)多個(gè)候選者

A,D節(jié)點(diǎn)同時(shí)變成候選者脂新，向隨從節(jié)點(diǎn)發(fā)送投票請(qǐng)求

image.png

隨從節(jié)點(diǎn)將票投給先到達(dá)該節(jié)點(diǎn)的投票請(qǐng)求的一方挪捕，同時(shí)拒收其他節(jié)點(diǎn)的投票請(qǐng)求。

image.png

圖中争便，B節(jié)點(diǎn)先收到A的投票請(qǐng)求级零，投票給A，同時(shí)拒收D的投票請(qǐng)求滞乙。同時(shí)C投票給D奏纪，那么本輪投票A,D票數(shù)相同，那么所有節(jié)點(diǎn)重新進(jìn)入自旋斩启。

所有節(jié)點(diǎn)重新進(jìn)入選舉超時(shí)（自旋）

等待節(jié)點(diǎn)重新變成候選者序调，并且重新進(jìn)行選舉，直到選出新的領(lǐng)導(dǎo)人兔簇。

image.png

Log Replication

日志復(fù)制发绢，每次同步數(shù)據(jù)都必須在心跳時(shí)間內(nèi)將數(shù)據(jù)同步請(qǐng)求發(fā)送出去

image.png

客戶端請(qǐng)求領(lǐng)導(dǎo)節(jié)點(diǎn)

image.png

領(lǐng)導(dǎo)節(jié)點(diǎn)在下一次心跳中硬耍，將日志同步給隨從節(jié)點(diǎn)

image.png

大多數(shù)節(jié)點(diǎn)都回復(fù)領(lǐng)導(dǎo)節(jié)點(diǎn)

image.png

此時(shí)領(lǐng)導(dǎo)節(jié)點(diǎn)可以提交數(shù)據(jù)，同時(shí)領(lǐng)導(dǎo)節(jié)點(diǎn)響應(yīng)給客戶端

此時(shí)不通知隨從節(jié)點(diǎn)提交數(shù)據(jù)

image.png

領(lǐng)導(dǎo)節(jié)點(diǎn)在下一次心跳中边酒，通知隨從節(jié)點(diǎn)提交數(shù)據(jù)

同時(shí)隨從節(jié)點(diǎn)提交后经柴，響應(yīng)給領(lǐng)導(dǎo)節(jié)點(diǎn)

image.png

Raft算法在網(wǎng)絡(luò)分區(qū)中如何保證一致性

在Raft算法中，如果出現(xiàn)網(wǎng)絡(luò)分區(qū)墩朦，會(huì)有一個(gè)區(qū)域分得當(dāng)前領(lǐng)導(dǎo)節(jié)點(diǎn)坯认，該節(jié)點(diǎn)因?yàn)槭詹坏酱蠖鄶?shù)請(qǐng)求的響應(yīng)而拒絕提交數(shù)據(jù)，而其他區(qū)域重新選舉氓涣，等到網(wǎng)絡(luò)分區(qū)結(jié)束牛哺，統(tǒng)一聽(tīng)最新選舉產(chǎn)生的領(lǐng)導(dǎo)節(jié)點(diǎn)，老領(lǐng)導(dǎo)退位回滾網(wǎng)絡(luò)分區(qū)過(guò)程中未提交的數(shù)據(jù)春哨，然后同步最新領(lǐng)導(dǎo)的數(shù)據(jù)荆隘。

網(wǎng)絡(luò)分區(qū)過(guò)程中Raft算法保持一致性的過(guò)程

image.png

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

image.png

原領(lǐng)導(dǎo)節(jié)點(diǎn)不在的區(qū)域重新進(jìn)行選舉

此時(shí)B節(jié)點(diǎn)作為領(lǐng)導(dǎo)節(jié)點(diǎn)分給了下半個(gè)區(qū)域，其所在的區(qū)域不用重新選舉赴背，而上半個(gè)區(qū)域沒(méi)有領(lǐng)導(dǎo)則需要重新進(jìn)行選舉

image.png

客戶端請(qǐng)求（下半?yún)^(qū)）

因?yàn)榫W(wǎng)絡(luò)分區(qū)了椰拒，所以此時(shí)分出了兩個(gè)客戶端，每個(gè)客戶端只能訪問(wèn)自己所有區(qū)域的領(lǐng)導(dǎo)者凰荚。

image.png

uncommitted

此時(shí)無(wú)論客戶端請(qǐng)求B節(jié)點(diǎn)保存任何數(shù)據(jù)燃观，B節(jié)點(diǎn)都會(huì)回復(fù)客戶端保存失敗，因?yàn)锽節(jié)點(diǎn)作為原先的領(lǐng)導(dǎo)便瑟，此時(shí)只收到了節(jié)點(diǎn)A的同步回復(fù)缆毁，并沒(méi)有收到大多數(shù)的回復(fù)，所以此時(shí)節(jié)點(diǎn)B不能提交數(shù)據(jù)到涂，回復(fù)客戶端提交失敗

image.png

客戶端請(qǐng)求（上半?yún)^(qū)）

image.png

因?yàn)樯习雲(yún)^(qū)是新選舉出來(lái)的領(lǐng)導(dǎo)脊框，可以獲得大多數(shù)同步回復(fù)，所以可以正常提交數(shù)據(jù)践啄。

網(wǎng)絡(luò)恢復(fù)

此時(shí)B(Term:1)要聽(tīng)更高一輪選舉（C term:2）的命令浇雹，所以B要退位,然后A,B兩個(gè)節(jié)點(diǎn)沒(méi)有提交的日志（數(shù)據(jù)）回滾，然后接收新領(lǐng)導(dǎo)的數(shù)據(jù)屿讽。

image.png

image.png

從而達(dá)到節(jié)點(diǎn)數(shù)據(jù)一致昭灵。