Raft 共识算法

Raft 概览

Raft 将共识问题分解为三个相对独立的子问题：Leader 选举、日志复制和安全性。每个服务器在任一时刻处于以下三种状态之一：

Raft 由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年发表（论文标题《In Search of an Understandable Consensus Algorithm》）。设计目标是比 Paxos 更容易理解，同时提供等价的安全性保证。Paxos 长期以来是共识算法的代名词，但其难以理解和工程实现的问题广受诟病。Raft 将共识分解为 Leader 选举、日志复制和安全性三个独立子问题，大幅降低了理解门槛。

Raft 使用 Term（任期）作为逻辑时钟。每个 Term 以一次选举开始，最多产生一个 Leader。Term 号单调递增，节点间通信时交换 Term 号——发现自己 Term 较小时立即退为 Follower，发现对方 Term 较小则拒绝该 RPC。Term 机制使得 Raft 能检测过期信息（如已下台的旧 Leader 发来的请求）。

Raft 节点间通过两种 RPC 通信：RequestVote（Candidate 在选举期间发起）和 AppendEntries（Leader 用于日志复制和心跳）。此外还有 InstallSnapshot（Leader 向严重落后的 Follower 发送快照）。RPC 可并行发起，超时后重试。

所有节点必须将 currentTerm、votedFor、log[] 三个变量持久化到磁盘（响应 RPC 之前写入）。这是 Raft 正确性的基石——重启后从磁盘恢复，不会违反投票规则或丢失已接受的日志。commitIndex 和 lastApplied 是易失的，可在重启后重新计算。

§5.6 时序要求：Raft 的安全性不依赖时序（即使时钟不准也不会产生错误结果），但可用性需要满足不等式 broadcastTime ≪ electionTimeout ≪ MTBF。典型值：broadcastTime 0.5~20ms、electionTimeout 150~300ms、MTBF 数周至数月。只要心跳比选举超时快一个数量级，Leader 就能持续维持地位而不触发新选举。

Leader 选举

§5.2：Raft 使用心跳机制触发选举。Leader 定期发送空的 AppendEntries RPC 作为心跳。当 Follower 在 electionTimeout 时间内未收到心跳，就认为 Leader 已宕机——递增 currentTerm、将自己转为 Candidate、投自己一票（votedFor = 自己）并向所有其他节点并行发送 RequestVote RPC。

RequestVote 携带 Candidate 的 term、candidateId、lastLogIndex 和 lastLogTerm。收到请求的节点检查两个条件：(1) Candidate 的 Term 不低于自己的 currentTerm；(2) Candidate 的日志至少和自己一样新（比较规则见「安全性」章节）。每个节点在同一 Term 内只投一票，先到先得。

选举有三种结果：① 获得多数票（N/2+1）→ 成为 Leader，立即发送心跳确立权威；② 等待期间收到了合法 Leader（Term ≥ 自己）的 AppendEntries → 承认该 Leader，退为 Follower；③ 超时仍无人当选 → 递增 Term 重新选举。由于每个 Term 最多一个 Leader，且需要多数票，因此不可能在同一 Term 产生两个 Leader。

Split Vote 分票

§5.2：当多个 Follower 几乎同时超时并发起选举时，选票会被分散——没有 Candidate 获得多数票。这就是 Split Vote 问题。如果不加处理，Split Vote 可能反复发生，导致集群长时间无法选出 Leader。

Raft 使用随机化选举超时解决此问题。每个节点的 electionTimeout 从固定区间（如 150~300ms）中随机选取。这使得大多数情况下只有一个节点最先超时并发起选举，在其他节点超时前就已获得多数票。论文实验表明，使用 150~300ms 的随机超时，选举通常在第一轮即可完成，极少需要第二轮。

日志复制

§5.3：Leader 当选后开始服务客户端请求。每个请求包含一条要被状态机执行的命令。Leader 将命令作为新日志条目追加到自己的日志末尾，然后并行发送 AppendEntries RPC 给所有 Follower。每条日志条目包含三个字段：index（日志索引，从 1 开始单调递增）、term（创建该条目时 Leader 的任期号）和 command（状态机命令）。

