MIT 6.824 Lab3 KVRaft 笔记

本以为写完 Raft 以后，在 Raft 上搭一个 app 想必是行云流水。事实证明我错了，又是踩了许多坑。 T_T

实现思路

How clients find the cluster leader?

我从这开始的第一步就陷入了纠结。Client 自己要存 leader 是肯定的，但我在考虑当 leader 挂掉以后，怎么快速发现新的 leader，想让 server 直接给 client 返回一个 leader 信息，这样就能让 client 更快地找到 leader，而不需要遍历一遍所有 server。但我的 Raft 实现里并没有存现任 leader。

其实这个问题确实是有意义的，不过我不该一上来就想这个优化，这明显不会是一开始的瓶颈。一开始关注大局，搭起骨架，能跑起来才是最重要的。还是那句老话，premature optimization is the root of all evil。

How do you know when a client operation has completed?

这个问题涉及到可以说是这个 lab 里最重要的问题之一：怎么处理「重复」请求，或者说怎么实现幂等性。

基本的思路，没有 failure 的时候是容易的：请求开始时，向 Raft 发送一个 entry，然后等待至 Raft apply 这条 entry 就完成了。那怎么「等待」呢？kvserver 的代码结构应该也是有一个 background worker 负责不断接收 Raft apply 的 command，然后更新状态机，而创造这条 command 的 RPC handler 需要被它通知 apply 完成。

简单用一个 channel 肯定是不行的，因为顺序会出问题。我们需要对一个特定 index 进行等待/通知。自然的想法是那就用一个 map[int]chan 吧。我的直觉又觉得，创建这么多小对象不太优雅，会不会开销很大？嗯…………总之我又是经过一通尝试以后，最后还是回到了这个简单方案。（我去偷看了一眼 etcd，发现好像就是这么做的）

这个只是细节小问题，关键的大问题还是如何处理重复请求：不能重复 APPEND，以及 PUT 旧值不能覆盖新值。

我一开始在想：GET 是不是也有时机问题？重复的 GET 可以直接返回当前的值吗，还是需要缓存第一次成功时候的值？（甚至想做一个 TCP 的滑动窗口那样的机制）后来没做结果缓存，发现根本没问题。现在想来，其实是每个 client 自己是一次发送一个请求的，而别的 client 的请求和它是并发的，就是没有固定的顺序。虽然两次 GET 在 server 端看来读到了不同的值，但其实 client 只收到了一个值，没有问题。

实现上首先容易想到 client 要自带一个 id 和序列号 seq，然后 server 可以记录每个 client 的最大 seq，要是遇到过就是重复请求了。一开始可能会觉得这个检测放在 RPC handler 里就行了，遇到一个请求就更新一下。但这问题重重：首先收到过请求不代表请求成功；更关键的问题是这样 server 之间没法共享 seq 记录，所以必然会失败。

其实 Raft 会重复 apply 是必然的：假设第一次请求超时，第二次请求又来了，此时并不能确定第一次请求的状态。如果直接放弃了有点不太好，如果提交这个 command 那就会重复 apply 了。加上上面说的要在 server 间共享状态，可以想到「去重」这个功能应该放到「状态机」里（而不是单个 server 的局部状态）。状态机中记录每个 client apply「成功」的最大序列号，而不是 server「收到」的最大序列号，就可以完美解决了。

---

故事本来到这里就该结束了，但是我在这里又自作多情，困在了一个自己给自己找的问题上，这可能也是这个 lab 花了我最久时间的问题。上面说了判断请求成功需要 RPC handler 等待对应 index 的 command 被 apply，这里 apply 是有可能会失败的，也就是对应的 index 上并不是这个 RPC 提交的 command，所以 RPC 就给 client 返回了一个「失败」的结果，这没有问题。

