1 引言

大約用了20多天的時(shí)間完成了6.824的lab2鸠天，期間穿插了畢業(yè)預(yù)答辯颗品，改論文趾徽，準(zhǔn)備外審等等事情朽缎，最終磕磕絆絆的完成了Lab2惨远，感覺(jué)算是自己寫(xiě)的程序中比較具有挑戰(zhàn)性的了，因?yàn)樵趯?shí)驗(yàn)過(guò)程中需要認(rèn)真的考慮并發(fā)话肖、加鎖北秽、死鎖等問(wèn)題，并且實(shí)際RAFT論文中省去了很多細(xì)節(jié)最筒，而且為了盡量通過(guò)測(cè)試與優(yōu)化性能贺氓，本人也對(duì)與RAFT論文中很多細(xì)節(jié)進(jìn)行更改，因此該Lab的完成具有一定挑戰(zhàn)床蜘。

實(shí)驗(yàn)結(jié)果

開(kāi)門見(jiàn)山辙培，先放結(jié)果：

對(duì)于2A部分，運(yùn)行1000次邢锯，都可以全部PASS扬蕊，取一組結(jié)果：

Test (2A): initial election ...
  ... Passed --   3.5  3  106   29540    0
Test (2A): election after network failure ...
  ... Passed --   5.5  3  158   29218    0
PASS
ok      _/home/hetianfang/gocodes/DS6.824/src/raft-2C   9.028s

對(duì)于2B部分，運(yùn)行1000次丹擎，也可以全部PASS厨相，取一組結(jié)果：

Test (2B): basic agreement ...
  ... Passed --   1.1  3   16    4686    3
Test (2B): RPC byte count ...
  ... Passed --   2.0  3   52  116026   11
Test (2B): agreement despite follower disconnection ...
  ... Passed --   5.3  3  152   38842    7
Test (2B): no agreement if too many followers disconnect ...
  ... Passed --   4.4  5  228   41540    3
Test (2B): concurrent Start()s ...
  ... Passed --   1.2  3   24    7126    6
Test (2B): rejoin of partitioned leader ...
  ... Passed --   4.0  3  100   23143    4
Test (2B): leader backs up quickly over incorrect follower logs ...
  ... Passed --  26.4  5 2132  673111  102
Test (2B): RPC counts aren't too high ...
  ... Passed --   2.7  3   82   24838   12
PASS
ok      _/home/hetianfang/gocodes/6.824_htf/src/raft-2B-success 48.052s

對(duì)于2C部分，運(yùn)行100次鸥鹉，除Figure 8 (unreliable)外所有測(cè)試均可順利通過(guò)蛮穿，但唯獨(dú)Figure 8 (unreliable)有過(guò)半的可能性無(wú)法通過(guò)，經(jīng)過(guò)本人分析毁渗，該測(cè)試項(xiàng)目為模擬網(wǎng)絡(luò)在長(zhǎng)時(shí)間混亂后能夠順利進(jìn)行提交践磅，該測(cè)試項(xiàng)目中使用cfg.setlongreordering(true)模擬在RPC回復(fù)時(shí)出現(xiàn)延遲（sometimes delay replies a long time），從而模擬長(zhǎng)時(shí)間網(wǎng)絡(luò)長(zhǎng)時(shí)間的混亂灸异，然而在模擬網(wǎng)絡(luò)混亂后并沒(méi)有恢復(fù)網(wǎng)絡(luò)狀態(tài)府适，本人在cfg.one(9999, servers, true)前采用cfg.setlongreordering(false)恢復(fù)網(wǎng)絡(luò)秩序，最終使得程序可以順利通過(guò)各項(xiàng)測(cè)試肺樟，取一組實(shí)驗(yàn)結(jié)果：

Test (2C): basic persistence ...
  ... Passed --   6.3  3  142   37280    6
Test (2C): more persistence ...
  ... Passed --  25.7  5 1692  265019   17
Test (2C): partitioned leader and one follower crash, leader restarts ...
  ... Passed --   2.8  3   52   12907    4
Test (2C): Figure 8 ...
  ... Passed --  34.1  5  680  125859    7
