raft 系列解讀(2) 之 測(cè)試用例

基于mit的6.824課程缀拭，github代碼地址：https://github.com/zhuanxuhit/distributed-system

case1：TestInitialElection

測(cè)試中3個(gè)server蜈敢，然后啟動(dòng)擂红，驗(yàn)證在同一個(gè)任期（term）內(nèi)是否只有一個(gè)leader，并且在2 * RaftElectionTimeout后，由于心跳的存在，不會(huì)發(fā)生重選。

在代碼實(shí)現(xiàn)中昧狮，主要有以下幾點(diǎn)：

• 實(shí)現(xiàn)AppendEnties和RequestVote兩個(gè)rpc部分功能
• 實(shí)現(xiàn)Make新建Raft

我們來(lái)看下其中主要的關(guān)鍵點(diǎn)：

程序整體組織上是在Make中啟動(dòng)了一個(gè)goroutine，是一個(gè)無(wú)限循環(huán)边苹，根據(jù)不同的狀態(tài)進(jìn)行不同的處理陵且，結(jié)構(gòu)如下：

圖片

follower

先講第一個(gè)狀態(tài)follower的處理
所有的server重啟后第一個(gè)狀態(tài)都是follower，如果在election timeout時(shí)間內(nèi)个束，既沒(méi)有收到leader的heartbeat慕购，也沒(méi)有收到RequestVote請(qǐng)求，那么開(kāi)啟選舉過(guò)程茬底，此時(shí)狀態(tài)將轉(zhuǎn)換為candidate沪悲，代碼如下：

        rf.resetElectionTimeout()
        // 等待心跳，如果心跳未到阱表，但是選舉超時(shí)了殿如，則開(kāi)始新一輪選舉
        select {
        case <-rf.heartbeatChan:
        case <-time.After(rf.randomizedElectionTimeout):
        // 開(kāi)始重新選舉
            log.Println("election timeout:", rf.randomizedElectionTimeout)
            if rf.status != STATUS_FOLLOWER {
                // panic
                log.Fatal("status not right when in follower and after randomizedElectionTimeout:", rf.randomizedElectionTimeout)
            }
            rf.convertToCandidate()
        }

candidate

接著開(kāi)始第二個(gè)狀態(tài)candidate的處理：

• 第一步，新增本地任期和投票
• 第二步最爬，重置 election timer 并開(kāi)始廣播
• 第三步等待結(jié)果
  • 1)他自己贏得了選舉;
  • 2)收到AppendEntries得知另外一個(gè)服務(wù)器確立他為L(zhǎng)eader涉馁，轉(zhuǎn)變?yōu)閒ollower
  • 3. 一個(gè)周期時(shí)間過(guò)去但是沒(méi)有任何人贏得選舉，開(kāi)始新的選舉

結(jié)構(gòu)大致如下：

圖片

leader

如果此時(shí)贏得了選舉爱致，則進(jìn)入第3個(gè)狀態(tài)leader的處理：目前l(fā)eader只實(shí)現(xiàn)了一個(gè)功能烤送，周期性的發(fā)送心跳，功能非常簡(jiǎn)單糠悯，此處不再貼代碼了帮坚。

rpc

剩下就是兩個(gè)rpc的發(fā)送和接收處理了，其中需要特別注意的點(diǎn)如下：

• 所有rpc處理中：如果收到的請(qǐng)求或者響應(yīng)中互艾，包含的term大于當(dāng)前的currentTerm试和，設(shè)置currentTerm=term，然后變?yōu)閒ollower
• 所有rpc處理中：判斷任期是否小于currentTerm纫普，小于的都丟棄

在完成第一個(gè)測(cè)試的過(guò)程中：AppendEnties只需要處理心跳請(qǐng)求即可阅悍。

最后給出代碼的地址：https://github.com/zhuanxuhit/distributed-system，tag是：lab3-raft-case1

case2：TestReElection

有3個(gè)server，選舉出來(lái)一個(gè)leader后溉箕，模擬leader故障晦墙，重新選舉出一個(gè)leader，然后再模擬older leader故障恢復(fù)重新加入肴茄，此時(shí)也只會(huì)有一個(gè)leader，再模擬3個(gè)2個(gè)都故障了但指，那理論上就不會(huì)有l(wèi)eader出現(xiàn)了寡痰，此時(shí)再逐個(gè)加入故障的server，都只會(huì)有一個(gè)leader

直接運(yùn)行測(cè)試

go test -v -run ReElection

