HyperLedger Fabric共识算法

迷南。 2023-06-14 10:58 182阅读 0赞

当前在联盟链的应用场景中，使用的共识算法有3种：SOLO、Kafka和PBFT（拜占庭容错）。

## Solo模式 ##

在Hyperledger Fabric中的solo模式的共识算法，是最简单的一种共识算法，只有一个排序节点（order）接收客户端peer节点消息，并完成排序，按照order节点的排序结果进行生成区块和上链处理。此种模式只能在测试环境中使用，不适合生产环境大规模使用。

## Kafka模式 ##

由一组orderer节点组成排序服务节点，与Kafka集群进行对接，利用Kafka完成消息的共识功能。  
客户端peer节点向Orderer节点集群发送消息后，经过Orderer节点组的背书后，封装成Kafka消息格式，然后发往Kafka集群，完成交易信息的统一排序。如果联盟链中有多个channel，在Kafka中实现就是按照每个channel一个topic的设定，每个channel都有一条链。

## 拜占庭容错（PBFT） ##

此部分内容介绍摘自：[共识算法：PBFT、RAFT][PBFT_RAFT]  
PBFT算法的提出主要是为了解决拜占庭将军问题。什么是拜占庭将军问题呢？拜占庭位于如今的土耳其的伊斯坦布尔，是古代东罗马帝国的首都。拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封地都驻扎一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。 在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。  
要让这个问题有解，有一个十分重要的前提，那就是信道必须是可靠的。如果信道不能保证可靠，那么拜占庭问题无解。关于信道可靠问题，会引出两军问题。两军问题的结论是，在一个不可靠的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。  
在联盟链的场景下，默认信道都是可靠的。  
拜占庭将军问题最早是由Leslie Lamport与另外两人在1982年发表的论文《The Byzantine Generals Problem 》提出的， 他证明了在将军总数大于3*f ，背叛者为f 或者更少时，忠诚的将军可以达成命令上的一致，即3*f+1<=n。算法复杂度为o（n(f+1))。而Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年发表的论文《Practical Byzantine Fault Tolerance》中首次提出PBFT算法，该算法容错数量也满足3\*f+1<=n,算法复杂度为o（n^2）.  
因为PBFT算法的除了需要支持容错故障节点之外，还需要支持容错作恶节点。假设集群节点数为N，有问题的节点为f。有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。那么会产生以下两种极端情况：

*  第一种情况，f个有问题节点既是故障节点，又是作恶节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即f+1个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。也就是说这种情况支持的最大容错节点数量是（n-1）/2。
 *  第二种情况，故障节点和作恶节点都是不同的节点。那么就会有f个问题节点和f个故障节点，当发现节点是问题节点后，会被集群排除在外，剩下f个故障节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即f+1个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是f+1个正确节点，f个故障节点和f个问题节点，即3\*f+1=n。  
    结合上述两种情况，因此PBFT算法支持的最大容错节点数量是（n-1）/3。

### 算法基本流程 ###

PBFT算法的基本流程主要有以下四步：

*  客户端发送请求给主节点
 *  主节点广播请求给其它节点，节点执行pbft算法的三阶段共识流程
 *  节点处理完三阶段流程后，返回消息给客户端
 *  客户端收到来自f+1个节点的相同消息后，代表共识已经正确完成  
    为什么收到f+1个节点的相同消息后就代表共识已经正确完成？从上一小节的推导里可知，无论是最好的情况还是最坏的情况，如果客户端收到f+1个节点的相同消息，那么就代表有足够多的正确节点已全部达成共识并处理完毕了。

### 算法核心三阶段流程 ###

如下图所示：  
![三阶段流程][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU_size_16_color_FFFFFF_t_70]  
算法的核心三个阶段分别是pre-prepare阶段（预准备阶段），prepare阶段（准备阶段），commit阶段（提交阶段）。图中的C代表客户端，0，1，2，3代表节点的编号，打叉的3代表可能是故障节点或者是问题节点，这里表现的行为就是对其它节点的请求无响应。0是主节点。整个过程大致是：

*  首先，客户端向主节点发起请求，主节点0收到客户端请求，会向其它节点发送pre-prepare消息，其它节点就收到了pre-prepare消息，就开始了这个核心三阶段共识过程了
 *  Pre-prepare阶段：节点收到pre-prepare消息后，会有两种选择，一种是接受，一种是不接受。什么时候才不接受主节点发来的pre-prepare消息呢？一种典型的情况就是如果一个节点接到了一条pre-pre消息，消息里的v和n在之前收到里的消息是曾经出现过的，但是d和m却和之前的消息不一致，或者请求编号不在高低水位之间，这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的v和n，但d和m却不同的消息
 *  Prepare阶段：节点同意请求后会向其它节点发送prepare消息。这里要注意一点，同一时刻不是只有一个节点在进行这个过程，可能有n个节点也在进行这个过程。因此节点是有可能收到其它节点发送的prepare消息的。在一定时间范围内，如果收到超过2f个不同节点的prepare消息，就代表prepare阶段已经完成
 *  Commit阶段：于是进入commit阶段。向其它节点广播commit消息，同理，这个过程可能是有n个节点也在进行的。因此可能会收到其它节点发过来的commit消息，当收到2\*f+1个commit消息后（包括自己），代表大多数节点已经进入commit阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据  
    处理完毕后，节点会返回消息给客户端，这就是PBFT算法的全部流程。  
    为了更清晰的展现这个过程和一些细节，下面以流程图来表示这个过程：  
    ![在这里插入图片描述][20191119172526290.png]  
    注解：  
    V：当前视图的编号。视图的编号是什么意思呢？比如当前主节点为A，视图编号为1，如果主节点换成B，那么视图编号就为2.这个概念和raft的term任期是很类似的。  
    N：当前请求的编号。主节点收到客户端的每个请求都以一个编号来标记。  
    M：消息的内容  
    d或D（m）：消息内容的摘要  
    i： 节点的编号