Test (2C): unreliable agreement ...
  ... Passed --  40.8  5 1484  412291  301
Test (2C): Figure 8 (unreliable) htf ...
  ... Passed --  30.6  5 2584  359827   20
Test (2C): churn ...
  ... Passed --  16.7  5  828  187978  103
Test (2C): unreliable churn ...
  ... Passed --  16.7  5  828  171317   64
PASS
ok      _/home/hetianfang/gocodes/DS6.824/src/raft-2C   173.823s

工程源碼

[源碼](CountingStars/6.824 (gitee.com))置于Gitee中檐春，為了省事許多實(shí)驗(yàn)過(guò)程中撰寫(xiě)的代碼帶有很多亂七八糟的注釋以及打印，只對(duì)于最終版本的簡(jiǎn)潔性進(jìn)行優(yōu)化么伯，Lab2實(shí)驗(yàn)中疟暖，最終經(jīng)優(yōu)化的代碼路徑為./src/raft/raft-2C-simplify

2 實(shí)現(xiàn)方式

Lab2分為ABC三部分，三部分內(nèi)容的如下：

• A：RAFT的leader選舉與心跳機(jī)制（Raft leader election and heartbeats）
• B：日志復(fù)制（Append new log entries）
• C：狀態(tài)持久化（Keep persistent state that survives a reboot）

三部分功能隔離，但是三部分的實(shí)現(xiàn)具有交叉俐巴，例如日志復(fù)制和心跳機(jī)制實(shí)際上是一體的骨望，而狀態(tài)持久化與RPC的發(fā)起與響應(yīng)相耦合，因此對(duì)于實(shí)現(xiàn)方式的描述不會(huì)按照三部分內(nèi)容展開(kāi)欣舵，而會(huì)是圍繞程序邏輯擎鸠。

主要類

程序主要實(shí)現(xiàn)基本都位于raft.go文件之中，除此之外缘圈，本人在time.go文件中實(shí)現(xiàn)了一個(gè)自定義的定時(shí)器以及一個(gè)具有限時(shí)功能的WaitGroup劣光，整個(gè)程序基本都圍繞著Raft這個(gè)類（Golang沒(méi)有嚴(yán)格的對(duì)象概念，不過(guò)這樣說(shuō)著方便）糟把，該類主要包括自帶的變量以及論文Figue2中所提及的變量绢涡，除此之外增加了applyCh用于記錄Raft對(duì)象初始化時(shí)提供的用于提交apply新的的chan，以及記錄本人聲明的其他用于記錄新的變量糊饱。Raft所包含多個(gè)成員函數(shù)垂寥，其中比較重要的成員函數(shù)有：

func RaftConstructer(peers []*labrpc.ClientEnd, me int, persister *Persister, applyCh chan ApplyMsg) *Raft
func (recv *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply)
func (recv *Raft) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply)
func (recv *Raft) startElection()
func (recv *Raft) broadcastAppendEntries()
func (recv *Raft) mainLoop()
func (recv *Raft) applyLoop()
func (recv *Raft) Start(command interface{}) (index int, term int, isLeader bool)

除Raft類外颠黎，還有ApplyMsg另锋，LogEntry,RequestVoteArgs，RequestVoteReply等類狭归，作用顯而易見(jiàn)無(wú)需描述夭坪，以及一些用于表示時(shí)間設(shè)置、狀態(tài)的預(yù)定義常量过椎。

整體運(yùn)行邏輯

單個(gè)節(jié)點(diǎn)的運(yùn)行開(kāi)始于其構(gòu)造函數(shù)RaftConstructer（本人對(duì)Make內(nèi)部又封裝了一個(gè)構(gòu)造函數(shù)）室梅，構(gòu)造函數(shù)中對(duì)于各個(gè)變量進(jìn)行初始化，并且啟動(dòng)兩個(gè)新的協(xié)程mainLoop和applyLoop疚宇，構(gòu)造函數(shù)基本流程為：

• 初始化各個(gè)變量
• 嘗試從persister中讀取歷史運(yùn)行信息
• 分別啟動(dòng)mainLoop和applyLoop

