Ciallo～(∠・ω< )⌒☆

记录一下 6.5840 2025 Spring Lab5 的过程

实验要求

在这个实验中，将会构建一个“分片”（sharded）的键值存储系统，即将键划分并存储在一组通过 Raft 副本机制实现的键值服务器组（shardgrps）中。一个分片是键值对的一个子集11 比如，所有以 “a” 开头的键可能是一个分片，所有以 “b” 开头的键是另一个分片，依此类推。分片可以提高性能。每个分片组仅处理少数几个分片的 Put 与 Get 请求，且各分片组并行运行；因此，系统的总吞吐量（单位时间内处理的 Put 与 Get 数量）会随着分片组数量的增加而按比例增加。一般来说，分片的数量会多于分片组的数量，这样每个组可以服务多个分片，从而方便的以较细的粒度进行负载转移。

分片键值服务的组件如右图所示。分片组（蓝色正方形）存储带有键的分片：分片组1持有一个存储键 “a” 的分片，分片组 2 持有一个存储键 “b” 的分片。分片键值服务的客户端通过一个 Clerk （以绿色圆圈表示）与服务交互，该 Clerk 实现了 Get 与 Put 方法。为了找到传递给 Put/Get 的键所属的分片组，Clerk 从 Kvsrv （使用黑色正方形表示）获取 “配置(configuration)”。配置描述了分片到分片组的映射关系22 比如，分片1由分片组3提供服务

这里需要注意的是：在本次的实验中，分片组内部的服务器集合是静态且固定的，服务器在实验过程中不会在不同的组之间切换。负载均衡与配置变更的实质是分片（数据子集）在不同组之间的归属权转移，而非服务器成员的重新分配。当系统需要调整负载或应对组的加入与离开时，发生的动作是键值数据在网络间的物理迁移。33 例如，如果系统发现，组 1 的负载过大时，就可以通过配置要求将分片 3 从组 1 移动到组 2 ，其过程是组 1 将该分片包含的所有键值对打包，通过 RPC 发送并安装到组 2 的服务器中，此后组 1 就不再负责该区域的数据，进而减小组 1 的负载，实现负载均衡

管理员（即测试程序）使用另一个客户端，可以称为控制器（使用紫色圆圈表示），从集群中添加或删除分片组，并更新哪个分片组应该服务于哪个分片。控制器有一个主要方法： ChangeConfigTo ，它接受一个新配置作为参数，并将系统从当前配置更改为新配置；这涉及到将分片移动到新加入系统的分片组，以及将分片从离开系统的分片组中移出。为此，控制器会：

  1. 向分片组发送 RPC，这些RPC是：FreezeShard, InstallShard和 DeleteShard
  2. 更新存储在 kvsrv 中的配置。

引入控制器的原因是，分片存储系统必须能够在分片组之间迁移分片。原因如下：

  1. 某些分片组的负载可能比其他组更高，因此需要移动分片来平稳负载。
  2. 分片组可能会加入或离开系统：可以添加新的分片组以增加容量，或者现有的分片组可能因维修或退役而下线。

本次实验的主要需要解决的问题是：确保以下情况下的 Get/Put 操作的线性一致性：

  1. 分片到分片组分配关系的变更
  2. 从在 ChangeConfigTo 期间发生故障或被网络分区的控制器中恢复

以下是需要注意的点

  1. ChangeConfigTo 在分片组之间移动分片。一个风险是某些客户端可能会使用旧的分片组，而其他客户端使用新的分片组，这可能会破坏线性一致性。因此，需要确保在任何时刻，对于每个分片，最多只有一个分片组在为其提供服务。
  2. 如果 ChangeConfigTo 在重新配置过程中失败，如果某些分片已经开始但尚未完成从一个处分组到另一个分片组的迁移，它们可能会变得不可访问。为了保证系统可以继续运行，测试程序会启动一个新的控制器，而我们需要确保新控制器可以完成前一个控制器启动的重新配置工作。
  3. 该实验使用 配置 来指代分片到分片组的分配。这与 Raft 集群成员变更（membership changes）不是一回事。
  4. 一个分片组服务器仅属于一个分片组。给定分片组中的服务器集合永远不会改变。

我的实现

任务A

任务A也太难了！其实我感觉也不是特别的难，它要实现的东西也很简单，我也可以很快速的就写出来，但是我就是经常考虑不到这些小细节，导致每一个测试用例都需要花费很长时间才能过。经过我3天的不断的尝试，终于过了。

这里正好记录一下我遇到的坑：

间歇性超时问题（TestManyConcurrentClerkUnreliable5A）：这个测试用例有时能通过，有时会在30秒内无返回结果导致超时。问题根源在于 shardgrp/client.go 中的 Get 和 Put 方法使用了无限重试循环。当不可靠网络导致某个 shard group 的所有 server 暂时不可达时，客户端会永久卡在 RPC 重试循环中，无法响应测试框架的停止信号。修复方法是给底层的 Get/Put 方法添加最大轮次限制（maxRounds=2），遍历所有 server 两轮后若仍失败则返回 ErrWrongLeader，让上层的 shardkv1/client.go 重新查询配置并重试。同时在上层也要处理 ErrWrongLeader 错误。因此，在分布式系统中要避免嵌套的无限循环，底层应该 “fail fast” 返回错误让上层决策，而不是无限阻塞；设计重试策略时要考虑层级化，并确保异步信号（如 done channel）能被及时响应。

任务B

任务B要求实现可以处理故障的控制器。具体来说，控制器在移动分片的过程中可能会发生故障或失去网络连接。因此，该任务要求修改控制器，以便新的控制器可以完成之前的重新配置工作。其具体的实现方法在实验的要求中表述的已经足够清晰了：使用两个配置，一个是当前的配置，一个是下一个配置。这两个都是保存在了 kvsrc 中。当控制器开始重新配置时，它先存储“下一个配置”。一旦控制器完成了分片迁移工作，它就将“下一个配置”变为“当前配置”。修改 InitController，使其首先检查是否存在一个配置编号（Num）高于当前配置的“下一个配置”；如果存在，则完成将系统重新配置到该“下一个配置”所需的必要分片迁移。

这个任务没有什么坑，非常顺利的就过了。