终于吧lab3调通到1k次运行稳如狗了. 写这个lab我感觉还是得靠坚持. 看到极低概率的失败还是心里会咯噔一下的. 不像是lab2, 照着论文算法按部就班老老实实写出来, Lab3给我感觉提供了更大的发挥空间, 很多种实现方式, 得自己来设计一些关键的步骤.
剧透警告
如果你还没写lab3, 最好不要看, 不然错过很多东西
关于client request去重
lab3 的 client 再于server失去连接的时候, 会尝试重新提交本次请求, 到不同的server上. 失去连接可以是timout, server lost the leadership, server crash. 这时候我们让每个client自己生成一个全局的global id, 由于client能保证序列化地发出请求(这个无伤大雅), 我们在server 端存好最近一次这个client的请求即可. 具体方式见其他博客.
为什么不能简单地在kvserver向raft提交command前挡住duplicated request
一种看上去直接的方法是, kvserver保存好每个client的最近的request记录, 在提交前做一次判断.假设这个request已经见过, 返回ErrWrongLeader. 当kvserver从raft收到到这个command的时候, 对最近request记录做一次更新.
可惜这种方法是错的. 假设kvserver向raft提交后并且在raft读到这个command前crash. 此时我们是无法判断这个command是否成功的. 可能的情况是,
- raft成功append复制到小于majority个follower, 然后挂掉.
- raft成功append复制到大于majority个follower,
- commit前挂掉
- commit之后但是apply command前挂掉
- apply command后但是返回client 前挂掉
上述2, 的各个子情况其实并没有区别. 此时2已经是事实上的执行成功了(虽然还没返回给client). 注: 对于2. 成功复制到majority的情况下不一定会被commit, 见论文figure 8 , 但是leader自己的term内的command成功复制到majority一定会被commit.
然后某个时候, 新的leader被选出来, 此时两种情况:
- 这个command 会在将来的某个时间点被commit (2情况和1情况 )
- 这个command 不会在将来的某个时间点被commit(1情况)
对于上述情况2. 此时client重新发送请求是ok的 没有重复. 对于情况1, 此时如果client在这个新的leader还没来得及收到这个command前任意一个时间点 (# 1), 对leader进行同样对请求, leader一看, 这个请求是新的, 好, 我给你提交. 此时当这个新的提交再次成功并且进入kvserver时候 (# 2), kvserver对这个提交又做了一次操作. 此时正确性被破坏.
现在绝大部分中文博客的解决方法是, 在kvserver在所有收到的command里作去重判断,也就是上述(#2)处, 如果看到了一个已经被执行过的command, 则不做任何操作并且向client返回成功. 这种方法简单有效, 不过每当client重复请求时候, 都会有一个新的command通过raft被复制, 进入到每个raft peer的日志里.
一种重复请求不进入raft.log的方法
这里的问题就是, 新的server启动后可能老的server还在运行. 老的server虽不能处理外界请求, 但是还是能持久化数据. 导致新的server可能无法读到 老server刚刚写下的client id成功记录. 导致操作重复. 针对于通过test而言, 请用通用的方法. 我这个方法得假设老server和新server不能同时运行. 这个问题还是我写到lab 4里其中一个疯狂做snapshot的case才发现的. 实际情况下我的方法应该是ok的
分割线 ————————————-
针对上述情况的分析, 不难发现, 如果我们能保证kvserver只在(#1)之后接受请求, 那么就可以按照之前所说的在提交给raft前把重复command挡掉.
怎么做呢? 首先, kvserver记录所从raft的applychan那边见过的最新的的term, 我们叫它kvterm. kvserver接受请求时候, 问一问rf.getState()来判断自己此时还是不是leader, 还有当前raft的term.不是leader直接拒绝. 如果是leader并且此时raftterm > kvterm, 拒绝这个请求. 如果raftterm >= kvterm, 则进入判断是否见过这个command, 如果见过,再进行提交.
当raftterm == kvterm 时候, kvserver已经见过了所有这个client的所有成功的term < kvterm 的command. 对于term==kvterm的command, 肯定都是通过这个kvserver(是leader)发出的, 所以也拥有足够信息来正确的判断是否为重复请求.
另外一个要注意的点是, 假设新的leader被选举出来后, 只有这一个client在发送请求, 因此kvserver无法再见到新的属于自己当前term的command, 就一直拒绝这个client. 解决方法是每当新leader被选举出来的时候, 提交一个no op到日志里. 这种方法在raft论文里有被提到, 是作为新leader发现raft commit到哪个日志的一个方式.
同样的, 新leader提交no op也能带来如下好处: 当只有一个client的情况下, 这个client正在等待kvserver返回结果, 但是kvserver的raft此时在成功commit前已经失去leadership了. 一旦有新的leader成功选举, 就能获知, 对这个client立即返回ErrWrongLeader
最后
lab3 写出来之后才去看网络上的博客的做法. 发现很多地方真的和自己的实现大相径庭. 难怪6.824的code要求:
You are not allowed to look at anyone else’s solution, you are not allowed to look at code from previous years, and you are not allowed to look at other Raft implementations. You may discuss the assignments with other students, but you may not look at or copy each others’ code.
如果写之前参照了其他人的实现, 我可能不会有上述的思考, 也不会理解为什么要这么做.
这门课真的让我收获巨大, 也让我体会到了国内高校在计算机课程教学方向和国外顶尖大学仍然有一定差距. 希望我们国内高校能早日有像mit 6.824这样的课, 真正早日成为世界一流大学.