Raft 算法

Raft 动图演示：http://www.kailing.pub/raft/index.html

更多链接：

image-20241023172554484

1. Raft 背景

Paxos 算法虽然理论上能够解决分布式的共识问题，但是其过于复杂，难以理解。实现 Paxos 算法的开源软件很少，比较有代表性的是 Google 的 Chubby。

正是由于 Paxos 算法的复杂性和实现难度，使得其在实际工程中的应用受到了限制。然而，分布式系统的发展迫切需要一种既高效又易于实现的分布式一致性算法。在这种背景下，Raft 算法应运而生，成为一种更具实用性和可读性的替代方案。

Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 在 2013 年发表的《In Search of an Understandable Consensus Algorithm》中提出。Raft 算法是一类基于日志复制的分布式共识算法，由于 Raft 算法易于理解和实现，在提出后，迅速获得了广泛关注，并成为了分布式系统中实际应用最广泛的一致性算法之一。目前，已经有十多种语言的 Raft 算法实现框架，比较有代表性的有 etcd、Consul，CockroachDB 等。

所以说掌握了 Raft 算法，就能比较轻松地处理绝大部分的一致性场景和需求，本文的大纲如下：

image-20241019022013692

2. Raft 算法优化思路

Raft 算法为了达到易于理解的目的，主要做了两件事：

  • 问题分解：将分布式共识问题拆分成主节点选举、日志复制、安全点，以及成员变更 4 个独立子问题逐一进行解决
  • 状态简化：通过减少算法中需要考虑的状态数，使得算法更加清晰和易于理解

3. 领导者选举（Leader Election）

3.1 Raft 角色

在一个 Raft 集群中，每个节点有以下三种状态，一般也称这三种状态的节点为 Raft 集群的三种角色

  • 领导者（Leader）
    1. 处理客户端请求
    2. 管理和同步日志
    3. 定期向 Follower 发送心跳（Heartbeat）信号，以表明自己仍然存活，并防止 Follower 发起选举
  • 跟随者（Follower）
    1. 被动地响应 Leader 的日志同步请求
    2. 响应 Candidate 发起的邀票请求
    3. 把客户端打到 Follower 的请求转发给 Leader
  • 候选者（Candidate）
    1. 在集群刚启动或 Leader 宕机时，Follower 节点可以转换为 Candidate 并发起选举
    2. 当 Follower 长时间未接收到 Leader 的心跳信号时，会认为 Leader 可能已经失效，从而将自己状态转换为 Candidate 并发起选举。Candidate 向其他节点请求选票，若获得超过半数节点的投票，它就会成为新的 Leader
    3. 如果选举胜出，Candidate 转变为 Leader；否则，如果有其他节点当选为 Leader，Candidate 会返回到 Follower 状态

节点状态转换如下图所示

image-20241019102437957

从上图可以看出，在集群启动时，所有的节点都处于 Follower 状态，如果在一段时间内，没有收到来自 Leader 的心跳信息，则 Follower 将切换成 Candidate，然后发起投票，如果该 Candidate 收到了多数（超过半数）的 Follower 的投票（包含该 Candidate 自己投给自己的一票），则该 Candidate 将切换成 Leader。在选举过程中，如果该 Candidate 发现有其他节点有比自己更新（即日志条目的任期号更高），它会自动放弃选举，并重新切回 Follower。

一句话概括：系统中最多只有一个 Leader，如果在某一段时间内没有 Leader，Follower 会通过选举投票的方式选出 Leader。Leader 会不停的给 Follower 发送心跳信息，保证自己的存活状态。如果 Leader 挂掉，Follower 会切换成 Candidate 发起投票，重新选出 Leader。

3.2 任期

任期是一个整数，用于标识 raft 集群的一个时间段。这个跟国家行政相似，比如上一个五年是领导人人 xx 任期的五年，这个五年是领导人 yy 的任期，可以简单的理解为“朝代”，用递增的整数表示。那对应到 raft 集群中，就可以简单的理解为，任期是某个节点处于 leader 的一个时间段。但这里需要明确一点，可能某些情况下，因为选票的分流，在选举期间内没有成功选出 Leader，则会进入下一个任期。
任期示意图如下：

image-20241019104758716

