汀的知识碎片

03 FLP 不可能定理与共识问题

30 min read

03 FLP 不可能定理与共识问题

摘要：

1985 年，Fischer、Lynch、Paterson 三位计算机科学家在 Journal of the ACM 上发表了一篇只有 8 页的论文，证明了一个令人震惊的结论：在异步网络中，哪怕只有一个进程可能崩溃，也不存在能够在有限时间内确定性地解决共识问题的算法。这就是著名的 FLP 不可能定理（FLP Impossibility Result）。它从理论上划定了分布式系统的能力边界，解释了为什么我们无法设计出一个”完美”的分布式共识协议。本文系统讲解共识问题的形式化定义，从零推导 FLP 定理的核心论证思路（不绕过数学，但力求直觉可理解），并深入分析 Paxos、Raft 等实用协议是如何在 FLP 的约束下”绕路”达成共识的——它们并非打破了 FLP，而是通过引入概率性（随机算法）或弱化异步假设（部分同步模型）在理论约束内求解。

第 1 章 共识问题：分布式系统的核心抽象

1.1 什么是共识

共识（Consensus） 是分布式系统中最核心的协调原语之一。它描述的是这样一个问题：多个进程各自提议一个值（Propose），最终所有进程需要就某一个值达成一致（Decide），且一旦决定就不可更改。

听起来很简单，但”在不可靠的分布式环境中实现共识”却是分布式计算理论中最困难的问题之一。

共识问题的三个正确性要求（形式化定义）：

性质一：终止性（Termination） 每个没有崩溃的进程（Correct Process）最终都会做出决定（Decide on a value）。终止性是**活性（Liveness）**属性——它保证系统最终会有进展，不会永远悬而未决。

性质二：协议性（Agreement） 任意两个做出决定的进程（无论是否崩溃），决定的值必须相同。协议性是**安全性（Safety）**属性——它保证不会出现两个进程决定了不同值的情况（这是最危险的情形：一个进程认为”大家决定了 A”，另一个进程认为”大家决定了 B”）。

性质三：有效性（Validity） 被决定的值，必须是某个进程提议过的值。有效性防止算法通过”凭空决定一个没人提议过的值”来取巧地满足协议性和终止性（如所有进程都固定决定值 0，无论提议的是什么）。

1.2 共识的典型应用场景

Leader 选举（Leader Election）：在主备架构中，多个节点需要就”谁是 Leader”达成共识。这是共识问题的直接映射——每个节点提议自己或某个候选节点，最终所有节点决定同一个 Leader。

原子提交（Atomic Commit）：在分布式事务中（如 2PC），多个参与者需要就”这个事务是提交还是回滚”达成共识。只有所有参与者决定相同（都提交或都回滚），事务的原子性才能保证。

状态机复制（State Machine Replication，SMR）：在多个副本之间保持操作日志的一致——多个节点需要就”下一条日志条目是什么操作”达成共识，这样所有副本以相同顺序执行相同操作，最终状态相同。Paxos 和 Raft 本质上都是在解决序列化的共识问题（对每个日志条目的值达成共识）。

1.3 共识 vs 一致性：两个容易混淆的概念

共识（Consensus） 是一个算法问题：多个进程如何就某个值达成一致？它是一个动态过程，描述的是协调协议本身。

一致性（Consistency） 是一个系统属性：分布式存储系统在不同操作之间应该呈现什么样的数据视图？它描述的是系统对外暴露的语义（如线性一致性、最终一致性）。

两者的关系：共识算法（如 Raft）是实现强一致性存储的手段。通过共识算法对每个写操作排序，可以构建出满足线性一致性的分布式存储。但一致性是目标，共识是达成目标的工具。

第 2 章 FLP 不可能定理：异步网络的根本限制

2.1 定理的完整陈述

FLP 不可能定理（FLP Impossibility）：

在一个异步消息传递的分布式系统中，即使只有一个进程可能发生崩溃故障（Crash Failure），也不存在一个确定性算法能够解决共识问题（同时满足终止性、协议性、有效性）。

