consensus.basic.md

共识算法之：起源

前言

在区块链大热的当下，“共识算法”一词被频繁的提及。凡是区块链相关的项目，几乎都会提及共识算法一词，而对于做区块链平台的项目，那就必须要说清楚其使用的共识算法模型，否则不可能获得别人的认可。那么到底什么是共识算法，它是如何产生的，共识算法为什么在区块链项目中拥有如此重要的江湖地位，它的功能到底是什么，区块链是否可以不要共识算法？

对于共识算法的问题非常多，我们无法在一篇文章中都说清楚。带着这一系列的疑问，本文先探讨第一个问题：共识算法是如何演变而来的？当我们知道了共识算法的成长经历，我们也就可以理解共识算法是为何而生，就可以做到知其然也知其所以然。

区块链，从本质上来说是一个分布式系统，所以要了解共识算法，我们先从分布式系统说起。

计算系统的演进

任何事物的出现，都是为了解决某一个特定的问题。那些不能解决任何问题的事物，是没有生命力的，从而无法长期生存下去。共识算法也是为了解决某一个特定问题而诞生的，要理解这个特定的问题，我们需要从计算系统的演进开始。

计算机最初被发明出来的时候，是一台独立的个体，而且在最初几十年的发展历程中，都是以一台一台个体的形式出现的。在这个阶段中，所有数据的输入、处理、存储、输出都在一台计算机上完成。因为数据只存在于一台机器上，所以只要在这一台机器上是正确的，就可以了。如果希望把数据从一台机器上转移到另外一台机器，只能通过人工的方式把数据copy到外置存储设备（比如：软盘甚至是更古老的设备，那个时候还没有U盘），然后再从这个外置存储设备copy到另外一个计算机上去。

随着网络的出现，情况变得有些不一样了。数据从一台计算机copy到另外一台计算机，现在可以通过网络传输，而不是必须通过外置存储设备这个中转媒介了。在这个阶段，数据量都还比较小，确保数据从一台计算机传递到另外一台计算机之后不发生变化的方法，只需要确保网络传输正确就可以了。

当网络从最初的简单形态发展到互联网时代，尤其是若干互联网巨头的发展，每家巨头都拥有庞大而复杂数据的时候，如何保证数据在不同的计算机上都是相同的这一个问题，已经变成了一个非常复杂的课题。伴随着这一课题的出现，发展出了一个全新的领域，分布式计算。

确保数据在不同计算机上相同的课题，有了一个专门的术语，叫做 数据一致性(Consistency)。

在这个大规模互联网应用阶段，数据一致性的概念也扩展了。从最初的仅仅是把数据从一台计算机传输到另外一台计算机，发展到了在两台或者多台计算机上执行相同序列的一系列指令之后得到的结果也是相同的。

如果数据在不同的计算机上不一致，会带来什么样的后果呢，这个要根据应用的类型，以及数据的含义而确定。有些数据无关紧要，而有些数据则至关重要。

举一个例子：

我们来考察一个信用卡支付系统在一个水果店的使用场景。由于信用卡系统已经是一个非常庞大的系统，拥有上亿的用户，相应的数据量也极其庞大，使用一台计算机显然无法存储这样的海量数据。另外从数据备份的角度考虑，也不能把所有数据只存储在一台计算机上，任何数据都需要存储在多台不同的机器上，既要把为用户提供的服务分散到不同的计算机上，也要考虑到一旦某台机器出现故障之后，在其他的机器上还有备份的数据，这样可以保证为用户提供持续不断的服务，并且确保用户的数据正确。既然任何数据都备份到了多台机器上，这里就必须要处理数据的一致性问题。

有一个水果店，他有一个用于收款的信用卡账户，初始余额为100元，“余额”这个数据就是存储在多台计算机上的。一个顾客前来购买了15元的苹果，并且通过信用卡付款。顾客付款之后，信用卡系统需要从顾客的账户里面扣除15元，在水果店的账户中添加15元。存储顾客账户“余额”的多台计算机都需要执行一致的操作，即：扣除15元，然后更新余额数据，保证更新结束之后，多台计算机上的“余额”是一致的。同样，存储水果店账户“余额”的多台计算机也需要相应的增加15元，并且保证添加完成之后，多台计算机上的“余额”是一致的，都是115元。假设有一台机器出错(暂时不讨论出错原因)，余额变成了116元，而其他机器都是115元，这个时候水果店的“余额”这个数据在多台计算机上就不相同了，结果出错，即：数据一致性没有得到保证。对于水果店来说，他的信用卡账户里面到底是115元，还是116元呢？这就变成了一个至关重要的问题。

对于这一种类型的数据，其一致性就必须要获得保证，否则会带来灾难性的后果。

保证水果店信用卡账户的“余额”在所有机器上都是一样的，115元，把这个结果所呈现的状态称为数据一致性。而从顾客付款开始，到最终达到“一致性”这个结果的中间过程，称为**“共识算法”**。

一致性描述的是结果的状态，而共识算法则是如何达成一致性的手段。

上述付款的过程，就是一次典型的分布式系统的状态更新过程。下面我们来看看分布式系统的几个基础知识点。

几个基础概念

节点(Node)： 分布式系统是由一个一个的节点所组成。节点一般是指运行的一个软件的进程(process)，如果一台物理计算机只运行了一个进程，那么这台计算机就代表了一个节点。相应的，如果运行了多个进程，就代表了多个节点。

副本(Replica/Copy)： 虽然现代计算机硬件的故障率已经非常低，但并不是说完全没有故障，工程实践表明，计算机系统是肯定会出现故障的。所以对于分布式系统来说，任何数据都不能只保存在一台机器上，必须要保存在多台机器上，以保证数据不丢失以及对用户提供服务的连续性。相同的数据保存在多台机器上，每一份数据都称作是一份副本。一般来说，一个节点会对应一份数据副本。