任期包含两个阶段：

  1. 选举阶段
  2. 已选举出 Leader 的阶段

同上面所说，任期也可能只包含选举阶段，没有 Leader，比如图中的任期 3，这种情况下，会立即进入到下一个任期，开始新的选举。

任期具有如下特点：

  • 每个节点都会保存当前的任期（即一个标识时间段的整数），并随着集群状态的变化进行更新
  • Follower 等待 Leader 的心跳超时后，会推举自己为 Candidate 发起投票，此时会将当前任期编号加 1。比如当前该 Follower 保存的任期为 1，在推举自己为候选人邀票时，会将任期编号增加到 2
  • 当一个节点发现自己保存的任期编号比另一个节点的任期编号小，它会主动更新自己的任期编号到最新的较大的任期编号，比如节点 A 当前的任期编号是 1，当收到来自节点 B 的请求投票 的 RPC 消息时，因为消息中包含了节点 B 的任期编号，且编号为 2，那么节点 A 将把自己的任期编号更新为 2
  • 如果一个节点接收到一个比自己任期编号小的 RPC 请求，该节点会立即拒绝这个 RPC 请求（无论是投票请求还是日志追加请求）。这是因为这个请求的任期编号已经过时，代表着发出请求的节点拥有的是旧任期，不再被视为合法的领导者或候选者
  • 如果一个 Leader 或者是 Candidate 发现自己的任期编号比其他节点小，该节点会立即退回到 Follower，假设由于网络分区错误，集群中出现了两个 Leader，LeaderA 任期编号为 4，LeaderB 任期编号为 5，当网络分区错误恢复后，LeaderA 收到了来自 LeaderB 的心跳信息，LeaderA 将回退为 Follower，接收 LeaderB 成为 Leader

3.3 随机超时

Raft 算法中的随机超时有以下两种情况：

  • Follower 等待 Leader 心跳信息的超时间隔是随机的：这里的随机化的超时机制可以防止多个 Follower 同时转换为 Candidate，减少选举冲突
  • Candidate 等待选举结果的超时间隔是随机的：当一个节点转换为 Candidate 并发起选举后，会等待其他节点的投票结果，这个等待时间是随机的。如果在这个等待的时间段内，没有获得大多数选票，将再次随机设置一个等待时间，发起新一轮投票。这里的随机化的超时机制降低了多个 Candidate 同时发起选举的可能性

总的来说，在 Raft 算法中，随机超时机制是一个关键设计，保证在大多数情况下只有一个节点发起选举，避免多 Candidate 选举带来的性能问题

3.4 通信方式

在 Raft 算法中，节点之间通过远程调用（RPC）进行通信，主要涉及以下三种类型的 RPC：

  • 投票 RPC：由 Candidate 节点在选举过程中向 Follower 发出
  • 附加日志条目 RPC：Leader 节点在日志复制过程中将日志条目发送给其他 Follower 节点，同时也起到维持心跳的作用，确保 Leader 的存活状态
  • 快照 RPC：当 Follower 的日志落后 Leader 太多时，Leader 会发送 Snapshot RPC 请求，通过快照的方式帮助 Follower 快速同步日志

3.5 选举流程

image-20241019105555033

如上图所示：Follower 在收到 Leader 心跳信息超时后，会推选自己为 Candidate，将自身的任期+1，然后发起选举，如果在设置的时间内收到了多数选票，将晋升为新的 Leader，如果没有获得足够多的选票，收到 Leader 的心跳包，则 Candidate 恢复成 Follower 角色。

3.5.1 选举详细流程下面以三个节点的集群来演示下选举的详细流程
  1. 初始状态

初始时，每个节点的角色都是 Follower，任期 Term 为 0（假设任期编号从 0 开始），每个节点都设置了一个随机超时时间（节点 A：100ms，节点 B：120ms，节点 C：160ms），如下图：

image-20241019115401253

  1. 发起投票

由于节点 A 的随机超时时间是设置的最小的，为 100ms，所以在 A 在 100ms 后倒计时结束被唤醒，成为 Candidate，并为自己发起投票，此时将自己的任期编号加 1，变为 1。先投自己一票，然后向其他的 Follower 发起投票 RPC 请求。

