第六课：拜占庭将军问题

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。

假设有9位忠诚的将军，5位判断进攻，4位判断撤退，还有2个间谍恶意判断撤退，虽然结果是错误的撤退，但这种情况完全是允许的。因为这11位将军依然保持着状态一致性。2个间谍怎么破坏状态一致性呢？他们跟5位判断进攻的将军说, 我们支持进攻，那么这5位将军统计发现7位支持进攻，4位支持撤退，将发动进攻。又跟4位撤退的将军说，我们支持撤退，一统计，5票进攻, 6票撤退，立马撤退。这场战争必输无疑了。

同样的，分布式数据库最糟糕的问题绝对不是写入或者读取失败，而是状态不同步，还感知不到。这个的后果就是correctness不能保证，那程序就没有任何意义了。避免这种状态不同步的问题，我称之为“广义拜占庭将军问题”。

为了解决这个问题，数学家设计了一套算法，让将军们在接到上一位将军的信息之后，加上自己的签名再转发给除自己之外的其他将军。在这样的信息连环周转中，将军们可以在不找出叛徒的情况下达成共识，从而保证得到的信息和作出的决策是正确的。

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是卡斯特罗和利斯科夫在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上。

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。

同所有的状态机副本复制技术一样，PBFT对每个副本节点提出了两个限定条件：（1）所有节点必须是确定性的。也就是说，在给定状态和参数相同的情况下，操作执行的结果必须相同；（2）所有节点必须从相同的状态开始执行。在这两个限定条件下，即使失效的副本节点存在，PBFT算法对所有非失效副本节点的请求执行总顺序达成一致，从而保证安全性。

该算法有四方面突破，第一，首次提出在异步网络环境下使用状态机副本复制协议，第二，使用多种优化使性能显著提升，第三，实现了一种拜占庭容错的分布式文件系统，最后一点，它为副本复制的性能损耗提供试验数据支持。

PBFT其实就是一种防拜占庭容错的共识算法。共识算法有很多种，且有不同的适用环境，我们需要学会辨别，究竟哪些算法适用于哪些环境，这样也能一定程度上辨别一些空气项目。