首先我们知道有两种故障容错类型：拜占庭容错(BFT)和崩溃容错(CFT)。

共识算法一般在分布式系统中经常使用，而且我们这学期也在想学习MapReduce、Spark、Flink这类框架。其实，区块链系统也是一种分布式系统，因为在区块链中每个节点独立运行交易，不同的节点可能运行在地理上分离的区域，而有些节点可能存在恶意、可能发生故障。

因此，区块链系统作为一个整体应该对外提供可靠、可用、一致性的服务，但处理结果的一致性是基础。

分布式系统分为同步和异步分布式系统。

同步分布式系统需要严格满足：

（1）节点运行指令的时间有严格的上限和下限；

（2）消息能够在有限的时间内传输到目标节点；

（3）每个节点有一个本地时钟，与实际时间的偏移率在一个已知的范围内。

同步分布式网络就像两个人打电话，只要不挂断，一个人就必须等待在那边听声音

对于运行在广域网上的区块链系统来说，上述约束条件很难满足(因为区块产生的速度比较慢)，而且区块链网络中的节点可能在空间上的距离不等。因此区块链系统一般采用异步分布式系统(弱同步)。

异步分布式系统具有如下性质：异构性、并发性、可靠性、可用性、缺乏全局时钟、故障独立性

异步分布式系统存在一些限制：

异步模型对运行速度和消息延迟没有任何假设，这就要求区块链系统中的模型和算法不应立足于某些限制进行设计。就好比发微信，我看到了别人发来的微信，才会回复，而不是一直抱着手机等在那边

一致性问题

可靠性问题

在集中式系统中，一旦出现单点故障，就只能让系统重启，任务会被搁置。分布式系统就解决了这个问题，分布式系统需要首先保证高可靠、高可用性。由此，在分布式系统中需要有多个节点。

假设系统中有n个节点，其中最多有f个节点可能崩溃，在剩下的n-f个好的节点中，从节点i提交一个区块$B_i$(输入值)开始，所有节点要遵循相同的协议，从全部提交的区块中选择一个区块(一致性结果，决策值)，并用该去快提交到区块链系统

从多个节点输入值中选取一个决策之就称为共识，达成共识过程中所遵循的协议就是共识算法

共识需要满足的条件

故障容错是指区块链系统中节点和通信信道都有可能出现故障，导致部分节点不可用或者偏离被认为正确的结果或行为。

不同故障的影响：“遗漏故障”，“随机故障”，“时序故障”（时序故障主要针对同步分布式系统，对执行时间、通信时间和时钟漂移均有限制）。

遗漏故障是指节点或通信信道不能完成它应该做的动作，就是崩溃了。也称为CFT。在异步环境下，由于对节点的运行速度和消息传递延迟没有限制，因此我们无法判断消息到底是在路上，还是节点已经崩溃。这种情况被称为可变消息延迟。区块链系统中共识算法的设计应该基于可变消息延迟的模式

遗漏故障在异步分布式系统中是比较难解决的——无论是节点还是通信，都难以判断其是否发生了故障。

随机故障也称为拜占庭故障，用于描述可能发生的任何类型故障，如故意返回错误结果或者处理的结果本身就是一个错误的。

因此在基于拜占庭故障的共识算法在设计时，除了考虑拜占庭节点是否返回结果，还需要考虑返回错误结果的情况，因此基于拜占庭的共识算法通常要求不超过1/3的出错节点，就是考虑到即使1/3的正常节点和1/3的故障节点对冲后，仍然有多数1/3能够使算法形成共识

FLP不可能原理：当允许存在节点失效的情况下，不存在一个确定性的共识算法总能在异步模型下达成一致。就连POW也不是确定性的，也可能存在一条链被推翻的情况

但是，在同步模型下，由于其对节点处理时间、消息传递、始终都有要求，很容易判断是否失败，从而决定是否重传或者其他方式进行故障排除。

