6.5840 - 2026年春季

6.5840 实验 4: 容错键值服务

协作政策 // 提交实验 // 配置Go // 指导 // Piazza

介绍

在本实验中，你将使用实验 3中的 Raft 库构建一个容错的键值存储服务。对客户端来说，该服务看起来与实验 2中的服务器类似。然而，与单个服务器不同，该服务由一组服务器组成，它们使用 Raft 来帮助维护相同的数据库。你的键值服务应在大多数服务器存活且能通信的情况下继续处理客户端请求，尽管存在其他故障或网络分区。在实验 4 之后，你将实现 Raft 交互图中显示的所有部分（Clerk、Service 和 Raft）。

客户端将通过 Clerk 与你的键值服务交互，就像在实验 2 中一样。 Clerk 实现的 Put 和 Get 方法与实验 2 具有相同的语义： Put 是至多一次的，并且 Put/Get 必须形成线性可序列化的历史。

对于单个服务器来说，提供线性可序列化是相对容易的。如果服务是复制的则更难，因为所有服务器必须为并发请求选择相同的执行顺序，必须避免使用不是最新的状态回复客户端，并且必须以保留所有已确认客户端更新的方式在故障后恢复其状态。

本实验有三个部分。在部分 A 中，你将使用你的 Raft 实现一个复制状态机包 rsm；rsm 对其复制的请求是无感知的。在部分 B 中，你将使用 rsm 实现一个复制键值服务，但不使用快照。在部分 C 中，你将使用实验 3D 中的快照实现，这将允许 Raft 丢弃旧日志条目。请在各自的截止日期前提交每个部分。

你应该复习Raft 扩展论文，特别是第 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。你可能可以重用一些实验 2 的代码（例如，通过复制或导入 "src/kvsrv1" 包来重用服务器代码），但这不是必需的。

要开始运行，请执行以下命令。别忘了 git pull 来获取最新的软件。

$ cd ~/6.5840
$ git pull
..

部分 A: 复制状态机 (RSM)

$ cd src
$ make rsm1
=== RUN   TestBasic4A
Test RSM basic (reliable network)...
    rsm_test.go:28: expected 0 instead of 0

在客户端/服务器服务使用 Raft 进行复制的常见场景中，服务与 Raft 的交互有两种方式：服务领导者通过调用 raft.Start() 提交客户端操作，所有服务副本通过 Raft 的 applyCh 接收已提交的操作并执行它们。在领导者上，这两个活动会交互。在任何给定时间，一些服务器 goroutine 正在处理客户端请求，已调用 raft.Start()，并且每个都在等待其操作提交并找出执行操作的结果。当已提交的操作出现在 applyCh 上时，每个都需要被服务执行，结果需要传递给调用 raft.Start() 的 goroutine，以便它能将结果返回给客户端。

rsm 包封装了上述交互。它作为服务（例如键值数据库）和 Raft 之间的一层。在 rsm/rsm.go 中，你需要实现一个读取 applyCh 的 "reader" goroutine，以及一个 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 领导者， Submit() 应返回 rpc.ErrWrongLeader 错误。 Submit() 应检测并处理在调用 raft.Start() 之后领导权刚刚改变，导致操作丢失（从未提交）的情况。

对于部分 A，rsm 测试器充当服务，提交它解释为对由单个整数组成的状态进行递增的操作。在部分 B 中，你将使用 rsm 作为实现 StateMachine（和 DoOp()）并调用 rsm.Submit() 的键值服务的一部分。

如果一切顺利，客户端请求的事件序列是：

客户端向服务领导者发送请求。
服务领导者使用请求调用 rsm.Submit()。
rsm.Submit() 使用请求调用 raft.Start()，然后等待。
Raft 提交请求并将其发送到所有对等体的 applyCh。
每个对等体上的 rsm reader goroutine 从 applyCh 读取请求并将其传递给服务的 DoOp()。
在领导者上，rsm reader goroutine 将 DoOp() 返回值传递给最初提交请求的 Submit() goroutine， Submit() 返回该值。

实现 rsm.go：Submit() 方法和 reader goroutine。如果你通过了 rsm 的 4A 测试，即完成了此任务：

  $ cd src
  $ make RUN="-run 4A" rsm1
