奇风 Java 工程师知识体系

Raft 算法

2023/2/13

Raft 实现了和 multi Paxos 相同的功能，它将一致性分解为多个子问题：Leader 选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）等

# 角色

Raft 将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
  • Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
  • Candidate：Leader选举过程中的临时角色。

Raft 要求系统在任意时刻最多只有一个 Leader，正常工作期间只有 Leader 和 Followers。

# leader 选举

如下图所示，分别用三种图代表跟随者、候选人和领导者。

初始状态 初始状态下，集群中所有节点都是跟随者的状态。 如下图所示，有三个节点(Node) a、b、c，任期（Term）都为 0。

Raft 算法实现了随机超时时间的特性，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如 A 节点等待超时的时间间隔 150 ms，B 节点 200 ms，C 节点 300 ms。那么 a 先超时，最先因为没有等到领导者的心跳信息，发生超时。如下图所示，三个节点的超时计时器开始运行。

up-501031a7051bf405999493e07f1b284f.webp

# 发起投票

当 A 节点的超时时间到了后，A 节点成为候选者，并增加自己的任期编号，Term 值从 0 更新为 1，并给自己投了一票。

  • Node A：Term = 1, Vote Count = 1。
  • Node B：Term = 0。
  • Node C：Term = 0。

up-c13af5ea7014c4d3a55f926c8b3ebef0.webp

# 成为领导者的简化过程

up-582304792322d1ae79efa9782ca28f5b.webp

  • 第一步：节点 A 成为候选者后，向其他节点发送请求投票 RPC 信息，请它们选举自己为领导者。
  • 第二步：节点 B 和 节点 C 接收到节点 A 发送的请求投票信息后，在编号为 1 的这届任期内，还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号。
  • 第三步：节点 A 收到 3 次投票，得到了大多数节点的投票，从候选者成为本届任期内的新的领导者。
  • 第四步：节点 A 作为领导者，固定的时间间隔给 节点 B 和节点 C 发送心跳信息，告诉节点 B 和 C，我是领导者，组织其他跟随者发起新的选举。
  • 第五步：节点 B 和节点 C 发送响应信息给节点 A，告诉节点 A 我是正常的。

# 领导者的任期

英文单词是 term，领导者是有任期的。

  • 自动增加：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任期号，如上图所示，节点 A 任期为 0，推举自己为候选人时，任期编号增加为 1。
  • 更新为较大值：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值。比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号，且编号为 1，节点 B 收到消息后，会将自己的任期编号更新为 1。
  • 恢复为跟随者：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。这种场景出现在分区错误恢复后，任期为 3 的领导者受到任期编号为 4 的心跳消息，那么前者将立即恢复成跟随者状态。
  • 拒绝消息：如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点 A 会拒绝这个消息。
  • 一个任期内，领导者一直都会领导者，直到自身出现问题（如宕机），或者网络问题（延迟），其他节点发起一轮新的选举。
  • 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，投完了就没了。

假设一个集群由 N 个节点组成，那么大多数就是至少 N/2+1。例如： 3 个节点的集群，大多数就是 2。

# 防止多个节点同时发起投票

为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间。这个时间内，节点不能成为候选者，只能等到超时。比如上述例子，节点 A 先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。

up-f74d19cd8abf89e246e901938ffccaa7.webp

# 触发新的一轮选举

如果领导者节点出现故障，则会触发新的一轮选举。如下图所示，领导者节点 B 发生故障，节点 A 和 节点 B 就会重新选举 Leader。

up-8abd1b53818ea03d5afdf6dc362548e1.webp

  • 第一步 ：节点 A 发生故障，节点 B 和节点 C 没有收到领导者节点 A 的心跳信息，等待超时。
  • 第二步：节点 C 先发生超时，节点 C 成为候选人。
  • 第三步：节点 C 向节点 A 和 节点 B 发起请求投票信息。
  • 第四步：节点 C 响应投票，将票投给了 C，而节点 A 因为发生故障了，无法响应 C 的投票请求。
  • 第五步：节点 C 收到两票（大多数票数），成为领导者。
  • 第六步：节点 C 向节点 A 和 B 发送心跳信息，节点 B 响应心跳信息，节点 A 不响应心跳信息。

# Raft 算法的几个关键机制

Raft 算法通过以下几个关键机制，保证了一个任期只有一位领导，极大减少了选举失败的情况。

  1. 任期
  2. 领导者心跳信息
  3. 随机选举超时时间
  4. 先来先服务的投票原则
  5. 大多数选票原则

# 日志复制

过程如下：

image.png

直接去理解日志复制，是很容易的，客户端的一条指令到达，领导者会为这条指令创建一条日志条目，并且并行发送到其他跟随者。当日志被安全复制（所谓安全复制后面会有），领导会将日志应用到状态机（比如如果是mysql的insert，那么就是执行insert操作），然后响应客户端。

image.png

如上图，每条日志都会有对应的任期号，和指令。 每个日志都会有对应的索引。

# raft 日志匹配特性

  1. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
  2. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

