一、角色模型
(一) Raft-node 存在三種角色：
1、Follower：接受來自leader和Candidate 的請求，節(jié)點啟動以后的初始化狀態(tài)一定是Follower
2、Leader：處理來自客戶端的請求，并且承擔(dān)log復(fù)制到Follower的工作
3、Candidate：發(fā)起投票，競選Leader（Follower 超時變成 Candidate）
(二) Raft Strong Leader
1、Raft是限制僅有Leader節(jié)點可以處理寫入操作
2、Leader負(fù)責(zé)與所有的Follower節(jié)點進(jìn)行通信，負(fù)責(zé)將log復(fù)制到Follower節(jié)點，并收集大多數(shù)節(jié)點的應(yīng)答
3、Leader需要向所用的Follower節(jié)點發(fā)起心跳，保持和確認(rèn)Leader地位
二、選舉
(一) Terms
時間被劃分為一個個任期 (term)，term id 按時間軸單調(diào)遞增；
每一個任期的開始都是 Leader 選舉，選舉成功之后，Leader 在任期內(nèi)管理整個集群，也就是 “選舉 + 常規(guī)操作”
每個任期最多一個 Leader，可能沒有 Leader (spilt-vote 導(dǎo)致)。
(二) 選舉示意圖
- 在系統(tǒng)初始化的時候，所有節(jié)點都出于Follower的角色。
2. 每個節(jié)點隨機分配了倒計時時間。倒計時結(jié)束以后，節(jié)點從Follower --> Candidate，并發(fā)起投票
3. B、C節(jié)點只收到了節(jié)點A的投票請求，于是都投票給節(jié)點A，節(jié)點A成為Leader角色，并與定時向所有的Follower節(jié)點發(fā)起Heartbeat，保持和確認(rèn)自己Leader角色。
上面描述了只有一個Candidate角色時，是如何發(fā)起投票的，如果同時有多個Candidate節(jié)點發(fā)起投票怎么辦呢？？
節(jié)點A和節(jié)點D同時成為Candidate角色發(fā)起投票，并獲取到一半的票數(shù)，都不滿足得到大多數(shù)票數(shù)的條件，因此會重新開始倒計時（時間是隨機的），最先倒計時結(jié)束的發(fā)起新一輪投票
節(jié)點B和節(jié)點C投票給節(jié)點A以后，就會拒絕投票給節(jié)點D，節(jié)點A晉升為Leader節(jié)點，并且發(fā)起Hearbeat，節(jié)點D收到HeartBeat以后自動轉(zhuǎn)化為Follower節(jié)點。
(三) 選舉限制
在任何基于領(lǐng)導(dǎo)人的一致性算法中，領(lǐng)導(dǎo)人都必須存儲所有已經(jīng)提交的日志條目。在某些一致性算法中，例如 Viewstamped Replication，
某個節(jié)點即使是一開始并沒有包含所有已經(jīng)提交的日志條目，它也能被選為領(lǐng)導(dǎo)者。
Raft 使用投票的方式來阻止一個候選人贏得選舉除非這個候選人包含了所有已經(jīng)提交的日志條目。候選人為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點，
這意味著每一個已經(jīng)提交的日志條目在這些服務(wù)器節(jié)點中肯定存在于至少一個節(jié)點上。如果候選人的日志至少和大多數(shù)的服務(wù)器節(jié)點一樣新（這個新的定義會在下面討論），
那么他一定持有了所有已經(jīng)提交的日志條目。請求投票 RPC 實現(xiàn)了這樣的限制： RPC 中包含了候選人的日志信息，然后投票人會拒絕掉那些日志沒有自己新的投票請求。
Raft 通過比較兩份日志中最后一條日志條目的索引值和任期號定義誰的日志比較新。如果兩份日志最后的條目的任期號不同，那么任期號大的日志更加新。
如果兩份日志最后的條目任期號相同，那么日志比較長的那個就更加新。
三、日志復(fù)制
(一) 日志復(fù)制原理介紹
一旦一個領(lǐng)導(dǎo)人被選舉出來，他就開始為客戶端提供服務(wù)。客戶端的每一個請求都包含一條被復(fù)制狀態(tài)機執(zhí)行的指令。領(lǐng)導(dǎo)人把這條指令作為一條新的日志條目附加到日志中去，然后并行的發(fā)起附加條目 RPCs 給其他的服務(wù)器，讓他們復(fù)制這條日志條目。
當(dāng)這條日志條目被安全的復(fù)制（下面會介紹），領(lǐng)導(dǎo)人會應(yīng)用這條日志條目到它的狀態(tài)機中然后把執(zhí)行的結(jié)果返回給客戶端。如果跟隨者崩潰或者運行緩慢，再或者網(wǎng)絡(luò)丟包，領(lǐng)導(dǎo)人會不斷的重復(fù)嘗試附加日志條目 RPCs （盡管已經(jīng)回復(fù)了客戶端）直到所有的跟隨者都最終存儲了所有的日志條目。
日志由有序序號標(biāo)記的條目組成。每個條目都包含創(chuàng)建時的任期號（圖中框中的數(shù)字），和一個狀態(tài)機需要執(zhí)行的指令。一個條目當(dāng)可以安全的被應(yīng)用到狀態(tài)機中去的時候，就認(rèn)為是可以提交了。
在上圖中，每一條日志條目中存儲了一條狀態(tài)機指令，和收到這條指令時的任期，并且每條日志條目按index順序存儲。raft算法的一致性模塊，覺得了那些日志條目被commited，并且將對應(yīng)的命令應(yīng)用到狀態(tài)機中
raft的日志系統(tǒng)存在一下特性：
- 如果在不同的日志中的兩個條目擁有相同的索引和任期號，那么他們存儲了相同的指令。
- 如果在不同的日志中的兩個條目擁有相同的索引和任期號，那么他們之前的所有日志條目也全部相同
(二) 日志的一致性保證
在Raft算法中，領(lǐng)導(dǎo)人處理不一致是通過強制跟隨者直接復(fù)制自己的日志來解決。這意味著在跟隨者中的沖突的日志條目會被領(lǐng)導(dǎo)人的日志覆蓋
使得跟隨者的日志進(jìn)入和自己一致的狀態(tài)，領(lǐng)導(dǎo)人必須找到最后兩者達(dá)成一致的地方，然后刪除從那個點之后的所有日志條目，發(fā)送自己的日志給跟隨者。
所有的這些操作都在進(jìn)行附加日志 RPCs 的一致性檢查時完成。領(lǐng)導(dǎo)人針對每一個跟隨者維護(hù)了一個 nextIndex，這表示下一個需要發(fā)送給跟隨者的日志條目的索引地址。
當(dāng)一個領(lǐng)導(dǎo)人剛獲得權(quán)力的時候，他初始化所有的 nextIndex 值為自己的最后一條日志的index加1（圖 7 中的 11）。如果一個跟隨者的日志和領(lǐng)導(dǎo)人不一致，
那么在下一次的附加日志 RPC 時的一致性檢查就會失敗。在被跟隨者拒絕之后，領(lǐng)導(dǎo)人就會減小 nextIndex 值并進(jìn)行重試。最終 nextIndex 會在某個位置使得領(lǐng)導(dǎo)人和跟隨者的日志達(dá)成一致。
四、網(wǎng)絡(luò)分區(qū)
(一) Symmetric network partition tolerance（對稱網(wǎng)絡(luò)分區(qū)容忍性）
如上圖 S1 為當(dāng)前 leader，網(wǎng)絡(luò)分區(qū)造成 S2 不斷增加本地 term，為了避免網(wǎng)絡(luò)恢復(fù)后 S2 發(fā)起選舉導(dǎo)致正在良心 工作的 leader step-down，從而導(dǎo)致整個集群重新發(fā)起選舉，
可以增加了 pre-vote 過程來避免這個問題的發(fā)生。在 request-vote 之前會先進(jìn)行 pre-vote(currentTerm + 1, lastLogIndex, lastLogTerm)，多數(shù)派成功后才會轉(zhuǎn)換狀態(tài)為 candidate 發(fā)起真正的 request-vote，
所以分區(qū)后的節(jié)點，pre-vote 不會成功，也就不會導(dǎo)致集群一段時間內(nèi)無法正常提供服務(wù)。
(二) Asymmetric network partition tolerance(非對稱網(wǎng)絡(luò)分區(qū)容忍性)
如上圖 S1 為當(dāng)前 leader，S2 不斷超時觸發(fā)選主，S3 提升 term 打斷當(dāng)前 lease，從而拒絕 leader 的更新。
可以增加了一個 tick 的檢查，每個 follower 維護(hù)一個時間戳記錄下收到 leader 上數(shù)據(jù)更新的時間(也包括心跳)，只有超過 election timeout 之后才允許接受 request-vote 請求。
參考文檔
https://juejin.im/post/5c88756a6fb9a049f9136c1a
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
