加载中 ...

“共识”深入浅出学习

2019-09-10 04:35 编辑:币牛牛 来源:币源

“区块链(Blockchain)技术是一种多方维护,通过密码学保证传输和安全,实现一致、难以篡改、防止抵赖的记账技术,称为分布式账本技术。而区块链技术框架中非常重要的一部分是共识机制,是在不可信的分布式环境下实现数据一致性的关键。”



【百度超级链学院】今天为大家奉上一篇超强万字干货,由深受超级链开发者喜爱的“小X姐姐”撰文的“区块链共识机制演进及应用”,带大家一同了解共识机制的发展脉络与未来趋势预测。



本文详细解析了PoW、PoS、PBFT…等主流共识机制各自特点及优劣;也从单一共识向可插拔共识、从链式共识向图式共识、从确定性共识向随机性共识,归纳总结出了共识机制的发展趋势。此外,还有更多的知识点和独家观点等你来发现哦~



概述



1.1 区块链技术



2008年11月1日,中本聪发表了《比特币:一种点对点的电子现金系统》[1]一文,阐述了基于P2P网络技术、加密技术、时间戳技术、区块链技术等的电子现金系统的构架理念,标志着比特币的诞生。2009年初,中本聪搭建了以其论文为原型的网络——比特币。区块链技术是比特币网络背后的技术基础,是一种基础设施。区块链作为一种解决不可信分布式环境下能够以较低成本建立信任的计算模式和协作模式,正在悄然改变这个世界。



1.2 共识机制



由于区块链系统多数采用去中心化的分布式设计,节点是分散在各处,所以必须设计一套完善的制度,以维护系统的运作顺序与公平性,统一区块链的版本,并奖励提供资源维护区块链的使用者,以及惩罚恶意的危害者。这样的制度,必须依赖某种方式来证明,是由谁取得了一个区块链的打包权(或称记帐权),并且可以获取打包这一个区块的奖励;又或者是谁意图进行危害,就会获得一定的惩罚,这就是区块链系统的共识机制[2]。



区块链是一个去中心化的分布式系统,在该系统中,所有的节点都是一个全副本,维护着全部的账本数据。这样,当某一个或多个节点故障时,用户可以从其他的节点读取数据。由于系统中有多个副本,如何保证副本之间的一致性是整个分布式系统的理论核心,下面会详细地向大家介绍传统分布式系统和区块链系统副本一致性问题。



传统分布式系统一致性问题



2.1 分布式一致性问题



从传统的集中式单节点结构,演变到分布式多节点结构,碰到的首个问题就是一致性的保障。如何保障副本之间的一致性是整个分布式系统的理论核心。



一致性是指分布式系统中的多个服务节点,给定一系列的操作,在约定协议的保障下,使它们对外界呈现的状态是一致的。换句话说,也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案(Proposal)达成一致。



一致性的要求,在分布式系统中,系统可以达成一致性需要满足以下三个要求:



有限性:达成一致的结果在有限的时间内完成。
约同性:不同节点最终完成决策的结果是相同的。
合法性:决策的结果必须是系统中某个节点提出来的。



一般地,非学术角度,分布式系统一致性主要包括以下三类:



· 强一致性(Strong):数据a一旦写入成功,在任意副本任意时刻都能读到a的最新值。
· 弱一致性(Weak):写入一个数据a成功后,在数据副本上可能读出来,也可能读不出来。系统不能保证多长时间之后每个副本的数据一定达成一致。
· 最终一致性(Eventually):最终一致性是弱一致性的一种特例。写入一个数据a成功后,在其他副本有可能暂时读不到a的最新值,但在某个不一致的时间窗口之后保证最终能读到。不一致性窗口的大小依赖于以下几个因素:交互延迟、系统负载、复制协议的副本数。



2000年,Berkeley大学计算机科学家埃里克·布鲁尔提出了著名的CAP定理,指出对于一个分布式计算机系统,不可能同时满足以下三点[3]:



· 一致性(Consistency):所有节点访问同一份最新的数据副本,读操作总是能读取到之前完成的写操作结果,满足这个条件的系统就符合我们前面对强一致性系统的定义。



· 可用性(Availability):每次请求都能获取到非错的响应,但是不保证获取的数据为最新数据,读写操作在单台机器发生故障的情况下仍然能够正常执行,不需要等到故障的节点将数据迁移到新的节点。



· 分区容错性(Partition tolerance):以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。



根据定理,分布式系统只能满足三项中的两项而不可能满足全部三项。理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致,即丧失了C性质。如果为了保证数据一致性,将分区一侧的节点设置为不可用,那么又丧失了A性质。除非两个节点可以互相通信,才能既保证C又保证A,这又会导致丧失P性质。



随着系统规模逐渐变大,故障的发生会是一种常态,系统的设计必须要考虑容错(Fault Tolerant)。依据分布式系统的部署环境,容错主要包括两大类:一是可信环境下的分布式容错,即我们通常说的CFT(Crash Fault Tolerant);二是不可信环境下的分布式容错,即我们通常说的BFT(Byzantine Fault Tolerant)。下面两节会详细向大家介绍一下两类环境下的分布式一致性问题和容错方案。



2.2 可信环境分布式一致性问题



