03. Raft PartA 领导者选举
实现要求
实现 Raft 选举和心跳逻辑(即不带日志条目的 AppendEntries)。本部分仅要求实现:
- 选出唯一的领导者,领导者选出后会持续进行心跳避免其他人发起选举
- 旧的领导者宕机或者网络故障无法触达时,选出新的领导者
PartA 并不需要实现日志同步逻辑,连带着在收到选举请求时,也都先忽略比较日志新旧的逻辑。
写完后在 src/raft 文件夹,使用 go test -run PartA -race 来测试代码逻辑是否正确、是否有数据竞态。
实现要点
下面罗列下实现概要:
- 遵照论文图 2 进行实现,但当前只需要关心收发
RequestVote请求、选举相关的规则和状态转换 - 选举逻辑:填充
RequestVoteArgs和RequestVoteReply结构体。修改Make()函数,在创建 Raft Peer 的时候,创建超时检测、发起选举的后台 goroutine。实现RequestVote()回调函数,以在 Leader 要票时进行投票。 - 心跳逻辑:为了保证 Leader 当选后压制其他 Peer 再次发起选举,你需要定义
AppendEntriesArgs和AppendEntriesReply结构体,但暂时并不需要填充字段,因为 PartA 你并不需要实现日志同步逻辑。只需要实现AppendEntries()回调函数,在收到AppendEntriesRPC 请求时,重置选举计时器即可。 - 随机超时:论文中着重强调了,为了避免“活锁”——每个人都不断地选自己,需要让选举超时是随机的。可以使用 golang 的 rand 包来制造随机超时。
- 测试限制1:测试代码要求 Leader 每秒不能发超过几十次的心跳 RPC,也即你的心跳间隔不能太小。论文中的 5.2 小节提到过选举超时可以选取 150ms ~ 300ms 的超时间隔,这意味着你的心跳间隔不能大于 150ms(否则不能压制其他 Peer 发起选举)。当然,你可以不按照论文来,适当调大选举超时范围,但也不能太大,原因见下一条。
- 测试限制2:测试代码要求在多数节点存活时,必须在 5s 内选出 Leader。需要注意的是,即使多数节点都存活,也不一定在一个轮次的选举 RPC 就能选出主(比如很小概率的有两个 Peer 同时发起选举并造成平票),因此要仔细选取选举超时参数,不能太大,否则规定时间内选不出 Leader。
- 轮询检查:后台 goroutine 需要不断轮询检查是否需要发起选举,golang 的初学者最好使用 for loop + sleep 的形式组织代码,不容易出错、且易于调试。当然,你如果是 golang 大师,可以考虑使用
time.Timer或者time.Ticker。 - 如果你的代码通不过测试,可以反复揣摩论文中图 2 中的逻辑。但虽然图 2 给出了所有实现要点,但是并没有按照实现顺序给出,还需要自己组织合理的逻辑顺序以及控制流。
- 不要忘记实现
GetState()函数,否则 tester 没有办法知道选出了 Leader。 - 当 tester 结束测试时,会调用
rf.Kill()设置标记位rf.dead,来告诉 Raft 可以退出了。你最好在所有后台线程都去检查该标志位,否则可能会在结束测试时打出一些奇怪日志。 - RPC 字段:golang 在进行 RPC 时,只会序列化所有大写字母开头的字段,因此一定要注意在定义
*Args(如RequestVoteArgs)和*Reply结构体的时候,确保所有字段首字母都是大写的,否则没有办法通过 RPC 传到对端 Peer。
到此,你就可以自己写代码做测试了,后面部分是实现部分,建议看到这里后,先自己实现一遍,然后跑测试。哪怕最终做不出来也先趟趟雷,才能带着问题去理解为什么要那么实现。
评论
