终于到了 Lab3 了，写一个 KV 服务🐍
# 要求
lab3 需要构建一个 fault-tolerance key/value storage service。用到之前 lab2 写的 Raft library。
三个 api 接口：
Put(key, value),Append(key, arg), andGet(key)。如果 key 不存在，Get(key)返回空 string，并且append与put操作等价。each client talks to the service through a
Clerkwith Put/Append/Get methods.实现强一致性。
达成效果
![image-20220309191901863]()
# Part A
每一个 kv server 都关联了一个 raft peer。
实现 Put 、 Append 、 Get 。kvserver 先 raft 提交这三个 operation，raft log 写这三个操作的序列。
kv server 由 raft 决定应该执行什么 operation。
Clerk 并不知道谁是 leader，因此如果 Clerk 发送 RPC 到错的 kvserver，或者不能到达这个 kvserver，那么 Clerk 需要重新发送到另一个 kvserver。
如果这个命令 commit 之后，那么 raft 会 apply command，亏 server 会先执行的结果返回给 Clerk。
如果 operation 没有被 commit，那么 server 发送一个 error，然后 Clerk 需要重试。
# 我的思考
client 通过 clerk 发送三种 operation，这三种 operation 只能被 leader 来执行。只要是 leader apply 的 operation 一定是 commit，这毫无疑问。现在的问题是如何让 kvserver 来检查这个操作是执行的呢？
Put 和 Append 操作只能被执行一次不能被多次执行，这一点需要注意。
对于 command，需要设计一个格式，能够让 kvserver 知道 operation 是什么。因为 command 就是一个 string。
按照要求也就是说 client 如果没有执行成功某个 operation 就会一直被阻塞。
我关于 PutAppend 的考虑，因为操作需要去除重复，因为 client 需要并发。所以不能
# Raft 实现线性一致性
多用户并发（每个 client 只是调用一个请求）
It's OK to assume that a client will make only one call into a Clerk at a time.
提升中也说了，可以假设 client 每一次只是 call 一次。
it's OK in this case for the server and client to wait indefinitely until the partition heals.
也就是说可以让这个 wait 无限制等下去。（等 commit 可以不限时间）
但是我们能不能操作一下？搞一个超时？
我没头绪的时候，看到了 Raft 博士论文，真的感动啊。
按照这个参数写 RPC 就行了。
# 去重复
我们假定每一个 client 每一次只是执行（call）一个操作，并且如果执行失败的话，那么它会阻塞住，并且一直执行这个请求。
这样去重复就很简单了，我们只需要在 server 端维护一个 lastComandID 就行了，数据结构为 map []
# 3.9 号更新
最近一个非常严重的 bug 卡了我一天，怎么都没办法处理好。是关于线性一致性的，我一直没有怎么理解线性一致性这就导致我这个 lab 做得很痛苦。
先看一下 raft 作者对线性一致性的理解：
In linearizability, each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response. This is a strong form of consistency that is simple for clients to reason about, and it disallows commands being processed multiple times.
注意这个 exactly once， at some point。也就是说所有操作都只能执行一次，并且是原子性瞬时的。这似乎有些奇怪，因为我们明明可以执行多次的，因为当有请求到 kv server 时候我们就进行了一次写 raft log，然后因为超时原因我们又一次向 raft 发送了请求，有一次写了一次 raft log。所以在 apply 阶段，为了实现这个 exactly once 我们需要对操作进行去重复，保证所有操作只能执行一次。
但是问题还没结束，去重真的保证了线性一致性吗？注意作者这句话：at some point between its invocation and its response. ** between its invocation and its response. 是关键所在，也就是说我们的执行是要发生在调用和返回之间的。但是在上面的描述中，我们是怎么操作的？如果当超时就重新发送请求 **。这意味着那个超时的请求已经结束了，它没有在调用和返回之间执行！
来看下面这个场景：
这里有三个 client，并发发送请求。现在我们把问题简单化，只是对 log 中的一个变量 x 进行考虑，它初始为空，A1 表示向 x Append 1。R 表示读这个变量 x。
注意！这里我的线段表示 client 发起某一个请求到结束的时间，这段时间内 client 可能因此超时等原因多次发送重复的请求，知道最终收到答复。
因为 KV server 首先执行了 A1、A2。所以这时候 client1 先读取 x，它读到了 x 的值为 12。但是因为 rpc 调用等原因，这个读取到的值没有返回给 client。那么 client 肯定会重新发送读请求的。但是因为去重，我们不能再执行这个读操作了，于是我们把这个读到的结果存起来。等下一次 client1 发送读请求的时候直接发送存好的结果。
ok，client3 此时执行了 A3，x 的值变为 123，那么 client2 再读后就读到了 123. 并且直接返回给了 client2。
过了一会，client1 也读到了结果，x 值为 12。
于是这就没有了线性一致性了，因为 client1 读到了一个旧的值！
为什么会出现这个情况，因为我们违背了：
each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response)
client 的读操作持续了很长一段时间，而不是 execute instantaneously。
我的思考就是，读请求不能进行去重，也就是说它只能在当前的 KV request 得到处理。
其实教授在课上讲到过这种场景，Read 操作返回旧值并不一定破化了一致性。
比如 C2 的 read 操作，在箭头处后面它会返回 4，但是在箭头处之前它可能返回 3。rpc 有网络延迟，所以客户端是可以接收到旧值的，但是这并不意味着破坏了线性一致性，因为这个旧值不是 server 希望的而是 client 看到了。
# 3.10 号更新
遇到问题，10 次测试里面总是会一次测试莫名奇妙丢失 log，导致数据在不同的 kv 上同步失败。。。很失败，我打了一天的 debug，还是没有找到原因。
我知道问题出在我的 raft 层，但是即使我查看了很久，我也没有找我我的 raft 层问题出在哪里。。。。
- leader 选举可能有点问题，导致选举了不应该成为 leader 的节点，致使覆盖了后续的日志。但是这个可能性不大
- AppendEntries 出错，没有 commit 的 log entries 认为 committed 了，这就导致后续这个丢失。
问题是我没有找到这个导致怎么情况。。。就这样吧，心累了。。。
而且 3B 是真的过不了，必须代码重构，把 raft 重新写一遍。。。感觉心好累啊。
# Raft 重构
参考代码：
# 3.12 号更新
愉快打过 lab3