go build -race -o main/rsm1d main/rsm1d.go
cd kvraft1/rsm; go test -v -race -run 4A 
=== RUN   TestBasic4A
Test RSM basic (reliable network)...
  ... Passed --  time  4.2s #peers 3 #RPCs    50 #Ops   10
--- PASS: TestBasic4A (4.57s)
=== RUN   TestConcurrent4A
Test concurrent submit (reliable network)...
  ... Passed --  time  1.0s #peers 3 #RPCs    28 #Ops   50
--- PASS: TestConcurrent4A (1.39s)
=== RUN   TestLeaderFailure4A
Test Leader Failure (reliable network)...
  ... Passed --  time  2.9s #peers 3 #RPCs    32 #Ops    2
--- PASS: TestLeaderFailure4A (3.29s)
=== RUN   TestLeaderPartition4A
Test Leader Partition (reliable network)...
2026/03/11 10:43:46 partition leader 0
  ... Passed --  time  3.6s #peers 3 #RPCs    61 #Ops    2
--- PASS: TestLeaderPartition4A (4.04s)
=== RUN   TestRestartReplay4A
Test Restart (reliable network)...
  ... Passed --  time  28.4s #peers 3 #RPCs   467 #Ops  101
--- PASS: TestRestartReplay4A (28.79s)
=== RUN   TestShutdown4A
Test Shutdown (reliable network)...
  ... Passed --  time  10.0s #peers 3 #RPCs     0 #Ops    0
--- PASS: TestShutdown4A (10.38s)
=== RUN   TestRestartSubmit4A
Test Restart and submit (reliable network)...
  ... Passed --  time  39.8s #peers 3 #RPCs   463 #Ops  102
--- PASS: TestRestartSubmit4A (40.21s)
PASS
ok  	6.5840/kvraft1/rsm	93.691s

你不需要向 Raft 的 ApplyMsg 或 Raft RPC（如 AppendEntries）添加任何字段，但允许你这样做。
你的解决方案需要处理 rsm 领导者已为使用 Submit() 提交的请求调用了 Start()，但在请求提交到日志之前失去了领导权的情况。一种方法是让 rsm 通过注意到 Raft 的 term 已改变或在 Start() 返回的索引处出现了不同的请求来检测它已失去领导权，并从 Submit() 返回 rpc.ErrWrongLeader。如果前领导者被单独分区，它不会知道新领导者；但同一分区中的任何客户端也无法与新领导者通信，所以在这种情况下服务器无限等待直到分区恢复是可以的。

部分 B: 不使用快照的键值服务

$ cd src
$ make RUN="-run 4B" kvraft1
go build -race -o main/kvraft1d main/kvraft1d.go
cd kvraft1 && go test -v -race -run 4B 
=== RUN   TestBasic4B
Test: one client (4B basic) (reliable network)...
Fatal: Wrong error

现在你将使用 rsm 包来复制键值服务器。每个服务器（"kvserver"）将有一个关联的 rsm/Raft 对等体。 Clerk 将 Put() 和 Get() RPC 发送给其关联 Raft 是领导者的 kvserver。 kvserver 代码将 Put/Get 操作提交给 rsm， rsm 使用 Raft 复制它并在每个对等体上调用你的服务器的 DoOp，它应将操作应用到对等体的键值数据库；目的是让服务器维护键值数据库的相同副本。

Clerk 有时不知道哪个 kvserver 是 Raft 领导者。如果 Clerk 将 RPC 发送给错误的 kvserver，或者无法到达 kvserver，Clerk 应通过发送给不同的 kvserver 来重试。如果键值服务将操作提交到其 Raft 日志（因此将操作应用到键值状态机），领导者通过响应其 RPC 将结果报告给 Clerk。如果操作未能提交（例如，如果领导者被替换），服务器报告错误，Clerk 使用不同的服务器重试。

你的第一个任务是实现一个在没有丢包且没有服务器故障时能正常工作的方案。

欢迎将你的客户端代码从实验 2（kvsrv1/client.go）复制到 kvraft1/client.go。你需要添加逻辑来决定将每个 RPC 发送给哪个 kvserver。

