Raft 筆記
5.3 Log replication
要保證：
-
如果不同日志中兩個(gè)entry有同樣的index和term, 那么儲(chǔ)存的是同一個(gè)指令
Leader 一次只創(chuàng)建一entry
-
如果兩個(gè)不同日志中兩個(gè)entry有同樣的index和term， 那么兩個(gè)entries之前的記錄都是一樣的
通過(guò)Leader發(fā)送AppendEntries給各個(gè)follower來(lái)檢查是否和Leader的log一致，如果不一致，F(xiàn)ollower就拒絕(拒絕后操作：Leader處理不一致)
理想情況，Leader和Follower的狀態(tài)是一樣的，但是可能遇到上一個(gè)Leader沒有復(fù)制所有的entries到日志中,或者Leader崩潰,沒來(lái)得及commit log
Leader處理不一致:
當(dāng)Follower和Leader的日志不一致時(shí)，Leader強(qiáng)制抹除Follower的日志內(nèi)容并將自己的日志內(nèi)容復(fù)制給Follower（Leader's log == Fowllower's log).
缺失entries，例如（a) (b）
多余的uncommitted entries，例如(c) (d)
兩者都有,例如(e) (f)
Leader發(fā)送AppendEntries 給 Follower 來(lái)找到最新的已經(jīng)committed了的entry，然后少了entries的添上，多了的entries刪除.
對(duì)于每個(gè)Follower，Leader會(huì)維護(hù)一個(gè) nextIndex ：index of next log entry the leader will send to that follower
當(dāng)Leader第一次啟動(dòng)(包括更換leader），所有的nextIndex設(shè)置為L(zhǎng)eader log 的下一個(gè)index. 上面圖中是 11
如果Follower's log和leader不一致，那么下一個(gè)AppendEntry就會(huì)失敗。Follower返回rejection，nextIndex--
上圖b和leader的情況：
1.nextIndex是11，sendAppendEntries到b， 發(fā)現(xiàn)index 11沒有指令，nextIndex減一并返回false，一直減到5然后發(fā)現(xiàn)index=4 term = 4匹配Leader的index=4，term=4， 返回true， matchIndex is 4，nextIndex是5。
2.Leader此時(shí)知道4是對(duì)的，將5的指令發(fā)送給b， b index = 5 填上4.
5.4 Safety
前面的一些機(jī)制并不能完全保證每個(gè)狀態(tài)機(jī)執(zhí)行的是相同的指令。比如，當(dāng)Leader提交的時(shí)候，其中一個(gè)follower可能不能用了，就會(huì)commit失敗，然后它被選成了新的Leader，這時(shí)候之前應(yīng)該提交的entries可能被新的entries取代。結(jié)果就是，不同的狀態(tài)機(jī)執(zhí)行了不同的command sequence.
5.4.1 Election restriction
Raft在選取新的Leader的時(shí)候會(huì)檢查candidate是不是擁有所有的committed entries，如果沒有就阻止它成為L(zhǎng)eader: 通過(guò)RequestVote RPC實(shí)現(xiàn)： RPC擁有candidate的log信息。
當(dāng)Follower投票時(shí)， 它會(huì)拒絕投票如果它的log比candidate的更新（擁有的committed entries更多）
5.4.2 Committing entries from previous terms
不能簡(jiǎn)單的通過(guò)count大多數(shù)entries的方式提交之前term的entry。例如：在（c）中，index2 中的2是大多數(shù)，但是（c）不能因?yàn)檫@個(gè)就commit 2. 可能出現(xiàn)（d）和 （e）兩種情況
（d）中，S5成為L(zhǎng)eader后，由于自己的值3擁有比2更大的term，導(dǎo)致用值3將已經(jīng)commit的2覆蓋,所以之前2是不能commit的
下圖描述了當(dāng)一個(gè)old entry儲(chǔ)存在大部分servers上 依然存在被未來(lái)新的Leader重寫的可能。
解決上述問(wèn)題：
因此Raft限制只能通過(guò)判斷大多數(shù)的方式提交當(dāng)前term的entry，進(jìn)而對(duì)之前的entry間接提交，如過(guò)程e所示
