介紹

通過 實(shí)驗(yàn)一: MapReduce，我們慢慢熟悉了實(shí)驗(yàn)環(huán)境和 Go 語言?，F(xiàn)在我們要開始構(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ù)性保障。

本次我們先來實(shí)現(xiàn) Raft。在一個(gè)用備份提高可用性的系統(tǒng)中，Raft 用于管理備份服務(wù)器。在高可用系統(tǒng)中，通過備份，小部分的機(jī)器故障不會(huì)影響系統(tǒng)的正常工作，但問題是每臺(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)開始繼續(xù)進(jìn)行。

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

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

本次實(shí)驗(yàn)我們先來實(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)測試不通過時(shí)，不易想明白是那種場景出了問題，所以不好debug。

寫代碼之前要仔細(xì)閱讀論文，實(shí)現(xiàn)基本按照論文的描述，測試也是按照論文設(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)行測試代碼

$ 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)然沒有通過，當(dāng)你寫好后，再次測試，看到下面的輸出，表示通過測試：

$ 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)，測試代碼會(huì)以它為測試藍(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ù)組，互相之間可訪問；me 是當(dāng)前創(chuàng)建的實(shí)例在 peers 數(shù)組中的索引值。Start(command) 讓 Raft 集群嘗試將 command 追加到備份復(fù)制的log中。Start() 應(yīng)該馬上響應(yīng)，不需要等待執(zhí)行結(jié)束。服務(wù)可通過監(jiān)聽 applyCh 的 ApplyMsg 到達(dá)來判斷某個(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)。通過前兩個(gè)測試。

提示：

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

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

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

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

Step 2: 接受客戶端命令

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

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

提示：

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

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)信息?？蓞⒖颊撐膱D二。

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

要求：

完善 persist 方法，然后在合適的時(shí)機(jī)調(diào)用，即考慮在 Raft 協(xié)議中何種情況下需要持久化狀態(tài)信息。需能通過 "basic persistence" 測試(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è)問題。

提示：

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