Raft 算法

Raft 是一种共识算法，相较于 Paxos，Raft 则更易被理解，但又具备其相当的容错性和性能。

共识 (Consensus) 是分布式系统中要解决的基本问题。大多数人可能都听说过 CAP 定理，它描述的是在解决共识问题时，最多只能同时满足：一致性（Consistency）、高可用（Availability）、分区容忍（Partition tolerance）这 3 个目标中的 2 个。而 Raft 是提供一致性、分区容忍保证的算法。

一个典型的共识算法实现应该满足以下准则：

• 确保安全（永远不返回错误的结果），在所有非 拜占庭 情况下，包括网络延迟、分区、丢包、重复和乱序
• 只要大多数节点可用（互相且与客户端可通讯），集群应该是功能完备的。所以 5 个节点的集群，可以容错 2 个节点
• 日志的一致性不依赖时间，时钟错误和极端的消息延迟在最坏的情况下会导致可用性问题
• 大部分情况下，大部分节点响应了命令就可以完成，小部分节点慢不影响整个系统的性能

另外，Raft 论文中给出了 Paxos 的 2 个问题：

• 算法难以理解
• 没有给出实际实现

接下来，我们将从 Raft 的基本组成和解决问题的方式开始逐一介绍。

简介

先介绍几个核心概念：

• Leader：集群中唯一的"指挥官"，负责处理所有客户端请求并向其他节点复制日志
• Follower：被动接收 Leader 的日志和心跳，不主动发起请求
• Candidate：选举过程中的临时状态
• 日志 Log：状态机命令的有序集合
• 任期 Term：单调递增的逻辑时钟，每次选举开始一个新任期

Raft 算法实现的集群一般由 3 或 5 个节点组成，具有以下几个特性：

• 强 Leader：命令/日志只能从 Leader 节点流向其他节点
• Leader 选举：使用随机定时器选举，增加心跳机制，有效地解决冲突
• 关系变更：在调整集群节点（增加/删除）时能够通过过渡机制，允许集群继续被操作

下面是 Raft 架构的示意图：

                       AppendEntries (heartbeat + log)
                ┌───────────────────────────────────────────┐
                ▼                                            │
   ┌────────┐          ┌────────┐          ┌────────┐
   │ Client │  ───→    │ Leader │  ───→    │Follower│
   └────────┘          └────────┘  ───→    └────────┘
                            │              ┌────────┐
                            └─────────→    │Follower│
                                           └────────┘

整个流程：

1. 客户端（Client）向集群 Leader 节点（Server）发起请求
2. 共识模块写入日志，并向其他节点复制
3. 大多数节点成功复制后，提交日志并应用到状态机
4. 返回响应到客户端

节点角色

Raft 算法中规定节点有 3 种角色：

• Follower：不会主动发起请求，只接收其他类型节点的请求；来自客户端的请求会被重定向到 Leader 节点
• Candidate：会发送 RequestVote 类型的请求进行选举
• Leader：会发送 AppendEntries 和 InstallSnapshot 请求，同时处理客户端的请求

一个正常的集群由一个 Leader 节点，以及若干个 Follower 节点组成。

数据结构

所有节点都需要持久化的状态：

struct PersistentState {
    currentTerm: i64,      // 当前任期（单调递增）
    votedFor: Option<i64>, // 当前任期内投给了哪个 Candidate
    log: Vec<LogEntry>,    // 日志条目
}

所有节点的易失状态（内存）：

struct VolatileState {
    commitIndex: i64,  // 已知已提交的最高日志索引
    lastApplied: i64,  // 已应用到状态机的最高索引
}

Leader 节点选举后重新初始化的易失状态：

struct LeaderState {
    nextIndex:  Vec<i64>, // 对每个 Follower，需要发给它的下一条日志索引
    matchIndex: Vec<i64>, // 对每个 Follower，已知它已复制的最高日志索引
}

角色转换

                ┌──────────┐
   启动时       │ Follower │ ←─────────────┐
   ─────────→   └────┬─────┘               │
                     │                     │
       electionTimeout 内没收到合法消息   收到合法 Leader 消息
                     │                     │
                     ▼                     │
                ┌──────────┐               │
                │Candidate │───┐           │
                └────┬─────┘   │           │
                     │         │           │
       获得 >N/2 选票  超时未当选 (新一轮选举)
                     │         │           │
                     ▼         └───→ Candidate
                ┌──────────┐
                │  Leader  │───────────────┘
                └──────────┘  (发现更高 Term, 退回 Follower)

时间常量必须满足：

broadcastTime ≪ electionTimeout ≪ MTBF

• broadcastTime：发送一次 RPC 的耗时（通常 ms 级）
• electionTimeout：触发新一轮选举的超时（通常 150ms ~ 300ms 之间随机）
• MTBF：节点平均故障间隔（通常天/月级）

选举（Leader Election）

选举是 Raft 最有趣的部分。Raft 把时间切成 任期（Term），每个 Term 最多有一个 Leader（也可能没有，即选举失败）。

选举触发

每个 Follower 维护一个 electionTimeout（150-300ms 之间随机）。如果在这个时间内：

• 收到当前 Leader 的 AppendEntries（心跳算空 AppendEntries）→ 重置定时器
• 收到合法 Candidate 的 RequestVote → 视情况投票/重置

如果定时器到期都没收到合法消息，Follower 认为 Leader 挂了，启动新一轮选举：

1. 自身 Term + 1
2. 转为 Candidate
3. 给自己投一票
4. 并行向其他节点发送 RequestVote RPC

投票规则

每个节点在每个 Term 内只能投一票，并遵循 first-come-first-served + 日志至少和自己一样新 的规则：

