分布式之PBFT算法

写在前面

在分布式之拜占庭问题 一文中我们分析了拜占庭问题，并一起看了支持拜占庭容错的口信消息性和签名消息性算法，但是这两种算法都有一个非常严重的问题，就是消息数量太多，通信的成本太大，消息数量复杂度为O(n ^ (f + 1))，其中f为判将数，所以导致这两种算法都不能在工程上实际落地，本文就一起来看下一个支持拜占庭容错的改进版本的算法PBFT，该算法的消息数量复杂度是O(n ^ 2),这个时间复杂度虽然也比较差，但要比O(n ^ (f + 1))好的多了，可以算得上是瘸子里的将军了。接下来我们就一起看下这位瘸子将军吧！

1：PBFT介绍

PBFT是一个支持拜占庭容错的分布式共识算法，其消息都是加密的不可篡改(这点类似秘钥消息型拜占庭问题之解)，假定叛徒数为f，总节点数为n，则二者需要满足3f + 1<=n，因为该系统假定叛徒的人数为(n - 1)/3，若叛徒人数不满足要求，则该算法将不使用，如总结点数为4，则最多允许有4-1/3=1个叛徒，当然没有或更少的叛徒肯定是可以的。另外该算法通过3阶段提交来达成共识，如下：

预准备阶段
准备阶段
提交阶段

语言不是很好描述每个阶段，我们接下来通过一个实际的例子来看下。

2：实例

4节点1叛徒场景。

假定我们有客户端苏秦，leader赵，follower魏，follower韩，follower楚（叛徒）,如下图：

假定苏秦某刻向楚发送进攻消息（即客户端向leader更新数据），如下图:

接着就进入到三阶段提交的第一阶段预准备阶段，分别向赵魏韩楚发出指令（同步客户端的更新），如下：

接着进入准备阶段，赵魏韩分别将受到的消息发送给对方，一旦某个节点收到了2f（这里因为f是1，所以就是2）个一致的消息时则进入到提交阶段，本例中叛徒楚因为其也不能伪造消息，所以就选择不发任何消息来扰乱达成共识的过程。如下图：

接下来进入提交阶段，告知其他节点自己已经准备到提交数据，当收到了2f+1（这里因为f是1，所以就是3）个消息时，则提交消息，如下图：

提交消息后返回成功给苏秦（leader），代表自己已经提交数据，当苏秦收到了f+1个提交的消息，则说明集群达成共识，如下图：

以上过程源码模拟参考这里 ，运行结果如下图：

3：交互次数分析

假定 13 节点集群中（f为4），则交互次数如下：

请求消息：1
预准备阶段：leader给所有的follower发消息，这里个数为13-1=12
准备阶段消息：只有可信节点才会发消息，可信节点数为8（不包括leader），因此发送消息数为8*12=96
提交阶段消息：除叛徒外的所有节点都要发送消息，因此总结点数是9（包括leader），因此发送消息数为9*12=108
回复消息：包括leader在内的所有非叛徒节点，都回复消息给客户端，因此消息数是9

因此总消息数就是226,可以看到消息交互次数还是蛮多的，但是支持拜占庭容错的要求本身就比较麻烦，所以该类算法都是比较耗时间的，有叛徒就是会比较麻烦。

写在后面

小结

本文分析了口信型拜占庭问题之解和签名消息型拜占庭问题之解因为消息通信量巨大而无法在工程上落地的问题，进而引入了本文分析的内容PBFT算法，并分析了其三阶段提交，预准备阶段，准备阶段，提交阶段，并给出了具体实例。希望本文能够帮助到你，也欢迎留言我们一起讨论。

参考文章列表

分布式之拜占庭问题 。