6.5840 实验 5: 分片键值服务

介绍

你可以基于自己的想法做一个期末项目，或者做本实验。

在本实验中，你将构建一个"分片"的键值存储系统， 将键分区到一组 Raft 复制的键值服务器组（shardgrp）上。 分片是键值对的子集；例如，所有以 "a" 开头的键可能是一个分片， 所有以 "b" 开头的键是另一个分片，等等。 分片的原因是性能。每个 shardgrp 只处理少数分片的 put 和 get， 并且 shardgrp 并行运行；因此系统总吞吐量 （单位时间的 put 和 get 数量）与 shardgrp 的数量成正比。

分片键值服务具有上面显示的组件。 Shardgrp（用蓝色方块显示）存储带有键的分片： shardgrp 1 持有存储键 "a" 的分片， shardgrp 2 持有存储键 "b" 的分片。 分片键值服务的客户端通过 clerk（用绿色圆圈显示）与服务交互， clerk 实现了 Get 和 Put 方法。 为了找到传递给 Put/Get 的键所属的 shardgrp， clerk 从 kvsrv（用黑色方块显示）获取配置， 这是你在实验 2 中实现的。 配置（未显示）描述了分片到 shardgrp 的映射 （例如，分片 1 由 shardgrp 3 服务）。

管理员（即测试器）使用另一个客户端——控制器（用紫色圆圈显示）， 来向集群添加/移除 shardgrp 并更新哪个 shardgrp 应该服务哪个分片。 控制器有一个主要方法：ChangeConfigTo， 它接受一个新配置作为参数，并将系统从当前配置更改为新配置； 这涉及将分片迁移到加入系统的新 shardgrp， 以及从离开系统的 shardgrp 迁出分片。 为此，控制器 1) 向 shardgrp 发送 RPC （FreezeShard、InstallShard 和 DeleteShard）， 2) 更新存储在 kvsrv 中的配置。

使用控制器的原因是分片存储系统必须能在 shardgrp 之间转移分片。 一个原因是某些 shardgrp 可能比其他 shardgrp 负载更高， 因此需要移动分片来平衡负载。 另一个原因是 shardgrp 可能加入和离开系统： 可能添加新的 shardgrp 以增加容量， 或者将现有的 shardgrp 下线以进行维修或退役。

本实验的主要挑战是在处理以下情况时确保 Get/Put 操作的线性可序列化： 1) 分片到 shardgrp 的分配变化， 2) 在 ChangeConfigTo 期间从故障或被分区的控制器恢复。

1. ChangeConfigTo 将分片从一个 shardgrp 迁移到另一个 shardgrp。 一个风险是某些客户端可能使用旧的 shardgrp， 而其他客户端使用新的 shardgrp，这可能破坏线性可序列化。 你需要确保在任何时候最多只有一个 shardgrp 在服务于每个分片的请求。
2. 如果 ChangeConfigTo 在重新配置期间失败， 某些分片可能变得不可访问，如果它们已经开始但未完成从一个 shardgrp 到另一个 shardgrp 的迁移。 为了取得进展，测试器启动一个新控制器， 你的任务是确保新控制器完成前一个控制器开始的重新配置。

本实验使用"配置"来指代分片到 shardgrp 的分配。 这与 Raft 集群成员变更不同。 你不需要实现 Raft 集群成员变更。

一个 shardgrp 服务器只是一个 shardgrp 的成员。 给定 shardgrp 中的服务器集合永远不会改变。

只能使用 RPC 进行客户端和服务器之间的交互。 例如，你的服务器的不同实例不允许共享 Go 变量或文件。

在部分 A 中，你将实现一个可工作的 shardctrler， 它将在 kvsrv 中存储和检索配置。 你还将实现用你的 Raft rsm 包复制的 shardgrp， 以及相应的 shardgrp clerk。 shardctrler 与 shardgrp clerk 通信以在不同组之间迁移分片。

在部分 B 中，你将修改你的 shardctrler 以处理配置变更期间的故障和分区。 在部分 C 中，你将扩展你的 shardctrler 以允许并发控制器而不互相干扰。 最后，在部分 D 中，你将有机会以任何你喜欢的方式扩展你的解决方案。

