共识算法:分布式系统的一致性

所谓一致性,就是指数据要完整、要同步。比如,我们在网上下了 个订单,付了款,商城系统会记录下这些数据,之后无论我们在哪里访 问自己的订单,都能看到同样的结果,即便商城系统出了故障,那一般 也会返回一个错误提示而不是给我们一个不一样的结果。再比如银行, 我们存了一笔钱进去,无论到哪里,我们查询银行账户的时候金额也不 会变。也就是说,在这些系统中,数据的结果总是一致而同步的,即便 这些系统的服务器不止一台,但都属于同一个中心集群,在内部是可以 高效一致同步的。

区块链系统本质就是一个分布式应用软件。分布式系统的首要问题 就是如何解决一致性的问题,也就是如何在多个独立的节点之间达成共 识。要注意的是,这里说的是要达成一致,而没有说保证一定要结果正 确,比如所有的节点都达成失败状态也是一种一致,说白了就是要成为 一致行动人。如果是中心化的场景,达成一致几乎没有任何问题,但分 布式环境并不是那么理想的,比如节点之间的通信可能是不可靠的、会 有延迟、会有故障,甚至节点直接宕机。而在无数个节点之间,如果采 用同步的方式来调用,那等于失去了分布式的优点,因为绝对理想的一 致性,代价通常是很大的。这样一个模型,通常要求不发生任何故障, 所有节点之间的通信没有任何时差,这几乎就等于是一台计算机了,这 样的强一致性往往意味着性能较弱。

历史经验表明,多路处理器和分布式系统中的一致性问题是非常难 以解决的。难点在于以下几个方面。

1〕分布式系统本身可能出故障。

2〕分布式系统之间的通信可能有故障,或者有巨大的延迟。

3〕分布式系统运行的速度可能大不相同,有的系统运行很快,而 有些则很慢。

但是,一致性是设计分布式系统时必须考虑的问题。一致性问题历

史悠久,而且臭名昭著。传统处理一致性问题的方法有两段式提交、令 牌环、时间戳等,计算机专业的读者应该有所耳闻。本章将集中讨论与 区块链相关的一致性问题和算法。

一致性问题

我们用状态机来解释一致性的问题。所谓状态机是表示有限个状态 以及在这些状态之间的转移和动作等行为的数学模型,状态可以特指某 个系统在某一时刻的数据变量,它具备以下几个特点:

  • 状态总数是有限的;

  • 任一时刻,只处在一种状态中;

  • 某种条件下,会从一种状态转变到另一种状态。

比如进销存系统中某一个时刻的库存状态,银行系统某一时刻的账 户状态等,对于分布式系统来说,就是指每个节点拥有的数据状态。假 设我们有^台机器,位于不同位置的机器之间通过网络协同工作,所有 机器的初始状态是一模一样的。给它们一组相同的指令,我们希望看到 相同的输出结果,而且希望看到状态的变化也是一样的。比如机器甲的 状态是从状态八到8再到匕而如果机器乙的状态是由八直接到^,这种 情况就是不一致的。

总而言之,一致性要求分布式系统中每个节点产生同样的结果或者 具备同样的状态,看起来就好像是一台机器一样,前提是没有一个中心 服务器作为调度员,这对于分布在互联网上、不在同一个机房内、不属 于同一个管理者的分布式系统来说,难度是很大的。出于系统的可用性 考虑,对于分布式系统来说,我们一般希望具备以下能力。

1〕分布式系统作为一个逻辑整体,不应该返回错误的结果。

2〕只要系统里的大部分机器工作正常,整个分布式系统就能有效 运行,这也是分布式系统应用的一个优点,抵抗单点故障。

3〕系统的性能是可以横向扩展的,对于分布式系统来说,木桶原 理不起作用。

4〕分布式系统必须是异步的,也就是说每个节点可以按照自己的 时序独立工作,没有全序的时间顺序。

