介紹

通過(guò) 實(shí)驗(yàn)一: MapReduce奶浦，我們慢慢熟悉了實(shí)驗(yàn)環(huán)境和 Go 語(yǔ)言∷奖裕現(xiàn)在我們要開(kāi)始構(gòu)建一個(gè)大實(shí)驗(yàn)淤击，高性能匠抗，分布式 Key/Value 服務(wù)。實(shí)驗(yàn)分三個(gè)階段污抬，首先我們實(shí)現(xiàn) Raft 協(xié)議汞贸，接著在 Raft 基礎(chǔ)上構(gòu)建一個(gè) Key/Value 服務(wù)，然后將服務(wù)分片(shard）化以提高性能印机，最后給分片間的操作提供事務(wù)性保障矢腻。

本次我們先來(lái)實(shí)現(xiàn) Raft。在一個(gè)用備份提高可用性的系統(tǒng)中射赛，Raft 用于管理備份服務(wù)器多柑。在高可用系統(tǒng)中，通過(guò)備份楣责，小部分的機(jī)器故障不會(huì)影響系統(tǒng)的正常工作竣灌，但問(wèn)題是每臺(tái)機(jī)器都有可能發(fā)生故障，所以不能保證機(jī)器集群上的數(shù)據(jù)始終是一樣的秆麸，而 Raft 協(xié)議就是幫助我們判斷帐偎，哪些數(shù)據(jù)才是正確的，哪些需要拋棄并用正確的數(shù)據(jù)更新蛔屹。

Raft 的底層思路是實(shí)現(xiàn)一個(gè)備份狀態(tài)機(jī)削樊。Raft 將所有的客戶端請(qǐng)求組織成一個(gè)序列，稱之為 log兔毒，不僅如此漫贞，在執(zhí)行 log 之前，Raft 還會(huì)保證所有的備份服務(wù)器都同意執(zhí)行本次 log 的內(nèi)容育叁。每個(gè)備份服務(wù)器都會(huì)按照前后順序執(zhí)行 log迅脐，讓客戶端的請(qǐng)求應(yīng)用到狀態(tài)機(jī)上。由于每臺(tái)機(jī)器都是按相同順序執(zhí)行相同請(qǐng)求豪嗽，所以他們始終保持相同的狀態(tài)谴蔑。如果一個(gè)服務(wù)器失敗后重連了豌骏，Raft 負(fù)責(zé)更新它的 log。只要大多數(shù)機(jī)器保持健康狀態(tài)并且能相互通訊隐锭，Raft 就能讓系統(tǒng)正確的持續(xù)運(yùn)行窃躲，否則系統(tǒng)將不再接受新的請(qǐng)求，一旦有足夠的機(jī)器钦睡，系統(tǒng)將會(huì)從之前狀態(tài)開(kāi)始繼續(xù)進(jìn)行蒂窒。

在本次實(shí)驗(yàn)中，我們將用 Go 語(yǔ)言實(shí)現(xiàn) Raft荞怒，規(guī)模當(dāng)然比實(shí)驗(yàn)一大多了洒琢。具體來(lái)說(shuō)就是幾個(gè) Raft 實(shí)例通過(guò) RPC 的方式通訊已維護(hù)各自的 log。Raft 集群應(yīng)該能接受帶有序號(hào)的指令或者叫 log 序列褐桌。每個(gè) log 都保證可以提交衰抑。

注意：只能通過(guò) RPC 實(shí)現(xiàn) Raft 實(shí)例之間的溝通。所以荧嵌，不同的 Raft 實(shí)例之間不能共享變量呛踊，也不要用文件。

本次實(shí)驗(yàn)我們先來(lái)實(shí)現(xiàn) Raft 論文中前5章的內(nèi)容完丽，包括保存需持久的狀態(tài)恋技，因?yàn)楫?dāng)一個(gè)服務(wù)器重連后需要根據(jù)這些信息恢復(fù)拇舀。

Raft 相關(guān)資料：

1. 論文
2. 動(dòng)畫展示

雖然實(shí)現(xiàn) Raft 協(xié)議的代碼量不是最大逻族，但是要讓它正確的工作并不是一件容易的事情。需要很多邊界情況骄崩。當(dāng)測(cè)試不通過(guò)時(shí)聘鳞，不易想明白是那種場(chǎng)景出了問(wèn)題，所以不好debug要拂。