传统的分布式系统中,所有服务器掌握在一个公司或者组织内部,系统没有恶意节点,所有节点都是可信的,这样的分布式系统我们称之为可信环境分布式系统TEDS(Trusted Environment Distributed System)。



可信环境分布式系统容错即CFT,该类系统中,只需要考虑单机故障、磁盘故障等故障恢复场景。



可信环境分布式系统的一致性协议有很多,比较著名的包括两阶段提交协议、Paxos协议和Raft协议。



2.2.1 两阶段提交协议(2PC)



两阶段提交协议2PC(Two-phase Commit)[4]是指在计算机网络以及数据库领域内,为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法。



2PC协议只有在所有节点都同意提交事务后才会提交事务[5]。



2PC协议包括两类节点,分别是协调者(Coordinator)和参与者(Cohorts),节点间可以进行网络通信。该协议假设所有的节点都采用预写入日志的方式,且日志被写入后会持久化到可靠的存储设备上,这样即使系统故障,也不会丢失日志。该协议同时假设所有的节点不会永久性损坏,即使损坏后也可以恢复。



2PC协议主要包括2个阶段:



· 提交请求阶段:



这个阶段,协调者会向所有参与者询问“是否可以执行提交”操作,同时会开始等待各参与者节点回复。参与着执行协调者的事务操作,将操作信息写入日志。如果参与的事务操作执行成功,则返回“同意”消息,否则回复“终止”消息。



· 提交执行阶段:



当第一个节点所有参与着都回复“同意”时,协调者会向所有节点发出正式“正式提交”操作请求,参与者节点正式完成操作,并释放整个事务处理期间占用的资源,然后参与者会向协调者发送“完成”消息。协调者收到所有节点反馈“完成后”,事务完成。当第一个阶段有任何一个参与者返回“终止”的消息,或者存在参与着操作超时,则协调者会向所有参与者发出“回滚操作”,协调者收到所有参与者返回“回滚完成”后取消事务。

2PC协议在现实分布式系统一般都不采用,主要是由于其有一个显著的缺点,其事务的提交的过程中节点是处于阻塞状态的,及节点在等待其他节点返回时无法响应其他服务。并且如果出现参与者宕机或者无响应时,协调者需要通过超时机制来恢复,系统无法容错且低效。

2.2.2 Paxos协议

Paxos协议是Lamport于1989年的一篇论文[6]首次提出,由于该算法晦涩难懂,直到1998年该论文才得以发表。Lamport后续又发表了相关文章《Paxos Made Simple》和《Fast Paxos》[7][8],因此大家习惯性地将这类算法称为Paxos算法。

Paxos算法自问世以来就垄断了可信环境分布式一致性算法。众多分布式系统都采用了该算法实现分布式一致性,如Google的Spanner、Chubby、Megastore,还有开源的ZooKeeper等。

Paxos协议将系统中节点分为三类:

· 提议者(Proposer): Proposer 负责提出提案,包括提案标号和提案内容。
· 决策者(Acceptor):参与提案的决策,Acceptor收到提案后会根据情况决策是否要接受提案,若足够多的Acceptor接受提案,则该提案3通过。
· 决策学习者(Learner):不参与提案的提出或者决策过程,Proposer收到足够多的Acceptor同意后,会将通过的决议发送给所有的Learner。

Paxos算法主要包括两部分,为决议的达成和决议的发布,其中决议的达成又包括2个阶段,整个过程如下图所示:

上述图描述了Paxos算法的流程,如下所述:

· 决议提出与达成:

准备阶段(Prepare):Proposer选择一个提案标号Proposer ID并将prepare消息发送给Acceptors中的一个多数;Acceptor收到Prepare的消息后,如果提案标号大于它接受的所有历史提案的标号,就回复接受,并承诺不再接受提案标号小于该标号的提案。

批准阶段(Accept):当一个proposer收到了多数acceptors对prepare的回复后,就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求,Acceptor在不违背其他提案的前提下对收到的Propose请求进行Accept处理。Proposer在收到多数节点的accept消息后,提案就已经达成。

· 决议的发布(Publish):当提案已经达成后,Proposer会将该提案发送给所有的Learner。

2.2.3 Raft协议

Raft也是一种可信环境分布式一致性算法[9]。相比于Paxos算法,Raft更加容易理解和容易实现,他强化了领导人的概念,将整个分布式一致性问题抽象成了两大阶段,领导人选举(Leader Election)和日志复制(Log Replication)。

Raft协议中每个节点可能会处于三种状态:

· 领导者状态(Leader):Leader负责处理客户端的请求并将事务同步给Follwer。
· 跟从者(Follower):接受Leader的更新事务请求,并写入本地的日志文件。
· 候选状态(Candidate): 当Follower一段时间内没有接收到Leader的心跳,会认为Leader不可用,此时副本会进入Candidate状态,并开始新一轮选主,直到新的主被选择出来。

其状态转换图如下所示:

关键词:比特币新闻 币牛牛

转载自比特币新闻网(www.btc268.com),提供比特币行情走势分析与数字货币投资炒币最新消息。

原文标题:“共识”深入浅出学习

原文地址:http://www.btc268.com/news/qkl/15219.html

本文来源:币源编辑:币牛牛

本文仅代表作者个人观点,与本网站立场无关。

本网站转载信息目的在于传递更多信息。请读者仅作参考,投资有风险,入市须谨慎!

'); })();