概述

在Raft大论文中3.6.2中,有一个细节“不允许提交之前任期的日志”,之前看了几次都理解的不够准确,把这部分内容展开阐述一下。

问题

还是先从论文的图例开始解释,如下图:

论文截图

需要特别说明的是,图例中演示的是“如果允许提交之前任期的日志,将导致什么问题”,这是大前提,这个前提条件后面会反复强调。

有了这个前提,下面展开图中的步骤讨论:

  • (a) :S1 是leader,将黄色的日志2同步到了S2,然后S1崩溃。
  • (b) :S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举,将蓝色日志3存储到本地,然后崩溃了。
  • (c):S1重新启动,选举成功。注意在这时,如果允许“提交之前任期的日志”,将首先开始同步过往任期的日志,即将S1上的本地黄色的日志2同步到了S3。这时黄色的节点2已经同步到了集群多数节点,然后S1写了一条新日志4,然后S1又崩溃了。
  • 接下来,就可能出现两种不同的情况:
    • (d1):S5重新当选,如果允许“提交之前任期的日志”,就开始同步往期日志,将本地的蓝色日志3同步到所有的节点。结果已经被同步到半数以上节点的黄色日志2被覆盖了。这说明,如果允许“提交之前任期的日志”,会可能出现即便已经同步到半数以上节点的日志被覆盖,这是不允许的。
    • (d2):反之,如果在崩溃之前,S1不去同步往期的日志,而是首先同步自己任期内的日志4到所有节点,就不会导致黄色日志2被覆盖。因为leader同步日志的流程中,会通过不断的向后重试的方式,将日志同步到其他所有follower,只要日志4被复制成功,在它之前的日志2就会被复制成功。(d2)是想说明:不能直接提交过往任期的日志,即便已经被多数通过,但是可以先同步一条自己任内的日志,如果这条日志通过,就能带着前面的日志一起通过,这是(c)和(d2)两个图的区别。图(c)中,S1先去提交过往任期的日志2,图(d2)中,S1先去提交自己任内的日志4。

再次强调,这里图示想演示的是“如果允许提交之前任期的日志,将导致什么问题”

我们可以看到的是,如果允许这么做,那么:

  • (c)中,S1恢复之后,又再次提交在任期2中的黄色日志2。但是,从后面可以看到,即便这个之前任期中的黄色日志2,提交到大部分节点,如果允许“提交之前任期的日志”,仍然存在被覆盖的可能性,因为:
  • (d1)中,S5恢复之后,也会提交在自己本地上保存的之前任期3的蓝色日志,这会导致覆盖了前面已经到半数以上节点的黄色日志2。

所以,“如果允许提交之前任期的日志”,即如同(c)和(d1)演示的那样:重新当选之后,马上提交自己本地保存的、之前任期的日志,就会可能导致即便已经同步到半数以上节点的日志,被覆盖的情况

而“已同步到半数以上节点的日志”,一定在新当选leader上(否则这个节点不可能成为新leader)且达成了一致可提交,即不允许被覆盖。

这就是矛盾的地方,即允许“提交之前任期的日志”,最终导致了违反协议规则的情况。

那么,如何确保新当选的leader节点,其本地的未提交日志被正确提交呢?图(d2)展示了正常的情况:即当选之后,不要首先提交本地已有的黄色日志2,而是首先提交一条新日志4,如果这条新日志被提交成功,那么按照Raft日志的匹配规则(log matching property):日志4如果能提交,它前面的日志也提交了。

可是,新的问题又出现了,如果在(d2)中,S1重新当选之后,客户端写入没有这条新的日志4,那么前面的日志2是不是永远无法提交了?为了解决这个问题,raft要求每个leader新当选之后,马上写入一条只有任期号和索引、而没有内容的所谓“no-op”日志,以这条日志来驱动在它之前的日志达成一致。

这就是论文中这部分内容想要表达的。这部分内容之所以比较难理解,是因为经常忽略了这个图示展示的是错误的情况,允许“提交之前任期的日志”可能导致的问题。

其他疑问

(c)和(d2) 有什么区别?

看起来,(c)和(d2)一样,S1当选后都提交了日志1、2、4,那么两者的区别在哪里?

虽然两个场景中,提交的日志都是一样的,但是日志达成一致的顺序并不一致:

  • (c):S1成为leader之后,先提交过往任期、本地的日志2,再提交日志4。这就是“提交之前任期日志”的情况。
  • (d2):S1成为leader之后,先提交本次任期的日志4,如果日志4能提交成功,那么它前面的日志2就能提交成功了。

关于(d2)的这个场景,有可能又存在着下一个疑问:

如何理解(d2)中,“本任期的日志4提交成功,那么它前面的日志2也能提交成功了”?

这是由raft日志的Log Matching Property决定的:

  • If two entries in different logs have the same index and term, then they store the same command. If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.
  • If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.

第一条性质,说明的是在不同节点上的已提交的日志,如果任期号、索引一样,那么它们的内容肯定一样。这是由leader节点的安全性和leader上的日志只能添加不能覆盖来保证的,这样leader就永远不会在同一个任期,创建两个相同索引的日志。

第二条性质,说明的是在不同节点上的日志中,如果其中有同样的一条日志(即相同任期和索引)已经达成了一致,那么在这不同节点上在这条日志之前的所有日志都是一样的。

第二条性质是由leader节点向follower节点上根据AppendEntries消息同步日志上保证的。leader在AppendEntries消息中会携带新的新添加entries之前日志的term和index,follower会判断在log中是否存在拥有此term和index的消息,如果没有就会拒绝。

  • leader为每一个follower维护一个nextIndex,表示待发送的下一个日志的index。初始化为日志长度。
  • leader在follower拒绝AppendEntries之后会对nextIndex减一,然后继续重试AppendEntries直到两者一致。

于是,回到我们开始的问题,(d2)场景中,在添加本任期日志4的时候,会发现有一些节点上并不存在过往任期的日志2,这时候就会相应地计算不同节点的nextIndex索引,来驱动同步日志2到这些节点上。

总而言之,根据日志的性质,只要本任期的日志4能达成一致,上一条日志2就能达成一致。