Lab 4: Fault-tolerant Key/Value Service

课程网站，实验网站，实验指南。

单个客户端只会串行发送 RPC，但服务器会收到多个客户端的 RPC。

Part A: Key/value service without snapshots

实现

实现 Clerk 的 Get 和 PutAppend 方法。如果不知道谁是 leader，则迭代地向每个服务器发送 RPC。直到某个服务器回复操作成功，此时记录该服务器为 leader，以免每次发送 RPC 都需要重新确定 leader。如果标记为 leader 的服务器回复操作失败或者超时未回复，依然需要迭代所有服务器。因为 leader 随时可能变化，甚至是在迭代的过程中，所以需要在迭代的外层添加一个无限循环。

实现 KVServer 的 Get、Put 和 Append 方法。基本的结构是，首先调用 rf.Start 方法，如果不是 leader 则响应 ErrWrongLeader。否则，在正常情况下，我们等待通道中出现对应的命令，将命令应用到状态机，然后返回响应。由于 rf.Start 方法不保证会提交指定的命令，我们需要一种能够检测当前服务器已经不是 leader 的方法，从而避免客户端阻塞在非 leader 服务器上。方式如下，可以定时调用 rf.GetState 检查当前服务器的任期是否和之前调用 Start 得到的任期不一致，或者在通道中出现和请求不匹配的消息。

对于每个服务器，我们应该使用一个线程来读取 ApplyMsg，不断地将已提交的命令应用到状态机。我们不能等待 RPC 去读取对应的 ApplyMsg，因为只有 leader 会收到 Clerk 的 RPC，此时其他服务器需要自动同步。需要注意，不是所有提交的命令都会应用到状态机，因为会存在重复的请求。例如，当前 leader 在提交日志之后崩溃，客户端没有收到响应，然后向新的 leader 发送重复的请求，如果此时命令没有被应用到状态机，依然会调用 rf.Start 方法，重复的请求会出现在日志中。

我们需要为每个客户端记录其最后应用到状态机的命令对应请求的标识，来过滤重复的请求。特别的，Get 请求不会对状态机产生影响，并且将 Get 请求放入日志只是为保证单个客户端视图的单调性，所以我们不需要过滤重复的 Get 请求，也就不需要保存上次 Get 请求的结果，而总是应该返回最新的结果。对于每个 Clerk，只缓存上次请求的 RequestId 是否有可能产生错误？例如，某个很早之前发送的 RPC 到达 KVServer，而对应的 RequestId 已经被覆盖。不会发生该情况，TCP 会保证发送顺序和到达顺序一致。

测试

使用命令 time go test -race -run 4A -count 1 -failfast -timeout 0 开始测试：

① 测试无法停止，查看日志发现，客户端请求阻塞在非 leader 服务器上。通过定时检查服务器的任期，可以解决该问题。

Part B: Key/value service with snapshots

实现

什么时候检查大小？可以定时检查。如果超过大小，该执行什么操作？调用 rf.Snapshot。什么时候读取快照？在服务器启动时，以及从通道中。特别的，如果 maxraftstate = -1，则不需要快照。通道中的快照是否有可能比服务器的当前状态更小？

测试

使用命令 time go test -race -run 4B -count 1 -failfast -timeout 0 开始测试：

① 报错 panic: runtime error: slice bounds out of range [-190:]。Raft 发送快照给服务器，而服务器也发送快照给 Raft，状态交叠从而产生错误。要解决该问题，第一个想法是在 Raft 向服务器发送快照时不释放锁，但是有可能产生死锁。第二个想法是，在服务器从通道接收快照消息之后，再更新 Raft 的状态。但是还是不行，如果服务器读取快照消息却没有应该到状态机，然后服务器在 Raft 更新状态之前，调用 persister.RaftStateSize 检查大小，此时 Raft 更新状态，之后服务器调用 rf.Snapshot 方法传递一个更小的快照，必然会产生索引越界。或者，服务器调用 rf.Snapshot 方法传递一个更大的快照，然后 Raft 更新状态，也会索引越界。而且，在之后更新状态必须重新检查假设，很麻烦。简单起见，依然在解锁之前更新状态，同时在 rf.Snapshot 中过滤更小的快照。

② 测试 TestSnapshotRecover4B，报错 test_test.go:148: duplicate element x 0 333 y in Append result。定位错误很慢，日志太长不好看，看半天看不出问题。原因是服务器从通道读取快照之后，通道中有快照已经包含的命令消息，所以会重复应用命令。在应用消息到状态机之前，需要限制消息的日志索引必须大于最后应用到状态机的日志索引。其实只要查看修改状态机的关键代码，应该是可以很快找到错误的。

③ 测试 TestSnapshotRecoverManyClients4B，报错 test_test.go:293: get wrong value, key 19。错误的信息表明状态缺失，定位错误很慢，主要日志太多，打印的信息也不全，经常需要添加打印信息然后重新测试，果然应该在最开始就打印所有信息。错误的原因在 Raft 代码，没有限制快照消息在日志消息之前发送，服务器会提前收到快照之后的命令，使得服务器在收到快照时会丢弃快照，因为最后应用的命令索引大于快照的最后索引。解决方案很简单，只需要做一下限制就行。

总结

每次做实验都会遇到两个难点，一个是功能实现，一个是定位错误。

关于功能实现：例如，如何实现将 ApplyMsg 应用到状态机？最开始，我是想让每个 RPC 去读取消息，然后将其应用到状态机。但是，思考之后，会发现不可行，然后又去想其他方案。实现方式的设计依赖于对整个交互逻辑的正确理解，难点在于处理异常情况，像是 leader 变更、服务器崩溃。

关于定位错误：总是应该在日志中包含所有信息，避免需要添加信息然后重新测试的情况，会非常痛苦。定位错误不要只看日志，一定要先思考可能是哪个部分有问题，比如说状态机的状态有问题，那么在什么情况下会修改状态？找到修改状态的代码，然后思考这段代码在什么情况下会有问题。如果代码没有问题，那么想一想是不是外界的输入有问题，什么样的输入会产生该错误？然后，我们就可以找到外部依赖的代码，确定是否有可能产生该输入序列。