这里的每个限定词都至关重要：

  • 异步消息传递：消息可以任意延迟，没有传递时间的上界。这是 FLP 成立的关键前提。在同步网络中（有已知的消息延迟上界），共识是可以解决的。
  • 只有一个进程：不是 f 个进程，而是最坏情况下哪怕只有 1 个进程可能崩溃，定理就成立。
  • 崩溃故障：是最温和的故障模型（进程停止响应，不会发送错误消息）。在拜占庭故障模型下，结论只会更悲观。
  • 确定性算法：排除了随机算法。FLP 只对确定性算法成立；带随机性的算法（如 Ben-Or 随机共识算法）可以以很高的概率在有限时间内达成共识。

2.2 为什么这个结论令人震惊

在 FLP 之前，计算机科学家普遍认为共识问题应该是可解的——毕竟，在网络完全正常的情况下（没有消息丢失、没有进程崩溃），共识显然是可以达成的（所有进程交换提案，选最大值）。

FLP 的震惊之处在于：它证明了即使只有一个进程”可能”（不是”一定”）崩溃，共识就变得不可解。注意是”可能”崩溃——这个进程在算法运行期间可能一直正常运行，但仅仅是”存在崩溃的可能性”，就足以让任何确定性共识算法失败。

为什么”可能崩溃”就够了？因为算法无法区分”进程崩溃了”和”进程的消息正在延迟中”——在异步网络中，这两种情况对其他进程来说是完全相同的观察结果（都是”没有收到消息”）。

2.3 FLP 证明的核心思路（非形式化）

FLP 的完整证明需要大量的形式化符号，但其核心思想可以用以下思路来直觉性地理解：

关键概念一：配置（Configuration）

一个”配置”描述了某个时刻系统的完整状态：每个进程的内部状态 + 在传输中的消息集合。初始配置是所有进程启动时的状态，最终配置是所有进程做出决定后的状态（决定 0 或 1）。

关键概念二：二价性（Bivalence）与单价性（Univalence）

对于任意一个配置：

  • 0-单价（0-valent）：从这个配置出发，无论接下来发生什么，最终的决定结果一定是 0
  • 1-单价（1-valent）：从这个配置出发，无论接下来发生什么，最终的决定结果一定是 1
  • 二价（Bivalent）：从这个配置出发，可能最终决定 0，也可能最终决定 1（取决于接下来的事件顺序）

引理一（FLP 证明第一步）：存在一个二价的初始配置。

这个引理的证明思路：假设所有进程初始都提议 0（v₀），最终必须决定 0（由有效性保证）。假设所有进程初始都提议 1（v₁），最终必须决定 1。现在考虑一系列初始配置，从”所有进程提议 0”到”所有进程提议 1”，每次只改变一个进程的初始提议。在这个序列中，必然存在相邻的两个配置 C 和 C’，它们只差一个进程的初始提议不同，但一个是 0-单价的，另一个是 1-单价的。如果这个进程在 C 和 C’ 中”崩溃”（对外不可见，因为它的提议不影响其他进程已经收到的消息），那么其他进程无法区分 C 和 C’，但它们在 C 中决定 0，在 C’ 中决定 1——矛盾！因此，存在一个二价的初始配置（C 和 C’ 之间的某个状态是二价的）。

引理二（FLP 证明第二步）：从一个二价配置出发，总可以到达另一个二价配置（系统可以在二价状态中无限循环）。

这个引理的证明是 FLP 证明的核心，也是最微妙的部分。它通过构造一系列的”对抗性调度”（Adversarial Schedule）——刻意延迟某些消息，使得系统永远停留在”还没有做出决定”的状态——来证明共识的终止性无法保证。

证明逻辑：假设系统处于一个二价配置 C，下一个要处理的事件 e（某个进程接收某条消息）。分两种情况讨论：

  1. 处理 e 后系统仍然是二价的 → 继续，可以一直维持二价状态，永不达成共识
  2. 处理 e 后系统变为单价的 → 但此时，如果那个”可能崩溃”的进程选择在这一刻”暂停”（延迟响应，异步网络允许任意延迟），系统在外部看来和”这个进程已经崩溃”完全一样，其他进程无法判断该如何前进，仍然处于二价状态

