[轉(zhuǎn)]
過(guò)去, Paxos一直是分布式協(xié)議的標(biāo)準(zhǔn)，但是Paxos難于理解践惑，更難以實(shí)現(xiàn)铲敛，Google的分布式鎖系統(tǒng)Chubby作為Paxos實(shí)現(xiàn)曾經(jīng)遭遇到很多坑膜眠。
來(lái)自Stanford的新的分布式協(xié)議研究稱(chēng)為Raft拗踢，它是一個(gè)為真實(shí)世界應(yīng)用建立的協(xié)議脚牍，主要注重協(xié)議的落地性和可理解性。
在了解Raft之前巢墅，我們先了解Consensus一致性這個(gè)概念诸狭，它是指多個(gè)服務(wù)器在狀態(tài)達(dá)成一致，但是在一個(gè)分布式系統(tǒng)中君纫，因?yàn)楦鞣N意外可能作谚，有的服務(wù)器可能會(huì)崩潰或變得不可靠，它就不能和其他服務(wù)器達(dá)成一致?tīng)顟B(tài)庵芭。這樣就需要一種Consensus協(xié)議，一致性協(xié)議是為了確保容錯(cuò)性雀监，也就是即使系統(tǒng)中有一兩個(gè)服務(wù)器當(dāng)機(jī)双吆，也不會(huì)影響其處理過(guò)程。
為了以容錯(cuò)方式達(dá)成一致会前，我們不可能要求所有服務(wù)器100%都達(dá)成一致?tīng)顟B(tài)好乐，只要超過(guò)半數(shù)的大多數(shù)服務(wù)器達(dá)成一致就可以了，假設(shè)有N臺(tái)服務(wù)器瓦宜，N/2 +1 就超過(guò)半數(shù)蔚万，代表大多數(shù)了。
Paxos和Raft都是為了實(shí)現(xiàn)Consensus一致性這個(gè)目標(biāo)临庇，這個(gè)過(guò)程如同選舉一樣反璃，參選者需要說(shuō)服大多數(shù)選民(服務(wù)器)投票給他，一旦選定后就跟隨其操作假夺。Paxos和Raft的區(qū)別在于選舉的具體過(guò)程不同淮蜈。
在Raft中，任何時(shí)候一個(gè)服務(wù)器可以扮演下面角色之一：
Leader: 處理所有客戶(hù)端交互已卷，日志復(fù)制等梧田，一般一次只有一個(gè)Leader.
Follower: 類(lèi)似選民，完全被動(dòng)
Candidate候選人: 類(lèi)似Proposer律師，可以被選為一個(gè)新的領(lǐng)導(dǎo)人裁眯。
Raft階段分為兩個(gè)鹉梨，首先是選舉過(guò)程，然后在選舉出來(lái)的領(lǐng)導(dǎo)人帶領(lǐng)進(jìn)行正常操作穿稳，比如日志復(fù)制等存皂。下面用圖示展示這個(gè)過(guò)程：
-
任何一個(gè)服務(wù)器都可以成為一個(gè)候選者Candidate，它向其他服務(wù)器Follower發(fā)出要求選舉自己的請(qǐng)求：
-
其他服務(wù)器同意了司草，發(fā)出OK艰垂。
注意如果在這個(gè)過(guò)程中，有一個(gè)Follower當(dāng)機(jī)埋虹，沒(méi)有收到請(qǐng)求選舉的要求猜憎，因此候選者可以自己選自己，只要達(dá)到N/2 + 1 的大多數(shù)票搔课，候選人還是可以成為L(zhǎng)eader的胰柑。
-
這樣這個(gè)候選者就成為了Leader領(lǐng)導(dǎo)人，它可以向選民也就是Follower們發(fā)出指令爬泥，比如進(jìn)行日志復(fù)制柬讨。
-
以后通過(guò)心跳進(jìn)行日志復(fù)制的通知
-
如果一旦這個(gè)Leader當(dāng)機(jī)崩潰了，那么Follower中有一個(gè)成為候選者袍啡，發(fā)出邀票選舉。
-
Follower同意后，其成為L(zhǎng)eader辩越，繼續(xù)承擔(dān)日志復(fù)制等指導(dǎo)工作：
值得注意的是黔攒，整個(gè)選舉過(guò)程是有一個(gè)時(shí)間限制的督惰，如下圖：
Splite Vote是因?yàn)槿绻瑫r(shí)有兩個(gè)候選人向大家邀票姑丑，這時(shí)通過(guò)類(lèi)似加時(shí)賽來(lái)解決栅哀，兩個(gè)候選者在一段timeout比如300ms互相不服氣的等待以后留拾，因?yàn)殡p方得到的票數(shù)是一樣的，一半對(duì)一半沦偎，那么在300ms以后咳蔚，再由這兩個(gè)候選者發(fā)出邀票，這時(shí)同時(shí)的概率大大降低侈询，那么首先發(fā)出邀票的的候選者得到了大多數(shù)同意糯耍，成為領(lǐng)導(dǎo)者Leader温技，而另外一個(gè)候選者后來(lái)發(fā)出邀票時(shí)，那些Follower選民已經(jīng)投票給第一個(gè)候選者震檩，不能再投票給它抛虏，它就成為落選者了，最后這個(gè)落選者也成為普通Follower一員了霜旧。
日志復(fù)制
下面以日志復(fù)制為例子說(shuō)明Raft算法挂据，假設(shè)Leader領(lǐng)導(dǎo)人已經(jīng)選出儿普，這時(shí)客戶(hù)端發(fā)出增加一個(gè)日志的要求眉孩，比如日志是"sally"：
-
Leader要求Followe遵從他的指令，都將這個(gè)新的日志內(nèi)容追加到他們各自日志中：
3.大多數(shù)follower服務(wù)器將日志寫(xiě)入磁盤(pán)文件后凛虽，確認(rèn)追加成功凯旋，發(fā)出Commited Ok:
- 在下一個(gè)心跳heartbeat中至非，Leader會(huì)通知所有Follwer更新commited 項(xiàng)目糠聪。
對(duì)于每個(gè)新的日志記錄，重復(fù)上述過(guò)程枷颊。
如果在這一過(guò)程中戳杀，發(fā)生了網(wǎng)絡(luò)分區(qū)或者網(wǎng)絡(luò)通信故障夭苗，使得Leader不能訪問(wèn)大多數(shù)Follwers了信卡，那么Leader只能正常更新它能訪問(wèn)的那些Follower服務(wù)器题造，而大多數(shù)的服務(wù)器Follower因?yàn)闆](méi)有了Leader傍菇，他們重新選舉一個(gè)候選者作為L(zhǎng)eader，然后這個(gè)Leader作為代表于外界打交道界赔，如果外界要求其添加新的日志丢习，這個(gè)新的Leader就按上述步驟通知大多數(shù)Followers淮悼，如果這時(shí)網(wǎng)絡(luò)故障修復(fù)了袜腥，那么原先的Leader就變成Follower，在失聯(lián)階段這個(gè)老Leader的任何更新都不能算commit，都回滾福侈，接受新的Leader的新的更新。
總結(jié)：目前幾乎所有語(yǔ)言都已經(jīng)有支持Raft算法的庫(kù)包辽社，具體可參考：raftconsensus.github.io
