乐趣区

MIT6824Lab2A

Lab2A

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 的结构.
  • 填写 RequestVoteArgsRequestVOteReply结构.
  • 修改 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).

Bugs

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 要求代码仓库不能公开,所以没法贴上来。

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

退出移动版