image-20241019115443774

  1. 响应投票

Follower 节点 B 和 C 收到 Candidate 节点 A 的投票请求后，会做如下处理：

  • 如果自身已经在任期编号为 1 的投票请求中投过票了，则会忽略该投票请求
  • 否则，将自己的选票投给 Candidate，也就是节点 A，并将自身保存的任期编号设置为 1，然后重置随机超时时间

假设 B 和 C 都没有在任期编号为 1 的投票请求中投过票，此时都将选票投给 A，并设置自身的任期编号为 1，然后重置随机超时时间。

image-20241019115524037

  1. 结束投票

image-20241019144905549

3.5.2 多 Candidate 选举

从上面的选举过程可知，每个节点都会设置一个随机超时时间，这样可以降低了多个节点在同一时刻被唤醒成为 Candidate 的概率。但是也只是能降低概率，并且由于系统可能存在网络延迟，所以仍然无法完全避免多个 Follower 同时成为 Candidate 发起投票，假设这里有两个 Follower（A 和 B）同时被唤醒，转换为 Candidate 发起投票：

假设 A 和 B 设置的随机超时时间都是 120ms，在 A 和 B 节点被同时唤醒之后，会各自为自己投上一票，然后开始向其他节点发送投票请求，假设节点 C 先收到 A 的投票请求，之后再收到 B 的投票请求，那样 C 将会把选票投给 A，最终节点 A 获得两票（包含自己一票）成为 Leader，而节点 B 只会获得一张选票（自己的一票），则会回退成 Follower.

image-20241019145739011

image-20241019145725893

3.5.3 平票问题

一般在集群中，节点的个数都会选择奇数个，很重要的一点就是防止两个 Candidate 同时发起选票获得相同票数，导致系统内无法选出 Leader 的情况。但是由于系统可能出现故障，导致某个节点故障之后，依然可能会存在这个问题。假设集群中的节点是出现了偶数个，结果又会怎样呢？

假设集群中有 A，B，C，D 四个节点，其中 A，B 两个节点设置的随机超时时间都是 120ms。现在假设 A，B 被同时唤醒了，向其他节点发送投票请求。节点 A 和 B 在同一任期内竞选领导者时，由于每个节点在同一个任期内只能投票一次，A 和 B 都已经投了自己的票，因此不会再给对方投票。然后节点 C 把票投给 A，节点 D 把票投给 B，这样节点 A 和 B 都获得了两张选票，出现了平票的情况，这种情况下是不会有 Leader 被选出来的，所有节点会恢复成 Follower 状态，重新设置随机超时时间，准备下一轮的选举，虽然会有下一次轮的选举，直到选出新的 Leader，但是在这个过程中，集群都是处于不可用状态，所以选举的轮次越多，集群不可用状态越久，因此要尽量避免平票问题。

节点 A 和节点 B 回退为 Follower 之后，重新设置随机超时时间，节点 A 50ms，节点 B 100ms，等待超时时间开启新一轮的选举：

image-20241019145808794

3.5.4 脑裂问题

前面所说的情况是在集群完全正常的情况下，一个集群中只会存在一个 Leader。假设在一个集群内发发生了网络分区，形成了两个分区，选举情况将会怎样进行呢？

这里以 5 个节点的集群为例，集群节点 A,B,C,D,E，节点 A 为集群 Leader。假设发生了网络分区，[A,B,C] 为一个分区，节点 [D,E] 为一个分区，由于 A 本身就是原集群的 Leader，所以 [A,B,C] 分区内还是按照以前的集群模式 A 为 Leader，向 B，C 节点发送心跳。而 [D,E] 由于发生了网络分区，收不到 A 节点的心跳信息了，假设 D 节点设置的随机超时时间较短，那么到时间后，会成为 Candidate，发起投票，成为 [D,E] 这个分区的 Leader，由于经过了一轮选举，那么 [D,E] 这个分区的任期将会比 [A,B,C] 分区的任期大 1。这个时候在整个集群 [A,B,C,D,E] 中就有了两个 Leader A 和 D，这就是“脑裂问题”。

脑裂问题如何解决？

