6.824

一个多月没写博客了。是因为入了大名鼎鼎的巨坑——6.824分布式系统的lab。整整一个月爆肝，现在终于写完了，开心。目前Lab4-ShardKv测试了5000次，但也不保证bug free。

我个人的时间分布

（不太准确，中间有的时间可能摸鱼了，比如中秋节）

• Lab1-MapReduce：2天左右（8月28通过）
• Lab2-Raft：共16天
  • 2A：3天左右（8月31通过）
  • 2B：5天左右（9月5通过）
  • 2C：2天左右（9月7通过）
  • 2D：6天左右（9月13通过）
• Lab3-KVRaft：共3天
  • 3A：1天左右（9月14通过）
  • 3B：2天左右（9月16通过）
• Lab4-ShardKV：共12天
  • 4A：3天左右（9月19通过）
  • 4B：5天左右（9月25通过）
    • Challenge1+2：4天左右（9月29通过）

结合个人感受以及时间分布，我认为Lab4B和Lab2D最难。Lab2具体做法都有参照，而Lab4则比较“自由发挥”。大部分时间都在盯着屏幕阅读log进行“happy” debug，而修bug是非常琐碎的过程，无法形成系统的知识，就不往博客里面写了。这篇博客我主要还是想讲一讲我Lab4B的做法。我做的是2022年的Lab。根据Collaboration Policy，代码我就不公开了。

介绍

Lab3是将数据分布到不同机器上，增加了Fault Tolerance，即便有一部分机器挂了，也能继续运行。但是对不同Key的操作要通过相同的Leader进行Start，直到commit。因此速度与单机相比没有提升（甚至由于存在commit操作，反而更慢了）

而Lab4在Lab3的基础上，将Key分散到各个ReplicaGroup（RG）上。不同RG管理不同的Shards，让不同Key的请求可以同时进行，从而提高performance。

先介绍一些概念：

• Shard（S）：代表一个key-value pair子集。比如‘a’开头的key都在同一个Shard中。（在Lab中，Shards数量是10）
• Replica Group（RG或G）：负责一部分Shards（比如前三个Shards）的机器集群，每个都对应一个Raft集群来保证一致性。
• Shard Controller（SC）：负责分配RG与Shard的对应关系configuration（Config或C）。这个关系会随时间变化。SC集群只有一个，通过raft支撑一致性。
• Client请求的流程：通过SC得知key对应的Shard对应的RG，然后去问RG。

Shards需要在不同的RG之间进行多次迁移。其目的：workload balance，或者因为存在新增或删除RG的操作。

因此，挑战是在迁移的过程中，依旧要保持数据一致性。推荐将reconfiguration与数据操作Op同时加入到raft的log中。

我们忽略Raft层面的细节，并且不用管Lab4A：Shard Controller（SC）。

思考过程

首先我们需要弄清楚机器有哪些操作。

RG为单机

先将RG简化为单机（不考虑Raft），我们应该如何实现它的各种操作？

假设我们Data保存了所有Shard的数据，也保存了历史中经过的所有Config的Data。

• 【收到Get，Put，Append】数据操作：根据自己的Config，检查key对应的Shard是否正确，然后进行正常操作就行
• 定时去SC那查询最新的Config，如果查询到比自己更新的Config
  1. 更新自己的Config
  2. 比较负责的Shard的变更：
     • 如果之前没有负责S，现在需要负责S，则需要找到之前负责S的RG，发送GetShard请求【发送GetShard】。在收到GetShard回复之前，都不能处理其对应S的请求。收到GetShard回复之后，更新自己的数据。自己拿到数据之后，让之前负责的RG删除数据【发送DeleteBefore】。
     • 如果之前负责S，现在不需要负责S了。等待其负责的RG找我来GetShard，在回复之前都可以继续负责S。
• 【收到GetShard】如果收到RG发过来的GetShard请求，说明自己一定在那个Config中在负责此Shard
  • 我有请求的Shard，则返回，并且停止处理S。
  • 有可能我现在也没有拿到Shard，但是我一定会拿到，所以让其等待一段时间后重试
• 【收到DeleteBefore】删除之前的数据。

RG为多机

多机在单机的基础上，添加：Data与Config的更新操作需要让所有机器执行。与单机不同的地方用#表明。