你还需要在 server.go 中实现 Put() 和 Get() RPC 处理函数。这些处理函数应使用 rsm.Submit() 将请求提交给 Raft。当 rsm 包从 applyCh 读取命令时，它应调用 DoOp 方法，你需要在 server.go 中实现它。

当你稳定地通过测试套件中的第一个测试时，即完成了此任务，使用 make RUN="-run TestBasic4B" kvraft1。

kvserver 不应该在不是大多数的一部分时完成 Get() RPC（这样它就不会提供过时数据）。一个简单的解决方案是使用 Submit() 将每个 Get()（以及每个 Put()）记录到 Raft 日志中。你不需要实现第 8 节中描述的只读操作的优化。
最好从一开始就添加锁，因为避免死锁的需要有时会影响整体代码设计。测试器默认使用竞争检测器运行你的代码。

现在你应该修改你的解决方案，使其在网络和服务器故障的情况下仍能继续运行。你将面临的一个问题是，Clerk 可能不得不多次发送 RPC，直到找到一个能正面回复的 kvserver。如果领导者在将条目提交到 Raft 日志后刚好失败， Clerk 可能不会收到回复，因此可能会将请求重新发送给另一个领导者。每次调用 Clerk.Put() 应该对特定版本号只产生一次执行。

添加处理故障的代码。你的 Clerk 可以使用与实验 2 类似的重试计划，包括在对重试的 Put RPC 的回复丢失时返回 ErrMaybe。当你的代码能稳定通过所有 4B 测试时即完成，使用 make RUN="-run 4B" kvraft1。

回想一下，rsm 领导者可能失去领导权并从 Submit() 返回 rpc.ErrWrongLeader。在这种情况下，你应该安排 Clerk 将请求重新发送给其他服务器，直到找到新领导者。
你可能需要修改你的 Clerk，让它记住哪个服务器在最后一次 RPC 中是领导者，并首先将下一个 RPC 发送给该服务器。这将避免在每次 RPC 上浪费时间搜索领导者，可能有助于你足够快地通过某些测试。

你的代码现在应该通过实验 4B 测试，如下所示：

$ cd src
$ make RUN="-run 4B" kvraft1
go build -race -o main/kvraft1d main/kvraft1d.go
cd kvraft1 && go test -v -race -run 4B 
=== RUN   TestBasic4B
Test: one client (4B basic) (reliable network)...
  ... Passed --  time  3.5s #peers 5 #RPCs   395 #Ops  122
--- PASS: TestBasic4B (4.11s)
=== RUN   TestSpeed4B
Test: one client (4B speed) (reliable network)...
  ... Passed --  time  33.4s #peers 3 #RPCs  3291 #Ops 1002
--- PASS: TestSpeed4B (33.80s)
=== RUN   TestConcurrent4B
Test: many clients (4B many clients) (reliable network)...
  ... Passed --  time  4.1s #peers 5 #RPCs   953 #Ops  558
--- PASS: TestConcurrent4B (4.69s)
=== RUN   TestUnreliable4B
Test: many clients (4B many clients) (unreliable network)...
  ... Passed --  time  4.6s #peers 5 #RPCs   685 #Ops  210
--- PASS: TestUnreliable4B (5.22s)
=== RUN   TestOnePartition4B
Test: one client (4B progress in majority) (unreliable network)...
  ... Passed --  time  4.9s #peers 5 #RPCs   231 #Ops    4
Test: no progress in minority (4B) (unreliable network)...
  ... Passed --  time  1.8s #peers 5 #RPCs   110 #Ops    7
Test: completion after heal (4B) (unreliable network)...
  ... Passed --  time  1.1s #peers 5 #RPCs    43 #Ops    4
--- PASS: TestOnePartition4B (8.36s)
=== RUN   TestManyPartitionsOneClient4B
Test: partitions, one client (4B partitions, one client) (reliable network)...
  ... Passed --  time  9.4s #peers 5 #RPCs   520 #Ops  114