寫代碼之前要仔細(xì)閱讀論文抠璃，實(shí)現(xiàn)基本按照論文的描述，測(cè)試也是按照論文設(shè)計(jì)的脱惰。圖2是比較完整的偽代碼搏嗡。

實(shí)驗(yàn)環(huán)境

拉取代碼

$ git clone git://g.csail.mit.edu/6.824-golabs-2016 6.824
$ cd 6.824
$ ls
Makefile src

進(jìn)入 raft 文件夾，運(yùn)行測(cè)試代碼

$ cd src/raft
$ GOPATH=~/6.824
$ export GOPATH
$ go test
Test: initial election ...
--- FAIL: TestInitialElection (5.03s)
    config.go:270: expected one leader, got 0
Test: election after network failure ...
--- FAIL: TestReElection (5.03s)
    config.go:270: expected one leader, got 0
...
$

當(dāng)然沒(méi)有通過(guò)拉一，當(dāng)你寫好后采盒，再次測(cè)試，看到下面的輸出蔚润，表示通過(guò)測(cè)試：

$ go test
Test: initial election ...
  ... Passed
Test: election after network failure ...
  ... Passed
...
PASS
ok      raft    162.413s

協(xié)議的實(shí)現(xiàn)代碼主要放在 raft/raft.go 文件中磅氨。這個(gè)文件里面已經(jīng)寫好了一些框架代碼，一些發(fā)送和接受 RPC 的示例嫡纠，還有一些保存持久化信息的例子烦租。

下面提供了一些接口延赌，我們的 Raft 需要一一實(shí)現(xiàn)，測(cè)試代碼會(huì)以它為測(cè)試藍(lán)本叉橱。

// 創(chuàng)建一個(gè)新的 Raft 實(shí)例
rf := Make(peers, me, persister, applyCh)

// 處理一個(gè)指令
rf.Start(command interface{}) (index, term, isleader)

// ask a Raft for its current term, and whether it thinks it is leader
// 返回該 Raft 實(shí)例的當(dāng)前 term 和是否是 Leader
rf.GetState() (term, isLeader)

// 每當(dāng)有一個(gè)請(qǐng)求被執(zhí)行了挫以，都應(yīng)當(dāng)向服務(wù)送一個(gè) ApplyMsg
type ApplyMsg

一個(gè)服務(wù)調(diào)用 Make(peers,me,…) 創(chuàng)建一個(gè) Raft 實(shí)例。peers 是
已經(jīng)創(chuàng)立的 RPC 連接數(shù)組赏迟，互相之間可訪問(wèn)屡贺；me 是當(dāng)前創(chuàng)建的實(shí)例在 peers 數(shù)組中的索引值。Start(command) 讓 Raft 集群嘗試將 command 追加到備份復(fù)制的log中锌杀。Start() 應(yīng)該馬上響應(yīng)甩栈，不需要等待執(zhí)行結(jié)束。服務(wù)可通過(guò)監(jiān)聽(tīng) applyCh 的 ApplyMsg 到達(dá)來(lái)判斷某個(gè) command 已經(jīng)完成糕再。

Raft 節(jié)點(diǎn)之間使用 labrpc 進(jìn)行通信量没。raft.go 里面有選舉Leader的RPC示例，發(fā)送 sendRequestVote()突想，處理請(qǐng)求 RequestVote()殴蹄。

Step I: 選舉Leader 和 heartbeat

要求：只能有一個(gè) Raft 被選舉成為 leader，并且用 heartbeat(發(fā)送空的 AppendEntry) 保持 leader 狀態(tài)猾担。通過(guò)前兩個(gè)測(cè)試袭灯。

提示：

1. 仔細(xì)閱讀論文中的圖二部分，為 Raft struct 添加必要的屬性绑嘹。同時(shí)還需要定義一個(gè)新的 struct 表示 log稽荧。不要忘了公開(kāi)的屬性即開(kāi)頭大寫才可以通過(guò) RPC 傳遞。

2. 先實(shí)現(xiàn)選舉部分工腋，完善 RequestVoteArgs 和 RequestVoteReply姨丈。在 Make() 方法里面創(chuàng)建一個(gè) gorutine，如果過(guò)了一段時(shí)間還沒(méi)有其他 Raft 給它發(fā)消息擅腰，說(shuō)明此時(shí)沒(méi)有 leader蟋恬，即讓自己成為 candidate，發(fā)送 RequestVote 競(jìng)選 leader，當(dāng)然對(duì)于每個(gè) Raft 來(lái)說(shuō)也要能夠處理別人發(fā)來(lái)的 RequestVote，滿足一定的規(guī)則時(shí)則投他一票秽褒。

