今天在團(tuán)隊(duì)內(nèi)部做了一次分享，給組內(nèi)的各位大神介紹了raft算法。老實(shí)說(shuō)講的內(nèi)容中還是有些欠缺，主要是在內(nèi)容深度上不夠，只能按照論文上的內(nèi)容講，沒(méi)有一些自己的提煉，再多多摸索吧。
這次會(huì)議我沒(méi)有做PPT，只是打了一個(gè)文字稿，然后在白板上講。下面貼的內(nèi)容是按照文字稿復(fù)制過(guò)來(lái)的，當(dāng)然和會(huì)議上實(shí)際講的所有出入，就當(dāng)做給沒(méi)有聽(tīng)說(shuō)過(guò)raft算法的朋友當(dāng)做一個(gè)入門介紹吧。正兒八經(jīng)學(xué)習(xí)還是得找其他資源，比如論文原文。
-----------------------分割線---------------------------
我會(huì)去了解raft是因?yàn)樵趤?lái)公司實(shí)習(xí)，尤其是接觸到prometheus之后，就去網(wǎng)上搜了一下學(xué)習(xí)分布式系統(tǒng)要看哪些東西，然后就搜出了raft。老實(shí)說(shuō)我最開(kāi)始是一點(diǎn)都看不懂它在講什么的，而且也看不到它的實(shí)際作用，感覺(jué)就是沒(méi)必要整出這么一個(gè)東西來(lái)。我打印出來(lái)的論文也一直放在屋里吃灰。
變化是在體驗(yàn)到influxdb-relay和influxdb集群版的差別后，我開(kāi)始漸漸意識(shí)到一致性算法對(duì)于分布式系統(tǒng)的重要性。relay它只是簡(jiǎn)單得將客戶端的數(shù)據(jù)轉(zhuǎn)發(fā)給多個(gè)influxdb實(shí)例，至于每個(gè)實(shí)例成不成功，它沒(méi)法保證。后來(lái)我試用了InfluxDB帶有集群功能的企業(yè)版，那個(gè)確實(shí)就是我們想要的功能，往任何一個(gè)節(jié)點(diǎn)寫入任何一條數(shù)據(jù)，只要服務(wù)器告訴我寫成功了，無(wú)論接下來(lái)這個(gè)集群發(fā)生了怎樣極端的故障, 我還是基本能相信這個(gè)數(shù)據(jù)是沒(méi)問(wèn)題的.而Influxdb的集群版就正是使用了raft算法保證了這種一致性，并且他們用的還是和consul同樣的庫(kù)。這時(shí)候我再去學(xué)raft就和幾個(gè)月前的感受不大一樣了。
raft的論文是斯坦福一個(gè)計(jì)算機(jī)博士在13年發(fā)的,而另外一個(gè)一致性算法paxos是1990發(fā)的.對(duì)比下發(fā)現(xiàn)最近幾年出來(lái)的項(xiàng)目很多都是用了raft而不是paxos,像etcd,consul,tidb這些都是用raft,而ceph用的是paxos,ceph查了下是10年開(kāi)始的項(xiàng)目.所以還是能看出raft與同類比起來(lái)的一些優(yōu)點(diǎn)的,應(yīng)該確實(shí)是比較容易學(xué).
然后接下來(lái)我就講下raft它的算法過(guò)程,其實(shí)我也只是看了幾遍論文,很多東西我的理解也不是很通透,這個(gè)要真正拿去實(shí)踐下才能做得到.我就大概按照論文的內(nèi)容講,會(huì)省略掉一些內(nèi)容.
我們先假設(shè)一個(gè)場(chǎng)景, 就拿consul來(lái)舉例, 假設(shè)我們現(xiàn)在有一個(gè)3節(jié)點(diǎn)的consul集群,nodeA,nodeB,nodeC.這3個(gè)節(jié)點(diǎn)都是運(yùn)行在consul的server模式下.我們看下raft會(huì)怎樣處理這3個(gè)節(jié)點(diǎn).
在raft里面, 有3種角色, 領(lǐng)導(dǎo)者, 候選者,跟隨者.
領(lǐng)導(dǎo)者的負(fù)責(zé)管理集群,并處理來(lái)自用戶的請(qǐng)求.
跟隨者是領(lǐng)導(dǎo)者的一個(gè)副本, 它會(huì)在領(lǐng)導(dǎo)者出現(xiàn)故障的時(shí)候頂替它.
而從跟隨者變成領(lǐng)導(dǎo)者,有一個(gè)中間狀態(tài),那就是候選者.
以我們上面的3個(gè)consul節(jié)點(diǎn)來(lái)做例子.我們先啟動(dòng)了3個(gè)consul,這時(shí)候他們都處于跟隨者的狀態(tài),這也是raft算法中節(jié)點(diǎn)啟動(dòng)時(shí)的初始狀態(tài).跟隨者啟動(dòng)之后,他們會(huì)等待一段時(shí)間,如果這個(gè)時(shí)間內(nèi)沒(méi)有領(lǐng)導(dǎo)者發(fā)心跳包給它,那么跟隨者就會(huì)進(jìn)入候選者的狀態(tài).進(jìn)入選舉階段,這也是raft算法中3個(gè)子問(wèn)題中的第一個(gè).
如何選舉的呢?每個(gè)候選者手中都有一張票, 這張牌可以投給集群任意一個(gè)節(jié)點(diǎn).比如nodeA可以投給nodeB,nodeC,當(dāng)然也可以投給自己.只要一個(gè)節(jié)點(diǎn)能夠拿到大多數(shù)節(jié)點(diǎn)的選票,那么它就當(dāng)選為leader.比如,nodeA拿到了nodeB,nodeC兩張票,那么它就是leader
但是實(shí)際上raft的算法的選舉沒(méi)有這么簡(jiǎn)單,因?yàn)檫@種方法有一個(gè)問(wèn)題,那就是選票可能會(huì)被瓜分掉.比如nodeA,nodeB,nodeC,他們分別把票都投給了自己,或者A投給B,B投給C,C投給A,這樣誰(shuí)也當(dāng)不成leader.
raft是怎么解決這個(gè)問(wèn)題的呢, 它引入兩個(gè)概念,一個(gè)是任期,一個(gè)是選舉超時(shí)時(shí)間.任期就是把時(shí)間軸切成一個(gè)個(gè)可以被編號(hào)的時(shí)間段.比如,我們上面3個(gè)節(jié)點(diǎn)啟動(dòng)的時(shí)候,都會(huì)進(jìn)入第一個(gè)任期.而選舉的超時(shí)時(shí)間是定義每個(gè)節(jié)點(diǎn)等待投票信息的最長(zhǎng)時(shí)間的
還是拿我們上面的三個(gè)節(jié)點(diǎn)舉例子.A,B,C啟動(dòng),進(jìn)入跟隨者狀態(tài),接下來(lái)等不到領(lǐng)導(dǎo)者的心跳過(guò)來(lái),都進(jìn)入候選者狀態(tài),開(kāi)始請(qǐng)求選舉leader,這時(shí)候任期是1.raft會(huì)給每個(gè)節(jié)點(diǎn)在一個(gè)范圍內(nèi)隨機(jī)設(shè)置一個(gè)超時(shí)時(shí)間,比如A是10ms,B是20ms,C是30ms.如果A在10ms內(nèi)當(dāng)不成leader, 那么它就給自己的任期號(hào)加1,變成任期2,重新開(kāi)始投票.這時(shí)候B和C還是任期1.而且raft有個(gè)限制,就是會(huì)拒絕來(lái)自任期號(hào)低于自己的節(jié)點(diǎn)的選票,.比如這時(shí)候只能A投給B和C, B和C如果投給A那么會(huì)被A拒絕掉.并且節(jié)點(diǎn)在通訊的時(shí)候發(fā)現(xiàn)有比自己的任期號(hào)更高的,它會(huì)也馬上提升自己的任期.用這種方法幾輪下來(lái),是一定可以選出一個(gè)leader的.
上面講的這個(gè)選舉問(wèn)題,是raft三個(gè)子問(wèn)題中的的第一個(gè),領(lǐng)導(dǎo)選舉.接下來(lái)我們看第二個(gè)問(wèn)題,日志復(fù)制.
當(dāng)leader被選舉出來(lái)后,我們就假設(shè)A當(dāng)上了leader.集群開(kāi)始能夠處理用戶的請(qǐng)求.我們可以把用戶的每一個(gè)請(qǐng)求都當(dāng)成是一個(gè)指令,leader的一個(gè)重要任務(wù),就是要將這些指令復(fù)制到集群的其他節(jié)點(diǎn)去.raft里面用日志這個(gè)詞來(lái)描述這樣一種指令,日志里面會(huì)記錄一個(gè)任期號(hào),一個(gè)日志的編號(hào),還有執(zhí)行的指令.Raft會(huì)維護(hù)日志,讓他們能夠滿足下面的兩個(gè)很重要的特性:
如果兩個(gè)日志條目擁有相同的日志編號(hào)和任期編號(hào),那么兩個(gè)日志就存儲(chǔ)了相同的指令
如果兩個(gè)日志條目擁有相同的日志編號(hào)和任期編號(hào),那么他們前面的日志所有日志都會(huì)相同
leader會(huì)決定什么時(shí)候可以應(yīng)用日志中的指令,這種可以被應(yīng)用的日志的狀態(tài)在raft里面被描述為commited,所有commited的日志都會(huì)持久化存儲(chǔ).一個(gè)日志怎樣才能算是commited呢.raft里面的定義就是,leader已經(jīng)能確認(rèn)這個(gè)日志已經(jīng)被復(fù)制到大多數(shù)節(jié)點(diǎn)上面.
它的流程是這樣的:比如我們有一個(gè)請(qǐng)求是要存一個(gè)kv到consul里面,請(qǐng)求到了leader nodeA這里,nodeA會(huì)將包含請(qǐng)求中的指令的日志發(fā)送到nodeB和nodeC上面.nodeA會(huì)等待他們返回的結(jié)果, 如果寫入的節(jié)點(diǎn)能夠超過(guò)半數(shù),那么nodeA才會(huì)告訴客戶端請(qǐng)求是成功的.
如果leader永遠(yuǎn)正常運(yùn)行,那么理論上那些能夠正常工作的副本的日志是會(huì)和leader保持一致的.但現(xiàn)實(shí)情況是leader總會(huì)有崩潰的那一天.比如NodeA在復(fù)制日志給B和C的過(guò)程中,B復(fù)制好了,但C還沒(méi)復(fù)制好時(shí)nodeA就崩潰了,這種情況就會(huì)導(dǎo)致集群中的狀態(tài)不一致,更加極端的是leader可能會(huì)在短時(shí)間內(nèi)更換多次,這種情況下,集群內(nèi)的日志會(huì)更加混亂.
(畫圖)
前面說(shuō)過(guò)一個(gè)合格的一致性算法,只要leader告訴我們請(qǐng)求是ok的,那么不管發(fā)生什么極端的情況,任何時(shí)候任何節(jié)點(diǎn)的數(shù)據(jù)應(yīng)該都是ok,但是像上面上面這種情況完全是有可能出現(xiàn)的,raft是如何保證數(shù)據(jù)的安全性呢?接下來(lái)就是raft的第三個(gè)子問(wèn)題,安全性.
安全性一:
選舉限制:
raft在選擇leader的時(shí)候還有一個(gè)限制,就是這個(gè)候選人在選舉時(shí)要聯(lián)系集群中的大部分節(jié)點(diǎn),驗(yàn)證這個(gè)候選者是不是擁有所有已經(jīng)提交過(guò)的日志.如果沒(méi)有,那么它就不可能當(dāng)上leader.
raft的比較規(guī)則是這樣的:
如果兩份日志最后的條目的任期號(hào)不同，那么任期號(hào)大的日志更加新。如果兩份日志最后的條目任期號(hào)相同，那么日志比較長(zhǎng)的那個(gè)就更加新。
安全性二:
對(duì)提交舊日志進(jìn)行限制,在提交當(dāng)前term的日志之前,不準(zhǔn)leader提交當(dāng)前任期之前的任何日志.
-------------------------------------分割線--------------------------
準(zhǔn)備的草稿只有這些了，昨晚準(zhǔn)備到12點(diǎn)多，擋不住困意只能作罷，第二天再臨場(chǎng)講了一些內(nèi)容。
留張照片做個(gè)紀(jì)念，以后不知道還會(huì)不會(huì)有。