本实验的分片键值服务遵循与 Flat Datacenter Storage、BigTable、 Spanner、FAWN、Apache HBase、Rosebud、Spinnaker 和许多其他系统相同的总体设计。 不过，这些系统在许多细节上与本实验不同，而且通常更复杂、更强大。 例如，本实验不会演变每个 Raft 组中的对等体集合； 它的数据和查询模型很简单；等等。

实验 5 将使用你实验 2 中的 kvsrv，以及实验 4 中的 rsm 和 Raft。 你的实验 5 和实验 4 必须使用相同的 rsm 和 Raft 实现。

你可以使用延迟时间来完成部分 A，但不能使用延迟时间来完成部分 B-D。

入门

我们为你提供了 src/shardkv1 中的测试和骨架代码：

• client.go 用于 shardkv clerk
• shardcfg 包用于计算分片配置
• shardgrp 包：用于 shardgrp clerk 和服务器。
• shardctrler 包，包含 shardctrler.go，其中有控制器更改配置 （ChangeConfigTo）和获取配置（Query）的方法

要开始运行，请执行以下命令：

$ cd ~/6.5840
$ git pull
...
$ cd src
$ make RUN="-run 5A" shardkv
go build -race -o main/kvsrv1d main/kvsrv1d.go
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run 5A
=== RUN  TestInitQuery5A
Test (5A): Init and Query ... (reliable network)...
...

部分 A: 迁移分片

你的第一个任务是实现 shardgrp 以及在没有故障时的 InitConfig、Query 和 ChangeConfigTo 方法。 我们已经为你提供了描述配置的代码，在 shardkv1/shardcfg 中。 每个 shardcfg.ShardConfig 有一个唯一标识号、 从分片号到组号的映射，以及从组号到复制该组的服务器列表的映射。 通常分片会比组多（这样每个组服务多个分片）， 以便能以相当细的粒度转移负载。

在 shardctrler/shardctrler.go 中实现这两个方法：

• InitConfig 方法接收第一个配置， 由测试器作为 shardcfg.ShardConfig 传递给它。 InitConfig 应将配置存储在实验 2 的 kvsrv 实例中。
• Query 方法返回当前配置； 它应从 kvsrv 读取配置，该配置之前由 InitConfig 存储在那里。

实现 InitConfig 和 Query，并将配置存储在 kvsrv 中。 当你的代码通过第一个测试时即完成。注意此任务不需要任何 shardgrp。

$ cd ~/6.5840/src
$ make RUN="-run TestInitQuery5A" shardkv
go build -race -o main/kvsrv1d main/kvsrv1d.go
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run TestInitQuery5A
=== RUN   TestInitQuery5A
Test (5A): Init and Query ... (reliable network)...
  ... Passed --  time  0.0s #peers 1 #RPCs     3 #Ops    0
--- PASS: TestInitQuery5A (0.13s)
PASS
ok  	6.5840/shardkv1	1.143s

• 通过从 kvsrv 存储和读取初始配置来实现 InitConfig 和 Query： 使用 ShardCtrler.IKVClerk 的 Get/Put 方法与 kvsrv 通信， 使用 ShardConfig 的 String 方法将 ShardConfig 转换为可以传递给 Put 的字符串， 并使用 shardcfg.FromString() 函数将字符串转换为 ShardConfig。

通过从实验 4 的 kvraft 解决方案复制代码， 在 shardkv1/shardgrp/server.go 中实现初始版本的 shardgrp， 并在 shardkv1/shardgrp/client.go 中实现相应的 clerk。

在 shardkv1/client.go 中实现一个 clerk， 它使用 Query 方法找到键所属的 shardgrp，然后与该 shardgrp 通信。 当你的代码通过 Static 测试时即完成。

$ cd ~/6.5840/src
$ make RUN="-run TestStatiOneShardGroup5A" shardkv
go build -race -o main/kvsrv1d main/kvsrv1d.go
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run TestStaticOneShardGroup5A
=== RUN   TestStaticOneShardGroup5A
Test (5A): one shard group ... (reliable network)...
  ... Passed --  time  9.4s #peers 1 #RPCs   822 #Ops  420