但是 client 端要怎么处理这次失败呢？可以直接发起相同的请求重试。但我不满足于此，我觉得，在一般的情况下，client 知道请求失败了，可以选择放弃这一请求，做别的事。关键是 client 明确知道了「失败」，这是一个确定的结果，获得了更多的信息，这在语义上和不确定发生了什么的「超时」是不一样的。因此，虽然这个 lab 要求 client 失败重试，我做了一个小 trick：「失败」后重试时 seq+1。

这一处理给我带来了相当大的麻烦，但是也让我的实现不得不更严谨了，本来有一些细节其实直接重试的话是无所谓的。

最简单的情景：

1. APPEND seq1 成功，但是 reply 丢包了。
2. Client 重试 APPEND seq1 失败，client 收到失败回复，增加 seq 变为2。
3. APPEND seq2 成功。出现了重复 APPEND。

这里的问题在于，RPC handler 里并不做去重检测，只有 apply 的时候会去重。这个问题如果 client 不改 seq 无脑重试的话是不存在的，相当于不管之前的请求是否成功 RPC handler 都选择再提交一次 command，反正状态机会做去重。

这个问题修复比较容易，在 RPC handler 的一开始加一个去重检测就可以了，这可能会稍微减少一些重复提交，但是并不能完全避免重复提交。于是问题就又来了：

1. APPEND seq1，超时。
2. Client 重试 APPEND seq1，RPC handler 里提交完 command 后第一次提交 apply 成功。
3. 第二次提交 apply 失败，返回失败。这里返回了错误的结果，可想而知 client 之后会重新提交 seq2，然后出现重复 APPEND。

这个问题和 lab2 里提过的一个问题很像：发送 RPC 请求前后状态可能已经发生了变化。这里是等待 command 被 apply，道理是一样的。有「等待」就需要考虑等待前后的状态。这个问题的解决也很简单，等待唤醒时再检测一次去重就可以了。

到这里，可能会感觉差不多够意思了，然后噩梦就来了：跑几百次测试，又会出现 missing/duplicate APPEND。慢慢地分析 log，发现情景是这样的：

1. [server A] index 574 seq60 超时（真实结果：成功）。
2. [server B] index 569 seq60 超时。
3. [server B] index 570 seq60 失败 -> seq61。
4. [server A] index 575 seq61 成功。重复 APPEND。

可以发现，出现问题的根本原因是：中途更换 leader。对 leader A 的结果仍然不确定（最终成功了）的情况下，换了个假 leader B，然后被它的结果误导了。换 leader 的行为是必须存在的，否则由于假 leader 无法 commit，对它请求会永远超时。

事情发展到这里，我就不想再继续修问题了，决定回归淳朴，不要让 client 增加 seq，放弃对「失败」语义的执着。我觉得有一个根本的问题，就是状态机里只记录了「apply 成功的最大序列号」，状态机并不知道「失败」，也不存在请求和回复的概念。处理 RPC 请求和回复完全是单个 server 的局部逻辑。在这样的情况下，要让请求有复杂的语义（如果是可以做到的）需要非常小心，处理各种边界情况。因此，我觉得这种设计可能本身就是不太合适的，如果有复杂请求处理的需求，那可能需要考虑再增加一个处理请求的状态机了。

（P.S. 上面这个换 leader 的小问题应该还是容易解决的，因为假 leader 不能 commit，之所以会失败肯定是已经收到真 leader commit 的消息，变回了 follower，所以在 RPC 返回的时候再检查一次是否是 leader 应该就可以了）

Key/Value index

其实这本应该是状态机的大头。但是这个 lab 好像并不太关心存储引擎，做一个纯内存的 hash index 就够了。存储引擎这个话题还是等以后看实际系统再慢慢研究吧。

Snapshot

Raft paper 里提到了它们使用了基于 fork() 的 copy-on-write 来实现高效的 snapshot，不过 lab 里没提这回事儿，暴力锁住 copy 就行了。我也没深究下去。

