About Raft
Raft是一個(gè)實(shí)現(xiàn)分布式一致性的協(xié)議。
定義節(jié)點(diǎn)的三種狀態(tài)：
Term 選舉輪次
1、leader選舉(Leader Election)
首先，所有的節(jié)點(diǎn)均從follower state（圖1-1） 開始：
如果 followers在心跳時(shí)間內(nèi)沒接收到leader發(fā)送的心跳消息，它會(huì)變成candidate狀態(tài)。
如圖1-2的節(jié)點(diǎn)a（最快變成）變成了candidate狀態(tài)。
然后節(jié)點(diǎn)a會(huì)向集群中所有節(jié)點(diǎn)（節(jié)點(diǎn)b和c）發(fā)起投票，圖1-3中的綠色實(shí)點(diǎn)。
然后節(jié)點(diǎn)b和c回復(fù)節(jié)點(diǎn)a的投票，圖1-4中的綠色虛點(diǎn)
如果candidate（圖1-4中的節(jié)點(diǎn)a）收到了過半節(jié)點(diǎn)的回復(fù)，則節(jié)點(diǎn)a就變成了leader，圖1-5中的節(jié)點(diǎn)a
這個(gè)處理過程就是Leader選舉。接下來，系統(tǒng)中所有的變更都要leader節(jié)點(diǎn)發(fā)起處理。并通過日志entry的形式假追加到節(jié)點(diǎn)的日志文件尾部。
Detail:
在raft算法中，有兩個(gè)超時(shí)配置項(xiàng)控制著leader選舉，第一個(gè)是選舉超時(shí)時(shí)間>（election timeout）,該配置項(xiàng)意味著follower會(huì)等待leader選舉的時(shí)間段，如果在這>個(gè)時(shí)間段內(nèi)，還沒有l(wèi)eader被選舉出來，那么該follower會(huì)變成candidate狀態(tài)，這個(gè)>選舉超時(shí)時(shí)間一般會(huì)在150ms 和 300ms區(qū)間范圍內(nèi)的一個(gè)隨機(jī)數(shù)。
情況一：
如圖1-6所示，節(jié)點(diǎn)b會(huì)首先到達(dá)選舉超時(shí)時(shí)間，那么它會(huì)先變成candidate。變成candidate后，該節(jié)點(diǎn)先回把自己的term 加1；然后為自己投票，所以Vote Count也變成了1，重置選舉超時(shí)時(shí)間如圖1-7所示。
接著，節(jié)點(diǎn)b會(huì)向集群所有節(jié)點(diǎn)發(fā)起投票請求(1的綠求)，當(dāng)follower節(jié)點(diǎn)收到投票請求后，會(huì)更新自己的term（與節(jié)點(diǎn)b一樣），然后更新投票為節(jié)點(diǎn)B并且重置選舉超時(shí)時(shí)間，向candidate（節(jié)點(diǎn)b）響應(yīng)ack（3中的綠圈），當(dāng)節(jié)b收到過半響應(yīng)后，就把自己變成leader狀態(tài)，圖1-8的展示過程。
1 2 3 4
節(jié)點(diǎn)b變成leader后，開始向集群的follower節(jié)點(diǎn)發(fā)送日志追加消息，并且開始向集群內(nèi)的follower發(fā)送心跳消息，然后follower響應(yīng)心跳，如圖1-9。此處的心跳消息就是控制著leader選舉的第二個(gè)超時(shí)配置項(xiàng)，換言之，當(dāng)leader選舉出來后，如果follower在心跳時(shí)間內(nèi)還沒收到消息，follower會(huì)在次變成candidate，重新發(fā)起leader選舉。
情況1.1，此時(shí)follower節(jié)點(diǎn)時(shí)因?yàn)樵瓉淼墓?jié)點(diǎn)B確實(shí)掛了，follower節(jié)點(diǎn)確實(shí)無法再收到心跳請求。這是節(jié)點(diǎn)A成立leader節(jié)點(diǎn)（1-10.1），此時(shí)自己的term加一變成2，在向集群所有節(jié)點(diǎn)發(fā)送心跳消息（包括已掛節(jié)點(diǎn)，1-10.2中的實(shí)心紅點(diǎn)），當(dāng)然如果follower收到心跳消息后，發(fā)現(xiàn)自己的term比leader小，那么會(huì)馬上更新自己的term，這里節(jié)點(diǎn)c更新自己的term為2，并回復(fù)心跳消息（1-10.3）
1 2 3
順便說一下，過半機(jī)制就可以保證每一輪leader選舉，就只有一個(gè)節(jié)點(diǎn)可以成為leader。
情況二：
剛剛的情況一是剛好只有一個(gè)節(jié)點(diǎn)變成candidate,那么如果同時(shí)有兩個(gè)節(jié)點(diǎn)變成candidate，會(huì)怎么處理呢？
1 2 3 4 5
如圖1-11，在過了選舉超時(shí)時(shí)間后，集群中的節(jié)點(diǎn)B和節(jié)點(diǎn)C同時(shí)變成了candidate后（1-11.2），各自為自己投票后，并且同時(shí)向集群內(nèi)所有節(jié)點(diǎn)發(fā)起投票（1-11.3），然后節(jié)點(diǎn)A會(huì)為節(jié)點(diǎn)B投票，節(jié)點(diǎn)，節(jié)點(diǎn)D會(huì)為節(jié)點(diǎn)C投票。這里，follower的投票策略為，假如follower已近為節(jié)點(diǎn)X投票，并且節(jié)點(diǎn)X的term為n,那么，follower就不會(huì)接受term <=n的其他投票。這時(shí)候，節(jié)點(diǎn)B和節(jié)點(diǎn)C都獲取了兩票投票，由于沒獲取過半的投票贊成，所以兩者只能重置自己的選舉超時(shí)時(shí)間。最后節(jié)點(diǎn)C最先過了選舉超時(shí)時(shí)間，然后，然后更新自己的term并重新發(fā)起投票，這時(shí)，由于沒有競選者，就成了master節(jié)點(diǎn)（1-11.5）。
2、日志復(fù)制（Log Replication）
如上圖的2-1，一個(gè)客戶端向leader節(jié)點(diǎn)a發(fā)起事務(wù)請求set 5，leader節(jié)點(diǎn)收到請求后，會(huì)追加log entry到本地日志中，但不會(huì)立刻commit（更新節(jié)點(diǎn)狀態(tài)）。
Leader節(jié)點(diǎn)會(huì)向集群中所有節(jié)點(diǎn)發(fā)起事務(wù)請求set 5，follower節(jié)點(diǎn)收到請求后，會(huì)追加log entry到本地日志中，然后向leader節(jié)點(diǎn)發(fā)送ack（圖2-3中的紅點(diǎn)）
Leader節(jié)點(diǎn)會(huì)一直等待follower的ack響應(yīng)，直到有過半的ack后，leader會(huì)commit狀態(tài)，把自己的狀態(tài)變成5（圖2-4中的節(jié)點(diǎn)a）
接著Leader節(jié)點(diǎn)會(huì)向集群中所有的follower節(jié)點(diǎn)發(fā)送commit請求（圖2-5的紅色請求），然后，follower接受到commit請求后，會(huì)更新自己的狀態(tài)為5，并相應(yīng)客戶端。此時(shí)，系統(tǒng)中的集群就變成一致性狀態(tài)了，這個(gè)處理流程稱為日志復(fù)制。
特殊情況（網(wǎng)絡(luò)分區(qū)），如圖2-6所示：
集群網(wǎng)絡(luò)健康時(shí)，節(jié)點(diǎn)B成為leader節(jié)點(diǎn)；可是，當(dāng)集群運(yùn)行一段時(shí)間后，網(wǎng)絡(luò)出現(xiàn)了分區(qū)現(xiàn)象，節(jié)點(diǎn)B（leader）節(jié)點(diǎn)僅可以和節(jié)點(diǎn)A互相通訊；而節(jié)點(diǎn)C、D、E可以互相通訊，并且節(jié)點(diǎn)D變成了leader節(jié)點(diǎn)（因?yàn)楂@得了過半贊成），這時(shí)，一個(gè)集群內(nèi)就會(huì)有兩個(gè)leader節(jié)點(diǎn)（B、D）。
此時(shí)，有兩個(gè)客戶端c1 和c2,c1向master節(jié)點(diǎn)D發(fā)起事務(wù)請求，獲得過半處理后，會(huì)響應(yīng)c1成功；c2向master節(jié)點(diǎn)B發(fā)起事務(wù)請求，由于無法獲得過半請求，B節(jié)點(diǎn)和A節(jié)點(diǎn)僅僅會(huì)記錄c2的事務(wù)請求，但不會(huì)commit。
當(dāng)網(wǎng)絡(luò)恢復(fù)正常后，節(jié)點(diǎn)D可以和節(jié)點(diǎn)B、A通訊了，并且發(fā)現(xiàn)節(jié)點(diǎn)D的Term比自己高，那么會(huì)回滾剛剛記錄c2的請求事務(wù)；并同步節(jié)點(diǎn)D最新的日志，同時(shí)更新自己的term。
動(dòng)畫請看：
http://thesecretlivesofdata.com/raft/