整個(gè)程序的運(yùn)行就是基于mainLoop和applyLoop亡鼠，是這個(gè)程序的核心，mainLoop主要用于監(jiān)測(cè)心跳是否超時(shí)以及發(fā)起選舉敷待；applyLoop用于將日志進(jìn)行提交间涵，其中mainLoop基本邏輯為：

• while自己這個(gè)Raft節(jié)點(diǎn)未被殺死：
  • 如果已經(jīng)心跳超時(shí)：
    • 切換為candidate狀態(tài)
    • 等待一個(gè)隨機(jī)的時(shí)間
    • 通過(guò)startElection發(fā)起選舉
  • 如果自己是leader：
    • 通過(guò)broadcastAppendEntries發(fā)起一次Append Entries
    • 等待一小段時(shí)間，防止心跳發(fā)送過(guò)于頻繁

通過(guò)以上邏輯可以實(shí)現(xiàn)對(duì)于心跳超時(shí)的監(jiān)測(cè)榜揖，以及在競(jìng)選成功后立即發(fā)送心跳包勾哩，其中所調(diào)用的startElection和broadcastAppendEntries兩個(gè)函數(shù)具有重要作用。

而applyLoop的基本邏輯為：

• while自己這個(gè)Raft節(jié)點(diǎn)未被殺死
  • 提交recv.log中所有index小于recv.commitIndex的日志

applyLoop的功能很簡(jiǎn)單举哟，也沒(méi)調(diào)用其他函數(shù)思劳，因此程序整體運(yùn)行邏輯的重點(diǎn)就是mainLoop，以及其包含的startElection與broadcastAppendEntries妨猩。

選舉與心跳

如前所述潜叛，startElection與broadcastAppendEntries是程序的重點(diǎn)，分別對(duì)應(yīng)選舉和日志復(fù)制兩大主要功能，整個(gè)Raft實(shí)現(xiàn)中也只有兩種RPC即選舉與日志復(fù)制钠导。

在startElection中通過(guò)RPC調(diào)用RequestVote震嫉，在broadcastAppendEntries中調(diào)用AppendEntries，因此startElection與RequestVote牡属，broadcastAppendEntries與AppendEntries是對(duì)應(yīng)的票堵！

startElection和broadcastAppendEntries均用于某個(gè)節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播，RequestVote與AppendEntries則分別為接收廣播的節(jié)點(diǎn)處理請(qǐng)求的回調(diào)函數(shù)逮栅。

選舉廣播

startElection用于發(fā)起一次選舉悴势，其流程如下（該流程與論文有不一致）：

• 自增自身的任期Term
• 向各個(gè)其他節(jié)點(diǎn)在規(guī)定時(shí)間內(nèi)并發(fā)執(zhí)行以下操作：
  • 通過(guò)RPC調(diào)用RequestVote，請(qǐng)求投票
  • 如果RPC請(qǐng)求成功并且獲得了VoteGranted：
    • 增加一個(gè)自身獲得的選票
  • 如果RPC請(qǐng)求成功并且被索票節(jié)點(diǎn)的Term大于自身Term：
    • 更新自身Term與被索票節(jié)點(diǎn)一致
    • 更新自身State為follower
• 如果加上自己一票數(shù)量超過(guò)了節(jié)點(diǎn)數(shù)量一半措伐，并且自己的State仍然是Candidate：
  • 給自己投一票
  • 相應(yīng)的更新lastVoteTerm和votedFor兩部分有關(guān)投票信息
  • 設(shè)定自身state為leader
  • leader初始化（matchIndex特纤、nextIndex數(shù)組的初始化）
• 狀態(tài)持久化（如果需持久化狀態(tài)有變動(dòng)的話）

本人程序中與論文的差異主要在于：

1. 選舉過(guò)程中不存在刷新選舉定時(shí)器 ：目的在于減少選舉失敗的間隔，加速選舉進(jìn)程
2. 選舉過(guò)程中先索要其他節(jié)點(diǎn)的票：如果先索要自己的票侥加，將使得在長(zhǎng)時(shí)間的RPC過(guò)程中持有自己這一票這個(gè)資源捧存，這更容易產(chǎn)生平票
3. 僅在其他節(jié)點(diǎn)票數(shù)量滿足要求時(shí)給自己投票：防止自己這一票被浪費(fèi)掉