• 【收到Get，Put，Append】数据操作：根据自己的Config，检查key对应的Shard是否正确，然后进行正常操作就行
• 定时去SC那查询最新的Config，如果查询到比自己更新的Config
  1. ####【发送UpdateConfig】####，从而更新自己的Config
  2. 比较负责的Shard的变更：
     • 如果之前没有负责S，现在需要负责S，则需要找到之前负责S的RG，发送GetShard请求【发送GetShard】。在收到GetShard回复之前，都不能处理其对应S的请求。收到GetShard回复之后，更新自己的数据，####【发送UpdateData】####。自己拿到数据之后，让之前负责的RG删除数据【发送DeleteBefore】。
     • 如果之前负责S，现在不需要负责S了。等待其负责的RG找我来GetShard，在回复之前都可以继续负责S。
• 【收到GetShard】如果收到RG发过来的GetShard请求，说明自己一定在那个Config中在负责此Shard
  • 我有请求的Shard，则返回，并且停止处理S。
  • 有可能我也没有拿到Shard，但是我一定会拿到，所以让其等待一段时间后重试
• ####【收到UpdateConfig】####，更新自己的Config。
• ####【收到UpdateData】####，更新自己的Data。
• 【收到DeleteBefore】删除之前的数据。

操作如何执行

接下来我们需要弄清楚这些操作要在什么时候执行，由谁来执行。

1. 【收到Put，Append，UpdateConfig，UpdateData，DeleteBefore】以及【收到GetShard：修改Config来停止处理对某些Shard的请求】。这些属于RG的状态变化，需要所有机器执行。通过Raft的applyCh来给所有Server发，在每个Server apply命令的时候执行。

2. 【收到Get，GetShard】。这些属于读取RG的状态。需要让收到请求的机器在得知命令commit之后，自己执行。需要用Raft来保证Linearizable。对于GetShard来说，在apply的时候需要额外修改config来停止对某些Shard的请求。

3. 【发送UpdateConfig，发送GetShard，发送UpdateData，发送DeleteBefore】。属于自己作为客户端来发送请求。

   他们只需要其中一个机器去发送请求，因此不属于1类，并且执行过程中可能block，不能让他们影响正常的apply过程（容易死锁）。这些操作需要自己来触发，没有外部请求来触发，因此也不属于2类。所以，最简单的做法是将其作为两个单独的定时任务：

   1. （定时）找SC拿最新Config，如果需要更新，触发【发送UpdateConfig】

   2. （定时）从旧往新遍历所有Data中所有历史Config，所有Shards，看是否存在需要【发送GetShard】，如果收到正确回复，再【发送UpdateData】与【发送DeleteBefore】

   我觉得这么做没问题，但是我实际没有实现ii，因为Data在大部分时间都不需要GetShard，只有在Config更新之后才需要，如果作为定时任务，可能比较耗时。

   我的做法是：在UpdateConfig命令Apply的时候，让Leader去异步执行ii。由于Log中记录了UpdateConfig命令，因此，每次Backup的时候也会重新执行ii。

为什么不能将这两个简单合并为一个定时任务

可能有问题的做法：定时去SC那拿最新Config，如果要更新，就触发【发送UpdateConfig】，然后遍历所有Data中所有Shard所有历史Config，看是否存在需要【发送GetShard】，如果收到正确回复，再【发送UpdateData】与【发送DeleteBefore】

如果【发送UpdateConfig】成功了。Config更新之后被Killed了，没来得及完成【发送GetShard】。假设之后没有新Config，于是之后就不会再触发【发送GetShard】了。这块Shard一直无法拿到，也就无法处理数据请求。

---

如何找到之前负责S的RG

RG拿到新的Config，发现需要负责某个S，怎么找到之前负责该S的RG呢？注意Config的更新之间可能会跳过一些Config。我尝试了两种做法。

一级级往前问，找到谁拿着最新的S

（通过1280次除Challenge1之外的4B，但是大概率还有bug，只是提供另一种思路，并且这种方式我不知道怎么实现Delete历史数据，所以Challenge1过不了）

1. 发送GetShard：UpdateConfig后，查询之前的Config，给之前可能会负责的RG发送GetShard，如果回复ErrNoResponsibility则继续向上一级询问。
2. 收到GetShard：
   • 如果Request的Config大于当前我的Config，说明我还没有负责，停止对S的操作（直到我的Config大于Request的C），返回ErrNoResponsibility。
   • 如果Request正好是当前的Config，则停止对S的操作，并返回当前的Data。
   • 如果Request小于当前的Config，则查询历史Data，如果有则返回，否则ErrNoResponsibility（这里可能还有问题）。

