图解 Raft 共识算法：领导者选举与日志复制

每个 Kubernetes 集群都把状态存放在 etcd 中，而 etcd 通过 Raft 就这些状态达成一致。Consul、CockroachDB、TiKV、RabbitMQ 的仲裁队列也是如此；自从 Kafka 4.0 移除 ZooKeeper 之后，Kafka 自己的控制器同样如此。如果你在运行其中任何一个系统，Raft 能解释那些否则看起来很随意的行为：为什么三节点集群在两个节点故障时会停止接受写入，为什么领导者切换期间写入会暂停一秒，以及为什么第四个节点会让集群更贵却不会更安全。

本文用一张五节点集群的日志复制图来讲解 Raft：任期、领导者选举、AppendEntries、提交规则、故障、集群规模、读取和成员变更。

模型：复制日志

Raft 构建的是一个复制状态机。每台服务器都保存一份命令日志。如果所有服务器都按相同顺序应用相同的命令，它们最终会处于相同的状态。Raft 的任务是让各份日志保持一致，即使服务器崩溃、消息丢失或延迟也不例外。

每台服务器都处于三种状态之一：跟随者（follower）、候选人（candidate）或领导者（leader）。时间被划分为任期（term），编号依次为 1、2、3 等；每个任期以一次选举开始，最多只有一个领导者。服务器一旦看到比自己更高的任期，就会更新自己的任期并成为跟随者，因此过时的领导者一听到新领导者的消息就会退位。

Raft 只需要两种 RPC，另外还有一种用于快照：

这一设计出自 Diego Ongaro 和 John Ousterhout 发表于 USENIX ATC 2014 的论文 In Search of an Understandable Consensus Algorithm。

领导者选举

跟随者期望定期收到领导者的心跳。如果在选举超时时间内一个都没有收到，它就认为领导者已经不在了：

1. 它把任期加一，成为候选人，并给自己投票。
2. 它向其他所有服务器发送 RequestVote，附上自己最后一个日志条目的索引和任期。
3. 每台服务器每个任期最多投一票，而且只投给日志至少和自己一样新的候选人：最后任期更高的胜出，任期相同时日志更长的胜出。
4. 获得多数票的候选人成为领导者，并开始发送心跳。

如果两个候选人瓜分了选票，就没有人胜出，这个任期在没有领导者的情况下结束。Raft 通过随机化超时时间让这种情况很少发生；论文建议使用 150 到 300 ms 这样的值，这样通常会有一台服务器最先超时，并在其他服务器开始之前胜出。

生产系统会根据自己的网络来选择超时时间。etcd 默认使用 100 ms 的心跳和 1,000 ms 的选举超时，其文档指出选举超时应至少是成员之间往返时间的十倍。正因为这些数字，Kubernetes 控制平面在失去 etcd 领导者后，可能需要一秒或更久才能重新接受写入。

日志复制

当选之后，领导者处理每一次写入：

1. 客户端向领导者发送一条命令，例如 SET x=5。
2. 领导者把它作为带有当前任期的新条目追加到自己的日志中，比如任期 3 中的索引 7。
3. 领导者向每个跟随者发送 AppendEntries，其中包含新条目，以及紧挨在它前面的那个条目的索引和任期（索引 6，任期 3）。
4. 只有当自己的日志在索引 6 处有一个任期为 3 的条目时，跟随者才会接受。这项一致性检查保证：如果两份日志在某个位置一致，那么它们在此之前的所有内容也都一致。
5. 当包括领导者在内的多数服务器存下该条目后，领导者把它标记为已提交，应用到自己的状态机，并回复客户端。
6. 跟随者从下一次 AppendEntries 中得知新的提交索引，也应用该条目。

如果跟随者因为日志出现分歧而拒绝某个条目，领导者会一次后退一个索引（有优化时会更快），直到日志匹配，然后用自己的条目覆盖跟随者上冲突的条目。被覆盖的只会是未提交的条目，这是安全的，因为从来没有人被告知它们已经成功。

提交规则，以及其中微妙的部分

“多数存下即提交”有一个例外，这也是论文中最著名的细节。新领导者不能通过统计副本数来提交之前任期遗留下来的条目。它是间接提交这些条目的：在它们之上提交一个属于自己任期的条目。如果没有这条规则，一个已经存放在多数服务器上的条目仍可能被之后的领导者覆盖。实践中，新领导者会在任期开始时追加一个空的 no-op 条目，以便快速提交之前的所有内容。

选举限制补全了安全性论证：因为候选人需要多数票，而每个已提交的条目都存在于多数服务器上，所以任何可能胜出的候选人都已经拥有全部已提交的条目。

集群能承受什么

由 n 台服务器组成的集群需要多数派才能选出领导者并提交写入，因此它能容忍少于一半的服务器故障：

四台服务器和三台一样只能容忍一个故障，但现在每次写入要等三个确认，而不是两个。这就是集群规模取奇数的原因。如果你希望在一台节点计划维护期间还能再承受一个故障，五台是通常的选择。

延迟也遵循同样的算术。每次写入都要等领导者联系上最快的多数派，并等这些服务器把条目持久化到磁盘。在横跨三个区域的集群中，每次写入至少要付出一次到最近的另一个区域的往返开销。慢磁盘的危害不亚于慢网络，这就是为什么 etcd 文档花在 fsync 延迟上的篇幅和花在超时上的一样多。