FLP原理实际上说明对于允许节点失效的情况下，纯粹的异步系统无法确保一致性在有限的时间内完成。即便对于非拜占庭错误的前提下，包括Paxos、Raft等共识算法都存在无法达成共识的情况。

但是，在工程实践中，在付出一些代价的情况下，获得高效的共识算法还是很有必要的。具体付出什么代价，共识算法能达到什么程度，往往通过CAP原理进行衡量。

在这篇博客数据库扩展性问题中学习过，这边再复习一下

CAP 原理是指在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance），三者不可兼得。

用如下系统进行解释

一致性的要求就是，在没有达到全部同步之前，是没有办法向客户提供服务的。

系统中非故障节点收到的每个请求都必须有响应

即可用性，所有的节点都保持高可用性。注意，这里的高可用还包括不能出现延迟，比如如果某节点由于等待数据同步而阻塞客户端请求，那么节点就不满足高可用性。也就是说，任何没有发生故障的服务必须在有限的时间内返回合理的结果集。

允许网络丢失从一个节点发送到另一个节点的任意多条消息，即不同步 。常常会发生在分布式系统出现网络故障的时候，但由于网络是脆弱不稳定的，因此分区容错性常常必不可少

我们举个例子，比如A、B两个机房构成一个分布式集群，如果A和B机房之间的网络不通了，那么一个分布式集群就会拆分成A和B两个集群。如果出现了分区，那肯定保证不了数据的强一致性。

分区容忍性是在物理上进行保证的，比如说在海底铺设多条光缆，出现光缆故障的概率较小且难以完全避免。因此我们只能在AC之间做一个trade-off，这是由业务场景决定的

有人会问，就不能保证AC吗？那就需要非常严格的全体一致协议，不能容忍网络错误或者节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不知道对面的那个结点是否挂掉了。

事务的ACID我们已经不陌生了，那么区块链中的ACID是什么样的呢？

在计算机网络中中，还有一个很重要的理论：BASE (Basic Availability ,Soft-state, Eventual Consistency 三个短语的缩写)

这个原则与ACID相对，就是说牺牲掉对一致性的约束(最终仍然实现一致性)，来换取一定的可用性。BASE理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性

BASE理论是对CAP中一致性和可用性权衡的结果(牺牲一致性，换取可用性)、其来源于对大规模互联网系统分布式实践的总结，是基于CAP定理逐步演化而来的。

BASE理论面向的是大型高可用可扩展的分布式系统，和传统的事务ACID特性是相反的，它完全不同于ACID的强一致性模型，而是通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。

在实际的分布式场景种，由于不同业务单元和组件对数据一致性的要求是不同的，因此在具体的分布式系统架构设计过程中，ACID特性和BASE理论又往往会结合在一起

Paxos算法是基于消息传递且具有高度容错的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。该算法能够解决分布式网络中存在遗漏故障，并且故障节点数小于总节点数的1/2的场景下的共识问题。

在我的这篇博客已经写的很详细了Raft

PBFT常常运用于联盟链当中，进入联盟链需要一个CA(合法性证明)。在公链系统中，共识是通过POW实现的，但是由于POW需要消耗大量能源，因此饱受诟病。在联盟链中，由于存在一定的信任基础(CA)，使得共识可以通过PBFT算法实现，其主要原理就是CPU投票。

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。它解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，是的拜占庭容错算法在实际系统应用中变得可行。

PBFT算法是基于状态机复制理念(听起来很耳熟，raft也是这个原理)设计的一个使用的并能解决拜占庭容错的算法，当存在f个失效节点时必须保证存在至少3f+1个副本，才能保证在异步分布式系统中达成共识，并且算法满足安全性和活性要求，即提供 $(n-1)/3$ 的容错性

在采用PBFT算法的区块链系统中，每个节点维护服务在本节点的状态(区块链)及相关服务操作(交易)，这里的服务被称为在系统中不同节点之间复制(消息传输)的状态机，包含状态和操作。