日志匹配特性（Log Matching Property）：① 如果两个节点的日志在相同 index 处有相同的 term，则它们包含相同的 command；② 如果两个节点的日志在相同 index 处有相同的 term，则该 index 之前的所有日志也完全相同。第一条由 Leader 保证（一个 Term 的 Leader 在给定 index 只会创建一条日志）；第二条由 AppendEntries 的一致性检查保证——每次 AppendEntries 都携带 prevLogIndex 和 prevLogTerm，Follower 只有在匹配时才接受新条目。

提交规则：当一条日志被成功复制到多数节点（N/2+1）后，Leader 将其标记为已提交（committed）。提交是持久的、不可逆的。所有在此之前的日志也自动被提交。Leader 在后续 AppendEntries 中携带 leaderCommit 字段，Follower 据此更新自己的 commitIndex，并将已提交日志按序应用到状态机。

日志不一致修复

§5.3：日志不一致发生在 Leader 崩溃时——旧 Leader 可能只将日志复制到了部分节点。经过多次 Leader 更替，Follower 的日志可能多出或缺少条目，甚至包含不同 Term 的冲突条目。

Leader 为每个 Follower 维护两个索引：nextIndex（下一条要发送给该 Follower 的日志索引）和 matchIndex（已确认复制到该 Follower 的最高索引）。新 Leader 上任时，将所有 nextIndex 初始化为自己日志末尾 + 1，matchIndex 初始化为 0。

修复机制：Leader 发送 AppendEntries 时携带 prevLogIndex 和 prevLogTerm。如果 Follower 在 prevLogIndex 处的 term 不匹配，返回失败。Leader 收到失败后递减该 Follower 的 nextIndex 并重试，直到找到双方日志的匹配点。找到后，Follower 删除匹配点之后的所有冲突条目，接受 Leader 的日志覆盖——最终 Follower 日志与 Leader 完全一致。这个机制是自动的，无需人工干预。

安全性与选举限制

§5.4.1 选举限制：Raft 通过在投票环节增加限制来保证安全性。RequestVote RPC 包含 Candidate 的日志信息（lastLogIndex 和 lastLogTerm），投票者会拒绝日志不如自己新的 Candidate。比较规则：先比较最后一条日志的 term，term 大的更新；term 相同则 index 大的更新。

这保证了 Leader Completeness 属性：如果一条日志已在某个 Term 被提交，那么该条目一定会出现在所有更高 Term 的 Leader 日志中。由此推导出 State Machine Safety：所有节点以相同顺序执行相同的已提交命令，所有状态机最终一致。

§5.4.3 安全性论证（反证法）：假设某已提交条目 E 不在新 Leader T 的日志中。E 已复制到多数节点 S1，T 获得了多数节点 S2 的投票。S1 和 S2 必有交集节点 V——V 既持有 E 又投票给了 T。如果 V 先投票后收到 E，则 E 的 Leader term 比 T 大，与 T 是更高 term 矛盾。如果 V 先收到 E 后投票，则 V 的日志比 T 新，按选举限制 V 不会投票给 T——矛盾。因此假设不成立，已提交条目一定存在于所有后续 Leader 中。

提交前任期日志

§5.4.2：Raft 规定 Leader 只能通过计算当前 term 的日志副本数来提交日志。如果一条日志是在前任期创建的，即使已被复制到多数节点，Leader 也不能直接将其标记为已提交。必须先提交一条当前 term 的新条目，根据日志匹配特性，之前的所有条目会被间接提交。

为什么直接提交前任期日志不安全？因为一个已经复制到多数的前任期条目，可能被未来的 Leader 覆盖。图 8 的场景 (d) 就展示了这种情况：Term 2 的条目在三个节点上存在，但若 Leader 宕机，拥有 Term 3 条目的 S5 仍可能当选并覆盖它们。

这就是为什么新 Leader 上任后通常会立即提交一条 no-op（空操作）日志——它不改变状态机状态，但确保了当前 term 有日志被提交，从而间接提交之前所有已复制到多数的日志。

崩溃恢复与幂等性

§5.5：Follower 和 Candidate 的崩溃处理比 Leader 简单得多。它们崩溃后，后续发往该节点的 RequestVote 和 AppendEntries RPC 会失败，Raft 的解决方式很直接——无限重试。节点重启后会收到并正常处理这些重试的 RPC。

