MIT 6.824 Distributed Systems 分布式系统课程系列3 Lab3-Fault-tolerant Key/Value Service

• 实验主页：https://pdos.csail.mit.edu/6.824/labs/lab-kvraft.html
• 任务：在raft基础上实现一个分布式可容灾的kv服务。

1.介绍

• 在Lab2中我们学习并实现了raft算法。有了raft，我们其实已经实现了数据的一致性存储和容灾。
  比如起3个raft节点，把一批数据存进某个节点，数据在三个节点上都会保持强一致性。
  整个系统可以承受在某个时间点有1个节点出现故障。
  如果配置大量节点，比如9台服务器，可靠性会非常有保障。可承受4台机器同时出故障

• 这次任务是在raft的基础上实现一个key/value服务。
  虽然是一个相对简单的kv服务，但是掌握基本技术之后可扩展为更复杂的应用，比如分布式数据库或分布式文件系统等等。

• 任务分为AB两部分。A部分是基础的kv服务。B部分引入log压缩(log快照)。

2. kv服务

架构

• 有数个raft节点。实现数据一致性。

• 有数个kvserver实体。存储实际的kv数据。可看作数据库实体。
  一个kvserver绑定一个raft节点。

• 可有任意多个client实体，即客户端。可以看作连接数据库的客户端工具。

• 比如有3台机器，每个机器上跑一个kvserver，每个kvserver里包含一个raft节点。
  raft节点之间可互通。kvserver可与自己的raft节点交互。
  client为任意多个，可与任意kvserver交互。

数据

• 数据就是简单的key和value键值对。都是string类型。

操作

• 实现3个操作：Put(key, value)赋值，Append(key, arg)追加，Get(key)取值。

实现

一些要点

• 只要多数server能互通，client发命令必须要能返回，不能无限卡死。否则允许卡死。
• client发一个命令必须等到server回复才能返回。这里肯定是简化了，现实应用肯定得有个超时提示。
• 没有commit的log可能被清掉(别的命令覆盖)。一旦commit，就不能被清掉，如果发生，那数据就坏了，就是实现有问题。
• 看一下论文第8章，少走弯路。

基本流程 TestBasic3A

• GenericTest是通用的测试流程。包含起kvserver，起client，发命令，设置网络故障、网络分组，重启节点等各种测试流程。

• 最简单的测试。5个server

• make_config
  对每个server调StartServer(我们实现)进行我们kv服务的初始化：起一个KVServer，KVServer包含一个raft节点。

• makeClient
  用MakeClerk(我们实现)创建客户端(他所谓的clerk)。

• 一些初始化后进入测试循环。

• spawn_clients_and_wait
  起一个channel
  用run_client起一个client并调用循环里的闭包
  等待channel的数据

• 闭包函数主要做一顿kv操作。先put一个值。
  再进入一个循环(会持续5秒(见done_clients))，每次随机选一个操作：

1.append。key是server id，value是根据循环造的一个值。并记下append后的值。
2.get。用key获取获取value，跟记下的值对比。不一样就是测试失败。

• 5秒过后
  做一些模拟(断网、重启等)，现在是最简测试，所以跳过。
  对每个server的kv进行检查(checkClntAppends)。因为存入的值是定了规则的，所以可检查正确性。
  最后对log的大小做一些检查

• 代码可总体分为3层：client，server，raft。
  client可看作各种数据库连接工具。处理人类或测试程序发来的请求，与server交互，获取结果。client可以自己选择连哪个server
  server实现kv存储，与raft系统交互，根据raft的指示来执行实际的kv操作。
  raft负责每个kv操作在整个系统中的一致性。
  例如一个命令来了以后，raft得把它安全复制到多数server后才通知server这个命令已经完成复制了，可以执行。然后各个server才能执行这个命令。然后client才能看到这个命令执行的最终结果。

• client.go里。Get和PutAppend，直接给server发Get和PutAppend的rpc。
  client把命令发给谁？
  应该找leader发，并记录每一次的leader。如果leader改变，rpc应该返回相应的错误，client就找新的leader。

