实现要求

实现 Raft 选举和心跳逻辑(即不带日志条目的 AppendEntries)。本部分仅要求实现:

  1. 选出唯一的领导者,领导者选出后会持续进行心跳避免其他人发起选举
  2. 旧的领导者宕机或者网络故障无法触达时,选出新的领导者

PartA 并不需要实现日志同步逻辑,连带着在收到选举请求时,也都先忽略比较日志新旧的逻辑。

写完后在 src/raft 文件夹,使用 go test -run PartA -race 来测试代码逻辑是否正确、是否有数据竞态。

实现要点

下面罗列下实现概要:

  1. 遵照论文图 2 进行实现,但当前只需要关心收发 RequestVote 请求、选举相关的规则和状态转换
  2. 选举逻辑:填充 RequestVoteArgsRequestVoteReply 结构体。修改 Make() 函数,在创建 Raft Peer 的时候,创建超时检测、发起选举的后台 goroutine。实现 RequestVote() 回调函数,以在 Leader 要票时进行投票。
  3. 心跳逻辑:为了保证 Leader 当选后压制其他 Peer 再次发起选举,你需要定义 AppendEntriesArgsAppendEntriesReply 结构体,但暂时并不需要填充字段,因为 PartA 你并不需要实现日志同步逻辑。只需要实现 AppendEntries() 回调函数,在收到 AppendEntries RPC 请求时,重置选举计时器即可。
  4. 随机超时:论文中着重强调了,为了避免“活锁”——每个人都不断地选自己,需要让选举超时是随机的。可以使用 golang 的 rand 包来制造随机超时。
  5. 测试限制1:测试代码要求 Leader 每秒不能发超过几十次的心跳 RPC,也即你的心跳间隔不能太小。论文中的 5.2 小节提到过选举超时可以选取 150ms ~ 300ms 的超时间隔,这意味着你的心跳间隔不能大于 150ms(否则不能压制其他 Peer 发起选举)。当然,你可以不按照论文来,适当调大选举超时范围,但也不能太大,原因见下一条。
  6. 测试限制2:测试代码要求在多数节点存活时,必须在 5s 内选出 Leader。需要注意的是,即使多数节点都存活,也不一定在一个轮次的选举 RPC 就能选出主(比如很小概率的有两个 Peer 同时发起选举并造成平票),因此要仔细选取选举超时参数,不能太大,否则规定时间内选不出 Leader。
  7. 轮询检查:后台 goroutine 需要不断轮询检查是否需要发起选举,golang 的初学者最好使用 for loop + sleep 的形式组织代码,不容易出错、且易于调试。当然,你如果是 golang 大师,可以考虑使用 time.Timer 或者 time.Ticker
  8. 如果你的代码通不过测试,可以反复揣摩论文中图 2 中的逻辑。但虽然图 2 给出了所有实现要点,但是并没有按照实现顺序给出,还需要自己组织合理的逻辑顺序以及控制流。
  9. 不要忘记实现 GetState() 函数,否则 tester 没有办法知道选出了 Leader。
  10. 当 tester 结束测试时,会调用 rf.Kill() 设置标记位 rf.dead ,来告诉 Raft 可以退出了。你最好在所有后台线程都去检查该标志位,否则可能会在结束测试时打出一些奇怪日志。
  11. RPC 字段:golang 在进行 RPC 时,只会序列化所有大写字母开头的字段,因此一定要注意在定义 *Args (如 RequestVoteArgs)和 *Reply 结构体的时候,确保所有字段首字母都是大写的,否则没有办法通过 RPC 传到对端 Peer。

到此,你就可以自己写代码做测试了,后面部分是实现部分,建议看到这里后,先自己实现一遍,然后跑测试。哪怕最终做不出来也先趟趟雷,才能带着问题去理解为什么要那么实现。