MIT 6.824 - Lab 3 (2): 实现
Lab 3 需要我们实现一个基于 Raft 的键值数据库，支持三个操作：
Put(key, value)Append(key, value)Get(key)
3A
客户端
客户端要做的只有一件事，就是向某个服务端发送请求。不过由于客户端不知道哪个服务端是主节点，所以需要不断轮询各服务端发送请求。为了避免每次轮询所有服务端浪费时间，客户端可以记录每次请求成功后的服务端编号，这个服务端就是当次请求中的主节点；当客户端再次发起请求时，可以先假定之前的服务端依然是主节点，从而先向该服务端发送请求，如果请求失败并返回 ErrWrongLeader 异常，则再尝试下一个服务端。
服务端
Lab 3 要求服务端将客户端请求成功的结果放到 RPC 响应中，不过 Raft.Start() 的执行成功不代表最终日志的应用成功，所以服务端调用 Raft.Start() 后需要阻塞等待，直到 Raft 将对应日志应用到状态机。等待/唤醒的模式可以想到使用条件变量 sync.Cond，不过 Go 中有 channel 这个更方便的特性来实现。
正常情况下，服务端调用 Raft.Start() 添加日志的顺序和之后从 applyCh 中收到日志的顺序一致，也就是说客户端请求到达服务端并被处理的顺序和服务端从 applyCh 中收到日志的顺序一致。所以，服务端可以维护一个客户端请求的队列，队列中存放的是 channel，每当服务端从 applyCh 中收到日志，就将日志发送到队首的 channel 中，并从队列中移除。这样阻塞等待中的 RPC 服务端线程就能被唤醒，并响应客户端。
不过在异常情况下，客户端请求队列和服务端从 applyCh 中收到日志的顺序并不是一一对应，因此服务端收到日志时需要剔除掉队列中无效的请求，并通过 channel 发送一个 ErrWrongLeader 异常，这样客户端就能换一个服务端来重试。由于通过日志索引无法唯一确定一条 Raft 日志，所以需要在 ApplyMsg 中添加 CommandTerm 来标识日志所属的任期，这样服务端从 applyCh 中收到日志后就能通过比较客户端请求队列中的日志任期和索引来判断请求是否有效。
记客户端请求队列队首日志的任期和索引为 (term_client, index_client)，记服务端从 applyCh 收到的日志的任期和索引为 (term_applied, index_applied)。正常情况下有 term_client == term_applied 以及 index_client == index_applied。从服务端角度来说，异常情况有两种，一种是当前服务端不再是主节点，另一种情况是当前服务端依然是主节点，不过中途发生了主从切换可能造成当前的日志和最初的不同。对于第一种情况可以直接清空客户端请求队列，虽然 (term_applied, index_applied) 有可能匹配部分客户端请求，不过由于当前服务端不再是主节点，下次客户端请求的时候本身就要再轮询所有的服务端，所以这里等同于是提前让客户端轮询。对于第二种情况（也考虑原来是从节点后来变成主节点的场景），可以从队首开始遍历客户端请求队列，剔除掉比 (term_applied, index_applied) 小的 (term_client, index_client) 请求，并通过 channel 返回异常（这里需要一个自定义异常，告诉客户端直接重试，因为当前服务端依然是主节点，所以客户端没有必要轮询）。这里的剔除掉比 (term_applied, index_applied) 小的 (term_client, index_client) 请求，指的是仅保留 term_client >= term_applied 和 index_client >= index_applied 的请求，因为根据 Raft 日志的性质，其他情况下的客户端请求都已经不可能被提交。
因此，服务端需要开启一个单独的 goroutine，并不断的从 applyCh 中获取日志，然后根据日志的指令内容更新本地的键值数据库，最后唤醒客户端请求队列中的请求。而如何实现本地键值数据库不是本实验的重点，所以简单使用了一个 map。
客户端请求去重
6.824 Lab 3: Fault-tolerant Key/Value Service 中提到：
It’s OK to assume that a client will make only one call into a Clerk at a time.
一个客户端一次只发送一个请求，加上请求阻塞的特性，任何时刻每个客户端都最多只有一个进行中的请求。为了对请求去重，每个客户端可以生成一个唯一的客户端 id，每次发请求时生成一个递增的请求序号，而服务端只需要维护每个客户端已提交到状态机的最大请求序号即可，这是因为当前场景下每个客户端的请求序列是个递增的序列（非严格递增，相邻数字之间可能存在重复）。所以，当服务端收到请求时，如果发现请求中的序号小于等于该客户端的最大请求序号，则说明该请求是重复的。
不过，处理重复的读请求有两种方案，一种是返回当前值，另一种是返回第一次收到读请求时的值。两种方式都可解释，本实验中直接返回当前值即可。
那么服务端收到 Raft 日志时如何知道这个日志对应的客户端请求序号？这个属于应用层面的数据，可以将客户端 id 和请求序号放到 Op 中，服务端收到 Raft 的日志后，将 ApplyMsg.Command 进行类型转换，转为 Op 即可。
问题
TestSpeed3A
TestSpeed3A 要求每个心跳周期至少完成三次客户端请求，不过在做 Lab 2 时，Raft 收到日志后不会马上发起共识，而是在下一次发送心跳时批量对收到的日志发起共识。又由于 TestSpeed3A 会循环发起请求，每个请求阻塞，服务端只有在收到 applyCh 的日志后才会通知客户端，所以本质上在这个测试中服务端约等于一个心跳周期只处理一个请求。所以需要修改 Raft.Start()，收到日志后开启一个 goroutine 发起心跳。
客户端请求队列无法被唤醒
服务端收到 Raft 的日志后才唤醒客户端请求队列会造成客户端请求队列永远不会被唤醒，因为这强依赖于某条日志被提交，而客户端的日志不一定会被提交。例如，某个服务端收到客户端的请求，将请求放到队列中，此时服务端发生异常，其他服务端成为新的主节点，而新的主节点并没有收到客户端的日志，在没有其他客户端请求的情况下，最开始的客户端请求永远不会被唤醒。所以，这里也额外开启了一个 goroutine，如果当前服务端不是主节点且客户端请求队列不为空，则清空客户端请求队列，并通知 ErrWrongLeader 异常。
不过，这个策略也会带来一个请求重复执行的问题。当前身为主节点的服务端成功提交了某个客户端的请求，注意这里是 commit，而不是 apply，此时服务端发生异常，另一个服务端成为新的主节点，原来的服务端发现自己不是主节点并且请求队列不为空，则清空了请求队列，然后客户端发起重试，新的主节点收到了请求并成功提交，最后 Raft 的日志中就会有两条内容一样的日志，但是 Raft 并不关心两条日志的内容是否相同。所以这个去重需要在服务端处理，服务端从 applyCh 收到日志后，需要判断日志中对应的请求是否已被处理。造成这个问题的主要原因在于 Raft 处理日志的 commit 和 apply 之间存在时间差，而服务端只通过 applyCh 和 Raft 进行交互。
3B
引入快照之后，服务端从 applyCh 收到日志时需要判断是否是快照消息，如果是快照消息则执行快照逻辑。3B 整体难度低于 3A，快照的代码逻辑类似于 Lab 2 中的快照代码，不过要注意两点：
- 快照会通过
RPC发送，所以涉及快照的字段命名注意首字母大写 Raft收到快照RPC后，再通过applyCh发送快照，但是服务端从applyCh中收到的快照消息不一定是最新的，即快照的最远日志索引有可能会落后于服务端已经应用到状态机的最远日志索引（因为Raft层收到的快照可能只覆盖了当前日志的一部分，而Raft往applyCh中发送已应用的日志或快照间没有顺序关系，所以对于服务端来说已经应用到状态机的日志索引可能会大于快照中的日志索引。）。如果快照不是最新的，服务端直接忽略即可，避免覆盖当前的状态机。如何知道当前快照不是最新的？服务端可以记录已提交到本地状态机的最大ApplyMsg.CommandIndex，收到快照消息后将其和快照消息中的ApplyMsg.SnapshotIndex比较即可