• PutAppend怎样算成功？
  命令提交给raft，按说要等raft把这个命令复制到多数server，再发apply消息后，kv服务才真正执行PutAppend，再返回成功。
  看测试代码是Append之后必须Get到正确的值，也就是应用层面是不考虑任何超时的。
  所以为了迎合测试，每次发命令一定要等到正确执行才返回。
  在server里rf.Start()之后，要死等apply消息，等到才返回。
  这里可以思考一些异常，如果leader apply这个之后马上挂了。下次这个client发命令时会连一个新的leader。这时会不会造成重发？各server的命令数据是否正确？

• rpc的reliable问题
  发rpc如果能收到正常回复，无论成功还是失败，都是好的。
  如果rpc无响应，就麻烦，无法确定是什么情况。
  测试程序可以模拟rpc不稳定，可能

1.对端收不到rpc(不执行)。
2.对端收到rpc，执行以后，回复结果时网络不通。
这两种情况rpc都会失败，得重发，但是2的情况可能造成一条命令重复执行。
想到序列号的方法，给每一个命令做一个唯一的sn，收到命令后每次判断一下sn是否已经执行过，就可能避免重复执行了。也保证了操作的幂等性。怎么做唯一sn？现实中应该也是很有讲究，这里直接用随机数简化。

• ApplyMsg的接收
  在每个kvserver里起一个ApplyTask的goroutine专门收ApplyMsg(在lab2里是测试程序收的这个消息)，收到就实际执行命令。
  对于不是收命令的server，不做其他事情。
  如果是该server接收的命令，那么得通知client命令已经执行完，让client返回。前面说过现在的模式是client发命令必须死等一个确切的结果。
  我加了另一个channel来传这个消息。

TestOnePartition3A

• 这个测试把server分割成两个群体，把当前leader放在少数群体。

• Put(cfg, ckp2a, “1”, “15”)发到少数群体，是无法commit的，也就无法apply，client也就阻塞无法返回。
  直到走到”Test: completion after heal (3A)”，恢复所有网络，p2的leader发的ae可以传到p1了，p1的leader发的ae也可以传到p2了，这时p1的leader的term一定是领先p2的，因为分割后p1没有leader，一定会选一个新的，term变大。
  那么p2的leader一定会变成follwer。p2接收的Put命令会被p1的命令冲掉。kvserver应该返回wrongleader给client，client重新找leader发这个命令。
  重点是kvserver执行命令等结果期间要能识别自己的命令被冲掉(因为自己的leader身份失效)。

• Get()必须从多数群体中获取，否则可能获得失效的数据。
  课程提示一个简单的方法。可以把Get也看作PutAppend，也走一遍一致性流程，这样肯定是从多数群体取值了。

• 一个死锁问题
  LeaderSendAE里发ApplyMsg时我是先锁住rf然后进循环挨个检测index是否可以apply，有时会出现一次可以apply多个index的情况。
  那么问题来了，循环里会往channel发消息，这样就带着锁到了一个kvserver的线程，这个线程里又会走到一个rf.GetState()的检测，GetState是要锁的。如果LeaderSendAE的第二个消息没发出去，就走到GetState()的话，就死锁了。
  把ApplyMsg消息的发送挪到一个单独的goroutine，结构更好，耦合低，循环检测，每次循环加锁就行，解决问题。
  其实lab2也是这么推荐的。

• 后话，挪到单独goroutine后，后来偶尔发现lab2的TestFigure8Unreliable2C居然过不了，能达成一致，但是很慢，耗了三分钟，测试程序最多给2分钟。而不挪出来只用40秒。
  因为挪出来后，循环里要每次加锁，这样死循环争锁影响了性能。
  还是改为最开始的方式，循环外面加锁，里面发消息。而接受消息的代码之前刚好做了优化，不连续发消息，而是设置kv的全局变量，另起goroutine来监控。所以不会死锁了。
  注意死循环里看情况要加个sleep，否则会很卡。
  最终形态就是死循环里每轮sleep10毫秒，争锁，然后循环发一波apply。
  但是有个问题，在最坏的情况下，每一波只能apply一个命令的话，还是很耗时。当然如果每次来一个命令也说明命令不是很多。
  一个很好的优化就是把多个apply打包一次发走。暂时跳过。