3. 要實(shí)現(xiàn) heartbeat扎即，得先定義 AppendEntries RPC 相關(guān)的 struct。然后讓 leader 定期給他的小弟(follower) 發(fā)送。當(dāng)然需要實(shí)現(xiàn)處理方法，成功處理后需要更新follower選舉等候時(shí)間，這樣 leader 就可通過(guò)發(fā) heartbeat 保持它的領(lǐng)導(dǎo)權(quán)洒沦。

4. 每個(gè) Raft 的選舉等待周期應(yīng)有一定的隨機(jī)性，以防止總是有多個(gè) Raft 同時(shí)競(jìng)選而無(wú)法選出 leader 的情況价淌。

Step 2: 接受客戶端命令

選出了 leader 然后就可以將這個(gè)集群當(dāng)做一個(gè)整體申眼，它能接受指令瞒津，并且保證持久性且具備一定容錯(cuò)性。所以我們要讓 Start() 方法能夠接受指令并把它們放入 log 中括尸。只有 leader 向 log 列表中添加新的內(nèi)容巷蚪，follower 的 log 列表通過(guò)來(lái)自 leader AppendEntries RPC 更新。

要求：leader 和 follower 的 log 列表更新操作濒翻。完善 Start() 方法屁柏，完善 AppendEntries，實(shí)現(xiàn) sendAppendEntries 和 handler有送。通過(guò) "basic persistence" 之前所有的測(cè)試淌喻。

提示：

1. 需要考慮各種失敗的情況如無(wú)法接收到 RPC，宕機(jī)后重連等雀摘。同時(shí)還得實(shí)現(xiàn)論文 5.4.1 中描述的競(jìng)選階段的限制裸删。

2. 盡管只有 leader 會(huì)將新的log追加到 log 列表中，但每個(gè) raft 都需要將 log 應(yīng)用即執(zhí)行 log 中的命令阵赠。所以盡可能將 log 的操作和應(yīng)用邏輯解耦涯塔。

3. 盡量降低 follower 同步 leader 時(shí)的溝通次數(shù)。

Step 3: 持久化數(shù)據(jù)

一個(gè) Raft 服務(wù)器重連后能恢復(fù)到宕機(jī)時(shí)候的狀態(tài)清蚀，所以我們需要持久化一些必要狀態(tài)信息匕荸。可參考論文圖二枷邪。

一個(gè)生產(chǎn)環(huán)境下的 Raft 服務(wù)器需要將狀態(tài)信息持久化到磁盤中榛搔，我們實(shí)驗(yàn)為了簡(jiǎn)化，將持久化操作封裝到 Persister 中齿风。用 Make() 創(chuàng)建 Raft 實(shí)例時(shí)需要傳入 Persister 參數(shù)药薯，用于初始化狀態(tài)信息绑洛，同時(shí)在 Raft 實(shí)例狀態(tài)改變時(shí)保存下來(lái)救斑。相關(guān)方法為 ReadRaftState() 和 SaveRaftState().

要求：

完善 persist 方法，然后在合適的時(shí)機(jī)調(diào)用真屯，即考慮在 Raft 協(xié)議中何種情況下需要持久化狀態(tài)信息脸候。需能通過(guò) "basic persistence" 測(cè)試(go test -run 'TestPersist1$')

注意：

1. persist() 需要將數(shù)據(jù)轉(zhuǎn)化成二進(jìn)制才能存儲(chǔ)

2. 為了避免 OOM(Out Of Memory)，Raft 會(huì)定期清理老的 log绑蔫，下個(gè)實(shí)驗(yàn)我們會(huì)用 snapshotting(論文的第7章) 解決這個(gè)問(wèn)題运沦。

提示：

1. RPC 和 GOB 只會(huì)對(duì) struct 的公開(kāi)屬性即首字母大寫有效。
2. 有些嚴(yán)格測(cè)試需要實(shí)現(xiàn)論文的第7頁(yè)尾到第8頁(yè)上部灰線標(biāo)記的部分配深，即當(dāng) AppendEntries 中的 log 與本 follower 沖突時(shí)携添，給 leader 反饋沖突的 term 和下一個(gè) index。