实践中的故障

• 领导者崩溃。 跟随者超时，其中一个赢得选举，写入恢复。正在进行中的请求可能已提交，也可能没有，所以客户端必须重试，而它们重试的命令应当是幂等的。
• 网络分区。 拥有多数派的一侧选出领导者并继续运行。处于少数派一侧的旧领导者无法提交任何内容；分区恢复后，它会看到更高的任期并退位。
• 慢跟随者。 提交不会等它。如果它落后太多，领导者会发送快照，而不是重放整份日志。
• 捣乱的服务器。 与领导者断开的服务器会不断超时并提高自己的任期，回来时可能引发不必要的选举。来自 Ongaro 博士论文的 pre-vote 让候选人在增加任期之前先确认自己能否胜出。

读取并不免费

领导者不能盲目地用自己的状态来回答读取：分区的另一侧可能已经选出了新领导者，而旧领导者会返回过时的数据。线性一致读要么需要在回答前进行一轮心跳来确认领导地位（Raft 的 ReadIndex），要么需要基于时间的领导者租约，而租约依赖于有界的时钟漂移。跟随者也可以提供读取，但只能在检查过领导者的提交索引之后，或者接受过时的结果。etcd 把这一点讲得很明确：etcdctl get 默认是线性一致的，而 --consistency=s 请求的是更快但可能过时的可串行化读取。

变更成员

增加或移除服务器会改变“多数”的含义，粗心地切换配置可能同时产生两个多数派。Raft 通过联合共识（joint consensus）或一次只变更一台服务器来处理这个问题。许多实现还会像 etcd 那样，把新服务器作为无投票权的 learner 加入，让新节点在计入多数派之前先追上日志。

日志复制图

这张图的读法如下：

• 客户端发送一条命令给任期 3 的领导者 S1。领导者把它写在索引 7。
• 每张表格都是一台服务器的日志：索引、任期和命令。不同表格中相同的行是同一个条目。
• AppendEntries 连线从领导者指向四个跟随者。S2 和 S3 确认了索引 7。
• S4 落后，停在索引 6；S5 无法访问，停在索引 5。两者都不会阻塞提交。
• 便签展示了提交规则：五台服务器中有三台存下了条目 7，所以它已提交，客户端得到回复。

绘制有教学意义的共识图

• 展示日志，而不只是服务器。 Raft 的保证都是关于日志的陈述。只有五个方框和几条箭头的图会把有意思的东西全藏起来。
• 在每个条目旁边写上任期。 任期解释了选举、冲突和提交规则。
• 画一个不健康的集群。 一个落后或被分区的跟随者，比完美的集群更能说明多数派为什么重要。
• 每个场景用一张图：一次选举、正常复制以及故障转移后的冲突修复，都值得各自单独成图。

想了解复制在数据库架构中的更广泛位置，请参阅数据库复制图。Kubernetes 架构图展示了 etcd 在控制平面中的位置，Kafka 架构图介绍了 KRaft 控制器。CockroachDB 这样的系统为每个数据范围运行一个 Raft 组，这把共识和数据库分片图中的思路联系了起来。

在 Archboard 中构建

1. 使用 Google 或 GitHub 登录，并新建一张图。
2. 为集群添加一个基础节点包中的 框架，并用当前任期作为标签。
3. 在其中添加五个基础节点包中的 表格 节点，每台服务器一个，列为索引、任期和命令。把领导者放在中间。
4. 在框架外为客户端添加一个基础节点包中的 方框，并用命令把它连到领导者。
5. 从领导者向每个跟随者画 AppendEntries 连线，再从存下条目的跟随者画回虚线确认连线。用警示色的虚线连线标出无法访问的跟随者。
6. 添加一个基础节点包中的 Markdown 块写明提交规则，并在领导者旁边添加一个注明提交索引的 便签。

这个示例共用 8 个图表节点，在 Free 套餐的限制之内。

常见问题

为什么 Raft 集群的节点数是奇数？ 集群需要多数派才能工作。在三个节点之外再加第四个，会把多数派从两个提高到三个，却不能多容忍任何故障；所以偶数规模只会增加延迟和成本，而不会增加容错能力。

领导者选举期间，写入会怎样？ 在新领导者选出之前，写入会等待或失败，通常在一到两个选举超时之内就会选出。客户端应该用幂等请求重试，因为超时的写入可能已经提交。

Raft 和 Paxos 有什么区别？ 它们以相似的保证解决同一个问题。Raft 的设计目标是更易于理解和实现：它使用强领导者，把选举与复制分开，并规定了成员变更的方式。

在 Raft 中，跟随者可以提供读取吗？ 可以，前提是它们先确认领导者的提交索引，或者应用能接受可能过时的数据。不经检查就读取跟随者的本地状态，可能会返回旧值。

Raft 能防御恶意节点吗？ 不能。Raft 能容忍崩溃、重启以及丢失或延迟的消息，但它假定服务器都遵守协议。拜占庭容错需要不同的算法和更多副本。

免费开始 — 1 个席位，无需信用卡。