《云计算技术系列丛书 云原生分布式存储基石： etcd深入解析》—1.2.5FLP不可能性

1.2.5　FLP不可能性

       FLP不可能性（FLP Impossibility，F、L、P三个字母分别代表三个作者Fischer、Lynch和Patterson名字的首字母）是分布式领域中一个非常著名的定理（能够在计算机科学领域被称为“定理”，可见其举足轻重的地位），该定理给出了一个令人吃惊的结论：

       No completely asynchronous consensus protocol can tolerate even a single unannounced process death.

       在异步通信场景下，任何一致性协议都不能保证，即使只有一个进程失败，其他非失败进程也不能达成一致。这里的“unannounced process death”指的是一个进程发生了故障，但其他节点并不知道，继续认为这个进程还没有处理完成或发生消息延迟了，要强于上文提到的“fail-stop Failure”。感兴趣的读者可以翻阅论文“Impossibility of Distributed Consensus with One Faulty Process”[5]。下面用一个小例子来帮助大家直观地理解FLP定理。

甲、乙、丙三个人各自分开进行投票（投票结果是0或1）。他们彼此可以通过电话进行沟通，但有人会睡着。例如：甲投票0，乙投票1，这时候甲和乙打平，丙的选票就很关键。然而丙睡着了，在他醒来之前甲和乙都将无法达成最终的结果。即使重新投票，也有可能陷入无尽的循环之中。

       FLP定理实际上说明了在允许节点失效的场景下，基于异步通信方式的分布式协议，无法确保在有限的时间内达成一致性。换句话说，结合CAP理论和上文提到的一致式算法正确性衡量标准，一个正确的一致性算法，能够在异步通信模型下（P）同时保证一致性（C）和可终止性（A）—这显然是做不到的！

       请注意，这个结论的前提是异步通信。在分布式系统中，“异步通信”与“同步通信”的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序等。

       可能会有读者提到TCP。在分布式系统的协议设计中，不能简单地认为基于TCP的所有通信都是可靠的。一方面，尽管TCP保证了两个TCP栈之间的可靠通信，但无法保证两个上层应用之间的可靠通信。另一方面，TCP只能保证同一个TCP连接内网络报文不乱序，而无法保证不同TCP连接之间的网络报文顺序。在分布式系统中，节点之间进行通信，可能先后会使用多个TCP连接，也有可能并发建立多个TCP连接。

       根据FLP定理，实际的一致性协议（Paxos、Raft等）在理论上都是有缺陷的，最大的问题是理论上存在不可终止性！至于Paxos和Raft协议在工程的实现上都做了哪些调整（例如，Paxos和Raft都通过随机的方式显著降低了发生算法无法终止的概率），从而规避了理论上存在的哪些问题，下文将会有详细的解释。