MIT6824Lab2A

jiezi

5 年前

Lab2A 的地址:https://pdos.csail.mit.edu/6.824/labs/lab-raft.html

Lab2A 需要我们做 Leader Election 部分。
根据论文，我们在 Lab2A 需要完成的内容是：

初始选举
Candidate 发布RequestVote rpc
Leader 发布AppendEntry rpc, 包括心跳
server 的状态转换(Follower, Candidate, Leader)

基本上就是照着 paper figure 2 去做。

Lab2A 的 Hint(真多)：

为 raft.go 添加需要的状态.
定义 log entry 的结构.
填写 RequestVoteArgs 和RequestVOteReply结构.
修改 Make() 去创建后台 goroutine, 必要时这个 goroutine 会发送RequestVoteRPC.
实现RequestVote()RPC handler.
定义AppendEntriesRPC 结构和 handler.
处理 election timeout 和只 vote 一次.
tester要求 heartbeat 发送速率不能超过 10 个 /s,
5s 内选出新 leader, 即使因为 split vote 导致多轮选举. 所以要选择恰当的时间参数.
因为 tester 的限制, 所以不能按照论文中的 election timeout 设置为 150ms~300ms, 必须更大. 但不能太大, 否则没办法达到 5s 内选出 leader.
切记, 在 Go 中, 大写字母开头的函数和结构 (方法和成员) 才能被外部访问!

lab 2A 有两个测试:TestInitialElection()和TestReElection(). 前者较为简单, 只需要完成初始选举并且各节点就 term 达成一致就可以通过.

经过不断重构, 最后的程序结构如下:

MainBody(), 负责监听来自 rf.Controller 的信号并转换状态.
Timer(), 计时器.
Voter(), 负责发送 RequestVote RPC 和计算选举结果．
APHandler(), 负责发送心跳，并且统计结果．

四个通过 channel 来通信 (自定义整型信号)．
先前的设计是MainBody() 监听来自若干个 channel 的信号，后来了解到
channel 一发多收, 信号只能被一个 gorouine 接受, 可能会有出乎意料的后果．

随后修改为 MainBody 主循环只监听rf.Controller，然后向其他 channel 中发送信号(MPSC).

TestReElection(), 时不时 fail, 预算笔者
给TestReElection()添加一些输出, 将其分为多个阶段, 方便 debug:

    选出 leader1
# 1 ------------------------------
    leader1 下线
    选出新 leader
# 2 ------------------------------
    leader1 上线, 变为 follower
# 3 ------------------------------
    leader2 和 (leader2 + 1) % 3 下线
    等待 2s, 没有新 leader 产生
# 4 ------------------------------
    (leader2 + 1) % 3 产生
    选出新 leader
# 5 ------------------------------
    leader2 上线
# 6 ------------------------------

但是测试会是不是失败，都是在第 3 - 4 阶段时失败。原因是：此时系统中应该不存在 leader, 但是某节点仍声称是 leader.

笔者进行多次测试发现如下规律:

test    leader1  leader2  (leader2 + 1) % 3
success   0         2         0
failed    0         1         2
success   2         1         2
success   1         0         1
failed    0         1         2
..

只有当 (leader2 + 1) % 3 == leader1时才成功! 而且导致 fail 的是leader1!

条件 l1 == (l2 + 1) % 3 使得在第三段时, l1, l2 都下线, 所以网络中没有 leader 了. 如果不满足这个条件, 加上 Old leader 迟迟不变为 Follower, 会导致测试失败.

继续调试发现: leader1 重新加入网络时, 没有收到 HeartBeat(会使 leader1 变为 follower), 也没有 send HB(通过查看 HB reply 可以得知更大的 Term 从而变为 follower), 也没有收到 RequestVote RPC.l

进一步调试发现新 leader 给老 leader 发 HB 没有调用AppendEntry rpc.

通过大量测试, 打日志, 分析日志, 基本确定是某些 gorouine 饥饿导致 old leader 迟迟不能变为 follower, 从而使得函数 checkNoLeader() 失败, 导致测试失败.

依据是: 在某次测试 (成功) 中, leader1 在第四阶段后通过 RequestVote RPC 收到了 RPCwithLargerTerm 从而变为 follower, 虽然这个本应该在前几个阶段就执行了. 但是另一个 leader 没有变 follower.

于是笔者修改 TestReElection() 函数, 在 2 - 3 和 4 - 5 阶段让测试函数睡眠若干个 election timeout:

fmt.Println("2--------------")
...
time.Sleep(time.Duration(2 * ElectionTimeout) * time.Millsecond)
// ...
fmt.Println("3--------------")
// ...
time.Sleep(time.Duration(2 * ElectionTimeout) * time.Millsecond)

笔者发现, 经过若干时间, old leader 都会得知存在更大的 Term 从而变为 follower. 在修改后的测试中, 每次测试均正常通过.

但是 仍无法解决饥饿 的问题, 这个需要继续深究了. Lab2A 先告一段落.

虽然是按照论文来实现，但在实现过程中，屡屡遗漏某些细节，不得不花大量时间测试(比如 rpc 中携带比自己还大的 Term, 自身就要立刻变为 follower).

笔者花了一个多星期的课余时间来 debug, 先怀疑程序出现死锁了, 接着分析是 mutex 还是 chan 导致死锁。然后通过到处打日志的方式排除了死锁。此中还把程序重构了。随后怀疑是饥饿问题，然后查阅资料发现的确有饥饿的可能，又通过修改测试函数，加长等待时间, 发现 old leader 最终都转化为 follower 了。

代码比价多, 约 500 行. 因为 MIT 要求代码仓库不能公开，所以没法贴上来。

此外，对于多线程 + 定时器这样的场景，基本不能用断点调试的办法。打日志，分析日志几乎是唯一路径。分析日志也挺考验思维逻辑的。

MIT6824Lab2A

Lab2A

测试

构思

Bugs

总结