1. leader故障棋凳，新的leader選出來(lái)
2. 老的leader加入拦坠，不影響只有一個(gè)leader
3. 兩個(gè)server故障，不會(huì)有新的leader
4. 恢復(fù)一個(gè)server剩岳，出現(xiàn)leader
5. 再次恢復(fù)一個(gè)server贞滨，出現(xiàn)leader

先看第1個(gè)，出現(xiàn)的調(diào)試信息:

2016/10/10 18:44:46 follower: 0 election timeout: 1.287113937s
2016/10/10 18:44:46 now I begin to candidate,index: 0
2016/10/10 18:44:47 follower: 2 election timeout: 1.54916732s
2016/10/10 18:44:47 now I begin to candidate,index: 2

可以看到0開(kāi)始選舉后拍棕，不知道為什么2沒(méi)有投票晓铆，去看代碼，發(fā)現(xiàn)問(wèn)題是：

• 當(dāng)發(fā)現(xiàn)遠(yuǎn)端term大于本地term后绰播，直接轉(zhuǎn)換為follower骄噪，并更新當(dāng)前的currentTerm和voteFor

修改后即可通過(guò)測(cè)試，接著馬上又出現(xiàn)另一個(gè)問(wèn)題：

2016/10/10 18:54:50 candidate: 0 'slog is not at least as up-to-date as receiver’s log

但是我們現(xiàn)在做的是沒(méi)有日志的蠢箩，查看代碼發(fā)現(xiàn)問(wèn)題是：

• (args.LastLogIndex < rf.commitIndex || args.LastLogTerm < currentTerm)链蕊，因?yàn)閏urrentTerm增加了，但是LastLogTerm是0谬泌，所以要考慮rf.commitIndex == 0表示還沒(méi)有日志滔韵，則沒(méi)必要檢查

修改完后，再次運(yùn)行case掌实，這次是兩個(gè)server故障陪蜻，不會(huì)有新的leader出問(wèn)題了，選舉不出來(lái)潮峦，接著查原因：

在處理投票的時(shí)候囱皿，往heartbeatChan寫(xiě)的時(shí)候阻塞了，rf.heartbeatChan = make(chan bool, 1)是有一個(gè)緩沖的channel忱嘹，那為什么會(huì)阻塞呢嘱腥，我們看下有幾個(gè)地方會(huì)寫(xiě)，幾個(gè)地方會(huì)去讀

有兩個(gè)地方會(huì)去寫(xiě)：

1. AppendEnties中收到心跳會(huì)去寫(xiě)拘悦，當(dāng)去寫(xiě)的時(shí)候齿兔，說(shuō)明是已經(jīng)有l(wèi)eader了，自己會(huì)轉(zhuǎn)變?yōu)閒ollower
2. RequestVote中收到投票也會(huì)去寫(xiě)

讀的地方也有兩個(gè)

1. 在狀態(tài)follower中，去讀heartbeatChan分苇，如果選舉超時(shí)內(nèi)沒(méi)收到心跳添诉，則開(kāi)始candidate
2. 在candidate狀態(tài)，去讀去讀heartbeatChan医寿，表示已經(jīng)有新的leader產(chǎn)生了

于是就發(fā)現(xiàn)了問(wèn)題：

• 在實(shí)現(xiàn)leader任務(wù)的時(shí)候栏赴，沒(méi)有一個(gè)點(diǎn)去觸發(fā)退出心跳
• 選舉失敗，應(yīng)該等待超時(shí)靖秩，然后重新開(kāi)始新一輪選舉须眷，而不是馬上開(kāi)始新一輪選舉，這樣子造成彼此都不成功

修改代碼后沟突，通過(guò)case2

case3：TestBasicAgree

這個(gè)case開(kāi)始要做提交了花颗，實(shí)現(xiàn)Start()函數(shù)了，這個(gè)case主要測(cè)試是：有5個(gè)server惠拭，沒(méi)提交前檢查沒(méi)有提交的log扩劝，然后提交后，測(cè)試該log是否已經(jīng)被每個(gè)server都存儲(chǔ)了职辅。

在實(shí)現(xiàn)start中棒呛，其做的步驟是：

// 客戶端的一次日志請(qǐng)求操作觸發(fā)
// 1)Leader將該請(qǐng)求記錄到自己的日志之中;
// 2)Leader將請(qǐng)求的日志以并發(fā)的形式,發(fā)送AppendEntries RCPs給所有的服務(wù)器;
// 3)Leader等待獲取多數(shù)服務(wù)器的成功回應(yīng)之后(如果總共5臺(tái),那么只要收到另外兩臺(tái)回應(yīng)),
// 將該請(qǐng)求的命令應(yīng)用到狀態(tài)機(jī)(也就是提交),更新自己的commitIndex 和 lastApplied值;
// 4)Leader在與Follower的下一個(gè)AppendEntries RPCs通訊中,
// 就會(huì)使用更新后的commitIndex,Follower使用該值更新自己的commitIndex;
// 5)Follower發(fā)現(xiàn)自己的 commitIndex > lastApplied
// 則將日志commitIndex的條目應(yīng)用到自己的狀態(tài)機(jī)(這里就是Follower提交條目的時(shí)機(jī))