以上處理均為了加速選舉進(jìn)程，盡量減少資源競(jìng)爭(zhēng)與平票

選舉RPC回調(diào)函數(shù)

RequestVote為處理投票請(qǐng)求的回調(diào)函數(shù)担败，其基本流程如下：

• 如果索票candidate的Term小于自身Term：
  • 拒絕投票昔穴，返回自身任期
  • return
• 如果索票的candidate日志比自身更up to date，且自己沒(méi)有比當(dāng)前索票的candidate更新的任期投過(guò)票：
  • 更新自身state為follower
  • 更新自身投票記錄
  • 更新自身任期Term
  • 為索票的候選人投票提前，返回自身任期
  • return
• defer中吗货，狀態(tài)持久化（如果需持久化狀態(tài)有變動(dòng)的話）

日志添加廣播

broadcastAppendEntries用于leader向其他節(jié)點(diǎn)進(jìn)行日志復(fù)制與發(fā)送心跳，其基本流程如下：

• 設(shè)定所需添加日志結(jié)尾位置狈网，初始化successCnt宙搬， followerCnt， finishCnt三個(gè)變量均為1

• 向各個(gè)其他節(jié)點(diǎn)在規(guī)定時(shí)間內(nèi)并發(fā)執(zhí)行以下操作：

  • 通過(guò)RPC調(diào)用AppendEntries拓哺，嘗試添加日志
  • 如果RPC調(diào)用成功勇垛，并且成功添加日志：
    • finishCnt，followerCnt士鸥，successCnt均加一
  • 如果RPC調(diào)用成功闲孤，未成功添加日志，但該節(jié)點(diǎn)仍然認(rèn)同自己是leader：
    • finishCnt础淤，followerCnt加一
    • 更新該節(jié)點(diǎn)對(duì)應(yīng)的nextIndex
  • 如果RPC調(diào)用成功崭放，未成功添加日志，且該節(jié)點(diǎn)不認(rèn)同自己是leaer：
    • finishCnt加一
    • 設(shè)定自身state為follower

• 如果followerCnt大于節(jié)點(diǎn)數(shù)量一半：

  • 刷新選舉定時(shí)器
  • 如果successCnt大于節(jié)點(diǎn)數(shù)量一半：
    • 更新commitIndex

• 狀態(tài)持久化（如果需持久化狀態(tài)有變動(dòng)的話）

其中successCnt鸽凶， followerCnt币砂， finishCnt三個(gè)變量分別表示：成功添加日志的節(jié)點(diǎn)數(shù)量，成功認(rèn)同自身為leader的節(jié)點(diǎn)數(shù)量玻侥，成功完成的RPC數(shù)量决摧，其中finishCnt僅用于監(jiān)測(cè)運(yùn)行狀態(tài)，實(shí)際對(duì)于程序邏輯沒(méi)有影響。

日志復(fù)制RPC回調(diào)函數(shù)

AppendEntries為處理日志復(fù)制請(qǐng)求的回調(diào)函數(shù)掌桩，其基本流程如下：

• 如果發(fā)送日志復(fù)制請(qǐng)求的節(jié)點(diǎn)任期小于自身任期：

  • 拒絕復(fù)制边锁，回傳自身的任期
  • return

• 刷新選舉計(jì)時(shí)器

• 設(shè)定自身state為follower

• 更新自身term

• 如果請(qǐng)求參數(shù)中PrevLogIndex和PrevLogTerm不符合自身日志：

  • 拒絕復(fù)制，回傳自身任期波岛，并給出一個(gè)推薦的Index即RecommendPrevLogIndex
  • return

• 如果請(qǐng)求中的日志中存在自己未包含的日志：

  • 截?cái)?code>PrevLogIndex之后的日志
  • 添加新的日志

• 更新自身commitIndex

• defer中茅坛，狀態(tài)持久化（如果需持久化狀態(tài)有變動(dòng)的話）