1985年，三位研究者Fischer、Lynch和Paterson发表了一篇论文，证明了一个令人沮丧的结论：在异步分布式系统中，即使只有一个进程可能崩溃，也不存在确定性的共识算法。这个被称为FLP不可能性定理的结果，并没有让分布式系统的发展停滞——相反，它催生了一系列优雅的工程解决方案。

今天，当你每次在Kubernetes上部署应用、在etcd中存储配置、或在TiDB中执行事务时，都在使用这些解决方案。它们的核心，是两个名字：Paxos和Raft。

共识问题：一个看似简单的定义

共识问题的定义出奇地简单：让一组节点就某个值达成一致。但这个简单背后隐藏着深刻的复杂性。

形式化地说，共识算法必须满足三个性质：

一致性（Safety）：所有正确节点最终决定相同的值。

有效性（Validity）：被决定的值必须由某个节点提出。

可终止性（Liveness）：所有正确节点最终都会做出决定。

问题在于，FLP不可能性定理告诉我们：在完全异步的网络模型下（没有时钟同步、消息延迟无上限），这三个性质不可能同时满足。更具体地说，不存在一个确定性算法能在至多一个节点崩溃的情况下保证一致性和可终止性。

这不是工程能力的问题，而是数学上的不可能。

绕过不可能性的三种路径

工程实践的智慧在于，既然无法在所有情况下都保证完美，那就退而求其次：

引入时机假设：假设网络延迟有界，或使用超时机制。这是大多数实际系统采用的方法。

随机化：引入随机性打破确定性约束，如Ben-Or算法。概率上可以无限接近完美，但理论上不保证。

弱化问题：接受部分节点可能永远无法达成一致，或允许在特定条件下违反一致性。

Paxos和Raft都选择了第一种路径——它们不声称在所有异步场景下都能工作，而是在"足够同步"的网络中保证正确性。这意味着：如果网络分区持续足够长时间，系统可能会停止处理请求，但绝不会做出错误的决定。

Paxos：简洁但令人困惑的优雅

Leslie Lamport在1989年提交了Paxos算法，但直到1998年才正式发表。论文以一个虚构的希腊岛屿Paxos的议会制度为背景，这种文学化的表达让很多人摸不着头脑。2001年，Lamport发表了"Paxos Made Simple"，用朴素的英语重新解释了这个算法。

三个角色的协议

Paxos定义了三种角色：

Proposer（提议者）：提出值的候选方案。

Acceptor（接受者）：对提议进行投票。

Learner（学习者）：获知被选定的值。

一个节点可以同时扮演多个角色。

两阶段协议的精妙之处

Paxos的核心是一个两阶段协议：

阶段一：Prepare/Promise

Proposer选择一个提案编号n，向大多数Acceptor发送Prepare(n)请求。Acceptor收到后，如果n大于它之前响应过的任何提案编号，就承诺不再接受任何编号小于n的提案，并返回它之前接受过的最大编号的提案（如果有）。

阶段二：Accept/Accepted

如果Proposer收到了大多数Acceptor的响应，它就可以发送Accept请求，包含提案编号n和值v。值v的选择规则是：如果响应中包含任何已接受的提案，v必须是其中编号最大的那个提案的值；否则，Proposer可以自由选择任何值。

这个设计的精妙之处在于提案编号的全序性。由于任何两个多数派集合必然有交集，一个提案一旦被多数派接受，后续任何更高编号的提案都必须选择相同的值——这保证了共识的一致性。

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    
    Note over P: 阶段一：Prepare
    P->>A1: Prepare(n=1)
    P->>A2: Prepare(n=1)
    P->>A3: Prepare(n=1)
    A1-->>P: Promise(无已接受提案)
    A2-->>P: Promise(无已接受提案)
    Note over P: 收到多数派响应
    
    Note over P: 阶段二：Accept
    P->>A1: Accept(n=1, v="X")
    P->>A2: Accept(n=1, v="X")
    P->>A3: Accept(n=1, v="X")
    A1-->>P: Accepted
    A2-->>P: Accepted
    Note over P: 值"X"被选定

