MIT 6.824 分布式系统 Lab 4B

发表于

这是一篇不太水的水文。

《分布式系统导论》课程做的 MIT 6.824 的最后一个实验 Lab 4B 终于做完了，过了除了 Challenge 1 以外的所有测试。这个实验挺坑的，虽然 Lab 2 的 Raft 也很难，但是毕竟是复现论文；Lab 4B 核心的东西必须完全自己设计。我在某一个晚上突然开窍，悟出了一个直观简洁的做法，先不管正确性，至少能够过掉测试；特地掏出大半年没更的博客记录下来。

Lab 4B 内容

在 Lab 2 实现的 Raft（不支持 reconfiguration）、Lab 3 实现的基于 Raft 的键值存储，以及 Lab 4A 实现的基于 Raft 的集群配置管理器的基础上，实现一个分片键值存储引擎（ShardKV）。

整个 ShardKV 管理 10 个分片，每个 key 固定映射到其中一个分片。这个系统由集群配置管理器（ShardCtrler) 和多个用于存储 KV pair 的 KVRaft 实例组成。每个 KVRaft 实例包含若干个 KVRaft 进程，每个 KVRaft 进程运行一个 Raft，一个 KVRaft 实例的 Raft 部分能够在内部实现共识，并保证架在上面的 KVRaft 进程之间处于一致的状态。

ShardCtrler 独立地接受集群配置更改请求，包括增加和删除 Raft 实例，以及分片在 Raft 实例间的移动。增加 Raft 实例时，已有 Raft 实例管理的部分分片需要进行移动，来实现负载均衡；删除时，被删除的 Raft 实例所管理的分片则要被移动回属于当前配置的那些 Raft 实例中。KVRaft 实例要监控集群配置的更新，并且在配置发生改变时执行分片的迁移。整个系统必须在共识容错的能力范围内实现可线性化（linearizable）。

这个东西的最大坑点就在于产生了 Raft 集群间的交互，而交互方式完全需要自己来想。

三状态协议

前置内容

  • 每个客户端同一时间最多执行一个请求；
  • 在 Lab 3 中，客户端请求被提交至 Raft 后，如果 Leader 崩溃，则客户端的这个请求可能被 commit 也可能不被 commit。因此，每个请求需要包含一个客户端 ID 和一个唯一的且单调递增的序列号，用来识别重复的请求；
  • 在 Lab 4A 中，ShardCtrler 为每个集群配置都分配一个从 1 开始依次递增的序列号（0 是初始的空配置），并且保留完整的集群配置更改历史供 KVRaft 查询。

状态和状态转移路径

我们让每个 KVRaft 进程维护自身的一个状态 $S$，并且规定 $S$ 的取值范围：

$$ S \in \left{ \texttt{NORMAL}(n), \texttt{MIGRATING}(n), \texttt{WAITING}(n+1) \right}, n \in \mathbb{N} $$

其中，$n$ 表示了 KVRaft 进程当前使用的配置。由于仅有 Leader 可以服务客户端请求，因此 KVRaft Leader 的状态就可以视为整个 KVRaft 实例的状态，KVRaft Leader 状态中的 $n$ 就是整个 KVRaft 实例当前正使用的配置编号。

状态转移路径如下：

  • 所有 KVRaft 初始时位于 $\texttt{NORMAL}(0)$ 状态；
  • 从 $\texttt{NORMAL}(n)$ 可以转移到 $\texttt{MIGRATING}(n)$ 或者 $\texttt{WAITING}(n+1)$；
  • 从 $\texttt{MIGRATING}(n)$ 可以转移到 $\texttt{WAITING}(n+1)$；
  • 从 $\texttt{WAITING}(n)$ 可以转移到 $\texttt{NORMAL}(n)$。

显然，这个转移路径定义了状态集上的全序关系。在下面的表述中，如果我们对状态使用了“小于”“大于”之类的描述，即是在使用这一全序关系。

状态转移的发起和执行

  1. 位于 $\texttt{NORMAL}(n)$ 的 KVRaft Leader 在检测到 $n + 1$ 号配置时，向 Raft 提交 MIGRATE-TO(n+1) 并保持原状态不变；
  2. 位于 $\texttt{NORMAL}(n)$ 的 KVRaft 进程在收到 Raft 向上 apply 的 MIGRATE-TO(n+1) 后转移到 $\texttt{MIGRATING}(n)$ 或者 $\texttt{WAITING}(n+1)$，取决于本次配置更新中当前 KVRaft 实例是否从其他 KVRaft 实例处得到了新的分片；
  3. 位于 $\texttt{MIGRATING}(n)$ 的 KVRaft Leader 向其他 KVRaft 实例发 RPC 拉取对应的分片，并在收到分片后向 Raft 提交一个 MULTIPUT；
  4. 位于 $\texttt{MIGRATING}(n)$ 的 KVRaft 进程在收到 Raft 向上 apply 的 MULTIPUT 时，检查是否已经持有 $n + 1$ 号配置所需的全部分片，如果是则转移到 $\texttt{WAITING}(n+1)$；
  5. 位于 $\texttt{WAITING}(n)$ 的 KVRaft 进程检查其他所有 KVRaft 实例所使用的配置编号。如果全部 KVRaft 实例至少使用 $n$ 号配置，那么转移到 $\texttt{NORMAL}(n)$。

