6.5840 实验 4：容错键/值服务
介绍
在本实验中，你将使用 实验 3 中实现的 Raft 库构建一个容错的键/值存储服务。你的键/值服务将作为一个复制状态机运行，由多个键/值服务器组成，每个服务器维护一个键/值对数据库（与 实验 2 中类似），但额外使用 Raft 进行数据复制。只要多数服务器存活且能够互相通信，你的服务就应继续处理客户端请求，即使在其他服务器发生故障或出现网络分区的情况下也是如此。完成实验 4 后，你将实现 Raft 交互图 中展示的所有部分（Clerk、Service 和 Raft）。
客户端与键/值服务的交互方式与实验 2 大致相同。具体来说，客户端可以向键/值服务发送三种 RPC 请求：
- Put(key, value)：在数据库中替换指定 key 的值
- Append(key, arg)：将 arg 追加到指定 key 的值上（若 key 不存在，则视为其当前值为空字符串）
- Get(key)：获取指定 key 的当前值（若 key 不存在，则返回空字符串）
键和值均为字符串。注意，与实验 2 不同，Put 和 Append 不再向客户端返回值。每个客户端通过一个具有 Put/Append/Get 方法的 Clerk 与服务通信，该 Clerk 负责管理与各服务器间的 RPC 交互。
你的服务必须确保应用程序对 Clerk 的 Get/Put/Append 调用满足线性化要求。若这些调用是逐个进行的，则它们应表现得仿佛系统只有一份状态副本，每次调用都能观察到之前调用所做的状态修改；对于并发调用，其返回值和最终状态必须与操作以某个顺序逐个执行的结果一致。调用之间若存在时间重叠（例如，客户端 X 调用了 Clerk.Put()，客户端 Y 调用了 Clerk.Append()，随后客户端 X 的调用返回），则每次调用都必须能观察到所有在其开始前完成的调用的影响。
对于单个服务器来说，提供线性化较为简单；但当服务被复制时，由于所有服务器必须对并发请求选择相同的执行顺序，避免使用未更新状态回复客户端，并在故障后恢复状态时保持所有已确认的客户端更新，因此实现起来会更为复杂。
本实验分为两个部分：
- A 部分：使用你的 Raft 实现构建一个不使用快照的复制键/值服务。
- B 部分：利用你在实验 3D 中实现的快照功能，使 Raft 能够丢弃旧的日志条目，从而节省日志空间并加快重启速度。
请在各自截止日期前提交对应部分。
建议你阅读 扩展 Raft 论文，特别是其中的第 7 节和第 8 节；若想获得更广泛的视角，可参考 Chubby、Paxos Made Live、Spanner、Zookeeper、Harp、Viewstamped Replication 以及 Bolosky 等人 的论文。
请及早开始！
入门
我们在 src/kvraft 目录中为你提供了骨架代码和测试。你需要修改以下文件：
kvraft/client.gokvraft/server.go- 以及可能的
kvraft/common.go
要启动开发环境，请执行以下命令（别忘了先 git pull 获取最新代码）：
$ cd ~/6.5840
$ git pull
...
$ cd src/kvraft
$ go test
...
$Part A：不使用快照的键/值服务 (moderate/hard)
每个键/值服务器（以下简称 “kvserver”）都将拥有一个对应的 Raft 节点。Clerk 将向其所认为是领导者的 kvserver 发送 Put()、Append() 和 Get() RPC。kvserver 代码将把 Put/Append/Get 操作提交给 Raft，使得 Raft 日志中保存一系列的 Put/Append/Get 操作。所有 kvserver 按 Raft 日志的顺序执行操作，将操作应用到各自的键/值数据库中，其目标是让所有服务器维持一模一样的键/值数据库副本。
有时，Clerk 无法确定哪个 kvserver 是当前的 Raft 领导者。如果 Clerk 向错误的 kvserver 发送 RPC，或无法联系到 kvserver，则 Clerk 应重试并转而发送到其他 kvserver。如果键/值服务将操作成功提交到 Raft 日志中（并因此将操作应用于状态机），领导者会通过回复 RPC 将结果反馈给 Clerk；若操作未能提交（例如领导者被替换），服务器会返回错误，此时 Clerk 应重试向其他服务器发送请求。
注意：你的 kvserver 之间不应直接通信，而只能通过 Raft 进行交互。
你的第一个任务是实现一个在无消息丢失且服务器均正常工作的情况下可运行的方案。
- 你可以将实验 2 中 kvsrv/client.go 的客户端代码复制到 kvraft/client.go 中，但需要添加逻辑以决定将每个 RPC 发送到哪个 kvserver。请注意，Append() 不再向 Clerk 返回值。
- 你还需要在
server.go中实现 Put()、Append() 和 Get() 的 RPC 处理程序。这些处理程序应调用 Raft 的 Start() 将一个操作（Op）写入 Raft 日志；你需要在 server.go 中完善 Op 结构体定义，以描述 Put/Append/Get 操作。每个服务器应当按 Raft 日志的提交顺序执行操作，也就是在 applyCh 中读取到的操作。RPC 处理程序应注意在 Raft 提交其操作后，再回复对应的 RPC 请求。
当你的实现能可靠地通过测试套件中 “One client” 测试时，说明任务完成。
额外注意事项：
- 在调用 Start() 后，你的 kvserver 需要等待 Raft 达成一致。达成一致的命令会通过 applyCh 到达，你的代码需要不断读取 applyCh，同时 RPC 处理程序通过 Start() 向 Raft 提交命令。注意避免 kvserver 与 Raft 库之间的死锁。
- 如果 kvserver 不属于多数派，则不应完成 Get() RPC（以免提供过时数据）。一种简单的方案是将每个 Get（以及每个 Put 和 Append）都写入 Raft 日志，而无需实现第 8 节中描述的只读操作优化。
- 通常无需为 Raft 的 ApplyMsg 或如 AppendEntries 之类的 Raft RPC 添加额外字段，但你可以根据需要添加。
- 从一开始就添加锁机制较为明智，因为避免死锁的需求可能会影响整体代码设计。请使用
go test -race确保你的代码无竞态问题。
接下来，你需要修改你的方案，使其能够应对网络和服务器故障。一个常见问题是，一个 Clerk 可能需要多次发送 RPC 才能找到回复正确的 kvserver。例如，如果一个领导者在将条目提交到 Raft 日志后刚刚失败，Clerk 可能收不到回复，从而会将请求重发给另一个领导者。每次对 Clerk.Put() 或 Clerk.Append() 的调用都应只执行一次，因此你必须确保重发请求不会导致服务器多次执行相同请求。
为此，你需要添加代码来处理故障，并应对重复的 Clerk 请求，包括 Clerk 在一个任期中向 kvserver 领导者发送请求后因超时等待回复，再在新任期中向新领导者重发请求的情况。重发的请求应仅执行一次。相关指导请参阅 重复检测 文档。你的代码应能通过 go test -run 4A 的测试。
其他提示：
- 你的方案需要处理这样一种情况：一个领导者在调用 Start() 处理 Clerk 的 RPC 后，在请求提交日志之前失去领导地位。此时，你应安排 Clerk 重发请求至其他服务器，直到找到新的领导者。一个解决方案是：服务器检测到自己已失去领导地位（例如通过注意到 Raft 任期发生变化或在 Start() 返回的索引位置出现了不同的请求），从而让 Clerk 重试。若前任领导因分区而独自隔离，则它不会获知新领导者的信息；同一分区内的任何客户端也无法与新领导者通信，因此在这种情况下，服务器和客户端可以无限期等待，直到分区恢复。
- 你可能需要修改 Clerk，使其记住上一次哪个服务器被确定为领导者，并优先向该服务器发送下一个 RPC，这可以避免每次都浪费时间搜索领导者，从而帮助你更快地通过部分测试。
- 应采用与实验 2 类似的重复检测方案，该方案应能迅速释放服务器内存，例如通过每个 RPC 表明客户端已收到前一次 RPC 的回复。可以假设客户端一次只会调用 Clerk 的一个方法。你可能需要调整在实验 2 中存储于重复检测表中的信息。
完成上述修改后，你的代码应能通过 Lab 4A 测试，类似输出如下：
$ go test -run 4A
Test: one client (4A) ...
... Passed -- 15.5 5 4576 903
Test: ops complete fast enough (4A) ...
... Passed -- 15.7 3 3022 0
Test: many clients (4A) ...
... Passed -- 15.9 5 5884 1160
Test: unreliable net, many clients (4A) ...
... Passed -- 19.2 5 3083 441
Test: concurrent append to same key, unreliable (4A) ...
... Passed -- 2.5 3 218 52
Test: progress in majority (4A) ...
... Passed -- 1.7 5 103 2
Test: no progress in minority (4A) ...
... Passed -- 1.0 5 102 3
Test: completion after heal (4A) ...
... Passed -- 1.2 5 70 3
Test: partitions, one client (4A) ...
... Passed -- 23.8 5 4501 765
Test: partitions, many clients (4A) ...
... Passed -- 23.5 5 5692 974
Test: restarts, one client (4A) ...
... Passed -- 22.2 5 4721 908
Test: restarts, many clients (4A) ...
... Passed -- 22.5 5 5490 1033
Test: unreliable net, restarts, many clients (4A) ...
... Passed -- 26.5 5 3532 474
Test: restarts, partitions, many clients (4A) ...
... Passed -- 29.7 5 6122 1060
Test: unreliable net, restarts, partitions, many clients (4A) ...
... Passed -- 32.9 5 2967 317
Test: unreliable net, restarts, partitions, random keys, many clients (4A) ...
... Passed -- 35.0 7 8249 746
PASS
ok 6.5840/kvraft 290.184s每个 “Passed” 后面的数字分别表示实际运行时间（秒）、节点数、发送的 RPC 数量（包括客户端 RPC），以及执行的键/值操作次数（Clerk 的 Get/Put/Append 调用）。
Part B：使用快照的键/值服务 (hard)
目前，你的键/值服务器尚未调用 Raft 库的 Snapshot() 方法，因此在重启时需要重放完整的持久化 Raft 日志以恢复状态。现在，你需要修改 kvserver，使其与 Raft 协作，通过快照来节省日志空间并减少重启时间，使用的是实验 3D 中实现的 Snapshot()。
测试程序会将一个 maxraftstate 参数传递给你的 StartKVServer()。maxraftstate 指定了持久化 Raft 状态的最大允许字节数（包括日志，但不包括快照）。你应将 maxraftstate 与 persister.RaftStateSize() 进行比较。每当你的键/值服务器检测到 Raft 状态大小接近该阈值时，应通过调用 Raft 的 Snapshot() 来保存一个快照。如果 maxraftstate 为 -1，则无需进行快照。注意，maxraftstate 针对的是 Raft 传递给 persister.Save() 的经过 GOB 编码的字节。
请修改 kvserver，使其能检测到持久化的 Raft 状态增长过大，并将快照传递给 Raft。当 kvserver 重启时，应从 persister 中读取快照并恢复状态。
注意以下几点：
- 思考 kvserver 何时应该对其状态进行快照，以及快照中应包含哪些内容。Raft 使用 Save() 将每个快照与相应的 Raft 状态一起存储到 persister 对象中。你可以使用 ReadSnapshot() 读取最新存储的快照。
- kvserver 必须能够检测日志跨检查点的重复操作，因此用于重复检测的所有状态都必须包含在快照中。
- 存储在快照中的结构体所有字段的首字母必须大写。
- 该实验可能会暴露你 Raft 库中的 bug。如果你对 Raft 实现进行了修改，请确保它依然能通过所有实验 3 的测试。
- 对于实验 4 测试，合理的运行时间约为 400 秒的实际时间和 700 秒的 CPU 时间。另外，
go test -run TestSnapshotSize应在不到 20 秒的实际时间内完成。
你的代码应能同时通过 Lab 4B 测试和 Lab 4A 测试（并且 Raft 必须继续通过实验 3 的所有测试），例如：
$ go test -run 4B
Test: InstallSnapshot RPC (4B) ...
... Passed -- 4.0 3 289 63
Test: snapshot size is reasonable (4B) ...
... Passed -- 2.6 3 2418 800
Test: ops complete fast enough (4B) ...
... Passed -- 3.2 3 3025 0
Test: restarts, snapshots, one client (4B) ...
... Passed -- 21.9 5 29266 5820
Test: restarts, snapshots, many clients (4B) ...
... Passed -- 21.5 5 33115 6420
Test: unreliable net, snapshots, many clients (4B) ...
... Passed -- 17.4 5 3233 482
Test: unreliable net, restarts, snapshots, many clients (4B) ...
... Passed -- 22.7 5 3337 471
Test: unreliable net, restarts, partitions, snapshots, many clients (4B) ...
... Passed -- 30.4 5 2725 274
Test: unreliable net, restarts, partitions, snapshots, random keys, many clients (4B) ...
... Passed -- 37.7 7 8378 681
PASS
ok 6.5840/kvraft 161.538s