Multi-Paxos：从单值到日志

原始Paxos只解决单个值的共识。实际系统中需要就一系列值达成共识——这需要运行多个Paxos实例。

关键优化：如果同一个Proposer持续提案，可以跳过阶段一。因为该Proposer已经知道之前的提案历史，可以直接进入阶段二。这就是所谓的"领导者"优化，也是Multi-Paxos高效运行的关键。

Raft：可理解性作为设计目标

2014年，Diego Ongaro和John Ousterhout发表了Raft论文，副标题是"In Search of an Understandable Consensus Algorithm"。这直接点明了Raft的设计哲学：可理解性不是事后考虑，而是核心目标。

三大子问题的分解

Raft将共识问题分解为三个相对独立的子问题：

领导者选举：当现有领导者失效时，选出一个新领导者。

日志复制：领导者接收客户端请求，将日志条目复制到其他服务器。

安全性：确保状态机以相同的顺序执行相同的命令。

这种分解让开发者可以逐个理解每个部分，而不是被整体复杂性压倒。

Term：逻辑时钟的实现

Raft将时间划分为任意长度的任期（Term），每个任期开始于一次选举。Term编号单调递增，作为逻辑时钟帮助服务器检测过时信息。

当服务器收到更高Term的消息时，会立即更新自己的Term并转换为Follower状态。这保证了系统中不会有两个不同Term的领导者同时存在。

领导者选举：随机化的妙用

当Follower在选举超时时间内没有收到领导者的心跳，就会转为Candidate状态，增加当前Term，向其他服务器请求投票。

Raft使用随机化选举超时（如150-300ms）来解决投票分裂问题。如果多个Candidate同时发起选举，得票可能分散，导致无人胜出。随机超时让某个Candidate更早发起下一轮选举，从而打破僵局。

更关键的限制是：只有日志最新的服务器才能成为领导者。Candidate在请求投票时会携带自己日志的最新索引和Term，投票者会拒绝那些日志不如自己新的Candidate。这保证了新领导者一定包含所有已提交的日志条目。

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 选举超时
    Candidate --> Leader: 获得多数票
    Candidate --> Follower: 收到更高Term
    Candidate --> Candidate: 选举超时（新Term）
    Candidate --> Follower: 发现新领导者
    Leader --> Follower: 收到更高Term
    
    note right of Follower: 响应领导者和Candidate
    note right of Candidate: 发起选举
    note right of Leader: 处理所有客户端请求

日志复制：强领导者的代价

Raft采用"强领导者"模型：所有日志条目都从领导者流向Follower。这简化了日志管理，但也带来了代价——所有写请求必须经过领导者。

当领导者收到客户端请求时：

  1. 将命令追加到自己的日志
  2. 并行向所有Follower发送AppendEntries RPC
  3. 当多数派确认后，提交该条目并应用到状态机
  4. 通知客户端成功

关键的安全性保证来自Raft的日志匹配性质：如果两个日志在某个索引位置有相同的Term编号，那么该位置的所有之前条目都相同。这通过AppendEntries的一致性检查实现——请求中包含前一条日志的索引和Term，Follower如果不匹配就拒绝接受。

为什么Raft更"容易理解"？

Heidi Howard在2020年的论文"Paxos vs Raft: Have we reached consensus on distributed consensus?“中给出了深刻分析：

“我们推测，Raft的可理解性很大程度上来自于论文的清晰表述，而非底层算法本身的本质差异。”

两者核心区别仅在于领导者选举：Raft要求领导者必须包含最新日志，Paxos允许任何服务器成为领导者，但需要额外步骤更新其日志。

换言之，Raft并非"更简单”，而是"更好地解释了复杂"。

ZAB与Viewstamped Replication：被遗忘的先驱

