15 KiB
6.5840 Lab 4: Fault-tolerant Key/Value Service
简介
在本实验中你将使用 Lab 3 的 Raft 库构建一个容错 key/value 存储服务。对客户端而言，该服务与 Lab 2 的服务器类似。但服务不是单台服务器，而是由一组使用 Raft 保持数据库一致的服务器组成。只要多数（majority）服务器存活且能通信，你的 key/value 服务就应继续处理客户端请求，即使存在其他故障或网络分区。完成 Lab 4 后，你将实现 Raft 交互图中所示的全部部分（Clerk、Service 和 Raft）。
客户端通过 Clerk 与你的 key/value 服务交互，与 Lab 2 相同。Clerk 实现的 Put 和 Get 方法与 Lab 2 语义一致：Put 为至多一次，Put/Get 必须形成 linearizable 历史。
对单机而言提供 linearizability 相对容易。在复制服务中更难，因为所有服务器必须对并发请求选择相同的执行顺序、必须避免用未更新的状态回复客户端、且必须在故障后以保留所有已确认客户端更新的方式恢复状态。
本实验分三个部分。在 Part A 中，你将用你的 Raft 实现一个与具体请求无关的复制状态机包 rsm。在 Part B 中，你将用 rsm 实现一个复制的 key/value 服务，但不使用快照。在 Part C 中，你将使用 Lab 3D 的快照实现，使 Raft 能丢弃旧日志条目。请分别在各自截止日前提交各部分。
建议复习 Raft 扩展论文，尤其是 Section 7（不含 8）。更广视角可参阅 Chubby、Paxos Made Live、Spanner、Zookeeper、Harp、Viewstamped Replication 以及 Bolosky et al。
尽早开始。
起步
我们在 src/kvraft1 中提供了骨架代码和测试。骨架使用 src/kvraft1/rsm 包复制服务器。服务器必须实现 rsm 中定义的 StateMachine 接口才能通过 rsm 复制自身。你的主要工作是在 rsm 中实现与具体服务器无关的复制逻辑。此外需要修改 kvraft1/client.go 和 kvraft1/server.go 实现服务器相关部分。这种拆分便于在下一实验复用 rsm。可以复用部分 Lab 2 代码（例如复制或导入 "src/kvsrv1" 包中的服务器代码），但非必须。
运行以下命令即可开始。别忘了 git pull 获取最新代码。
$ cd ~/6.5840
$ git pull
...
Part A: Replicated State Machine (RSM)
$ cd src/kvraft1/rsm
$ go test -v
=== RUN TestBasic
Test RSM basic (reliable network)...
..
config.go:147: one: took too long
在使用 Raft 复制的常见客户端/服务架构中，服务与 Raft 有两种交互：服务 leader 通过调用 raft.Start() 提交客户端操作，所有服务副本通过 Raft 的 applyCh 接收已提交的操作并执行。在 leader 上，这两类活动会交织：某些服务器 goroutine 在处理客户端请求、已调用 raft.Start()，各自在等待其操作提交并得到执行结果；而 applyCh 上出现的已提交操作需要由服务执行，且结果需交给曾调用 raft.Start() 的 goroutine 以便返回给客户端。
rsm 包封装上述交互。它位于服务（如 key/value 数据库）与 Raft 之间。你需要在 rsm/rsm.go 中实现：
- 一个**“reader” goroutine**，读取 applyCh
- 一个 rsm.Submit() 函数，为客户端操作调用 raft.Start()，然后等待 reader goroutine 把该操作的执行结果交回
使用 rsm 的服务对 rsm 的 reader goroutine 呈现为提供 DoOp() 方法的 StateMachine 对象。Reader goroutine 应将每条已提交操作交给 DoOp()；DoOp() 的返回值应交给对应的 rsm.Submit() 调用并返回。DoOp() 的参数和返回值类型为 any；实际类型应分别与服务传给 rsm.Submit() 的参数和返回值类型一致。
服务应将每个客户端操作传给 rsm.Submit()。为便于 reader goroutine 将 applyCh 消息与等待中的 rsm.Submit() 调用对应，Submit() 应将每个客户端操作与一个唯一标识一起包装进 Op 结构。Submit() 然后等待该操作提交并执行完毕，返回执行结果（DoOp() 的返回值）。若 raft.Start() 表明当前节点不是 Raft leader，Submit() 应返回 rpc.ErrWrongLeader 错误。Submit() 须检测并处理这种情况：在调用 raft.Start() 后 leadership 发生变化，导致该操作丢失（从未提交）。
在 Part A 中，rsm 测试程序充当服务，提交被解释为对单个整数状态做自增的操作。Part B 中你将把 rsm 用作实现 StateMachine（及 DoOp()）并调用 rsm.Submit() 的 key/value 服务的一部分。
顺利时，一次客户端请求的事件序列为：
- 客户端向服务 leader 发送请求。
- 服务 leader 用该请求调用 rsm.Submit()。
- rsm.Submit() 用该请求调用 raft.Start()，然后等待。
- Raft 提交该请求并向所有节点的 applyCh 发送。
- 每个节点上的 rsm reader goroutine 从 applyCh 读取该请求并交给服务的 DoOp()。
- 在 leader 上，rsm reader goroutine 将 DoOp() 的返回值交给最初提交该请求的 Submit() goroutine，Submit() 返回该值。
你的服务器之间不应直接通信；它们只应通过 Raft 交互。
实现 rsm.go：Submit() 方法以及 reader goroutine。当通过 rsm 的 4A 测试时，该任务即完成：
$ cd src/kvraft1/rsm
$ go test -v -run 4A
=== RUN TestBasic4A
Test RSM basic (reliable network)...
... Passed -- 1.2 3 48 0
--- PASS: TestBasic4A (1.21s)
=== RUN TestLeaderFailure4A
... Passed -- 9223372036.9 3 31 0
--- PASS: TestLeaderFailure4A (1.50s)
PASS
ok 6.5840/kvraft1/rsm 2.887s
- 不应需要给 Raft 的 ApplyMsg 或 AppendEntries 等 Raft RPC 增加字段，但允许这样做。
- 你的方案须处理：rsm leader 已为 Submit() 提交的请求调用了 Start()，但在该请求提交到日志前失去了 leadership。一种做法是 rsm 通过发现 Raft 的 term 已变或 Start() 返回的 index 处出现了不同请求，检测到已失去 leadership，并从 Submit() 返回 rpc.ErrWrongLeader。若旧 leader 独自处于分区中，它无法得知新 leader；但同一分区内的客户端也无法联系新 leader，因此服务器无限等待直到分区恢复是可以接受的。
- 测试在关闭节点时会调用你的 Raft 的 rf.Kill()。Raft 应关闭 applyCh，以便 rsm 得知关闭并退出所有循环。
Part B: 无快照的 Key/value 服务
$ cd src/kvraft1
$ go test -v -run TestBasic4B
=== RUN TestBasic4B
Test: one client (4B basic) (reliable network)...
kvtest.go:62: Wrong error
$
现在用 rsm 包复制 key/value 服务器。每台服务器（"kvserver"）对应一个 rsm/Raft 节点。Clerk 向与 Raft leader 对应的 kvserver 发送 Put() 和 Get() RPC。kvserver 代码将 Put/Get 操作提交给 rsm，rsm 通过 Raft 复制并在每个节点调用你服务器的 DoOp，将操作应用到该节点的 key/value 数据库；目标是使各服务器维护一致的 key/value 数据库副本。
Clerk 有时不知道哪台 kvserver 是 Raft leader。若 Clerk 向错误的 kvserver 发 RPC 或无法到达该 kvserver，Clerk 应重试，向其他 kvserver 发送。若 key/value 服务将操作提交到其 Raft 日志（从而应用到 key/value 状态机），leader 通过回复该 RPC 将结果报告给 Clerk。若操作未提交（例如 leader 被替换），服务器报告错误，Clerk 向其他服务器重试。
你的 kvserver 之间不应直接通信；它们只应通过 Raft 交互。
第一个任务是实现在无丢包、无服务器失败时正确的方案。
可以将 Lab 2 的客户端代码（kvsrv1/client.go）复制到 kvraft1/client.go。需要增加决定每次 RPC 发往哪台 kvserver 的逻辑。
还需在 server.go 中实现 Put() 和 Get() 的 RPC 处理函数。这些处理函数应通过 rsm.Submit() 将请求提交给 Raft。rsm 包从 applyCh 读取命令时，会调用 DoOp 方法，你将在 server.go 中实现。
当你能稳定通过测试套件中第一个测试（go test -v -run TestBasic4B）时，该任务即完成。
- 若 kvserver 不处于多数，则不应完成 Get() RPC（以免提供过期数据）。一种简单做法是像每个 Put() 一样，通过 Submit() 把每个 Get() 也写入 Raft 日志。不必实现论文 Section 8 中只读操作的优化。
- 最好从一开始就加锁，因为避免死锁有时会影响整体代码设计。用 go test -race 检查代码无数据竞争。
接下来应修改方案以在网络和服务器故障下继续正确工作。你会遇到的一个问题是 Clerk 可能需多次发送 RPC 才能找到能正常回复的 kvserver。若 leader 在将条目提交到 Raft 日志后立即失败，Clerk 可能收不到回复，从而向另一台 leader 重发请求。对同一 version 的每次 Clerk.Put() 调用应只执行一次。
加入故障处理代码。 你的 Clerk 可采用与 lab 2 类似的重试策略，包括在重试的 Put RPC 的回复丢失时返回 ErrMaybe。当你的代码能稳定通过全部 4B 测试（go test -v -run 4B）时，即完成。
- 回忆：rsm leader 可能失去 leadership 并从 Submit() 返回 rpc.ErrWrongLeader。此时应让 Clerk 向其他服务器重发请求直到找到新 leader。
- 可能需要修改 Clerk，使其记住上一轮 RPC 中哪台服务器是 leader，并优先将下一轮 RPC 发往该服务器。这样可避免每次 RPC 都重新找 leader，有助于在限定时间内通过部分测试。
你的代码此时应能通过 Lab 4B 测试，例如：
$ cd kvraft1
$ go test -run 4B
Test: one client (4B basic) ...
... Passed -- 3.2 5 1041 183
Test: one client (4B speed) ...
... Passed -- 15.9 3 3169 0
Test: many clients (4B many clients) ...
... Passed -- 3.9 5 3247 871
Test: unreliable net, many clients (4B unreliable net, many clients) ...
... Passed -- 5.3 5 1035 167
Test: unreliable net, one client (4B progress in majority) ...
... Passed -- 2.9 5 155 3
Test: no progress in minority (4B) ...
... Passed -- 1.6 5 102 3
Test: completion after heal (4B) ...
... Passed -- 1.3 5 67 4
Test: partitions, one client (4B partitions, one client) ...
... Passed -- 6.2 5 958 155
Test: partitions, many clients (4B partitions, many clients (4B)) ...
... Passed -- 6.8 5 3096 855
Test: restarts, one client (4B restarts, one client 4B ) ...
... Passed -- 6.7 5 311 13
Test: restarts, many clients (4B restarts, many clients) ...
... Passed -- 7.5 5 1223 95
Test: unreliable net, restarts, many clients (4B unreliable net, restarts, many clients ) ...
... Passed -- 8.4 5 804 33
Test: restarts, partitions, many clients (4B restarts, partitions, many clients) ...
... Passed -- 10.1 5 1308 105
Test: unreliable net, restarts, partitions, many clients (4B unreliable net, restarts, partitions, many clients) ...
... Passed -- 11.9 5 1040 33
Test: unreliable net, restarts, partitions, random keys, many clients (4B unreliable net, restarts, partitions, random keys, many clients) ...
... Passed -- 12.1 7 2801 93
PASS
ok 6.5840/kvraft1 103.797s
每个 Passed 后的数字依次为：实际时间（秒）、节点数、发送的 RPC 数（含客户端 RPC）、执行的 key/value 操作数（Clerk Get/Put 调用）。
Part C: 带快照的 Key/value 服务
目前你的 key/value 服务器没有调用 Raft 库的 Snapshot() 方法，因此重启的服务器必须重放完整持久化 Raft 日志才能恢复状态。现在将修改 kvserver 和 rsm，与 Raft 协作以节省日志空间并缩短重启时间，使用 Lab 3D 的 Raft Snapshot()。
测试程序将 maxraftstate 传给你的 StartKVServer()，你再传给 rsm。maxraftstate 表示持久化 Raft 状态的最大允许大小（字节），含日志但不含快照。应将 maxraftstate 与 rf.PersistBytes() 比较。每当 rsm 检测到 Raft 状态大小接近该阈值时，应通过调用 Raft 的 Snapshot 保存快照。rsm 可通过调用 StateMachine 接口的 Snapshot 方法获取 kvserver 的快照来创建该快照。若 maxraftstate 为 -1，则不必做快照。maxraftstate 限制适用于你的 Raft 作为第一个参数传给 persister.Save() 的 GOB 编码字节。
persister 对象的源码在 tester1/persister.go。
修改你的 rsm，使其在检测到持久化 Raft 状态过大时向 Raft 提交快照。rsm 服务器重启时，应用 persister.ReadSnapshot() 读取快照，若快照长度大于零则传给 StateMachine 的 Restore() 方法。当通过 rsm 的 TestSnapshot4C 时，该任务即完成。
$ cd kvraft1/rsm
$ go test -run TestSnapshot4C
=== RUN TestSnapshot4C
... Passed -- 9223372036.9 3 230 0
--- PASS: TestSnapshot4C (3.88s)
PASS
ok 6.5840/kvraft1/rsm 3.882s
- 考虑 rsm 何时应对状态做快照，以及快照中除服务器状态外还应包含什么。Raft 用 Save() 将每个快照与对应 Raft 状态一起存入 persister。可用 ReadSnapshot() 读取最新存储的快照。
- 快照中存储的结构体所有字段名首字母大写。
实现 kvraft1/server.go 中的 Snapshot() 和 Restore() 方法，供 rsm 调用。修改 rsm 以处理 applyCh 上包含快照的消息。
- 该任务可能暴露出 Raft 和 rsm 库中的 bug。若修改了 Raft 实现，请确保其仍能通过全部 Lab 3 测试。
- Lab 4 测试的合理耗时为实际时间 400 秒、CPU 时间 700 秒。
你的代码应通过 4C 测试（如下例），以及 4A+B 测试（且 Raft 须继续通过 Lab 3 测试）。
$ go test -run 4C
Test: snapshots, one client (4C SnapshotsRPC) ...
Test: InstallSnapshot RPC (4C) ...
... Passed -- 4.5 3 241 64
Test: snapshots, one client (4C snapshot size is reasonable) ...
... Passed -- 11.4 3 2526 800
Test: snapshots, one client (4C speed) ...
... Passed -- 14.2 3 3149 0
Test: restarts, snapshots, one client (4C restarts, snapshots, one client) ...
... Passed -- 6.8 5 305 13
Test: restarts, snapshots, many clients (4C restarts, snapshots, many clients ) ...
... Passed -- 9.0 5 5583 795
Test: unreliable net, snapshots, many clients (4C unreliable net, snapshots, many clients) ...
... Passed -- 4.7 5 977 155
Test: unreliable net, restarts, snapshots, many clients (4C unreliable net, restarts, snapshots, many clients) ...
... Passed -- 8.6 5 847 33
Test: unreliable net, restarts, partitions, snapshots, many clients (4C unreliable net, restarts, partitions, snapshots, many clients) ...
... Passed -- 11.5 5 841 33
Test: unreliable net, restarts, partitions, snapshots, random keys, many clients (4C unreliable net, restarts, partitions, snapshots, random keys, many clients) ...
... Passed -- 12.8 7 2903 93
PASS
ok 6.5840/kvraft1 83.543s