FLP 不可能性与CAP原理

FLP 不可能原理:在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。

提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表,该论文后来获得了 Dijkstra(就是发明最短路径算法的那位)奖。

FLP 不可能性与CAP原理

理解这一原理的一个不严谨的例子是:

三个人在不同房间,进行投票(投票结果是 0 或者 1)。三个人彼此可以通过电话进行沟 通,但经常会有人时不时地睡着。比如某个时候,A 投票 0,B 投票 1,C 收到了两人的投票,然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。如果可以重新投票, 则类似情形每次在取得结果前发生:(FLP 原理实际上说明对于允许节点失效情况下,纯粹异步系统无法确保一致性在有限时间内完成。

这岂不是意味着研究一致性问题压根没有意义吗?

先别这么悲观,学术界做研究,考虑的是数学和物理意义上最极端的情形,很多时候现实生活要美好的多(感谢这个世界如此鲁棒!)。例如,上面例子中描述的最坏情形,总会发生的概率并没有那么大。工程实现上多试几次,很大可能就成功了。

学术告诉你什么是不可能的;工程则告诉你,付出一些代价,我可以把它变成可能。这就是工程的魅力。

那么,退一步讲,在付出一些代价的情况下,我们能做到多少? 回答这一问题的是另一个很出名的原理:CAP 原理

学术上告诉你去赌场赌博从概率上总会是输钱的;工程则告诉你,如果你接受最终输钱的话,中间说不定偶尔能小赢几笔呢!?


CAP 原理最早由 Eric Brewer 在 2000 年,ACM 组织的一个研讨会上提出猜想,后来 Lynch等人进行了证明。

该原理被认为是分布式系统领域的重要原理。

CAP 原理

定义

分布式计算系统不可能同时确保一致性(Consistency)、可用性(Availablity)和分区容忍性

(Partition)。

  • 一致性(Consistency):任何操作应该都是原子的,发生在后面的事件能看到前面事件发生导致的结果;

  • 可用性(Availablity):在有限时间内,任何非失败节点都能应答请求;

  • 分区容忍性(Partition):网络可能发生分区,即节点之间的通信不可保障。

比较直观地理解,当网络可能出现分区时候,系统是无法同时保证一致性和可用性的。要么,节点收到请求后因为没有得到其他人的确认就不应答,要么节点只能应答非一致的结果。

好在大部分时候网络被认为是可靠的,因此系统可以提供一致可靠的服务;当网络不可靠时,系统要么牺牲掉一致性(大部分时候都是如此),要么牺牲掉可用性。

应用

既然 CAP 不可同时满足,则设计系统时候必然要弱化对某个特性的支持。

  • 不保证一致性

对结果一致性不敏感的应用,可以允许在新版本上线后过一段时间才更新成功,期间不保证一致性。例如网站静态页面内容、实时性较弱的查询类数据库等。

  • 不保证可用性

对结果一致性很敏感的应用,例如银行取款机,当系统故障时候会拒绝服务。Paxos、Raft 等算法的设计目标。

  • 不保证分区容忍性

现实中,网络分区出现概率减小,但较难避免。网络通过双通道等机制增强可靠性,达到高稳定的网络通信。




玖壹区块链声明

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

分享:

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

区块链评论

玖壹区块链培训

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