### checkpoint、stable checkpoint和高低水位 ###

什么是checkpoint呢？checkpoint就是当前节点处理的最新请求序号。前文已经提到主节点收到请求是会给请求记录编号的。比如一个节点正在共识的一个请求编号是101，那么对于这个节点，它的checkpoint就是101.  
那什么是stable checkpoint（稳定检查点）呢？stable checkpoint就是大部分节点（2\*f+1）已经共识完成的最大请求序号。比如系统有4个节点，三个节点都已经共识完了的请求编号是213.那么这个213就是stable checkpoint了。  
那设置这个stable checkpoint有什么作用呢？最大的目的就是减少内存的占用。因为每个节点应该记录下之前曾经共识过什么请求，但如果一直记录下去，数据会越来越大，所以应该有一个机制来实现对数据的删除。那怎么删呢？很简单，比如现在的稳定检查点是213，那么代表213号之前的记录已经共识过的了，所以之前的记录就可以删掉了。  
那什么是高低水位呢？下面以一个示意图来进行解释。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU_size_16_color_FFFFFF_t_70 1]图中A节点的当前请求编号是1039，即checkpoint为1039，B节点的checkpoint为1133.当前系统stable checkpoint为1034.那么1034这个编号就是低水位，而高水位H=低水位h+L，其中L是可以设定的数值。因此图中系统的高水位为1034+100=1134。  
举个例子：如果B当前的checkpoint已经为1034，而A的checkpoint还是1039，假如有新请求给B处理时，B会选择等待，等到A节点也处理到和B差不多的请求编号时，比如A也处理到1112了，这时会有一个机制更新所有节点的stabel checkpoint ，比如可以把stabel checkpoint设置成1100，于是B又可以处理新的请求了，如果L保持100不变，这时的高水位就会变成1100+100=1200了。

### ViewChange（视图更改）事件 ###

当主节点挂了（超时无响应）或者从节点集体认为主节点是问题节点时，就会触发ViewChange事件，ViewChange完成后，视图编号将会加1。  
下图展示ViewChange的三个阶段流程：  
![在这里插入图片描述][20191119172842909.png]  
如图所示，viewchange会有三个阶段，分别是view-change，view-change-ack和new-view阶段。从节点认为主节点有问题时，会向其它节点发送view-change消息，当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到2*f个其它节点的view-change消息，则证明有足够多人的节点认为主节点有问题，于是就会向其它节点广播  
New-view消息。注意：从节点不会发起new-view事件。对于主节点，发送new-view消息后会继续执行上个视图未处理完的请求，从pre-prepare阶段开始。其它节点验证new-view消息通过后，就会处理主节点发来的pre-prepare消息，这时执行的过程就是前面描述的pbft过程。到这时，正式进入 v+1（视图编号加1）的时代了。  
为了更清晰的展现ViewChange这个过程和一些细节，下面以流程图来表示这个过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU_size_16_color_FFFFFF_t_70 2]  
上图里红色字体部分的O集合会包含哪些pre-prepare消息呢？假设O集合里消息的编号范围：（min～max），则Min为V集合最小的stable checkpoint，Max为V集合中最大序号的prepare消息。最后一步执行O集合里的pre-preapare消息，每条消息会有两种情况: 如果max-min>0,则产生消息<pre-prepare,v+1,n,d> ；如果max-min=0，则产生消息<pre-prepare,v+1,n,d(null)>。  
PBFT算法，核心过程有三个阶段，分别是pre-prepare（预准备）阶段，prepare（准备）阶段和commit（提交）阶段。对于pre-prepare阶段，主节点广播pre-prepare消息给其它节点即可，因此通信次数为n-1；对于prepare阶段，每个节点如果同意请求后，都需要向其它节点再 广播parepare消息，所以总的通信次数为n*（n-1），即n2\-n；对于commit阶段，每个节点如果达到prepared状态后，都需要向其它节点广播commit消息，所以总的通信次数也为n\*（n-1），即n2\-n。所以总通信次数为（n-1）+（n2\-n）+（n2\-n），即2*n2\-n-1，因此PBFT算法复杂度为O（n2）。  
对于PBFT算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人（2*f+1）都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。

[PBFT_RAFT]: https://www.cnblogs.com/linguoguo/p/10178196.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191119172252934.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU=,size_16,color_FFFFFF,t_70
[20191119172526290.png]: https://img-blog.csdnimg.cn/20191119172526290.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191119172716201.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU=,size_16,color_FFFFFF,t_70
[20191119172842909.png]: https://img-blog.csdnimg.cn/20191119172842909.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191119172924424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4bTAwN2xvdmU=,size_16,color_FFFFFF,t_70