区块链系统,首先是一个分布式系统。
从传统的集中式单节点结构,演变到分布式多节点结构,碰到的首个问题就是**一致性的保障。**本文将介绍分布式系统领域中两个很基础的概念:一致性和共识性。包括两者的定义,分类,区别与联系等等。全文按照如下结构展开:
一致性问题是分布式领域最为基础也是最重要的问题。
如果分布式系统能实现“一致”,对外就可以呈现为一个完美的、可扩展的“虚拟节点”,相对物理节点具备更优越性能和稳定性。这也是分布式系统希望能实现的最终目标。那么,让我们来看看“一致性”的定义和性质是什么吧!
一致性的定义
在分布式系统中,运行着多个相互关联的服务节点。一致性是指分布式系统中的多个服务节点,给定一系列的操作,在约定协议的保障下,使它们对外界呈现的状态是一致的。换句话说,也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案(Proposal)达成一致。
在学习过程中,一度被分布式事务一致性和分布式数据一致性这两种说法搞混淆。实际上,两者是从两种不同的角度对一致性的描述。
在这里,事务(数据库事务的简称)是数据库管理系统中执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成。
分布式事务一致性,指的是“操作序列在多个服务节点中执行的顺序是一致的”。分布式数据一致性,指的是“数据在多份副本中存储时,各副本中的数据是一致的”。保证了分布式事务的一致性,也就保证了数据的一致性。
一致性的要求
在分布式系统中,要达成的一致性,需要满足哪些要求呢?
也就是说,在分布式系统中,如果一个由节点提出的提案,能够用在有限的时间内,达到一致性的结果,我们就说该提案达到了一致性。
一致性的分类
一般来讲,分布式系统中的一致性(strong consistency)按照对一致性要求的不同,主要分为,严格一致性,强一致性,弱一致性和最终一致性这四大类。接下来按照这个下图架构一一说明:
严格一致性
在分布式系统中,有一种理想状态的“严格一致性”。
严格一致性的标准是,对于数据项x的任何读操作将返回最近一次对x进行的写操作的结果所对应的值。
严格一致性中存在的问题是它依赖于绝对的全局时间。对于所有的进程来说,所有写操作都是瞬间可见的,系统维持着一个绝对的全局时间顺序。如果一个数据项被改变了,那么无论数据项改变之后多久执行读操作,无论哪些进程执行读操作,无论这些进程的位置如何,所有在该数据项上执行的后续读操作都将得到新数值。
严格一致性,是在系统不发生任何故障,而且所有节点之间的通信无需任何时间这种理想的条件下,才能达到。这个时候整个系统其实就等价于一台机器了。在现实中,是不可能达到的。
实际上,越强的一致性要求往往会造成越弱的处理性能,以及越差的可扩展性。
强一致性
当满足强一致性时,满足如下要求:
当分布式系统中更新操作完成之后,任何多个进程或线程,访问系统都会获得最新的值。
一般来讲,强一致性(strong consistency)主要包括下面两类
顺序一致性是指任何执行结果都是相同的,就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的,并且每个进程的操作按照程序所指定的顺序出现在这个序列中 。
顺序一致性的介绍比较抽象,这里举一个例子来说明。
假设我们有两个线程(线程1和线程2)分别运行在两个CPU上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:
初始条件: x = y = 0;
因为多线程程序是交错执行的,所以程序可能有如下几种执行顺序:
当然上面三种情况并没包括所有可能的执行顺序,但是它们已经包括所有可能出现的结果了,所以我们只举上面三个例子。我们注意到这个程序只可能出现上面三种结果,但是不可能出现
r1==0 and r2==0
的情况。**所谓的顺序一致性,**其实就是规定了一下两个条件:
- 每个线程内部的指令都是按照程序规定的顺序(program order)执行的(单个线程的视角);
- 线程执行的交错顺序可以是任意的,但是所有线程所看见的整个程序的总体执行顺序都是一样的(整个程序的视角);
第一点很容易理解,就是说线程1里面的两条语句一定在该线程中一定是x=1先执行,r1=y后执行。
第二点就是说线程1和线程2所看见的整个程序的执行顺序都是一样的。
举例子就是假设线程1看见整个程序的执行顺序是我们上面例子中的Execution 1,那么线程2看见的整个程序的执行顺序也是Execution 1,不能是Execution 2或者Execution 3。
总结下来,顺序一致性,要求所有线程所见的整个程序的总体执行顺序是一样的。也就是说,顺序一致性保证的是对一系列地址访问的一致性。
顺序一致性实际上限制了各进程内指令的偏序关系,但不在进程间按照物理时间进行全局排序**。**
线性一致性假设操作具有一个全局有效时钟的时间戳,但是这个时钟仅具有有限的精确度。要求时间戳在前的进程先执行。线性化是根据一系列同步时钟确定序列顺序的 。
弱一致性是指系统并不保证后续进程或线程的访问都会返回最新的更新的值。系统在数据成功吸入之后,不承诺立即可以读到最新写入的值,也不会具体承诺多久读到。但是会尽可能保证在某个时间级别(秒级)之后。可以让数据达到一致性状态。也就是说,如果能容忍后续的部分或者全部访问不到,则是弱一致性。
最终一致性是弱一致性的特定形式。系统保证在没有后续更新的前提下,系统最终返回上一次更新操作的值。 也就是说,如果经过一段时间后要求能访问到更新后的数据,则是最终一致性。
在最终一致性的要求下,如果没有故障发生,不一致窗口的时间主要受通信延迟,系统负载和复制副本的个数影响。DNS是一个典型的最终一致性系统。
共识性的定义
共识性描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。 在实践中,要保障系统满足不同程度的一致性,核心过程往往需要通过共识算法来达成。
共识算法
共识算法解决的是对某个提案(proposal)大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛,如多个事件发生的顺序、某个键对应的值、谁是领导……等等。可以认为任何可以达成一致的信息都是一个提案。对于分布式系统来讲,各个节点通常都是相同的确定性状态机模型(又称为状态机复制问题,state-machine replication),从相同初始状态开始接收相同顺序的指令,则可以保证相同的结果状态。因此,系统中多个节点最关键的是对多个事件的顺序进行共识,即排序。
根据解决的是非拜占庭的普通错误情况还是拜占庭错误情况,共识算法可以分为Crash Fault Tolerance(CFT)类算法和Byzantine Fault Tolerance(BFT)类算法。
针对常见的非拜占庭错误的情况,已经存在一些经典的解决算法,包括Paxos、Raft及其变种等。这类容错算法往往性能比较好,处理较快,容忍不超过一半的故障节点。
对于要能容忍拜占庭错误的情况,一般包括PBFT(Practical Byzantine Fault Tolerance)为代表的确定性系列算法、PoW为代表的概率算法等。对于确定性算法,一旦达成对某个结果的共识就不可逆转,即共识是最终结果;而对于概率类算法,共识结果则是临时的,随着时间推移或某种强化,共识结果被推翻的概率越来越小,成为事实上的最终结果。
拜占庭类容错算法往往性能较差,容忍不超过1/3的故障节点。此外,XFT(Cross Fault Tolerance)等最近提出的改进算法可以提供类似CFT的处理响应速度,并能在大多数节点正常工作时提供BFT保障。
一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一致性、线性一致性,描述了多个节点对数据状态的维护能力。
共识性则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。
因此,一致性描述的是结果状态,共识则是一种手段。达成某种共识并不意味着就保障了一致性(这里的一致性指强一致性)。只能说共识机制,能够实现某种程度上的一致性。
实践中,要保障系统满足不同程度的一致性,核心过程往往需要通过共识算法来达成。
因此,一致性描述的是结果状态,共识则是一种手段。达成某种共识并不意味着就保障了一致性(这里的一致性指强一致性)。只能说共识机制,能够实现某种程度上的一致性。
实践中,要保障系统满足不同程度的一致性,核心过程往往需要通过共识算法来达成。