【分布式】MIT 6.824 Lab 2B实现细节分析

基于6.824 2020版 http://nil.csail.mit.edu/6.824/2020/schedule.html

Lab 2A（选举）一天就完成了，主要是第一次开始写Raft需要稍微熟悉一下，但是几乎不用修改，很容易就通过了。不过到了Lab 2B就会发现2A能够通过纯属侥幸，有很多小细节逻辑错误，是由于2A的限制不大还是能够通过。

Lab 2B的完整实现花了整3天，调试就花了一天半，首先修改2A的遗留问题就要花其中接近一个白天。而且这还是我先看了LEC 5、6、7，以及Assign中的到Lab 2B（也就是log 复制与提交）相关建议/提示之后再完成的，这些准备的内容就花了快一个礼拜（因为不是光看就得了，觉得重点的要标记，由于是英文，一边看能看懂但为了再翻的时候方便还是要适当翻译一下）。
整个实现完全没有看课程网站以外的资料，尤其是其他人的实现。当然确实也不能保证2A完全正确，但是我连续运行过了测试脚本5次以上，可能一定程度上是正确的（例如，最后一次的bug会在运行大致3次时在倒数第二个项目，也就是在TestBackup2B爆出来）（同时由于我shell脚本还不太熟练，LEC 5提供的go-test-many.sh直接用有点问题，暂时还没有用）。

wangjy@DESKTOP-861RECN:~/research/6.824/src/raft$ time go test -run 2B
Test (2B): basic agreement ...
  ... Passed --   0.7  3   16    4804    3
Test (2B): RPC byte count ...
  ... Passed --   1.4  3   48  115376   11
Test (2B): agreement despite follower disconnection ...
  ... Passed --   4.3  3  124   33193    7
Test (2B): no agreement if too many followers disconnect ...
  ... Passed --   3.5  5  324   72078    3
Test (2B): concurrent Start()s ...
  ... Passed --   0.7  3   12    3624    6
Test (2B): rejoin of partitioned leader ...
  ... Passed --   6.1  3  305   75278    4
Test (2B): leader backs up quickly over incorrect follower logs ...
  ... Passed --  15.5  5 2800 2269915  102
Test (2B): RPC counts aren't too high ...
  ... Passed --   2.1  3   38   12074   12
PASS
ok      _/home/wangjy/research/6.824/src/raft   34.290s

real    0m34.960s
user    0m2.211s
sys     0m2.627s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我还在课程提供的日志函数的基础上又封装了一个小Log打印工具，会在打印内容前加上当前的节点编号（即rf.me），个人感觉会看着方便一点。

func (rf *Raft) PeersDPrintf(format string, a ...interface{}) {
	content := fmt.Sprintf(format, a...)
	number := strconv.Itoa(rf.me)
	blankLeft := ""
	blankRight := ""
	for i:=0;i<rf.me;i++ {
		blankLeft = blankLeft + " "
	}
	for i:=rf.me+1;i<len(rf.peers);i++ {
		blankRight = blankRight + " "
	}
	blankRight = blankRight + " "
	DPrintf("Peers " + blankLeft + number + blankRight + content)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

显示效果：

wangjy@DESKTOP-861RECN:~/research/6.824/src/raft$ time go test -run 2B
Test (2B): basic agreement ...
2023/11/15 21:38:07 Peers 0   change from [Follower]-Term[0]-Vote[0] to [Candidate]-Term[1]-Vote[0] with last log[0]-Term[0]
2023/11/15 21:38:07 Peers 0   change from [Candidate]-Term[1]-Vote[0] to [Leader]-Term[1]-Vote[0] with last log[0]-Term[0]
2023/11/15 21:38:07 Peers 0   ~~~~~~~~~~~~~~ become Leader of Term[1] ~~~~~~~~~~~~~~
2023/11/15 21:38:07 Peers 0   receive log[1] at Term [1]
2023/11/15 21:38:07 Peers  1  log len[0] match [0] append to len[1]
2023/11/15 21:38:07 Peers   2 log len[0] match [0] append to len[1]
2023/11/15 21:38:07 Peers 0   receive LogAppend reply from ind[1], termStamp[1], currentTerm[1], prevLogIndex[0]-Entries len[1]; Success[true]
2023/11/15 21:38:07 Peers 0   update commit from [0] to [1]
2023/11/15 21:38:07 Peers 0   response for log[1]
2023/11/15 21:38:07 Peers 0   receive LogAppend reply from ind[2], termStamp[1], currentTerm[1], prevLogIndex[0]-Entries len[1]; Success[true]
2023/11/15 21:38:07 Peers  1  increase commitIndex from [0] to [1]
2023/11/15 21:38:07 Peers   2 increase commitIndex from [0] to [1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里提供一些个人在debug时遇到的原文中没有的个人实现的细节，或注意事项。当然课程已经提到了最重要的点是要按照原文的图2来实现，在此基础上，我自己总结的问题/关键点是：

1. 每次收到RPC返回的信息时，重新获取锁后都要校验保证当前的一些状态没变，例如几乎每次都要校验的：currentTerm号或membership（Leader、Candidate或Follower），这种问题其实LEC 5也强调了。
2. 注意Lab 2B校验程序是会收集每个节点向各自applyCh提交的ApplyMsg然后进行校验，所以每个从节点也要发送applyCh。
3. 注意每次当选Leader后要重置nextIndex[]和matchIndex[]
4. 注意对于一些开启新协程的任务，如选举倒计时——需要标记一个时间戳，然后在time.Sleep后校验，或是发送选票——需要标记选举term戳等，这里的如“时间戳”和“term戳”需要作为参数传入对应使用go调用的函数，同时调用的时候是判断需要进行状态转换并持有锁的（也就是类似CAS问题）。
5. 收到投票的节点的角色和状态可能各种各样，但是如何处理原文并没有交代得很详细，这里有两个关键点（主要是要防止我们在后期实现时过度设计）：
   a. 一个Term只有一个Leader能够当选。或者换句话说，一个Term最多属于一个Leader。
   b. 一个Follower在一个Term中只能给一个Candidate投票，绝不能给其他Candidate投票。
6. 任何节点的currentTerm是不能回退的（这个课程中有提及为什么），所以如果Candidate和Leader收到了带有高的Term的RequestVote，即使发送者的log不够Up-to-date，其也要更新自己的Term，然后进行相应操作，例如Leader要先退位在参选等等。否则该发送者（不够Up-to-date的Candidate）会一直试图选举，这样该节点就不可用了。
7. 有个问题是，当一个leader累积了很多未提交的log后，又成为了Follower。由于从节点也要更新commitIndex，并提交log到自己的applyCh，那么其commitIndex一定要在至少与新Leader对齐过一次再用AppendEntries中的LeaderCommit更新，否则会提交没有共识的log。我这里通过限制match包和心跳包的内容来实现。（这一点就是我在TestBackup2B爆出的bug）

然后这里有个自己的设计的一个小数据结构，如何更新Leader的commitIndex呢？——在更新了一个从节点的matchIndex后触发，维护第majority个大的matchIndex[]即为commitIndex（Leader自己的matchIndex等于自己的log长度）