--- PASS: TestStaticOneShardGroup5A (9.52s)
PASS
ok  	6.5840/shardkv1	10.542s

• 从你的 kvraft client.go 和 server.go 复制 Put 和 Get 的代码， 以及你从 kvraft 需要的任何其他代码。
• shardkv1/client.go 中的代码为整个系统提供 Put/Get clerk： 它通过调用 Query 方法找出哪个 shardgrp 持有期望键的分片， 然后与持有该分片的 shardgrp 通信。
• 实现 shardkv1/client.go，包括其 Put/Get 方法。 使用 shardcfg.Key2Shard() 找到键的分片号。 测试器将 ShardCtrler 对象传递给 shardkv1/client.go 中的 MakeClerk。 使用 Query 方法获取当前配置。
• 要从 shardgrp put/get 一个键，shardkv clerk 应通过调用 shardgrp.MakeClerk 为该 shardgrp 创建一个 shardgrp clerk，传入配置中找到的服务器和 shardkv clerk 的 ck.clnt。 使用 ShardConfig 的 GidServers() 方法获取分片所属的组。
• shardkv1/client.go 的 Put 必须在回复可能丢失时返回 ErrMaybe， 但这个 Put 调用的是 shardgrp 的 Put 来与特定 shardgrp 通信。 内部 Put 可以用错误信号通知这种情况。
• 创建时，第一个 shardgrp（shardcfg.Gid1）应初始化自己拥有所有分片。

现在你应该通过实现 ChangeConfigTo 方法来支持分片在组之间的迁移， 该方法从旧配置更改为新配置。 新配置可能包括旧配置中不存在的新 shardgrp， 也可能排除旧配置中存在的 shardgrp。 控制器应迁移分片（键值数据），使每个 shardgrp 存储的分片集合与新配置匹配。

我们建议的迁移分片的方法是，ChangeConfigTo 首先在源 shardgrp "冻结"分片，使该 shardgrp 拒绝迁移分片中键的 Put。 然后，将分片复制（安装）到目标 shardgrp；然后删除冻结的分片。 最后，发布新配置，使客户端能找到迁移后的分片。 这个方法的一个很好的特性是它避免了 shardgrp 之间的任何直接交互。 它还支持服务不受正在进行的配置变更影响的分片。

为了能够对配置变更进行排序， 每个配置都有一个唯一的编号 Num （见 shardcfg/shardcfg.go）。 部分 A 的测试器按顺序调用 ChangeConfigTo， 传递给 ChangeConfigTo 的配置的 Num 将比前一个大 1；因此，Num 较高的配置比 Num 较低的配置更新。

网络可能会延迟 RPC，RPC 可能会在 shardgrp 处乱序到达。 为了拒绝旧的 FreezeShard、InstallShard 和 DeleteShard RPC， 它们应该包含 Num （见 shardgrp/shardrpc/shardrpc.go）， 并且 shardgrp 必须记住它们为每个分片看到的最大 Num。

实现 ChangeConfigTo （在 shardctrler/shardctrler.go 中）并扩展 shardgrp 以支持冻结、安装和删除。 ChangeConfigTo 在部分 A 中应始终成功，因为测试器在本部分不会引发故障。 你需要使用 shardgrp/shardrpc 包中的 RPC 在 shardgrp/client.go 和 shardgrp/server.go 中实现 FreezeShard、InstallShard 和 DeleteShard， 并根据 Num 拒绝旧的 RPC。 你还需要修改 shardkv1/client.go 中的 shardkv clerk 以处理 ErrWrongGroup， 如果 shardgrp 不负责该分片则应返回此错误。

当你通过 JoinBasic 和 DeleteBasic 测试时，即完成了此任务。 这些测试侧重于添加 shardgrp；你还不需要担心 shardgrp 离开的问题。

