广告

问题定义 对区块链的作用

问题定义

在分布式系统中,一致性(consensus,早期叫 agreement)问题是指对于系统中的多个服务节点,给定一系列操作,在一致性协议保障下,试图使得它们对处理结果达成一致。

如果系统能实现一致性,对外就可以呈现是一个功能正常的,但性能和稳定性都要好很多的“虚处理节点”。

需要注意,这个一致性并不代表正确与否,所有节点都达成失败状态也是一种一致性。

举个例子,某影视公司旗下有西单和中关村的两个电影院,都出售某电影票,票一共就一万张。那么,顾客到达某个电影院买票的时候,售票员该怎么决策是否该卖这张票,才能避免超售呢?当电影院个数更多的时候呢?

这个问题在人类世界中,看起来似乎没那么难,你看,英国人不是刚靠 投票 达成了“某种一致性”吗?

挑战

在实际的计算机系统(看似强大的计算机系统,很多地方都比人类世界要脆弱的多)中,存在如下的问题:

  • 节点之间的网络通讯是不可靠的,包括任意延迟和内容故障;
  • 节点的处理可能是错误的,甚至节点自身随时可能宕机;
  • 同步调用会让系统变得不具备可扩展性。

要解决这些挑战,愿意动脑筋的读者可能会很快想出一些不错的思路。

为了简化理解,仍然以两个电影院一起卖票的例子。可能有如下的解决思路:

  • 每次要卖一张票前打电话给另外一家电影院,确认下当前票数并没超售;
  • 两家电影院提前约好,奇数小时内一家可以卖票,偶数小时内另外一家可以卖;
  • 成立一个第三方的存票机构,票都放到他那里,每次卖票找他询问;
  • 更多……

这些思路大致都是可行的。实际上,这些方法背后的思想,将可能引发不一致的并行操作进行串行化,就是现在计算机系统里处理分布式一致性问题的基础思路和唯一秘诀。只是因为计算机系统比较傻,需要考虑得更全面一些;而人们又希望计算机系统能工作的更快更稳定,所以算法需要设计得再精巧一些。

要求

规范的说,一个分布式的一致性算法应该满足:

  • 可终止性(Termination):一致性的结果在有限时间内能完成;
  • 一致性(Consensus):不同节点最终完成决策的结果应该相同;
  • 合法性(Validity):决策的结果必须是其它进程提出的提案。

第一点很容易理解,这是计算机系统可以被使用的前提。需要注意,在现实生活中这点并不是总能得到保障的,例如取款机有时候会是“服务中断”状态,电话有时候是“无法连通”的。

第二点看似容易,但是隐藏了一些东西。算法考虑的是任意的情形,凡事一旦推广到任意情形,就往往有一些惊人的结果。例如现在就剩一张票了,中关村和西单的电影院也分别刚确认过这张票的存在,然后两个电影院同时来了一个顾客要买票,从各自“观察”看来,自己的顾客都是第一个到的……怎么能达成结果的一致呢?记住我们的唯一秘诀,核心在于需要把这两件事情有能力进行排序,而且这个顺序还得是大家都认可的。

第三点看似绕口,但是其实比较容易理解,即达成的结果必须是节点执行操作的结果。仍以卖票为例,如果两个影院各自卖出去一千张,那么达成的一致就是还剩八千张,决不能是票售光了。

带约束的一致性

做过分布式系统的读者应该能意识到,绝对理想的一致性很难达成。除非不发生任何故障,所有节点之间的通信无需任何时间,这个时候其实就等价于一台机器了。实际上,越强的一致性要求往往意味着越弱的性能。

很多时候,人们发现对一致性可以适当放宽一些要求,在一定约束下实现一致性,从弱到强分别有如下几种:

  • 顺序一致性(Sequential Consistency):Leslie Lamport 1978 年提出,是一种较弱的约束,保证所有进程自身执行的实际结果跟指定的指令顺序一致。例如,某进程先执行 A,后执行 B,则实际得到的结果就应该为 A, B,而不能是 B, A,所有其它进程也应该看到这个顺序,但不保证什么时候能看到。顺序一致性实际上只限制了各进程内指令的偏序关系,不在进程间进行排序。
  • 线性一致性(Linearizability Consistency):Maurice P. Herlihy 与 Jeannette M. Wing 在 1990 年共同提出,在顺序一致性前提下加强了进程间的操作排序,形成唯一的全局顺序(系统等价于是顺序执行,所有进程看到的所有操作的序列顺序都一致),是很强的原子性保证。但是很难实现,基本上要么依赖于全局的时钟或锁(原子钟是个简单粗暴但有效的主意),要么性能比较差。

莫非分布式领域也有一个测不准原理?这个世界为何会有这么多的约束呢?

一致性的理论界限

搞学术的人都喜欢对问题先确定一个界限,那么,这个问题的最坏界限在哪里呢?很不幸,一般情况下,分布式系统的一致性问题无解。

当节点之间的通信网络自身不可靠情况下,很显然,无法确保实现一致性。但好在,一个设计得当的网络可以在大概率上实现可靠的通信。

然而,即便在网络通信可靠情况下,一个可扩展的分布式系统的一致性问题的下限是无解。

这个结论,被称为 FLP 不可能性 原理,可以看做分布式领域的“测不准原理”。

24小时热点

DeFi市场的下一个明星项目—YFIQ

据DeFi Pulse 的数据,从8月至今,抵押在DeFi平 ...

44352

财经视野

lbr币值得长期购买吗?lbr币是龙头吗?

近年来,加密货币市场发展迅猛,各种数字货币层出不穷。在这些中 ...

54424

LTC Litecoin 浏览器

03-16发布:区块链网评分降幅日榜

03-16发布:区块链网评分降幅日榜 第一名: ...

4328

区块矿池统计
广告

热点专题

虚拟货币传销/诈骗案件的通常做法

当更多人似懂非懂的对虚拟货币有些模糊的概念,还搞不清比特币和 ...

4189130

瓦特(WBF)交易所

iBox 链盒科技

据iBox官方消息,9月17日20:00,iBox将正式发布 ...

3392217

iBox

揭秘网络传销行骗七大套路!

不管网络传销打着什么旗号,戴着什么面具,即便有着“72变”, ...

3030354

A网(AOFEX)交易所

gpt4.0中文版免费

GPT-4(生成预可训练技术4.0)是一个由OpenAI开发 ...

2852147

维公链

Gem和Genie功能大对比

2022年4月25日,OpenSea官方发推宣布收购NFT交 ...

2378355

TopHolder 头号藏家

Genie 就是一个 NFT 市场的交易聚合器

Web3 中的「聚合器」是一个非常重要的组件,例如 1inc ...

2344350

嗨艺购

一文读懂NFT 交易聚合器GEM

购买 NFT 的主要问题之一在于,限制了用户一次只能购买一个 ...

2304795

第九空间

亚洲最大成人平台“SWAG”网站关停,负责人被捕

2020 年,SWAG 发行了 6.25 亿枚治理代币 SW ...

1591540

NFT和元宇宙

链图百科:美国政府官员级别排名

美国政府官员的级别排名是由总统(President)首先,然 ...

1107103

Tokhun

北海传销,投资7万回报1040万真相揭秘

整天打着国家政府宏观调控的资本运作,坑害了多少善良的人?对北 ...

1063686

ImToken 多链钱包