MIT 6.824 Lab 4 ShardKV Write-up

作者: twd2 日期: 2020 年 05 月 23 日被围观 1,185 次发表评论 (0) 查看评论

目标

本次Lab的目标是在Lab 2实现的Raft协议的基础上构建一个分片的分布式Key-Value存储系统，包括分片Master以及分片组的服务器和客户端。此外，本次Lab有若干挑战功能，这里逐一全部实现。

设计与实现

Lab 4A (Shard Master)

Shard Master负责管理所有的组，决定每个组负责存储哪些分片，以及响应用户对组的增加（Join）、删除（Leave）、移动（Move）和查询（Query）操作。与Lab 3中实现的简易分布式Key-Value存储系统类似，Shard Master同样分为服务器和客户端。其框架与Lab 3完全相同，区别仅在需要处理的请求的语义不同。Lab 3中需要处理Get、Put以及Append，本节则处理Join、Leave、Move和Query操作。

每个组的服务器配置信息以及分片到组的对应关系，称为配置（config）。历史上的所有配置均保留在服务器中，每次对配置进行修改操作（即Join、Leave以及Move操作）时，最新的配置会被复制一份，然后再进行修改，同时其序号（Num）增加一。用户可以通过Query查询最新配置，或历史上某一个特定配置。上述修改操作具体实现为：

Join操作

对于Join操作，其参数为一系列组的配置信息。服务器处理该操作时，首先将组的信息保存在配置中，然后进行下文所述的重平衡算法。特别地，如果本次新加入的组是首批组，那么在重平衡前需要将所有分片（它们原先不对应任何组）移动到新加入的编号最小的组（需要确保Shard Master所有服务器执行相同的、确定性的操作，因此不能为任意组）。

Leave操作

对于Leave操作，其参数为一系列组的编号。处理该操作时，服务器会将这些组从配置中删除，并将这些组存储的分片移动到剩余的编号最小的组，然后进行重平衡算法。执行完该操作后，服务器要求至少剩余一个组。

Move操作

对于Move操作，Shard Master会将指定的分片移动到指定的组。这个接口是为了调试和测试用的，执行完该操作后不进行重平衡算法。

重平衡算法

在对配置进行修改后，每个组存储的分片数量可能会变得不均匀，因此需要进行重平衡。重平衡的目标是使得每个组存储的分片数量变得均匀（数量的最大值与最小值之差不超过1），并且重新达到平衡的过程中被移动的分片的数量最少。

对于一个配置，重平衡算法首先通过分片到组的对应关系计算出每个组存储的分片的列表，然后将这些组按照其存储的分片数量从大到小排序。为了确保Shard Master所有服务器执行相同的操作，当某两个组的分片数量一致时，编号更小的组排在更前。排序后，算法计算每个组平衡后应当存储的分片数量。假设共有ngroups个组，nshards个分片，那么前nshards % ngroups个组存储nshards / ngroups + 1个分片，剩下的组存储nshards / ngroups个分片。接着算法遍历每个组，将分片数量多于预期的组的多余分片取出并统一暂存。最后，算法遍历每个组，将暂存的多余分片分配至分片数量少于预期的组。算法总计需要一次对组的排序、两次对组的遍历以及其中的分片复制操作，总体时间复杂度为O(ngroups * log(ngroups) + nshards)。

Lab 4B (Shard KV)

根据配置，每个分片组负责存储相应的若干分片，并处理对这些分片的客户端请求。同样，分片组分为服务器和客户端。

客户端

客户端的实现是简洁的。客户端与Lab 3中所述的客户端实现非常类似，但其在每轮尝试向服务器发送RPC请求前，会先利用Shard Master的客户端向Shard Master请求当前最新配置，然后向相应的组的各个服务器依次尝试发送请求。

服务器

本次实验的分片组服务器与Lab 3中的服务器不同，其需要处理多个分片。本节的核心设计思想为，服务器存储的分片可以分为实际存储数据的分片和不实际存储数据的分片引用。分片引用存储该分片实际数据的来源（配置序号以及分片编号），表示服务器正在等待其他组的服务器将此分片迁移至当前服务器。这一设计允许服务器将配置更新与分片迁移操作分离，配置更新时仅需快速更新分片引用，而分片数据则可以后续独立传送。一旦某一分片数据传送（迁移）完成，服务器可立即开始处理对该分片的请求，而无需等待其他正在传送的分片数据（对应TestChallenge2Unaffected及TestChallenge2Partial）。