• 对于客户端 Put/Get 中 shardgrp 不负责的键 （即键的分片未分配给该 shardgrp），shardgrp 应回复 ErrWrongGroup 错误。 你将不得不修改 shardkv1/client.go 以重新读取配置并重试 Put/Get。
• 注意，你将不得不通过你的 rsm 包运行 FreezeShard、 InstallShard 和 DeleteShard，就像 Put 和 Get 一样。
• 你可以在 RPC 请求或回复中将整个映射作为状态发送， 这可能有助于保持分片传输代码的简洁。
• 如果你的一个 RPC 处理函数在其回复中包含了服务器状态的一部分的映射 （例如键值映射），你可能会因为竞争而遇到错误。 RPC 系统必须读取映射才能将其发送给调用者， 但它没有持有覆盖该映射的锁。 然而，你的服务器可能会在 RPC 系统读取映射时继续修改同一个映射。 解决方案是让 RPC 处理函数在回复中包含映射的副本。

扩展 ChangeConfigTo 以处理离开的分片组； 即，在当前配置中存在但在新配置中不存在的 shardgrp。 你的解决方案现在应通过 TestJoinLeaveBasic5A。 （你可能在前一个任务中已经处理了这种情况， 但之前的测试没有测试 shardgrp 离开的场景。）

使你的解决方案通过所有部分 A 测试， 这些测试检查你的分片键值服务是否支持许多组的加入和离开、 shardgrp 从快照重启、在某些分片离线或参与配置变更时处理 Get， 以及当许多客户端与服务交互而测试器并发调用控制器的 ChangeConfigTo 来重新平衡分片时的线性可序列化。

$ cd ~/6.5840/src
$ make RUN="-run 5A" shardkv
go build -race -o main/kvsrv1d main/kvsrv1d.go
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run 5A
Test (5A): Init and Query ... (reliable network)...
  ... Passed --  time  0.0s #peers 1 #RPCs     3 #Ops    0
Test (5A): one shard group ... (reliable network)...
  ... Passed --  time  5.1s #peers 1 #RPCs   792 #Ops  180
Test (5A): a group joins... (reliable network)...
  ... Passed --  time  12.9s #peers 1 #RPCs  6300 #Ops  180
Test (5A): delete ... (reliable network)...
  ... Passed --  time  8.4s #peers 1 #RPCs  1533 #Ops  360
Test (5A): basic groups join/leave ... (reliable network)...
  ... Passed --  time  13.7s #peers 1 #RPCs  5676 #Ops  240
Test (5A): many groups join/leave ... (reliable network)...
  ... Passed --  time  22.1s #peers 1 #RPCs  3529 #Ops  180
Test (5A): many groups join/leave ... (unreliable network)...
  ... Passed --  time  54.8s #peers 1 #RPCs  5055 #Ops  180
Test (5A): shutdown ... (reliable network)...
  ... Passed --  time  11.7s #peers 1 #RPCs  2807 #Ops  180
Test (5A): progress ... (reliable network)...
  ... Passed --  time  8.8s #peers 1 #RPCs   974 #Ops   82
Test (5A): progress ... (reliable network)...
  ... Passed --  time  13.9s #peers 1 #RPCs  2443 #Ops  390
Test (5A): one concurrent clerk reliable... (reliable network)...
  ... Passed --  time  20.0s #peers 1 #RPCs  5326 #Ops 1248
Test (5A): many concurrent clerks reliable... (reliable network)...
  ... Passed --  time  20.4s #peers 1 #RPCs 21688 #Ops 10500
Test (5A): one concurrent clerk unreliable ... (unreliable network)...
  ... Passed --  time  25.8s #peers 1 #RPCs  2654 #Ops  176
Test (5A): many concurrent clerks unreliable... (unreliable network)...
  ... Passed --  time  25.3s #peers 1 #RPCs  7553 #Ops 1896
PASS
ok      6.5840/shardkv1 243.115s
$

你的解决方案必须继续服务不受正在进行的配置变更影响的分片。

部分 B: 处理故障控制器

控制器是一个短生命周期的命令，由管理员调用： 它迁移分片然后退出。但它可能在迁移分片时故障或失去网络连接。 本实验这部分的主要任务是从未能完成 ChangeConfigTo 的控制器恢复。 测试器在分区第一个控制器后启动一个新控制器并调用其 ChangeConfigTo； 你需要修改控制器，使新控制器完成重新配置。 测试器在启动控制器时调用 InitController； 你可以修改该函数来检查是否需要完成被中断的配置变更。

