经典算法深度解析|Raft:从复制状态机到领导者选举、日志复制与线性一致性
如果你学过分布式系统,大概率已经反复看到过这样一句话:
共识很难,而 Raft 的目标是把它讲清楚。
这句话并不只是宣传语。
在很长一段时间里,很多工程师第一次接触共识算法时,面对的往往是 Paxos。一方面,Paxos 在理论上极其重要;另一方面,它对很多初学者来说,确实不太“顺手”。不是因为它不严谨,而是因为它的叙述方式更偏证明导向,系统工程视角不够直接。于是很多人学完以后,依然很难回答下面这些问题:
- 一个分布式数据库到底是怎么选 leader 的
- 客户端写入之后,为什么能保证多数副本最终看到同一个顺序
- leader 宕机以后,为什么不会把已经提交的数据弄丢
- 为什么有些日志明明存在于某些节点上,却仍然不能算 committed
- 配置变更、快照压缩、只读请求这些工程问题,又该怎么放进共识框架里
Raft 的价值就在这里。
它不是说“共识变简单了”,而是说:
把问题拆开,限制系统结构,明确谁负责做决定,让整个算法更符合工程师的大脑模型。
这篇文章会尽量做到两件事:
- 深入浅出,把 Raft 的核心思路讲得足够直观
- 保持深度,不只停留在“有 leader、会复制日志”的表层描述
我们会一路讲到:
- Raft 解决的到底是什么问题
- term、leader、log、commit 这些概念为什么要这样设计
- 领导者选举和日志复制是如何互相配合的
- Raft 为什么能提供线性一致的状态机语义
- 配置变更、快照、读请求这些工程细节应该怎么理解
- 常见误解和真实代价分别是什么
1. 先把问题说清楚:Raft 解决的是“复制状态机”问题
很多文章一上来就讲 RequestVote、AppendEntries、election timeout,看完之后你还是容易只记住流程,而忘了它真正服务的目标。
Raft 要解决的问题,其实可以先抽象成一句话:
怎样让多台机器,即使在部分节点宕机、网络延迟甚至短暂分区的情况下,依然对一串命令的顺序达成一致,并把它们执行成同一个状态。
这就是经典的 replicated state machine 模型。
你可以把它想象成这样:
- 每台节点上都跑着同一个状态机
- 状态机本身是确定性的
- 只要它们按同样顺序执行同样命令,最终状态就相同
例如,一个简单的键值存储:
set x = 1set y = 2delete x
如果所有副本都按这个顺序执行,那么它们最终的内存状态一定一致。
所以问题就从“复制整个内存”变成了:
复制一份全体节点都认可的命令日志。
这一步很关键。
因为状态机复制的核心,不是把每次状态变化都直接同步过去,而是先让大家对“操作顺序”达成一致。顺序一旦一致,确定性状态机自然会收敛到一致结果。
于是我们可以把 Raft 的任务拆成三件事:
- 选出一个 leader,让系统有一个主要决策入口
- 由 leader 接收客户端命令并复制日志
- 在满足一定条件后,把日志标记为 committed,再应用到状态机
看起来朴素,但这里面真正难的是:
- leader 可能挂掉
- 某些 follower 可能落后很多
- 网络可能让不同节点短时间内对“谁是 leader”有不同看法
- 旧 leader 曾经写过但未提交的日志,不能错误覆盖已提交数据
Raft 的全部设计,几乎都在围绕这些失败场景建立不变量。
2. 理解 Raft 的第一把钥匙:它故意把系统做成“强 leader”
Raft 和很多人直觉中的“大家投票共同决定每条日志”不同。
它最鲜明的设计选择,是 strong leader。
也就是说:
- 客户端写请求通常只发给 leader
- 日志只能从 leader 流向 follower
- follower 不会彼此协商生成新日志顺序
- commit 的推进也由 leader 统一判断
为什么这样设计?
因为分布式系统里,复杂度常常不是来自“功能不够”,而是来自“决策入口过多”。
如果多个节点都能独立提出并决定日志顺序,那么你立刻就要处理:
- 冲突提案怎么比较
- 不同提案如何合并
- 提案编号和接受条件如何设计
- 多条并行路径如何在失败恢复后重新归并
Raft 的选择很直接:
不要让所有人都参与每条日志的决策,把大多数复杂性集中到 leader 生命周期管理上。
这让 Raft 的整体理解路径变成:
- 先保证任意时刻尽量只有一个 leader 在当前 term 内合法工作
- 再保证 leader 产生的日志有一套单调扩展规则
- 最后保证未来的 leader 不会丢失已经提交的历史
这就是它“可理解性更好”的根本原因。不是它没有复杂性,而是它把复杂性压缩到了更容易讲清楚的地方。
3. Raft 的四个核心对象
理解 Raft,先把四个对象记牢。
3.1 Term:把时间切成一段一段的任期
Raft 里的时间不是物理时钟,而是逻辑上的 term(任期)。
你可以把 term 理解成系统的“朝代编号”:
- 每次新的选举开始,term 增加
- 在一个 term 内,最多允许有一个合法 leader
- 所有 RPC 都会携带 term,节点借此识别谁更“新”
term 的作用非常大,因为它给了系统一个最简单但极强的判断规则:
谁看到更大的 term,谁就承认自己过时。
一旦节点发现收到的请求带着更大的 term,它就会:
- 更新自己的 current term
- 退回 follower 状态
- 放弃旧 term 内自认为拥有的领导权
这个规则是很多安全性的起点。
3.2 Role:Follower、Candidate、Leader
每个节点在任一时刻都处于三种角色之一:
- Follower:默认状态,不主动发起日志决策
- Candidate:选举期间的竞选者
- Leader:当前任期的主写入节点
这个角色机非常简洁,但足以覆盖完整生命周期:
- 长时间收不到 leader 心跳,follower 变 candidate
- candidate 发起投票,请求多数支持
- 赢得多数后升级为 leader
- 看到更高 term 后,无论原来是什么角色,都退回 follower
3.3 Log:真正被复制的是日志,不是状态
Raft 复制的基本单位是 log entry。
每条日志通常至少包含:
index:日志位置term:产生该日志时的 leader termcommand:要应用到状态机的命令
这里 term 很关键。
它不是装饰字段,而是日志历史的“血统标记”。后面 Raft 判断日志新旧、比较候选人资格、处理冲突覆盖,都离不开这个字段。
3.4 Commit:存在于日志里,不等于已经被确认
很多人初学时最容易混淆三个概念:
- 日志被 leader 接收了
- 日志被复制到若干 follower 了
- 日志被 committed 并应用到状态机了
这三件事不是同一时刻发生的。
在 Raft 里,一条日志“存在”并不自动意味着它对外生效。只有当系统判断它已经满足提交条件时,才会把它视为 committed,然后各节点才能按顺序 apply 到状态机。
这个延迟是 Raft 保证安全性的关键。
4. 领导者选举:为什么随机超时就能大幅降低冲突
Raft 的 leader election 看起来非常简单,但简单不代表随便。
4.1 选举是怎么触发的
follower 平时会持续接收 leader 的心跳。这个心跳通常就是不带新日志的 AppendEntries。
如果 follower 在一段时间内没收到合法 leader 的消息,它就会怀疑 leader 不可用了,于是:
- 把自己的 term 加一
- 把自己变成 candidate
- 先投自己一票
- 向其他节点发送
RequestVote
如果拿到多数票,它就成为新的 leader。
4.2 为什么需要随机 election timeout
如果所有节点的超时时间完全一样,那么 leader 一旦失联,很容易出现所有 follower 同时发起竞选:
- A 投自己
- B 投自己
- C 投自己
于是大家都拿不到多数,选举僵住,然后下一轮再重复。
Raft 的办法不复杂:
给每个节点一个随机的选举超时区间。
这样一来,通常总会有一个节点比别人更早超时、率先发起投票。它抢先拿票后,就有机会在别人还没开始竞选前成为 leader。
这不是严格证明意义上的“杜绝冲突”,但在工程上极其有效。
它体现了 Raft 的一贯风格:
不追求花哨结构,而是优先选择最容易解释、最容易实现、又足够有效的机制。
4.3 为什么一个节点不能在同一 term 投多票
这是选举安全性的基本前提。
每个节点在同一个 term 中最多投给一个 candidate。否则两个不同候选者都可能分别拿到“看起来像多数”的支持,直接破坏单 leader 假设。
所以节点需要持久化至少两类元数据:
- 当前
currentTerm - 当前 term 已投给谁
votedFor
这里“持久化”非常重要。否则节点重启后忘记自己投过票,就可能在同一 term 里重复投票。
4.4 候选人不是只靠“先发起”就能当选
如果只靠谁先发起选举,系统很容易选出一个日志明显落后的 leader。那就危险了,因为这个 leader 可能不包含某些已经接近提交、甚至已提交的历史。
所以 RequestVote 除了带 term,还要带上候选人的日志信息,通常是:
lastLogTermlastLogIndex
投票者只有在候选人的日志 至少和自己一样新 时,才会把票投给它。
这个“up-to-date check”是 Raft 的关键防线之一。它的意义可以概括成一句话:
不要把领导权交给一个历史明显更旧的人。
后面我们会看到,这和“已提交日志不丢失”直接相关。
5. 日志复制:Raft 真正的主体工作流
一旦选出了 leader,Raft 的主线就进入日志复制阶段。
5.1 客户端写入之后发生了什么
假设客户端向 leader 发出一个写请求,比如:
set user:42 = alice
leader 收到请求后,通常会这样做:
- 把命令作为一条新日志追加到本地 log
- 并发向 follower 发送
AppendEntries - 等待多数副本确认接收
- 满足提交条件后推进
commitIndex - 把日志应用到本地状态机
- 返回成功给客户端
注意这里返回成功发生在“多数确认之后”,而不是“刚写到 leader 本地之后”。
这是线性一致写语义的根本来源之一。
5.2 AppendEntries 不只是“追加”,还承担一致性校验
名字叫 AppendEntries,很容易让人误以为它只是个“发新日志”的 RPC。其实它还负责做日志对齐。
leader 在发送日志时,不会只说“请接收这些 entries”,还会说:
- 这些新 entries 之前,应该先有一条
prevLogIndex - 这条旧日志的 term 应该等于
prevLogTerm
follower 收到请求后,会先检查:
- 自己在
prevLogIndex上是否真的有日志 - 如果有,它的 term 是否与
prevLogTerm一致
只有这两个条件都成立,follower 才会接受后续 entries。
这一步是 Raft 日志一致性的核心。
因为它实际上在说:
不是单纯把新日志补上,而是要求 follower 先证明“我们对共同前缀的理解一致”。
5.3 为什么会出现日志冲突
在一个正常稳定的 term 里,leader 追加日志通常不会有冲突。冲突主要发生在 leader 切换之后。
一个典型场景是:
- 旧 leader 在自己 term 中写入了一些日志
- 这些日志只复制到少数节点,还没提交
- 旧 leader 宕机
- 新 leader 当选,它的日志历史和旧 leader 分叉了
这时,某些 follower 上可能保留着“旧 leader 的未提交尾巴”。
Raft 的处理方式是:
- 新 leader 用
prevLogIndex/prevLogTerm探测共同前缀 - 一旦发现 follower 在某个位置与自己不一致
- follower 删除冲突点之后的本地日志
- 然后接受 leader 发来的正确后缀
这意味着一个重要事实:
未提交日志是可能被覆盖的。
这听起来像“数据丢了”,但这里丢掉的是系统从未承诺成功的历史,因此是允许的。
真正不能被覆盖的,是已提交日志。
6. Commit 到底怎么判定:这是理解 Raft 安全性的核心关口
很多文章会说:“一条日志复制到多数节点就提交。”
这句话只对了一半,甚至在某些上下文里会误导人。
6.1 直观版本:多数复制意味着有交集
先说最直观的一层。
如果一条日志已经复制到多数节点,那么任何未来的多数集合都至少会和它有一个共同节点。因为两个多数集合在同一个固定节点集上不可能完全不相交。
这个多数交集性质,是 Raft 和 Paxos 这一类协议最底层的安全基础。
它保证了:
一旦某条历史已经进入一个多数,它就不可能在未来被整个系统“集体遗忘”。
6.2 但 Raft 还多了一条容易被忽视的限制
在 Raft 里,leader 不能仅仅因为“某个旧 term 的日志已经出现在多数节点上”,就立即认定它 committed。
Raft 论文中的规则更精细:
leader 只直接依据“当前 term 的日志已经复制到多数”来推进 commitIndex。
一旦当前 term 某条日志 committed,那么它之前的所有日志,借助日志前缀性质,也就间接 committed 了。
为什么需要这条限制?
因为如果允许 leader 直接根据“旧 term 某条日志当前看起来在多数上”来宣布提交,就会引入微妙风险:未来可能出现另一个更合格的 leader,它并不包含那条旧日志,而系统却曾错误地把它承诺给客户端。
这条规则的本质是:
Raft 不让 leader 轻易替过去的 term 做最终背书;它只对自己任期内、自己亲手推进到多数的日志做直接提交判断。
这比“多数复制就提交”要严谨得多。
6.3 这背后连接的是 Leader Completeness
Raft 有一个非常重要的安全性质:Leader Completeness。
它的意思是:
如果一条日志在某个 term 已经 committed,那么之后所有更高 term 的 leader 都一定包含这条日志。
这是整个协议最值得反复体会的性质之一。
因为客户端真正关心的不是“这条日志当前是不是在几台机器上”,而是:
- 系统以后会不会忘掉它
- 未来 leader 会不会缺少它
- 它是否真能成为集群历史的一部分
Raft 通过“投票时检查日志新旧”加上“只直接提交当前 term 日志”这两个机制,拼出了这个性质。
7. 为什么已提交日志不会丢:把几个关键规则连起来看
现在可以把前面的机制串起来了。
假设一条日志 E 已经 committed。为什么未来不可能被覆盖?
完整直觉大致是这样:
E已经进入某个多数副本集合- 未来任何 leader 都必须来自某个新的多数集合
- 两个多数集合必有交集
- 至少有一个投票者持有
E - 候选人想拿到它的票,日志必须至少和它一样新
- 因而新 leader 不能比包含
E的历史更旧 - 所以未来 leader 也必须包含
E
这里你会发现,Raft 的安全性不是某一条规则单独完成的,而是多条规则互相咬合:
- 多数交集
- 一任期一票
- 候选人日志新旧检查
- leader 只直接提交当前 term 日志
- follower 只接受与共同前缀一致的追加
这也是为什么学习 Raft 不能只背 RPC 流程图。
真正要学会的是:
每条规则在防哪一种故障路径。
8. Log Matching Property:为什么大家最终会收敛成同一条历史
Raft 还有一个基础性质,通常叫 Log Matching Property。可以简化表述成:
- 如果两个日志在相同 index 上有相同 term 的 entry
- 那么这两个日志在该位置之前的所有 entry 都相同
这个性质为什么成立?
因为 follower 接受日志不是盲收,而是要求 prevLogIndex 和 prevLogTerm 先匹配。换句话说,每次追加都像是在已有公共前缀后面接新内容。
一旦某个位置的 (index, term) 已对齐,前缀就已经被“锁定”了。
它的工程意义非常直接:
- leader 不需要把整个日志每次全量重发
- 它只要找到和 follower 的最大公共前缀
- 再把后缀修正过去即可
于是日志同步可以在“前缀匹配 + 后缀覆盖”的模型下工作。
这也是 Raft 能够既严谨又实用的原因之一。
9. Raft 不是“只要选出 leader 就完事”,读路径同样有讲究
很多教程主要讲写入路径,但现实系统里读请求通常远多于写请求。
这时候一个自然问题就来了:
leader 能不能直接用本地状态回答读请求?
答案是:不是无条件可以。
原因在于,某个节点“自认为是 leader”,不等于它此刻依然是集群公认的 leader。
一个典型风险场景:
- 原 leader 与多数派分区
- 多数派已经选出新 leader
- 原 leader 还没意识到自己过期
- 如果它继续直接回答线性一致读,就可能返回陈旧数据
所以要做线性一致读,leader 通常还需要额外确认自己的领导权没有过期。常见做法有两种:
- Read Index:在处理读前,先和多数副本确认一次自己仍是合法 leader
- Leader Lease:在有严格时钟假设和心跳约束时,用租约窗口优化读路径
这说明一件很重要的事:
Raft 的共识核心主要解决写顺序,但要把它做成真正的数据库或 KV 系统,还要认真处理读语义。
etcd 之类系统里,这部分工程细节同样非常关键。
10. 成员变更为什么麻烦:因为“多数”这个概念本身在变化
静态 3 节点或 5 节点集群里,多数很好定义。但如果你要扩容、缩容,问题就来了。
比如从 3 节点配置变成 5 节点配置:
- 旧配置的多数是 2
- 新配置的多数是 3
如果切换过程设计不好,可能出现一个非常危险的窗口:
- 某组节点按旧配置选出一个 leader
- 另一组节点按新配置又选出另一个 leader
也就是“两个配置、两个多数、两个 leader”的灾难。
Raft 为了解这个问题,提出了 joint consensus。
它的核心思想不是“一步切换”,而是“过渡态同时认可两套配置”:
- 先从旧配置
C_old进入联合配置C_old,new - 在联合配置中,决策需要同时满足旧配置多数和新配置多数
- 再从联合配置过渡到新配置
C_new
这个做法看起来更啰嗦,但非常必要。
本质上,它是在保证配置切换前后,多数集合仍然保持安全交叠,不会凭空裂成两套互不承认的合法世界观。
这类问题很能说明:
共识算法真正难的,不是正常写一条日志,而是系统模型本身发生变化时,如何保持过去那些证明依赖的结构仍然成立。
11. 日志不能无限增长:所以还要有快照与日志压缩
如果一个 Raft 集群运行足够久,log 一定会越来越长。
这带来两个现实问题:
- 磁盘空间会持续增长
- 新节点或严重落后的节点追日志会越来越慢
所以工程实现里必须支持 snapshot 和 log compaction。
11.1 快照在做什么
本质上,快照是在说:
某个 index 之前的日志,我已经不需要逐条重放了,因为它们的效果已经凝结成一个完整状态。
于是节点可以:
- 把状态机在某个
lastIncludedIndex的结果持久化成快照 - 记录对应的
lastIncludedTerm - 删除更早的日志前缀
以后如果有落后太多的 follower,leader 不再一点点补旧日志,而是直接发送快照,让它一口气追到某个较新状态。
11.2 为什么快照也要带 index 和 term
因为快照不是“另一个世界”,它仍然要和日志历史拼接起来。
lastIncludedIndex / lastIncludedTerm 的作用,是告诉系统:
- 这份快照已经包含到哪里为止
- 它和后续日志该如何衔接
否则 follower 恢复后,根本无法判断后面的日志是不是接在正确前缀之后。
所以你会发现,Raft 的很多设计都在反复强调同一件事:
历史边界必须可比较、可验证、可延续。
12. Raft 为什么“容易理解”,但并不“简单到没有坑”
Raft 经常被说成“比 Paxos 简单”。这句话最好理解成:
它更容易组织成工程师能跟住的叙述。
而不是说它没有深水区。
现实实现里,下面这些地方都很容易踩坑:
12.1 持久化边界
哪些状态必须在回复 RPC 前持久化?
典型包括:
currentTermvotedFor- 新追加的日志
如果时序搞错,例如先回成功、后落盘,节点崩溃恢复后就可能违反协议假设。
12.2 应用状态机与提交推进的时序
日志写入、提交、应用三者不是一回事。
实现里必须清楚区分:
matchIndexcommitIndexlastApplied
否则就容易出现重复 apply、乱序 apply 或对外可见状态超前的问题。
12.3 Follower 回退优化
最朴素的做法是 leader 发现 follower 不匹配,就把 nextIndex 一点点减一再重试。这样逻辑没错,但当 follower 落后很远时会非常慢。
实际实现常常会在拒绝响应里带更多冲突信息,帮助 leader 快速跳过整段不匹配区间。
12.4 Pre-Vote 与无谓 term 膨胀
有些实现会加入 Pre-Vote 机制。原因是某个网络不稳定节点如果频繁自增 term 发起正式选举,可能干扰一个本来稳定工作的 leader。
Pre-Vote 的思路是:
- 先不正式增加 term
- 试探自己是否有希望拿到多数
- 有机会再进入真正竞选
这不是 Raft 最初论文的核心部分,但在工程实践里很常见。
12.5 Read Index、Lease Read、Check Quorum
只读优化很容易做错。
如果系统对“自己还是 leader 吗”这件事确认不严谨,就可能返回陈旧读。很多成熟实现会配合 CheckQuorum、Read Index 或租约策略来保证线性一致性读。
所以别把“会选 leader + 会复制日志”当成 Raft 实现完成了。真正能上线的系统,难点往往恰恰在这些边角但致命的部分。
13. Raft 和 Paxos 的区别,应该怎么理解
这部分最好不要粗暴总结成“Raft 好,Paxos 不好”。更准确的说法是:
- Paxos 更早、更基础,很多后续共识协议都能在它的思想体系里理解
- Raft 更强调问题分解与工程可解释性
Raft 做了几件很有代表性的事:
- 明确区分 leader election、log replication、safety
- 使用强 leader 模型降低并发提案复杂度
- 用更贴近实现的状态机来叙述协议
- 直接把成员变更、快照等工程问题纳入主叙述
所以如果你问“工程里为什么很多系统更愿意讲 Raft”,答案通常不是因为它理论上压倒一切,而是:
它更适合作为一个可实现、可维护、可推演的系统设计框架。
这也是 etcd、consul、TiKV 等系统喜欢基于类似思路建设复制一致性模块的重要原因。
14. 常见误区:这些说法都不够准确
最后把几个常见误解集中澄清一下。
14.1 “只要多数节点存了这条日志,它就一定 committed”
不准确。
更严谨的说法是:
- 多数复制是必要基础
- 但 leader 直接推进 commit 时,还要遵守当前 term 提交规则
14.2 “Follower 上有的日志都不会丢”
不对。
未提交日志在 leader 切换后可能被覆盖。不会丢的是已提交历史,而不是所有曾经出现过的尾部日志。
14.3 “有 leader,所以读天然线性一致”
不对。
leader 还需要确认自己没有过期,才能安全回答线性一致读。
14.4 “Raft 解决了分布式数据库的一切一致性问题”
也不对。
Raft 主要解决的是:
- 单个复制组内的顺序一致与故障切换
- 状态机命令的线性一致提交
它不自动解决:
- 跨分片事务
- 全局二级索引一致性
- 长事务冲突控制
- 多 Raft Group 之间的调度和负载均衡
真正的数据库系统,还需要在 Raft 之上再搭很多层。
15. 学懂 Raft,真正该带走什么
如果只背流程,Raft 很快会又变成另一个“记住几个 RPC 名字”的协议。
真正该带走的,是下面这些结构化理解。
15.1 它不是在复制状态,而是在复制一个被多数认可的命令顺序
这决定了为什么日志是中心对象,而状态机只是日志的执行结果。
15.2 它把复杂度集中到了 leader 生命周期与日志历史管理上
这就是 strong leader 的意义。
15.3 它的安全性来自多条规则的组合,而不是单点魔法
你不能只拿“多数派”四个字解释一切。真正起作用的是:
- 多数交集
- 任期单调递增
- 一任期一票
- 候选人日志新旧检查
- 前缀匹配后再追加
- 当前 term 提交规则
15.4 它是工程协议,不只是纸上证明对象
成员变更、快照、只读优化、持久化边界、慢 follower 回退、领导权确认,这些都不是“补充阅读”,而是协议落地的主体部分。
16. 结语
Raft 最打动人的地方,不是它把共识问题变得轻飘飘,而是它在一个确实困难的问题上,给出了非常克制的结构化答案。
它没有试图让所有节点都平等地同时决定一切,而是老老实实承认:
- 顺序必须有人主导
- 主导者可能失效
- 失效后必须有可验证的交接规则
- 历史一旦被承诺,就必须进入未来所有合法领导者的记忆
从这个角度看,Raft 的核心并不是“leader 选举算法”,而是:
如何在不可靠环境里,给一条共享历史建立可靠继承关系。
一旦你抓住这一点,term、vote、append、commit、snapshot、joint consensus 这些看似分散的机制,就会慢慢拼成同一幅图。
如果后面继续展开,一个很自然的方向就是把 Raft 放到具体系统里去看,比如:
- etcd 是怎么用 Raft 维护元数据一致性的
- 多 Raft Group 存储系统如何做分片与调度
- 线性一致读和事务语义在数据库里如何继续往上搭建
那时候你会更清楚地看到:
Raft 不是分布式系统的终点,但它确实是理解现代一致性系统的一块核心地基。