| title | Raft 算法详解 | ||
|---|---|---|---|
| description | Raft共识算法原理详解，涵盖Leader选举、日志复制、安全性保证等核心机制及与Paxos的对比分析。 | ||
| category | 分布式 | ||
| tag |
|
本文由 SnailClimb 和 Xieqijun 共同完成。
当今的数据中心和应用程序在高度动态的环境中运行，为了应对高度动态的环境，它们通过额外的服务器进行横向扩展，并且根据需求进行扩展和收缩。同时，服务器和网络故障也很常见。
Raft 算法由 Diego Ongaro 和 John Ousterhout 于 2014 年在 Usenix ATC 会议论文《In Search of an Understandable Consensus Algorithm》中提出。Raft 通过复制日志来保证副本状态机的一致性与安全性；在配套正确的客户端交互与读实现（如 ReadIndex / Lease Read、请求去重）后，可实现线性一致（linearizable）的读写语义，旨在作为 Paxos 的更易理解替代。
相比 Paxos，Raft 通过分解为相对独立的子问题降低复杂度：
- Leader 选举：使用随机化选举超时（工程上常见如 150–300ms 或更大范围，具体取决于网络与故障模型）。
- 日志复制：Leader 通过 AppendEntries RPC 广播日志。
- 安全性：包括选举限制和日志匹配。
Raft 在实际生产中得到了广泛应用，基于 Raft 的实现如 etcd、Consul 等已成为分布式系统的重要组成部分。后续学术界和工业界也对 Raft 进行了多项扩展和优化，包括：
- Pre-Vote（2014）：防止网络分区的节点干扰稳定集群的选举
- Read Index（2014）：在 Leader 任期内通过线性一致性读优化读性能
- Lease Read：基于租约的线性一致性读方案
- Joint Consensus：用于集群成员变更的联合一致机制（通过引入过渡配置，典型过程为旧配置 → 联合配置 → 新配置）
因此，系统必须在正常操作期间处理服务器的上下线。它们必须对变故做出反应并在几秒钟内自动适应；对客户来说的话，明显的中断通常是不可接受的。
幸运的是，分布式共识可以帮助应对这些挑战。
Raft 工作在非拜占庭（Crash Fault Tolerance, CFT）假设下：节点可能宕机、重启、网络延迟或分区，但不会恶意伪造/篡改消息。下面用"多方通过投票选出指挥者"的类比，仅用于帮助理解 Leader 选举与重试机制，不涉及拜占庭容错（BFT）。
假设多位将军需要选出一位指挥官，信使的信息可靠但有可能被暗杀（网络故障），将军们如何达成一致？
解决方案大致可以理解成：先在所有的将军中选出一个大将军，用来做出所有的决定。
举例如下：假如现在一共有 3 个将军 A，B 和 C，每个将军都有一个随机时间的倒计时器，倒计时一结束，这个将军就把自己当成大将军候选人，然后派信使传递选举投票的信息给将军 B 和 C，如果将军 B 和 C 还没有把自己当作候选人（自己的倒计时还没有结束），并且没有把选举票投给其他人，它们就会把票投给将军 A，信使回到将军 A 时，将军 A 知道自己收到了足够的票数，成为大将军。在有了大将军之后，是否需要进攻就由大将军 A 决定，然后再去派信使通知另外两个将军，自己已经成为了大将军。如果一段时间还没收到将军 B 和 C 的回复（信使可能会被暗杀），那就再重派一个信使，直到收到回复。
共识是可容错系统中的一个基本问题：即使面对故障，服务器也可以在共享状态上达成一致。
共识算法允许一组节点像一个整体一样一起工作，即使其中的一些节点出现故障也能够继续工作下去，其正确性主要是源于复制状态机的性质：一组Server的状态机计算相同状态的副本，即使有一部分的Server宕机了它们仍然能够继续运行。
一般通过使用复制日志来实现复制状态机。每个Server存储着一份包括命令序列的日志文件，状态机会按顺序执行这些命令。因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。由于状态机是确定性的，所以处理相同的状态，得到相同的输出。
因此共识算法的工作就是保持复制日志的一致性。服务器上的共识模块从客户端接收命令并将它们添加到日志中。它与其他服务器上的共识模块通信，以确保即使某些服务器发生故障，系统仍能在日志顺序上达成一致；最终每个日志都包含相同顺序的请求。一旦命令被正确地复制，它们就被称为已提交。每个服务器的状态机按照日志顺序处理已提交的命令，并将输出返回给客户端，因此，这些服务器形成了一个单一的、高度可靠的状态机。
适用于实际系统的共识算法通常具有以下特性：
-
安全。确保在非拜占庭条件（也就是上文中提到的简易版拜占庭）下的安全性，包括网络延迟、分区、包丢失、复制和重新排序。
-
高可用。只要大多数服务器都是可操作的，并且可以相互通信，也可以与客户端进行通信，那么这些服务器就可以看作完全功能可用的。因此，一个典型的由五台服务器组成的集群可以容忍任何两台服务器端故障。假设服务器因停止而发生故障；它们稍后可能会从稳定存储上的状态中恢复并重新加入集群。
-
一致性不依赖时序。错误的时钟和极端的消息延迟，在最坏的情况下也只会造成可用性问题，而不会产生一致性问题。
-
在集群中大多数服务器响应，命令就可以完成，不会被少数运行缓慢的服务器来影响整体系统性能。
一个 Raft 集群包括若干服务器，以典型的 5 服务器集群举例。在任意的时间，每个服务器一定会处于以下三个状态中的一个：
Leader：负责发起心跳，响应客户端，创建日志，同步日志。Candidate：Leader 选举过程中的临时角色，由 Follower 转化而来，发起投票参与竞选。Follower：接受 Leader 的心跳和日志同步数据，投票给 Candidate。
在正常的情况下，只有一个服务器是 Leader，剩下的服务器是 Follower。Follower 是被动的，它们不会发送任何请求，只是响应来自 Leader 和 Candidate 的请求。
Raft 算法将时间划分为任意长度的任期（term），任期用连续的数字表示，看作当前 term 号。每一个任期的开始都是一次选举，在选举开始时，一个或多个 Candidate 会尝试成为 Leader。如果一个 Candidate 赢得了选举，它就会在该任期内担任 Leader。如果没有选出 Leader（例如出现分票 split vote），该任期可能没有 Leader；随后在新的选举超时后会进入下一个任期并重新发起选举。只要多数节点可用且网络最终可达，系统通常能够在若干轮选举后选出 Leader。
每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号；如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值。如果一个 Candidate 或者 Leader 发现自己的 term 过期了，他会立即退回成 Follower。如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求。
下面这张图是我手绘的，更容易理解一些，就很贴心：
entry：每一个事件成为 entry，只有 Leader 可以创建 entry。entry 的内容为<term,index,cmd>其中 cmd 是可以应用到状态机的操作。log：由 entry 构成的数组，每一个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机中。
补充两个常用指针：
commitIndex：已提交（committed）的最大日志索引；表示哪些日志已经被集群确认并可以安全地应用到状态机。lastApplied：已被状态机应用（applied）的最大日志索引；通常 lastApplied ≤ commitIndex。
Raft 使用心跳机制来触发 Leader 的选举。
如果一台服务器持续收到来自 Leader 的 AppendEntries（心跳或日志复制）等合法 RPC，它会保持为 Follower 状态并刷新选举计时器。
Leader 会向所有的 Follower 周期性发送心跳来保证自己的 Leader 地位。如果一个 Follower 在一个周期内没有收到心跳信息，就叫做选举超时，然后它就会认为此时没有可用的 Leader，并且开始进行一次选举以选出一个新的 Leader。
为了开始新的选举，Follower 会自增自己的 term 号并且转换状态为 Candidate。然后他会向所有节点发起 RequestVote RPC 请求， Candidate 的状态会持续到以下情况发生：
- 赢得选举
- 其他节点赢得选举
- 一轮选举结束，无人胜出
赢得选举的条件是：一个 Candidate 在一个任期内收到了来自集群内的多数选票（N/2+1），就可以成为 Leader。
在 Candidate 等待选票的时候，它可能收到其他节点声明自己是 Leader 的心跳，此时有两种情况：
- 该 Leader 的 term 号大于等于自己的 term 号，说明对方已经成为 Leader，则自己回退为 Follower。
- 该 Leader 的 term 号小于自己的 term 号，那么会拒绝该请求并让该节点更新 term。
由于可能同一时刻出现多个 Candidate，导致没有 Candidate 获得大多数选票，如果没有其他手段来重新分配选票的话，那么可能会无限重复下去。
Raft 使用了随机的选举超时时间来避免上述情况。每一个 Candidate 在发起选举后，都会随机化一个新的选举超时时间，这种机制使得各个服务器能够分散开来，在大多数情况下只有一个服务器会率先超时；它会在其他服务器超时之前赢得选举。
一旦选出了 Leader，它就开始接受客户端的请求。每一个客户端的请求都包含一条需要被复制状态机（Replicated State Machine）执行的命令。
Leader 收到客户端请求后，会生成一个 entry，包含<index,term,cmd>，再将这个 entry 添加到自己的日志末尾后，向所有的节点广播该 entry，要求其他服务器复制这条 entry。
如果 Follower 接受该 entry，则会将 entry 添加到自己的日志后面，同时返回给 Leader 同意。
如果 Leader 收到了多数 Follower 对该日志复制成功的响应，Leader 会推进自己的 commitIndex，并在随后将这些已提交（committed）的日志按顺序应用（apply）到状态机后再向客户端返回结果。
需要注意一个关键限制：Leader 只能基于"当前任期（current term）内产生的日志在多数派上复制成功"来推进 commitIndex。对于之前任期遗留的日志，即使它们已经被复制到多数节点，Leader 也不应仅凭多数派直接提交；通常会通过提交当前任期的一条新日志（常见做法是当选后追加并提交一条 no-op 日志）来间接推动历史日志一并提交。
Follower 不会自行决定提交点；它们从 Leader 的 AppendEntries RPC 中携带的 leaderCommit 得知当前可提交的最大索引，并将本地 commitIndex 更新为 min(leaderCommit, lastLogIndex)，再按序 apply 到状态机。
Raft 通过 日志匹配属性（Log Matching Property） 保证日志绝对不会分叉，这是 Raft 安全性的基石之一。该属性包含两个核心保证：
- 保证一：如果两个日志在相同 index 位置的 entry 具有相同的 term，那么它们存储的 cmd 一定相同
- 保证二：如果两个日志在相同 index 位置的 entry 具有相同的 term，那么该位置之前的所有 entry 也完全相同
日志匹配属性通过归纳法得以保证：
- 基础情况：日志为空时，属性自然成立
- 归纳步骤：假设日志在 index N 之前完全一致，当 Leader 尝试追加 entry N+1 时，通过 AppendEntries RPC 的一致性检查 确保：
AppendEntries RPC 参数：
- prevLogIndex：前一条日志的索引（Leader 认为与 Follower 对齐的位置）
- prevLogTerm：前一条日志的任期
- entries[]：待追加的新日志条目
一致性检查逻辑：
- Follower 收到 AppendEntries 请求后，检查本地日志中 index = prevLogIndex 的位置
- 如果该位置的 entry.term == prevLogTerm，说明Leader和Follower在prevLogIndex之前的日志完全一致，通过检查
- 如果不存在或 term 不匹配，拒绝追加，返回失败
关键点：通过检查 prevLogIndex 和 prevLogTerm 的配对，Leader 和 Follower 能够数学上确保它们对日志历史达成一致。只有当"最后一个已知一致点"确实一致时，才会追加新日志。这形成了归纳证明的传递链条：
entry[0] 一致 → entry[1] 一致 → entry[2] 一致 → ... → entry[N] 一致
↑_____________通过 prevLogIndex/prevLogTerm 递归验证_____________↑
因此，日志绝不会出现两个不同的值在同一 index 位置被"提交"的情况——即日志不分叉。
在实际生产实现（如 etcd 3.5.x）中，除了上述基础的一致性检查外，还包含多项工程优化：
-
快速回退（Fast Backup）：当 AppendEntries 一致性检查失败时，Follower 返回冲突日志对应的 term 及其边界索引（该 term 的第一条和最后一条 index），Leader 据此一次性跳过整段冲突区间，而非逐条递减 nextIndex 重试。
-
重试风暴防护：高负载下可能出现大量 AppendEntries 失败重试，实现中通常会加入：
- Jitter 退避：重试间隔加入随机抖动，避免多个 Follower 同时重试
- 背压机制：限制单个 Follower 的重试速率，防止占用过多网络带宽
这些优化不影响日志匹配属性的理论正确性，而是提升了系统在异常场景下的恢复效率。
一般情况下，Leader 和 Follower 的日志保持一致，但 Leader 的崩溃会导致日志出现差异。此时 AppendEntries 的一致性检查会失败，Leader 通过强制 Follower 复制自己的日志来处理日志的不一致。这就意味着，在 Follower 上的冲突日志会被领导者的日志覆盖。
为了使得 Follower 的日志和自己的日志一致，Leader 需要找到 Follower 与它日志一致的地方，然后删除 Follower 在该位置之后的日志，接着把这之后的日志发送给 Follower。
Leader 给每一个Follower 维护了一个 nextIndex，它表示 Leader 将要发送给该追随者的下一条日志条目的索引。当一个 Leader 开始掌权时，它会将 nextIndex 初始化为它的最新的日志条目索引数+1。如果一个 Follower 的日志和 Leader 的不一致，AppendEntries 一致性检查会在下一次 AppendEntries RPC 时返回失败。
**（朴素实现）**在失败之后，Leader 会将 nextIndex 递减然后重试 AppendEntries RPC，直到找到 Leader 与 Follower 日志一致的位置。
**（工程优化）**实际生产实现通常会加入快速回退（Fast Backup）：Follower 在拒绝 AppendEntries 时返回冲突日志对应的任期（term）以及该任期的边界索引，Leader 据此一次性跳过整段冲突区间，显著减少重试次数。
最终 nextIndex 会达到一个 Leader 和 Follower 日志一致的地方。这时，AppendEntries 会返回成功，Follower 中冲突的日志条目都被移除了，并且添加所缺少的上了 Leader 的日志条目。一旦 AppendEntries 返回成功，Follower 和 Leader 的日志就一致了，这样的状态会保持到该任期结束。
Leader 需要保证自己存储全部已经提交的日志条目。这样才可以使日志条目只有一个流向：从 Leader 流向 Follower，Leader 永远不会覆盖已经存在的日志条目。
每个 Candidate 发送 RequestVote RPC 时，都会带上最后一个 entry 的信息。所有节点收到投票信息时，会对该 entry 进行比较，如果发现自己的更新，则拒绝投票给该 Candidate。
判断日志新旧的方式：如果两个日志的 term 不同，term 大的更新；如果 term 相同，更长的 index 更新。
Leader 推进 commitIndex 时，需要满足"当前任期产生的某条日志已复制到多数派"这一条件。对于旧任期遗留的日志，即使它们已经复制到多数派，Leader 也不应仅凭此直接提交；通常通过提交当前任期的一条新日志（常见为 no-op）来间接提交历史日志。这一限制用于避免 Leader 频繁切换时出现已提交日志被覆盖的安全性问题。
如果 Follower 和 Candidate 崩溃，处理方式会简单很多。之后发送给它的 RequestVote RPC 和 AppendEntries RPC 会失败。由于 Raft 的所有请求都是幂等的，所以失败的话会无限的重试。如果崩溃恢复后，就可以收到新的请求，然后选择追加或者拒绝 entry。
如果 Leader 崩溃，节点在 electionTimeout 内收不到心跳会触发新一轮选主；在选主完成前，系统通常无法对外提供线性一致的写入（以及线性一致读），表现为一段不可用窗口。
量化分析：在 5 节点集群中，Leader 崩溃后的不可用窗口通常小于 1 秒（P99 < 500ms 选举超时 + 一轮选举时间）。这是 PACELC 定理的体现：发生分区（P）时，系统选择牺牲可用性（A）以保证一致性（C）。幂等重试机制确保节点恢复后能安全追赶数据状态。
在标准 Raft 算法中，单节点网络隔离可能导致 Term 暴增（Term Inflation） 问题，造成"劣币驱逐良币"——一个被隔离的少数派节点在恢复后破坏健康集群的稳定性。
场景推演：
假设一个 5 节点集群，Leader 为节点 A，Follower 为 B、C、D、E。此时节点 E 发生网络分区，被彻底隔离：
正常区域：{A, B, C, D} （Leader A + 多数派，可正常服务）
隔离区域：{E} （单节点隔离，无法收到心跳）
| 时间线 | 正常区域 {A, B, C, D} | 隔离区域 {E} |
|---|---|---|
| T0 | Leader A 正常服务，Term = 5 | E 收不到心跳，选举超时 |
| T1 | 集群继续正常工作 | E 自增 Term 发起选举（Term 6），但无响应 |
| T2 | ... | E 继续自增（Term 7, 8, ...），假设涨到 Term 99 |
| T3 | 网络恢复，E 带着 Term 99 接入集群 | E 向 {A, B, C, D} 广播 RequestVote (Term 99) |
| T4 | 节点 A 收到 Term 99 > 自己的 Term 5，被迫退位 | E 的"高 Term"破坏了健康集群 |
问题分析：
- {A, B, C, D} 是合法的多数派（4/5），系统本应继续正常工作
- 节点 E 是少数派（1/5），它的隔离不应影响集群整体
- 关键问题：E 的 Term 暴涨导致健康的 Leader A 被迫下线
- 后果：整个集群需要重新选举，造成不必要的写入中断
这是标准 Raft 的一个已知边界问题：少数派节点的"疯狂选举"会干扰多数派的正常运行。
为了解决上述问题，Raft 的扩展方案 Pre-Vote 被提出。Pre-Vote 要求节点在真正发起选举前，先进行一次"预投票"：
- 预投票阶段：Candidate 向其他节点发送 PreVoteRequest，携带自己的日志信息
- 预投票条件：
- 候选人的日志至少与接收者一样新（选举限制）
- 接收者确认自己与 Leader 的连接已断开（超过 electionTimeout 未收到心跳）
- 正式选举：只有收到多数节点的 PreVote 响应后，才真正增加 term 并发起 RequestVote
Pre-Vote 如何防止 Term 暴增：
- 在上述单节点隔离场景中，E 在隔离期间发起 Pre-Vote 时，其他节点仍能收到 Leader A 的心跳
- 因此其他节点会拒绝 E 的 PreVote 请求（因为与 Leader 连接正常）
- E 无法获得多数 PreVote 响应，不会真正增加 Term
- 网络恢复后，E 的 Term 仍然较低，不会干扰健康的 Leader A
核心思想：只有确认自己与 Leader 失去连接后，节点才开始真正增加 Term。这有效防止了少数派节点的 Term 暴涨干扰多数派。
Pre-Vote 机制已广泛应用于 etcd、TiKV、Consul 等生产级 Raft 实现。
Raft 的要求之一就是安全性不依赖于时间：系统不能仅仅因为一些事件发生的比预想的快一些或者慢一些就产生错误。为了保证上述要求，最好能满足以下的时间条件：
broadcastTime << electionTimeout << MTBF
broadcastTime：向其他节点并发发送消息的平均响应时间；electionTimeout：选举超时时间；MTBF(mean time between failures)：单台机器的平均健康时间；
broadcastTime应该比electionTimeout小一个数量级，为的是使Leader能够持续发送心跳信息（heartbeat）来阻止Follower开始选举；
electionTimeout也要比MTBF小几个数量级，为的是使得系统稳定运行。当Leader崩溃时，大约会在整个electionTimeout的时间内不可用；我们希望这种情况仅占全部时间的很小一部分。
由于broadcastTime和MTBF是由系统决定的属性，因此需要决定electionTimeout的时间。
一般来说，broadcastTime 一般为 0.5～20ms，electionTimeout 可以设置为 10～500ms（工程上常见如 150–300ms），MTBF 一般为一两个月。