在本实验中，你将为一台单机构建一个键值服务器， 确保每次 Put 操作在网络故障的情况下也能至多执行一次， 并且操作是线性可序列化的。你将使用这个键值服务器来实现一个锁。 后续实验将复制这样的服务器来处理服务器崩溃的情况。
每个客户端使用一个Clerk（客户端代理）与键值服务器交互， Clerk 是一组向服务器发送 RPC 的库函数。 客户端可以向服务器发送两种不同的 RPC： Put(key, value, version) 和 Get(key)。服务器 维护一个内存中的映射表，为每个键记录一个 (value, version) 元组。键和值都是字符串。版本号 记录了该键被写入的次数。 Put(key, value, version) 仅在 Put 的版本号 与服务器中该键的版本号匹配时，才会在映射表中 安装或替换特定键的值。如果版本号 匹配，服务器还会递增该键的版本号。如果版本号 不匹配，服务器应返回 rpc.ErrVersion。客户端可以通过使用版本号 0 调用 Put 来创建新键 （服务器存储的结果版本号将是 1）。如果 Put 的版本号大于 0 且键不存在，服务器应返回 rpc.ErrNoKey。
Get(key) 获取该键的当前值及其关联的 版本号。如果键在服务器中不存在，服务器应 返回 rpc.ErrNoKey。
为每个键维护版本号将有助于 使用 Put 实现锁，以及在网络不可靠且客户端 重传时确保 Put 的至多一次语义。
当你完成本实验并通过所有测试后，你将拥有一个从 调用 Clerk.Get 和 Clerk.Put 的客户端角度来看 线性可序列化的键值服务。 也就是说，如果客户端操作不是并发的，每个 客户端的 Clerk.Get 和 Clerk.Put 将观察到 由前面的操作序列所暗示的状态修改。对于并发操作， 返回值和最终状态将与操作按某种顺序逐个执行时相同。 如果操作在时间上重叠，则它们是并发的：例如，如果 客户端 X 调用 Clerk.Put()，客户端 Y 也调用 Clerk.Put()，然后客户端 X 的调用返回。一个操作 必须观察到在该操作开始之前所有已完成操作的效果。 请参阅 线性可序列化 的常见问题解答 以了解更多背景知识。
线性可序列化对应用程序来说很方便，因为它的行为 与单个服务器逐个处理请求时你看到的行为一样。 例如，如果一个客户端从服务器收到了更新请求的成功响应， 随后其他客户端发起的读取保证能看到该更新的效果。 对于单个服务器来说，提供线性可序列化是相对容易的。
我们为你提供了 src/kvsrv1 中的骨架代码和测试。 kvsrv1/client.go 实现了一个 Clerk，客户端使用它 来管理与服务器的 RPC 交互；Clerk 提供 Put 和 Get 方法。 kvsrv1/server.go 包含服务器代码， 包括实现 RPC 请求服务器端的 Put 和 Get 处理函数。 你需要修改 client.go 和 server.go。 RPC 请求、回复和错误值 定义在 kvsrv1/rpc 包的 kvsrv1/rpc/rpc.go 文件中， 你应该查看它，尽管你不需要修改 rpc.go。
要开始运行，请执行以下命令。 别忘了 git pull 来获取最新的软件。
$ cd ~/6.5840
$ git pull
...
$ cd src
$ make kvsrv1
go build -race -o main/kvsrv1d main/kvsrv1d.go
cd kvsrv1 && go test -v -race
=== RUN TestReliablePut
One client and reliable Put (reliable network)...
kvsrv_test.go:25: Put err ErrNoKey
--- FAIL: TestReliablePut (0.31s)
...
$
你的第一个任务是实现一个在没有丢包的情况下 能正常工作的方案。 你需要在 client.go 中的 Clerk Put/Get 方法中添加发送 RPC 的代码，并在 server.go 中实现 Put 和 Get RPC 处理函数。
当你通过测试套件中的 Reliable 测试时， 即完成了此任务：
$ cd src $ make RUN="-run Reliable" kvsrv1 go build -race -o main/kvsrv1d main/kvsrv1d.go cd kvsrv1 && go test -v -race -run Reliable === RUN TestReliablePut One client and reliable Put (reliable network)... ... Passed -- time 0.0s #peers 1 #RPCs 5 #Ops 5 --- PASS: TestReliablePut (0.12s) === RUN TestPutConcurrentReliable Test: many clients racing to put values to the same key (reliable network)... ... Passed -- time 6.3s #peers 1 #RPCs 11025 #Ops 22050 --- PASS: TestPutConcurrentReliable (6.36s) === RUN TestMemPutManyClientsReliable Test: memory use many put clients (reliable network)... ... Passed -- time 29.0s #peers 1 #RPCs 50000 #Ops 50000 --- PASS: TestMemPutManyClientsReliable (52.91s) PASS ok 6.5840/kvsrv1 60.732s $
每个 Passed 后面的数字分别是实际运行时间（秒）、 常数 1、 发送的 RPC 数量（包括客户端 RPC）以及执行的键值 操作数量（Clerk 的 Get 和 Put 调用）。
在许多分布式应用中，运行在不同机器上的客户端 使用键值服务器来协调它们的活动。例如， ZooKeeper 和 Etcd 允许客户端使用分布式锁来协调， 类似于 Go 程序中的线程可以使用锁（即 sync.Mutex）来协调。 Zookeeper 和 Etcd 使用条件写入来实现这样的锁。
你的任务是使用你的键值服务器来实现锁， 在服务器中存储你的设计所需的每个锁的状态。 可以有多个独立的锁，每个锁都有自己的名称， 作为参数传递给 MakeLock。 一个锁支持两个方法：Acquire 和 Release。 规范是：一次只有一个客户端能成功获取给定的锁； 其他客户端必须等到第一个客户端使用 Release 释放锁。
我们为你提供了 src/kvsrv1/lock/ 中的骨架代码和测试。 你需要修改 src/kvsrv1/lock/lock.go。 你的 Acquire 和 Release 应通过调用 lk.ck.Put() 和 lk.ck.Get() 将每个锁的状态存储在键值服务器中。
如果客户端在持有锁时崩溃， 锁将永远不会被释放。 在一个比本实验更复杂的设计中， 客户端会给锁附加一个租约。 当租约到期时，锁服务器会代表客户端释放锁。 在本实验中，客户端不会崩溃，你可以忽略这个问题。
实现 Acquire 和 Release。 当你的代码通过以下测试时，即完成了此练习：
$ cd src $ make RUN="-run Reliable" lock1 go build -race -o main/kvsrv1d main/kvsrv1d.go cd kvsrv1/lock; go test -v -race -run Reliable === RUN TestReliableBasic Test: a single Acquire and Release (reliable network)... ... Passed -- time 0.0s #peers 1 #RPCs 4 #Ops 4 --- PASS: TestReliableBasic (0.13s) === RUN TestReliableNested Test: one client, two locks (reliable network)... ... Passed -- time 0.1s #peers 1 #RPCs 17 #Ops 17 --- PASS: TestReliableNested (0.17s) === RUN TestOneClientReliable Test: 1 lock clients (reliable network)... ... Passed -- time 2.0s #peers 1 #RPCs 477 #Ops 477 --- PASS: TestOneClientReliable (2.14s) === RUN TestManyClientsReliable Test: 10 lock clients (reliable network)... ... Passed -- time 2.2s #peers 1 #RPCs 5704 #Ops 5704 --- PASS: TestManyClientsReliable (2.36s) PASS ok 6.5840/kvsrv1/lock 5.817s $
如果你还没有实现锁，前两个测试会通过。
这个练习需要的代码不多，但比前一个练习 需要更多独立思考。
本练习的主要挑战是网络可能会重新排序、 延迟或丢弃 RPC 请求和/或回复。为了从 丢弃的请求/回复中恢复，Clerk 必须不断重试每个 RPC， 直到它收到服务器的回复。
如果网络丢弃了 RPC 请求消息，那么客户端 重新发送请求就能解决问题：服务器将收到并 执行重新发送的请求。
然而，网络可能丢弃的是 RPC 回复消息。 客户端不知道哪个消息被丢弃了；客户端只知道 它没有收到回复。 如果是回复被丢弃了，而客户端重新发送了 RPC 请求，那么服务器将收到两份请求。 这对 Get 来说没关系，因为 Get 不会修改服务器状态。 使用相同版本号重新发送 Put RPC 是安全的， 因为服务器根据版本号有条件地执行 Put； 如果服务器已经收到并执行了一个 Put RPC， 它将用 rpc.ErrVersion 响应重新传输的 该 RPC 副本，而不是第二次执行 Put。
一个棘手的情况是，服务器对 Clerk 重试的 RPC 回复了 rpc.ErrVersion。在这种情况下，Clerk 无法知道 Clerk 的 Put 是否已被服务器执行：第一次 RPC 可能已被服务器执行，但网络可能丢弃了 来自服务器的成功响应，所以服务器只对重新传输的 RPC 发送了 rpc.ErrVersion。或者，可能是另一个 Clerk 在 Clerk 的第一次 RPC 到达服务器之前更新了键， 所以服务器没有执行 Clerk 的任何一次 RPC， 并对两次都回复了 rpc.ErrVersion。 因此，如果 Clerk 对重新传输的 Put RPC 收到 rpc.ErrVersion， Clerk.Put 必须向应用程序返回 rpc.ErrMaybe 而不是 rpc.ErrVersion，因为请求可能已被执行。 然后由应用程序来处理这种情况。 如果服务器对初始（非重新传输的）Put RPC 回复了 rpc.ErrVersion， 那么 Clerk 应向应用程序返回 rpc.ErrVersion， 因为该 RPC 肯定没有被服务器执行。
如果 Put 是精确一次语义（即没有 rpc.ErrMaybe 错误）， 对应用开发者来说会更方便，但在不在服务器中 为每个 Clerk 维护状态的情况下很难保证。 在本实验的最后一个练习中，你将使用你的 Clerk 实现一个锁，以探索如何使用至多一次的 Clerk.Put 进行编程。
现在你应该修改你的 kvsrv1/client.go， 使其在 RPC 请求和回复被丢弃时仍能继续工作。 客户端的 ck.clnt.Call() 返回 true 表示客户端收到了服务器的 RPC 回复； 返回 false 表示没有收到回复 （更准确地说，Call() 等待回复消息一个超时间隔， 如果在该时间内没有收到回复则返回 false）。 你的 Clerk 应该不断重新发送 RPC， 直到收到回复。请记住上面关于 rpc.ErrMaybe 的讨论。 你的解决方案不需要对服务器做任何修改。
在 Clerk 中添加代码，如果在重试前没有收到回复则重试。 如果你的代码通过了 kvsrv1 的所有测试，即完成了此任务：
$ make kvsrv1 go build -race -o main/kvsrv1d main/kvsrv1d.go cd kvsrv1 && go test -v -race === RUN TestReliablePut One client and reliable Put (reliable network)... ... Passed -- time 0.0s #peers 1 #RPCs 5 #Ops 5 --- PASS: TestReliablePut (0.12s) === RUN TestPutConcurrentReliable Test: many clients racing to put values to the same key (reliable network)... ... Passed -- time 6.4s #peers 1 #RPCs 11021 #Ops 22042 --- PASS: TestPutConcurrentReliable (6.52s) === RUN TestMemPutManyClientsReliable Test: memory use many put clients (reliable network)... ... Passed -- time 28.8s #peers 1 #RPCs 50000 #Ops 50000 --- PASS: TestMemPutManyClientsReliable (52.44s) === RUN TestUnreliableNet One client (unreliable network)... ... Passed -- time 4.0s #peers 1 #RPCs 268 #Ops 422 --- PASS: TestUnreliableNet (4.13s) PASS ok 6.5840/kvsrv1 64.442s $
修改你的锁实现，使其在网络不可靠时 能与你修改后的键值客户端正确配合工作。 当你的代码通过所有 lock1 测试时， 即完成了此练习：
$ make lock1 go build -race -o main/kvsrv1d main/kvsrv1d.go cd kvsrv1/lock; go test -v -race === RUN TestReliableBasic Test: a single Acquire and Release (reliable network)... ... Passed -- time 0.0s #peers 1 #RPCs 4 #Ops 4 --- PASS: TestReliableBasic (0.13s) === RUN TestReliableNested Test: one client, two locks (reliable network)... ... Passed -- time 0.1s #peers 1 #RPCs 17 #Ops 17 --- PASS: TestReliableNested (0.17s) === RUN TestOneClientReliable Test: 1 lock clients (reliable network)... ... Passed -- time 2.0s #peers 1 #RPCs 471 #Ops 471 --- PASS: TestOneClientReliable (2.13s) === RUN TestManyClientsReliable Test: 10 lock clients (reliable network)... ... Passed -- time 2.2s #peers 1 #RPCs 5658 #Ops 5658 --- PASS: TestManyClientsReliable (2.35s) === RUN TestOneClientUnreliable Test: 1 lock clients (unreliable network)... ... Passed -- time 2.1s #peers 1 #RPCs 66 #Ops 57 --- PASS: TestOneClientUnreliable (2.18s) === RUN TestManyClientsUnreliable Test: 10 lock clients (unreliable network)... ... Passed -- time 4.1s #peers 1 #RPCs 778 #Ops 617 --- PASS: TestManyClientsUnreliable (4.23s) PASS ok 6.5840/kvsrv1/lock 12.227s $