实现细节

防止重复提交大量 MIGRATE-TO 和 MULTIPUT

KVRaft Leader 需要维护一个额外的标记 issued，在当前状态为 $\texttt{NORMAL}$ 或者 $\texttt{MIGRATING}$ 时，判断是否已经提交了 MIGRATE-TO 或者已经开始从其他 KVRaft 实例拉取分片。

issued 不能被写进快照中，因为从崩溃中恢复的 KVRaft 进程可能需要重新提交 MIGRATE-TO 才能让它被 Raft 协议 commit。issued 应该在每次状态转移时被重置。

MIGRATE-TO 和 MULTIPUT 的处理

KVRaft 进程会自主检测新配置的出现并向 Raft 提交 MIGRATE-TO 消息，因此一个从崩溃中恢复的 KVRaft 进程可能会重复提交某些 MIGRATE-TO；MULTIPUT 也完全同理。因此，只有第一个合法的 MIGRATE-TO 消息和 MULTIPUT 应该被接受，其余的则直接忽略。

从崩溃中恢复的 KVRaft 还可能在 $\texttt{WAITING}(n)$ 状态收到 Raft apply 上来的 MIGRATE-TO(n+1)。这时，它应该原地等待直到系统前进至 $\texttt{NORMAL}(n)$。如果 KVRaft 有全局互斥锁，等待时需要放开这个锁。

可服务分片列表

KVRaft 始终维护一个当前可服务的分片列表，并仅仅以此为依据判断是否能服务客户端的某个请求。这个分片列表会在两个时刻被修改：

  • MIGRATE-TO(n+1) 被 apply 并且被接受时：仅保留那些在本次配置更新中继续由当前 KVRaft 实例负责的分片；
  • MULTIPUT 被 apply 并且被接受时：在列表中加入该 MULTIPUT 包含的那个分片。

这个列表同时可以用来对 MULTIPUT 去重。

拉取分片规则

当 KVRaft Leader 收到一个来自位于 $\texttt{MIGRATE}(n)$ 状态的其他 KVRaft 实例发来的拉取分片请求时，应该遵循以下规则：

  • 如果自身处于某个小于 $\texttt{MIGRATE}(n)$ 的状态，则拒绝请求并要求对方重试；
  • 如果自身处于某个大于 $\texttt{WAITING}(n+1)$ 的状态，则拒绝请求，对方也不应该再重试。

第二个规则事实上留有一些疑问，因为我不是这么实现的。我在实现时采用了进入 $\texttt{MIGRATE}(n)$ 时备份整个键值存储的做法。这样，第二条规则就可以变为：检查自己备份的键值存储所使用的配置编号，如果它大于等于 $n$，那么就拒绝请求，对方也不应该再重试。

跨配置更新的请求去重

在拉取分片时，应该同时拉取对方的整个去重用的数据结构（我的实现中为一个 map），并且与本地的那个合并。

协议的容错

  • 进程的崩溃和恢复由 Raft 直接保证，不需要额外考虑；
  • 两个关键的状态转移 $\texttt{NORMAL}(n) \to \texttt{MIGRATE}(n)$ 和 $\texttt{MIGRATE}(n) \to \texttt{WAITING}(n+1)$ 都需要 Raft apply 相应消息，因此配置更新事件的发生一定是 Raft 实例内部已经达成了共识；
  • 一个不在 majority 中的 KVRaft Leader 也有资格处理发来的拉取分片请求；这是因为如果它位于 $\texttt{MIGRATE}(n)$ 状态，那么根据上一条讨论，majority 一定也就进入 $\texttt{MIGRATE}(n)$ 状态达成了共识，它当前冻结的那些分片（即在 $n$ 号配置中拥有，但在 $n + 1$ 号配置中失去）必然也和 majority 一致，因此不需要在意它是否属于 majority。

对 Challenge 1 的讨论

Challenge 1 要求 KVRaft 进程如果失去某些分片的所有权，则应该在合适的时候删除这些分片。

完成 Challenge 1 意味着被拉取分片的 KVRaft Leader 需要得知另一个 KVRaft 实例将相应的 MULTIPUT commit 的信息。感官上，这需要以下修改：

  • 将拉取分片改为推送分片，或者改为拉取时直接返回，然后对方异步地进行一次推送；
  • 推送完成后需要将一个 DELETE-SHARD 消息提交给 Raft，并在 apply 上来时执行删除操作；
  • 如果我在 DELETE-SHARD 提交之后就崩溃了，导致它没能 commit，新的 Leader 就需要去找对方再问一次，然后重新把它提交给 Raft。

这需要一定的代码量，所以我没有做。相比之下，Challenge 2 靠上面所说的可服务分片列表就能完美解决。