在Paxos和Raft的讨论中，经常被忽略的是ZAB（Zookeeper Atomic Broadcast）和Viewstamped Replication（VR）。它们不仅早于Raft，而且被广泛使用。

Viewstamped Replication：比Paxos更早

1988年，Brian Oki和Barbara Liskov提出了Viewstamped Replication，比Lamport的Paxos论文早了十年。VR同样使用领导者（称为主节点）和视图切换机制，与Raft的相似度极高。

VR的核心是视图（View）概念，等同于Raft的Term。当主节点故障时，通过视图切换选举新主节点，新主节点需要从其他副本获取缺失的日志条目。

Raft论文承认VR是其主要灵感来源之一，但Raft在可理解性和工程实践上做了大量改进。

ZAB：为Zookeeper定制

ZAB是Zookeeper的专用共识协议，设计目标是支持主备系统的高可用性。与Paxos/Raft的通用定位不同，ZAB从一开始就是为Zookeeper的协调服务设计的。

ZAB的核心概念是 epoch（等同于Term/View），同样通过领导者协调所有写操作。ZAB将协议分为两个阶段：恢复阶段（选举领导者和同步状态）和广播阶段（处理客户端请求）。

ZAB与Raft的主要区别：

特性 ZAB Raft
设计目标 专用协调服务 通用共识
领导者选举 允许日志落后节点当选 只有最新日志节点可当选
日志同步 选举后主动同步 被动同步（通过AppendEntries拒绝）
客户端请求 必须发给领导者 可发给Follower（转发给领导者）

这三种协议本质上殊途同归：都是基于领导者的日志复制协议，差异主要在于实现细节和工程权衡。

线性一致性：共识算法交付的承诺

共识算法解决了"达成一致"的问题，但"一致"意味着什么？

一致性模型的层级

线性一致性（Linearizability）：最强的单对象一致性保证。每个操作看起来都在某个时间点瞬间完成，且所有操作形成一个全序，与实时时间一致。读取操作一定返回最近的写入值。

顺序一致性（Sequential Consistency）：所有操作形成一个全序，但不必与实时时间一致。只需保证每个进程内部的操作顺序被保持。

因果一致性（Causal Consistency）：只有因果相关的操作需要被所有进程以相同顺序看到。

Raft和Paxos保证的是线性一致性：一旦某个日志条目被提交，任何后续读取都能看到该条目（假设读取也经过共识）。

只读查询的复杂性

读取操作是否需要经过共识？这是一个性能与一致性的权衡。

方案一：读写都经过共识

每次读取都作为日志条目提交。最安全，但延迟最高。

方案二：领导者直接读取

领导者知道最新的提交索引，可以直接响应读取。但存在风险：领导者可能已经"假死"——它认为自己还是领导者，但其他节点已经选出了新领导者。

方案三：ReadIndex优化

领导者先向多数派发送心跳确认自己仍是领导者，然后等待状态机执行到最新提交索引，再响应读取。etcd使用这种方式。

方案四：Lease Read

领导者通过租约机制，在租约有效期内可以直接响应读取。租约通过心跳续期，如果领导者故障，租约到期后新领导者才能当选。这是最高效的方案，但依赖时钟假设。

生产环境的挑战：理论到实践的距离

共识算法的正确性证明是在理想化模型下进行的，实际部署会遇到各种边缘情况。

网络分区：脑裂与可用性

当网络分区发生时，系统必须在一致性和可用性之间选择。CAP定理的形式化表述是：在分区存在时，系统不可能同时保证一致性和可用性。

Raft的选择是优先一致性（CP）：如果领导者被隔离在少数派分区，它无法获得多数派确认，写请求会失败。少数派分区无法选举新领导者。多数派分区可以选举新领导者继续服务。

这导致一个微妙问题：被隔离的旧领导者可能还认为自己是领导者，直到它尝试联系其他节点或收到更高Term的消息。在此期间，客户端可能向它发送请求并超时。

etcd的数据不一致事故

