Sharded Key/Value Service

6.824 的 LAB 4 的内容是构建一个分片的分布式 KV 存储系统。分片是 Key/Value 对的子集。例如，所有以 “a” 开头的 Key 可能是一个分片，所有以 “b” 开头的 Key 可能是另一个分片。分片的目的是获取更好的性能，每个副本组只负责几个分片的 puts 和 gets，当访问的分片处于不同的副本组时，这些操作就可以并行地执行。因此，系统的总吞吐量与副本组的数量成正比。

分片 KV 存储系统包括两个主要组件：

• 一组副本组。每个副本组负责分片的一个子集，并由少数使用 Raft 复制分片的服务器组成；
• 分片控制器。分片控制器决定一个副本组负责哪些分片，这个信息被称为配置。客户端询问分片控制器找到 Key 对应的副本组，副本组询问分片控制器找到要服务的分片。整个系统有一个单一的分片控制器，使用 Raft 作为容错服务实现。

LAB 4 实验的主要挑战将是处理重新配置——将分片分配给副本组的更改。在一个副本组中，所有的服务器必须就何时应用新的配置达成一致。例如，Put 可能与重新配置同时到达，导致副本组不再负责对应的 Key。副本组中的服务器必须就 Put 发生在重新配置之前还是之后达成一致。如果之前，Put 应该生效，分片的新所有者应该看到它的效果；如果之后，Put 将不会生效，客户端必须在新所有者处重新尝试。

重新配置还需要副本组之间的交互。例如，在配置 10 中，副本组 G1 可能负责分片 S1。在配置 11 中，副本组 G2 可能负责分片 S1。在从 10 到 11 的重新配置过程中，G1 和 G2 必须使用 RPC 将分片 S1 从 G1 移动到 G2。

LAB 4A

LAB 4A 的内容是实现分片控制器，支持添加新的副本组、清除副本组以及在副本组之间移动分片。LAB 4A 的实现非常简单，除了没有使用快照之外，跟 LAB 3 的实现非常相似。

需要注意的是，当创建新的配置时，不要把之前的配置的 Groups 赋值给新的配置（因为 Groups 是引用类型），实现完后跑一下测试：

LAB 4B

LAB 4B 的内容是实现分片 KV 存储系统，为使用客户端接口的应用程序提供可线性化的接口。也就是说，对 Get、Put 和 Append 方法的完整应用程序调用必须以相同的顺序影响所有副本。 Get 应该看到最近的 Put/Append 写入到同一个 Key 的值。即使 Gets 和 Puts 与配置更改几乎同时到达，也必须如此。

每个 shardkv 服务器都作为副本组的一部分运行。每个副本组为某些分片的 Key 提供 Get、Put 和 Append 操作。

Hint

我写完第一版代码后只通过了前面三个测试，第四个测试一直报错 Get 操作返回了错误的值。我反复检查了代码都没找到什么问题，于是就去仔细看了一下实验给的提示，终于发现了问题的所在。

提示里面给出了非常关键的信息：”Process re-configurations one at a time, in order.”，即应该按照顺序一次处理一个重新配置。在我之前的实现中副本组的 Leader 以100MS的频率向分片控制器询问最新配置，如果配置号大于当前的配置，那么就开始进行分片迁移，在分片迁移完成后进化到新的配置。但这样是有问题的，假设有如下的场景：

Server 1 和 Server 2 初始状态都是配置1，此时 Server 2 向分片控制器询问最新的配置，分片控制器返回了配置3。Server 2 根据配置3向 Server 1 发送分片2的请求，但是 Server 1 不拥有分片2，于是 Server 1会返回空数据或者无用的垃圾数据，Server 2 会把返回的垃圾数据保存起来，之后如果有客户端向 Server 2 发送 Get 请求，那么 Server 2 就会返回错误的值。

原因是副本组没有按照顺序处理重新配置，Server 2 不应该跳过配置2直接到达配置3，而是要先到达配置2，再到达配置3。

但即使这样还需要额外的判断才能保证正确性，假设副本组按照顺序一次处理一个重新配置，有如下的场景：

Server 1 初始状态是配置1，Server 2 初始状态是配置2。此时 Server 2 向分片控制器询问最新的配置，分片控制器返回了配置3。Server 2 根据配置3向 Server 1 发送分片2的请求，但是 Server 1 不拥有分片2，于是 Server 1会返回空数据或者无用的垃圾数据，Server 2 会把返回的垃圾数据保存起来，之后如果有客户端向 Server 2 发送 Get 请求，那么 Server 2 就会返回错误的值。

原因是 Server 2 的配置高于 Server 1，Server 1到达配置2后才会拥有分片2。因此当一个 Server 接收到请求分片的 RPC 时，需要先判断请求分片的配置号是否高于本服务器当前的配置，如果高于则返回一个错误提示告诉对方你要求的分片的配置太高了，否则就可以安全地把分片发送给对方。

