理解 Raft 算法：一致性和 Leader 选举机制详解

4568字约15分钟

2024-10-17

在一个分布式系统中, 通常拥有许多节点. 节点之间如果需要达成共识, 确保节点之间的一致性成为了所有分布式系统都关注的问题.

Raft 是非常经典的一个分布式算法, 它可以保证一个分布式系统中所有节点都保持连续的一致性状态, 是一种用于管理复制日志的一致性算法. Raft 算法旨在通过提供容错和确保选出单个领导者来协调操作所有节点. 本文中我们将深入研究 Raft 算法的核心概念, 重点在于节点的一致性和领导节点的选举.

什么是 Raft 算法?

Raft 算法最早是被斯坦福大学的 Diego Ongaro 和 John Ousterhout 提出的. 是为了能更好地理解之前的分布式一致性算法, 例如: Paxos 的同时提供更好的容错率以及领导者的选举能力.

快速连接

Raft 论文

那么什么叫做一致性算法呢? 我们为什么需要它呢?

一致性算法主要是为了解决分布式系统中的容错问题. 如果所有的信息都存储在集群中的一个节点上, 那么当这个节点宕机时, 集群将无法响应客户端的请求并且可能发生信息的丢失. 那么为了解决这个问题, 我们希望集群中的所有节点都保存相同的信息, 这样就算其中一个节点宕机, 其他的节点也能履行相同的义务, 响应请求. 那么如何使得集群中的所有节点保持一致呢? 通常的做法时利用 复制日志. 每个节点都拥有一组日志, 日志里面包含了相同顺序的执行命令, 所以最终执行之后的效果也是一样的. 一致性算法的目标就是达到复制日志的一致性.

在这个复制状态机架构图中我们可以看到:

客户端发送了一个请求.
一致性算法将请求中对于数据的 3 个操作生成了日志: $x \leftarrow 3$ , $y \leftarrow 1$ , $y \leftarrow 9$ .
状态机根据日志进行了数据的修改.
将修改的结果返回客户端.

核心概念

注

为了不产生歧义并与论文对齐, 此处使用英文单词, 但是附上中文解释. 在后文中这些关键概念也使用英文.

Node: 节点. 在 Raft 中, 一个网络集群是由多个节点或者服务器组成的.
Leader: 领导者. 在一个 Raft 集群中, 其中一个节点会被选为 Leader. Leader 会负责管理所有集群中节点的日志复制.
Follower: 跟随者. 集群中所有除了 Leader 以外的节点都是 Follower. 它们会响应 Leader 的请求并向 Leader 转发客户端的请求.
Candidate: 候选者. 当 Leader 宕机的时候, 集群需要选举出一个新的 Leader. 节点会将身份转变为 Candidate, 并开始竞选.
Term: 任期. Raft 算法以 Term 为周期. 每个 Term 以一个选举开始并以下一个新 Leader 被选出或重新选举的时候为结束.
Log Replication: 日志复制. Raft 算法会保证集群中所有的日志都被复制并且以相同的顺序保存.
RequestVote RPC: 选举期间由 Candidate 发起.
Append-Entries RPC: 由 Leader 发起, 用来复制日志条目并提供一种形式的 Heartbeat.
SnapShoot RPC: 传输节点快照时使用.

Raft 流程

Raft 算法主要分为三个问题:

Leader 选举. 当现有的 Leader 宕机时需要选择新的 Leader
日志复制. Leader 节点接受客户端的请求, 写入日志, 并管理其他节点使它们与自己的日志一致.
安全性.
- 选举安全. 最多只有一个 Leader
- 日志仅追加.
- 日志匹配. 如果两个日志包含具有相同索引和任期的条目, 那么从给定索引开始的所有条目的日志都是相同的.
- Leader 完整性. 如果一个日志条目是在一个给定任期中提交的, 那么这个条目会出现在所有更高编号的任期的 Leader 的日志中.
- 状态机安全. 如果一个节点的状态机中应用了一个给定索引的日志条目, 那么其他节点将不会对同一个索引应用不同的日志条目.

Raft 首先会在集群中选取一个 Leader, 然后这个 Leader 节点会全权负责一致性的实现. Leader 会接受客户端的请求, 将相关的数据操作生成日志条目, 通知其余的节点复制这些日志条目, 并在复制完成后告诉其他节点何时将日志条目应用到它们的状态机是安全的.

可以看出, Leader 是 Raft 算法中简化日志复制管理的关键. 数据以一种简单的方式从 Leader 流向其他节点, 只需要简单地复制日志即可达到同步一致的效果.

Leader 选举

Raft 节点拥有三种状态: Follower, Candidate, Leader.

