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 的解决方案。

阅读原文

简介:一名系统研究者的攀登之路,欢迎关注微信公众号:多颗糖
(0)
打赏 喜欢就点个赞支持下吧 喜欢就点个赞支持下吧

声明:本文来自“多颗糖”,分享链接:https://www.zyxiao.com/p/293607    侵权投诉

网站客服
网站客服
内容投稿 侵权处理
分享本页
返回顶部