MIT 6.824 Lab3 RaftKV
待补充
实验内容
在lab2的Raft函数库之上，搭建一个能够容错的key/value存储服务，需要提供一致性保证。
强一致性的解释如下：对于单个请求，整个服务需要表现得像个单机服务，并且对状态机的修改基于之前所有的请求。对于并发的请求，返回的值和最终的状态必须相同，就好像所有请求都是串行的一样。即使有些请求发生在了同一时间，那么也应当一个一个响应。此外，在一个请求被执行之前，这之前的请求都必须已经被完成（在技术上我们也叫着线性化（linearizability））。
整体架构
Part A - 不需要日志压缩的key/value服务
Clerk客户端实现
需要解决的问题：客户端发送请求，服务端同步成功并且提交，接着apply后返回给客户端执行结果，但返回客户端时候rpc丢失，客户端只能进行重试直到明确地写入成功或失败为止，但该操作可能已经在服务端应用过了，违背了线性一致性。
clientId和commandId来唯一的标识一个客户端，从而保证线性一致性。RAFT原文介绍需要保证日志仅被执行一次，即它可以被 commit 多次，但一定只能 apply 一次。
可以看一下：
链接：https://www.zhihu.com/question/278551592/answer/400962941
在Raft论文的6.3节，这个问题有详细讨论。
用普通后台术语就是幂等。Raft作者把这归为实现linearizable semantics所需要处理的一部分。Raft论文里，也给出了具体的通用解决办法。基本思路是：
- 每个要做proposal的client需要一个唯一的identifier，它的每个不同proposal需要有一个顺序递增的序列号，client id和这个序列号由此可以唯一确定一个不同的proposal，从而使得各个raft节点可以记录保存各proposal应用以后的结果。
- 当一个proposal超时，client不提高proposal的序列号，使用原proposal序列号重试。
- 当一个proposal被成功提交并应用且被成功回复给client以后，client顺序提高proposal的序列号，并记录下收到的成功回复的proposal的序列号。raft节点收到一个proposal请求以后，得到请求中夹带的这个最大成功回复的proposal的序列号，它和它之前所有的应用结果都可以删去。proposal序列号和client id可用于判断这个proposal是否应用过，如果已经应用过，则不再再次应用，直接返回已保存的结果。等于是每个不同的proposal可以被commit多次，在log中出现多次，但永远只会被apply一次。
- 系统维护一定数量允许的client数量，比如可以用LRU策略淘汰。请求过来了，而client已经被LRU淘汰掉了，则让client直接fail掉。
- 这些已经注册的client信息，包括和这些client配套的上述proposal结果、各序列号等等，需要在raft组内一致的维护。也就是说，上述各raft端数据结构和它们的操作实际是state machine的一部分。在做snapshotting的时候，它们同样需要被保存与恢复。
可能感觉让这样重试的request被commit多次有奇怪。其实不奇怪，实际操作中，它们对状态机而言是个NO-OP。原文中的原话也清楚列明这些log entry会在raft log中重复出现，由状态机来负责过滤掉，状态机能看到接触到的自然是commit以后的log entry。
The Raft log provides a serial order in which commands are applied on every server. Commands take effect instantaneously and exactly once according to their first appearance in the Raft log, since any subsequent appearances are filtered out by the state machines as described above.
不是所有的应用都需要这样的功能。最直接的例子就是membership change本身。membership change的时候，比如有一个node的id是XYZ，因为超时你试图去再次提交一个membership remove操作，再次去删除这个id为XYZ的节点，它并不带来实际损害（很多raft库不允许一个已经被删除的节点再次以相同node id加入回来）。
还需要注意的是：请求服务端超时或请求的服务端不为主节点时，能尝试连接其他服务端。