整个系统共同维护一个状态，并在不同节点之间赋值，所有的节点采取一致的行动，从而满足分布式系统的一致性要求。状态机在每个节点的复制体称为副本，每个节点都有一个完整的副本，所有副本的集合用R表示，每个副本用$R_i~ ,R_i\in(0\sim|R|-1)$ 表示。

同所有的状态机复制技术一样，PBFT对每个副本节点提出了两个限定条件：

视图可以理解为Raft当中的任期，其视图编号也是连续的。

视图是一次成功地节点配置轮换过程。在一个视图中，会根据算法来确认一个副本作为主节点(primary),其他副本作为备份(backups)。

但是与Raft算法竞争Leader不同，PBFT算法中，主节点由公式 $p=\text{v mod |R|}$ 计算得到，这里v是视图编号，p是副本编号，$|R|$ 是副本集合的个数。因此，在PBFT中，是轮流做庄的，谁当Leader是确定的。

主要用于分配基于本视图的消息序列号(全局编号)，从而对分布式系统的消息进行全局排序。进而，所有副本会按照视图编号、序列号的顺序处理消息，变更状态，使得所有副本的状态保持一致

使用加密和签名技术来防止欺骗攻击和重放攻击，以及检测被破坏的信息。但是，对消息本身的错误、消息的延迟或者不响应则要通过共识算法来防止。

因此，算法中消息包含了公钥签名、消息摘要等安全信息及检测消息重复的消息验证编码(MAC)。

算法中，使用m表示消息，$m_i$表示由节点i签名的消息，$D(m)$ 表示消息m的摘要。

客户端c向主节点发送请求 , 请求执行状态机操作o。

客户端发起消息之后，副本会给客户端一个Reply，响应格式是： ，其中v是视图编号，t是时间戳，i是副本节点的编号，r是请求执行的结果。

主节点接收到来自客户端的请求之后，按照三阶段协议，会向全网广播该消息。主要包括预准备(pre-prepare)、准备(prepare)和确认(commit)三个阶段

我们看到，由于大家都知道主节点是谁(通过视图号v取模运算得出)，因此客户端直接向主节点发起请求。这是request阶段

由上图可知，预准备阶段主节点给予当前视图v分配一个序列号n给收到客户端请求，然后，向所有备份节点群发送预准备消息。

这个消息格式为: ，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。

注意，客户端请求本身是不包含在预准备的消息里面的，其目的有两个：

备份节点收到预准备信息后，需要开始验证、检查一些内容：

一旦某个备份节点 i 接收并验证了预准备信息，那么它就会进入准备阶段

节点i开始准备阶段之后，会向所有副本节点发送准备消息，并将预准备消息和准备消息在节点i进行保存。

当节点i收到来自其他节点的准备消息，那么当满足如下条件时

副本节点i将 (m,v,n,i) 保存到本地并标记为Prepared状态，即为prepared(m,v,n,i) 。其中

当变更为prepared(m,v,n,i) 之后，节点i 向其他副本节点广播格式为 的确认消息，于是协议进入确认阶段。

我们看到，每个节点在接收到信息之后，又会向全体节点发送消息。因此消息的复杂度到达了$O(n^2)$

在确认阶段，每个副本节点接收确认消息并写入消息日志，具体条件为：

当副本节点i接收到2f+1个m的确认消息、并都满足上述条件之后，消息m会变更为committed-local状态，记为 committed-local(m,v,n,i)。具体条件为：

当消息m在节点i的状态为committed-local(m,v,n,i)时，节点执行m的请求，节点i的状态能够确保所有编号小于n的请求一次顺序执行。在完成m的请求操作之后，每个副本节点都会向客户端发送回复

副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。

当节点i的消息m变更为committed-local(m,v,n,i)时，对于分布式系统来说，消息m会变更为commited(m,v,n) 。也就是意味着，任意f+1个正常副本结点集合中的所有副本节点i ，其prepared(m,v,n,i)为真。这就确保了所有正常节点以同样的顺序执行所有请求，确保了节点状态的复制并保证了算法的正确性