举个例子：假设S的负责过程如下，假设我们是G3，拿到最新的C4，而最新的S在C1的G1手中

C0: 0
C1: G1 // S
C2: G2 // -> ErrNoResponsibility
C3: G1 // -> ErrNoResponsibility
C4: G3 // G3

首先G3向上一级C3的G1问是否有S，G1回复不负责，G1停止处理S的数据请求（直到收到比C4的G3更高的Config）。由于没问到，G3再向上一级C2的G2问，G2同意不负责，G2停止处理S的数据请求。G3再向上一级C1的G1问，负责，并返回此时的S。

保证每个C中负责S的RG都要拿到S（Step-By-Step）

通过5000次4B包括Challenge，感觉这个实现起来更容易一点。思路：

1. 发送GetShard：UpdateConfig后，只查询上一级的Config，并给对应RG其发送GetShard，直到GetShard成功返回。
2. 收到GetShard：如果有数据，则返回，否则让其等待后重试（避免互相发导致死锁）。

调试中的琐碎细节

Reconfiguration

• 历史Config不会变化，因此可以给Configs缓存，减少与SC之间的RPC数量
• Client调用需要server名字，但要更新的Config中不一定包含该RG，因此需要查询历史Config去寻找
• GetShard的重试时间可以设置为随机时间减少互相发GetShard导致死锁的可能

Applier

• commitIndex需要包括所有apply的命令，包括那些重复的，WrongGroup的命令。不然可能出现Snapshot不减少Log长度的情况。
• GetShard在apply的时候，停止后续对某些Shard的处理，仅将config.Shard改为-1还不够。需要提示出直到什么configNum才能继续处理。
• Step-By-Step的做法带来的性质：如果C中的S全部完成交接，则C之前的S也一定全部完成了。因此在“从旧往新遍历所有Data中所有历史Config”之前，可以先从新往旧遍历，找到交接完成的最后一个C，从那之后进行GetShard。
• 去重相关的map也需要随data一样，切分为不同的Shard，同时也需要在GetShard中进行传输

Client

• 不同的RG各自需要一套request ID来去重。

• 在Challenge2中，要求Config更新后，集群需要在1秒内完成所有GetShard的操作，因此我们可以降低集群内RPC的ErrLeader重试时间（本来是100毫秒，可能几次重试就超时了）。

• 需要注意不论是SC的Client还是ShardKV的Client，都存在并发请求的时候（SC的Query，ShardKV的内部请求）。不要直接锁住整个RPC调用。

Bonus: Shard Controller如何最小化Shard移动

我觉得这个也值得一提

计算每个G负责的S数量

$N$为Shards的数量，$G_i$为第$i$个RG分配的S数量。$NG$为RG的数量。

则$G_i = N / NG$，$N$ -= $G_i$，$NG$ -= 1。其中/为整除。

如何分配

遍历每个Shard：

1. 如果old config中的G还有可持有数量不为0，则继续让其作为持有者，并将其可持有数量减一。
2. 如果old config中的G可持有数量为0，则先跳过。

最后，如果存在S没有G持有，则将其给剩余有可持有数量的G，这里的顺序无所谓，因为要么就是Joined RG来拿RG，要么就是RG来拿Leaved RG。

看了下面这个例子就清楚了。假设Shard数量为10，我们考虑多个G加入或离开时，各自应该持有的S：

C0: 0 0 0 0 0 0 0 0 0 0 // Join 0, Gi = [10]
// Join 1, Gi = [5, 5]
C1: 0 0 0 0 0 1 1 1 1 1
// Join 2, Gi = [3, 3, 4]
Cm: 0 0 0 x x 1 1 1 x x
C2: 0 0 0 2 2 1 1 1 2 2
// Join 3, Gi = [2, 2, 3, 3]
Cm: 0 0 x 2 2 1 1 x 2 x
C3: 0 0 3 2 2 1 1 3 2 3
// Leave 3, Gi = [3, 3, 4]
Cm: 0 0 x 2 2 1 1 x 2 x // Gi = [1, 1, 1]
C4: 0 0 0 2 2 1 1 1 2 2
// Leave 1, Gi = {0:5, 2:5}
Cm: 0 0 0 2 2 x x x 2 2 // Gi = {0:2, 2:1}
C4: 0 0 0 2 2 0 0 2 2 2