實(shí)現(xiàn)的關(guān)鍵點(diǎn)：在Start函數(shù)中，一旦判斷出當(dāng)前server是leader罐农，馬上開(kāi)啟一個(gè)goroutine条霜，開(kāi)始異步進(jìn)行agree工作，然后立即返回涵亏，代碼如下：

圖片

此處第4步和第5步需要在另外的地方完成宰睡，一個(gè)是heartbeat中，另一個(gè)是follower在處理AppendEntries過(guò)程中

還有就是在成為leader的時(shí)候气筋，需要初始化nextIndex,matchIndex

圖片

圖片

還有最重要的一點(diǎn)：為了通過(guò)測(cè)試抹沪，記住要在日志提交后，發(fā)送消息ApplyMsg給applymsg瓤球，這樣才能通過(guò)測(cè)試

好了到此為止融欧，寫(xiě)的代碼剛好通過(guò)第三個(gè)測(cè)試，繼續(xù)下一關(guān)的卦羡！

case4：TestFailAgree

測(cè)試的內(nèi)容是：有3個(gè)server噪馏，其中一個(gè)follower故障麦到，發(fā)的命令只有2個(gè)能收到，當(dāng)恢復(fù)故障后欠肾，發(fā)的命令都能收到

出現(xiàn)的問(wèn)題：由于每個(gè)command真正提交都是通過(guò)goroutine來(lái)執(zhí)行的瓶颠，因此每個(gè)goroutine之間并發(fā)執(zhí)行，怎么保證前一個(gè)agree了刺桃，下一個(gè)才能agree成功呢粹淋？
現(xiàn)在出現(xiàn)的問(wèn)題是：
map[3:103 5:104 1:101 2:102]，亂序瑟慈，即4還沒(méi)有提交了廓啊，5就提交成功了

現(xiàn)在的問(wèn)題是：誰(shuí)也不服誰(shuí)，當(dāng)follower恢復(fù)后封豪，大家都競(jìng)選，但是沒(méi)有一個(gè)成功炒瘟，查明原因后發(fā)現(xiàn)是因?yàn)闆](méi)有處理一個(gè)概念：
>如果候選人的日志至少和大多數(shù)的服務(wù)器節(jié)點(diǎn)一樣新

這個(gè)一樣新通過(guò)：比較兩份日志中最后一條日志條目的索引值和任期號(hào)定義誰(shuí)的日志比較新吹埠。如果兩份日志最后的條目的任期號(hào)不同，那么任期號(hào)大的日志更加新疮装。如果兩份日志最后的條目任期號(hào)相同缘琅，那么日志比較長(zhǎng)的那個(gè)就更加新。

進(jìn)行到這廓推，發(fā)現(xiàn)已經(jīng)很難調(diào)試了刷袍，代碼太亂，邏輯混亂樊展，于是準(zhǔn)備開(kāi)始重構(gòu)

現(xiàn)有代碼的問(wèn)題：

• 臨界區(qū)的混亂呻纹，到底哪里加鎖，哪里不加
• 各個(gè)goroutine之間交互的混亂
• 代碼功能組織的問(wèn)題

重構(gòu)的代碼最重要的一點(diǎn)是：抽象出了狀態(tài)機(jī)专缠，在里面去更新

case5：FailNoAgree

測(cè)試內(nèi)容是：5個(gè)server雷酪，3個(gè)follow故障，此時(shí)提交的命令將不會(huì)Committed涝婉，然后恢復(fù)3個(gè)follower哥力，此時(shí)發(fā)送第3個(gè)命令，會(huì)忘記第2個(gè)沒(méi)有確認(rèn)的命令墩弯，此時(shí)第3個(gè)命令的index應(yīng)該還是2

現(xiàn)在出現(xiàn)的問(wèn)題是：
follow的日志沒(méi)更新吩跋，但是leader的nextIndex確更新了！

2016/10/13 10:44:20 leader is 4
2016/10/13 10:44:22 server:0,currentTerm:3,role:candidate
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:22 server:1,currentTerm:3,role:candidate
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:22 server:2,currentTerm:3,role:candidate
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:22 server:3,currentTerm:2,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1} {2 20 2}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:22 server:4,currentTerm:2,role:leader
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1} {2 20 2}]
nextIndex is:[2 2 2 3 3]
matchIndex is:[1 1 1 2 0]