从状态转换图中可以看到, 开始的时候所有节点都是 Follower. 如果一段时间没有收到 Leader 的心跳, 就会转变为 Candidate 参加选举. 如果获得大多数节点的投票, 则成为新的 Leader. 如果发先其他节点成为了新 Leader, 则退化成为 Follower.

选举的流程

在每个任期的开始, 所有节点都是 Follower.
如果一个 Follower 在一个周期内没有收到 Leader 发送的任何信息(选举过期), 它会转变为 Candidate.
Candidate 会请求其他节点投票给它. 如果它收到了半数以上的选票, 它将会成为 Leader.
如果没有任何一个 Node 成功收到超过半数的选票, 一个新的选举会在下一个 Term 展开.

日志复制

从上面的示意图我们可以看出, 每一条日志条目包含两个信息: 状态机需要执行的命令 和 日志条目所属的 Term 任期. 图中所有的日志分为 3 个 Term, 分别标为了绿色, 黄色和蓝色. 每个 Term 都代表着一个新的 Leader. Follower 的日志的编号会小于等于 Leader, 取决于它的同步进度. 图的最下面显示 committed entries, 意味着 1- 7 编号的条目已经被提交至状态机, Leader 会认为 index = 7 的日志是 "安全的".

日志复制的流程

Leader 接受客户端的请求并将其作为一个新的日志条目追加写入其日志中.
Leader 并发地将 AppendEntries RPC 请求发送给所有 Follower, 要求它们来复制该条目.
Follower 在成功复制后会回复 Leader 以确认复制完成.
一旦超过半数的 Follower 确认了该请求, Leader 将该日志条目应用到自己的状态机中, 并回复客户端消息接收成功.

通常情况下 Leader 和 Follower 的日志会保持一致, 但是 Leader 的崩溃宕机可能会导致日志的不一致, 这些不一致可能会在一系列的 Leader 和 Follower 的崩溃中加剧.

当图中第一行的那个节点成为第 8 个任期的新 Leader 的时候，Follower 日志可能是 (a-f) 其中的任意一种情况. (同样的, 每个方框代表一个日志条目; 方框里的数字是它的项)

一个 Follower 可能缺少条目. 例如实例(a - b)
可能有额外的未提交条目. 例如实例(c-d)
或者以上两者都有. 例如实例(e-f)

例如场景(f)可能会因为这个原因而发生: 如果该节点是 Term 2 的领导者, 在其日志中添加了几个条目, 然后在提交任何条目之前崩溃. 它很快重新启动, 成为 Term 3 的 Leader, 并在其日志中添加了更多条目. 在提交 Term 2 或 Term 3 中的任何条目之前, 该节点再次崩溃, 并在接下来的几个 Term 内都保持关闭状态.

考虑到以上的场景, Raft 的 Leader 会强制 Follower 跟自己进行日志的同步. 这意味着 Follower 中冲突的日志条目会被 Leader 的日志强制覆盖.

那么 Leader 是怎么做到让 Follower 与自己强制同步的呢?
Leader 必须找到自己与 Follower 之间最后一条双方都认同的日志条目, 删掉 Follower 中那个条目之后的所有日志, 然后将自己那个条目之后的日志全部发送给 Follower. 所有这些操作都是对 AppendEntries RPC 执行的一致性检查的响应.
那么 Leader 是如何找到自己和 Follower 之间最后的一条不冲突的日志条目的呢?
Leader 会保存每个 Follower 对应的 nextIndex, 这个 index 表示下一个 Leader 将要发送给这个 Follower 的日志. 当一个新的 Leader 刚刚当选, 它就会把所有 Follower 的 nextIndex 的值初始化为自己的最后一条日志的下一个索引值(在图 5 中该值为 11). 如果一个 Follower 的日志与 Leader 的日志是不一致的, 那么就会在下一次的 AppendEntries RPC 中的 AppendEntires consistency check 一致性检查中失败. 被拒绝后, Leader 会通过试错法, 即递减 nextIndex 的值并重试 AppendEntries RPC. 最终 nextIndex 会达到 Leader 和 Follower 日志匹配的最新点. 此时, AppendEntries 会成功, 然后删除 Follower 日志中所有冲突的部分然后将匹配最新点后的 Leader 的日志追加写入(如果有的话). 一旦 AppendEntries 成功, Follower 和 Leader 的日志就是一致的, 并且它将在剩余的任期内保持这种处理方式.