其实在网络恢复后，虽然有了两个 Leader，Leader 都会向其他的节点发送心跳信息，这里 A 和 C 会互相收到对方发送的心跳信号，但是在 A 节点收到 C 节点发送的心跳之后，会发现携带的任期比自身保存的任期要大，所以 A 节点会退成 Follower，集群会再次恢复成只有一个 Leader 的状态。

image-20241019145832505

4. 日志复制（Log Replication）

Raft 算法中第二个很重要的字问题就是日志复制，日志复制（Log Replication）是保证整个集群中的所有节点（follower）一致地存储相同状态的核心机制。它的主要目标是通过将客户端提交的指令（通常是状态变化操作）复制到每个节点的日志中，确保所有节点都达成一致的状态，即一致性。

4.1 日志

在 raft 日志其实是一种数据格式，主要用于存储客户端的一些列操作指令，日志由三部分组成，分别是：

  • 索引值（Log index）
  • 任期编号（Term）
  • 指令（Command）

image-20241019161047597

  • 索引值：日志条目对应的索引值，用来标识第几条日志，是一个连续单调递增的整数
  • 任期编号：创建这条日志条目的 Leader 的任期编号
  • 指令：客户端发起请求需要执行的指令，例如指令 X <- 2 表示将 X 变量赋值为 2

一条日志也叫日志项，从上图可以看出，在一个 Leader 的任期内，可以有多个日志项，比如任期 1 内有 3 个日志项，任期 3 内有 4 个日志项。

日志还对应有两个状态：

  • committed（已提交）：针对的是日志，对应于某个日志项被成功复制到集群的大多数节点之后，这个日志项就处于 committed 状态，比如索引值 1-7 所对应的日志项均处于 committed 状态，因为他们都被复制到了大多数节点
  • applied （已应用）：针对的是状态机即节点，节点要将日志真正应用到状态机，即真正改变了节点上对应变量的值

4.2 日志复制过程

集群中只有 Leader 会跟客户端交互，接收客户端的指令，而这些指令除了要在客户端执行以外，还需要通过日志复制的方式讲这些指令复制到各个 Follower 节点，以保证集群的一致性。

image-20241019161611127

日志复制的过程可以总结如下：

  • Leader 接收到客户端请求，请求中的指令创建一个新的日志项，然后追加（append）到当前本地日志中（此时 Leader 中该日志项的状态为 uncommitted）
  • Leader 通过日志复制 RPC 请求将该日志项复制到其他 Follower 节点（此时在各个 Follower 中该日志项的状态为 uncommitted）
  • 当 Leader 确认将日志项成功复制到大多数节点后，Leader 会将该日志项标记为 committed，之后 Leader 会将该日志项应用到自己的状态机，即真正执行指令，修改对应的值
  • Leader 将执行结果返回给客户端
  • Leader 通过心跳或新的日志复制请求将提交了该日志项的状态同步给 Follower，如果 Follower 发现 Leader 已提交了该日志项，而自己还没将该日志项应用 apply 至状态机，则会将该日志项应用至自己的状态机中
  • 如果 Follower 节点出现宕机或者由于网络丢包，Leader 会通过不断重试发送日志复制请求来确保日志条目最终复制到 Follower 上

可以看出，在日志复制过程中，只要有半数以上的处于正常工作的状态，整个系统就可用，假如在复制日志的过程中，出现了节点宕机、进程中断等问题，可能导致日志不一致，这种情况会怎么处理呢？

4.3 日志一致性

从前面的日志复制过程可以看出，在日志复制过程中，只要有半数以上的处于正常工作的状态，整个系统就可用，假如在复制日志的过程中，出现了节点宕机、进程中断等问题，可能导致日志不一致，这种情况会怎么处理，怎么来保证各个节点日志的一致性呢？

首先看一下 Raft 日志的特点，Raft 日志具体如下两个特性：

  • 如果不同日志中的两个日志项有相同的「任期编号」和「索引值」，那么这两个日志项一定有相同的指令
  • 如果不同日志中的两个日志项有相同的「任期编号」和「索引值」，那么这两个日志项之前的所有日志项也全部都相同

