先这么放着，之后再来补

Lab 4: Sharded Key/Value Service

lab4a: 要求我们基于raft写一个管理raft集群的shardctrler,它能够接收来自客户端的配置更新，支持集群的动态加入和退出，同时还要实时计算各个raft集群应该负责的shards. 当然这里并不负责真正shard的迁移，真正shard的迁移在4b部分，这里只是计算出相应的数据以供4b部分使用。

基本框架和lab3类似，用一个前置分派器来处理来自客户端的请求并根据请求类型来将其分派到对应的handler去处理请求。 每次有raft集群加入或退出时都尝试重新平衡数据分片在各个集群之间的分配情况.重新分配的方法如下:不断尝试将拥有最多分片集群的一个分片移动至拥有最少分片的集群，直到集群中拥有最多分片的分片数比拥有最少分片集群的分片数多1,此时一定处于分片平衡状态(既符合要求的状态)

其余部分和lab3一致。

lab4b: 要求我们在写一个K/V集群, 支持动态扩缩容, 集群内部的负载均衡, 线性一致性以及宕机后可恢复。 总体架构和lab3基本上一样，需要考虑的部分主要是分片在不同raft集群之间的转移

首先要明确，所以对状态机修改的操作必须要集群的leader通过下推修改日志到raft层后才能进行 比如分片的收发应只能由发送方集群的leader发送到接收方集群的leader,然后接后方集群的leader下推一条InsertShard的日志将其传播到自己的集群当中，这样才能满足题目的要求

challeng2中要求各个shard之间互不干扰，所以要将shard这个数据结构抽象出来。具体来说，一个shard应当包含自己存储的数据、当前状态(用于分片的发送与接收)，同时为了保证客户段操作的幂等性，保存各个客户端最后一次请求Id的map也要放在shard当中存储。一个shard的状态有normal(可以给客户端提供服务),sending(该分片需要发给另一个集群),recieving(正在等待其他集群发送这个分片给自己)

分片转移的难点主要在于如何做到不漏发shard。由于在更新配置和分片转移的过程中，发送方和接收方都可能随时挂掉，我们需要保证集群在挂掉重新恢复之后还能正确的处理之前没处理完的分片，所以我们必须保存每个分片当前的状态，然后用一个一直运行在后台的协程不停地根据分片状态去收发shard

每个节点要注册一个shardctrler的client并开启一个go协程去不断尝试拉取最新的config,当拉取到比自己当前config刚好比自己当前的config大一个版本号的时候开始更新分片数据(修改所有shard的状态,然后由分片拉取协程去处理)。注意config的更新需要一个一个顺序处理，在一个节点更新config的过程中，即只要有一个分片还处于待更新状态(recieving状态)，就要禁止拉取更新的config防止覆盖当前状态造成错误，只有在当前config的更新完成后才能去拉取下一个config

由于我们阻塞了config的更新过程，所以每个节点只用保存当前config和上一次config.上一次config用于和最新config比较得出需要进行收发的shard.

分片转移的rpc可以设计成接收方拉取，也可以设计成发送方主动发送。但是如果发送方主动发送的话，由于只能leader接收分片数据，发送方需要向接受方的每个节点尝试发送分片数据，而分片数据较大，这样带来的损耗较大(也可以发送方先询问接受方的leader然后再直接发给leader但这样比较麻烦)。最后我使用的接收方主动去拉取分片的模式，这样，发送方中非leader节点在接收到拉取分片的请求时直接返回Err让接受方尝试另一个节点拉取即可。

当一个节点接收到来自客户端的get/put/append请求时，只要当前分片属于自己这个集群负责并且其状态不是receiving就可以相应这个请求。即challenge2中的配置更新和相应请求可以并行。