(a): S1 当选为 Leader, 同步 Term 2 的日志(黄色)到 S2.
(b): S1 离线, 在 Term 3 中 S5 成为 Term 3 的新 Leader, 并追加写入一条日志(蓝色).
(c): S5 离线. S1 恢复并重新成为 Leader, 继续日志同步. 此时多数 Follower 已经同步了 S1 的 Term 2, 但是没有提交.
(d): S1 再一次离线, S5 再一次成为 Leader(收到 S2, S3 和 S4 的投票), 并强制其他节点同步自己 Term 3 的日志(蓝色).
(e): 如果 S1 在离线前大多数的节点复制了当前任期的条目, 如(e), 这个红色的条目被提交(S5 无法赢得选举). 此时红色条目前的所有日志条目也都被提交.

上述的情况说明, 在根据大多数 Follower 同步原则提交的情况下, 尽管旧的日志放在大多数的节点上, 但是也会被覆盖掉.

所以提交日志条目前, 应该等到有一个 Leader 当前任期的条目提交之后, 所有的之前条目再一起提交.

Follower 和 Candidate 的宕机

如果一个 Follower 或 Candidate 崩溃, 则之后发送给它的 RequestVote 和 AppendEntries RPC 将会失败.
Raft 通过无限重试来处理这些失败. 如果崩溃的服务器重新启动, RPC 将成功完成. 如果服务器在完成 RPC 之后但在响应之前崩溃, 那么它将在重新启动后再次接收相同的 RPC.
如果一个 Follower 接收到一个 AppendEntries 请求, 该请求包含已经在其日志中存在的日志条目, 则它将忽略新请求中的那些条目. 即 Raft 中的 RPC 是幂等的.

时间和可用性

选择 Leader 必须要满足以下公式:

broadcastTime \ll electionTimeout \ll MTBF

broadcastTime: 节点向集群中每个节点并行发送 RPC 并接受响应所需的平均时间. 0.5 ms - 20 ms.
electionTimeout: 选举超时. 10 ms - 500 ms.
MTBF: 单个节点故障间隔的平均时间. 可能能长达几个月.

总结

Raft 中的节点共识

Raft 达成共识的方法对于确保分布式系统的完整性和一致性至关重要.共识是通过一系列步骤达成的：

Leader 选举:

如果 Leader 发生故障, 对等节点将在设定的阈值内监视来自 Leader 的同步请求. 如果超过此阈值, 对等节点将认为 Leader 不可用, 并触发 Leader 选举. 它会向其他节点请求投票, 并在获得多数后宣布自己为新的 Leader.
每个节点会随机设置其阈值, 以防止同时选举. 这个阈值必须超过同步间隔, 以防止在 Leader 未宕机的情况下触发选举.

日志复制
- 当客户端发起一个操作, 例如: 插入一个键值对, Leader 节点会收到请求.
- Leader 将操作附加到其日志中, 并将此日志条目广播到集群中的所有其他节点.
- 每个集群中的节点都会在自己的日志中追加写入这一条请求.
大多数同意
- Raft 的运作原则是多数同意. 在向其状态机提交操作之前, Leader 会等待大多数节点的确认.
- 如果大多数节点(例如 $\frac{N}{2} + 1$ 个)都在其日志中复制该操作, 即认为其确认该操作, 则 Leader 将该操作提交到其状态机
- 这确保了操作正式成为系统状态的一部分, 并将在所有节点上一致地应用.
此外, Leader 会定期向其他服务器发送更新以保持它们同步. 这确保了即使服务器掉队或崩溃, 它也可以快速赶上键值存储的最新状态.

与对等节点同步

与对等节点同步是 Raft 设计的一个关键方面, 它可以保持一致性并使新节点快速加入. 下面是它的工作原理：

新服务器同步
- 当一个新的服务器加入 Raft 集群, 它需要迅速地与当前的键值对存储保持一致.
- 为了完成这个目标, Leader 会向新服务器发送一系列日志信息, 确保它拥有完整的日志备份.
- 这些日志会包含此前所有的数据操作.
判断同步日志
- Leader 根据每个对等节点最后确认的日志索引确定为同步过程发送哪些日志.
- 如果对端节点已经确认到索引 $k$ 的日志, 则 Leader 将从索引 $k + 1$ 开始发送到最后一个日志(n)进行同步.
- 此过程确保新服务器接收它错过的所有操作, 并使其与键值存储的最新状态保持一致.
处理同步错误
- 如果 Leader 不知道对等节点的最后一个已确认的日志索引, 它将使用试错法.
- Leader 从其日志索引的末尾开始, 并根据对等节点的响应减少索引.
- 如果对等节点在作为同步请求的一部分发送索引之前没有日志, 它将返回一个错误.
这个迭代过程确保新服务器接收到用于同步的正确日志.