通过这两个特征其实可以看出，只要同步到位的日志都是一致的，在 Raft 算法中，其实是以领导者日志为准来实现日志的一致性的，主要包括两个步骤：

  1. Leader 通过日志复制 RPC 请求的一致性检查，找到 Follower 节点上与自己具有相同日志项的最大索引值（在该索引值之前的日志项，Leader 和 Follower 是一致的，之后不一致）
  2. Leader 强制 Follower 更新不一致日志条目，Leader 强制 Follower 将该索引值之后的所有日志项删除，并将 Leader 该索引值之后的所有日志项同步给 Follower
4.3.1 一致性检查

Leader 为了找到 Follower 节点上与自己具有相同日志项的最大索引值，每次日志复制请求除了发送该日志项之外，还要发送一些额外信息，这里引入两个新的概念：

  1. prevLogIndex：Leader 当前需要复制的日志项的前一个日志项的索引值
  2. prevLogTerm：Leader 当前需要复制的日志项的前一个日志项的任期编号

如下图，假设 Leader 当前需要将索引值为7的日志项发送复制到 Follower，则 prevLogIndex 为 6，prevLogTerm 为 3

下面以一个具体的例子来看：

image-20241019162239119

当前 Leader 的最大日志项索引为 10，假设当前 Leader 需要将 10 号日志项复制给 Follower，步骤如下：

  1. Leader 将索引值为 10 的日志项通过日志复制 RPC 请求发送给 Follower，同时还会发送该日志项的 prevLogIndex（9）和 prevLogTerm（3），Follower 收到消息后，判断自己没有索引值为 9 的日志，因此拒绝更新日志并向 Leader 失败信息
  2. Leader 收到 Follower 的失败响应后，将日志项的索引值减 1，接着发送索引值为 9 的日志项并且携带 prevLogIndex（8）和 prevLogTerm（3）给 Follower，Followe 发现自己索引值为 8 的日志项中任期为 4，指令为 N <- 5，和 Leader 发过来的日志项不一样 ，再次拒绝更新，向 Leader 响应失败
  3. 直至需要复制索引值为 7 的日志项时，Follower 发现同步过来的 prevLogIndex 为 6，prevLogTerm 为 3，与自己在索引值为 6 的的日志条目相同（任期也是 3），则接收该日志复制 RPC 请求
  4. Leader 收到跟 Follower 的成功响应后，Leader 通过日志复制 RPC 消息，强制 Follower 复制并更新覆盖索引值为 7 及之后的内容。保证 Follower 与 Leader 的日志状态一致

5. 安全性

前面分析了 Raft 算法是如何进行 Leader 选举以及日志复制的，但是这套机制还不能够完全保证每个节点都会严格按照相同的顺序 apply 日志，这就可能造成各个节点的状态机不一致。

假设有如下场景：

  1. Leader 将某些日志项复制到了大多数节点上，在 commit 后发生了宕机
  2. 某个 Follower 尚未被复制这些日志项，但是在 Leader 挂了之后，进行的选举中，该 Follower 成为了 Leader
  3. 这个新的 Leader 又同步并提交了一些新的日志，这些日志覆盖掉了其它节点上的上一任提交的日志
  4. 各个节点在进行 apply 时可能应用了不同的日志序列，导致出现不一致

所以要想保证各个节点状态机一致性，光有 Leader 选举和日志复制策略还是不够的，还要有一些额外的措施，这就是本小节要讨论的安全性限制策略。

5.1 对选举的限制

回顾上述场景，为什么会出现日志被错误地覆盖，导致不一致。根本问题其实就是在第二部，一个落后的 Follower（还没被复制上一任 Leader 的最新日志）就当选了新的 Leader。那么他接下来的操作肯定会以自己的日志为准，导致集群中其他节点的日志被覆盖掉。所以这个 Candidate 来竞选 Leader 其实是不合格的，Candidate 必须有足够的资格才能当选 leader，所以在 Candidate 发起选举投票的时候，可以加一个条件限制：

  • ⚠️每个 Candidate 发起投票 RPC 请求时必须在请求体中包含自己本地日志最新的任期编号（term）和索引值（index）当 Follower 收到 Candidate 的投票请求时，如果发现该 Candidate 的日志还没有自己的新，则拒绝投票给该 Candidate。

