16 KiB
6.5840 Lab 5: Sharded Key/Value Service
简介
你可以选择做基于自己想法的期末项目，或做本实验。
本实验中你将构建一个 key/value 存储系统，在一组由 Raft 复制的 key/value 服务器组（shardgrps）上对 key 进行 "shard"（分片/分区）。一个 shard 是 key/value 对的一个子集；例如所有以 "a" 开头的 key 可以是一个 shard，以 "b" 开头的为另一个，等等。分片的目的是性能。每个 shardgrp 只处理少数 shard 的 put 和 get，各 shardgrp 并行工作；因此系统总吞吐（单位时间内的 put/get 数）随 shardgrp 数量增加。
分片 key/value 服务的组件见实验示意图。Shardgrps（蓝色方块）存储带 key 的 shard：shardgrp 1 存 key "a" 的 shard，shardgrp 2 存 key "b" 的 shard。客户端通过 clerk（绿色圆）与服务交互，clerk 实现 Get 和 Put 方法。为找到 Put/Get 所传 key 对应的 shardgrp，clerk 从 kvsrv（黑色方块，即你在 Lab 2 实现的）获取 configuration。Configuration 描述从 shard 到 shardgrp 的映射（例如 shard 1 由 shardgrp 3 服务）。
管理员（即测试程序）使用另一个客户端 controller（紫色圆）向集群添加/移除 shardgrp 并更新应由哪个 shardgrp 服务哪个 shard。Controller 有一个主要方法：ChangeConfigTo，以新 configuration 为参数，将系统从当前 configuration 切换到新 configuration；这涉及将 shard 迁移到新加入的 shardgrp、以及从即将离开的 shardgrp 迁出。为此 controller 1) 向 shardgrp 发 RPC（FreezeShard、InstallShard、DeleteShard），2) 更新存储在 kvsrv 中的 configuration。
引入 controller 是因为分片存储系统必须能在 shardgrp 之间迁移 shard：用于负载均衡，或当 shardgrp 加入、离开时（新容量、维修、下线）。
本实验的主要挑战是在 1) shard 到 shardgrp 的分配发生变化，以及 2) controller 在 ChangeConfigTo 期间失败或处于分区时恢复的情况下，保证 Get/Put 操作的 linearizability。
- 若 ChangeConfigTo 在重配置过程中失败，部分 shard 可能已开始但未完成从一 shardgrp 迁到另一 shardgrp，从而不可访问。测试会启动新的 controller；你的任务是确保新的能完成旧 controller 未完成的重配置。
- ChangeConfigTo 会在 shardgrp 之间迁移 shard。你必须保证任意时刻每个 shard 最多只有一个 shardgrp 在服务请求，这样使用旧 shardgrp 与新 shardgrp 的客户端不会破坏 linearizability。
本实验用 "configuration" 指 shard 到 shardgrp 的分配。这与 Raft 集群成员变更不是一回事；不需要实现 Raft 集群成员变更。
一个 shardgrp 服务器只属于一个 shardgrp。给定 shardgrp 内的服务器集合不会改变。
客户端与服务器之间的交互只能通过 RPC（不得使用共享 Go 变量或文件）。
- Part A：实现可用的 shardctrler（在 kvsrv 中存储/读取 configuration）、shardgrp（用 Raft rsm 复制）和 shardgrp clerk。shardctrler 通过 shardgrp clerk 迁移 shard。
- Part B：修改 shardctrler，在 configuration 变更期间处理故障与分区。
- Part C：允许多个 controller 并发且互不干扰。
- Part D：以任意方式扩展你的方案（可选）。
本实验的设计与 Flat Datacenter Storage、BigTable、Spanner、FAWN、Apache HBase、Rosebud、Spinnaker 等思路一致（细节不同）。
Lab 5 将使用你在 Lab 2 的 kvsrv，以及 Lab 4 的 rsm 和 Raft。Lab 5 与 Lab 4 必须使用相同的 rsm 和 Raft 实现。
迟交时长仅可用于 Part A；不能用于 Part B–D。
起步
执行 git pull 获取最新实验代码。
我们在 src/shardkv1 中提供了测试和骨架代码：
- shardctrler 包：
shardctrler.go，包含 controller 变更 configuration 的 ChangeConfigTo 和获取 configuration 的 Query - shardgrp 包：shardgrp clerk 与 server
- shardcfg 包：计算 shard configuration
- client.go：shardkv clerk
运行以下命令即可开始：
$ cd ~/6.5840
$ git pull
...
$ cd src/shardkv1
$ go test -v
=== RUN TestInitQuery5A
Test (5A): Init and Query ... (reliable network)...
shardkv_test.go:46: Static wrong null 0
...
Part A: 迁移 Shard（困难）
第一个任务是：在无故障时实现 shardgrp 以及 InitConfig、Query、ChangeConfigTo。Configuration 的代码在 shardkv1/shardcfg。每个 shardcfg.ShardConfig 有唯一编号 Num、从 shard 编号到 group 编号的映射、以及从 group 编号到复制该 group 的服务器列表的映射。通常 shard 数多于 group 数，以便以较细粒度调整负载。
1. InitConfig 与 Query（尚无 shardgrp）
在 shardctrler/shardctrler.go 中实现：
- Query：返回当前 configuration；从 kvsrv 读取（由 InitConfig 存储）。
- InitConfig：接收第一个 configuration（测试程序提供的 shardcfg.ShardConfig）并存入 Lab 2 的 kvsrv 实例。
用 ShardCtrler.IKVClerk 的 Get/Put 与 kvsrv 通信，用 ShardConfig.String() 序列化后 Put，用 shardcfg.FromString() 反序列化。通过第一个测试时即完成：
$ cd ~/6.5840/src/shardkv1
$ go test -run TestInitQuery5A
Test (5A): Init and Query ... (reliable network)...
... Passed -- time 0.0s #peers 1 #RPCs 3 #Ops 0
PASS
ok 6.5840/shardkv1 0.197s
2. Shardgrp 与 shardkv clerk（Static 测试）
通过从 Lab 4 kvraft 方案复制，在 shardkv1/shardgrp/server.go 实现 shardgrp 的初始版本，在 shardkv1/shardgrp/client.go 实现 shardgrp clerk。在 shardkv1/client.go 实现 shardkv clerk：用 Query 找到 key 对应的 shardgrp，再与该 shardgrp 通信。通过 Static 测试时即完成。
- 创建时，第一个 shardgrp（shardcfg.Gid1）应将自己初始化为拥有所有 shard。
- shardkv1/client.go 的 Put 在回复可能丢失时必须返回 ErrMaybe；内部（shardgrp）的 Put 可用错误表示这一点。
- 要向 shardgrp put/get 一个 key，shardkv clerk 应通过 shardgrp.MakeClerk 创建 shardgrp clerk，传入 configuration 中的服务器以及 shardkv clerk 的 ck.clnt。用 ShardConfig.GidServers() 获取 shard 的 group。
- 用 shardcfg.Key2Shard() 得到 key 的 shard 编号。测试程序将 ShardCtrler 传给 shardkv1/client.go 的 MakeClerk；用 Query 获取当前 configuration。
- 可从 kvraft 的 client.go 和 server.go 复制 Put/Get 及相关代码。
$ cd ~/6.5840/src/shardkv1
$ go test -run Static
Test (5A): one shard group ... (reliable network)...
... Passed -- time 5.4s #peers 1 #RPCs 793 #Ops 180
PASS
ok 6.5840/shardkv1 5.632s
3. ChangeConfigTo 与 shard 迁移（JoinBasic、DeleteBasic）
通过实现 ChangeConfigTo 支持在 group 之间迁移 shard：从旧 configuration 切换到新 configuration。新 configuration 可能加入新 shardgrp 或移除现有 shardgrp。Controller 必须迁移 shard 数据，使每个 shardgrp 存储的 shard 与新 configuration 一致。
迁移一个 shard 的建议流程：
- 在源 shardgrp Freeze 该 shard（该 shardgrp 拒绝对该迁移中 shard 的 key 的 Put）。
- Install（复制）该 shard 到目标 shardgrp。
- 在源端 Delete 已 freeze 的 shard。
- Post 新 configuration，使客户端能找到迁移后的 shard。
这样避免 shardgrp 之间直接交互，并允许继续服务未参与变更的 shard。
顺序：每个 configuration 有唯一 Num（见 shardcfg/shardcfg.go）。Part A 中测试程序顺序调用 ChangeConfigTo；新 config 的 Num 比前一个大 1。为拒绝过时 RPC，FreezeShard、InstallShard、DeleteShard 应包含 Num（见 shardgrp/shardrpc/shardrpc.go），且 shardgrp 须记住每个 shard 见过的最大 Num。
在 shardctrler/shardctrler.go 中实现 ChangeConfigTo，并扩展 shardgrp 支持 freeze、install、delete。在 shardgrp/client.go 和 shardgrp/server.go 中实现 FreezeShard、InstallShard、DeleteShard，使用 shardgrp/shardrpc 中的 RPC，并根据 Num 拒绝过时 RPC。修改 shardkv1/client.go 中的 shardkv clerk 以处理 ErrWrongGroup（当 shardgrp 不负责该 shard 时返回）。先通过 JoinBasic 和 DeleteBasic（加入 group；离开可稍后）。
- 像 Put 和 Get 一样，通过你的 rsm 包执行 FreezeShard、InstallShard、DeleteShard。
- 若 RPC 回复中包含属于服务器状态的 map，可能产生数据竞争；在回复中附带该 map 的副本。
- 可以在 RPC 请求/回复中发送整个 map，使 shard 迁移代码更简单。
- 若 Put/Get 的 key 的 shard 未分配给该 shardgrp，shardgrp 应返回 ErrWrongGroup；shardkv1/client.go 应重新读取 configuration 并重试。
4. 离开的 Shardgrps（TestJoinLeaveBasic5A）
扩展 ChangeConfigTo 以处理离开的 shardgrp（在当前 config 中但不在新 config 中）。通过 TestJoinLeaveBasic5A。
5. 全部 Part A 测试
你的方案必须在 configuration 变更进行时继续服务未受影响的 shard。通过全部 Part A 测试：
$ cd ~/6.5840/src/shardkv1
$ go test -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): many concurrent clerks unreliable... (unreliable network)...
... Passed -- time 25.3s #peers 1 #RPCs 7553 #Ops 1896
PASS
ok 6.5840/shardkv1 243.115s
Part B: 处理失败的 Controller（简单）
Controller 生命周期短，在迁移 shard 时可能失败或失去连接。任务是在启动新 controller 时恢复：新 controller 必须完成前一个未完成的重配置。测试程序在启动 controller 时调用 InitController；你可以在其中实现恢复。
做法：在 controller 的 kvsrv 中维护两个 configuration：current 和 next。Controller 开始重配置时存储 next configuration。完成时把 next 变为 current。在 InitController 中，若存在存储的 next configuration 且其 Num 大于 current，则完成 shard 迁移以重配置到该 next config。
从前一个失败 controller 继续的 controller 可能重复 FreezeShard、InstallShard、Delete RPC；shardgrp 可用 Num 检测重复并拒绝。
在 shardctrler 中实现上述逻辑。通过 Part B 测试时即完成：
$ cd ~/6.5840/src/shardkv1
$ go test -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
- 在 shardctrler/shardctrler.go 的 InitController 中实现恢复。
Part C: 并发 Configuration 变更（中等）
修改 controller 以允许多个 controller 并发。当某个失败或处于分区时，测试会启动新的，新 controller 必须完成任何进行中的工作（同 Part B）。因此多个 controller 可能并发运行，向 shardgrp 和 kvsrv 发 RPC。
挑战：确保 controller 互不干扰。Part A 中你已用 Num 对 shardgrp RPC 做 fencing，过时 RPC 会被拒绝；多个 controller 的重复工作是安全的。剩余问题是只有一个 controller 应更新 next configuration，这样两个 controller（例如分区中的与新的）不会为同一 Num 写入不同 config。测试会并发运行多个 controller；每个读取当前 config、为 join/leave 更新、然后调用 ChangeConfigTo——因此多个 controller 可能用同一 Num 的不同 config 调用 ChangeConfigTo。可使用 version 与带 version 的 Put，使只有一个 controller 能成功提交该 Num 的 next config，其他直接返回不做任何事。
修改 controller，使对给定 configuration Num 只有一个 controller 能提交 next configuration。通过并发测试：
$ cd ~/6.5840/src/shardkv1
$ go test -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
$ go test -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 了解测试如何并发运行 controller。
恢复 + 新 controller：新 controller 仍应执行 Part B 的恢复。若旧 controller 在 ChangeConfigTo 期间处于分区，确保旧的不干扰新的。若所有 controller 更新都用 Num 正确 fencing（Part B），可能不需要额外代码。通过 Partition 测试：
$ go test -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 ... (unreliable network)...
... Passed -- time 60.5s #peers 1 #RPCs 11422 #Ops 2336
PASS
ok 6.5840/shardkv1 217.779s
重新运行全部测试，确保最近的 controller 修改没有破坏前面的部分。
Gradescope 会运行 Lab 3A–D、Lab 4A–C 和 5C 测试。提交前：
$ go test ./raft1
$ go test ./kvraft1
$ go test ./shardkv1
Part D: 扩展你的方案
在这最后一部分你可以以任意方式扩展你的方案。你必须为自己的扩展编写测试。
实现下列想法之一或你自己的想法。在 extension.md 中写一段话描述你的扩展，并将 extension.md 上传到 Gradescope。对较难、开放式的扩展，可与另一名同学组队。
想法（前几个较易，后面更开放）：
- （难） 修改 shardkv 以支持事务（跨 shard 的多个 Put 和 Get 原子执行）。实现两阶段提交与两阶段锁。编写测试。
- （难） 在 kvraft 中支持事务（多个 Put/Get 原子）。这样带 version 的 Put 不再必要。参见 etcd's transactions。编写测试。
- （难） 让 kvraft leader 不经 rsm 直接处理 Get（Raft 论文 Section 8 末尾的优化，含 leases），并保持 linearizability。通过现有 kvraft 测试。增加测试：优化后的 Get 更快（如更少 RPC）、以及 term 切换更慢（新 leader 等待 lease 过期）。
- （中等） 为 kvsrv 增加 Range 函数（从 low 到 high 的 key）。偷懒做法：遍历 key/value map；更好做法：支持范围查询的数据结构（如 B-tree）。包含一个在偷懒实现下失败、在更好实现下通过的测试。
- （中等） 将 kvsrv 改为 恰好一次 Put/Get 语义（如 Lab 2 丢包风格）。在 kvraft 中也实现恰好一次。可移植 2024 的测试。
- （简单） 修改测试程序，使 controller 使用 kvraft 而非 kvsrv（例如在 test.go 的 MakeTestMaxRaft 中用 kvraft.StartKVServer 替换 kvsrv.StartKVServer）。编写测试：在一个 kvraft 节点宕机时 controller 仍能查询/更新 configuration。测试代码在 src/kvtest1、src/shardkv1、src/tester1。
提交步骤
提交前最后运行一遍全部测试：
$ go test ./raft1
$ go test ./kvraft1
$ go test ./shardkv1