2022.12.18 完成了 Lab2B，内容是实现 Raft 的共识算法。经过 200 轮测试的检验没有发现问题，我就当作实验完成了。这里记录一下过程中发现的比较有意思的 bug。它们不一定很难修改，很多也都明确地写在 Raft paper 的 Figure 2 中，但是去思考它们为什么会导致错误，什么情况会触发这些错误，是很有意思的一件事，并且能帮助我们更好地理解 Raft 这个系统，想到读 paper 时没有想到的问题。
Livelock
有时会发生这种情况：系统虽然在线，但不再做有效的工作，连心跳都不发送。打印许多日志后发现集群（由3台机器组成）一直在选举，而且永远是同一个机器竞选，而另外两台机器拒绝投票，因为 Candidate 没有通过 up-to-date 检查（Raft paper 5.4.1）。这个 bug 错在 RequestVote RPC 的接收方不加判断地更新重新选举定时器，正确地做法是仅在投票时更新定时器，拒绝投票时不更新定时器，来保证自己可以正确地超时、启动竞选。在这里，Candidate 没有通过任何 Follower 的 up-to-date 检查，说明它无法竞选成功，要使系统继续工作，需要另外两台机器之一超时启动竞选。
类似地，AppendEntry RPC 应当在 RPC term 没有过期时更新定时器。注意这不要求 RPC 成功，因为 RPC 可能因为 log 不一致而失败，这时 Leader 会自减 nextIndex[] 并重试，这仍然构成一个 Heartbeat，应当更新定时器。
错误地认为 log 冲突导致不必要的删除
在 Raft Paper Figure 2 中，AppendEntry Step 3是：
If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it.
我曾经在比较 term 时出错，用 existing entry 的 term 与 AppendEntry 的 term 比较了，正确的做法与 AppendEntry 中新的 Log Entry 的 term 进行比较。这可能会导致不必要的删除日志，因为传输的新 Log Entry 不一定是当前 term 的内容，也可能是之前 term 的内容。
这会导致问题的场景是：如果 AppendEntry 在网络中经历了较高的延迟，RPC 可能已经过期，正确做法下两条 log 不会冲突，所以不会删除，而这个错误会导致删除这条以及其后所有的 log，而我们很可能之前已经告诉了 Leader 我们拥有那条 log。如果集群中拥有这条 log 的机器数刚好过半，Leader commit 并应用到状态机上，这时我们删除了这条 log，拥有 log 的机器数就不再过半。如果此时 Leader 再离开集群，重新选举的 Leader 就不一定包含这条 log 了（正常情况下，新Leader 包含这条 log 这件事由 5.4.1 的 up-to-date check 保证）。也就是 committed log 被回滚了。
助教的这篇博文也提到了这一问题。
这个 bug 是我阅读代码发现的。这可能并不好测试，根据我的理解，6.824 的测试用例并没有模拟乱序的网络通信。
CommitIndex 的激进更新导致某些机器做出错误 commit
问题在于：TestBackup2B 会有很小的概率失败，原因是某台机器作出的 commit 和其他机器已经作出的不一致。这个问题困扰了我很久，直到我离开电脑准备睡觉时才想到这个问题可能的原因。在 Raft Paper Figure 2 中，AppendEntry Step 5 是：
If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry).
这个 new 很重要，我的错误在于直接用 log 长度更新 commitIndex，正确的做法是用 AppendEntry RPC 中携带的最新 Entry 的下标来更新 commitIndex。这会导致 commitIndex 的更新过于激进，后面的尚未确认与 Leader 同步的 log 也会被 commit。这看起来应该经常出错，为什么在 TestBackup2B 中很少出现呢？因为带有错误 log 的机器在连接到正确集群时，Leader 会不断地自减 nextIndex[] 并重试 AppendEntry RPC，直到在某处 Log 吻合，这时该 Leader 会第一次更新该 Follower 的 commitIndex。commitIndex 首次被更新时 AppendEntry RPC 通常携带新的 Entry，而这个 Entry 和 RPC 接收方的 log 是冲突的，所以 log 都在步骤 3 中被清空了，于是步骤 5 中 index of last new entry 也就是 log 的长度。那什么时候才会触发这个错误呢？答案是 commitIndex 首次被更新时接收到的是心跳（不带 Entry 的 AppendEntry RPC），它不会清空后面的错误的 log，而且还会更新 commitIndex。这就要求心跳刚好在 nextIndex[] 减少到正确值的时候发送，所以出现的概率很低。
要定位这个 bug 还是很困难的，因为这个问题出现的概率真的很低（跑50次出1次问题左右），每跑一次都需要等很久，而且每次 commit 都打印一条信息导致输出很长。推荐一篇文章：Debugging by Pretty Printing，是 6.824 的一名助教写的，帮助我们更好地用日志调试分布式系统。
Committing entries from previous terms
我在 Leader 上的 CommitIndex 更新采用的方法是：找 matchIndex[] 中第 n/2+1 大的数。这时要注意：这条 log 还需要属于当前 term，否则无法宣布 commit。也就是不能 commit 之前 term 的日志。原因在 Raft paper 的 5.4.2 节和 Figure 8 中有详细说明。