🌟在加了这个条件之后，再结合上本身 Candidate 就必须赢得集群大多数节点的投票才会成为 Leader，同时一条日志只有复制到了大多数节点才能被 commit，所以 Leader 就一定拥有所有 committed 日志。也就是说：Follower 不可能比 leader 多出一些 committed 日志。

比较日志新旧的策略也很简单：(term, index) 比较，先比较 term， term 更大的日志更新，term 相同的话，index 大的日志更新。

5.2 对提交的限制

单独的对选举加一定限制还不能保证日志的正确性，不正确的提交（commit）同样会带来问题。回顾一下 commit 的作用：

当 leader 得知某条日志项被成功复制到集群的大多数节点后，就可以进行 commit，表明该日志项可以被 apply 生效到状态机，committed（已提交） 日志项一定最终会被状态机 apply。

但是不正确的 commit 也可能带来日志覆盖的问题，考虑如下场景：

image-20241020172124036

图中的方框内的数字表示该日志项的任期 term，对应坐上面一栏的数字表示该日志项的索引值 index，一条日志项用（term，index）表示，从左到右随着时间集群状变更如下：

  • 阶段 a：S1 是 leader，收到请求后将日志项(2, 2) 只复制给了 S2，尚未复制给 S3，S4，S5
  • 阶段 b：S1 宕机，S5 选举获取了 S3、S4、S5 三票，当选任期（term）为 3 的 leader，收到客户端请求后保存了 日志项（3，2），尚未复制给任何节点
  • 阶段 c：S5 宕机，S1 恢复，S1 重新当选 term 为 4 的 leader，继续将日志项 (2, 2) 复制给了 S3，已经满足大多数节点（S1，S2，S3），于是 S1 将该日志项 commit
  • 阶段 d：S1 又宕机，S5 恢复，S5 选举获得了 S2、S3、S4 三票，重新当选 ，将 日志项(3, 2) 复制给了所有节点并 commit。注意，此时发生了日志覆盖错误，已经 committed 的 日志项(2, 2) 被 (3, 2) 覆盖了

为了避免这个错误，需要在日志的提交阶段也加一个限制：

⚠️ Leader 只允许 commit 包含当前任期 (term) 的日志。

假设有了这个限制，再来模拟一下上述场景，在加了这个限制后，其实上述阶段的阶段 c 就出错了，阶段 c 虽然 S1 恢复当选了 term4 的 Leader，但是其并不能直接将日志项（2，2）commit，因为 S1 当前的日志为（4，3），必须等到（4，3）成功复制后才能 commit。

一旦有了这个限制，在阶段 c 就只存两种情况了：

  1. 日志项（2，2）始终没有被 commit，这样 S5 在阶段 d 将其覆盖就是安全的
  2. 日志项（2，2）连同（4，3）一起被成功 commit，这样的话，在阶段 d，S5 就无法成功当选 Leader（对选举的限制，当 Follower 收到 Candidate 的投票请求时，如果发现该 Candidate 的日志还没有自己的新，则拒绝投票给该 Candidate），就不存在上述问题了

6. 节点变更问题

集群中的节点数量并不是恒定不变的，比如随着业务的发展，集群需要扩容或者是缩容，那么就需要适当的增加或者是减少机器节点，又或者是某些几点出现了故障，需要变更机器等等，都需要变更集群的节点数量。Raft 算法如何处理集群成员节点变更的问题呢？

6.1 配置

在介绍节点变更过程之间，需要先明确一个概念：配置（configuration）

在 Raft 算法中，使用用配置来表示集群的节点集合，比如某个集群由 A、B、C 三个节点构成，那么集群的配置就是 [A, B, C]，在稳定的状态下，所有节点的配置都相同。从这里就可以知道，每个节点是通过这个配置信息来获取集群状态的，比如在选举，日志同步过程中，集群中有哪几个 Follower，Leader 需要向哪几个节点发送 RPC 通信都需要通过配置来获取。

6.2 节点变更可能带来的问题

集群中节点的变更很有可能给集群的一致性带来影响，主要是会影响集群的多数派。我们知道在 Raft 中很多场合都需要多数派的支持，比如在投票中，只有当一个节点收到多数派投票（超过半数）才会成为 Leader，在日志同步中，只有当 Leader 确认将日志项成功复制到多数派（超过半数）节点后，会将该日志项标记为 committed，类似的场景还有很多。