要达到这些要求,可是不容易呢!从生活中我们也可以发现,即便 有统一的命令指挥,尚且不一定能完全做到整齐划一,何况是没有这么 一个指挥员呢!在互联网的场景中,任意一个节点的状态,我们都是没 法去强力管控的,比如比特币节点,谁能控制网络中的那些节点呢!可 能就是关闭了、断网了,甚至是一个恶意伪装的节点。一切看起来似乎 无解。然而实际上,很多时候我们对一致性的要求并没有那么迫切,在 一定的约束下,可以实现所谓的最终一致性,也就是说在某个时刻系统 达到了一致的状态。这个节点现在断网了,没问题,等恢复后跟上,通 过其他节点来同步自己的数据;那个节点宕机了,也没问题,恢复后跟 上。只要整个网络中绝大部分的节点都是正常工作的,整个系统总能在 未来的某一个时刻达成数据状态的一致。

两个原理:FLP与CAP

1.FLP定理

叫?'[口是因为提出该定理的论文是由朽5也^^ 7^也和化他1'50^三位

作者在1985年发表的,取了各自名字的首字母作为定理名称。看下定 义:在网络可靠、存在节点失效(即使只有一个〕的最小化异步模型系 统中,不存在一个可以解决一致性问题的确定性算法。在这个原理的前 提下,也告诉人们:不要浪费时间去为异步分布式系统设计在任意场景 下都能实现共识的算法,在允许节点失效的情况下,纯粹异步系统无法 确保一致性在有限时间内完成。

这个其实也很好理解,比如三个人在不同房间回答问题,虽然三个 人彼此之间是可以通过电话沟通的,但是经常会有人时不时地开小差, 比如八11⑶和8013都回答了某个问题,[办收到了两者的回答结果,然后 玩游戏去了,忘了回复,则三个人永远无法在有限时间内获得最终一致 的答复。这个定理在理论上证明了此路不通,也就节省了后来者的研宄 时间。

2.CAP定理

CAP定理最早是由价化8比〜^在2000年八^…组织的一个研讨会上提

出猜想,后来也等人进行了证明。我们还是先来看下定义:分布式 计算系统不可能同时确保一致性、可用性和分区容错性,这三者不可兼 得。通过定义我们可以知道,这是一个典型的不可能三角。那么这三个 术语具体是什么意思呢?含义如下。

  • 自一致性:所有节点在同一时刻能够看到同样的数 据,即“强一致性”。

  • 自可用性:确保每个请求都可以收到确定其是否成功 的响应,并且是在有限的时间内。

  • 分区容错性(口3他10^ 101613^^6〕:因为网络故障导致的系统分区 不影响系统正常运行,比如1号模块和2号模块不能使用了,但是3号和4 号依然能提供服务。

直觉上的论证很简单:如果网络分成了两半,我在一半的网络中给 八发送了 10个币,在另外一半的网络中给8发送了 10个币,那么要么系 统不可用,因为其中一笔交易或者全部两笔都不会被处理,要么系统会 变得没有一致性,因为一半的网络会完成第一笔交易,而另外一半网络 会完成第二笔交易。

既然不能同时满足,那么如果弱化对某个特性的支持呢?

〔1〕弱化一致性

比如软件升级新版本后,过一段时间其他人才更新成功;再如网站 更新内容后,浏览器也是刷新后才显示更新内容。很多时候对于实时的 强一致性并没有很高的要求,生活中也有这样的例子:如果事情不那么 紧急,就会发个短消息或者发个邮件,等对方看到了再处理;如果紧急 的话,就直接打电话,所以说电话是一种强连接方式,不过很多朋友肯 定不喜欢时不时地就有电话打进来吧。

〔2〕弱化可用性

有些场合对一致性非常敏感,比如银行取款机,一旦系统故障就会 拒绝服务,再如飞机上的控制系统,这个时候如果不能实时处理,那可 是要命的。对计算机使用比较熟悉的朋友都知道,很多服务器操作系统 都是不带图形界面的,只能靠命令行来处理,因为服务器要提高性能, 保持可靠,会尽量避免加载不必要的模块,这也是一个牺牲可用性的例 子。

〔3〕弱化分区容错性

对于分布式系统来说,分区容错是必然的,幸运的是这种情况出现 的概率并不是很大。如果真的是大规模的服务不可用,那无论是什么样 的系统都是不能正常工作的。

计算机系统的设计,有时候跟生活中的场景是很类似的,你不得不 做出一些妥协以便保证自己最想要得到的结果。区块链系统中,尤其是 公有链系统,使用各种共识算法,优先的目的就是要保证整个系统的容 错能力,这也是设计为分布式或者去中心结构的目的之一。

拜占将军问题

拜占庭将军问题的经典描述是:拜占庭的军队是由小分队组成的, 每个小分队由一个将军指挥,将军们通过传令兵来策划一系列的行动。 有些将军是叛徒,他们会有意地妨碍忠诚的将军达成一致的计划。这个 问题的目标是使忠诚的将军达成一致的计划,即使背叛的将军一直在诱 使他们采用糟糕的计划。已经证明,如果背叛的将军超过了将军总数的 1/3,达成上述目标是不可能的。特别要注意的是,要把拜占庭将军问 题和两军问题区分开。两军问题的模型要比拜占庭将军问题简单,并且 设立的前提场景也有差别,我们来看一幅示意图:

拜占将军问题

如上图所示,在此问题模型中,假设有两支对抗的军队(一支为八 军,一支为8军),这也就是所谓的两军。人军被8军隔开为两个部分, 分别是左八军和右八军。从战斗力来说,八军的两个部分必须同时合力进 攻才能打败8军,这就要求八军的左右两支分队必须要协商好进攻时间 和一些进攻的其他约定,协商就意味着要通信,通过两边的互相通信来 保持进攻指令的一致性。那么问题来了,左右两边的八军要互相通信, 就必须经过8军的区域,这就很难保证通信是畅通的,两边必须要不断 发送回执来确认对方是否收到了消息,很显然,从理论上来讲,任何一 次的回执都没法真正确认双方的消息接收是一致的。比如左八军发送了 消息给右八军,右八军接收到了并且发送了确认回执给左八军,可是确认 回执被8军阻截了,此时左八军无法知道右八军到底收到消息没有,即便 右八军的回执成功到达了左八军,可是若没有左八军的回执(左八军的回 执也可能被8军阻截〕,右八军同样无法确认左八军到底收到回执没有。 按照这种确认模式,只要有8军的阻截存在,左右两边八军就没法在理 论上保证总是能达成一致的消息确认。

我们可以看到,两军问题的关键点在于:两点之间的信道传输不可 靠。我们日常使用的大多数网络通信软件〔支付、聊天、发送邮件等) 其实都会面临这样的问题,通信过程发生在互联网,谁也没法保证中间

经过的“B军”是可靠的,一般也只能通过有限次数的双方回执来确认消 息的到达,这也是一个不得已的折中方案。值得注意的是,在这个问题 模型中,并没有去假设中间是否存在故意破坏者,也就是在两军的通信 过程中,不考虑某一方可能叛变的情况。回到拜占庭将军问题,其考虑 的主要问题在于通信的各方(不一定是两军,也可能是多军〕存在故意 破坏者或叛徒的情况下,大家如何来保持正确的一致性的问题。

拜占庭容错

拜占庭将军问题的复杂性,可以用计算机容错学里的概念来表述。

1〕拜占庭容错:这是最难处理的情况,指的是有一个节点压根就 不按照程序逻辑执行,对它的调用会返回随意或者混乱的结果。要解决 拜占庭式故障需要有同步网络,并且故障节点必须小于1/3,通常只有 某些特定领域才会考虑这种情况,通过高冗余来消除故障。

2〕崩溃容错:它比拜占庭容错多了一个限制,那就是节点总是按 照程序逻辑执行,结果是正确的,但是不保证消息返回的时间。不能及 时返回消息的原因可能是节点崩溃后重启了、网络中断了、异步网络中 的高延迟等。

3〕遗漏容错:它比崩溃容错多了一个限制,就是一定要“非健 忘”。非健忘是指这个节点崩溃之前能把状态完整地保存在持久存储 上,启动之后可以再次按照以前的状态继续执行和通信。比如最基本版

本的?3X05,它要求节点必须把投票的号码记录到持久存储中,一旦崩 溃,修复之后必须继续记住之前的投票号码。

4〕崩溃停止容错:它比遗漏容错多了一个故障发生后要停止响应 的要求。简单讲,一旦发生故障,这个节点就不会再和其他节点有任何 交互,就像它的名字描述的那样,崩溃并且停止。

共识算法的目的

在有错误的进程存在并且有可能出现网络分区的情况下,定理 堵死了我们在传统计算机算法体系下提出解决方案的可能性。计算机科 学家就想,如果我们把?定理的设定放松一点,问题是否有解呢?由 社会学和博弈论中得到启发,科学家尝试引入了以下机制。

1〕激励机制。比如,在拜占庭将军问题中给忠诚的将 军以奖励。当背叛的将军发现背叛行为没有任何收益的时候,他们还有 背叛的动机吗?这里引进了博弈论的概念:我们不再把节点或者说将军 分成公正丨恶意(忠诚丨背叛〕两方,认为每一个节点的行为是由激励机 制决定的。正如两千年前中国诸子百家热烈争论的话题:人之初,性本 善焉,性本恶焉?我们认为,人之初,性无善无恶。性的善恶由后天的 激励机制决定。如果激励机制设置得当,考虑到每个节点都有最大化自 己利益的倾向,大部分的节点都会遵守规则,成为公正的节点。

2〕随机性。在拜占庭将军问题中,决定下一步行 动需要将军们协调一致,确定统一的下一步计划。在存在背叛将军的条 件下,忠诚的将军的判断可能被误导。在传统的中心化系统中,由权威 性大的将军做决定。在去中心化的系统中,研宄者提出一种设想:是否 能在所有的将军中,随机地指定一名将军作决定呢?这个有点异想天开 的设想为解决拜占庭将军问题打开了一扇门。根据什么规则指定做决定 的将军呢?对应到金融系统里,就是如何决定谁有记账权。

1〕根据每个节点(将军〕的计算力来决定。

谁的计算力强,解开某个谜题,就可以获得记账权(在拜占庭将军问题 里是指挥权〕。这是比特币里用的pow共识协议

2〕根据每个节点(将军〕具有的资源来决定。所用到的 资源不能被垄断,谁投入的资源多,谁就可以获得记账权。这是pos共 识协议

出于上面的考虑,科学家引入共识算法,试图解决拜占庭将军问 题。分布式共识协议具有以下两点属性:

1〕如果所有公正节点达成共识,共识过程终止;

2〕最后达成的共识必须是公正的。

下面我们来谈谈共识算法的适用范围。区块链的组织方式一般有以 下3种。

1〕私有链:封闭生态的存储网络,所有节点都是可信任的,如某 大型集团内部的多数公司。

2〕联盟链:半封闭生态的交易网络,存在对等的不信任节点,如 行业内部的公司八、8、〔等。

3〕公有链:开放生态的交易网络,即所有人都可以参与交易,没 有任何限制和资格审核。

由于私有链是封闭生态的存储网络,因此使用传统分布式一致性模 型应该是最优的;由于联盟行业链的半封闭、半开放特性,使用 delegated proof of xxx是最优的;对于公有链,pow界应该是最优的选择。

常见共识算法一览表:

共识算法一览表

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。