2022年，Kubernetes社区报告了etcd数据不一致问题。根本原因是：在特定故障模式下，etcd的Raft实现在应用日志到状态机时可能失败，但日志条目已被标记为已提交。

这揭示了共识理论与实践的鸿沟：理论保证日志的一致性，但日志到状态机的应用过程仍可能出错。数据完整性不仅需要共识算法，还需要状态机级别的原子性保证。

性能瓶颈：领导者是单点

Raft的强领导者模型简化了设计，但也带来了性能瓶颈：所有写请求都必须经过领导者。在高吞吐场景下，领导者成为系统的瓶颈。

几种缓解策略：

批量提交：将多个客户端请求打包成一个日志条目，减少网络往返。

流水线：不等前一条目提交就追加新条目，充分利用网络带宽。

读写分离：Follower处理只读请求（需要ReadIndex或Lease保证一致性）。

多Raft组：将数据分片，每个分片运行独立的Raft实例。TiDB使用这种架构。

拜占庭容错：当节点可能作恶

到此为止，我们假设节点只会崩溃（fail-stop），不会恶意行为。这在企业内网是合理的假设，但在开放网络中，节点可能被攻破或故意作恶——这就是拜占庭故障模型。

PBFT（Practical Byzantine Fault Tolerance）是第一个实用的拜占庭容错共识算法。它需要3f+1个节点来容忍f个拜占庭节点（相比之下，Raft只需2f+1个节点容忍f个崩溃故障）。

PBFT的核心是三阶段协议：Pre-prepare、Prepare、Commit。每个阶段都需要收集足够的消息来确保即使有恶意节点，正确节点也能达成一致。

区块链系统引入了不同的拜占庭容错机制。工作量证明（PoS）和权益证明（PoS）通过经济激励和密码学保证来选择区块生产者，与传统BFT算法的设计哲学完全不同。

Google Spanner：用原子钟打破不可能性

Google的Spanner数据库展示了一种绕过共识延迟限制的方法：TrueTime API。

传统分布式系统使用逻辑时钟或向量时钟，只能提供偏序关系。Spanner使用GPS和原子钟提供有界的时间误差：TrueTime.now()返回一个时间区间[t-ε, t+ε]，其中ε通常小于10毫秒。

利用TrueTime，Spanner可以给事务分配全局唯一的时间戳，并确保外部一致性（External Consistency）——如果一个事务T1在T2开始前提交，那么T1的时间戳一定小于T2。

这是在工程层面"欺骗"FLP不可能性的优雅案例：虽然网络延迟无界，但时钟误差有界；利用这个有界误差，可以做出确定性决策。

选择指南：何时用哪种算法

没有放之四海而皆准的最佳选择。以下是决策框架：

场景 推荐算法 理由
需要快速原型 Raft 生态成熟，文档丰富
已有Paxos基础设施 Multi-Paxos 兼容性优先
协调服务（如配置中心） ZAB/Raft 强一致性保证
高吞吐数据库 Multi-Raft 并行化瓶颈
跨地域部署 Paxos变种 + TrueTime思想 优化延迟
拜占庭环境 PBFT/PoS 恶意节点容忍

关键问题清单：

  1. 故障模型：节点只可能崩溃，还是可能作恶？
  2. 性能要求：延迟敏感还是吞吐敏感？
  3. 部署环境：单数据中心还是跨地域？
  4. 团队经验：是否有分布式系统开发经验？
  5. 生态系统：是否有成熟的库和工具？

写在最后

分布式共识是计算机科学中最深刻的领域之一。从FLP不可能性定理到Paxos的优雅，从Raft的可理解性到Spanner的TrueTime，四十年的研究与实践，证明了"不可能"只是起点，不是终点。

共识算法的价值不在于解决了什么问题，而在于它划定了什么可以做到、什么做不到。理解这些边界，才能在面对分布式系统的复杂性时做出清醒的决策。

下次当你在etcd中写入一个键值对，或在Kubernetes中创建一个Deployment时，想一想：背后是无数节点的精确协调，是四十年的理论积累，是安全性与活性的微妙平衡。这，才是分布式系统的真正魅力。