在异步网络中，“对抗性调度”总可以找到方法让系统停留在二价状态——这意味着算法永远不能保证终止，即终止性不满足。

结论：不存在能同时满足终止性、协议性、有效性的确定性共识算法。

2.4 一个直觉性的类比

想象三个人（进程 A、B、C）需要就”投票结果”达成共识，他们通过纸条传递信息（异步消息）。其中一个人（比如 C）可能在某个时刻”突然失联”（崩溃）。

A 向 B 发送了自己的票（纸条），B 收到了。B 向 A 回复了自己的票，但纸条在路上——A 还没收到。

问题：A 是否可以做出最终决定？

  • 如果 A 等待 B 的回复，但 B 可能已经崩溃了——A 要等多久？（A 无法确定 B 是崩溃了还是回复正在路上）
  • 如果 A 不等 B，直接做出决定，可能与 B 的决定冲突（B 已经有了自己的票，B 会做出不同的决定）

这就是 FLP 定理的直觉核心：在异步系统中，等待意味着可能永远等待（失去终止性），不等待意味着可能做出错误决定（失去协议性）。

第 3 章 实用协议如何”绕过”FLP

FLP 定理的结论是”不可能”，但 Paxos、Raft、ZAB 等协议都声称能解决分布式共识——这不是矛盾吗？

不矛盾。实用协议通过两种合法的方式绕开了 FLP 的约束：

3.1 方式一：放弃纯异步假设，引入部分同步模型

FLP 定理的前提是纯异步网络（消息延迟没有上界）。实用协议并不工作在纯异步网络中，而是假设一个更贴近现实的**部分同步（Partially Synchronous）**网络模型。

部分同步网络的核心假设：存在一个消息延迟上界 Δ（Global Stabilization Time，GST），在 GST 之后，所有消息会在 Δ 时间内到达。在 GST 之前，网络是异步的（没有延迟上界）；在 GST 之后，网络是同步的。

Δ 是未知的（否则就退化为同步网络），但它存在。这个假设比”纯异步网络”弱（因为假设了上界 Δ 的存在），但比”纯同步网络”弱（因为不知道 Δ 的具体值，也不知道 GST 何时到达）。

部分同步下共识的可能性：

在部分同步模型中，共识是可以解决的，但需要满足一个条件：算法在 GST 之前（网络不稳定时）必须保证安全性（不做出错误决定），在 GST 之后（网络稳定时）必须保证活性（最终做出决定）。

这正是 Paxos 和 Raft 的核心设计原则：

  • 安全性永远保证：无论网络多么不稳定，协议永远不会让两个副本决定不同的值（不违反协议性）
  • 活性在网络稳定后保证：只要网络稳定下来（GST 到达后），协议最终会达成共识

这意味着：如果网络长期不稳定（如 Leader 反复切换），系统可能长时间无法提交新操作——但它不会损坏数据。一旦网络稳定，系统会恢复服务。

3.2 方式二：使用随机算法（概率性共识）

FLP 定理只对确定性算法成立，随机算法可以绕开它。

Ben-Or 随机共识算法（1983 年）是最早的随机共识算法之一，它通过在每一轮决策中引入随机选择，使得即使在纯异步网络中，也能以概率 1 在有限期望步数内达成共识。

然而，随机算法在实践中很少用于生产级共识协议，原因有两个：

  1. 性能不稳定：期望步数可能很大，在高并发场景下平均性能较差
  2. 工程实现复杂：需要可靠的随机源，安全随机数的获取本身有性能开销

现代生产级共识协议（Paxos、Raft、ZAB）都选择了”部分同步模型”而非随机算法。

3.3 FLP 在实践中意味着什么

FLP 定理对工程实践的最重要启示不是”共识不可能”，而是：在异步网络中，共识协议在某些时刻必须在安全性和活性之间做出选择——而现代协议选择了”永远保证安全性，活性条件性保证”。

