莫那·鲁道

惯于闲看花飞花落, 心念天际云卷云舒.

Coder, 欢迎留言 😆.


GitHub

Raft 安全性和一致性 Safety and consistency

背景

为了增加一致性算法的正确性,即日志复制的正确性,Raft 又增加了一些安全机制,也就是打补丁。

我们一起来看看。

选举的限制

首先说结论,Raft 保证所有之前的任期号中已经提交的日志条目在选举的时候,都会出现在新的领导人中。不需要额外传送这些日志给领导人 —— 这意味了保证了数据的单向流动,即只从领导人传给跟随者, 并且领导人从不会覆盖自身本地日志已经存在的日志条目。

如何实现?

Raft 使用投票的方式,来阻止一个候选人赢得选举 —— 除非这个候选人包含了所有已经提交的日志条目。

也就是说,如果想成为领导人,该节点必须包含所有已经提交的日志条目。

候选人为了赢得选举,必须联系集群中的大部分节点,那么,这些节点依据什么规则投票给 候选者 呢?

答:当候选者发送 RPC 给投票者时,RPC 中包含了候选人的日志信息,然后投票人会拒绝掉那些日志没有自己的投票请求。

什么是新? Raft 通过比较两个节点最后一条日志条目的索引值任期号来定义谁的日志比较新。

  1. 首先比较任期号,谁都任期号大,谁就新。
  2. 如果任期号相同,那谁的日志长,谁就新。

通过这个规则来选举出日志最新的节点作为 leader。

提交之前任期内的日志条目

首先,领导人如何提交自己当前任期内的日志条目?

答:当自己发送出去的日志 RPC 被大多数 follower 存储到了服务器上,那么就可以提交。

第二个问题:领导人如何提交之前任期内的日子呢

例如,如果这个 leader 在发送 RPC 之后、本地提交之前,崩溃了,怎么办?

在之前的介绍里,如果 leader 崩溃了,后面的新 leader 会继续尝试复制这条记录。

Raft 论文中关于这个规则的介绍:

但是,这将带来一个问题:一个领导人不能断定“一个之前任期里的日志条目被保存到大多数服务器上的时候” 就一定提交了。

下图将展示这种情况:

图 2

按照之前既有的规则:

  1. 在 (a) 中,S1 是领导者,部分的复制了索引位置 2 的日志条目。
  2. 在 (b) 中,S1 崩溃了,然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引 2 处。
  3. 然后到 (c),S5 又崩溃了;S1 重新启动,选举成功,开始复制日志。在这时,来自任期 2 的那条日志已经被复制到了集群中的大多数机器上,但是还没有被提交。
  4. 这时会发生 2 种情况: 4.1. 如果 S1 在 (d) 中又崩溃了,S5 可以重新被选举成功(通过来自 S2,S3 和 S4 的选票),然后覆盖了他们在索引 2 处的日志

    4.2. 反之,如果在崩溃之前,S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上,就如 (e) 中那样,那么在后面任期里面这些新的日志条目就会被提交(因为S5 就不可能选举成功)

注意:这两种情况在目前的规则下,都是会发生的!!!

但是,d1 的状态是错误的!!!

为什么?因为 d1 覆盖了 (c) 的日志!!!要知道,当 (c)将日志复制到了大多数机器上,虽然 leader 没提交,但 follower 是有可能提交的。但是 d1 却将日志覆盖了,这将会导致 S2 和 S3 的状态机和日志不一致!!!

为什么会发生这个问题?

我们看看之前的选举规则,有没有漏洞。

  1. 首先比较任期号,谁的任期号大,谁就新。
  2. 如果任期号相同,那谁的日志长,谁就新。

最后,需要回顾一下 leader 选举的目标:Raft 使用投票的方式,来阻止一个候选人赢得选举 —— 除非这个候选人包含了所有已经提交的日志条目。 也就是说,如果想成为领导人,该节点必须包含所有已经提交的日志条目

在 c 中,S5 满足这两个条件吗?答案是满足的,因为他的任期号(任期 2)确实比 follower(任期 1) 新。

但是,他达到 leader 的选举目标了吗?

显然,在 c 中,S5 不包含所有已经提交的日志条目,所以没达到。

为什么?因为 c 中,S1 提交了他的上一个任期的日志。导致任期号的生成和任期日志的提交不是原子的。

不是原子的会有什么影响?

这将会导致: 新 leader 如果提交“之前的任期日志”崩溃了,后面的 leader 的任期将大于刚刚提交的任期,这将让他成为 leader ,并覆盖日志。

如果是原子的:新 leader 不可能不包含上一个任期的日志。因为要想成为 leader,必须满足任期 + 下标的条件。

我们假设一下,如果 c 中,S1 不提交上个任期的日志,会怎么样?他不会将日志 2 发送到 follower 上,而是应该优先将日志 4 提交,顺便提交之前的日志 2,当成功提交日志 4,即使崩溃,S5 也无法成功获取选举(任期号过小)。

所以,Raft 又加了一条限制:leader 只能在自己当前任期的日志满足多数规则时,才能提交。历史时期的日志默认提交,类似上图的 d2 阶段,即,提交 日志4 时,一起提交 日志2(日志匹配特性的作用) ,可防止这种情况发生。

但如果没有日志可以提交怎么办?

答:提交一条空白日志,利用日志匹配特性,提交上个任期的日志。

所以,提交之前任期内的日志条目是可行的,但必须是新的 leader 提交一条日志(可以是空白的)间接提交。

但,如果直接提交之前的日志,将会导致非原子操作,之前的任期将可能会被后面的 leader 覆盖日志,导致状态机和日志不一致。

Summary

这一段可以说,全是补丁,说白了,Raft 就是一个个补丁打起来的。

关于选举的限制: Raft 的限制如下: 首先比较任期号,谁都任期号大,谁就新。 如果任期号相同,那谁的日志长,谁就新。

但是仅仅有这 2 个规则是不够的,如果有节点贸然提交了上个任期的日志却崩溃了,后面的节点将会覆盖日志。

所有,Raft 加了一条规定(补丁):leader 只能在自己当前任期的日志满足多数规则时,才能提交。

也就是说, leader 只能提交自己任期的日志。不能直接提交别人的日志,就算提交,也是间接提交。

关于 “提交之前任期内的日志条目” 这一块内容,欢迎一起探讨。

参考

英文 paper pdf 地址

Raft paper 中文翻译 —— 寻找一种易于理解的一致性算法(扩展版)

Raft 作者讲解视频

Raft 作者讲解视频对应的 PPT

一个简单的讲解 Raft 协议的动画