--- PASS: TestManyPartitionsOneClient4B (10.08s)
=== RUN   TestManyPartitionsManyClients4B
Test: partitions, many clients (4B partitions, many clients (4B)) (reliable network)...
  ... Passed --  time  16.1s #peers 5 #RPCs  1271 #Ops  558
--- PASS: TestManyPartitionsManyClients4B (16.68s)
=== RUN   TestPersistOneClient4B
Test: restarts, one client (4B restarts, one client 4B ) (reliable network)...
  ... Passed --  time  8.4s #peers 5 #RPCs   311 #Ops   62
--- PASS: TestPersistOneClient4B (9.01s)
=== RUN   TestPersistConcurrent4B
Test: restarts, many clients (4B restarts, many clients) (reliable network)...
  ... Passed --  time  8.5s #peers 5 #RPCs   994 #Ops  350
--- PASS: TestPersistConcurrent4B (9.11s)
=== RUN   TestPersistConcurrentUnreliable4B
Test: restarts, many clients (4B restarts, many clients ) (unreliable network)...
  ... Passed --  time  10.3s #peers 5 #RPCs   672 #Ops  114
--- PASS: TestPersistConcurrentUnreliable4B (10.89s)
=== RUN   TestPersistPartition4B
Test: restarts, partitions, many clients (4B restarts, partitions, many clients) (reliable network)...
  ... Passed --  time  14.3s #peers 5 #RPCs   804 #Ops   94
--- PASS: TestPersistPartition4B (14.95s)
=== RUN   TestPersistPartitionUnreliable4B
Test: restarts, partitions, many clients (4B restarts, partitions, many clients) (unreliable network)...
  ... Passed --  time  22.0s #peers 5 #RPCs  1229 #Ops  102
--- PASS: TestPersistPartitionUnreliable4B (22.64s)
=== RUN   TestPersistPartitionUnreliableLinearizable4B
Test: restarts, partitions, random keys, many clients (4B restarts, partitions, random keys, many clients) (unreliable network)...
  ... Passed --  time  24.1s #peers 7 #RPCs  4464 #Ops  444
--- PASS: TestPersistPartitionUnreliableLinearizable4B (24.94s)
PASS
ok  	6.5840/kvraft1	175.518s

每个 Passed 后面的数字分别是实际运行时间（秒）、对等体数量、发送的 RPC 数量（包括客户端 RPC）以及执行的键值操作数量（Clerk 的 Get/Put 调用）。

部分 C: 使用快照的键值服务

就目前而言，你的键值服务器没有调用 Raft 库的 Snapshot() 方法，所以重启的服务器必须重放完整的持久化 Raft 日志来恢复其状态。现在你将修改 kvserver 和 rsm 以与 Raft 协作来节省日志空间并减少重启时间，使用实验 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 编码字节。

你可以在 tester1/persister.go 中找到 persister 对象的源码。

修改你的 rsm，使其能检测持久化 Raft 状态何时变得过大，然后将快照交给 Raft。当 rsm 服务器重启时，它应使用 persister.ReadSnapshot() 读取快照，如果快照的长度大于零，则将快照传递给 StateMachine 的 Restore() 方法。如果你通过了 rsm 中的 TestSnapshot4C，即完成了此任务。

$ cd src
$ make RUN="-run 4C" kvraft1
go build -race -o main/kvraft1d main/kvraft1d.go
cd kvraft1 && go test -v -race -run 4C 
=== RUN   TestSnapshotRPC4C
Test: snapshots, one client (4C SnapshotsRPC) (reliable network)...
Test: InstallSnapshot RPC (4C) (reliable network)...
signal: killed
FAIL	6.5840/kvraft1	61.186s

思考 rsm 应该何时快照其状态，以及快照中除了服务器状态外还应包含什么。 Raft 使用 Save() 将每个快照存储在 persister 对象中，以及相应的 Raft 状态。你可以使用 ReadSnapshot() 读取最新存储的快照。
将快照中存储的结构体的所有字段名首字母大写。

实现 rsm 调用的 kvraft1/server.go 中的 Snapshot() 和 Restore() 方法。修改 rsm 以处理包含快照的 applyCh 消息。

