Raft算法

概述

Raft算法是2014年由Diego Ongaro和John Ousterhout提出的分布式共识算法，明确以"可理解性"为首要设计目标，是Paxos算法的替代方案。Raft在理论能力上与Multi-Paxos等价，但通过更好的分解和简化大幅降低了理解和实现的难度。

关键内容

1. 设计理念：
2. 以可理解性为首要目标
3. 将共识问题分解为更简单的子问题

4. 提供清晰的协议描述和实现指导

5. 核心特性：

6. 强Leader：所有写请求必须经过Leader，简化了推理
7. 日志连续性：不允许日志中出现空洞，简化了恢复逻辑
8. 明确的Leader选举：使用随机超时机制，规则清晰

9. 成员变更的联合共识：提供了详细的配置变更方案

10. 与Paxos的对比：

11. 在理论能力上与Multi-Paxos等价
12. 通过更好的表述方式降低了工程实现的复杂性

13. 成为现代分布式系统中更常用的共识算法

14. 组成部分：

15. Leader选举：当现有Leader失效时选举新Leader
16. 日志复制：将日志条目从Leader复制到所有节点

17. 安全性：保证状态机安全的属性

18. 实际应用：

19. 被广泛应用于现代分布式系统
20. etcd使用Raft算法，支撑Kubernetes集群
21. 成为云原生基础设施的重要组成部分

来源

• 18-lamport-paxos — 详细比较了Raft与Paxos的关系
• Paxos算法 — 相关算法

相关

• Paxos算法 — predecessor
• 分布式共识 — solves
• 状态机复制 — implements
• Diego Ongaro — authored
• John Ousterhout — authored
• Multi-Paxos — relates_to