写在前面

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。

 

 

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

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

如图，这个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都能过，就没当回事