具体地说，Paxos 和 Raft 在以下情况下可能无法完成共识（暂时失去活性）：

  • Leader 刚刚崩溃，新 Leader 还未选出（选举期间无法提交新操作）
  • 网络分区导致无法达到多数派（少数派侧永远无法提交）
  • 多个候选人同时发起选举，分散了选票（选举竞争，需要等待超时后重试）

但在这些情况下，协议不会产生不一致的数据——安全性从未被违反，活性只是暂时缺失，网络稳定后会恢复。

FLP 与 CAP 的关系

FLP 和 CAP 是两个不同角度描述分布式系统局限性的定理：

  • CAP 描述的是”分布式存储系统”在网络分区时的权衡（一致性 vs 可用性）
  • FLP 描述的是”分布式共识算法”在异步网络中的根本不可能性（安全性 vs 活性）

两者并不互相包含，但都指向同一个根本事实：在不可靠的分布式环境中，信息无法瞬间传播，这种物理限制决定了分布式协调的固有复杂性。

第 4 章 共识的实用解法：活性 vs 安全性的工程权衡

4.1 Paxos/Raft 的”安全优先”设计哲学

现代共识协议的设计哲学可以归结为一句话：“安全性是绝对的，活性是有条件的”。

为什么安全性优先？

安全性违反（两个节点决定了不同的值）会导致不可修复的数据不一致：一旦发生，必须人工干预才能恢复，且往往意味着数据已经损坏或业务已经做出了错误决定。

活性违反（系统暂时无法达成新的共识）只是暂时性的不可用：系统停止服务，但数据仍然正确。用户看到的是”服务暂时不可用”，而不是”数据已损坏”。两者的严重性差距是巨大的。

这种设计选择是分布式系统工程实践中的普遍共识：宁可短暂不可用，也不能数据不一致。

4.2 Paxos 和 Raft 对活性问题的处理

Leader 选举超时（Election Timeout）：

Raft 通过随机化的选举超时来解决”多个候选人同时竞争”（分散选票）的活性问题：每个节点的选举超时时间是从一个区间（如 150ms ~ 300ms）中随机选取的。随机化使得多数情况下只有一个节点先发起选举，能够在其他节点超时之前收到足够的选票当选 Leader。

这本质上是将随机性引入了活性（Leader 选举）部分，但仍然保持了安全性（日志提交）的确定性。

PreVote 优化（防止无谓的选举干扰）：

在某些场景下（如网络分区后某节点独立），一个节点反复发起选举（因为它无法联系到 Leader），会干扰正常节点的工作。Raft 的 PreVote 扩展在正式发起选举之前先进行一轮预检，只有确认自己有机会当选才正式发起，减少了无效选举对系统的干扰。

Leadership Transfer：

Raft 支持 Leader 主动将 Leader 权转让给另一个节点（如在计划内的维护操作时），转让过程保证了在转让期间不提交新操作（安全性），且快速完成（活性）。

4.3 活性与安全性的度量

在工程实践中，我们通常用以下指标来量化共识协议的活性和安全性表现：

安全性指标：

  • 数据丢失率：已提交的操作是否会因故障而丢失（理想值：0）
  • 脑裂发生概率：是否可能同时有两个 Leader 各自提交数据（理想值：0）

活性指标：

  • 故障恢复时间（MTTR，Mean Time to Recovery）：Leader 崩溃后，集群恢复到能提交新操作的平均时间
  • 选举完成时间：从发起选举到新 Leader 当选的时间（通常与选举超时设置相关）
  • 写操作延迟 P99：正常情况下一次写操作从发起到提交的 P99 延迟

典型生产级 Raft 集群（如 etcd）的参考数值：

  • 选举超时：150ms ~ 300ms
  • Leader 崩溃恢复时间：约 150ms ~ 500ms（一个选举超时周期）
  • 写操作延迟 P99（同机房）：< 5ms
  • 数据丢失率：0（已提交操作永远不会丢失）

第 5 章 共识问题的历史演进与工程意义