虽然总体来说实现 snapshot 还是不太困难的，但是要考虑的细节依然不少。诸如更新 commitIndex，是否要删除多余 log 等等情况，一不小心就写错了。这种东西可能还是最好要先想清楚各种情况然后再实现，可以在纸上先画画。

踩坑记录 & 心得体会

Raft 没测出来的问题

TestSnapshotSize3B 非常慢

这个问题在 lab 2 的笔记里已经说过了，原因在于这个测试的 pattern 是每次先请求指令，等完成了再发下一条，所以对 latency 有要求，要在请求来时主动额外多发一次心跳就可以了。

这个问题拖到这么后面才出现，其实还是有点难排查的，稍微有点不合理。

TestCount2B: only 2 decided for index 6; wanted 3

lab 3 写着写着也重跑了一下 lab 2 的测试，结果出现这个问题，有点吓人。看日志发现明明达成了一致，却没有 apply 是怎么回事。仔细看是有一个 server 更新 commitIndex 之后没有 apply，是 applier 里的 Cond 没有被唤醒。原因是我写出了这样的代码：

for {
  mu.Lock()
  cond.Wait()
  toApply = copy(...)
  mu.Unlock()

  for _, cmd := toApply {
    applyCh <- cmd
  }
}

又是一个有点小聪明的优化：觉得 apply 开销比较大，甚至可能 block，所以先复制再 apply，apply 的时候不需要锁。其实还是有点道理的，但是这就带来了 Cond 丢失唤醒的问题。解决的话要么就老老实实带锁 apply，要么需要再加一个定时唤醒 Cond 的 worker。其实我在做 kvserver 的时候也有担心过类似的问题，没想到在这里遇到了。总之丢失唤醒是一个使用 Cond 需要考虑的问题。通常的提醒是：不持有锁的时候唤醒可能会丢失。但我这里主动释放了 Cond 醒来后带的锁，所以就算持有锁唤醒，这儿也可能丢。

之所以这个测试会出现问题，是因为这里 cfg.one() 要求「成功」，而且参数 retry 是 false。看注释就知道了：

if retry==true, may submit the command multiple times, in case a leader fails just after Start(). if retry==false, calls Start() only once, in order to simplify the early Lab 2B tests.

其他测试要么不要求「成功」，只需要达成「一致」，要么是会重试的。

AppendEntries

一个 3A 早期卡了很久的大问题。现象是出现 missing append。看 log 追踪到如下情况：

1. Follower（4，4，4，4，4），括号内为 entry 的 term。
2. Leader （4，4，7，7）
3. Follower 收到 AppendEntries，变为（4，4，7，7，4）
4. 下次选举，follower 投票给了 outdate candidate（term < 7）。

问题很明显了。原因是我一开始的 AppendEntries 将 PrevLogIndex 之后的原有 entries 一概删除，后来（上次说了踩坑之后）改成了仅当 PrevLogIndex 有冲突的时候才删除。但这还不够，没有冲突也不能简单覆盖，还需要逐项检查。看 paper 中其实说的很清楚：if an existing entry conflicts，并不仅仅是 prev entry conflicts。

又是一个在 Raft 的测试里没测出来的问题，分布式系统真的处处是坑，真需要咬文嚼字啊。

日志的重要性

在分布式系统里不能单步执行，不能依赖 debugger 了（虽然我也不会用），log 对排查问题非常重要。以前，我已经感受到 log 相比无脑 print 的优越性了，在 lab 2 中我也会尽量多打印一些有用的信息。但是在 lab 3，我发现做的还是并不够。