提案(Proposal)： 保存相同数据的不同节点都应该具有相同的初始状态，任何一个要改变这些状态的请求，称为一个提案(proposal)。比如前述例子中，顾客刷卡这个动作就产生了一个提案，这个提案请求改变两个账户的状态，顾客的账户减去15元，而水果店的账户增加15元。

一致性(Consistency)： 对于存储在多个不同节点上的数据副本，都要保证是相同的。对于信用卡的网络来说，从收到这个提案(要求改变两个账户的状态)开始，共识算法就开始工作，共识算法需要确保，在所有相关的节点上，这两个账户的状态改变，要么全部同时成功，要么全部同时失败。无论成功还是失败，也无论是正确还是错误，只要所有相关节点的结果是相同的，就说达成了一致性。

分布式系统的常见问题

节点故障： 指的是组成分布式系统的节点出现“宕机”或者“假死”的现象。根据经验来看，每个节点都有可能发生故障，可能会由于硬件导致、由系统软件导致、或者由应用软件导致。

通信异常： 由于分布式系统依赖于通过网络来传递消息，而网络本身是不可靠的，随时都有可能发生数据丢失或者延迟的现象。网络光纤、路由器、DNS等等网络中的每一个环节都有可能导致通信故障，所以消息丢失和消息延迟在分布式系统中非常普遍。

网络分区： 俗称“脑裂”，由于通信异常的存在，导致部分节点之间的通信极大的延迟甚至中断，最终整个分布式系统之中的部分节点能够正常通信，而另外的部分则不能，在这种情况下，整个分布式系统被动的被划分为若干个小的子网络。在极端情况下，某些子网络能够独立完成原先需要整个分布式系统才能完成的工作。这个时候对数据一致性提出了严重的挑战。

三态： 这是分布式系统特有的现象，即：成功、失败、超时。在单机系统的时代，一个操作要么成功，要么失败。而在分布式系统中，由于通信异常的存在，有些操作，不知道是成功了，还是失败了，这种现象称为超时。主要有以下两种情况：

1. 消息没有成功的发送到接收方
2. 消息成功的发送到了接收方，但是接收方发送回来的反馈消息丢失，发送方收不到反馈消息

在发生超时的情况时，发送方无法确定接收方的执行结果是成功还是失败

分布式系统的几个基本原理

FLP不可能原理： 即使在网络通信可靠的情况下，对于可扩展的分布式系统，没有一个通用的共识算法能够解决任意场景下的一致性问题。

这个原理是说，在任意的分布式系统下，总是存在着某种异常，导致无法设计出通用的共识算法。当然这是极端的情况，在工程应用上，极端情况并不会总是出现，有些时候，多尝试几次，就成功了，哈哈 ~~~

CAP原理： 这个原理说明，对于一个分布式系统来说，无法同时满足以下三个特性：

• Consistency(C)：一致性，即确保分布式系统的数据一致
• Availability(A)：可用性，即给用户提供的服务一直可用，对用户提出的每一次请求，都能够在有限的时间内返回有效的结果
• Partition tolerance(P)：分区容错性，在发生网络分区的时候，仍然能够对外提供满足一致性和可用性的服务

ACID理论： 这是一个著名的描述分布式数据库对数据一致性要求的原则，其主要特征是：

• Atomicity(A)：每次操作都是原子性的，要么成功，要么不执行
• Consistency(C)：数据一致性是确定的，没有中间状态
• Isolation(I)：各种操作之间，彼此是隔离的，互不影响
• Durability(D)：状态的改变是持久的，不能丢失

BASE理论：

• Basically Available(BA)：基本可用，在分布式系统出现故障的时候，允许损失部分可用性，比如返回时间长一些等
• Soft state(S)：软状态，也称为弱状态，指的是系统中的数据存在中间状态，并且这个中间状态不会影响到系统的整体可用性
• Eventually Consistent(E)：最终一致性，指的是系统中的所有数据副本，在经过一段时间的同步之后，最终能够达到一个一致的状态

分布式系统、共识算法、区块链之间的关系

前面简述了分布式系统的基础知识，共识算法在分布式系统中的核心功能，就是确保在不同节点上的数据副本的一致性。

区块链，从本质上来说首先是一个分布式系统，所以在分布式系统上的各种问题，在区块链上也天然存在。在区块链的每一个节点上都保存有一份数据副本，对于全节点来说是一份完整的副本，对于轻节点来说是一部分数据的副本。共识算法就是确保在区块链不同节点上的数据副本一致性的算法。

共识算法的要求

共识算法在达成一致性的过程中，需要满足如下要求：

• Termination：需要在有限的时间内达成一致性的结果

  对前面的例子(通过信用卡购买苹果)来说，需要在一个有限的时间内，比如说一分钟，达成一致性的结果，而不能是一个太长的时间。对于这个例子来说，如果需要一天的时间才能达成一致性的结果，那么这个系统就不具备实用价值

• Agreement：不同的机器最终完成的结果是相同的

  这个在前述例子中已经说明了

• Validity：不同机器最终达成的结果必须是某一个机器提出的提案

  这些不同的机器最终达成的结果，都是来自于顾客在水果店的刷卡动作，这个刷卡动作就产生了一个提案

与分布式系统相同，区块链的共识算法就是要在区块链的节点之间，达成区块链数据的一致性。

小结

本文本着知其然亦知其所以然的出发点，着重介绍计算系统的演进，以及伴随而来的共识算法的演进过程。紧接着介绍了分布式系统的几个基本问题。对于具体的共识算法，我们会在后续的文章中逐步给出，敬请期待~~