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

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) % 3success   0         2         0failed    0         1         2success   2         1         2success   1         0         1failed    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要求代码仓库不能公开， 所以没法贴上来。

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