MIT6.824-Raft
这个寒假可算把搁置许久的Lab02给做完了。之前一直被卡在Test 2B的一个case里,寒假时候重新看看大佬们的实现思路,可算是完成了所有内容,于是简单记录一下。
算法简介
共识算法的基础是复制状态机,即按照相同顺序执行相同的确定性指令最终必然达到一致状态。Raft是一种代替Paxos的分布式共识算法,相比Paxos更利于学习与理解。
Raft算法核心内容可以分为三个部分: $Leader Election + Log Replication + Satety$ 。
集群机器初始为Follower,一旦一定时间内未接收到来自Leader的心跳,机器将成为Candidate并触发选举,请求剩下Follower投票。获得半数以上选票的Candidate成为Leader。
Raft是一种强领导人的强一致性的分布式共识算法,它使用Term作为逻辑时钟,一个任期中只能有领导人。领导人需要周期性发送心跳以维护其地位,同时需要处理复制提交日志。
复制日志时,Leader首先将日志复制到其他Follower上,直到半数以上的Follower成功复制,Leader才会提交此日志。
安全性主要有五个部分,与实现相关的最核心的内容我认为有两个。一个是领导人只追加原则,不允许修改已提交的日志;另一个是选举安全性,避免脑裂问题,同时保证新Leader拥有比较新的日志。
剩下的其他内容请参考论文原文。
实现思路
实现的思路大体上是参考了一篇大佬的博文(见参考),算法的细节很多也在原Paper的Figure2中,故而以下只讲一下实现各个功能时需要注意的地方。
领导人选举
发起选举+选举结果处理
发起选举是会开启多个goroutine后台发送RPC请求到其他结点,所以处理RPC response的时候需要确定当前结点为Candidate,以及请求未过期,即rf.state == Candidate && req.Term == rf.currentTerm
。选举成功需要立即发送心跳,通知其他结点选举结果。
如果发现失败的Responseresp.Term > rf.currentTerm
,此时需要切换到Follower状态,更新任期,并重置投票信息。
实际上一旦更新了任期,就需要重置投票信息。如果不重置votedFor信息,会有一些测试通过不了
请求投票RPC
前置逻辑过滤过期req.Term < rf.currentTerm
以及当前任期的重复投票请求。之后再按照算法描述的逻辑处理,注意如果成功投票,需要重置选举计时器。
在 grant 投票时才重置选举超时时间,这样有助于网络不稳定条件下选主的 liveness 问题
状态切换
注意在切换角色时处理不同的计时器状态(stop or reset),切换到Leader时需要重置matchIndex以及nextIndex的值。
日志复制
Raft算法的核心,需要注意的地方最多。
我的实现是使用多个replicator和applier线程异步复制和apply的方式。
日志复制RPC
前置逻辑过滤掉req.Term < rf.currentTerm
过期的请求。之后处理日志不一致以及日志被压缩以及重复日志的情况,之后复制日志再处理commitIndex
。
发起日志复制+请求结果处理
发起日志复制需要判断是直接复制日志或者发送快照。
请求结果处理重点是如何处理matchIndex
和nextIndex
以及commitIndex
。
matchIndex
用来记录其他节点成功复制的最新日志,nextIndex
是记录发送给其他节点的下一个日志。commitIndex
通过排序matchIndex
来更新。再决定是否需要触发applier更新appliedIndex
。
请求失败则可以回退nextIndex或者切换到Follower状态。
异步Apply
实际上就是一个后台goroutine,通过条件变量控制,使用Channel通信。每次触发会把log[lastApplied:commitIndex]
发送给上层,并更新appliedIndex
。
持久化
在需要持久化状态的属性更新时及时的刷盘。
安装快照
主要就是Leader触发的Snapshot以及RPC。应用Snapshot的时候需要先判断其新旧以及更新log[0]
和appliedIndex
以及commitIndex
。
坑
Defer
首先是Golang的defer关键字。我比较喜欢在RPC开头使用defer关键字直接打印出结点的一些数据:defer Dprintf("%+v", raft.currentTerm)
,这样在调用结束时能打印出log,但实际上,在运行到defer这一行的代码时,打印的内容已经固定。正确的使用方式应该是defer func(ID int) { Dprintf("%+v", id) }()
Log Dummy Header
Log处最好预留一个位置用于存放快照保存的Index和Term,不然Snapshot那部分的重构很痛苦。
Lock
参看guidance的用锁建议。使用一个大锁,而不是用多个锁。算法的正确性比性能重要。在发送RPC以及使用Channel时不要加锁,不然可能会超时。