Raft
Raft 是一种共识算法,让多个节点对日志顺序达成一致,再按这个顺序执行命令、更新状态。理解 Raft 的重点是:Leader 故障以后,新 Leader 为什么还能保留已提交的结果,以及读请求凭什么相信当前节点没有过期。
1. 面试核心
先记住这几条,再读正文- 每个节点在一个任期内最多投给一个候选者,当前任期和投票记录必须持久化,重启后也要遵守。
- 比较候选者日志新旧时,先比较最后条目的任期,再比较位置,不能只看日志长短。卡 · 角色与任期
- Leader 只能按多数副本数直接提交当前任期的条目,此前的旧任期条目随这段日志前缀一起提交。卡 · 当前任期与旧任期条目
- 线性一致读既要确认当前领导权,也要等待本地状态机应用到安全读取位置。卡 · 读取屏障
- 联合配置同时要求新旧配置的多数;新节点作为 learner 追赶时,不参与投票,也不提高多数门槛。卡 · Learner 与多数门槛
2. 角色与任期
Raft 节点有三种角色。Follower(跟随者)响应日志复制和投票请求;Candidate(候选者)发起选举、请求其他节点投票;Leader(领导者)接收命令、复制日志并发送心跳。
任期(term)是单调递增的编号,用来区分不同轮次的选举。节点看到更大的任期,就更新自己的记录并退回 Follower。同一个任期内,每个节点最多投给一个候选者。两个多数派必然相交,这条投票限制就能阻止两个候选者在同一任期各自获胜。
2.1 持久状态与故障模型
当前任期 currentTerm、投票记录 votedFor 和日志,都要在回复相关远程调用(RPC)之前持久化。否则,节点重启后可能忘记自己投过票,在同一任期再次投票;副本如果确认后又丢失日志,也会破坏后续恢复的前提。
Raft 处理崩溃、重启、延迟、丢包和分区,但假设节点遵守协议。伪造投票、发送相互矛盾的日志等不按协议执行的行为属于拜占庭故障,超出普通 Raft 的保证。
固定配置下,2f+1 个投票节点可以容忍 f 个不可用,因为还剩 f+1 个节点,足以形成多数。继续推进也要求这些节点能够互通,通信条件足够稳定,能完成选举和复制。
3. 领导者选举
Follower 在选举超时后增加任期,转为 Candidate,先给自己投票,再向其他节点请求选票。取得多数票后,它成为 Leader。各节点采用随机超时,减少同时开始竞选、分散选票的机会。
投票节点还会检查候选者的日志是否至少与自己一样新。比较时先看最后一条日志的任期,任期相同再看位置 index。因此,日志较短但最后条目任期更大的候选者,仍然算更新。这个限制与提交规则一起保护已经提交的日志。
选举超时应明显长于正常通信耗时。延迟持续过大时,频繁竞选会降低可用性。安全规则仍需保持。
4. 日志复制
Leader 通过 AppendEntries 请求复制日志。每个条目包含位置 index、任期 term 和命令;请求还携带前一个条目的位置与任期,让 Follower 检查新条目能否接在自己的日志后面。
前一个条目不匹配时,Follower 拒绝请求,Leader 回退下一次发送的位置 nextIndex,继续寻找共同前缀。找到后,如果新条目与本地相同位置的条目任期冲突,Follower 删除冲突条目及其后缀,再接上 Leader 的日志,已经匹配的部分保留。
这维持了日志匹配性质:两个日志在相同位置有相同任期的条目时,该条目及之前的前缀也相同。
5. 提交
提交表示日志已经满足协议的安全条件,可以交给状态机执行。Leader 跟踪各副本持久化到了哪里,当前任期的条目复制到多数后,就可以推进提交位置 commitIndex,按日志顺序执行命令,再返回结果。
Follower 根据 Leader 通知的提交位置推进本地提交。这里要分清两个进度:commitIndex 是已知可以应用到的位置,lastApplied 是实际上已经应用到的位置。日志提交了,本地状态也可能还没更新完。
5.1 当前任期与旧任期条目
尚未提交的旧任期条目,即使已经复制到多数,也不能只凭副本数直接提交。原因在于选举先比较最后条目的任期:另一个候选者可能拥有任期更高、内容不同的后缀,仍能通过日志新旧检查,赢得后续选举。
Leader 要先让一条当前任期的条目取得多数。它可以是业务命令,也可以是不改变业务状态的空操作(no-op)。这条日志提交后,之前的日志前缀才随之提交。
安全性来自选举限制、日志匹配和当前任期提交规则的配合。多数集合相交只说明有共同节点,不代表这个节点必然拒绝另一个候选者;它仍会按日志新旧规则投票。
6. 客户端重试
Raft 保证日志顺序,不会自动识别两条命令其实是同一次业务请求。命令已经提交但响应丢失时,客户端重试,可能产生第二条日志;状态机直接执行它,就会重复修改数据。
为此,状态机可以保存客户端 ID、请求序号和执行结果,识别重复请求后返回原结果。发送邮件、调用外部 HTTP 接口等操作还需独立保证幂等,具体恢复见分布式流程恢复。
7. 线性一致读
Leader 读取自己的本地状态,也可能读到过期结果。它失联后,其他节点可以选出新 Leader 并完成写入;旧 Leader 尚未收到更高任期的消息,仍会认为自己有效。因此,线性一致读必须确认本次读取的依据。
7.1 读取屏障
读取屏障用来确定本次读取至少应看到哪些已提交的变化。新 Leader 先提交当前任期的条目,确认此前已提交的前缀;论文采用任期开始时提交 no-op 的做法。
接着还要确认当前领导权。ReadIndex 类流程通过与多数派交互取得安全读取位置,本地再等待 lastApplied 到达这个位置,才读取状态。前一步防止过期 Leader 提供结果,后一步防止读取尚未应用完的状态。
Follower 也可以向 Leader 获取安全位置,等本地应用到该位置后读取。只检查自己的任期或历史 commitIndex,缺少本次请求所需的确认。
租约读可减少往返,但安全性依赖时钟与租约假设。
8. 快照
快照保存已经应用的状态,以及最后包含条目的 index 和 term,用来代替压缩掉的日志前缀。Follower 落后太多、所需的旧日志已经被压缩时,就先安装快照,再复制后续日志。
快照还需包含生效的成员配置。状态与位置应一致且可持久恢复。共识副本之外的历史备份仍用于逻辑损坏恢复。
9. 成员变更
直接把旧成员列表换成新列表,可能让新旧配置各自形成互不相交的多数,破坏原有安全条件。联合共识(joint consensus)在过渡期要求同时取得新旧两套配置的多数,再提交最终的新配置。
部分实现采用经过证明的单成员变更协议。它与联合配置是不同实现路径,应按具体协议操作。
9.1 Learner 与多数门槛
新增投票节点可能提高多数门槛,不一定立即增加容错余量。三节点需要两票,四节点需要三票。如果原来已有一个节点故障,新加入的投票节点又尚未就绪,就只有两票可用,达不到新的门槛。
Learner 是接收日志但暂不投票的成员。etcd 3.6 支持让新节点以 learner 身份加入,追赶期间不提高多数门槛;追平并通过提升检查后,再转为投票成员。
成员变更通过现有共识完成。丢失多数后,普通加节点操作无法恢复法定票数。
10. 常见问题
10.1 三节点集群故障两台后,还能继续写吗?
不能按正常共识流程继续提交写入,因为剩余一台达不到两票的多数门槛。坚持这个限制,才能避免不同分区各自提交冲突结果。如果接口明确允许陈旧读,可以另行提供这类读取服务。
10.2 没有新日志的心跳,也要遵守复制规则吗?
要。论文中的心跳是没有新条目的 AppendEntries,仍携带任期、前缀和提交信息,不能因条目为空就跳过必要检查。具体实现可以优化消息格式,但要保留相应安全条件。
10.3 两个节点都自认为是 Leader,会不会提交冲突结果?
不同任期的节点可以暂时都自认为是 Leader,但在正常协议和持久化假设下,不能因此各自提交互相冲突的日志。例如旧 Leader 被隔离后,其余多数节点选出了更高任期的新 Leader;旧节点尚未收到消息,角色记录仍可能是 Leader,但缺少多数确认,不能继续提交新的命令,也不能仅凭本地状态提供线性一致读。
旧 Leader 恢复通信并得知更高任期后退回 Follower,按新 Leader 的日志修复未提交的冲突后缀。已经提交的日志由选举与提交规则保护,不是恢复时任意选择一个节点的内容覆盖其他副本。
10.4 Raft 与 Paxos 怎样比较,优化要保留哪些条件?
比较时先对齐问题范围:Basic Paxos 为一个值达成共识,Multi-Paxos 把共识用于连续的日志;Raft 则直接围绕复制日志划分选举、复制和安全规则。不能把“Paxos 没有 Leader”或“Raft 一定更快”作为所有实现的结论,Multi-Paxos 的稳定领导者也可以协调连续提案。
Raft 的明确角色和日志前缀规则便于推演故障恢复,代价是写入通常经过 Leader,多数确认、持久化和网络延迟限制吞吐与响应时间;失去多数时也不能继续正常提交。增加副本可以提高相应的故障余量,同时增加复制工作,不等于单个共识组能按节点数线性提升写吞吐。
优化可以从批量复制、并行向各副本发送、流水线与快照追赶入手。批量减少每条命令的固定开销,却可能增加等待攒批的延迟;流水线允许多个复制请求在途,仍要正确跟踪每个副本实际确认的进度。无论怎样优化,都不能提前确认尚未持久化的数据、绕过多数提交,或让旧 Leader 跳过读取屏障。跨多个共识组分片还会引入跨组操作的协调问题,需要另行说明。
11. 面试题卡片
12. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明