Raft 的 Figure 8 讲了什么问题？为什么需要 no-op 日志？

▲ 点击上方"多颗糖"关注公众号

发现之前写的 Raft 文章并没有分析过 Figure 8 的问题，而这张图比较容易让人产生歧义，群里讨论过不止一次。在这里谈谈我的理解。

Figure 8 用来说明为什么 Leader 不能提交之前任期的日志，只能通过提交自己任期的日志，从而间接提交之前任期的日志。

先按错误的情况，也就是 Leader 可以提交之前任期的日志。那么上述的流程：

• (a) S1 是任期 2 的 Leader(仔细看，有个黑框)，日志已经复制到了 S2。

• (b) S1 宕机，S5 获得 S3、S4 和 S5 的选票成为 Leader，然后写了一条日志 index=2 & term=3。

• (c) S5 刚写完就宕机了，S1 重新当选 Leader，currentTerm = 4，此刻还没有新的请求进来，S1 将 index=2 & term = 2 的日志复制到了 S3，多数派达成，S1 提交了这个日志(注意，term=2 不是当前任期的日志，我们在讨论错误的情况)。然后请求进来，刚写了本地 index=3 & term=4 的日志，S1 就故障了。

• (d) 这时候 S5 可以通过来自 S2、S3、S4 和自己的投票，重新成为 Leader(currentTerm>=5)，并将 index=2 && term=3 的日志复制到其他所有节点并提交，此时 index=2 的日志提交了两次！一次 term=2，一次term=3，这是绝对不允许发生的，已经提交的日志不能够被覆盖！

• (e) 这里的情况是，S1 在宕机之前将自己 term=4 的日志复制到了大多数机器上，这样 S5 就不可能选举成功。这是 S1 不发生故障，正确复制的情况。

这里主要通过 (c) 和 (d) 来说明问题所在。其实这张图用 Raft 大论文的图会比较好理解。(d) 和 (e) 分别对应 term=4 有没有复制到多数派的情况。

所以，我们要增加提交的约束，不让 (d) 这种情况发生。这个约束就是，Leader 只能提交自己任期的日志。

我们再来看看，加了约束后会变成什么样？前面 (a) 和 (b) 没有任何改变，我们从 (c) 开始。

• (c) 还是将 index=2 & term=2 复制到大多数，由于 currentTerm = 4，所以不能提交这条日志。如果 S1 将 term = 4 的日志复制到多数派，那么 Leader 就可以提交日志，index=2 & term=2 也会间接一起提交，其实这就是 (e) 的情况，1-2-4 都被提交。

• (d) 的情况我觉得是理解问题的关键。如果 S1 只将 term=4 写入自己的日志，然后宕机了；S5 选举成功成为 Leader，然后将 index=2 & term=3 的日志复制到所有节点，现在 index=2 是没有提交过的，S5 能提交 index=2 & term=3 的日志吗？

答案是不能。因为 S5 在 S1(term=4) 选举出来后 currentTerm 至少是 5，也可能是 6、7、8……我们假设就是 5，但这条日志 term = 3，Leader 不能提交之前任期的日志，所以这条日志是不能提交的。只有等到新的请求进来，超过半数节点复制了 1-3-5 后，term=3 的日志才能跟着 term=5 的一起提交。

虽然加了这个约束不会重复提交了，但如果一直没新的请求进来，index=2 & term=3 岂不是就一直不能提交？那这里不就阻塞了吗？如果这里是 kv 数据库，问题就很明显了。假设 (c) 或 (d) 中 index=2 那条日志里的 Command 是 Set("k", "1")，S5 当选 Leader 后，客户端来查询 Get("k")，Leader 查到日志有记录但又不能回复 1 给客户端(因为按照约束这条日志未提交)，线性一致性要求不能返回陈旧的数据，Leader 迫切地需要知道这条日志到底能不能提交。

所以 raft 论文提到了引入 no-op 日志来解决这个问题。这个在 etcd 中有实现。

引入 no-op 日志

no-op 日志即只有 index 和 term 信息，command 信息为空。也是要写到磁盘存储的。

具体流程是在 Leader 刚选举成功的时候，立即追加一条 no-op 日志，并立即复制到其它节点，no-op 日志一经提交，Leader 前面那些未提交的日志全部间接提交，问题就解决了。像上面的 kv 数据库，有了 no-op 日志之后，Leader 就能快速响应客户端查询了。

本质上，no-op 日志使 Leader 隐式地快速提交之前任期未提交的日志，确认当前 commitIndex，这样系统才会快速对外正常工作。

另外说一句，6.824 的实验不需要实现 no-op 日志。

这个问题之前阿里巴巴团队称之为“幽灵复现”，参见《如何解决分布式系统中的“幽灵复现”？》，里面讨论了 Paxos、Raft 和 Zab 的解决方案。

相关阅读

欢迎关注我的公众号：