• go test -race的问题
  可以检测可能的race condition。比如有个变量某一处加了锁，另外一处没加，运行时如果出现篡改的可能，它就会检测出来报错。
  是否有必要？比如有的地方我绝对有把握不会死锁。
  如果统一加上锁肯定能避免一些难查的死锁。在lab2里试过，感觉有的地方略显啰嗦。特别是打印变量时，比较繁琐。

以下走进了死路

TestManyPartitionsOneClient3A

• 一个client。随机分组。
  发现一个问题。如果client发了一个命令cmd1，leader1短暂变成follower，client返回准备重发cmd1，leader1这时又变成leader.
  那么记过就是client认为只发了一个cmd1，但实际leader1上存了两个cmd1。
  问题在于client被返回wrongleader时，第一个cmd1没有被删除。一般情况如果有leader2取代leader1，那么会把cmd1擦掉，没问题。
  但如果leader1又做回leader，那么老的cmd1就会保留，出现重复。
  可能的解法：
  start会生成一个index，跟踪这个index，如果能apply，没问题。如果被擦除，返回wrongleader。其他情况都死等。期间不要自行检查leader。

• 这又会引出一个问题，一个命令可能会单纯被清掉而不是被覆盖(比如一个高term的leader1复活，发ae给leader2，leader2变成follower并且被清掉不同的命令)。
  考虑上面说的情况：（ca为commit和apply。t1为term1。）

| | 1 | 2 | 3 | 4 | 5 | 6|
| — | — | — | — | — | — | — | — | — | — |
|2 Leader1| put’’0 ca | x 0 0 y ca | x 0 1 y ca t1 | x 0 2 y t1|
|1 Leader2 | put’’0 ca | x 0 0 y ca | x 0 1 y t1 | t2|
|3 | …|
|4 | …|
|5 | …|

• 2先当leader，给2发一个命令，未复制成功时，被独立分割，1再当leader。
  这时把1和2联通。1和2的身份都是leader。
  2给1发AE会失败，因为term小。
  1给2发AE会成功。因为1、2两点都通过。

• 问题是到底需不要把2的index4上的log删掉？
  论文图2收AE的第3点。字面上是如果出现冲突要删掉冲突和之后的log。目前的实现是删掉。
  如果把index4删掉，然后白等，就会导致index4没法apply。导致client卡死。因为按上面的等待index的实现，没考虑直接删除index4的情况。

• 如果不删，这时2会变成Follower，1继续做leader，虽然2比1多一个命令。
  如果这时给1发命令。1会发ae把2的index4冲掉。
  如果一直不发，那么2的index4的命令永远得不到返回，造成cleint卡死。那么这个情况按理要给这个client返回wrongleader吧。

• 想个办法，还是按删掉的实现来。
  raft做个接口查询某个index上的命令。kvserver定时把正在等待的index查一遍，如果发现被删除，那么返回wrongleader。

按这个思路来，感觉问题越来越多，越来越复杂。是不是钻了牛角尖？

• 再从头理一遍client的交互。
  client发命令，每个kvserver里起一个map判断重复，记录每个client的最高sn。
  防止的是：实际commit但没有返回给client，比如rpc故障，client又把命令提交一遍。
  这里有个问题，如果这时出了新的leader，client重新提交给新的leader，是否能防住？
  如果是的话，那么是可以在kvserver里给等待命令设一个超时的，不死等index，而是返回让client重发命令。直接从源头解决了问题，不会造成client卡死了。
  为什么重发命令给新leader可以判断重复？

| | 1 | 2 | 3 |4 |5 | index|
| — | — | — | — | — | — | — | — | — | — |
| —–>0 Leader | cmd1
| 1 | cmd1|
| 2 | cmd1|
| 3 |
| 4 |

• client先连0，成功复制到012，commit，这意味着cmd1在系统里是确定的，一定会执行，不会被清除。
  当raft返回apply消息到kvserver时（这里简化为一定能成功返回apply消息），kvserver会记录cmd1的client和sn，这样后续就能判断重复了。
  注意，发到0，但是012收apply消息时都会记录。这样后续再发到012时都能判断重复了。
  下一个命令有没有可能发到3或4，不可能，因为34是少数，不管网络怎么分割，新leader一定是在012中产生。
  也就是说只要命令得到成功复制，新的leader一定存了这个命令的唯一标识，一定可以判断出重复。
  一个不爽的地方是重复的命令也会存到raft的log里，如果要做恢复数据等操作，还需要判断重复。

