鲁班 - 系统设计大全

22.2 FLP 不可能性

一句话

FLP 说：在完全异步（消息延迟无上界）+ 至少一个进程可能崩溃的模型里，不存在 “既保证安全（不乱决定）又保证一定终止（总会决定）” 的确定性共识算法；工程上不是 “绕过定理”，而是换假设——加超时、加随机化、加部分同步。

定理的三个前提（缺一不可）

前提 含义 去掉它会怎样
异步 消息可任意延迟，无法区分 “慢” 与 “死” 若能给延迟上界（同步），可用超时判定，算法可终止
崩溃故障 进程可能停止响应（不是拜占庭） 拜占庭需要更强假设（3f+1），但也要额外机制
确定性 每一步由输入与消息唯一决定 允许随机化，可以 “以概率 1 终止”（如随机化 Paxos）

经典论证（直觉版）：假设存在这样的算法，则存在一个 “临界执行”，此时下一步的决定取决于某条消息；对手（adversary）把这条消息无限延迟，算法既不能安全地决定，也不能排除 “对方只是慢”，于是永远不终止。

一张表看清 “边界在哪”

模型 共识可解？ 代表
同步 + 崩溃 ✅ 传统 2PC（但依赖超时假设）
异步 + 崩溃 ❌（FLP） —
异步 + 随机化 ✅ 以概率 1 随机化 Paxos、Ben-Or
部分同步 + 崩溃 ✅（GST 后终止） Paxos、Raft、ZAB
异步 + 拜占庭 ❌（需 3f+1 + 签名等额外假设） PBFT 在部分同步下可解

代码：为什么 “等不到回复” 不能被判定为 “对方死了”

// 异步模型下的 “猜疑”：超时只是本地判断，不是事实
select {
case msg := <-ch:
    return msg            // 收到：继续推进
case <-time.After(3 * time.Second):
    // 关键：这里无法区分三种情况
    //   ① 对方崩了  ② 对方慢  ③ 消息在网络上丢了
    // 任何 “基于此就决定” 的规则，都可能在 ② 时做出错误决定
    return suspect(peer)
}

FLP 的实质就是：上面那个 select 里的三个分支，在异步模型下不可区分。任何 “用超时当事实” 的算法，都只能保证 “大概率对”，而不是 “一定对”。

反模式

反模式 后果
宣称 “我们的共识算法没有 FLP 问题” 要么偷偷依赖了同步假设（超时），要么牺牲了活性
用固定超时做 “故障判定” 网络抖动时误判，引发不必要的切主
为了 “一定终止” 放弃安全性 出现脑裂/双写，比不终止更糟
忽略随机化退避 多个候选同时超时，选票分裂，永远选不出
把 “最终一致” 当作 “共识” 混淆了 “会收敛” 与 “已决定”
不记录 “未决定” 的状态 卡住时无法判断是 “在等” 还是 “已死锁”

三条铁律

🔑 异步 + 崩溃 + 确定性 = 不可能；工程必须换掉其中一个。

🔑 超时是 “本地判断”，不是 “全局事实”。

🔑 安全性不可交易：宁可暂时不决定，不可决定错。

自检

Q1 FLP 说 “不可能”，为什么 Raft/Paxos 还能用？

▸ 答案：因为它们不满足 FLP 的前提：Raft/Paxos 假设 “部分同步”（消息延迟最终有界），并依赖超时来触发选举与推进。它们保证的是 “在 GST 之后会终止”，而不是 “在任意异步执行下都终止”——这正是 “换假设” 而不是 “违反定理”。

Q2 为什么 “加随机化” 能绕开 FLP？

▸ 答案：因为 FLP 针对的是确定性算法：每一步由输入唯一决定。随机化让 “下一步” 变成概率分布，对手无法构造 “永远让它犹豫” 的执行；算法以概率 1 在有限步内决定（期望步数有限，但最坏情况仍可能很久）。

Q3 “不终止” 和 “决定错” 哪个更糟？

▸ 答案：决定错更糟。不终止只是 “暂时不可用”，可以重试、人工介入、降级；决定错会造成数据不一致（双主、丢更新），修复成本高且可能不可逆。所以共识算法一律 “安全优先，活性次之”。

Q4 2PC 为什么不算 “解决 FLP”？

▸ 答案：因为 2PC 依赖 “协调者最终会恢复” 这个隐含的同步假设：协调者挂掉后，参与者只能无限等待。它没有解决 “异步下无法区分慢与死” 的问题，只是把不确定性转移到了 “阻塞窗口”。

Q5 拜占庭故障为什么需要 3f+1？

▸ 答案：因为要容忍 f 个可能撒谎的节点，必须保证 “诚实的多数派” 能压过它们：N - f > f 且要覆盖 “可能分歧” 的投票，推导出 N ≥ 3f + 1。相比崩溃故障（2f+1），多出的 f 是用来 “对冲谎言” 的。

Q6 工程上怎么 “感知” 自己是否踩到了 FLP 的边界？

▸ 答案：看 “是否存在无限期的未决定状态”：选举反复超时、提案永远 commit 不了、副本间 lag 无限增长。出现这些，说明系统已经进入 “异步 + 无法判定” 的区域，需要人工干预或引入更强假设（如降低网络抖动、调大超时）。

Q7 为什么 “最终一致” 的系统不需要 FLP？

▸ 答案：因为 “最终一致” 放弃的是 “何时一致”，只承诺 “最终会一致”：它不需要在有限步内 “决定”，所以不受 FLP 约束。FLP 约束的是 “共识（在有限时间内决定一个值）”，不是 “收敛”。

关联