5.1 从 2PC 到 Paxos：工程界对 FLP 的回应

在 FLP（1985 年）之前，工业界广泛使用**两阶段提交（2PC）**来解决分布式事务的原子提交问题。2PC 是一个确定性的协议，它在协调者（Coordinator）正常的情况下工作得很好，但在协调者崩溃时，系统可能无限期地阻塞——这正是 FLP 所预言的：确定性算法在面对崩溃故障时无法保证终止性。

Paxos（Lamport，1989 年正式写成，1998 年发表）的出现，提供了一个在部分同步假设下既安全又有活性的共识协议——它优雅地在 FLP 的约束内工作，而不是试图违反它。Paxos 成为分布式系统理论和工程实践的里程碑。

5.2 FLP 的工程实践启示

启示一：不要期望一个”完美的”共识算法

FLP 告诉我们，在异步环境中，完美的共识（同时满足所有三个性质）是不存在的。实用协议都是在特定假设（部分同步）下的近似解，工程师需要理解这些假设和它们的局限。

启示二：系统的不可用期是设计的正常部分，不是 Bug

当 Raft 集群在 Leader 切换期间（约 200ms）无法提交新操作时，这不是 Bug——这是协议在优先保证安全性的代价。工程师需要接受”系统偶尔短暂不可用”是分布式一致性的固有代价。

启示三：超时设置是影响活性的关键参数

选举超时、心跳间隔等参数直接影响共识协议的活性（故障恢复速度）。过长的超时导致故障恢复慢（活性差），过短的超时导致误判频繁（频繁触发选举，影响正常性能）。这是共识协议调优中最重要的工程问题之一。

启示四：活性不是免费的——需要网络稳定性作为前提

部分同步假设要求网络”最终会稳定”（GST 存在）。如果网络持续不稳定（如数据中心间的跨域链路质量很差），共识协议可能长期无法完成选举，导致持续不可用。这是为什么生产级 Raft/Paxos 集群通常部署在同机房（低延迟、稳定）而非跨数据中心（高延迟、不稳定）的根本原因。

参考资料

  1. Fischer, M.J., Lynch, N.A., & Paterson, M.S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2), 374–382. （FLP 原始论文）
  2. Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems, 16(2), 133–169. （Paxos 原始论文）
  3. Ben-Or, M. (1983). Another advantage of free choice: Completely asynchronous agreement protocols. PODC 1983.
  4. Dwork, C., Lynch, N., & Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of the ACM, 35(2), 288–323. （部分同步模型的理论基础）
  5. Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm (Extended Version). USENIX ATC 2014. （Raft 论文）
  6. Kleppmann, M. (2017). Designing Data-Intensive Applications. O’Reilly Media. Chapter 9: Consistency and Consensus.
  7. Lynch, N. (1996). Distributed Algorithms. Morgan Kaufmann. Chapter 5-7.
  8. Chandra, T.D., & Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2), 225–267.

思考题

  1. Raft 的 Leader 选举使用任期（Term）和随机化超时。如果 Leader 与 Follower 之间的心跳中断超过选举超时——Follower 成为 Candidate 发起选举。在网络分区恢复后，旧 Leader（低 Term）发现新 Leader（高 Term）——旧 Leader 自动降级为 Follower。在分区期间旧 Leader 已接受的写入会丢失吗？
  2. Raft 的日志复制保证了’已提交的日志不会丢失’——通过’Leader 的日志是最完整的’这一安全性保证。但在 Leader 崩溃和新 Leader 选举期间，部分’未提交’的日志可能被新 Leader 覆盖。在什么场景下客户端需要关注’写入已确认但实际未提交’的风险？Raft 的线性一致性读如何避免’读到未提交的数据’？
  3. Raft 集群的可用性取决于多数节点在线。5 节点集群容忍 2 个节点故障。但在实际部署中，节点分布在不同的故障域（如可用区）——如果 3 个节点在同一可用区，该可用区故障会导致集群不可用。你如何规划 Raft 节点的物理分布以最大化容错能力？

Backlinks