RaftReplicated-state consensus
通过任期、领导者和日志复制维护一致的状态机。
- 核心约束
- 提交与应用必须遵守协议的任期、日志及多数派约束。
- 适用问题
- 管理平面一致性与复制状态。
- 边界与取舍
- 失去多数派时无法正常提交新操作。
常见操作#
p 为投票节点数，b 为本次新日志字节数；下面指稳定 leader 下无故障的一次复制。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 复制新日志 | 通常 消息与 网络数据 | 不含重传、快照和批次内条目摊分；leader 可并行发送给各 follower。 |
| 提交日志 | 多数派复制与必要持久化的时延 | 提交当前任期日志需遵循 Raft 的多数派和任期规则，不是到达任一副本就完成。 |
| 选举 / 落后副本追赶 | 超时、重试和缺失日志决定 | 网络分区时不保证有限时间内继续提交。 |
时间与空间#
- 时间复杂度
- 正常复制的消息量随 p 增长；提交时延依赖多数派
- 辅助空间
- 每节点持久日志 / 快照；leader 另存 复制进度
多数派是容错与提交条件。压缩日志、线性一致读和成员变更各有额外协议，不可由单条消息复杂度推断。
工程中的应用#
1 个案例 · 附源码SwarmKit 的管理节点通过 Raft 复制状态，leader 负责将更新提案纳入一致日志。
附源码片段 · 通信与流量
基础原理参考资料
Ongaro & Ousterhout · Raft, extended version第 5 节日志复制与安全性、第 6 节成员变更、第 7 节日志压缩。