技术 | 分布式系统的共识算法和容错

谢谢大家今天抽出时间来听这个分享。

今天的分享内容是和大家分享分布式系统和共识算法的基础理论、基本问题，以及相应的性能对比。

一、分布式系统的基本问题

现在让我们从第一个部分分布式系统开始。

图1

简单地说，分布式系统就是一组通过网络进行通信的节点，然后它们可以协调完成共同的任务。

从图1右侧部分可以看出，之前的中心拓扑是一个中心服务器在中间，节点围绕它（中心服务器）呈星形分布。

在分布式系统中，比如区块链，每个节点都是平等的，拥有相同的权利，没有中央服务器和终端的区别。

这里有一些主要的问题，比如每个节点都启动并运行了吗？ 如果它不能正常工作，它可能会崩溃；

节点之间的通信主要通过网络进行，网络可能存在延迟、不稳定、中断等情况；

第三种情况是现在最难解决的问题，即一些恶意节点对全网发起攻击，比如我们常说的“双花攻击”。

图 2

在解决上述问题之前，首先要对它进行建模和抽象，这里主要是形式化模型； 从网络的角度，分布式系统模型可以分为两类：同步模型和异步模型；

它们之间有什么区别？ 如图2中的表格所示，首先是每个节点自身的时钟漂移。 对于同步模型来说，虽然每次漂移每个节点的时钟都不一样，但是时钟差异其实是有上限的，但是对于异步模型来说，其实是没有这个上限的。

网络传输时间也是，对于同步模型来说，在两个节点之间，可以保证消息能够在一定时间内准确到达，但是对于异步模型来说，这个延迟的上限是无法确定的。

另一个是节点的计算速度。 一般来说比特币的共识算法是什么，同步模型中每个节点的速度几乎是一样的，但是对于异步模型，节点的计算速度也是不可预测的。

刚才的表格（图2）主要从网络模型的角度列出了分布式系统的分类；

从故障模型来看，如果只是节点崩溃或者网络宕机，就称为非拜占庭故障。

如果存在恶意节点，则为拜占庭故障。 这种拜占庭故障很难解决，如果要在拜占庭问题下达成共识，算法的复杂度和消耗的通信性能都远超非拜占庭故障。

2.分布式系统理论

先说一下这个分布式系统的基本原理。

不可能性原理主要有两个，一个是FLP不可能性原理，（三个字母FLP是发表这个定理的作者的首字母缩写）问题是基于前面的异步模型，即使是最小的模型，即使有最简单的故障模型，没有确定性算法可以解决一致性问题。 这里的关键点是最简单的模型，没有确定性算法。

图 3

第二个不可能原则是 CAP 原则。 尤其是在传统或者经典的分布式系统中，大家对这个定理都非常熟悉。 例如，在一个系统中不可能同时保证强一致性、可用性和分区容错性。 如果是在实际情况下，根据工程特点，弱化其中一个特性，保证另外两个特性。

三是BASE理论。 它是CAP原理的延伸，CAP理论具有很强的一致性； 用BASE理论来说，BA是基本可用性，S是软状态，E是最终一致性。

图 4

比如比特币，它的共识其实就是最终一致性。 例如，在某个时刻，不能保证当前区块一定是有效确认的区块。 每个区块产生后，都需要经过一定时间后进行确认。 时间越长，这个区块越有可能成为有效区块。 大，这就是最终的一致性。

通过这三个特性，可以在牺牲一些一致性约束的情况下，获得一些符合实际要求的分布式系统。

3. 分布式系统共识算法

有了前面的基本问题，模型从这些问题中抽象出来，从理论上保证了哪些问题无法解决，哪些问题可以实现，以及如何达到一定的性能要求。

结合这些问题和前面的基础，如何解决这个分布式系统中的共识问题，需要一个共识算法。

基本上比特币的共识算法是什么，共识算法目前分为三类：

图 5

第一类，Paxos用于解决非拜占庭分布式异步网络共识问题；

第二类，BFT用于解决拜占庭传统的分布式异步网络共识问题；

第三类，POW，用于解决拜占庭区块链分布式异步网络共识问题；

前两种在传统的分布式系统中比较常用，可以保证网络中的正常运行，正常工作的网络中的节点数量一般都比较少。

如果我们要做一条公链，从技术发展的角度来看，POW是第一个可以支持数万节点甚至更大节点的共识算法。

后面会讲这些算法的联系和区别，为什么说POW可以支持上万个节点，而前面两种算法都支持不了，只能支持比较少的节点。