FLP 不可能定理介绍

本文最后更新于：2 年前

前言

FLP 不可能定理与 CAP，BASE 定理等一样，都是分布式系统的基本理论，因此我们有必要了解该理论。

本博客摘抄了此博客中对 FLP 不可能定理的部分描述。

定义

1985 年，Fisher、Lynch、Paterson 三位科学家就发表了关于分布式一致性问题的不可能定理：在完全异步的分布式网络中，故障容错问题无法被解决。（ We have shown that a natural and important problem of fault-tolerant cooperative computing cannot be solved in a totally asynchronous model of computation）

说得更直白点：在异步网络中，不可能存在能够容忍节点故障的一致性算法，哪怕只有一个节点故障。并且这里并没有考虑拜占庭错误，而是假设网络非常稳定、所有的消息都能被正确传递、并且仅被传递一次，即便如此都不可能找到能容忍哪怕只有一个节点失效的一致性协议，可见该结论有多强。（ In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliableit delivers all messages correctly and exactly once）

现实生活中的系统往往都是异步系统。因为系统中各个节点之间的延时，是否宕机等等都是不确定的。那么，在最小化异步模型系统中，是否存在一个可以解决一致性问题的确定性共识算法？

FLP 不可能定理的最大适用前提是异步网络模型。何为同步、异步模型呢？

所谓异步模型，是说从一个节点到另一个节点的消息延迟是有限的，但可能是无界的（finite but can be unbounded）。这就意味着如果一个节点没有收到消息，它无法判断消息到底是丢失了，还是只是延迟了。也就是说，我们无法通过超时时间来判断某个节点是否故障。
所谓同步模型，是说消息传递的延迟是有限的，且是有界的。这就意味着我们可以通过经验或采样精确估算消息的最大可能延迟，从而可以通过超时时间来确定消息是否丢失、节点是否故障。

所幸的是，我们所处于的真实的网络世界更接近同步模型，在很多场景上，我们都可以通过经验或采样确定最大超时时间。举个通俗点的例子：你给朋友快递了一本书，朋友过了 3 天还没收到，此时朋友很难判断到底是快递延迟了，还是快递出问题送丢了。但是如果过了一个月，朋友仍没收到书，基本就可以断定快递送丢了。而背后的推论就是基于经验或统计：通常快递都能在 1-2 周内送达。显然，异步模型其实是反映了节点间通讯的最差情况、极端情况，异步模型包含了同步模型，即能在异步模型上有效的一致性协议，在同步模型上也同样有效。而同步模型是对异步模型做了修正和约束，从而使得更接近真实世界，也使得在实践中一致性问题有可能得到有效解。

另外，即便是在异步网络模型下，FLP 也并不意味着一致性永远无法达成，只是说无法保证在有界的时间（in bounded time）内达成。在实践上，如果放宽对 bounded time 的限制，仍然是有可能找到实践中的解法的。

根据 DLS 的研究，一致性算法按照网络模型可以分为三大类：

部分同步网络模型（partially synchronous model）中的一致性协议可以容忍最多 1/3 的任意错误。这里的部分同步模型是指网络延迟是有界的，但是我们无法提前得知。这里的容错也包含了拜占庭类错误。
异步网络模型（asynchronous model）中的确定性协议无法容忍错误。这里的异步模型即是前文所说的网络延迟是无界的。该结论其实就是 FLP 不可能定理的含义，在完全异步网络中的确定性协议不能容忍哪怕只有一个节点的错误。
同步网络模型（synchronous model）可以达到惊人的 100% 容错，虽然对错误节点超过 1/2 时的节点行为有限制。这里的同步模型是指网络延迟一定是有界的，即小于某个已知的常数。

从另一个角度来理解，FLP 实际上考虑了分布式系统的 3 个属性：安全 (safety)、活性（liveness)、容错：

安全是说系统内各个节点达成的值是一致的、有效的。safety 其实是保证系统一致性运行的最低要求，其核心是 cannot do something bad，即不能干坏事、不能做错事。
活性是说系统内各个节点最终（在有限时间内）必须能够达成一致，即系统必须能够向前推进，不能永远处于达不成一致的状态。liveness 其实是更高要求，意味着不能只是不干坏事，也不能一直不干事，you must do something good，即必须使得整个系统能良好运转下去。
容错是说该协议在有节点故障的情况下也必须能有效。

FLP 不可能定理其实意味着在异步网络中，不可能存在同时满足这三者的分布式一致性协议。因为分布式环境中，节点故障几乎是必然的，因此容错是必须要考虑的因素，所以 FLP 不可能定理就意味着一致性协议在能做到容错的情况下，没办法同时做到安全性与系统活性。通常在实践中，我们可以做出部分牺牲，比如牺牲一部分安全性，意味着系统总能很快达成结论，但结论的可靠性不足；或者牺牲一部分系统活性，意味着系统达成的结论非常可靠，但可能长时间、甚至永远都在争论中，无法达成结论。所幸的是，很多时候现实世界的鲁棒性很强，使一致性协议失效的倒霉事件发生的概率也很可能极低。例如分布式共识协议 Paxos 和 Raft 都是保证了容错性和 safety，然后通过随机超时时间来规避 liveness 的问题。