分布式理论:CAP是三选二吗?

image.png

CAP是什么? CAP理论,被戏称为[帽子理论]。CAP理论由Eric Brewer在ACM研讨会上提出,而后CAP被奉为分布式领域的重要理论[1] 。

分布式系统的 CAP 理论:首先把分布式系统中的三个特性进行了如下归纳: ● 一致性(C):在分布式系统中的所有数据备份,在同一时刻是否同样的 值。(等同于所有节点访问同一份最新的数据副本)

● 可用性(A):在集群中一部分节点故障后,集群整体是否还能响应客户端 的读写请求。(对数据更新具备高可用性)

● 分区容忍性(P):以实际效果而言,分区相当于对通信的时限要求。系统 如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前 操作在 C 和 A 之间做出选择。(分区状态可以理解为部分机器不连通了,比如 机器挂了,繁忙失去响应,单机房故障等)

Partition 字面意思是网络分区,即因网络因素将系统分隔为多个单独的部 分,有人可能会说,网络分区的情况发生概率非常小啊,是不是不用考虑 P, 保证 CA 就好。要理解 P,我们看回 CAP 证明中 P 的定义:

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another。

网络分区的情况符合该定义,网络丢包的情况也符合以上定义,另外节点宕 机,其他节点发往宕机节点的包也将丢失,这种情况同样符合定义。现实情况 下我们面对的是一个不可靠的网络、有一定概率宕机的设备,这两个因素都会 导致 Partition,因而分布式系统实现中 P 是一个必须项,而不是可选项。

高可用、数据一致性是很多系统设计的目标,但是分区又是不可避免的事情。 我们来看一看分别拥有 CA、CP 和 AP 的情况。

CA without P:如果不要求 P(不允许分区),则 C(强一致性)和 A(可用 性)是可以保证的。但其实分区不是你想不想的问题,而是始终会存在,CA 系 统基本上是单机系统,比如单机数据库。2PC 是实现强一致性的具体手段。

image.png

CP without A:如果不要求 A(可用),相当于每个请求都需要在 Server 之间 强一致,而 P(分区)会导致同步时间无限延长,如此 CP 也是可以保证的。很 多传统的数据库分布式事务都属于这种模式。

image.png

AP wihtout C:要高可用并允许分区,则需放弃一致性。一旦分区发生,节点 之间可能会失去联系,为了高可用,每个节点只能用本地数据 供服务,而这 样会导致全局数据的不一致性。现在众多的 NoSQL 都属于此类。

CAP 理论的证明

该理论由 brewer 出,2 年后就是 2002 年,Lynch 与其他人证明了 Brewer 猜 想,从而把 CAP 上升为一个定理。但是,它只是证明了 CAP 三者不可能同时满 足,并没有证明任意二者都可满足的问题,所以,该证明被认为是一个收窄的 结果。

Lynch 的证明相对比较简单:采用反证法,如果三者可同时满足,则因为允许 P 的存在,一定存在 Server 之间的丢包,如此则不能保证 C,证明简洁而严谨。

在该证明中,对 CAP 的定义进行了更明确的声明:

  • C:一致性被称为原子对象,任何的读写都应该看起来是 “原子“的,或串行的。写后面的读一定能读到前面写的内容。所有的读写请 求都好像被全局排序一样。
  • A:对任何非失败节点都应该在有限时间内给出请求的回 应。(请求的可终止性)
  • P:允许节点之间丢失任意多的消息,当网络分区发生时, 节点之间的消息可能会完全丢失。

对于 CAP 进一步的案例解释

2010 年的这篇文章 brewers-cap-theorem-on-distributed-systems/,用了三 个例子来阐述 CAP,分别是 example1:单点的 mysql;example2:两个 mysql, 但不同的 mysql 存储不同的数据子集,相当于 sharding;example3:两个 mysql,对 A 的一个 insert 操作,需要在 B 上执行成功才认为操作完成(类似 复制集)。作者认为在 example1 和 example2 上 都能保证强一致性,但不能保 证可用性;在 example3 这个例子,由于分区(partition)的存在,就需要在 一致性与可用性之间权衡。对于复制而言,在很多场景下不追求强一致性。比 如用户支付之后,交易记录落地了;但可能消费记录的消息同步存在延迟,比 如消息阻塞了。在金融业务中,采取类似两地三中心架构,往往可能采取本地 数据和异地机房数据同时写成功再返回的方式。这样付出了性能的损耗,响应 时间变长。但发生机房故障后,能确保数据是完全可以读写的,保障了一致性。

CAP 理论澄清

[CAP 理论十二年回顾:"规则"变了]一文首发于 Computer 杂志,后由 InfoQ 和 IEEE 联合呈现,非常精彩[2],文章表达了几个观点。

“三选二”是一个伪命题

不是为了 P(分区容忍性),要在 A 和 C 之间选择一个。分区很少出现,CAP 在 大多数时候允许完美的 C 和 A。但当分区存在或可感知其影响的情况下,就要 预备一种策略去探知分区并显式处理其影响。这样的策略应分为三个步骤:探

知分区发生,进入显式的分区模式以限制某些操作,启动恢复过程以恢复数据 一致性并补偿分区期间发生的错误。

