![]()
作为服务端开发的同学，你可能听说过Paxos、Raft这类分布式一致性算法，也在工作中使用过ZooKeeper、etcd等工具来解决一致性问题。但你可能不知道，这些算法和工具解决的并不是一致性中最难的问题，要讨论这个最难的问题，这就要追溯到 Leslie Lamport 1982 年发表的著名论文 《拜占庭将军问题》（The Byzantine Generals Problem ）上了。
![]()
1、拜占庭将军问题是什么？
拜占庭将军问题，其实是一个共识问题。通过比喻的方式来描述分布式一致性中一类最难的问题，这里大致叙述一下：
拜占庭帝国派出多支军队去围攻一个强大的敌人，每支军队有一个将军，但由于彼此距离较远，他们之间只能通过信使传递消息。敌方很强大，必须有超过半数的拜占庭军队一同参与进攻才可能击败敌人。在此期间，将军们彼此之间需要通过信使传递消息并协商一致后，在同一时间点发动进攻。
问题难点：困扰这些将军的问题，是他们不确定他们中是否有叛徒，叛徒可能会擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭的将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？
以上，这就是著名的拜占庭将军问题。
2、问题实质推演
回顾上述问题：
一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作， 达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。
注意，这里“一致性”才是拜占庭将军问题探讨的内容，如果本来叛徒数量就已经多到了问题不可解的地步，这个就是“反叛”的问题了；同时，我们的目标是忠诚的将军能够达成一致，对于这些忠诚的将军来说，进攻或者撤退都是可以的，只要他们能够达成一致就行。
但是，仔细想想： 光靠“一致性”就可以解决问题吗？
考虑一下，如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在他们都“一致性”没有进攻；反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在所有人都“一致性”进攻了。所以，我们还需要提出一个“正确性”要求。
那我们该如何定义这个“正确性”呢？
我们或许可以简单地说，正确就是每个忠诚的将军都正确的表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。最终，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并最终一致行动；而形式化的要求就是：“一致性”与“正确性”。
3、难题细化分析
介绍到现在，想必大家还是比较疑惑，我们以具体案例辅助解释一下：
我们把问题简化一下，假设只有三个拜占庭将军，分别为A、B、C，他们要决定的只有一件事情：明天是进攻还是撤退。为此，将军们需要依据“少数服从多数”原则投票表决，只要有两个人意见达成一致就可以了。
举例来说，A和B投进攻，C投撤退：
-
那么A的信使传递给B和C的消息都是进攻；
-
B的信使传递给A和C的消息都是进攻；
-
而C的信使传给A和B的消息都是撤退。
如此一来，三个将军就都知道进攻方和撤退方二者占比是 2 : 1 了。显而易见，进攻方胜出，第二天大家都要进攻，三者行动最终达成一致。
目前看来一切比较顺利，理解起来也非常简单。但是，假如三个将军中存在了一个叛徒呢？
叛徒的目的是破坏忠诚将军间一致性的达成，让拜占庭的军队遭受损失。
3.1 问题难点
假设A和B是忠诚将军，A投进攻，B投撤退，如果C是这个叛徒将军，那么C该做些什么，才能在第二天让两个忠诚的将军做出相反的决定呢？
目前看来，进攻方和撤退方现在是 1 : 1 ，无论C投哪一方，都会变成 2 : 1 ，一致性还是会达成。但是，作为叛徒的C，你必然不会按照常规出牌，于是你让一个信使告诉A的内容是你“要进攻”，让另一个信使告诉B的则是你“要撤退”。
至此，A将军看到的投票结果是：
进攻方 ：撤退方 = 2 : 1
而B将军看到的投票结果是：
进攻方 ：撤退方 = 1 : 2
第二天，忠诚的A冲上了战场，却发现只有自己一支军队发起了进攻，而同样忠诚的B，却早已撤退。最终，A的军队败给了敌人。
截止目前，你有没有发现，明明大多数将军都是忠诚的（2/3），却被少数的叛徒（1/3）耍得团团转？
实质上，“拜占庭将军”问题的可怕之处，恰恰在此：在一致性达成的过程中，叛徒将军（恶意节点）甚至不需要超过半数，就可以破坏占据多数的正常节点一致性的达成。
3.2 狡猾的叛徒
这时候，会存在你可能不相信甚至无法接受的一种情况：在大多数将军都是忠诚的情况下，却无法抓出这个为所欲为的叛徒。
还是上面的例子，假设A与B是忠诚的将军，C是叛徒将军。忠诚的将军经历了上次战役的失败，就已经发觉他们中出现了叛徒，但是并不知道具体是谁。
依旧是上面投票的例子，A投进攻，B投撤退，C传递给A和B两种不同的消息。
现在，我们从忠诚将军A的视角来看一下，他是如何做决策的。
A现在知道另外两人中可能有一个是叛徒，他收到了B的撤退消息和C的进攻消息，他应该如何分辨呢？
A可以问一下B：“我从C那儿收到的是进攻，你从C那儿收到的是什么？”
因为B是忠诚的将军，不会伪造信息，B会告诉A：“收到的是撤退。”
C发送了两条不同的消息，A现在也发现了这个问题，但是A现在就可以判断C是叛徒了么？
可悲的事情发生了，尽管忠诚的B说了实话，但是A反而对他产生了怀疑。因为从A的视角来看，B和C的说法不一致，他无法判断：
同样的情况，也会出现在B身上，两个忠诚的将军无法做正确的判断，而可以任意进行信息造假的叛徒C，此时只需要再次进行消息伪造：和A说“B告知我的消息是进攻”，和B说“A告知我的消息是撤退”，如此一来，就可以进一步把信息搞混，从而隐藏了自己是叛徒的真相。
![]()
综上所述，我们可以得出一个结论：在拜占庭三个将军中出现一个叛徒，并且叛徒可以任意伪造消息的情况下，只要叛徒头脑清醒，他就始终无法被发现，甚至还能造成整个系统的信任危机。
根据这一结论进一步推导可以得出一个更通用的结论，如果存在 m 个叛徒将军，那么当将军总数小于或等于 3m 时（n <= 3m，m代表叛徒将军个数)，叛徒便无法被发现，整个系统的一致性也就无法达成。
3.3 叛徒是否可被抓？
从上面的结论，可以看出，忠诚将军的人数是叛徒人数 2 倍的时候，依然不能找出叛徒，那么再多一个忠诚的将军呢？
为了简化问题，接下来假设有 4 个拜占庭将军，分别是A、B、C、D，其中有一个是叛徒。我们依然秉承找出叛徒的关键，即判断哪个将军发送了不一致的消息。
也就是说，接下来就是和其他接收到消息的将军进行信息的同步判断：是否收到的消息不一致。
现在，将问题再进一步简化，暂不需要考虑整个投票的过程，只需要考虑一个将军向其他三个将军各发送了一条命令，忠诚将军能否对这个命令达成一致的情况，为了区分发送命令的将将军和接收消息的将军，我们将发送命令的将军称为发令将军（M），将接收命令的将军称为副官（S）。
![]()
考虑下面两个问题：
这时候就出现了两种情况：
Case1：发令将军是叛徒
假设D是叛徒，向A和B发送了进攻，向C发送了撤退。现在，我们切入到A的视角。
A问B和C：“我从D那里收到的消息是进攻，你从D那里收到的是什么呢？”
B说是进攻，C说是撤退。
此时，从A的视角来看，C和D对同一条消息的说法是不一致的，那么他们两个人中肯定有一个是叛徒，但是A无法判断的是：
-
D给不同人发送了不一致的消息；
-
还是C伪造了D的消息。
好在，由于A知道最多只有一个叛徒存在。
那么根据反证法，如果B也是叛徒，就有两个叛徒存在，那么B肯定不是叛徒。
那么A和B至少在D发送的是进攻这一消息上，达成了一致，两者选择都是进攻。
B也是同样的情况，现在A和B彼此建立了信任，而同样是忠诚副官的C，最终则和真正的叛徒D被一同怀疑。
![]()
Case2：副官里有叛徒
假设C是叛徒，D给三个副官都发送了进攻，那么叛徒C应该怎样同步D的消息，才能分裂忠诚的发令将军和忠诚副官间的关系呢？
如果将D的消息原样转发出去，那么这一想法实施后也就无法再去当叛徒了。如果给A与B均发送和D相反的撤退消息，那么就回到了前文所讲的第一种情况，A和B认为D发送的是进攻，发送消息的D也认为自己发送的消息是进攻，忠臣们行动上又一次达成了一致。
然而，为了给系统增加更多的混乱，叛徒C决定再次发送不一致的消息，告诉B自己从D收到的是进攻，告诉A自己从D收到的是撤退。这种情况下，B看到所有人都认为D是进攻，会傻傻地认为大家是个团结一致的集体，没有叛徒。而A会发现C和D中出现了一个叛徒，不过A也再次可以确认B是自己人。此时，A决定再和B同步一轮消息，看看C是不是说了两个不一致的消息，这种情况下，叛徒C就完全暴露了。
![]()
由此可见，在多了一个忠臣的情况下，叛徒需要处处小心，才能避免被发现。与此同时，忠臣们即便在存在混乱信息的情况下，行动上也依旧达成了一致。根据推理，我们可以推导出一个结论：当忠臣的个数为 2m + 1 时，他们可以容忍 m 个叛徒产生的破坏。
总结
至此，拜占庭将军问题的白话解析版本就讲完了。
你应该已经知道了 m 个可以任意伪造消息的叛徒能够破坏规模最大为 3m 个将军的一致性。你也已经了解了叛徒是如何通过发送不一致的消息来制造混乱，以及忠诚将军又如何通过交换信息在混乱中保持一致的。
那么接下来让我们跳出拜占庭将军的比喻回到计算机的世界中。如果三个节点中有一个异常节点，那么最坏情况下两个正常节点之间是无法保证一致性的。
参考文章： https://zhuanlan.zhihu.com/p/65800882
![]()
延伸点
“拜占庭将军问题”可以进一步延伸到各个领域。
人们在互联网上进行数据交易的时候，总会习惯性依赖强大的第三方平台来进行信任担保。然而，这些解决人们信任问题的第三方正在逐渐失效，因为总有黑客能够抓住第三方平台的漏洞进行金融诈骗。
“拜占庭将军问题”中的“叛徒”就是互联网金融交易中的“骗子”，如果第三方平台出现了大漏洞或者为了规避过多的步骤将第三方信任机构撤走，“叛徒”就会利用信息在没有第三方信任机构的担保之下进行“行骗”。
在不去花费大量时间、资源揪出这个“叛徒”的情况下，能够让交易者双方都彼此信任、进行正常交易的方式就是区块链。
- END -
作者：架构精进之路，专注软件架构研究，技术学习与个人成长，关注并私信我回复“01”，送你一份程序员成长进阶大礼包，欢迎勾搭。
往期热文推荐：
![]()
「技术架构精进」专注架构研究，技术分享
Thanks for reading!
