你好，我是任杰。这一讲我们聊一聊，什么情况下不存在正确的分布式共识算法。
对于金融行业来说，系统的正确性要远高于系统的执行效率。打个比方，当你在网上和朋友聊天的时候，漏掉了一两条消息其实无所谓。但是如果你给朋友网上转钱，钱转丢了就是件大事了。
金融行业的信息系统和互联网企业一样，也是由很多台机器组成的集群提供服务。机器一旦多了就会出现分布式系统常见的各种问题，比如宕机、网络中断。
那这种情况下，我们怎么才能保证金融系统的正确性呢？套用一句知乎上经常看到的评论，我们在回答为什么之前，先要问问是不是。你有没有想过，万一正确的分布式系统并不存在呢？
这些问题其实是对分布式系统的深入思考，也是金融级软件对架构师的要求。只有知其然并且知其所以然了，客户才能对你做出来的金融系统有信心。
共识是指多台机器之间达成统一的结论。这节课我们会证明可能是分布式系统里最重要的一个结论，那就是不存在共识算法。准确来说，在一个完全异步的分布式系统里，如果至少有一台机器可能会出问题，那么就不存在非随机的共识算法。
从结论可以看出，想要共识算法不存在，需要同时存在两个现象：一个是机器出问题，另一个是完全异步。只要我们能让任何一个条件失效，就存在共识算法。
很显然我们无法保证机器不出问题，所以重点要放在怎么让系统不是完全异步。幸运的是完全异步这个条件非常容易去除，只需要给每台机器增加一个时钟来判断发送的消息是否丢失。
这也是为什么常见的共识算法，比如Paxos和Raft，里面一定会判断消息是否超时。所以虽然理论上分布式系统不存在共识算法，但是现实中很容易绕开这些理论约束，实现正确的共识算法。
证明的过程分为三步。第一步证明，分布式系统一定存在某个特殊的开始状态，共识算法的最终结果与这个特殊状态无关，只取决于某台机器是否出问题。
第二步证明我们能构造出一些特殊场景，使得分布式系统从这个特殊状态开始运行后，还会进入下一个特殊状态。
第三步结合了前面两步的证明，我们不断构造特殊场景，系统会周而复始地进入特殊状态，从而永远无法做出共识结论。由于对于任何一个号称具有共识能力的算法，我们都可以构造出这些特殊的情境，也就不存在真正的共识算法了。
如果你想更深入地了解这个结论，可以看这几篇论文：
好，现在我已经交代了这节课的核心内容，不过你要是有好奇心，可以仔细看看后面的证明过程。
算法课一般会讲如何实现一个算法，很少会谈到如何证明算法不存在。证明算法存在只需要举个例子就可以，但是证明算法不存在，就需要证明所有可能的算法都不行，难度非常高。你可以通过下面的证明，提高自己对分布式系统复杂度的理解。
"Impossibility of Distributed Consensus with One Faulty Process"这篇划时代的论文在2001年被评为Dijkstra分布式系统最具影响力论文。因为这个结论太重要，所以一般称为“FLP结论”。
这篇论文证明了分布式系统不存在共识算法。我们前面说过共识的定义，但不够准确。所以在证明开始之前，让我们重新定义一些专有名词。
分布式系统由至少3台机器组成。每台机器都有自己的初始状态。为了方便证明，我们假设状态是二元的，即只能是0或者1。不是二元状态的情况和二元状态一样，只是证明过程会稍微繁琐一点。
分布式系统是一个封闭的系统，没有外界输入。系统里的所有机器节点在最开始都有自己的状态，随后这些节点之间，会按照算法定好的逻辑给彼此发送消息。每台机器在收到消息之后可以做三件事。
第一，改变自己的状态。这时机器从初始状态变为中间状态。
第二是向其他机器发送消息。发送的机器数量不做限制，可以一个机器都不发，也可以发给很多机器。
第三是输出一个结果。这个结果只能从0或者1中选择，而且机器只能输出一次结果。
通俗地说，每台机器里面最开始含有一个数字，0或者1。机器最后会输出一个数字，也是0或者1。机器之间可以互相发送消息，通过消息来改变彼此内部的状态。输入和输出示意图如下：
和现实世界类似，分布式系统内的机器并不稳定。它们会死机，会重启，也会变得很慢。但是我们这里假设机器逻辑都是正确的，一旦我们写了一个算法，机器会老老实实地按算法执行，不会偷偷利用算法的漏洞来攻击算法。
用现在的区块链理论来说，我们这里假设碰到的是非拜占庭问题，而不是区块链或者比特币解决的拜占庭问题。如果你对拜占庭问题有兴趣可以自行查找相关定义，或者参考这篇文章。
最后说说论文对共识算法的一个隐含假设。这里假设共识算法不是随机的，主要是考虑结果可复现性。
有了前面对机器的准确定义，共识就更好定义了。共识其实就是要求这组机器的输出都相同，但是这还不够准确，更加精准一点的定义是这样的，共识需要满足以下3个条件：
1.终止性（termination）
2.一致性（agreement）
3.有效性（validity）
其中，终止性指每个还能正常运行的机器最终都需要确定唯一一个结果。这里有两个重点。一是所有还能正常运行的机器都需要生成结果，一个不落。不能正常运转的机器没有任何要求。二是结论只能生成一次，一旦做出就无法更改。
一致性相对好理解一点。一致指所有结果都需要完全相同。终止性和一致性有一个更通俗的解释：所有机器的状态初始可以在0和1中任意选择，最后当共识算法结束的时候，所有还活着的机器需要输出一样的结果，要么都是0，要么都是1。示意图如下：
最后一个条件是有效性。有效性指的是所有结果都有可能是共识结果。举个例子，你其实也可以参与分布式系统的决策。你可以写一个共识算法，不管机器初始状态是什么，最后都输出0。这样也算是一个共识，但是这个共识算法毫无意义，所以我们需要把这种极端简化的情况排除。
我们前面提到了机器之间是可以互相发消息的。消息需要仔细定义，因为分布式系统的复杂度是和消息传输方式的复杂度一一对应的。
消息的第一个假设是消息的发送是异步的。异步是指你给对面的机器发送了一条消息后，你不一定能收到反馈。
收不到反馈可能有很多种情况，这时候你不知道究竟是消息还没发送到那台机器，还是那台机器已经收到了，但是给你反馈前死机了。
收到消息的时间间隔也没有任何假设。你的消息可能几分钟后就能收到，或者很久才收到，甚至永远收不到。时间间隔是一个重点，我们在最后会再次提到。
消息的另一个假设是消息系统本身的运行是完美的。所有消息会被先存储在消息队列里。这个队列不会丢失任何消息。
另外，所有消息只会被处理一次，也就是说不会碰到消息重发的问题。一旦机器从消息队列里读取了一条消息，这条消息就会永远从消息队列里消失。这时候如果机器刚好又重启，那么这条消息就会永远在系统中消失。
虽然现实中不会存在这么完美的消息系统，但是由于我们解决的不是消息系统的问题，在这里对消息系统做完美假设，这有利于让你关注分布式系统本身。
消息的最后一个假设是消息的接收是异步的。消息的接收顺序是完全随机的，并不是先到先得。这意味着你给一台机器发送两条消息，先发的消息可能后到。
正在运行的机器会不断地从队列里拉取消息。当队列里没有和它相关的消息时，系统会返回一个空消息。机器也可以根据空消息的情况来改变自己的状态。
到这里为止我们明确了论文对分布式系统里机器、共识和消息这3个术语的定义。为了方便你理解，我在这里举个例子。
假设分布式系统由A、B、C三台机器组成，初始值分别为1、0、0。系统在运行了一定时间之后，A给B和C发了两个不同消息，同时A输出结果为0。
B过了一定的时间后，收到了A给自己的消息。B这时候决定输出结果为0，现在A和B达成了共识，都输出了0。
C收到了A给自己的消息后，没有给外面发任何消息，也没有输出任何结果。C虽然一直在运行，但是没有输出任何结果，因此不满足共识算法的终止性。所以A、B和C这三个节点组成的分布式系统没能达成共识。
但是我们稍微改改对C的描述，结果就会大不一样。如果这时候C死机了，那么C就处于非运行状态。由于共识的定义对于非运行的机器没有任何要求，此时A、B和C组成的分布式系统就达成了共识。你可以再仔细体会一下两者的区别，下面是这个例子的示意图：
完成上面的定义后，我们终于可以对要证明的问题做一个准确概括了：在一个完全异步的分布式系统里，如果至少有一台机器可能会出问题，那么不存在非随机的共识算法。证明的过程分为三步。
第一步证明分布式集群存在一个特殊初始状态。我们无法通过这个初始状态预先知道共识结果，具体结果取决于哪些机器会在什么时候出问题。我们把集群的这个特殊初始状态称为非确定状态。
第二步，证明一旦存在一个非确定状态，系统在运行了一段时间后，一定还会进入下一个非确定状态。
第三步是将第一步、第二步合起来。从一个非确定性的初始状态开始，系统会运行到第二个非确定状态，然后会运行到下一个非确定状态，最后一直无限运行下去。这样就违反了共识算法的终止性，也就证明了不存在共识算法。
证明过程用了反证法，比较精妙。接下来，你需要紧跟我的思路，仔细体会论证过程。
当分布式系统处于某种状态时，如果我们能提前计算出最后的共识结果，那么这个状态叫确定性状态。反之，如果最后的共识结果取决于机器是否在线，这个状态就叫不确定性状态。
我们在这里需要证明的是，任意一个集群都存在一个非确定性的初始状态，即我们无法通过这个初始状态，判断最后的共识结果。
现在反证法开始了。反证法需要将需要证明的结论反过来描述，所以我们假设从所有初始状态开始，不管机器是不是出问题，我们都能提前计算共识结果。
我们先假设有一个初始状态的集合C（configuration），C包含了集群内所有机器的初始状态。比如下图画了3台机器和它们的初始状态集合C：
根据反证法的假设，我们能提前计算出最后的共识结果，所以上图的初始状态也会有一个共识结果，比如说为0：
接下来我们需要用到共识算法的第3个特性：有效性。有效性表示当我们遍历所有初始状态时，一定有的初始状态最终会产生共识结果0，也一定会产生共识结果1。简单起见，假设初始状态集合为C0的时候，共识结果为0。当初始状态为C1的时候，共识结果为1。
下面就是反证法最精妙的地方了。前面提到的C0和C1是关于集群的初始状态。这两个初始状态虽然不一样，但我们可以一步步将它们变成一样的，过程很简单。
先选出C0里的一台机器，它在C0和C1的状态不一样。然后，将C0的所有状态复制一份到新建的初始状态C2，并将C2里这台机器的状态变为它在C1里的状态。
接着，在C2里找一台和C0状态不一样的机器，建立一个新的初始状态C3，并将这台新机器的状态改变。以此类推，由于机器数目是有限的，最后一定会构建出一系列初始状态，它们之中只有一台机器的状态不一样。
举个例子，如下图所示，假设C0里的3台机器初始状态都是0，C0的共识结果为0。C1的所有初始状态都为1，共识结果为1。C2将C0里的第1台机器的初始状态从0变为1。C3将C2里的第2台机器的状态变为1。这样通过3次变化，我们最终可以将初始状态C0变为C1：
那么问题来了。在上面这个例子里，C2和C3所对应的共识结果应该是什么呢？其实不管它们对应的结果是什么，你会发现对于上面的4个初始状态，一定有相邻的2个初始状态，它们分别对应了0和1这两种不同的共识结果。你可以试试枚举所有共识结果的排列组合来验证。
我们假设C2和C3对应的共识结果都为0，这样C3和C1这两个相邻的初始状态集合，就会有不同的共识结果：
现在就到考验你的时候了。C3和C1只有第3台机器的初始状态不一样。如果这第3台机器从一开始就死机了，C3和C1的初始状态就会完全一样，这时它们俩都会产生怎样的共识结果呢？
下图展示了这个疑惑。反证法里假设过，集群的共识结果只和初始状态有关。那么如果第3台机器一直有问题，C1和C3的初始状态其实是一样的，那么它们俩会产生一样的共识结果，要么是0，要么是1。
如果最后结果都是0，那么C1在第3台机器不出问题时产生共识结果1，但是当这台机器出问题后，会产生不同的共识结果，这和我们反证法假设矛盾。如果最后结果为1，这样C3也会产生同样的矛盾。示意图如下：
按照同样的道理，我们可以证明任意数目的集群都会产生类似的矛盾。所以对于任意一个机器集群，一定存在一个特殊初始状态，它的共识结果取决于一台特殊机器是否正常运行。第一步证明结束。
第一步证明只用到了分布式系统的初始状态和最终结果，而第二步证明则需要用到分布式系统的中间状态。和这一节课最开始类似，在证明之前我们再做一个定义。
分布式系统里消息的接收是有顺序的，尽管接收消息的时间差可能会很短，但是依然有顺序差别。所以，我们可以给分布式系统状态的变化定个顺序，任何两个相邻的状态变化之间是新接收到的消息，这个状态变化的顺序叫作路径。
和第一步证明一样，分布式系统的状态也分为非确定性状态和确定性状态两种。系统可能从非确定性状态运行至确定性状态，但是反过来不行。路径和两种状态的示意图如下：
这里还要说到一个新的操作。由于消息系统是异步的，消息的接收可以任意延迟。下图展示了对于某一条路径，将第一个消息e一步一步往后挪时，系统的不同运行状态：
好，我们终于可以开始证明了。这里需要用到第一步的非确定性初始状态。
从这个状态开始，我们先随便选择一个消息，比如集群里可能会出现的任意一个消息e。接下来，我们从集群所有可能的中间状态中，选择两大类出来。
一类是从来没接收过消息e的状态，我们称之为C，另一类是刚刚接收过消息e的中间状态集合，称之为D。剩下的中间状态跟证明无关，可以忽略。
那么，我们接下来证明，在集合D里一定存在另一个非确定性的中间状态。示意图如下：
这里还是用反证法，我们假设集合D里所有的状态都是确定性状态。
非确定性的初始状态一定会有两条不同的路径，分别产生0和1这两个共识结果。如果这个初始状态所有路径的最终共识结果都一样，那么就没有非确定性了。对于产生共识结果0的路径，如果这个路径没有穿过集合D，那么表示路径在集合C里就结束了。
那么我们可以将消息e添加到这个路径的末尾。这样，构造出的新路径会穿过集合D。由于路径在添加消息e之前共识结果为0，那么添加消息e之后的共识结果也为0。这里用到异步消息的一个属性：既然消息e出现过，那么消息e的接收时间可以任意调整。
所以，一定有一条穿过集合D的路径会产生共识结果0。同理，也有一条会产生共识结果1。所以，集合D里所有状态不仅仅是确定性状态，它们一定能产生0和1两个共识结果。
接下来选取两条路径。一条是第一个消息是e的路径，假设对应的共识结果为0。由于初始状态是非确定性的，所以剩下的路径中，一定有一条产生不一样的共识结果。
如下图所示，我们选取另一条产生共识结果为1的路径。如果这个路径不穿过集合D，那么就可以按照上面的步骤，添加消息e到路径最后面，这样这条路径一定可以穿过集合D。
然后，我们调整第一个消息e的接收时间，一步一步往后挪，这时候会产生一些新的穿过集合D的路径。那么对于中间的几个可能的路径，它们的共识结果是什么呢？
不管这些路径的共识结果是多少，和第一步证明类似，我们一定可以在集合D里找到两个相邻的路径，而它们的共识结果刚好相反。
如下图所示，我们假设状态C0在收到消息e后会进入状态D0，D0最终输出共识为0。状态C0收到消息f后，会进入状态C1，C1收到消息e后，会进入状态D1，D1会输出共识结果为1。
到这里为止，最关键的4个状态我们已经找到了。反证法的下一步是对上图消息f和e进行分析，看看这两个消息的接收方是否一样。
我们接下来会证明，不管这两个消息的接收方是否一样，如果集合D的所有状态都是确定性状态，最终都会有逻辑矛盾。
下面进入分情况讨论的环节。首先我们先看看消息的接收方不一样是什么情况。
这时候，我们将上图D0和D1之间增加一个消息f，也就是把消息f的接收时间调整到消息e之后。这表示，我们有两条从C0状态到D1状态的路径。第一条是先接收消息f，然后接收消息e。第二条是先接收消息e，然后接收消息f。如下图所示：
这时候出现了一个悖论。消息e和f对应了两台不同的机器，它们互不影响，所以e和f的接收顺序并不影响最后的共识结论。那么，上图从C0到D1的两条不同路径，最终应该导致同一个共识结果。这样看来，这个菱形的关系是正确的。
但是请你注意，我们在反证法里假设了状态D0是个确定性状态，它不能既产生共识结果0，又在接收消息f后产生共识结果1，所以这个菱形关系和我们之前的反证法假设矛盾。
那我们再来看看如果e和f的接收方一样，又会出现什么情况。我们假设从状态C0开始，接收这两个消息的机器就出了故障，无法运行。系统在经过了一条路径g后，到达最终状态A，并且产生共识结果。因为无限路径和共识算法的终止性相矛盾，所以路径g的步数是有限的，。
如下图所示，状态A究竟会产生什么样的共识结果呢？
先看上图的左边，我们构造两个场景。第一个场景是这样的。假设分布式系统从状态C0通过路径g到达状态A之后，原来一直出问题的机器突然恢复了。碰巧这时候消息e也刚刚到达，分布式系统会到达一个新的状态E0。
另一个场景从状态D0开始。由于消息是可以任意延时的，我们可以将路径g贴在状态D之后，这样状态D0在经过路径g后，也会到达一个状态。那么问题来了，如下图所示，这两个场景最终会达到同一个状态E0吗？
答案是会的。接收消息e的机器在路径g中一直无响应，所以消息e和路径g没有共同的机器，两者之间互换顺序不会影响最终结果。因此上图左边的菱形是合理的。两条不同的路径都会到达同一个状态E0。
按照反证法的假设，D0是一个确定性的状态，最终生成的共识为0。所以E0最终会达到共识0，这也意味着状态A也应该达到共识0。
同理，我们也可以将右边用两条新的路径补全。一条是从状态A开始，添加一条f+e的路径。另一条是从状态D1开始，增加一条路径g。这样右边也会达到同一个状态E1。由于状态D1会达到共识结果1，状态E1也会到达共识1。下图画出了补全之后的情况：
所以A这个状态既可以达到共识结果0，也可以达到共识结果1。这意味着A是一个非确定性状态，这和我们前面假设A是一个确定状态相矛盾。
好了，到目前为止我们证明了，不管e和f这两个消息的接收方是否是一样的，如果集合D的所有状态都是确定性状态，最终都会有逻辑矛盾。所以反证法的假设不成立，也就是说，集合D里一定存在非确定性的状态。
证明的第三步是构造出一个不会终止的共识过程，构造过程很简单。按照第一步证明，存在一个非确定性的初始状态，和它对应的第一个接收消息e。如下图所示：
按照第二步的证明，我们能够找到下一个非确定性状态，这个状态刚刚接收了消息e。如下图所示：
这样每当到达了一个不确定性状态，我们可以将消息e往后挪，从而制造出下一个不确定性状态。由于这个过程可以永远重复下去，系统会永远处于非确定性状态，这就违反了共识算法的第一个特性终止性。示意图如下：
1996年的论文"Unreliable failure detectors for reliable distributed systems"证明了，如果在分布式系统里，存在一个能让你最终做出准确判断的不准确时钟，那么系统存在共识算法。这个时钟起到的作用是在分布式环境下，检测机器是否出问题。
失败检测分为两种属性：完整性和准确性。按照排列组合，一共有4种可能的情况：
1.强完整性。所有正确的节点都会最终怀疑每个出错的节点。
2.弱完整性。一些正确的节点都会最终怀疑每个出错的节点。
3.强准确性。所有正确的节点都不会被怀疑出了问题。
4.弱准确性。一些正确的节点不会被怀疑出了问题。
论文指出，就算只有很弱的失败检测，也能实现共识算法。你觉得这里的“弱”是指哪几种情况呢？
欢迎你在留言区跟我交流互动。如果学完这节课让你有收获的话，也欢迎你转发给同事、朋友，一起学习、探讨共识算法不存在的证明过程。
评论