在执行Get、Put以及Append时，服务器会首先检查请求的Key对应的分片在当前配置下是否由本服务器负责，若不由本服务器负责，则直接返回组错误响应。若确实由本服务器负责，则服务器继续按照规定的语义执行，并产生返回值。其中，若被访问的分片由本服务器负责但尚为引用，服务器不会阻塞，其会返回分片未就绪的响应，期望客户端一段时间后重试。

配置更新与分片迁移

分片服务器在启动时会启动一个goroutine负责更新配置，其定期利用Shard Master客户端向Shard Master轮询最新的配置，并获取当前配置之后的所有新配置。然后，其调用Raft协议的Start接口来将分片组服务器当前配置之后的所有新配置逐一加入Raft日志（log）中。当这些日志（新配置）被Raft协议提交（commit）后，便会出现在applyCh。此时，分片组服务器会进行配置更新，配置更新一般会导致每个组负责的分片的情况发生变化，服务器会进行如下处理（updateConfig）：

若原先无人负责的分片在新配置下由本组负责，则服务器创建一个新的分片数据。
若原先由本组负责的分片在新配置下仍由本组负责，则服务器简单地重复使用这一分片数据。
若原先由其他组负责的分片在新配置下由本组负责，则进一步分为两种情况。若所需的分组数据已经被传输到当前服务器，则服务器直接使用该分片数据，这说明当前服务器在分片原先所在的组之后更新配置。若所需的分片数据还未被传输到当前服务器，则服务器创建一个分片引用以及一个条件变量，用于等待分片数据，这说明当前服务器在分片原先所在的组之前更新配置。此处不会阻塞。
若原先由本组负责的分片在新配置下由其他组负责，则无论分片是实际数据还是引用，服务器都会创建一个分片发送任务并记录在transferringShards中。其中，transferringShards为一个需要被记录在快照中的服务器状态，以便服务器崩溃重启后恢复这个发送任务。同时，服务器会创建一个goroutine按照下文所述方法来处理这一任务。在分片迁移成功后，服务器将该任务删除，此后，该分片的数据便不再存储于本组服务器中了。

发送分片迁移数据（beginTransfer）

发送分片数据至其他组的服务器前，若被发送的分片仍为引用，则服务器首先通过条件变量等待分片数据从其他组的服务器迁移至当前服务器，然后再继续发送流程。等待操作仅阻塞当前goroutine，不会影响服务器处理其他请求、配置更新或分片迁移任务。

若待发送的分片数据已准备好，服务器会将创建该发送任务时配置的序号、分片编号、分片数据以及用于客户端请求去重的状态信息（clients[].Ops）打包为一个分片迁移请求，然后发送至目标组。分片迁移请求的发送和处理过程与Lab 3的请求处理过程类似，即发送者依次尝试目标组的各个服务器，由目标组的Leader将分片迁移请求加入Raft日志中，然后在日志被提交后，接收者处理请求并返回响应。

在分片迁移数据发送完毕并获得成功响应后，服务器将该任务从transferringShards中删除。此后，该分片的数据便不再存储于本组服务器中了，这样也就自动实现了分片垃圾回收（对应TestChallenge1Delete）。

最后，服务器创建一个新的快照，尽快释放不再使用的空间。

接收分片迁移数据（applyTransferOp）

当服务器收到分片迁移请求被Raft协议提交的消息时，其首先判断该分片迁移请求的配置序号：

若配置序号小于本服务器当前配置的序号，则服务器应当正在等待该分片的数据被迁移至当前服务器。此时，服务器存储这一分片数据，并用条件变量通知可能的等待者。若服务器没有等待该分片的数据，则说明该分片迁移请求为重复的，服务器直接忽略。
若配置序号大于等于本服务器当前配置的序号，则说明发送方先于当前服务器进行了配置更新并发送了分片迁移。此时，服务器存储这一分片数据，后续更新配置时将会使用。此外，若服务器此前收到过相同配置序号的相同分片，则说明该分片迁移请求为重复的，服务器直接忽略。

最后，服务器同样创建一个新的快照，尽快释放不再使用的空间。