我一度觉得出了问题，看问题周围几十上百行 log 就差不多够意思了。但并发量大的时候，有海量的无关信息。因此，需要日志可搜索、可追踪。我一开始在 lab 2 里的日志很随意，例如 DPrintf("%v: var1: %v, var2:%v, do something", rf.me, v1, v2)，这首先有个大问题就是我没法追踪一个固定 server 的日志了，因为只打印了一个数字，没办法搜索。其次，因为没有固定格式，在搜索一些东西的时候可能要写很复杂的正则表达式（凭我蹩脚的正则表达式水平勉强拼出来）。在 lab 3 中，我就更注意了一点，例如会打成 DPrintf("[kvserver][me: %v] balabala ...", kv.me, ...)。由于我到挺后面才被难看的日志恶心到，所以也没有全面改造（还是不得不改了一些）。更进一步，其实还可以使用结构化日志，更加规范要求；也可以对对象实现自己的 log 方法，固定打印一些常用的变量。总之，不管具体实践如何，日志应该是个从一开始就要考虑，不能草率对待的东西。

另外，在排查问题的时候，尤其是性能问题，我有时候还想统计一下 RPC 调用的次数。我通过打日志的方式实现了一下，但这会让日志膨胀得很厉害。这个问题让我感受到了对监控系统的需求（Prometheus & Grafana？）。

last 是上一个还是最后一个？

其实 Raft 里好像没有这个问题，上一个就明确是 prev，last 只表示最后，而且我自己也没写错遇到问题被坑到。只是我自己看代码还是会产生迷惑，想到这个问题。总之，尽量要区分，甚至避免使用容易出现歧义的命名，虽然凭语境可能很容易区分清楚，但是不要给自己带来处理额外信息的心智负担。

goroutine leak

我在测试中遇到了这样的情况：测试超过 10 分钟，强制结束，显示有两百多个 goroutine，很多等待了超过 8 分钟。

有一个卡住的位置是在 Raft 的 applier 里 applyCh<-。这个会卡住应该是因为 kvserver 被 Kill() 了，不再消费消息了。我一开始 Kill 里没有处理逻辑，但是所有 background worker 的循环都加了 !rf.killed() 的条件，本以为这已经足够了。但虽然循环次数不会无限了，循环内部还有无限等待的操作，可能会卡住。因此 Kill() 内需要做一些回收操作。除了 applier，还有几个地方类似。

当然，测试卡住并不是因为这个，而是其他地方的逻辑错误，这里是顺手解决一下问题。

真实的一个导致卡死的逻辑错误：kvserver 里，我传消息的方式是每个 index 对应的 channel 大小为 1，因为不会重复 apply 相同的 index。但是在 InstallSnapshot 之后，有可能 lastApplied 会变小，于是就重复 apply 了相同的 index，就有可能在相应的 channel 上卡住了。

解决这个问题，要么可以拒绝 install 太老的 snapshot，要么可以在 install 之后重建一个新的 map[int]chan。

小结

看了一下写完 6.824 的 Lab 1-3 做了一个月，一共花了 95 个小时（WakaTime 数据），一开始实现其实也还好，到最后 debug 真的是花了几十小时，有点体力活的感觉。尤其是跑几百次测试可能才出现一次的 bug，看了半天日志，修好了，结果过了几个小时跑了几百次又出了新的 bug，真叫人有点绝望。分布式系统 debug 确实不容易，出现问题难以复现，所以需要各种手段的帮助，比如良好的日志，测试框架支持（如果在网络正常的情况下测试，那得多久才能发现问题？混沌工程真是意义重大）。

收获

• 领域知识：Raft、single-leader replication

• 编程实践练习：
  • 多线程（协程/任务）编程：
    • 等待与通知
    • chan 和 select
    • Mutex 和 Cond
  • Background worker
  • Bash script
  • 计时器
• 经历了一些常见的问题：
  • 阻塞操作（RPC 调用、channel）前后状态可能不一致
  • 改代码要 find all usage 检查多处一致
• 如果抽掉一切技术细节，剩下的 takeaway 我想可能是：
  • 设计好了再开始实现，要想清楚不同情况下的行为规则。让代码忠实地遵守规则，并通过一些手段来检验和保证。
  • 在实现的一开始就要考虑如何为排查问题设置辅助手段（这里是 log），不要轻敌，不要过于自信。
  • Debug 要有耐心，也要动脑子，对问题敏感。