Bug

再说一说在实现 LAB 4B 的过程中遇到的一个小 Bug。在我的之前的实现中，每当服务器返回一个分片给请求方时，都会直接把这个分片对应的 GID 设置为0，表示不再拥有这个分片：

func (kv *ShardKV) doShard(command *Op) NotifyMsg {
	// ....
    // ....
	for _, shard := range command.Shards {
		// ....
        // ....
		kv.config.Shards[shard] = 0
	}

	return notifyMsg
}

但这样做是有问题的，假设有如下的场景：

Server 1 已经到达了配置2，Server 2 到达了配置1。此时 Server 2 向分片控制器询问最新的配置，分片控制器返回了配置2，Server 2 根据配置2向 Server 1 发送分片1的请求，Server 1就把分片1的数据返回给 Server 2，并直接把 kv.config.Shards[1] 设置为0。

那么问题来了，当 Server 1 想要到达配置 3 时 需要分片1的数据，但是 Server 1已经把 kv.config.Shards[1] 置为0了，因此 Server 1 无法知道现在是谁拥有分片1。

解决方法很简单，加一个额外的判断即可：

if kv.config.Shards[shard] == kv.gid {
	kv.config.Shards[shard] = 0
}

如果 Server 1 已经到了配置2，则不把 kv.config.Shards[shard] 设置为0。

Challenge 1

挑战1是垃圾状态收集，即当一个副本组失去对分片的所有权时，副本组应该把相应的分片数据删除。

最简单的办法是，在一个副本组返回分片给请求者后就立马把这个分片的数据删掉。但这样是有问题的，由于网络的不可靠性，请求者可能没有收到返回的分片数据，之后这个请求者就会重试，但此时副本组已经把这个分片删掉了，请求者不可能再拿到这个分片了。

解决方案是，副本组返回分片给请求者后不立即删掉这个分片。在请求者设置好分片后，再发送消息给分片的原来的持有者：告诉它这个分片我已经拿到了，你可以把这个分片的数据删掉了。这样副本组就能安全地删除掉分片了。

当然，这里面还有一些细节性的判断，这里就不再赘述了。

Challenge 2

挑战2是在配置更改期间能够处理客户端请求：

• 在配置更改期间，如果一个分片没有收到影响，那么发送到这个分片的请求能够继续执行；
• 在配置更改期间，当副本组收到它需要的一个分片时，这个副本组可以立马为这个分片提供服务。

第一个问题很简单，只要不在配置更改期间禁用客户端请求就可以通过这个测试。

对于第二个问题，解决方案是：在副本组得到一个分片后，就创建一个设置分片的操作提交到 Raft 中，当这个操作被复制到多数节点后，就执行这个操作，把分片保存到服务器状态中，之后就可以为这个分片提供服务了。这样就不需要等待到达新的配置就可以为新的分片提供服务了。

解决完所有的 Bug 并实现两个挑战后，跑一下测试：

难度排序

终于把 6.824 的所有 LAB 都做完了，结合我自己实现 LAB 的经历给这4个 LAB 的难度做一个排序吧：

1. LAB 2。LAB 2 的难度最高，我认为主要是比较难 Debug，测试报错后很多时候都有上万行的日志，除了看日志以外没有什么好的 Debug 方法。我在做 LAB 2A 的时候参考了 Github 上的一个 Raft 的开源实现，主要是看一下需要定义哪些字段和方法，因为我刚开始做的时候完全不知道从哪儿下手😥。然后 2B、2C、2D 都是我完全独立完成的；
2. LAB 4。LAB 4 的难度比 LAB 2 的难度低一点，但是远高于 LAB 3 和 LAB 1 的难度。LAB 4A 和 4B 的所有内容都是我自己独立完成的，包括 4B 的最后两个挑战练习。LAB 4 的第一版代码我很快就写完了，但是只能通过前3个测试，直到看到 “Process re-configurations one at a time, in order.” 提示才直到自己哪儿错了，之后只改动几行代码就通过了前面的测试。再之后就慢慢地想要怎么实现最后的两个挑战练习，经过思考后也是顺利地完成了代码；
3. LAB 3。LAB 3 的难度本来挺低的，但是我在 LAB 3A 卡了接近一天，原因是我把 LAB 3 的架构搞错了（具体可见之前的文章），我看了一下别人的实现思路后才知道自己竟然犯了这么低级错误，之后改了10来行代码就通过所有测试了ヽ(✿ﾟ▽ﾟ)ノ；
4. LAB 1。LAB 1 的难度最低，我感觉 LAB 1 就相当于这门课的热身练习，实现逻辑比较简单，也没有什么复杂的交互，Debug 也比较简单。

参考

• MIT 6.824