• 因为开始没有完全想清楚判断重复命令的细节，所以绕了弯路。
  最后在kvserver等待index那加上超时返回wrongleader，让client重发。解决了重发问题。
  过了partitions, one client和partitions, many clients这两个测试。

TestPersistOneClient3A

• 从这开始，会重启kvserver。raft的log已经实现了持久化没问题，但kvserver也是有很多状态和数据的。
  课程里好像没有直接提怎么恢复kvserver的数据。只在Part B开始时带了一句，As things stand now with your code, a rebooting server replays the complete Raft log in order to restore its state.
  那么就从raft的log里恢复数据试试。
  replay比想象的要容易，把rf的log跑一遍，同时更新命令sn信息，判断一下重复命令不要执行就行了。

• 到这里3A都通过了测试。跑一遍耗时4分钟。

go相关

• 发AE时rpc传的arg参数在接收的地方变成了nil。
  导致panic: runtime error: invalid memory address or nil pointer dereference
  最后定位到labrpc.go的dispatch函数和value.go里的Elem()。
  估计是新的命令类型造成。之前的命令是一个int没有问题。
  我直接传的PutAppendArgs类型报错。后来用了server.go里他定义好的Op类型就不报错。搞不懂，用不同文件的类型会出这种错。
  一堆reflect、value、type比较底层的东西，看不懂放弃。有恶心到。

• 简单情况下，channel如果没有人接收消息，发消息就会一直阻塞？

• 消息里放int64好像有时发不出去。不确定。

• 居然不能直接给map里的某个元素赋值

3. log压缩

论文解读

• log不能任其增长。如果量巨大，即占空间，replay也很耗时。
  需要一个机制来把老的的log信息给挪走。

• “快照”是一种最简单的压缩方式：
  在某个时间点，当前系统的整个状态会存为一个快照并持久化备用，然后把这个时间点之前的log删除。

• chubby和zookeeper都用到了快照。

• 作者又比较了一下其他的log压缩方法。结论是快照更简洁。

• 图12描述了raft的快照。
  一个快照包含了最后的term和index，以及每个key的当前值(只保留最新的值，过程(log)丢弃)。

• 图13描述了具体算法。即“安装快照(IS)”rpc。
  IS一定是leader发出。可分次发送（我们实际不实现），可作为一次心跳。

流程

1. kvserver每次收到正常apply的命令后需要检测一下raft的log大小，超出一定值就要发起存快照的操作。
   把本地kv数据发给raft，raft删除被快照覆盖的log，再把快照和log持久化。
   重要的原则是保持所有数据不丢，要么在快照里要么在log里，并已经持久化。

2. 每个节点只保存一份快照。保存快照后，要记录快照最末log的index和term。

3. leader发AE时如果对端需要的index落在自己的快照里，给对端发自己的快照，即InstallSnapshot RPC。
   否则正常发AE。

4. raft收到快照后判断有效性，再把快照发给自己的kvserver，kvserver拿到后直接覆盖本地kv数据。log和快照都要做好持久化。

实现

• 引入快照后，log的一些边界上的操作可能需要大范围改造，改得更通用、清晰，是一种进步。
  改动后一定要保持lab2能通过测试。
  可能需要折腾一番才能稳定下来。

一个错误场景

• TestSnapshotRecoverManyClients3B报错。get出来的值是值比预期要短，是个旧的值。

• 原因：raft收到有效的快照后，把本地log清空，发给kvserver安装，但是没有持久化。
  如果这时服务重启，这个raft节点选为leader，数据就丢失了，因为log删了，log持久化了，但快照却没持久化。违反了上述数据不能丢失的原则。

go相关

• go test -race的问题
  出现一个经典的ab/ba死锁的情况。检测不出来。具体没懂。

• channel的问题
  循环阻塞读消息进行处理，里面加锁，容易死锁。可改成读出消息后进队列，再另起goroutine循环处理。