MIT 6.824: Distributed Systems- 实现Raft Lab3B

接上文《MIT 6.824: Distributed Systems- 实现Raft Lab3A》,Raft Lab3B要求实现snapshot,避免log不断变大无法继续运作。

Lab3B比之前的Lab都要难,因为论文对snapshot部分的描述非常粗略,对个人Raft理解的要求是比较高的,工程上涉及KV层和Raft层的状态联动,牵扯到的代码变动范围覆盖整个Raft实现,因此需要极为仔细。

我在实现的过程中为了逐步逼近正确代码,首先在Raft层引入了LastIncludedIndex和LastIncludedTerm两个持久化状态,然后将原有Raft逻辑逐步适配上来,不断执行Lab3A单元测试来验证兼容性,最终一次性通过了Lab3B测试。

至此,整个Raft代码的完整实现已经放在了github中,引入Snapshot后整个代码变得复杂了不少,大家可以参考我的实现思路:https://github.com/owenliang/mit-6.824

snapshot实现关键

snapshot包含什么

首先,snapshot除了包含KV层的完整KV Map外,还需要包含Client SeqID Map,这样当leader宕机后安装snapshot后,当继续提交后续log时才能继续保证幂等性(与snapshot被压缩的log之间幂等判定)。

我在KV层使用独立的协程检测raft层log长度,一旦到达阈值则产生一个snapshot并下沉状态到raft层进行log截断等变更:

raft负责将KV传来的snapshot和snapshot的最后index持久化下来,这里注意判断raft log长度时不要加KV锁,否则会出现Raft和KV层死锁。

在这里就可以对snapshot部分的log进行截断处理了,同时注意新snapshot index一定要比原先的snapshot index更大,否则这个snapshot就没必要做了。

判断是否有必要snapshot只需要走Raft层看一下实际序列化后的raftstatesize(也就是log+currentTerm+voteFor加起来的大小),即日志太长就可以snapshot一下了。

raft如何向kv层安装snapshot

当follower收到leader发来的snapshot时,它会保存快照并进行日志截断等处理,然后将日志提交游标重置到snapshot之后,并将将snapshot安装给KV层。

raft层是通过applyChan向kv层安装snapshot的,并且保证此后向applyChan投入的log都是紧随snapshot之后的。

在KV层的apply协程,在原本只能逐条apply log的逻辑基础上,增加一个分支来apply一个snapshot:

安装snapshot后,内存状态被重置,此时相当于lastIncludedIndex之前的日志被提交到KV层,后续继续等待Raft层提交的Log即可。(Raft层会保证snapshot之后紧跟着后续log)

首次启动恢复snapshot

当一个node宕机重启后,是由raft层读取持久化的snapshot,通过applyChan向KV层做首次安装的。

虽然KV层读取applyChan也是协程异步处理的,但是因为我们的KV层无论读写操作都是先写Log等提交后再执行,因此任何读写操作在applyChan内都一定会排到snapshot安装之后,所以首次异步安装snapshot是可靠的。

快照传给KV层后,要更新Raft层的lastApplied索引,强制从snapshot之后的log继续向KV层提交Log。

raft层新增2个snapshot持久化状态

这样node重启后可以知道snapshot的index范围,以便继续向后工作。

降低snapshot带来的逻辑复杂度

raft原先很多地方都用到log长度和最后log的term等信息,在引入snapshot情况下的就得考虑最后一个index是snapshot,另外计算log数组下标也变得复杂,因此获取最后的index和最后的term的逻辑进行了封装:

根据index计算log数组下标:

有这些小函数的帮忙,才能继续改造其他逻辑。

applyLoop提交协程

提交日志到KV层的协程,修改很小,就是取log时候注意下标改成相对值:

这里不需要担心lastApplied位置是snapshot,因为其他关于snapshot处理的逻辑都会保障当snapshot的范围发生变化后一定会调整lastApplied为snapshot之后的位置。

因为snapshot也会向applyCh投递消息,为了保证安装snapshot到applyCh之后投递的Log是紧随snapshot位置之后的log,因此lastApplied状态修改和Log投递必须都在锁内,锁外投递将导致snapshot和log乱序,导致提交时序混乱。

appendEntriesLoop新跳协程

原先该loop只负责向follower同步log,但现在需要增加一个同步snapshot的逻辑。

当发现某个Follower的nextIndex落入了leader的snapshot索引范围内,那么leader就只能向follower 发送snapshot了。

因此,该函数改造成2分叉逻辑:

改造doAppendEntries逻辑

能够进入该函数,说明要同步的nextIndex一定是Log形态。

复杂之处在于,我们需要考虑prevLogIndex恰好是snapshot最后一条log的情况,因此我在实现的时候比较严谨的列出了所有case,确保代码容易解释。

另外nextIndex回退逻辑也需要兼容snapshot,这块主要靠appendEntries服务端做了处理,我们需要考虑prevLogIndex落在folllower自己的snapshot范围内或者恰好在边界上或者在log部分,三种case需要认真处理:

如果要宏观的描述的话,就是如果follower没有能力比对prevLogIndex位置的term是否冲突(prevLogIndex位于follower的snapshot范围内),那么就让leader把自己的snapshot发过来吧(也就是让conflictIndex=1)。

doInstallSnapshot逻辑

其实把snapshot发给follower没啥,就是发过去之后对方接收后,leader下一次nextIndex指向哪里呢?

我考虑把nextIndex指向leader的日志末尾就行,继续通过回退来补全follower的log部分,这样处理最简单最保守。

installSnapshot服务端

follower只接收更长的snapshot,否则没啥意义。

另外需要看一下leader的snapshot和follower的log的关系,看一下该怎么截断,这边case需要想清楚关系。其中如果lastIncludedIndex位置的Log term和snapshot term一样,后续的日志是可以保留的,我理解并不是说后续Log是可靠的,只能说明后续log可能有效的,还是需要leader将nextIndex重置到末尾来回退验证。

最后就是更新lastIncludedIndex和lastIncluedTerm并持久化这些数据,再把snapshot安装给KV层。

其他变化

类似于requestVote、Start等方法都需要逐个检查,兼容一下snapshot带来的下标问题,大概就是这样了。

最后提一个死锁的坑点:

raft层持有rf.mu向applyCh写入可能阻塞,此时如果kv层出现一种代码逻辑是先拿到了kv.mu然后再去拿rf.mu的话,此时肯定无法拿到rf.mu(因为raft层持有rf.mu并阻塞在chan),而此刻kv层如果正在处理前一条log并试图加kv.mu,那么也无法拿到kv.mu,就会死锁。

解决办法就是kv层不要拿着kv.mu去请求rf.mu,一定要在kv.mu的锁外操作raft,谨记这一点即可。

 

如果文章帮助了你,请帮我点击1次谷歌广告,或者微信赞助1元钱,感谢!

知识星球有更多干货内容,对我认可欢迎加入:

MIT 6.824: Distributed Systems- 实现Raft Lab3B》有2个想法

  1. yy

    求问,TestSnapshotRecover3B可以通过,但是TestSnapshotRecoverManyClients3B就过不了,有可能是什么原因呢?找了很久找不到bug,博主有过类似经验吗?

    回复

发表评论

电子邮件地址不会被公开。