Raft 的 RPC 天然幂等：如果一条 AppendEntries 发送了已经存在于 Follower 日志中的条目，Follower 会发现日志匹配并忽略重复条目，不会产生副作用。同样，重复收到同一 Term 的 RequestVote 也不会改变 votedFor（因为已经投过了）。

正确性的前提：currentTerm、votedFor 和 log[] 必须在响应任何 RPC 之前持久化到稳定存储（磁盘）。如果 votedFor 没有持久化，节点重启后可能在同一 Term 给另一个 Candidate 投票，导致一个 Term 内出现两个 Leader——违反安全性。这就是为什么这三个变量被称为「持久化状态」，而 commitIndex 和 lastApplied 属于「易失状态」可以在重启后重建。

客户端交互

§8：Raft 的目标是实现线性化语义（linearizable semantics）——每个客户端命令在调用和收到响应之间的某个时刻恰好执行一次。但网络异常可能导致命令重复：如果 Leader 提交日志并应用到状态机后、响应客户端之前崩溃，客户端会重试发送同一命令，导致命令被执行两次。

解决方案——序列号去重：每个客户端为每条命令分配一个唯一的递增序列号。Leader 维护每个客户端的最新已执行序列号及对应的响应缓存。当收到一个已执行过的序列号时，直接返回缓存的结果，不再追加日志或重复应用到状态机。这就保证了恰好一次语义。

只读请求优化：只读操作不需要写日志，但如果 Leader 直接返回本地状态可能返回过期数据——因为可能有一个新 Leader 已经上任，旧 Leader 还不知道。Raft 的解决方案：Leader 在处理只读请求之前，先向多数节点发送一轮心跳。如果收到多数回复且没有发现更高的 Term，则证明自己仍是合法 Leader，可以安全地返回当前状态。

集群成员变更

§6：集群成员变更是工程实践中的重要需求（扩容、缩容、替换故障机器）。直接从旧配置 C_old 切换到新配置 C_new 是不安全的——因为不同节点在不同时间切换配置，可能导致同一 Term 内 C_old 的多数派和 C_new 的多数派各自独立选出一个 Leader。

Raft 使用联合共识（Joint Consensus）分两阶段完成变更：第一阶段，Leader 将 C_{old,new} 联合配置作为日志条目提交——在联合阶段，任何决策（选举和提交）都需要同时获得旧配置和新配置各自多数派的同意。这保证了 C_old 和 C_new 不会单方面做出决策。第二阶段，联合配置提交后，Leader 再提交 C_new 配置，此后只需要新配置的多数派即可。

三个关键边界情况：① 新加入的节点可能需要较长时间追赶日志，在追赶期间它们作为无投票权的 learner（只接收日志不参与选举计数）；② 如果 Leader 自身不在 C_new 中，它在提交 C_new 后退位，新配置中的某个节点接替 Leader；③ 被移除的节点如果没收到 C_new，可能会超时发起选举干扰当前 Leader。Raft 通过 Pre-Vote 或让节点在收到心跳时忽略 RequestVote 来解决此问题。

日志压缩与快照

§7：日志不可能无限增长——它会消耗大量存储空间，并在重启时拖慢恢复速度。Raft 使用快照（snapshot）进行日志压缩：每个节点独立地将自己已提交的日志的最终状态保存为一个快照，然后丢弃该快照覆盖的所有日志条目。

快照包含三部分：完整的状态机状态、lastIncludedIndex（快照覆盖到的最后一条日志索引）和 lastIncludedTerm（该条目的 Term）。lastIncludedIndex 和 lastIncludedTerm 用于 AppendEntries 的一致性检查——紧跟快照之后的第一条日志需要它们作为 prevLogIndex 和 prevLogTerm。

当 Leader 发现某个 Follower 严重落后（nextIndex ≤ lastIncludedIndex，即要发的日志已被快照覆盖），Leader 通过 InstallSnapshot RPC 将整个快照发送给该 Follower。Follower 收到后丢弃全部旧日志，加载快照中的状态机状态，从快照点之后继续跟随。值得注意的是，Raft 让每个节点独立做快照而非由 Leader 统一推送，避免了浪费网络带宽——大多数情况下 Follower 自身就有足够的已提交日志来做快照。