“一致性的作用范围”其实反映了这样一种观念,即在一定的边界内状态是一 致的,但超出了边界就无从谈起。比如在一个主分区内可以保证完备的一致性 和可用性,而在分区外服务是不可用的。Paxos 算法和原子性多播(atomic multicast)系统一般符合这样的场景。像 Google 的一般做法是将主分区归属 在单个数据中心里面,然后交给 Paxos 算法去解决跨区域的问题,一方面保证 全局协商一致(global consensus)如 Chubby,一方面实现高可用的持久性存 储如 Megastore。

ACID、BASE、CAP

ACID 和 BASE 这两个术语都好记有余而精确不足,出现较晚的 BASE 硬凑的感觉 更明显,它是“Basically Available, Soft state, Eventually consistent (基本可用、软状态、最终一致性)”的首字母缩写。其中的软状态和最终一 致性这两种技巧擅于对付存在分区的场合,并因此 高了可用性。

CAP 与 ACID 的关系更复杂一些,也因此引起更多误解。其中一个原因是 ACID 的 C 和 A 字母所代表的概念不同于 CAP 的 C 和 A。还有一个原因是选择可用性 只部分地影响 ACID 约束。

进一步看[分区]之后

image.png

用一下这张图[引用自 link 2],在状态 S 的时候是非分区状态,而分区模式则 演化出来了 S1,S2,那么问题来了,分区恢复之后,状态究竟是多少呢?有几 种解决方案。

分区恢复策略:可交换多副本数据类型 注意,能支持此类处理的场景是有限的。 riak_dt 就是这样一种保障最终一致性实现的数据结构,它分为Operation- based CRDTs、State-based CRDTs 2 种形态。 riak_dt link 参见 link [3]。

分区恢复策略:回放合并 在分区恢复过程中,设计师必须解决两个问题:

  • 分区两侧的状态最终必须保持一致
  • 并且必须补偿分区期间产生的错误。

如上图所示,对于分区恢复的状态 S*可以通过未分区时的状态 S 为起点,然后 按顺序[回放]相应的变化事件[以特定方式推进分区两侧的一系列操作,并在过 程中一直保持一致的状态。]。Bayou[link 4]就是这个实现机制,它会回滚数 据库到正确的时刻并按无歧义的、确定性的顺序重新执行所有的操作,最终使 所有的节点达到相同的状态。

对于有冲突的情况,比如版本管理软件 cvs,存在人工介入、消除冲突的处理策略。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人分享

storm概念学习及流处理与批处理的区别

在过去10 年中,随着互联网应用的高速发展,企业积累的数据量越来越大,越来越多。随着Google MapReduce、Hadoop 等相关技术的出现,处理大规模...

12610
来自专栏张戈的专栏

修改WordPress默认评论表情(附:跳转到多说评论框的方法)

先吐槽一下:这两天博主折腾抢票火车票去了,博客也没怎么打理,最不爽的是折腾到最后才弄到一张无座的,唉,说多了都是泪啊!铁道部你技术不行可以招标啊,干嘛拿老百姓做...

39690
来自专栏ytkah

【已修复】微信后台服务故障 部分用户收发消息或登录受影响

  就在不久前的刚刚,部分微信用户反映在使用微信时,出现退出后无法登陆的情况。微信团队在官方微博上确认了此事,并发公告正在紧急抢救。对于月活跃用户达到三四亿的a...

32630
来自专栏java一日一条

这十二行代码是如何让浏览器爆炸的?

今天刷推特的时候发现 Cyber Security@cyber__sec 的推文让人眼前一亮:

7820
来自专栏开源优测

AutoLink开源平台系统流程

为了方便大家理解AutoLink源码和设计原理,画了AutoLink开源平台的关键业务流程

18640
来自专栏ImportSource

NoSQL Sharding 分片

翻译内容: NoSQL Distilled 第四章 Distribution Models 作者简介: ? 本节摘要: 各位周末好,今天我们主...

440120
来自专栏更流畅、简洁的软件开发方式

文档驱动式代码设计器——代码是设计出来的!

  代码是敲出来的吗?是批量生成出来的吗?   No no no,代码是设计出来的!   如果说到代码生成器,大家可能会想到三层、动软代码生成器、数据库表等等。...

22880
来自专栏鸿的学习笔记

事务的处理

事务应该是数据库提供给应用程序的,并且为了隐藏并行问题和软硬件会发生的错误,而使用的一种抽象。下图中提到的方法包含了几个前提,那就是时钟是相对可靠的...

9530
来自专栏.NET技术

正确理解CAP定理

  CAP的理解我也看了很多书籍,也看了不少同行的博文,基本每个人的理解都不一样,而布鲁尔教授得定义又太过的简单,没有具体描述和场景案例分析。因此自己参考部分资...

13520
来自专栏不止思考

架构设计之「服务隔离」

那什么是「服务隔离」呢? 顾名思义,它是指将系统按照一定的原则划分为若干个服务模块,各个模块之间相对独立,无强依赖。当有故障发生时,能将问题和影响隔离在某个模块...

15430

扫码关注云+社区

领取腾讯云代金券