• 如果请求中的 Term < 自己的 Term，拒绝
• 如果本 Term 已经投过票了，拒绝
• 如果 Candidate 的日志比自己旧（最后一条日志的 Term 更小，或 Term 相同但 Index 更小），拒绝
• 否则同意，并把 votedFor = candidateId，重置自己的 electionTimeout

这个"日志至少和自己一样新"的约束很关键——它保证了已提交的日志一定会被新的 Leader 继承（Leader Completeness Property）。

选举结果

Candidate 等到以下三种情况之一：

1. 赢得选举：收到大多数节点的同意票 → 立即转为 Leader，开始发心跳
2. 发现更高 Term 的 Leader：收到合法 AppendEntries → 退回 Follower
3. 选举超时：例如多个 Candidate 同时发起选举导致票数瓜分（split vote）→ Term + 1，重新选举

随机化的 electionTimeout 是用来打破 split vote 死循环的关键设计——只要超时时间随机，就大概率会有一个 Candidate 先超时，重新发起，错开拿到多数票。

日志复制（Log Replication）

Leader 选出来之后，所有客户端请求都走 Leader：

1. 接收请求：Leader 把请求作为一个新的日志条目（LogEntry）追加到本地日志
2. 并行复制：通过 AppendEntries RPC 把这条日志发给所有 Follower
3. 等待多数派：当 Leader 知道大多数节点都已经持久化了这条日志，就标记为 committed
4. 应用状态机：Leader 把 committed 的日志应用到状态机，并返回结果给客户端
5. 通知 Follower：下一次 AppendEntries（或心跳）会带上最新的 leaderCommit，Follower 看到后也会把对应日志应用到自己的状态机

日志匹配性（Log Matching Property）

Raft 保证：如果两个日志在某个 index 上有相同的 Term，那么：

• 这两条日志的内容相同
• 这两个日志在该 index 之前的所有日志也都相同

这个性质通过 AppendEntries 中的 prevLogIndex 和 prevLogTerm 一致性检查保证：

struct AppendEntriesRequest {
    term: i64,
    leaderId: i64,
    prevLogIndex: i64,
    prevLogTerm: i64,
    entries: Vec<LogEntry>,
    leaderCommit: i64,
}

Follower 收到 AppendEntries 时，先检查自己 log[prevLogIndex].term == prevLogTerm：

• 不匹配 → 拒绝，让 Leader 把 nextIndex 往前推一格继续重试
• 匹配 → 接受 entries，并截断后面冲突的日志

这就保证了 Follower 的日志最终和 Leader 一致。

Leader 不直接覆盖之前任期的日志

Raft 论文里有一个微妙的细节：Leader 不能直接提交之前任期的日志，只能通过提交自己任期的日志间接提交它们（Figure 8 反例）。

直觉是：一条日志被大多数节点复制不等于它一定能被提交，因为可能存在网络分区让另一个有更新日志的节点重新成为 Leader 然后覆盖它。Raft 通过这个限制规避了这种"幽灵复活"问题。

安全性（Safety）

Raft 通过几个不变量保证安全性：

性质	含义
Election Safety	任意一个 Term 最多只有一个 Leader
Leader Append-Only	Leader 永远不删除/覆盖自己的日志
Log Matching	两个日志相同 index 相同 term → 之前所有日志也相同
Leader Completeness	任意 committed 日志一定出现在所有后续 Leader 的日志中
State Machine Safety	所有节点应用到状态机的日志序列相同

这些性质组合起来，保证了在任何故障组合下（节点挂、网络分区、消息丢失、重启），状态机最终一致。

集群成员变更（Cluster Membership Change）

线上集群难免要做扩缩容（加节点、换节点）。直接切换会有问题——新旧配置的多数派可能不重叠，导致两个 Leader 并存。

Raft 给出了两种方案：

1. Joint Consensus（共识联合）：先切到 C_old,new 的过渡配置（要求新旧两个配置都达成多数派），再切到 C_new。论文的"正统"方案，比较复杂。
2. 单节点变更：一次只增加/移除一个节点，因为新旧配置的多数派一定有交集，所以可以不需要过渡阶段。etcd/Consul 等主流实现都采用了这种方案。

日志压缩（Log Compaction）

日志会无限增长，所以需要快照机制：

1. 节点周期性地把当前状态机的状态做一个快照（snapshot）
2. 丢掉快照之前的日志
3. 落后太多的 Follower 通过 InstallSnapshot RPC 直接拿快照

快照的关键是要包含 lastIncludedIndex 和 lastIncludedTerm，让接收快照的节点知道自己的 log 应该截断到哪里。

工程实现要点

理论很美，但落地时有不少坑：

1. 持久化时机：currentTerm、votedFor、log 必须在响应 RPC 前 fsync 到磁盘，否则掉电后可能违反 Election Safety
2. 批量提交：实际系统不会每条日志都 fsync，而是 batch 起来一起 fsync，否则性能太差
3. 流水线（Pipeline）：Leader 发给 Follower 的 AppendEntries 可以不等回复就发下一批，靠 nextIndex 失败重试来回退
4. Pre-Vote：分区恢复后，少数派分区的节点可能因为 Term 已经涨得很高而扰乱集群，Pre-Vote 机制让 Candidate 在真正发起选举前先试探一下能不能赢，避免无意义的 Term bump
5. Leader Lease：纯 Raft 协议中，Leader 不知道自己是否还是 Leader，只能强制让所有读请求也走多数派；Lease 机制允许 Leader 在租约期内本地处理只读请求

推荐资源

• Raft 论文（In Search of an Understandable Consensus Algorithm）
• Raft 可视化动画（极力推荐，看一遍胜过读半天论文）
• etcd 的 raft 库：工业级 Go 实现，代码可读性极佳
• TiKV 的 raft-rs：Rust 实现，性能极强