允许控制器完成前一个控制器开始的重新配置的好方法是 保存两个配置：当前配置和下一个配置，两者都存储在控制器的 kvsrv 中。 当控制器开始重新配置时，它存储下一个配置。 一旦控制器完成重新配置，它使下一个配置成为当前配置。 修改 InitController 以首先检查是否存在一个存储的下一个配置， 其配置编号高于当前配置，如果存在，完成重新配置到下一个配置所需的分片迁移。

修改 shardctrler 以实现上述方法。 接管故障控制器工作的控制器可能会重复 FreezeShard、InstallShard 和 Delete RPC； shardgrp 可以使用 Num 来检测重复并拒绝它们。 如果你的解决方案通过了部分 B 测试，即完成了此任务。

$ cd ~/6.5840/src
$ make RUN="-run 5B" shardkv
go build -race -o main/kvsrv1d main/k
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run 5B
Test (5B): Join/leave while a shardgrp is down... (reliable network)...
  ... Passed --  time  9.2s #peers 1 #RPCs   899 #Ops  120
Test (5B): recover controller ... (reliable network)...
  ... Passed --  time  26.4s #peers 1 #RPCs  3724 #Ops  360
PASS
ok      6.5840/shardkv1 35.805s
$

• 测试器在启动控制器时调用 InitController； 你可以在 shardctrler/shardctrler.go 中的该方法中实现恢复。

部分 C: 并发配置变更

在本实验的这部分，你将修改控制器以允许并发控制器。 当控制器崩溃或被分区时，测试器将启动一个新控制器， 它必须完成旧控制器可能正在进行的所有工作 （即，像部分 B 一样完成迁移分片）。 这意味着多个控制器可能并发运行并向 shardgrp 和存储配置的 kvsrv 发送 RPC。

主要挑战是确保这些控制器不会互相干扰。 在部分 A 中，你已经使用 Num 隔离了所有 shardgrp RPC， 使旧 RPC 被拒绝。即使多个控制器并发接管旧控制器的工作， 其中一个成功而其他控制器重复所有 RPC，shardgrp 也会忽略它们。

因此剩下的具有挑战性的情况是确保只有一个控制器更新下一个配置， 以避免两个控制器（例如，一个被分区的和一个新的） 将不同的配置放入下一个配置。 为了强调这种情况，测试器并发运行多个控制器， 每个控制器通过读取当前配置并更新离开的或加入的 shardgrp 来计算下一个配置， 然后测试器调用 ChangeConfigTo； 因此多个控制器可能用具有相同 Num 的不同配置调用 ChangeConfigTo。 你可以使用键的版本号和带版本号的 Put 来确保只有一个控制器更新下一个配置， 而其他调用不做任何事就返回。

修改你的控制器，使每个配置 Num 只有一个控制器能发布下一个配置。 测试器将启动许多控制器，但只有一个应为新配置启动 ChangeConfigTo。 如果你通过了部分 C 的并发测试，即完成了此任务：

$ cd ~/6.5840/src
$ make RUN="-run TestConcurrentReliable5C" shardkv
go build -race -o main/kvsrv1d main/k
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run TestConcurrentReliable5C
Test (5C): Concurrent ctrlers ... (reliable network)...
  ... Passed --  time  8.2s #peers 1 #RPCs  1753 #Ops  120
PASS
ok      6.5840/shardkv1 8.364s
$ make RUN="-run TestAcquireLockConcurrentUnreliable5C" shardkv
go build -race -o main/kvsrv1d main/k
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run TestAcquireLockConcurrentUnreliable5C
Test (5C): Concurrent ctrlers ... (unreliable network)...
  ... Passed --  time  23.8s #peers 1 #RPCs  1850 #Ops  120
PASS
ok      6.5840/shardkv1 24.008s
$

• 参见 test.go 中的 concurCtrler 了解测试器如何并发运行控制器。

在这个练习中，你将把旧控制器的恢复与新控制器结合起来： 新控制器应执行部分 B 的恢复。 如果旧控制器在 ChangeConfigTo 期间被分区， 你将不得不确保旧控制器不会干扰新控制器。 如果控制器的所有更新都已经用部分 B 的 Num 检查正确隔离了， 你就不需要写额外的代码。 如果你通过了 Partition 测试，即完成了此任务。