你的 Raft 和 rsm 库中可能有此任务暴露的错误。如果你对 Raft 实现进行了更改，请确保它继续通过所有实验 3 测试。
实验 4 测试的合理时间是 400 秒的实际时间和 700 秒的 CPU 时间。

你的代码应该通过 4C 测试（如此处的示例所示），以及 4A+B 测试（并且你的 Raft 必须继续通过实验 3 测试）。

$ make RUN="-run 4C" kvraft1
go build -race -o main/kvraft1d main/kvraft1d.go
cd kvraft1 && go test -v -race -run 4C 
=== RUN   TestSnapshotRPC4C
Test: snapshots, one client (4C SnapshotsRPC) (reliable network)...
Test: InstallSnapshot RPC (4C) (reliable network)...
  ... Passed --  time  4.8s #peers 3 #RPCs   248 #Ops   72
--- PASS: TestSnapshotRPC4C (5.18s)
=== RUN   TestSnapshotSize4C
Test: snapshots, one client (4C snapshot size is reasonable) (reliable network)...
  ... Passed --  time  21.0s #peers 3 #RPCs  2569 #Ops 1200
--- PASS: TestSnapshotSize4C (21.42s)
=== RUN   TestSpeed4C
Test: snapshots, one client (4C speed) (reliable network)...
  ... Passed --  time  24.9s #peers 3 #RPCs  3208 #Ops 1002
--- PASS: TestSpeed4C (25.32s)
=== RUN   TestSnapshotRecover4C
Test: restarts, snapshots, one client (4C restarts, snapshots, one client) (reliable network)...
  ... Passed --  time  8.2s #peers 5 #RPCs   273 #Ops   50
--- PASS: TestSnapshotRecover4C (8.78s)
=== RUN   TestSnapshotRecoverManyClients4C
Test: restarts, snapshots, many clients (4C restarts, snapshots, many clients ) (reliable network)...
info: linearizability check timed out, assuming history is ok
info: linearizability check timed out, assuming history is ok
info: linearizability check timed out, assuming history is ok
  ... Passed --  time  12.5s #peers 5 #RPCs  3525 #Ops 1670
--- PASS: TestSnapshotRecoverManyClients4C (13.15s)
=== RUN   TestSnapshotUnreliable4C
Test: snapshots, many clients (4C unreliable net, snapshots, many clients) (unreliable network)...
  ... Passed --  time  5.5s #peers 5 #RPCs   773 #Ops  230
--- PASS: TestSnapshotUnreliable4C (6.16s)
=== RUN   TestSnapshotUnreliableRecover4C
Test: restarts, snapshots, many clients (4C unreliable net, restarts, snapshots, many clients) (unreliable network)...
  ... Passed --  time  10.7s #peers 5 #RPCs   804 #Ops   78
--- PASS: TestSnapshotUnreliableRecover4C (11.28s)
=== RUN   TestSnapshotUnreliableRecoverConcurrentPartition4C
Test: restarts, partitions, snapshots, many clients (4C unreliable net, restarts, partitions, snapshots, many clients) (unreliable network)...
  ... Passed --  time  17.4s #peers 5 #RPCs   894 #Ops   94
--- PASS: TestSnapshotUnreliableRecoverConcurrentPartition4C (17.97s)
=== RUN   TestSnapshotUnreliableRecoverConcurrentPartitionLinearizable4C
Test: restarts, partitions, snapshots, random keys, many clients (4C unreliable net, restarts, partitions, snapshots, random keys, many clients) (unreliable network)...
  ... Passed --  time  19.6s #peers 7 #RPCs  2957 #Ops  368
--- PASS: TestSnapshotUnreliableRecoverConcurrentPartitionLinearizable4C (20.45s)
PASS
ok  	6.5840/kvraft1	130.724s

6.5840 - 2026年春季

6.5840 实验 4: 容错键值服务

介绍

入门

部分 A: 复制状态机 (RSM) g("moderate/hard")

部分 B: 不使用快照的键值服务 g("moderate")

部分 C: 使用快照的键值服务 g("moderate")

部分 A: 复制状态机 (RSM)

部分 B: 不使用快照的键值服务

部分 C: 使用快照的键值服务