上來先看了2b的要求文檔。主要就是要handle log了。
里面強烈推薦了3篇文章，我認(rèn)真做了閱讀。發(fā)現(xiàn)了我之前實現(xiàn)的一些問題。
其中一個是來自中文的翻譯
比如：如果在超過選取領(lǐng)導(dǎo)人時間之前沒有收到來自當(dāng)前領(lǐng)導(dǎo)人的AppendEntries RPC或者沒有收到候選人的投票請求，則自己轉(zhuǎn)換狀態(tài)為候選人
原文：If election timeout elapses without receiving AppendEntries RPC from current leader or granting vote to candidate: convert to candidate.
區(qū)別就是一個是授予了投票再喚醒，另一個是只要收到rpc就喚醒。
文章鏈接來自hint：
- Give yourself time to rewrite your implementation in light of lessons learned about structuring concurrent code. In later labs you'll thank yourself for having Raft code that's as clear and clean as possible. For ideas, you can re-visit our structure,locking and guide, pages.
實現(xiàn)的時候，發(fā)現(xiàn)除了是授予了投票，要喚醒。還有當(dāng)選了LEADER也要喚醒。
重跑了下測試，沒啥問題
第一步 閱讀論文5.3- 6之前
https://www.infoq.cn/article/raft-paper
第二步 FROM HINT
You will need to implement the election restriction (section 5.4.1 in the paper).
Raft 使用投票的方式來阻止沒有包含全部日志條目的服務(wù)器贏得選舉。一個候選人為了贏得選舉必須要和集群中的大多數(shù)進行通信，這就意味著每一條已經(jīng)提交的日志條目最少在其中一臺服務(wù)器上出現(xiàn)。如果候選人的日志至少和大多數(shù)服務(wù)器上的日志一樣新（up-to-date，這個概念會在下邊有詳細(xì)介紹），那么它一定包含有全部的已經(jīng)提交的日志條目。RequestVote RPC 實現(xiàn)了這個限制：這個 RPC（遠(yuǎn)程過程調(diào)用）包括候選人的日志信息，如果它自己的日志比候選人的日志要新，那么它會拒絕候選人的投票請求。
Raft 通過比較日志中最后一個條目的索引和任期號來決定兩個日志哪一個更新。如果兩個日志的任期號不同，任期號大的更新；如果任期號相同，更長的日志更新。
這一步 應(yīng)該上一章已經(jīng)實現(xiàn)了。
剩下一些HINT，在上一章基本都COVER住了，不用太多改動
比如
One way to fail the early Lab 2B tests is to hold un-needed elections, that is, an election even though the current leader is alive and can talk to all peers. This can prevent agreement in situations where the tester believes agreement is possible. Bugs in election timer management, or not sending out heartbeats immediately after winning an election, can cause un-needed elections.
第三步 實現(xiàn)START
根據(jù)方法描述，實現(xiàn)如下
第四步 實現(xiàn)startAppendLog
搜索到//now only for heartbeat
然后開始把這個方法從只是發(fā)送HEART BEAT 到真的開始發(fā)日志。
論文重點
當(dāng)這個條目被安全的復(fù)制之后（下面的部分會詳細(xì)闡述），領(lǐng)導(dǎo)人會將這個條目應(yīng)用到它的狀態(tài)機中并且會向客戶端返回執(zhí)行結(jié)果。如果追隨者崩潰了或者運行緩慢或者是網(wǎng)絡(luò)丟包了，領(lǐng)導(dǎo)人會無限的重試 AppendEntries RPC（甚至在它向客戶端響應(yīng)之后）直到所有的追隨者最終存儲了所有的日志條目。
領(lǐng)導(dǎo)人跟蹤記錄它所知道的被提交條目的最大索引值，并且這個索引值會包含在之后的 AppendEntries RPC 中（包括心跳 heartbeat 中），為的是讓其他服務(wù)器都知道這條條目已經(jīng)提交。一旦一個追隨者知道了一個日志條目已經(jīng)被提交，它會將該條目應(yīng)用至本地的狀態(tài)機（按照日志順序）
- 如果在不同日志中的兩個條目有著相同的索引和任期號，則它們所存儲的命令是相同的。
- 如果在不同日志中的兩個條目有著相同的索引和任期號，則它們之間的所有條目都是完全一樣的。
第一條特性源于領(lǐng)導(dǎo)人在一個任期里在給定的一個日志索引位置最多創(chuàng)建一條日志條目，同時該條目在日志中的位置也從來不會改變。第二條特性源于 AppendEntries 的一個簡單的一致性檢查。當(dāng)發(fā)送一個 AppendEntries RPC 時，領(lǐng)導(dǎo)人會把新日志條目緊接著之前的條目的索引位置和任期號都包含在里面。如果追隨者沒有在它的日志中找到相同索引和任期號的日志，它就會拒絕新的日志條目。這個一致性檢查就像一個歸納步驟：一開始空的日志的狀態(tài)一定是滿足日志匹配原則的，一致性檢查保證了當(dāng)日志添加時的日志匹配原則。因此，只要 AppendEntries 返回成功的時候，領(lǐng)導(dǎo)人就知道追隨者們的日志和它的是一致的了。
下面是最關(guān)鍵的一段話
為了使得追隨者的日志同自己的一致，領(lǐng)導(dǎo)人需要找到追隨者同它的日志一致的地方，然后刪除追隨者在該位置之后的條目，然后將自己在該位置之后的條目發(fā)送給追隨者。這些操作都在 AppendEntries RPC 進行一致性檢查時完成。領(lǐng)導(dǎo)人給每一個追隨者維護了一個nextIndex，它表示領(lǐng)導(dǎo)人將要發(fā)送給該追隨者的下一條日志條目的索引。當(dāng)一個領(lǐng)導(dǎo)人開始掌權(quán)時，它會將nextIndex初始化為它的最新的日志條目索引數(shù) +1（圖 -7 中的 11）。如果一個追隨者的日志和領(lǐng)導(dǎo)者的不一致，AppendEntries 一致性檢查會在下一次 AppendEntries RPC 時返回失敗。在失敗之后，領(lǐng)導(dǎo)人會將nextIndex遞減然后重試 AppendEntries RPC。最終nextIndex會達(dá)到一個領(lǐng)導(dǎo)人和追隨者日志一致的地方。這時，AppendEntries 會返回成功，追隨者中沖突的日志條目都被移除了，并且添加所缺少的上了領(lǐng)導(dǎo)人的日志條目。一旦 AppendEntries 返回成功，追隨者和領(lǐng)導(dǎo)人的日志就一致了，這樣的狀態(tài)會保持到該任期結(jié)束。
需要知道GO 切片知識
https://stackoverflow.com/questions/27055626/concisely-deep-copy-a-slice?rq=1
因為 //在失敗之后，領(lǐng)導(dǎo)人會將nextIndex遞減然后重試 AppendEntries RPC
所以要包在一個FOR循環(huán)里，失敗就重試，成功就RETURN,因為變成了循環(huán) 注意DEFER unlock就不能用在循環(huán)體里了，不然就死鎖了。
下圖我們發(fā)現(xiàn)第一條我們實現(xiàn)了，后面都沒有完整實現(xiàn)。第二條的前半段在之前Start()里實現(xiàn)的。后半段把條目應(yīng)用到狀態(tài)機后響應(yīng)客戶端還沒實現(xiàn)。
領(lǐng)導(dǎo)人規(guī)則的第五條，因為是要看MATCH INDEX，而MATCH INDEX只在發(fā)送成功的時候會更新。所以為了減少不必要的CHECK，我們可以放在
reply.Success里來做注意 這里中文是病句
因為原文為
If there exists an N such that N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm: set commitIndex = N (§5.3, §5.4).
我們一點一點來，先處理reply.Success
第五步 實現(xiàn)updateCommitIndex
就是根據(jù)上面的英文來實現(xiàn)，超過半數(shù)的話，就排序然后找中間偏大的那個，來比即可。
注意在找超過半數(shù)的時候，很容易忘記LEADER自己的INDEX沒有更新，造成臨界點剛好沒到半數(shù)。
到此為止，我們基本實現(xiàn)了startAppendLog，第一個//now only for heartbeat變?yōu)榱苏娴臅嗀PPEND LOG的方法
下面開始寫HANDLER
第六步 實現(xiàn)AppendEntries
這里論文也有寫怎么做，介于中文翻譯的質(zhì)量確實不理想。這里貼個英文圖
因為這邊開始會RETURN了。所以我們要把收到APPEND ENTRIES 這個RPC的CHANNEL 喚醒的操作放到DEFER里去
在UTIL.GO 里定義MIN INT 方法
不知道你有沒有注意到我們一直在更新commitIndex，但是我們沒有更新lastApplied
這里還有一條所有服務(wù)器的規(guī)則
如果commitIndex > lastApplied，lastApplied自增，將log[lastApplied]應(yīng)用到狀態(tài)機（5.3 節(jié)）
第七步 思考何時updateLastApplied
為了減少調(diào)用次數(shù)，我們只要思考何時會更新COMMITINDEX
發(fā)現(xiàn)2處
第八步 實現(xiàn)updateLastApplied
調(diào)試
BUG 1
按照老師的建議，我們先測2B最簡單的，發(fā)現(xiàn)出問題了，INDEX越界
排查了下。
這邊應(yīng)該是=，我之前寫成+=
BUG2
數(shù)組越界的錯沒了。下面的錯非常棘手。
他報了這個 config.go:465: one(100) failed to reach agreement
在仔細(xì)閱讀了https://thesquareplanet.com/blog/students-guide-to-raft/
我依然沒有任何收獲。
決定在關(guān)鍵位置打LOG。大概率是因為APPEND ENTRIES 這個RPC 有邏輯沒做對。
所以我在發(fā)送RPC前后，加了LOG
得到信息如下
感覺沒太大問題，不過可以知道REPLY 是SUCCESS的。說明HANDLER里面邏輯是正確的。
因為最終服務(wù)器需要在APPLY CHANNEL，讀信息
所以我們在CHANNEL出去的時候做一個打印，看下有沒有出去。
隨后因為走的分支是REPLY.SUCCESS
在這個里面把對應(yīng)的參數(shù)也打印一下。
打印結(jié)果，發(fā)現(xiàn)消息完全沒有出去的跡象。
分析LOG可以得知
matchIndex 一開始是-1，后來變成了0
而我們初始化的時候就對matchIndex 初始化為了0.
再增加了一個元素后，依然是0，而updateCommitIndex的關(guān)鍵就是N > commitIndex, a majority of matchIndex[i] ≥ N。
那么問題就是即使所有NODE 都收到了那個元素，然而matchIndex最大也是到0， 0是不會超過commitIndex 初始化的0
再回過去看commitIndex 和 matchIndex的定義
按照這個定義的理解，只有被提交的最高索引。那么初始化怎么說也應(yīng)該是-1呀。
我開始按照我的思路改成-1，APPLYMSG出去了?？墒菧y試需要的INDEX是我返回的INDEX還要+1.我又不好改測試。
一陣無語的時候我發(fā)現(xiàn)
這么重要的信息中文翻譯里竟然沒有
改動如下0改稱1，加上注釋
PASS 2B
Test Race
TEST.SH
因為有些并發(fā)的問題，可能不是每次重現(xiàn)，所以要盡可能多測來確定有沒有問題。
我把這個標(biāo)準(zhǔn)定為1000次， 可是1000次要跑很久。所以我通過SHELL來處理這個問題。
SHELL 腳本如下，每處理完10次TEST打一個進度
#!/bin/bash
export PATH="$PATH:/usr/lib/go-1.9/bin"
rm res -rf
mkdir res
test_list=(
2A
2B)
for i in `seq 1000`
do
if [ $(($i % 10)) -eq 0 ]
then
echo $i
fi
for j in ${test_list[@]}
do
go test -run $j &> ./res/$j
if [ $? -ne 0 ]
then
echo "run failed."
exit 1
fi
done
done