$ cd ~/6.5840/src
$ make RUN="-run Partition" shardkv
go build -race -o main/kvsrv1d main/k
go build -race -o main/shardgrp1d main/shardgrp1d.go
cd shardkv1; go test -timeout 15m -v -race -run Partition
Test (5C): partition controller in join... (reliable network)...
  ... Passed --  time  7.8s #peers 1 #RPCs   876 #Ops  120
Test (5C): controllers with leased leadership ... (reliable network)...
  ... Passed --  time  36.8s #peers 1 #RPCs  3981 #Ops  360
Test (5C): controllers with leased leadership ... (unreliable network)...
  ... Passed --  time  52.4s #peers 1 #RPCs  2901 #Ops  240
Test (5C): controllers with leased leadership ... (reliable network)...
  ... Passed --  time  60.2s #peers 1 #RPCs 27415 #Ops 11182
Test (5C): controllers with leased leadership ... (unreliable network)...
  ... Passed --  time  60.5s #peers 1 #RPCs 11422 #Ops 2336
PASS
ok      6.5840/shardkv1 217.779s
$

你已经完成了实现一个高可用的分片键值服务， 具有许多分片组以实现可扩展性， 重新配置以处理负载变化，以及容错控制器；恭喜！

重新运行所有测试以检查你对控制器的最近更改是否没有破坏之前的测试。

$ make raft1
$ make kvraft1
$ make shardkv

部分 D: 扩展你的方案

在本实验的最后部分，你可以以任何你喜欢的方式扩展你的解决方案。 你将不得不为你选择实现的任何扩展编写自己的测试。

实现以下想法之一或提出自己的想法。 在文件 extension.md 中写一段描述你的扩展， 并将 extension.md 上传到 Gradescope。 如果你想做更难、更开放的扩展， 欢迎与课上的另一个学生合作。

以下是一些可能的扩展想法（前几个比较简单，后面的更开放）：

• 修改测试器以使用 kvraft 而不是 kvsrv （即，将 test.go 中 MakeTestMaxRaft 里的 kvsrv.StartKVServer 替换为 kvraft.StartKVServer）， 使控制器使用你的 kvraft 来存储其配置。 编写一个测试，检查在一个 kvraft 对等体宕机时控制器是否能查询和更新配置。 测试器的现有代码分布在 src/kvtest1、src/shardkv1 和 src/tester1 中。
• 修改 kvsrv 以实现 Put/Get 的精确一次语义， 如同去年的实验 2 （参见丢包部分）。 你可能可以从 2024 年移植一些测试，而不必从头编写。 在你的 kvraft 中也实现精确一次。
• 修改 kvsrv 以支持 Range 函数， 返回 low 键到 high 键范围内的所有键。 实现 Range 的懒惰方式是遍历服务器维护的键值映射； 更好的方式是使用支持范围搜索的数据结构（例如 B 树）。 包含一个使懒惰方案失败但能通过更好方案的测试。
• 修改你的 kvraft 实现， 允许领导者在不需要通过 rsm 运行 Get 的情况下服务 Get。 即，实现 Raft 论文第 8 节末尾描述的优化， 包括租约，以确保 kvraft 维护线性可序列化。 你的实现应通过现有的 kvraft 测试。 你还应添加一个测试，检查你的优化实现是否更快 （例如，通过比较 RPC 数量）， 以及一个测试，检查 term 切换是否更慢， 因为新领导者必须等待租约到期。
• 在 kvraft 中支持事务， 使开发者可以原子地执行多个 Put 和 Get。 一旦有了事务，你就不再需要版本号 Put；事务取代了版本号 Put。 查看 etcd 的事务 了解接口示例。编写测试来演示你的扩展有效。
• 修改 shardkv 以支持事务， 使开发者可以跨分片原子地执行多个 Put 和 Get。 这需要实现两阶段提交和两阶段锁。 编写测试来演示你的扩展有效。

提交流程

$ make raft1
$ make kvraft1
$ make shardkv