而集群节点的变更最主要的就是会影响到多数派，比如在一个三个节点的集群中原本只要 2 个节点就可以达到多数派，假设现在往集群新增两个节点，则需要三个节点才能达到多数派。

在 Raft 集群中，同样是由 Leader 节点负责同步集群的配置信息，当集群中出现节点变更，几乎不能保证所有节点同时进行配置的变更，由于网络先后等因素导致一部分节点配置已变更，另一部分没有变更在所难免，所以就会导致集群中部分节点使用的新的配置信息 C_new，而有的节点使用老的配置信息 C_old。

假设有如下场景中，原来集群有三个节点 [server1,server2,server3]，现在向集群新增了两个节点 server4 和 server5.

image-20241020173239227

当处于画框的时间点时，假如此时出发了选举，server1 和 server2 用的是旧的配置文件 C_old，因此他们会从节点 [server1,server2] 中选出 Leader；而节点 server3，server4 和 server5 已经是新的配置文件 C_new 了，他们会从节点 [server3,server4,server5] 中选出新的 Leader。此时集群就可能会有两个 Leader，出现脑裂问题。

6.3 节点变更策略

前面分析了在集群变更的时候很可能导致集群的一致性出现问题，那又没有什么策略可以解决这个问题呢？主要有以下这几种解决方案。

6.3.1 串行更新

这种方法就是先将集群原来所有节点关闭，更新其配置后，再启动新的集群，显然这种方法很安全，可以保证集群始终只有一个 Leader，但是这种方法会导致每次成员变更时都需要关闭集群，导致集群无法对外提供服务，对于高可用的业务场景显然不适用。

6.3.2 单节点变更

每一次集群的变动只能新增或者删除一个节点，假设集群需要变更多个节点，那么需要分多个步骤来完成，每次只变更一个节点。比如原集群有 3 个节点，先需要扩容到 5 个节点，那么需要分两步，第一步扩充到 4 个节点，再由 4 个节点增加到 5 个节点，所以单节点变更法也叫单步成员变更法。

详细步骤如下：

  1. 客户端向 Leader 提交一个集群成员变更请求，请求的内容新增或者删除节点，以及服务节点的地址信息
  2. Leader 在收到请求之后，向本地日志中追加一条配置信息志，其中包含了新的集群配置信息 C_new，之后，这个新的配置信息会随着 RPC 请求（AppendEntries）同步给所有的 Follower 节点。注意：配置信息日志被添加到日志中是立即生效（不需要 commit 之后再生效）
  3. 当配置信息日志被复制到新的配置信息 C_new 所标识的所有节点的多数派节点后，就 commit 该日志

提交配置日志的作用：

  1. 日志提交之后，才可以响应客户端，完成集群节点变更
  2. 标志着本轮节点变更已结束，可以开始下一轮的节点变更
  3. 如果集群中有删除节点，那么提交日志之后，被删除的节点可以关机了
6.3.2.1 单步成员变更法为什么可以解决集群节点变更带来的脑裂问题呢？

这里可以枚举出奇偶节点情况下，新增或者删除节点的情况

image-20241020173822354

从上图可以看出，不管原集群节点数是奇数还是偶数，也不管是在原集群上新增一个节点还是删除一个节点，在集群的节点数变更之后，原集群的多数派和新集群的多数派一定存在交集，那么再同一个任期内，原集群 C_old 和新集群 C_new 中交集的那一个节点只会进行一次投票，要么投票给 C_old，要么投票给 C_new，这样就避免可同一任期出现在两个 Leader 的现象。

需要注意的是：单节点变更法虽然简单，很好理解，但是也有其缺陷，这种方式在串行化的方式下可以保证一个集群只能有一个 Leader，但是并发执行单节点变更，可能会出现一次单节点变更还没完成，新一次单节点变更已经执行，导致集群出现脑裂问题，这里不过多阐述，感兴趣的话可以去看 Raft 论文 。

6.3.3 两阶段切换集群成员配置