第一点：一个任期只有一个领导人，并且领导人在一个任期中对于同一索引日志，只会创建一条日志，是不会改变的，是确定的。这就保证第一点成立。 第二点：要想全部相同，就要保证跟随者得到的日志是领导者发送的顺序附加上去的。领导者在发送新的日志时，会附加这条日志之前日志的索引和任期号。如果跟随者发现数据匹配，才会附加上去，否则拒绝。就是一个个状态保证了日志的匹配特性。 一般情况下follower的日志都会和leader保持一致，Leader崩溃可能会导致日志不一致，如下：

image.png

如上图，对于 a-f，最终都会和 leader 同步，也就是说，d会丢弃日志。f的对应日志也会被丢弃和覆盖。

# 那么如何去做覆盖跟随者日志

Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。

Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。

Leader会从后往前试，每次Append失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

# 安全性

我们明白了如何选举和日志复制，但是没有考虑安全性问题。比如一个宕机很久的跟随着会被选为领导者，进行日志覆盖操作会有丢失问题。 Raft中节点在投票的时候，会判断被投票的候选者对应的日志是否至少和自己一样新。如果不是，则不会给该候选者投票。 日志比较的方法：

  1. 最后一条日志的任期号。如果大说明新。如果小，说明不新。如果相等。跳到2
  2. 判断索引长度

# 日志压缩

日志数据如果不进行压缩处理掉的话，会一直增长下去。为此Raft使用快照数据来进行日志压缩，比如针对键值a的几次操作日志a=1、删除a、a=3最后可以被压缩成为最后的结果数据即a=3。

image.png

在上图中：

  • 未压缩日志前，日志数据保存到了<3,5>（任期3，索引5）的位置，而在<2,3>的位置之前的数据都已经进行提交了，所以可以针对这部分数据进行压缩。
  • 压缩日志之后，快照文件中存放了几个值：压缩时最后一条日志的二元数据是<2,3>，而针对a的几次操作最后的值为a=3，b的值为2。

# 集群成员变化

考虑一种场景，原来 Raft 集群中存在三个节点，现在需要增加2 个节点。那么，在这种情况下， Raft 算法如何能保证同一个任期内，只有一个领导者呢？ 在 Raft 论文 (opens new window) 中，作者使用配置（configuration）来表示集群由哪些节点组合，即集群所有节点的信息集合。在稳定状态下，所有节点的配置都是一致的。 由于集群存在多个节点，因此，一次性原子地更新所有节点的配置是不可能的，集群在更新配置的过程中，可能会出现新旧配置的两个大多数：

image.png

例如，上图中，集群的节点数量 由 3 个增加至 5 个。由于各个节点可能在不同的时间进行新旧配置的转换，因此，可能存在一段时间，集群中在同一个任期内，存在两个领导者。一个领导者由使用旧配置的大多数选举产生，即图中节点 1， 2；一个领导者由使用新配置的大多数选举产生，即图中节点 3，4，5。 这显然是跟 Raft 算法的规定相悖的。

为解决成员变更时领导者选举的问题，Raft 作者提出了几种方法。例如，可以先将集群原来所有节点关闭，更新其配置后，再启动新的集群。由于所有节点的配置都是固定的，Raft 可以保证同一任期只有一个领导者。不过此方法会导致每次成员变更时都需要关闭集群，导致集群无法对外提供服务。

Raft 作者还提出一种“联合共识”（joint consensus）的方法，不过此方法实现起来比较复杂，本文也不再赘述，有兴趣可以参考 Raft 论文 (opens new window) 有关联合共识的描述。

本节重点讲述单节点变更（single-server change）的方法。

单节点变更，即每次只允许增加或者删除一个节点，如果集群需要增加或者删除多个节点，可以通过执行多步的单节点操作实现。例如，如果需要将集群节点数量从 3 调整到 5 ，可以执行 2 次单节点变更操作，先将节点数量从 3 调整到 4，再从 4 调整到 5。

为什么单节点变更方法可以解决成员变更可能带来的同一个任期存在多个领导者的问题呢？

这是由于，不管集群节点数量是偶数，还是奇数，不管是增加节点，还是删除节点，集群中新旧配置的大多数都会存在重叠的情况，如下图所示：

image.png

上图蓝色区域表示采用旧配置的大多数，红色区域表示采用新配置的大多数。对于单节点变更来说，新旧配置的大多数都会存在节点重叠的情况。在 Raft 中，节点在同一个任期只有一张选票，因此，重叠的节点在同一个任期内不会投出两张选票，这样就不会出现同一任期存在两个领导者的现象。

# 参考

  1. https://www.cnblogs.com/crazymakercircle/p/14343154.html#autoid-h3-1-1-0 (opens new window)
  2. https://zhuanlan.zhihu.com/p/32052223 (opens new window)
  3. https://www.pdai.tech/md/algorithm/alg-domain-distribute-x-raft.html (opens new window)
  4. https://leehao.me/Raft-%E5%85%B1%E8%AF%86%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-%E4%B8%89%EF%BC%9A%E6%88%90%E5%91%98%E5%8F%98%E6%9B%B4/ (opens new window)
  5. https://raft.github.io/ (opens new window)
  6. https://zhuanlan.zhihu.com/p/27908888 (opens new window)

#

#

#

#

Zab 算法