2016/10/13 10:44:22 恢復(fù)3個(gè)server
2016/10/13 10:44:25 LeaderId: 4 has big term: 5 than follower: 3 currentTerm: 4
2016/10/13 10:44:25 server 3 len(rf.log) 3 args.PrevLogIndex 1
2016/10/13 10:44:26 重新選舉后leader is 4
2016/10/13 10:44:26 server:0,currentTerm:5,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:26 server:1,currentTerm:5,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:26 server:2,currentTerm:5,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {2 10 1}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:26 server:3,currentTerm:5,role:follower
commitIndex:2,lastApplied:2
log is:[{0 <nil> 0} {2 10 1} {2 20 2}]
nextIndex is:[0 0 0 0 0]
matchIndex is:[0 0 0 0 0]

2016/10/13 10:44:26 server:4,currentTerm:5,role:leader
commitIndex:2,lastApplied:2
log is:[{0 <nil> 0} {2 10 1} {2 20 2}]
nextIndex is:[3 3 3 3 3]
matchIndex is:[2 2 2 2 0]

看重新選舉后渔工，leader4：matchIndex is:[2 2 2 2 0]锌钮，但是其他的follower確沒(méi)有收到新的日志，怎么回事呢涨缚？看代碼什么情況下回去更新matchIndex呢轧粟？

問(wèn)題在于發(fā)送心跳的時(shí)候返回了reply=true了策治，確沒(méi)有去檢查日志是否是最新的

此處記住appendEntries如果返回true，則一定表示是日志一樣新了兰吟！

true if follower contained entry matching prevLogIndex and prevLogTerm

case6：ConcurrentStarts

這個(gè)case測(cè)試的是：
同時(shí)發(fā)送5個(gè)命令通惫，然后測(cè)試5個(gè)命令能夠被順序的提交
測(cè)試中的修改是：

圖片

將紅色框中的內(nèi)容移動(dòng)到了鎖里面，為了防止并發(fā)訪問(wèn)的時(shí)候混蔼，index得到相同履腋。

case7：Rejoin

測(cè)試重新加入直接通過(guò)了，之前的代碼就能實(shí)現(xiàn)
測(cè)試內(nèi)容是：3個(gè)server惭嚣，leader故障遵湖，然后向故障的leader發(fā)送命令，同時(shí)向新選舉出來(lái)的leader發(fā)送命令,大致如下圖晚吞，最后能統(tǒng)一

圖片

case8：Backup

類似case7：不同在于此處有5個(gè)server延旧，然后命令更多，測(cè)試也是網(wǎng)絡(luò)分區(qū)后出現(xiàn)多l(xiāng)eader槽地，然后恢復(fù)網(wǎng)絡(luò)后迁沫，再重新同步數(shù)據(jù)
不用修改，直接通過(guò)

case9：Count

case9主要是性能測(cè)試捌蚊，測(cè)試rpc的次數(shù)不能太多

case10-12：Persist1-3

持久化的邏輯一直沒(méi)有加上集畅，此處加上的

先看需要持久化哪些數(shù)據(jù)，然后持久化的時(shí)機(jī)是什么時(shí)候缅糟？

需要持久化哪些日志挺智？

    e.Encode(rf.currentTerm) // 當(dāng)前任期
    e.Encode(rf.log) // 收到的日志
    e.Encode(rf.votedFor) // 投票的
    e.Encode(rf.commitIndex) // 已經(jīng)確認(rèn)的一致性日志，之后的日志表示還沒(méi)有確認(rèn)是否可以同步窗宦，一旦確認(rèn)的日志都不會(huì)改變了

既然這幾個(gè)需要同步赦颇，那就是發(fā)生改變的時(shí)候把數(shù)據(jù)持久化下來(lái)就可以了

需要調(diào)用persist()函數(shù)的地方有：

• leader向各個(gè)follower發(fā)送完日志，確認(rèn)提交的時(shí)候
• follower處理AppendEnties有新日志或者commiIndex更新的時(shí)候

case13：Figure8

測(cè)試主要測(cè)試的是下面的這張圖：

圖片

描述的問(wèn)題是：為什么領(lǐng)導(dǎo)人無(wú)法通過(guò)老的日志的任期號(hào)來(lái)判斷其提交狀態(tài)迫摔。

