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 结构体如下：

1
2
3
4
5


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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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。

还要记得在一个节点刚成为 leader 的时候发送空日志以 apply 旧的日志。

tips：

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

6.824 Lab4

Task

tips：