分布式系統(tǒng)基礎(chǔ)-Raft算法
注意:這篇文章是我在閱讀Raft算法的論文之后的一些想法刽宪，記錄下來．其中可能有些地方表述的不準確，也可能我理解有誤．所以請各位還是先閱讀Raft算法論文<<In Search of an Understandable COnsensus Algorithm>>然后再讀這篇文章．防止我誤人子弟．
簡介
學(xué)習(xí)分布式系統(tǒng)的朋友應(yīng)該都知道界酒，分布式一致性問題一直是一個很難的問題．針對這個問題圣拄，最早提出的算法是Lamport大神的Paxos算法，但是這個算法由于難于實現(xiàn)毁欣，以及不易于理解庇谆，而被人詬病．基于此凭疮，Standford大學(xué)的博士Diego Ongaro和John Ousterhout就發(fā)明了Raft算法．
Chubby的作者說饭耳，世界上只有一種一致性算法，那就是Paxos算法执解，其他的算法哥攘，不是Paxos算法的簡化版，就是錯誤的．我覺得Raft就是Paxos算法的一個簡化版本．事實上它也確實是．
Raft的整體架構(gòu)材鹦，我認為是結(jié)合了Primary-Backup 模式以及 State Machine模式，關(guān)于State Machine模式耕姊，前面我在一篇文章中桶唐，專門介紹過，文末我會附上這篇文章的鏈接茉兰，這里也不再介紹了．而Primary-Backup模式尤泽，也早已被大家所熟知，它是一種主從結(jié)構(gòu)规脸，平時只使用主節(jié)點來響應(yīng)客戶端請求坯约，然后主節(jié)點可以有好幾個備用節(jié)點，一旦主節(jié)點掛掉莫鸭，備用節(jié)點就頂上．
關(guān)于Primary-Backup模式以及State Machine的介紹闹丐，請大家查看文末的鏈接中，Fault Tolerant Services這一篇文章．
在Raft算法中被因，就有這么一個專門的Leader節(jié)點卿拴，這點便是對Paxos算法進行的簡化，在Paxos算法中梨与，可以有多個Proposer(Proposer相當于這里的Leader節(jié)點).而且Leader有且只能有一個．其他的節(jié)點均為Follower節(jié)點．在Leader節(jié)點以及Follower節(jié)點中堕花，均存在一個狀態(tài)機，Leader節(jié)點在接收到客戶端的請求之后粥鞋，會先保存到本地的Log Entry隊列中缘挽，然后將其發(fā)送給Follower節(jié)點，一旦收到多數(shù)Follower節(jié)點的響應(yīng)，Leader節(jié)點便會告知客戶端操作成功并返回相應(yīng)的結(jié)果壕曼，然后提交Log Entry并通知Follower節(jié)點提交Log Entry.寫請求是上面的那個流程苏研，而如果是寫請求呢，則直接從Leader節(jié)點的本地狀態(tài)機中讀取相應(yīng)的數(shù)據(jù)并返回給客戶端．
我們這么一看窝稿，實際上它就是一個結(jié)合了Primary-Backup模式以及State Machine模式．
細節(jié)我們會在后面的小節(jié)中討論．
Raft算法中的一些概念
在上一小節(jié)中楣富，我們大體介紹了Raft的工作流程，但是伴榔，這是不夠的．我們還需要詳細考慮其實現(xiàn)．
那么在此之前纹蝴，我們先了解一下Raft算法中的一些概念．這些概念我們不會進行翻譯，因為我當初在讀這篇論文的時候踪少，翻譯這些概念的時候塘安，讓我有點懵．
我們先說Log Entry．我們把客戶端請求執(zhí)行的命令，放到一個隊列中援奢，其中每一條要執(zhí)行的命令兼犯，都把它封裝一下，加上一些其他數(shù)據(jù)集漾，變成了一條Log Entry.
Log Entry中切黔，存儲的除了要執(zhí)行的命令，還有term.terms是Leader的標志具篇，表示是哪個Leader提交的命令．因為在這個Log Entry隊列中是還存儲之前的Leader提交的命令的纬霞，所以需要term.不要誤會為可以同時有多個Leader.當時,term還有其他作用，我們后面會介紹．
在Log Entry隊列中驱显，還有一個其他的概念诗芜，是index.它表明Log Entry在這個隊列中的位置．就跟數(shù)組中的元素在數(shù)組中的位置一樣．具體的用處我們也會在后面介紹．
Raft算法中節(jié)點的三種狀態(tài)
在Raft中，存在以下幾種類型的節(jié)點:
- Leader.Leader負責(zé)接收客戶端發(fā)送的請求埃疫，通知Follower節(jié)點以及響應(yīng)客戶端．
- Follower.集群中除Leader節(jié)點之外的節(jié)點伏恐，都是Follower節(jié)點．Follower節(jié)點負責(zé)維護一個狀態(tài)機，接收Leader發(fā)送來的Log Entry以及其他命令．
- Candidate.當集群中的Leader不可用時栓霜，F(xiàn)ollower節(jié)點就會轉(zhuǎn)換成Candidate狀態(tài)直到選舉出一個Leader.
Raft算法的具體過程
我們在上面粗略的介紹過Raft算法的處理過程．這里我們詳細的介紹一下．
首先翠桦，集群啟動時，選舉出一個Leader節(jié)點叙淌，然后其他的節(jié)點都處于Follower狀態(tài)．然后秤掌，客戶端隨機選擇集群中的一臺機器，并訪問它鹰霍，如果這臺機器是Follower節(jié)點闻鉴，那么它會拒絕客戶端的請求并且告訴它Leader節(jié)點的訪問地址．當Leader節(jié)點收到客戶端的請求之后，正如上面我們說的那樣茂洒，它會生成一個Log Entry并保存在一個隊列中孟岛，然后將這個Log Entry廣播給全部Follower節(jié)點，當收到多數(shù)Follower節(jié)點的響應(yīng)時，就會給客戶端回應(yīng)并且提交這個Log Entry.提交一個Log Entry的意思是渠羞，將其對應(yīng)的命令應(yīng)用到狀態(tài)機．在這里斤贰，Leader節(jié)點還會同時將這個提交Log Entry的命令廣播給其他節(jié)點．
當然Leader節(jié)點也可能會由于網(wǎng)絡(luò)延時的問題，而沒有收到多數(shù)Follower節(jié)點的響應(yīng)．那么Leader節(jié)點就會對那些沒有收到響應(yīng)的節(jié)點次询，重復(fù)發(fā)送請求荧恍，直到收到響應(yīng)．
當Follower節(jié)點收到Leader命令的提交Log Entry的命令時，就會將其對應(yīng)的命令應(yīng)用到狀態(tài)機．并且屯吊，在其Log Entry隊列中的index小于需要提交的Log Entry的index的Log Entry,也會同時被提交．
當Follower節(jié)點在一定時間內(nèi)沒有收到來自Leader節(jié)點的請求時送巡，便會認為Leader節(jié)點出故障了，于是盒卸，便會把它自身變?yōu)橐粋€Candidate節(jié)點骗爆，進行選舉過程．如果其他的大多數(shù)節(jié)點同意讓它做Leader節(jié)點，或者收到了其他新任命的Leader的消息蔽介，那么它便會停止選舉過程摘投，重新轉(zhuǎn)換為Follower節(jié)點．
所以，為了防止Leader其實并沒有出現(xiàn)故障虹蓄，而是由于一段時間內(nèi)確實沒有收到請求犀呼，而沒有給Follower節(jié)點發(fā)送請求，Leader節(jié)點需要定期發(fā)送給Follower一個請求薇组，表明它其實還在正常工作．
同樣圆凰，在選舉過程中，為了讓其他的Candidate知曉已經(jīng)選舉出來了Leader,所以Leader需要在上任的時候体箕，給其他的Candidate發(fā)送請求，表明它是新選出來的Leader.
各個節(jié)點上需要存儲的數(shù)據(jù)
Raft算法中的RPC
從上面的過程中挑童，我們可以看到累铅，至少需要兩種RPC操作:
- AppendEntries RPC: Leader在將Log Entry廣播給Follower時，便是用的這種RPC.
- RequestVote RPC:當Candidate需要其他的Candidate協(xié)助它被選舉為Leader節(jié)點時站叼，就需要向其他的Candidate節(jié)點發(fā)送這種RPC.
關(guān)于這兩種RPC的具體細節(jié)娃兽，這里我直接就貼出來了，論文中描述的已經(jīng)很詳細了．
還有其他的一些操作尽楔，這里也一并列出了:
Raft算法中Leader的產(chǎn)生
每一個節(jié)點上投储，都需要存儲一些配置，一些數(shù)據(jù)阔馋，比如玛荞，當前是哪個Leader主事，用currentTerm表示．在Candidate節(jié)點A進行選舉時呕寝，它需要提出一個更大的term,并發(fā)送給其他的Candidate節(jié)點B和C．如果Candidate節(jié)點B和C發(fā)現(xiàn)Candidate A提出的term比它當前維護的currentTerm大勋眯，并且Candidate B和C的voteFor為空或者它自己，并且Candidate B的Log Entry隊列中的記錄比他的更新，就告訴Candidate B客蹋，我選舉你為Leader啦．如果上述三個條件中的任意一個不滿足塞蹭，則不選舉其為Leader.
那么上面說的記錄更新是什么意思呢?
- 如果Log Entry隊列中的最后一個Log Entry的term不相同，那么具有更大的term的那個Candidate中的Log Entry隊列更新．
- 如果Log Entry隊列中的最后一個Log Entry的term相同讶坯，那么Log Entry隊列更長的那個Candidate更新.
如果集群中僅有三臺機器A,B,C番电，根據(jù)上面的過程,Candidate B就可以成為Leader了．因為加上他自己同意他自己成為Leader,已經(jīng)達成集群中多數(shù)機器同意的條件了，那Candidate B現(xiàn)在就成為Leader了．
如果Candidate B在超時的時間范圍內(nèi)辆琅，既沒有成為Leader,又沒有其他的Candidate告訴它漱办，我成為Leader啦，那么Candidate B就保持Candidate的狀態(tài)涎跨，繼續(xù)進行選舉．
上面我們用三臺機器舉例洼冻，那么如果集群中有四臺機器，我們假設(shè)它們分別為A,B,C,D隅很，那么很可能有這么一種情況產(chǎn)生撞牢，就是A和B都同時獲得了兩票，誰也不能成為Leader.在Raft中叔营，通過每一臺Candidate隨機選擇一個選舉超時時間來避免這個問題．這個選舉超時時間應(yīng)該滿足下面這個公式:
broadcastTime << electionTimeout << MTBF
在上面的那個公式中屋彪，broadcastTime代表的是機器給其他機器發(fā)送RPC的平均時間，包括去和回．MTBF代表機器故障的平均時間．這兩個變量都是集群中的一些屬性绒尊，我們能夠選擇的只能是electionTimeout.取決于所采用的存儲技術(shù),broadcastTime可能在0.5ms~20ms,因此畜挥，electionTimeout就可能是10ms~500ms.
日志復(fù)制
我們知道，剛被選舉出來的Leader的Log Entry婴谱，一定是最新的蟹但，最全的．為了保持全部的節(jié)點上的狀態(tài)機狀態(tài)一致，我們需要讓它們執(zhí)行相同的命令序列谭羔，所以华糖，我們需要將Leader節(jié)點上的Log Entry復(fù)制到Follower節(jié)點上．
既然要將Leader節(jié)點的Log Entry復(fù)制到Follower節(jié)點上，自然存在Follower節(jié)點上的Log Entry和Leader節(jié)點上的Log Entry沖突的問題．比如瘟裸，F(xiàn)ollower節(jié)點上的Log Entry隊列為:[{1, a <- 1}, {1, a <- 2}, {2, a <- 1}],而Leader節(jié)點上的Log Entry隊列為:[{1, a <- 1}, {1, a <- 2}, {2, a <- 3}]．我們在這里用{term, command}來定義一個Log Entry,用[{term, command}, ...]來定義一個Log Entry隊列．
我們可以從上面那個例子中看到客叉，Leader節(jié)點的Log Entries和Follower節(jié)點的Log Entries沖突了．
那么Raft是解決的呢？
我們從前面的部分话告，也知道了兼搏，Leader節(jié)點維護著nextIndex[]和matchIndex[]這兩個變量．我們也知道, nextIndex[]代表的是下次要從那個index之后的Log Entry發(fā)送給Follower, matchIndex[]代表Follower和Leader的匹配的最后一個Log Entry的Index.當選舉出來一個Leader時，會將nextIndex[]初始化為它的最后一個Log Entry + 1,將matchIndex[]全部初始化為0.
這樣沙郭，當選舉完Leader之后佛呻，Leader會把它的最新的一條Log Entry發(fā)送給Follower,如果這條Log Entry不匹配，那么Follower會報告一個錯誤信息病线，然后Follower節(jié)點就依次減少nextIndex[]的值件相，并再次進行嘗試．直到Follower告訴Leader節(jié)點再扭，誒，現(xiàn)在你跟我匹配了．然后Follower節(jié)點清除那些不匹配的Log Entry并替換成Leader發(fā)送過來的Log Entry.
那會不會出現(xiàn)清除已經(jīng)提交的Log Entry的情況呢夜矗？
我個人認為是沒有這個可能的．因為在投票決定Leader的時候泛范，選擇的就是具有最新的Log Entry的節(jié)點．
集群中增加或者刪除新成員
這一部分，在實踐中應(yīng)該是必不可少的一部分．但是紊撕，說實話罢荡，論文中的這部分我是真沒看懂，所以請各位還是讀原文來獲取這部分信息．
快照
隨著時間的增加对扶，Log Entries隊列可能會越來越大．會占用大量的磁盤空間区赵，所以，我們還需要對Log Entries隊列進行壓縮浪南，以快照的形式．
Follower可以自行制作快照笼才，但是必要的時候，Leader還是需要給Follower發(fā)送快照．一般發(fā)生在Follower處理速度慢络凿，或者新節(jié)點加入的情況下．
一旦Follower發(fā)現(xiàn)Leader發(fā)來的快照中骡送，跟它的發(fā)生沖突，那么它會放棄它的快照絮记，而轉(zhuǎn)而使用Leader的．
Raft算法的弊端
各位朋友應(yīng)該已經(jīng)注意到了摔踱，我們上面的討論，都是基于Fail-Stop Failure來討論的怨愤，并沒有涉及到Byzantine Failure.
實際上派敷，Raft算法的實現(xiàn)，就是假設(shè)不會發(fā)生Byzantine Failure.當然撰洗，其他人也提出了一些基于Raft算法的改進版篮愉，能夠容忍Byzantine Failure.
