【公开课】MIT 6.824 Lab 3（容错 kv）

设计要求

整个任务要求基于 Raft 构建一个可以容错的 Key/Value 存储服务。细分为如下两个具体的任务：

• Part A：Key/value service without log compaction
• Part B：Key/value service with log compaction

Part A

交互流程

整体的交互流程如下：

• Client 找到集群中的 Leader，发送操作命令 Put/Get/Append 给 Leader，并等待 Leader 返回执行的结果。
• Leader 通过底层的 Raft 协议把命令日志复制到其他的节点上。
• 等到集群内超过半数的节点都完成了日志的复制，Leader 执行这个命令，并且将结果返回给 Client。

在前面我们已经实现了一个可用的 Raft 协议，我们在这个任务中主要使用 Raft 提供的接口。

func (rf *Raft) Start(command interface{}) (int, int, bool)

Client

Client 的设计采用了以下的思路：

• 保证每个操作仅仅执行一次，因此需要一个唯一的编号表明每个客户端的操作。
• 保证客户端每次只发送一个请求给服务端，可以通过加锁实现。
• 记录当前服务端的 Leader 编号，下次访问的时候直接访问记录的 Leader，节省了寻找 Leader 的时间。

Client 的结构设计如下：

type Clerk struct {
	servers []*labrpc.ClientEnd
	serial   int
	clientId int64
	leaderId int
	mu       sync.Mutex
}

当 Client 向 Server 发送 RPC 请求时，需要给每个 RPC 请求一个唯一的编号，Server 根据 Client 编号和 RPC 编号验证当前指令是否已经执行过了，保证指令的唯一执行。

Server

Server 端接收到了 Client 发送的指令后，需要通过底层的 Raft 库完成以下的事情：

1. 主节点把命令复制到 Raft 日志中（通过 Raft 的 Start 函数），并且等待 Raft 日志已经在集群超过一半的机器上成功复制完成，并且完成最终的提交工作。
2. Server 接收到 Raft 库提交的日志，执行日志中的命令。

为了保证整个系统的行为是线性一致性的，Server 端需要有一个在后台运行的 apply goroutine，接收 Raft 系统提交的日志，并且执行日志的内容。所有客户端发送的命令都必须提交到 Raft 系统中，等待复制过程结束了才能执行命令的操作。

所有类型的操作都需要按照上面的过程执行，包括 Get() 操作，这种做法可以保证系统不会读到 KV 系统中的过期值。

如果 Client 发送了命令之后，Server 端的主节点变了，那么该如何处理？根据 Guide 的提示：

Once the operation at that index is sent to apply(), you can tell whether or not the client’s operation succeeded based on whether the operation that came up for that index is in fact the one you put there. If it isn’t, a failure has happened and an error can be returned to the client.

我们可以通过 index 完成 Leader 变更的判断，具体的执行思路如下：

通过 Start() 的返回值，我们可以得到一个和该命令关联的 index。我们为每一个 index 创建一个 channel，用于返回 Raft 库在这个 index 上提交的命令。Client 在该 channel 上等待返回的命令，判断返回的命令和字节发送的命令是否相等。这会造成以下两个结果：

1. 相等。说明命令执行完毕，返回 OK。
2. 不相等。说明主节点发生了变更，Client 需要重新发送命令给新的 Leader。

Part B

Part B 的任为根据 Raft 论文的内容实现基于内存的快照机制，需要阅读论文第 7 章了解整体的运行流程。

快照机制可以减少 Raft 系统日志的大小，这么做的好处有以下几点：

1. 减少了存储 Raft 快照需要的空间。
2. 减少日志存储的数量，加快了 Raft 节点崩溃恢复的速度。

整体流程

快照机制的运行流程如下：

1. 复制状态机（此处是 Server）检查日志的大小，判断是否需要执行保存日志的操作。
2. 如果需要执行保存日志的操作，Server 调用 Raft 库提供的接口保存快照，截断日志。
3. 在系统启动的过程中，从快照恢复系统的初始状态。

快照机制还存在一个问题：如果主节点需要通过 ApplyEntries() 发送自己的日志给从节点，但此时日志已经被截断，无法发送。为了解决这个问题，Raft 作者提出了一种新的 RPC 请求：InstallSnapshot()，用于发送主节点的快照，解决了主节点发送已被截断日志的问题。

InstallSnapshot

InstallSnapshot 的整体流程见下图。

在本项目的实现中，Snapshot 在一个 RPC 中全部传输完毕，不需要执行分块传输。

Raft 的 Snapshot 机制在快照大小比较小的时候，是一种比较有效的手段。但是，如果快照的大小过大（达到了 GB 级别，这种情况在实际应用中很常见），该如何处理？有以下可能的方法：

• 把数据存储在磁盘上。
• 延迟删除 log 日志的内容。
  这些思路可以参考作者在博士论文中的内容。

参考

• extended Raft Paper
• Student Guide