虽然 Raft 论文中认为单步变更是更简单的办法，但节点变更有一定的问题，但是现在主流的实现都使用了 Joint Consensus（联合共识）算法来完成集群变更，也就是小标题所说的两阶段切换集群成员配置。

具体流程如下：

  1. 阶段一
    1. 客户端将新配置 C_new 发送给 Leader，Leader 取旧配置 C_old 和新配置 C_new 的并集（称为联合配置（表示为 C_old,new））并立即 apply 即生效
    2. Leader 将配置 C_old,new 包装成日志通过 AppendEntries 请求复制到 Follower 节点
    3. Follower 收到 C_old,new 后立即生效，立刻应用该配置作为当前节点的配置，当 C_old,new 的大多数节点（即 C_old 的大多数节点和 C_new 的大多数节点）都切换后，leader 将 commit 该日志
  2. 阶段二
    1. 紧接着 Leader 将新配置 C_new 包装成日志通过 AppendEntries 请求复制到 Follower 节点
    2. Follower 收到 C_new 后立即生效，如果此时发现自己不在 C_new 列表，则主动退出集群
    3. Leader 确认 C_new 的大多数节点都切换成功后，给客户端发送执行成功的响应

几个概念详细解释一下：

  • C_old,new：比如 C_old 为 [A, B, C]，C_new 为 [B, C, D]，那么 C_old,new 就为他们的并集 [A, B, C, D]
  • C_old,new 的大多数节点：是指 C_old 中的大多数和 C_new 中的大多数，如下表所示，第一行因为 C，D 节点还没有被复制到日志，导致 C_new 的多数派不能达成，所以该日志不能被 commit

image-20241020174404877

image-20241020174420174

上图展示了用两阶段提交方法集群节点变更过程中的几个过渡期：

  • 虚线：表示已经创建但尚未 commit 的成员配置日志
  • 实线：表示 committed 的成员配置日志

在每一个时期，每一个任期下都不可能出现两个 Leader.

原因如下

阶段一：C_old,new 日志尚未 commit

  • 在这个阶段，集群中节点可能处于旧配置 C_old 下，也有可能处于联合配置 C_old,new 下，但无论这两种情况的哪一种，只要原 leader 发生宕机，新 leader 都必须得到旧配置 C_old 下大多数节点的投票，所以不会出现两个 Leader
  • 再次强调一下：C_old 节点发起选举需要 C_old 的大多数，C_old,new 发起选举需要 C_old 和 C_new 两者的大多数

阶段二： C_old,new 已经 commit，C_new 下发之前

  • 在这个阶段，C_old,new 已经被 commit，表示联合配置 C_old,new 已经被应用到了集群的大多数节点上（C_old 的大多数节点和 C-new 的大多数节点），因此当 leader 宕机时，新选出的 leader 一定是已经拥有 C_old,new 的节点，否则票数通不过，所以不可能出现两个 leader

阶段三： C_new 已经下发，但尚未 commit

  • 在这个阶段，集群中可能有三种节点，集群中节点可能处于旧配置 C_old 下，也有可能处于联合配置 C_old,new 下，还有可能处于新配置 C_new 下，但由于已经经历了阶段 2，因此 C_old 节点不可能再成为 leader。而无论是 C_old,new 还是 C_new 节点发起选举，都需要经过大多数 C_new 节点的同意，因此也不可能出现两个 leader

阶段四：C_new 已经 commit

  • 在这个阶段，C_new 已经被 commit，因此只有 C_new 节点可以得到大多数选票成为 leader，所以也不会出现两个 Leader，至此，集群已经安全地完成了这轮变更，可以继续开启下一轮变更了

7. 小结

Raft 算法将共识问题分解成了多个相对独立的子问题，从而简化了共识的实现。其主要流程包括领导者选举以及日志复制，集群先选举出 leader，然后 leader 负责复制、提交日志。当然为了在任何异常情况下系统不出错，还需要满足一定的安全性，以及需要对 Leader Election，Log Replication 两个子问题加一些限制条件。最后集群都是动态变化的，所以 Raft 算法也应用了单节点变更以及联合共识机制来保证集群节点安全的变更。

许可协议

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

分享文章
✍️ Yikun Wu 已发表了 69 篇文章 · 总计 293k 字，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

🌀 本站总访问量 次