MIT6.824 spring21 Lab2D总结记录

写在前面

lab2D是今年新添加的部分,网上很难找到博客资源。

这一部分要求我们为raft添加log compaction功能:在运行一段时间后,raft的上层service可以生成一个snapshot,并通知raft。在这之后,raft就可以丢弃snapshot包含的log entries,起到节约空间的作用。

这部分难度不大,但是细节略多。

代码见:https://github.com/sun-lingyu/MIT6.824-spring21/tree/Raft-2D

关于CondInstallSnapshot

看过Lab2D实验指导的人都会发现,如果follower收到了一个InstallSnapshot RPC,其处理逻辑是非常扭曲的:

首先,在InstallSnapshot Handler中,follower需要将收到的snapshot通过applyCh发送给上层service。此时follower并会安装这个snapshot。

在一段时间后,上层service会调用CondInstallSnapshot函数,询问raft是否应该安装此snapshot。若在follower执行InstallSnapshot Handler到执行CondInstallSnapshot的这段时间里,raft没有因为收到applyentries RPC导致其commitID超过该snapshot。

在什么情况下CondInstallSnapshot会拒绝安装snapshot?

当然,出现“CondInstallSnapshot拒绝安装snapshot”这种情况,是可以理解的。下面给出一种可能的情况:

leader的当前状态如下。图中的直线代表leader的log,且假设所有的log entry都已commit。

leader向其中一个落后的follower发送appendEntries RPC。其中包含了从nextIndex直到log末尾的所有entry。

MIT6.824 spring21 Lab2D总结记录

 

 

 由于种种原因(不稳定的网络或follower fail),这个包并没有及时被follower接受。

接下来,leader的上层应用调用Snapshot(),对leader的log进行压缩:

MIT6.824 spring21 Lab2D总结记录

如图,这个snapshot可能超过了nextIndex。因此,当leader试图重发刚刚的appendEntries时,它将只能发送整个snapshot给follower。

若由于网络波动,follower首先收到了snapshot,它将执行InstallSnapshot RPC。

若在它还未执行CondInstallSnapshot时,它收到了先前发送的appendEntries,并commit,那么在执行CondInstallSnapshot时,它将拒绝安装此snapshot。

为什么InstallSnapshot RPC的处理逻辑这么扭曲?

论文中对InstallSnapshot 的描述远比实验指导中简单:论文中甚至根本没有提及过CondInstallSnapshot。

那么我们为什么需要CondInstallSnapshot?为什么不可以在InstallSnapshot RPC handler中直接安装snapshot?

实验指导中给出的答案是:这样可以确保service与raft安装snapshot的原子性。

如果你对Lab2B的实现还有印象,就会发现:这个问题的答案与我们的实现高度相关。

 

让我从“如何向applyCh发送log entry”讲起:

在我的Lab2B实现中,向applyCh发送log entry的时机有两个:

1. appendEntries RPC handler中,发现commitIndex需要更新之后

2. leader appendEntries RPC receiver中,commit新的log entry之后

在这两个发送时机,执行发送的goroutine都是持有锁的。

如果在向applyCh发送任何信息时,总持有锁,那么可以保证raft与上层service的通信是严格串行的。(没有任何不确定性)

那么如果在InstallSnapshot RPC handler中,向applyCh发送snapshot时也持有锁,就也可以保证service与raft安装snapshot的原子性。

即:service可能滞后一段时间,但是其正确性可以保证。

这样一来,似乎可以在InstallSnapshot RPC handler中直接安装snapshot。

 

但是:这个过程涉及了一把锁与一个blocking channel。一旦处理不当,将导致死锁

虽然在2B/2C中,这样的实现不会产生问题。这是因为raft的上层service一定会及时读取applyCh。

但是在2D中引入Snapshot函数后,这种机制将导致死锁!

在实验提供的service代码中:当上层service从applyCh中收到了一定数量的log entry后,它将执行Snapshot函数,使raft压缩其log。在Snapshot函数返回前,上层service不会向下执行。

执行Snapshot函数需要获取锁。若此时有goroutine正在持有锁并试图向applyCh中发送log entry,则会发生死锁。

因此,Frans Kaasoek教授在讲解2A/2B时,特意提到不要在向applyCh发送log entry时持有锁。在他的实现中,向applyCh发送是采用一个专门goroutine执行来确保串行的。(我发现2B/2C的testcase都能过,就没当回事

上一篇:原创-阿里elasticsearch数据迁移


下一篇:Oracle等待事件之buffer busy waits