编号对照：现行课程已改名 6.5840 并重排了 lab——Lab 1 MapReduce、Lab 2 Key/Value server、Lab 3 Raft（3A/3B/3C/3D）、Lab 4 KV Raft、Lab 5 Sharded KV。本文的 Lab4（分片 KV）对应现行的 Lab 5，本文里的 Lab3 是现行 Lab 4、Lab2 是现行 Lab 3。正文中的测试名沿用旧编号。

Task

完成 Multi-Raft

  • lab4A：完成 Multi-Raft 控制中心（和 lab3 内容差不多，一句话来说就是 shardctrler 是一个将 Config 作为日志进行维护的单 Raft 集群，并且不需要实现快照和持久化） 需要注意的地方是执行节点的 Join 和 Leave 操作时 shards 应该怎么平均且有序地分配给 gids（注意在 Leave 操作中，Group 里面可能有多余的 gid，此时需要注意将其算在 gids 里面），主要逻辑和 lab3 差不多，比较简单。

  • lab4B：实现一个拥有分片功能，能够随时加入退出成员，可以根据配置同步迁移数据，支持断线重连日志快速追赶和快照功能并且能够保证线性一致性的 kv 数据库。 虽然叠了很多 buff，但很多地方我们之前已经实现了，比如加入退出成员和日志同步在 lab4A；断线重连和日志快速追赶在 lab2；线性一致性的 kv 数据库在 lab3。

所以我们在 lab4B 的主要任务是根据最新配置来实现分片的处理，进行分片处理和回复客户端的请求都需要通过 Raft 层实现一致性，所以都要调用kv.rf.Start()并启动一个 go routine 处理 Raft 层回调的 applyCh。

首先是 shard，我们需要将 Client 的 PUT、GET、APPEND 请求通过 key 值的 hash 分配给不同的 shard，shard2gid 数组可以通过读取配置获取。为了防止重复 apply，我们要在 shard 结构加上去重表。所以我实现的 shard 结构体如下：

type Shard struct {
	Log         map[string]string
	LastCommand map[int64]int
	Status      int
}

考虑更新 config，leader 需要另起一个 go routine 不断读取新配置，在更新配置之前我们需要判断当前 gid 是否需要 pull 或 push（存下 lastcfg，用来与当前 cfg 作比较）。

func (kv *ShardKV) allSentL() bool {
	for shard, gid := range kv.lastcfg.Shards {
		if gid == kv.gid && kv.cfg.Shards[shard] != kv.gid && kv.stateMachine[shard].Status != Serving {
			return false
		}
	}
	return true
}
func (kv *ShardKV) allReceivedL() bool {
	for shard, gid := range kv.lastcfg.Shards {
		if gid != kv.gid && kv.cfg.Shards[shard] == kv.gid && kv.stateMachine[shard].Status != Serving {
			return false
		}
	}
	return true
}

若需要，则等待相关 shards处理完毕再查询新一个 config（因为步子不能迈得太大，需要一个个 config 地进行状态机的更新，原因之一是更新过程会涉及到 shard 的切换）。

若有一个 gid 需要 push，则另一个就必然需要 pull。无论是用 push 还是用 pull 处理都是可以的。考虑到 Challenge 任务需要在 push 之后删除废弃 shard 释放内存。push 至少比 pull 少一个 RPC 请求，所以我选择了 push。

push 主要是需要发送 RPC 给对应 status 为 pulling 的 shard，并等待 receiver 接受并 apply 回复 OK 后进行 delete。

分片迁移的 RPC 有两点必须做到，否则线性一致性直接崩：

  1. RPC 里必须带 ConfigNum，接收方只接受 args.ConfigNum == kv.cfg.Num 的请求。比自己当前配置小的，说明是一个迟到的重复请求，这批 shard 早就装过了，回 OK 让对方安心删除即可，但不能再装一遍；比自己当前配置大的，说明自己还没推进到那个配置，要回一个错误让对方重试，不能提前装。
  2. 重复到达必须幂等。网络会重传，同一批 shard 的 RPC 到两次是常态。判断依据同样是 ConfigNum——装过一次之后 kv.cfg.Num 已经推进，第二次自然被上面的规则挡掉。注意随 shard 一起迁移过来的还有那个 shard 的去重表（LastCommand），它必须跟着数据一起搬，否则客户端的重试请求换了 group 之后会被当成新请求重复 apply。
  3. 顺带一提，Get/Put/Append 进来的时候要先按 kv.cfg.Shards[key2shard(key)] == kv.gid 判断这个 shard 是不是归自己管，不归就立刻回 ErrWrongGroup 让 Clerk 去问新配置。这个判断在 apply 的时候还要再做一遍——请求入队和真正执行之间配置可能已经变了。

还要记得在一个节点刚成为 leader 的时候发送空日志（no-op）以 apply 旧的日志。这一点和 lab2B 里「lab 中没有需要及时更新旧 commit 的情况」是对不上的：那句话只在纯 Raft 的 lab2 里成立，到了 lab3/lab4，上层要等 apply 才能回复客户端，新 leader 不发空日志就可能一直卡着前任留下的未提交日志，请求直接超时。

tips：

  1. TestConcurrent2 测的是宕机再重启 Service 层不借助 snapshot，用 raft 层的日志快速追赶，然后我的 Get 结果总是与正确答案不一致，表现在前面正确，后面正确，中间缺失。原来是在 shardkv 初始化的时候，cfg 不能初始化为kv.sc.Query(-1)，因为我将 cfg 初始化为最新值，被 Raft 层推到 Service 层的日志在应用在状态机的时候因为 cfgNum 不等于当前的 cfg，所以自动屏蔽掉了（其实这个问题应该不难发现，但我在打 log 的时候没有将 cfgNum 作为 log 头，就没怎么注意到，找了好久。

    2026-08 更新（待核实）：这里的测试名我不太确定。现行 shardkv 的测试里，「配置变更叠加宕机重启」这个组合通常是 TestConcurrent3，TestConcurrent2 更偏纯并发配置变更。我手上没有当年那份 test_test.go，无法核对，所以只标注存疑，不改结论——踩坑的现象和根因（cfg 不能初始化为最新配置）是确定的，跟具体测试名无关。

  2. 需要思考怎么做到 Multi-Raft 的幂等和线性一致性，关键就是上面那三条：ConfigNum 校验、迁移幂等、ErrWrongGroup。