节点状态变化路线 ：

一轮投票可以不可以？ 在不换主或者主节点不作恶的情况下，是可以的，但是我们举一个极端的例子：

在分布式系统下，假设现在少部分进入prepared阶段，另外一些节点还没有进入prepare阶段。此时， 若主节点是恶意节点的话，它可以改变原来的信息，将m修改为具有相同序号的m’,并获得大多数未提交的节点的同意。

但是，如果有两轮投票的话，两轮就可以保证一致性。

为了节省存储，系统需要一种将日志中的无异议消息记录删除的机制：算法设置周期性的检查点协议，将系统中的服务器同步到某一个相同的状态，同时可以定期地处理日志、节约资源并及时纠正服务器状态。

在PBFT算法中，会保存所有接收到的消息并记录到日志中，如果日志不能及时清理，会导致奈统资源被大量的日志占用并影响系统的性能和可用性。

另一方面由于拜占庭节点的存在，算法不能保证每个节点执行了相同序列的请求，因此所有节点状态可能不一致。

当副本节点i接收到的请求消息的序号可以被某个常数（如100）整除时会周期性向其他节点广播检查点消息 , 这里n是最近一个影响状态的请求序号，d是状态的摘要。

每个副本节点都默默地在各自的日志中收集并记录其他节点发过来的检查点消息，直到收到来自2f+1个不同副本节点的具有相同序号n和摘要d的检查点消息。

算法将这些请求执行后得到的状态称作检查点 (checkpoint)并且将具有证明的检查点称作稳定检查点 (stable checkpoint)。每个副本节点保存了服务状态的多个逻辑版本：包括最新的稳定检查点，零个或者多个非稳定的检查点，以及个当前状态。

节点确认某个检查点为稳定检查点后，然后副本节点就可以将所有序号小于等于口的预准各、准备和确认消息从日志中删除。同时也可以将之前的检查点和检查点消息一并删除。

这两个高低值限定了可以被接受的消息。水线的低值h与最近稳定检查点的序列号相同，而水线的高值$H=h+k$，k需要足够大才能使副本不至于为了等待稳定检查点而停顿。假如检查点每100个请求产生一次，k的取值可以是200。

图中A节点的当前请求编号是1039, B节点的请求编号是1133

当前系统的stable checkpoint 为1034，那么这个1034 就是低水位；而高水位$H=h+L$， 即1134

我们看到，A和B的请求编号在高水位和低水位之间，因此这两个请求都会被应答

如果B的请求编号位1135，那么说明B节点处理得很快，跑到很前面去了，这时候B就会停止应答，一直到其编号落入新的高低水位之间。

在PBFT算法中，主节点承担消息序号分配、请求转发等核心功能。因此一旦主节点发生了错误，就会导致系统无法正常运行

视图更换协议就是确保主节点失效时算法的活性。

视图更换的触发可以通过备份节点中一个请求的超时执行触发。当一个节点i的超时产生时，会启动视图更换，并将视图编号v变更为v+1,同时不再接受处检查点消息、视图更换消息和新视图消息以外的其他消息请求

这时候，节点i 会向其他副本节点广播视图更换消息

然后，会通过公式 $p = \text{v mod |R|}$ 计算得到主节点p，当主节点p收到2f个来自其他复制节点的有效的视图更换消息之后，节点p向其他复制节点广播新视图消息

V包含主节点收到的2f+1个有效的视图更换消息(包括主节点p本身发送的视图更换消息)

Q包含有效的预准备消息（不包括请求消息），其范围通过以下算法获得：从集合V中获取最小的稳定检查点序号min_s和最大的稳定检查点max_s，主节点p为min_s到max_s中间的每个序号n在新的视图v+1中创建新的预准备消息。

示意图如下：

通过视图更换协议，是的即使拜占庭节点被称为主节点，也能在视图变换后确保分布式系统的一致性

在PBFT算法中，通过一下四个方面来确保分布式系统中的共识：