• (a) S1 是領(lǐng)導(dǎo)者沐扳，部分的復(fù)制了索引位置 2 的日志條目
• (b) S1 崩潰了，然后 S5 在任期 3 里通過(guò) S3句占、S4 和自己的選票贏得選舉沪摄，然后從客戶端接收了一條不一樣的日志條目放在了索引2 處
• (c) S5 又崩潰了；S1 重新啟動(dòng)纱烘，選舉成功杨拐，開(kāi)始復(fù)制日志。在這時(shí)擂啥，來(lái)自任期 2 的那條日志已經(jīng)被復(fù)制到了集群中的大多數(shù)機(jī)器上哄陶，但是還沒(méi)有被提交
• (d) S1 又崩潰了，S5 可以重新被選舉成功（通過(guò)來(lái)自 S2哺壶，S3 和 S4 的選票）屋吨，然后覆蓋了他們?cè)谒饕?2 處的日志蜒谤。但是，在崩潰之前至扰，如果 S1 在自己的任期里復(fù)制了日志條目到大多數(shù)機(jī)器上
• (e) 然后這個(gè)條目就會(huì)被提交（S5 就不可能選舉成功）鳍徽。 在這個(gè)時(shí)候，之前的所有日志就會(huì)被正常提交處理

Raft采用計(jì)算副本數(shù)的方式,使得永遠(yuǎn)不會(huì)提交前前 面紀(jì)元的日志條目敢课，

現(xiàn)在出現(xiàn)的問(wèn)題是commit了不同的值阶祭？
即在沒(méi)有達(dá)成一致的情況下就就行了提交！

Test: Figure 8 ...
2016/10/13 20:38:35 server:0,currentTerm:2,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {1 1752890841475247006 1}]
nextIndex is:[1 1 1 1 1]
matchIndex is:[0 0 0 0 0]

2016/10/13 20:38:35 server:2,currentTerm:2,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {1 1752890841475247006 1}]
nextIndex is:[1 1 1 1 1]
matchIndex is:[0 0 0 0 0]

2016/10/13 20:38:35 server:4,currentTerm:2,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {1 1752890841475247006 1}]
nextIndex is:[1 1 1 1 1]
matchIndex is:[0 0 0 0 0]

2016/10/13 20:38:35 apply error: commit index=2 server=1 4541014630978635374 != server=3 8558661384468427932

到這就得加上之前忘記的一個(gè)策略

如果存在以個(gè)N滿足 N>commitIndex,多數(shù)的matchIndex[i] >= N,并且 log[N].term == currentTerm:設(shè)置commitIndex = N

主要是指：leader只會(huì)提交本紀(jì)元的日志

case14：UnreliableAgree

模擬網(wǎng)絡(luò)不可靠直秆，在不可靠的情況下cfg.setunreliable(false)濒募，則有概率還是丟棄請(qǐng)求，在這種情況下測(cè)試協(xié)議最后還能達(dá)成一致

case15：Figure8Unreliable

通過(guò)設(shè)置cfg.setlongreordering(true)圾结，在labrpc中會(huì)直接睡眠一段時(shí)間瑰剃，模擬這次情況下協(xié)議還是達(dá)成一致

ms := 200 + rand.Intn(1 + rand.Intn(2000))
time.Sleep(time.Duration(ms) * time.Millisecond)

2016/10/14 14:51:11 server:4,currentTerm:31,role:follower
commitIndex:3,lastApplied:3
2016/10/14 14:51:11 server:3,currentTerm:31,role:follower
commitIndex:3,lastApplied:3
2016/10/14 14:51:11 server:2,currentTerm:31,role:follower
commitIndex:3,lastApplied:3
2016/10/14 14:51:11 server:1,currentTerm:31,role:follower
commitIndex:3,lastApplied:3
2016/10/14 14:51:11 server:0,currentTerm:31,role:leader
commitIndex:3,lastApplied:3
nextIndex is:[186 53 58 51 62]
matchIndex is:[185 0 0 0 0]

2016/10/14 16:09:45 check log type: raft.AppendEntiesArgs value: {6 1 1 1 1 [{1 4411 2} {2 9540 3} {4 3863 4} {6 2769 5}]}
2016/10/14 16:09:45 error log indexserver:0,currentTerm:6,role:follower
commitIndex:1,lastApplied:1
log is:[{0 <nil> 0} {1 606 1} {1 4411 2} {4 3863 4} {6 2769 5}]
nextIndex is:[84 0 0 3 2]
matchIndex is:[83 1 1 2 1]

錯(cuò)誤日志，由于沒(méi)有很好的傳遞日志筝野，代碼bug

case16-17：TestReliableChurn培他，UnreliableChurn

測(cè)試通過(guò)

下一篇的計(jì)劃是結(jié)合代碼再次看下關(guān)鍵實(shí)現(xiàn)