参考资料

  1. Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM.
  2. Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems.
  3. Lamport, L. (2001). Paxos Made Simple. ACM Sigact News.
  4. Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC.
  5. Howard, H., & Mortier, R. (2020). Paxos vs Raft: Have we reached consensus on distributed consensus? PaPoC.
  6. Oki, B. M., & Liskov, B. H. (1988). Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. PODC.
  7. Hunt, P., et al. (2010). ZooKeeper: Wait-free coordination for internet-scale systems. USENIX ATC.
  8. Corbett, J. C., et al. (2012). Spanner: Google’s Globally-Distributed Database. OSDI.
  9. Castro, M., & Liskov, B. (1999). Practical Byzantine Fault Tolerance. OSDI.
  10. etcd Documentation. Raft implementation details. https://etcd.io/docs/
  11. TiDB Documentation. Raft in TiKV. https://docs.pingcap.com/
  12. CockroachDB Documentation. Replication Layer. https://www.cockroachlabs.com/docs/
  13. Martin Kleppmann. Designing Data-Intensive Applications. O’Reilly, 2017.
  14. Wikipedia. Raft (algorithm). https://en.wikipedia.org/wiki/Raft_(algorithm)
  15. Wikipedia. Paxos (computer science). https://en.wikipedia.org/wiki/Paxos_(computer_science)
  16. Raft Official Website. https://raft.github.io/
  17. Google SRE Book. Managing Critical State: Distributed Consensus. https://sre.google/sre-book/
  18. AlgoMaster.io. Raft Algorithm. https://algomaster.io/learn/system-design/raft-algorithm
  19. Martin Fowler. Patterns of Distributed Systems: Paxos. https://martinfowler.com/articles/patterns-of-distributed-systems/paxos.html
  20. Boris Burkov. Overview of consensus algorithms in distributed systems. https://borisburkov.net/
  21. Neon Blog. Why does Neon use Paxos instead of Raft? https://neon.com/blog/paxos
  22. Alibaba Cloud. A Brief Analysis of Consensus Protocol: From Logical Clock to Raft. https://www.alibabacloud.com/blog/
  23. Jian Zhen. Viewstamped Replication: The Less-Famous Consensus Protocol. https://brooker.co.za/blog/
  24. Medium. Distributed Consensus: The Power of RAFT in Leader Election. https://medium.com/
  25. GeeksforGeeks. Paxos vs. Raft Algorithm in Distributed Systems. https://www.geeksforgeeks.org/
  26. ResearchGate. Performance Comparison and Analysis of Paxos, Raft and PBFT.
  27. arXiv. Performance Analysis of the Raft Consensus Algorithm. https://arxiv.org/
  28. GitHub. etcd-io/raft: Raft library. https://github.com/etcd-io/raft
  29. Kubernetes Blog. Announcing etcd 3.4. https://kubernetes.io/blog/
  30. ByteByteGo. Strong Consistency In Databases: Promises and Costs. https://blog.bytebytego.com/
  31. CSDN. 分布式系统理论：CAP、BASE、一致性算法详解.
  32. 知乎. 面渣逆袭：分布式十二问.
  33. 掘金. 彻底搞懂Raft算法.
  34. 阿里云开发者社区. 从分布式一致性到共识机制.
  35. Milvus. What is a quorum in distributed databases? https://milvus.io/
  36. Wikipedia. Safety and liveness properties. https://en.wikipedia.org/wiki/Safety_and_liveness_properties
  37. Wikipedia. Split-brain (computing). https://en.wikipedia.org/wiki/Split-brain_(computing)
  38. Google Cloud. Spanner Documentation. https://cloud.google.com/spanner/
  39. YugabyteDB Blog. How Consensus-Based Replication Work. https://www.yugabyte.com/blog/
  40. Wikipedia. Distributed SQL. https://en.wikipedia.org/wiki/Distributed_SQL