分布式一致性算法
这篇主要梳理分布式一致性领域几篇经典论文。它们回答的是同一类问题：当节点会宕机、网络会延迟甚至丢包时，系统怎样对“某个值”或“某个日志顺序”达成一致。
可以先建立一个总脉络：
- 事务提交问题关注的是“这次事务到底提交还是回滚”
- 共识问题关注的是“多个副本最终到底认同哪个值”
- 状态机复制则是在共识之上更进一步，要求大家对同一串日志顺序达成一致
- 理论上有 FLP 不可能性约束，工程上则依赖超时、领导者、重试和部分同步假设来实现可用系统
A Brief History of Consensus, 2PC and Transaction Commit
分布式事务的发展。
这篇文章适合拿来建立背景：一致性问题最早不是直接以 Paxos、Raft 的形式出现，而是从数据库事务提交、主备复制和故障恢复这些工程问题里逐渐抽象出来的。
2PC（Two-Phase Commit，两阶段提交）的目标是让多个参与者对一笔事务的提交结果保持一致：
- prepare 阶段：协调者询问所有参与者是否可以提交
- commit 阶段：如果所有参与者都返回可以提交，则广播 commit，否则广播 abort
2PC 的问题在于阻塞：
- 协调者一旦在关键时刻宕机，参与者可能长时间卡在“不知道该提交还是回滚”的状态
- 它解决的是原子提交问题，不是通用意义上的分布式共识
- 2PC 默认更偏向数据库事务语义，不擅长处理长期网络分区和副本领导者切换
后续 3PC、Paxos Commit 等工作，本质上都是在尝试降低阻塞和单点协调者故障带来的风险。
可以把它和共识算法的区别理解为：
- 2PC：让大家对“某次事务是否提交”达成一致
- 共识算法：让大家对“某个提议值”达成一致
- 复制状态机：让大家对“一串操作日志”达成一致
Paxos Made Simple
由于 Paxos 初版论文过于晦涩难懂，这篇相当于 Lamport 亲自给 Paxos 写的简化版说明。
Paxos试图解决的问题是：在一组会出现故障的进程中，选择出一个被多数派接受的值，并保证这个值一旦被选定就不会再被另一个不同的值推翻。
Paxos 中通常有三类角色：
- Proposer：提出提案
- Acceptor：投票并接受提案
- Learner：学习最终被选中的值
核心流程分为两个阶段：
- Prepare/Promise
- Proposer 发送编号为 n 的 prepare 请求
- Acceptor 如果还没承诺过更大的编号，就承诺不再接受小于 n 的提案
- 同时返回自己已经接受过的最大编号提案
- Accept/Accepted
- 如果 proposer 收到多数派 promise，就可以发 accept 请求
- 若返回的历史提案中已经有人接受过某个值，那么 proposer 必须沿用编号最大的那个旧值
- Acceptor 若未承诺过更大的编号，就接受该提案
Paxos 最关键的安全性思想是：
- 编号大的提案会继承编号小但已被多数接受的值
- 多数派集合彼此相交，因此一旦某个值被选中，后续提案无法再合法地选出别的值
难点也很明显：
- 论文定义抽象、角色拆分多，初学时不容易建立整体图景
- Basic Paxos 一次只决定一个值，如果直接用来复制日志，成本很高
- 活性依赖于“最终只剩一个稳定 proposer”这类工程条件
Paxos Made Practical
Paxos 如何映射到工程上。
理论版 Paxos 只告诉你“如何保证安全”，但工程系统还需要解决很多现实问题：
- 日志如何持久化
- Leader 如何选举
- 客户端请求如何重试
- 节点恢复后如何追日志
- 多条日志如何连续提交
把 Paxos 真正落到工程里，通常会演化出下面这些设计：
- 引入稳定 Leader，减少多个 proposer 竞争
- 将“一次共识一个值”扩展成“对一系列日志槽位逐个达成共识”
- 把 acceptor 的承诺和已接受值持久化到磁盘，防止重启后破坏安全性
- 用批量提交、流水线和日志截断降低性能开销
这类工作说明了一件事：Paxos 不是不能工程化，而是它的论文形式和工程实现之间存在很长的一段距离。
Paxos Made Live
讲述 Multi-Paxos。
这篇是 Google Chubby 团队非常经典的工程复盘。它最重要的价值，不是重新证明 Paxos 正确，而是告诉你：把一个“理论上正确”的算法做成可维护的工业系统，真正困难的部分在哪里。
Multi-Paxos 的核心思想是：
- Basic Paxos 每个日志槽位都要走完整 prepare + accept
- 一旦选出稳定 Leader，后续大多数日志项可以跳过重复 prepare
- 这样就把两轮消息降低为近似一轮，从而显著提升吞吐与延迟表现
文章里能看到很多现实问题：
- 代码复杂度远高于论文描述
- 故障往往不是单一节点宕机，而是磁盘损坏、时钟漂移、运维误操作、网络抖动
- 正确性不只是算法正确，还包括实现正确、测试充分、监控完善
它的一个重要工程结论是：
- 一致性系统的难点，往往不是“想出算法”
- 而是“让算法在真实世界里长期稳定运行”
Raft: In Search of An Understandable Consensus Algorithm
Raft 协议，etcd、Consul 等系统广泛采用；Nacos 在 CP 模式下也使用 Raft 思路。
Raft 的目标非常明确：在不牺牲安全性的前提下，把共识算法设计得更容易理解和实现。
Raft 将问题拆成三个相对清晰的子问题：
- Leader election：领导者选举
- Log replication：日志复制
- Safety：安全性保证
Raft 中节点有三种状态：
- Follower
- Candidate
- Leader
基本过程如下：
- 正常情况下由 Leader 接收客户端写请求
- Leader 把日志复制给 Followers
- 当某条日志被多数节点持久化后，就认为该日志 committed
- Leader 再通知 followers 应用到状态机
Raft 相比 Paxos 更易懂，主要体现在：
- 强 Leader 模型更直观，日志流向基本单向
- 把日志一致性约束写成了更容易验证的规则
- 借助 term、index、commitIndex 这些概念，把状态变化描述得很明确
Raft 中几个非常关键的点：
- 选举限制：候选人的日志必须“足够新”，否则不能当选
- 日志匹配性质：如果两个日志在同一个 index、term 上相同，那么此前日志一定相同
- Leader Completeness：已提交日志一定会出现在未来 Leader 的日志中
Raft 的代价是：
- 对强 Leader 依赖更重
- 某些成员变更场景处理复杂，因此引入了 Joint Consensus
- 理论表达更友好，但实现上依旧不能掉以轻心
如果把 Raft 当成一句话记忆，就是：
- 用“领导者驱动的日志复制”来实现可理解的状态机复制
Zookeeper: Wait-Free Coordination for Internet-Scale Systems
ZooKeeper 本身不是一个通用数据库，而是一个分布式协调服务。
它提供的是一套非常适合上层系统构建协调逻辑的抽象：
- 配置管理
- 命名服务
- 分布式锁
- Leader 选举
- Group Membership
ZooKeeper 的数据模型很像文件系统：
- 以 znode 组织成树形结构
- 支持临时节点、顺序节点
- 支持 watch 机制，客户端可以订阅节点变化
它背后的核心协议是 ZAB（ZooKeeper Atomic Broadcast），可以理解为一种偏原子广播/主从复制风格的一致性协议，目标是保证：
- 所有事务请求按全局顺序广播
- 已提交事务不会丢失
- Leader 崩溃恢复后，集群还能继续对外提供一致视图
ZooKeeper 的设计特点是：
- 读多写少场景表现好
- 强调顺序一致性和协调能力，而不是大规模通用数据存储
- 客户端通常通过“临时顺序节点 + watch”组合实现锁、选主、注册发现等功能
它对工程实践的影响非常大，很多中间件早期都把 ZooKeeper 作为外部协调中心。
Using Paxos to Build A Scalable, Consistent, and Highly Available Datastore
这篇可以和 Google Megastore 联系起来看：作者讨论了如何用 Paxos 构建一个可扩展、强一致、高可用的数据存储系统。
核心思想是：
- 不是把整个数据库放进一个 Paxos 组
- 而是按数据分片、实体组或日志段拆分成多个独立的复制单元
- 每个复制单元内部通过 Paxos 保证一致性
这种设计的好处是：
- 一致性边界清晰
- 故障影响范围有限
- 可以把全局系统拆成许多局部共识实例，提高可扩展性
它也揭示了强一致存储系统的一些现实代价：
- 跨分区事务变复杂
- 写入延迟受多数派确认影响
- 地理多活场景下，跨机房 RTT 直接影响提交时延
很多后来的分布式数据库都沿着这个方向演进：
- 局部强一致
- 全局按分片扩展
- 通过日志复制和故障转移保证高可用
Impossibility of Distributed Consensus With One Faulty Process
FLP 定理：在完全异步模型中，只要允许哪怕一个进程发生故障，就不存在一个确定性算法，能够保证分布式共识同时满足安全和活性。
这里最容易误解的一点是，FLP 不是说“共识做不到”，而是说：
- 在最强的异步假设下
- 对任意执行过程
- 不可能总能保证最终做出决定
FLP 前提是完全异步系统：
- 没有全局时钟
- 消息传递延迟可以任意大
- 进程执行速度任意，但不会停顿
因此在这种模型里，你无法区分：
- 对方是真的宕机了
- 还是只是网络太慢、消息还没到
这就是分布式系统里“故障检测不可靠”的根源。
FLP 的工程启示非常重要：
- 超时不是数学上准确的故障判断，只是工程上的猜测
- 共识算法通常通过随机化、领导者选举、失败重试来争取活性
- 实际系统都会引入“部分同步”假设，而不是工作在纯异步模型里
Consensus in the Presence of Partial Synchrony
这篇论文的重要意义在于：它给出了介于“完全同步”和“完全异步”之间的模型，也就是部分同步模型。
部分同步的直觉是：
- 系统大多数时候也许很混乱
- 但在某个未知时刻之后，消息延迟和处理时间会收敛到某个上界之内
这比完全同步更现实，也比完全异步更可做工程。
很多现代共识算法实际上都建立在这个前提上：
- 平时允许网络抖动、重试、误判
- 只要系统最终进入一段“足够稳定”的时期
- 领导者选举和日志复制就能继续推进，系统恢复活性
这和 FLP 并不矛盾：
- FLP 讨论的是完全异步模型下的绝对不可能性
- 部分同步则是在更贴近现实的假设下重新获得可实现性
所以实际工程可以总结为：
- 安全性通常要求在任何时候都不能破坏
- 活性则依赖额外条件，例如多数派存活、网络最终稳定、选举超时参数合理
总结
这一组论文基本串起了分布式一致性的发展路线：
- 从 2PC 这样的事务提交协议出发，逐渐走向通用共识
- Paxos 给出了经典的多数派共识框架
- Multi-Paxos 解决了连续日志复制的效率问题
- Raft 进一步强调可理解性和工程可实现性
- ZooKeeper / ZAB 则展示了协调服务如何把一致性能力封装成基础设施
- FLP 与部分同步理论解释了为什么这些系统必须依赖超时、选主和现实世界中的“最终稳定”