參考資料：
https://raft.github.io/
https://raft.github.io/raft.pdf
http://thesecretlivesofdata.com/raft/
https://www.cnblogs.com/linbingdong/p/6442673.html
一、Raft基礎概念
1. 節(jié)點狀態(tài)
節(jié)點的狀態(tài)有三種：leader策肝、follower和candidate。任何一個時刻，節(jié)點都只能處于三種狀態(tài)中的一種镜雨。在正常情況下侥啤，集群中只有一個leader并且其他節(jié)點全部是follower末购。
不同狀態(tài)下節(jié)點的行為表現(xiàn)：
- leader：處理所有的客戶端請求预伺；日志復制茫船；心跳操作。
- follwer：不會發(fā)送任何情況扭屁，只是簡單的響應來自leader和candidate的請求。當客戶端和follower通信涩禀，follower會將請求重定向給leader料滥。
- candidate：用來選舉一個新的leader。
2. 節(jié)點RPC通信
Raft 算法中服務器節(jié)點之間使用 RPC 進行通信艾船，并且基本的一致性算法只需要兩種類型的 RPC：請求投票（RequestVote）RPC和追加條目（AppendEntries）RPC葵腹。
- 請求投票（RequestVote）RPC：由candidate在選舉期間發(fā)起，請求follower給自己投票屿岂；
- 追加條目（AppendEntries）RPC：由leader發(fā)起践宴，用來復制日志和提供一種心跳機制。
RequestVote RPC
RequestVote RPC是被candidate調(diào)用以收集投票爷怀。
-請求參數(shù)
term：候選人的任期號
candidateId：請求投票的候選人id
lastLogIndex：候選人最新日志條目的索引值（槽位）
lastLogTerm：候選人最新日志條目對應的任期號
-返回值
term：當前任期號阻肩，用于候選人更新本地的term值
voteGranted：如果候選人得到了Follower的這張選票，則為true运授，否則為false
-RPC接收者實現(xiàn)
1）如果term < currentTerm，即RPC的第一個參數(shù)term的值小于接收方本地維護的term（currentTerm）值，則返回（currentTerm啸罢，false）履磨，以提醒調(diào)用方其term過時了，并且明確地告訴這位候選人這張選票不會投給他逗宜；否則執(zhí)行步驟2雄右。
2）如果之前沒把選票投給任何人（包括自己）或者已經(jīng)把選票投給當前候選人，并且候選人的日志和自己的日志一樣新纺讲，則返回（term擂仍，true），表示在這個任期刻诊，選票都投給這位候選人防楷。如果之前已經(jīng)把選票投給其他人，那么很遺憾则涯，這張選票還是不能投給他复局，這時就會返回（term冲簿，false）。
AppendEntries RPC
AppendEntries RPC被leader調(diào)用以復制日志條目亿昏；也被用作心跳反應峦剔。
-請求參數(shù)
term：領導人的任期號
leaderId：領導人的ID，為了其他Raft節(jié)點能夠重定向客戶端請求
prevLogIndex：領導人最新日志前一個位置日志的索引值
prevLogTerm：領導人最新日志前一個位置日志的任期號
entries[]：將要追加到Follower上的日志條目角钩。發(fā)生心跳包時為空吝沫，有時為了效率而向多個節(jié)點并發(fā)發(fā)送
leaderCommit：leader服務器的commitIndex
-返回值
term：當前的任期號，即AppendEntries RPC參數(shù)中term（領導人的）與Follower本地維護的當前任期號的較大值递礼。用于領導人更新自己的任期號惨险。一旦領導人發(fā)現(xiàn)當前任期號比自己的要大，就表明自己是一個“過時”的領導人脊髓，便停止發(fā)送AppendEntries RPC辫愉，主動切換回Follower。
success：如果其他服務器包含能夠匹配prevLogIndex和preLogTerm的日志将硝，則為真
-RPC接收者實現(xiàn)
1）如果term<currentTerm恭朗，則領導人的任期號小于Follower本地維護的當前任期號，則返回（currentTerm依疼，false）痰腮；否則繼續(xù)步驟2。
2）如果Follower在prevLogIndex位置的日志的任期號與prevLogTerm不匹配律罢，則返回（term膀值，false）；否則繼續(xù)步驟3误辑。
3）Follower進行日志一致性檢查虫腋。
4）添加任何在已有的日志中不存在的條目，刪除多余的條目稀余。
5）如果leaderCommit > commitIndex悦冀，則將commitIndex（Follower自己維護的本地已提交的日志條目索引值）更新為min{leaderCommit，F(xiàn)ollower本地最新日志條目索引}睛琳。即信任Leader的數(shù)據(jù)盒蟆，樂觀地將本地已提交日志的索引值“躍進”到領導人為該Follower跟蹤記錄的那個值（除非leaderCommit比本地最新的日志條目索引值還要大）。這種場景通常發(fā)生在Follower剛從故障恢復過來的場景师骗。
3. 選舉超時時間(electionTimeout)
從上面的狀態(tài)轉(zhuǎn)換圖中可以看到历等，F(xiàn)ollower->Candidate和Candidiate->Candidate狀態(tài)的轉(zhuǎn)變是通過time outs來觸發(fā)的，這個觸發(fā)的time outs叫做選舉超時時間辟癌。具體的來講就是發(fā)生新一輪選舉的超時時間寒屯，或者是Follower或Candidate狀態(tài)的維持超時時間。
節(jié)點啟動，初始都為Follower狀態(tài)寡夹。那么問題來了处面，什么時候進行選舉操作。在解決這個問題前菩掏，需要明確的是魂角，選舉操作是做些什么。選舉操作就是節(jié)點從Follower狀態(tài)變成Candidate狀態(tài)智绸，然后處于Candidate狀態(tài)的節(jié)點向其他的節(jié)點發(fā)送請求投票RPC野揪，請求其他的節(jié)點將它投為Leader。所以瞧栗，這里第一步就是節(jié)點狀態(tài)需要從Follower狀態(tài)轉(zhuǎn)化成Candidate狀態(tài)斯稳，而這個轉(zhuǎn)變的觸發(fā)條件就是Follower節(jié)點的選舉時間超時。
處于Follower狀態(tài)的節(jié)點都有權(quán)進行Leader的競爭迹恐，也就是說都可能從Follower變成Candidate平挑，多個Follower同時成為Candidate，這樣就會出現(xiàn)競爭成為Leader的情況發(fā)生系草。 Raft中對這種情況稱作瓜分選票。為了減少瓜分選票這種情況的出現(xiàn)唆涝，Raft協(xié)議對這個選舉超時時間的取值是這樣處理的：處于Follower狀態(tài)的節(jié)點的選舉超時時間是從一個固定的區(qū)間（例如150-300毫秒）隨機選擇的找都。在固定的區(qū)間隨機選擇一個時間值，這樣就可以減少多個節(jié)點的選舉時間同時超時的情況發(fā)生廊酣。不過能耻，這里要明確的是這里是減少，但是不能完全避免亡驰，因為隨機選擇也會獲取到相同的值晓猛。
這里我們選取單Candidate的情況來說明之后選舉超時時間的變化。有A凡辱、B戒职、C三個服務器節(jié)點，啟動后透乾，節(jié)點的狀態(tài)如下：
上圖中A洪燥，B，C三個節(jié)點都處于Follower狀態(tài)乳乌，C節(jié)點的超時時間最短捧韵，所以C的狀態(tài)最先由Follower轉(zhuǎn)變成Candidate。下圖是節(jié)點C由Follower變成Candidate那一刻的狀態(tài)圖示：
C節(jié)點由Follower狀態(tài)變成Candidate狀態(tài)汉操，選舉操作開始再来。上面C節(jié)點中的Timeout值是當它處于Follower狀態(tài)時的選舉超時時間，現(xiàn)在變成了0×琢觯現(xiàn)在問題就來了芒篷，處于Candidate狀態(tài)的C節(jié)點內(nèi)還有選舉超時時間嗎搜变？當時是有的，Raft協(xié)議對于Candidate節(jié)點是這樣規(guī)定的：每個candidate在開始一次選舉的時候會重置一個隨機的選舉超時時間梭伐，然后一直等待直到選舉超時痹雅。可以說糊识，F(xiàn)ollower中選舉超時時間控制選舉事件的發(fā)生绩社，Candidate中的選舉超時時間控制選舉投票動作的發(fā)生。節(jié)點成為Candidate之后赂苗，就會向其他節(jié)點發(fā)送請求投票RPC請求愉耙，然后就在選舉超時時間消逝之前的這段時間內(nèi)（等待投票期間）等待投票結(jié)果。若選舉超時拌滋，Candidate節(jié)點無法成為Leader朴沿，并且還是處于Candidate狀態(tài)（后面說明狀態(tài)的變化），那么新一輪的選舉投票動作發(fā)生败砂，Candidate繼續(xù)發(fā)送請求投票RPC赌渣，當然在開始選舉之前會重置選舉超時時間。
A和B節(jié)點的選舉超時時間如何變化呢昌犹？
在等待投票期間坚芜，C成為Candidate后會向其他節(jié)點發(fā)送請求投票RPC請求，處于Follower狀態(tài)的節(jié)點接收到這個請求后就會對選舉超時時間進行重置斜姥『枋可以看到，等待投票期間Follower節(jié)點選舉超時時間的重置可以說是Candidate的RPC請求觸發(fā)的铸敏。
除了等待投票期間缚忧，F(xiàn)ollower節(jié)點的選舉超時時間會重置外，當Candidate節(jié)點成為Leader之后杈笔，也會進行重置闪水。當一個節(jié)點成為Leader之后，它會向其他的服務器節(jié)點發(fā)送心跳（不包含日志條目的AppendEntries RPC）來確定自己的地位并阻止新的選舉蒙具。Follower節(jié)點接收到心跳消息后就會重置自己的選舉超時時間敦第。
4. 任期（term）
Leader選舉開始到結(jié)束，會產(chǎn)生選舉出Leader和未選舉出Leader這兩種結(jié)果店量。未選舉出Leader包含一個時間段：選舉進行時時間段芜果；選舉出Leader這種情況包含有兩個時間段：選舉進行時時間段和選出Leader到下一次選舉開始時間段（Leader在位時間段）。進入到下一次選舉融师，那么時間段就如此反復右钾。
上圖描述了選舉到下一次選舉的時間段圖示，若將從左至右看作是時間的流逝，我們會發(fā)現(xiàn)時間被分割成任意長度的時間段舀射。這些時間段就是Raft中所定義的"任期（term）"概念窘茁。
任期是一個全局的、連續(xù)遞增的的整數(shù)脆烟。每進行一次選舉山林，任期值加1，每個節(jié)點都會記錄當前的任期值（currentTerm）邢羔。
每一個服務器節(jié)點存儲一個當前任期號驼抹，該編號隨著時間單調(diào)遞增。
那么任期在Raft協(xié)議中的具體作用是什么呢拜鹤？
考慮下面的一個場景框冀，在第一次選舉過后，A成為了Leader敏簿，此時各個節(jié)點的任期值為1明也，即currentTerm=1。這時候A會定期地往B和C節(jié)點發(fā)送心跳反應來維持自己的地位和阻止下一次選舉的發(fā)生惯裕∥率考慮到網(wǎng)絡節(jié)點通信的故障A在B的選舉超時時間之內(nèi)，未能及時發(fā)送心跳反應蜻势，這時候B的選舉超時時間過期撑刺，使得它的狀態(tài)變成了Candidate，新的一次選舉發(fā)生咙边，B的任期加1，變成了2次员。此時會發(fā)生些什么事以及如何處理败许？
發(fā)生的事情如下：
- A繼續(xù)向B和C發(fā)送心跳請求
- B向A和C發(fā)送請求投票RPC
如何處理呢？這時候任期的作用就體現(xiàn)出來了淑蔚。
A向B發(fā)送心跳請求：此時B的任期已經(jīng)為2市殷，比A的任期大，表示已經(jīng)進入到下一個選舉周期了刹衫，A是上一任的Leader，B表示你已經(jīng)無效了带迟，我不可能接受你的請求重置我的選舉超時時間了。也就是說A的任期號已經(jīng)過期了嗅绰。Raft協(xié)議規(guī)定如下：如果一個節(jié)點接收到一個包含過期的任期號的請求，它會直接拒絕這個請求。
B向C發(fā)送請求投票RPC：B的任期為2窘面，C的狀態(tài)為Follower财边，任期為1肌括。一個新選舉周期的候選人發(fā)送投票請求，作為Follower的節(jié)點會接受此請求酣难，并且會更新自己的任期為當前的任期。Raft協(xié)議規(guī)定如下：如果一個服務器的當前任期號比其他的小慧库，該服務器會將自己的任期號更新為較大的那個值馋嗜。
B向A發(fā)送請求投票RPC：A作為老一屆的Leader，在新的候選人面前已經(jīng)是日落西山了甘磨，那么就必須接受這種變遷眯停。Raft協(xié)議規(guī)定如下：如果一個candidate或者leader發(fā)現(xiàn)自己的任期號過期了莺债，它會立即回到follower 狀態(tài)。
從我們上面的時間段的圖還可以看出椎侠，任期在Raft協(xié)議中也起到了邏輯時鐘的作用措拇，可以用來區(qū)分事件的發(fā)生順序。
二浅悉、Raft算法中的狀態(tài)术健、規(guī)則和關鍵特性
1. 狀態(tài)
currentTerm
當前的任期號（初始啟動為0粘衬，單調(diào)遞增）
votedFor
當前任期獲得投票的節(jié)點的candidatedId，無則為null
log[]
日志條目泼舱；每一個條目包含了應用于狀態(tài)機的命令和leader接收到記錄時的任期號（初始索引為1）
commitIndex
當前節(jié)點已知的娇昙、最大的尺迂、已提交的日志索引值（初始為0，單調(diào)遞增）
lastApplied
當前節(jié)點最后一條被應用到狀態(tài)機中的日志索引值（初始為0噪裕，單調(diào)遞增）
下面的狀態(tài)只在Leader節(jié)點進行維護：Leader節(jié)點中不僅需要知道自己的關于日志條目的信息膳音，還需要了解集群中其他Follower節(jié)點的這些信息铃诬，例如趣席，Leader節(jié)點需要了解每個Follower節(jié)點的日志復制到哪個位置，從而決定下次發(fā)送Append Entries消息中包含哪些日志記錄想罕。
nextIndex[]
記錄了需要發(fā)送個每個Follower節(jié)點的下一條日志的索引值（初始為leader最后一條條目索引+1）
matchIndex[]
記錄了已經(jīng)復制給每個Follower節(jié)點的最大的日志索引值（初始為0按价，單調(diào)遞增）
通過https://raft.github.io中"Raft可視化"示例程序運行截圖來對這兩個數(shù)組有一個初步感知：
2. 規(guī)則
所有節(jié)點規(guī)則
- 如果commitIndex > lastApplied楼镐，則增加lastApplied逮走，將log[lastApplied]應用到狀態(tài)機
- 如果RPC請求或返回包含的任期T>currentTerm师溅，則設置currentTerm = T盾舌，節(jié)點轉(zhuǎn)換成follower節(jié)點妖谴。
Followers規(guī)則
- 響應candidate和leader節(jié)點的RPC請求
- 如果選舉超時時間到期未從leader節(jié)點收到AppendEntries RPC請求或者未投票給candidate酌摇，則節(jié)點轉(zhuǎn)換成candidate
Candidates規(guī)則
- 關于轉(zhuǎn)換為candidate窑多，開始選舉：
-# 增加currentTerm
-# 投票給自己
-# 重置選舉計時器
-# 發(fā)送RequestVote RPCs給其他節(jié)點 - 如果收到了大多數(shù)節(jié)點的投票洼滚，則成為leader
- 如果從一個新的leader收到AppendEntries RPC遥巴，則轉(zhuǎn)變成follower
- 如果選舉超時時間過期，則開始一輪新的選舉
Leaders規(guī)則
- 選舉完后拾弃，則發(fā)送初始的空的AppendEntries RPCs（心跳）給其他節(jié)點摆霉，定時發(fā)送以阻止新的選舉產(chǎn)生
- 如果從客戶端接收到命令斯入，則將條目追加到本地日志，當條目應用到狀態(tài)機后再回復給客戶端
- 如果對于一個follower來說當前l(fā)eader的最后一條日志索引值>=nextIndex增蹭，則發(fā)送從nextIndex開始的日志條目給follower滋迈。
-# 如果成功户誓，則更新follower對應的nextIndex和matchIndex
-# 如果因為日志不一致導致AppendEntries失敗帝美，則減小nextIndex后重試 - 如果存在一個這樣的N，N>commitIndex庇忌，大部分的match[i]>=N舰褪，并且log[N].term == currentTerm占拍，則設置commitIndex == N捎迫。
3. 關鍵特性
- Election Safety：在任意一個任期內(nèi)窄绒，最多只有一個leader颗祝。
- Leader Append-Only：Leader從來不會覆蓋或者刪除自己的日志條目恼布，只追加新的日志條目折汞。
- Log Matching：如果不同日志中的兩個條目擁有相同的索引和任期號爽待，那么他們之前的所有日志條目也都相同。
- Leader Completeness：對于給定的任意任期號膏燃， leader都包含了之前各個任期所有被提交的日志條目何什。
- State Machine Safety：如果有任何的服務器節(jié)點已經(jīng)應用了一個特定的日志條目到它的狀態(tài)機中处渣，那么其他服務器節(jié)點不能在同一個日志索引位置應用一條不同的指令。
三黍衙、Leader選舉
關于Leader選舉的流程上面介紹"選舉超時時間"的時候有所涉及琅翻，此章節(jié)對于選舉中涉及到的一些重要點進行描述柑贞。
1. Candidate節(jié)點
Raft協(xié)議中對Candidate節(jié)點有這樣的描述：
要開始一次選舉過程凌外，follower 先增加自己的當前任期號并且轉(zhuǎn)換到 candidate 狀態(tài)涛浙。然后投票給自己并且并行地向集群中的其他服務器節(jié)點發(fā)送 RequestVote RPC（讓其他服務器節(jié)點投票給它）。Candidate 會一直保持當前狀態(tài)直到以下三件事情之一發(fā)生：(a) 它自己贏得了這次的選舉（收到過半的投票）胸墙，(b) 其他的服務器節(jié)點成為 leader 按咒，(c) 一段時間之后沒有任何獲勝者励七。
根據(jù)上面的描述然后結(jié)合節(jié)點狀態(tài)轉(zhuǎn)換圖，Candidate節(jié)點的狀態(tài)轉(zhuǎn)變就有下面這三種情況：
- (a) 贏得了選舉成為Leader
當一個candidate獲得集群中過半服務器節(jié)點針對同一個任期的投票吼野，它就贏得了這次選舉并成為 leader 瞳步。 - (b) 其他的服務節(jié)點成為Leader
上面在描述 "選舉超時時間" 的時候說到過腰奋，它是觸發(fā)新一次選舉開始的觸發(fā)器劣坊，同時通過選取一定區(qū)間內(nèi)的隨機時間來保證很少出現(xiàn)選票瓜分的請求，也就是保證很少出現(xiàn)多個Candidate的情況局冰，但是很少并不意味著不出現(xiàn)锐想，當出現(xiàn)多個Candidate存在的情況下，通過投票規(guī)則的保證最終還是可以選擇出一個Leader固逗，這是這個Leader就會發(fā)送心跳反應給之前與其競爭的Candidate烫罩，那么這些Candidate就會接受結(jié)果洽故，變成Follower狀態(tài)时甚。 - (c) 一段時間內(nèi)沒有任何獲勝者
在一次選舉周期內(nèi)沒有選出Leader哈踱，那么就會進入下一次選舉开镣。也就是說Candidate狀態(tài)不變進入下一個選舉周期咽扇。如果存在多個Candidate质欲，那么進入下一個選舉周期嘶伟，通過隨機的選舉超時時間設置最終還是會選出一個Leader。
2. 選舉限制
Candidate發(fā)送請求投票RPC到其他節(jié)點申請投票盛霎，當存在多個Candidate的時候耽装，對于某一個節(jié)點來說如何處理投票RPC請求呢掉奄？
Raft協(xié)議的規(guī)定是這樣的：對于同一個任期姓建，每個服務器節(jié)點只會投給一個candidate ，按照先來先服務（first-come-first-served）的原則墅拭。
也就是說雖然存在多個Candidate發(fā)送請求投票RPC谍婉，但是接收的節(jié)點按照先來先服務的原則最終也只投給一個Candidate镀钓。
但是僅僅按照這個規(guī)則丁溅，會不會有問題呢？考慮這種情況：一個 follower可能會進入不可用狀態(tài)妓柜，在此期間领虹，leader可能提交了若干的日志條目求豫，然后這個follower可能會被選舉為leader 并且用新的日志條目覆蓋這些日志條目蝠嘉；結(jié)果蚤告，不同的狀態(tài)機可能會執(zhí)行不同的指令序列。
在這例子中已經(jīng)缺失大部分日志條目的follower可能按照先來先服務的原則被選為了leader获诈，而leader強制其他follower復制它的日志來到達一致性舔涎，這樣就導致了日志條目缺失的問題逗爹。也就是說掘而，leader選舉在先來先服務原則的基礎上要增加限制才能保證選舉的安全性。
Raft協(xié)議當然對選舉的安全性做了保證知染，這里再來看一下RequestVote RPC中的下面的兩個參數(shù)：
lastLogIndex：候選人最新日志條目的索引值（槽位）
lastLogTerm：候選人最新日志條目對應的任期號
這兩個參數(shù)對選舉做了限制持舆，通過這兩個參數(shù)與參與選舉的節(jié)點中相對應的屬性進行比較來確定誰的日志更新逸寓，如果投票者自己的日志比 candidate 的還新覆山，它會拒絕掉該投票請求。
RequestVote RPC執(zhí)行了這樣的限制： RPC中包含了candidate的日志信息吧享，如果投票者自己的日志比candidate的還新譬嚣，它會拒絕掉該投票請求拜银。
Raft通過比較兩份日志中最后一條日志條目的索引值和任期號來定義誰的日志比較新尼桶。如果兩份日志最后條目的任期號不同，那么任期號大的日志更新趾盐。如果兩份日志最后條目的任期號相同救鲤，那么日志較長的那個更新秩冈。
四漩仙、日志復制
日志復制的大致流程：Leader一旦被選舉出來队他，就開始為客戶端請求提供服務∥客戶端的每一個請求都包含一條將被復制狀態(tài)機執(zhí)行的指令窜锯。Leader把該指令作為一個新的條目追加到日志中去芭析，然后并行的發(fā)起 AppendEntries RPC給其他的服務器馁启，讓它們復制該條目。當該條目被安全地復制（下面會介紹）妖啥，leader會應用該條目到它的狀態(tài)機中（狀態(tài)機執(zhí)行該指令）然后把執(zhí)行的結(jié)果返回給客戶端对碌。如果follower崩潰或者運行緩慢朽们，或者網(wǎng)絡丟包华坦，leader會不斷地重試AppendEntries RPC（即使已經(jīng)回復了客戶端）直到所有的 follower 最終都存儲了所有的日志條目不从。
1. 日志條目
Raft協(xié)議中每個日志條目包含三部分：
- 指令：應用到狀態(tài)機的指令
- 任期號：leader收到該指令時的任期號
- 索引值：表明它在日志中的位置
日志是由順序編號的日志條目組成椿息，可以將日志看成是一個存儲日志條目的數(shù)組寝优。
2. 已提交的日志條目
leader創(chuàng)建的日志條目最終是會被應用到狀態(tài)機中的乏矾，那么何時應用？Raft規(guī)定只有已提交的日志條目凄硼，才能安全地被應用到狀態(tài)機中摊沉。而日志條目成為已提交的日志條目的前提是它被創(chuàng)建它的leader復制到了過半的服務器中说墨。
已提交日志條目還有以下的特點：
- 所有已提交的日志條目都是持久化的并且最終會被所有可用的狀態(tài)機執(zhí)行苍柏；
- leader日志中該已提交的日志條目之前的所有日志條目也都會被提交试吁，包括由其他 leader 創(chuàng)建的條目。
3. 與日志復制相關的屬性和參數(shù)
在"Raft算法中的狀態(tài)爬橡、規(guī)則和關鍵特性"章節(jié)和講述RPC章節(jié)我們可以看到很多關于日志相關的屬性和參數(shù)糙申，比如說commitIndex船惨、nextIndex[]等等粱锐。這些屬性和參數(shù)跟日志的復制息息相關怜浅，這個小節(jié)再重點梳理一下這些屬性和參數(shù)恶座。
log[]
所有節(jié)點都具有的數(shù)據(jù)結(jié)構(gòu)，用于存儲日志條目自点。leader從客戶端獲取到指令桂敛，創(chuàng)建相對應的日志條目术唬，真實的leader實現(xiàn)中就需要有一個數(shù)據(jù)結(jié)構(gòu)來存儲這些日志條目碴开，log[]數(shù)組就是這樣的數(shù)據(jù)結(jié)構(gòu)博秫。同樣挡育，leader將日志條目復制給其他的follower節(jié)點即寒，follower節(jié)點同樣用log[]這樣的數(shù)據(jù)結(jié)構(gòu)來存儲從leader節(jié)點復制過來的日志條目。
commitIndex
上面在講到已提交日志條目的時候說到過具滴，只有已提交的日志條目才能被安全地應用到狀態(tài)機中师倔，那么這個commitIndex不論是在leader還是在followers中都是用來記錄已提交的日志條目的最大索引趋艘。
lastApplied
節(jié)點將已提交的日志條目應用到狀態(tài)機中瓷胧，假如此時已記錄了commitIndex搓萧，但是此時節(jié)點崩潰了矛绘，那么已提交的日志條目就并沒有真正的應用到狀態(tài)機中刃永，那么怎么知道真實應用到狀態(tài)機的日志是哪些呢斯够？那么就需要lastApplied這個屬性的協(xié)助读规，這個屬性記錄了最后一條應用到狀態(tài)機中的日志條目的索引值，此索引值和索引值之前的所有日志條目都是已經(jīng)應用到狀態(tài)機中的束亏。那么像日志已提交铃在，但是還未真正應用的情景，lastApplied就會與commitIndex不同碍遍，commitIndex就會比lastApplied大定铜，也就是說lastApplied+1 到 commintIndex這個編號區(qū)間的日志條目都沒有應用到狀態(tài)機，所以當commitIndex > lastApplied時怕敬，就將lastApplied做加1處理揣炕，然后將新的lastApplied對應的日志條目應用到狀態(tài)機东跪，重復處理直到lastApplied與commitIndex相等畸陡。
nextIndex[] 和 matchIndex[]
所有的客戶端指令都由leader直接或間接處理鹰溜。leader負責將客戶端接收的指令包裝成日志條目，除了存儲到本地日志中丁恭，還需要將這些日志條目復制給其他的節(jié)點曹动。那么leader節(jié)點就需要知道follower節(jié)點日志復制情況，比如說要了解每個follower節(jié)點的日志復制到哪個位置了牲览，了解這個那么就可以決定下次發(fā)送Append Entreis消息中包含哪些日志記錄仁期。
leader節(jié)點維護了nextIndex[]和matchIndex[]兩個數(shù)組來記錄follower節(jié)點日志條目復制的相關信息，這兩個數(shù)組中記錄的都是索引值竭恬。nextIndex[]根據(jù)我們上面的描述已經(jīng)知道記錄的是需要發(fā)送給每個Follower節(jié)點的下一條日志的索引值跛蛋。那么matchIndex[]是其什么作用呢？
思考一下痊硕，leader發(fā)送日志復制請求給follower節(jié)點赊级，能一定保證復制成功嗎？或者說是怎么樣判斷復制是否成功了岔绸？不能保證復制一樣成功理逊，比如說follower節(jié)點崩潰或者運行緩慢，或者網(wǎng)絡丟包盒揉，這樣follower節(jié)點是沒有成功響應復制請求的晋被，當然了leader節(jié)點會不斷地發(fā)送重試 AppendEntries RPC（即使已經(jīng)回復了客戶端）直到所有的follower最終都存儲了所有的日志條目。除了這個刚盈，leader節(jié)點當然需要知曉到底哪些日志是成功被復制了羡洛，matchIndex[]正是用于記錄這個信息。matchIndex[]記錄了已經(jīng)復制給每個follower節(jié)點的最大的日志索引值藕漱。
這里簡單看一下leader節(jié)點和某一個follower節(jié)點復制日志時欲侮，對應nextIndex和matchIndex值的變化：follower節(jié)點中最后一個日志的索引值大于等于該follower節(jié)點對應的nextIndex值，那么Append Entries消息發(fā)送從nextIndex開始的所有日志肋联。之后威蕉，leader節(jié)點會檢測該follower節(jié)點返回的相應響應，如果成功則更新相應該follower節(jié)點對應的nextIndex值和matchIndex值橄仍；如果因為日志不一致而失敗韧涨，則減少nextIndex值重試。
要使得 follower的日志跟自己一致侮繁，leader 必須找到兩者達成一致的最大的日志條目（索引最大）虑粥，刪除 follower日志中從那個點之后的所有日志條目，并且將自己從那個點之后的所有日志條目發(fā)送給follower 鼎天。所有的這些操作都發(fā)生在對AppendEntries RPCs 中一致性檢查的回復中舀奶。Leader針對每一個follower都維護了一個nextIndex ，表示leader要發(fā)送給 follower 的下一個日志條目的索引斋射。當選出一個新leader時育勺，該leader將所有nextIndex的值都初始化為自己最后一個日志條目的index加1但荤。如果follower的日志和leader的不一致，那么下一次AppendEntries RPC 中的一致性檢查就會失敗涧至。在被follower拒絕之后腹躁，leader就會減小 nextIndex值并重試AppendEntries RPC 。最終nextIndex會在某個位置使得leader和follower 的日志達成一致南蓬。此時纺非，AppendEntries RPC 就會成功，將follower中跟leader沖突的日志條目全部刪除然后追加leader中的日志條目（如果有需要追加的日志條目的話）赘方。一旦AppendEntries RPC成功烧颖，follower的日志就和leader一致，并且在該任期接下來的時間里保持一致窄陡。
AppendEntries RPC - prevLogIndex炕淮、prevLogTerm、entries[]和leaderCommit
- entries[]
這個參數(shù)存儲的是將要追加到Follower上的日志條目跳夭。
- prevLogIndex和prevLogTerm
prevLogIndex表示的是leader所認為的follower與leader保持一致的最后一個日志index涂圆。prevLogTerm是與prevLogIndex對應的term。
而leader對這兩個參數(shù)取值是：
prevLogIndex：領導人最新日志前一個位置日志的索引值
prevLogTerm：領導人最新日志前一個位置日志的任期號
根據(jù)上面的描述我們就可以知道币叹，leader傳遞這個兩個參數(shù)用來給follower端檢查日志是否一致润歉。
關于這兩個參數(shù)，AppendEntries RPC的接收方實現(xiàn)中有這樣的描述：
Reply false if log doesn't contain an entry at preLogIndex whose term matches prefLogTerm
也就是接收方有這樣的一個邏輯：
if (log[preLogIndex].term == preLogTerm)
return true;
else
return false;
- leaderCommit
主節(jié)點的CommitIndex颈抚。
對于這個參數(shù)的作用踩衩，AppendEntries RPC的接收方實現(xiàn)中有這樣的描述：
If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)
4. 日志復制流程
1）客戶端向Leader發(fā)送寫請求。
2）Leader將寫請求解析成操作指令追加到本地日志文件中邪意。
3）Leader為每個Follower廣播AppendEntries RPC九妈。
4）Follower通過一致性檢查反砌，選擇從哪個位置開始追加Leader的日志條目雾鬼。
5）一旦日志項提交成功，Leader就將該日志條目對應的指令應用（apply）到本地狀態(tài)機宴树，并向客戶端返回操作結(jié)果策菜。
6）Leader后續(xù)通過AppendEntries RPC將已經(jīng)成功（在大多數(shù)節(jié)點上）提交的日志項告知Follower。
7）Follower收到提交的日志項之后酒贬，將其應用到本地狀態(tài)機又憨。
五、Raft協(xié)議Java版實現(xiàn)
https://github.com/sofastack/sofa-jraft
https://github.com/hazelcast/hazelcast/tree/master/hazelcast/src/main/java/com/hazelcast/cp/internal/raft
