CAP 理论

标签: 算法数据结构 软件技术 CAP理论 | 发表时间:2014-07-27 23:28 | 作者:童燕群
出处:http://shentar.me

CAP理论被很多人拿来作为分布式系统设计的金律,然而感觉大家对CAP这三个属性的认识却存在不少误区。从CAP的证明中可以看出来,这个理论的成立是需要很明确的对C、A、P三个概念进行界定的前提下的。在本文中笔者希望可以对论文和一些参考资料进行总结并附带一些思考。

一、什么是CAP理论

CAP原本是一个猜想,2000年PODC大会的时候大牛Brewer提出的,他认为在设计一个大规模可扩放的网络服务时候会遇到三个特性:一致性(consistency)、可用性(Availability)、分区容错(partition-tolerance)都需要的情景,然而这是不可能都实现的。之后在2003年的时候,Mit的Gilbert和Lynch就正式的证明了这三个特征确实是不可以兼得的。

二、CAP的概念

Consistency、Availability、Partition-tolerance的提法是由Brewer提出的,而Gilbert和Lynch在证明的过程中改变了Consistency的概念,将其转化为Atomic。Gilbert认为这里所说的Consistency其实就是数据库系统中提到的ACID的另一种表述:一个用户请求要么成功、要么失败,不能处于中间状态(Atomic);一旦一个事务完成,将来的所有事务都必须基于这个完成后的状态(Consistent);未完成的事务不会互相影响(Isolated);一旦一个事务完成,就是持久的(Durable)。

对于Availability,其概念没有变化,指的是对于一个系统而言,所有的请求都应该‘成功’并且收到‘返回’。

对于Partition-tolerance,所指就是分布式系统的容错性。节点crash或者网络分片都不应该导致一个分布式系统停止服务。

三、基本CAP的证明思路

CAP的证明基于异步网络,异步网络也是反映了真实网络中情况的模型。真实的网络系统中,节点之间不可能保持同步,即便是时钟也不可能保持同步,所有的节点依靠获得的消息来进行本地计算和通讯。这个概念其实是相当强的,意味着任何超时判断也是不可能的,因为没有共同的时间标准。之后我们会扩展CAP的证明到弱一点的异步网络中,这个网络中时钟不完全一致,但是时钟运行的步调是一致的,这种系统是允许节点做超时判断的。

CAP的证明很简单,假设两个节点集{G1, G2},由于网络分片导致G1和G2之间所有的通讯都断开了,如果在G1中写,在G2中读刚写的数据, G2中返回的值不可能G1中的写值。由于A的要求,G2一定要返回这次读请求,由于P的存在,导致C一定是不可满足的。

四、CAP的扩展

CAP的证明使用了一些很强的假设,比如纯粹的异步网络,强的C、A、P要求。事实上,我们可以放松某些条件,从而达到妥协。

首先 —— 弱异步网络模型

弱异步网络模型中所有的节点都有一个时钟,并且这些时钟走的步调是一致的,虽然其绝对时间不一定相同,但是彼此的相对时间是固定的,这样系统中的节点可以不仅仅根据收到的消息来决定自己的状态,还可以使用时间来判断状态,比如超时什么的。

在这种场景下,CAP假设依旧是成立的,证明跟上面很相似。

不可能的尝试 —— 放松Availability或者Partition-tolerance

放弃Partition-tolerance意味着把所有的机器搬到一台机器内部,或者放到一个要死大家一起死的机架上(当然机架也可能出现部分失效),这明显违背了我们希望的scalability。

放弃Availability意味着,一旦系统中出现partition这样的错误,系统直接停止服务,这是不能容忍的。

最后的选择 —— 放松一致性

我们可以看出,证明CAP的关键在于对于一致性的强要求。在降低一致性的前提下,可以达到CAP的和谐共处,这也是现在大部分的分布式存储系统所采用的方式:Cassandra、Dynamo等。“Scalability is a bussness concern”是我们降低一致性而不是A和P的关键原因。

Brewer后来提出了BASE ( Basically Available, Soft-state, Eventually consistent),作为ACID的替代和补充。

五、战胜CAP

1,2008年9月CTO of atomikos写了一篇文章“ A CAP Solution (Proving Brewer Wrong)”,试图达到CAP都得的效果。

这篇文章的核心内容就是放松Gilbert和Lynch证明中的限制:“系统必须同时达到CAP三个属性”,放松到“系统可以不同时达到CAP,而是分时达到”。

Rules Beat CAP:

1) 尽量从数据库中读取数据,如果数据库不能访问,读取缓存中的数据

2) 所有读都必须有版本号

3) 来自客户端的更新操作排队等候执行,update必须包括导致这次更新的读操作的版本信息

4) 分区数量足够低的时候排队等待的update操作开始执行,附带的版本信息用来验证update是否应该执行

5) 不管是确认还是取消更新,所有的结构都异步的发送给请求方

证明:

1) 系统保证了consistency,因为所有的读操作都是基于snapshot的,而不正确的update操作将被拒绝,不会导致错误执行

2) 系统保证了availability,因为所有的读一定会返回,而写也一样,虽然可能会因为排队而返回的比较慢

3) 系统允许节点失效

缺点:

1) 读数据可能会不一致,因为之前的写还在排队

2) partition必须在有限的时间内解决

3) update操作必须在所有的节点上保持同样的顺序

2, 2011年11月Twitter的首席工程师Nathan Marz写了一篇文章,描述了他是如何试图打败CAP定理的: How to beat the CAP theorem

本文中,作者还是非常尊重CAP定律,并表示不是要“击败”CAP,而是尝试对数据存储系统进行重新设计,以可控的复杂度来实现CAP。

Marz认为一个分布式系统面临CAP难题的两大问题就是:在数据库中如何使用不断变化的数据,如何使用算法来更新数据库中的数据。Marz提出了几个由于云计算的兴起而改变的传统概念:

1) 数据不存在update,只存在append操作。这样就把对数据的处理由CRUD变为CR

2) 所有的数据的操作就只剩下Create和Read。把Read作为一个Query来处理,而一个Query就是一个对整个数据集执行一个函数操作。

在这样的模型下,我们使用最终一致性的模型来处理数据,可以保证在P的情况下保证A。而所有的不一致性都可以通过重复进行Query去除掉。Martz认为就是因为要不断的更新数据库中的数据,再加上CAP,才导致那些即便使用最终一致性的系统也会变得无比复杂,需要用到向量时钟、读修复这种技术,而如果系统中不存在会改变的数据,所有的更新都作为创建新数据的方式存在,读数据转化为一次请求,这样就可以避免最终一致性的复杂性,转而拥抱CAP。

具体的做法这里略过。

总结:

其实对于大规模分布式系统来说,CAP是非常稳固的,可以扩展的地方也不多。

它很大程度上限制了大规模计算的能力,通过一些设计方式来绕过CAP管辖的区域或许是下一步大规模系统设计的关键。

————— 参考文献 ———————–

[1] Seth Gilbert and Nancy Lynch. 2002. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33, 2 (June 2002), 51-59. DOI=10.1145/564585.564601 http://doi.acm.org/10.1145/564585.564601

[2] Guy Pardon, 2008, A CAP Solution (Proving Brewer Wrong), http://blog.atomikos.com/2008/09/a-cap-solution-proving-brewer-wrong/

[3] Werner Vogels, 2007, Availability & Consistency, http://www.infoq.com/presentations/availability-consistency

[4] Nathan Marz, 2011, How to beat the CAP theorem, http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html

相关 [cap 理论] 推荐:

CAP 理论

- - 忘我的追寻
CAP理论被很多人拿来作为分布式系统设计的金律,然而感觉大家对CAP这三个属性的认识却存在不少误区. 从CAP的证明中可以看出来,这个理论的成立是需要很明确的对C、A、P三个概念进行界定的前提下的. 在本文中笔者希望可以对论文和一些参考资料进行总结并附带一些思考. CAP原本是一个猜想,2000年PODC大会的时候大牛Brewer提出的,他认为在设计一个大规模可扩放的网络服务时候会遇到三个特性:一致性(consistency)、可用性(Availability)、分区容错(partition-tolerance)都需要的情景,然而这是不可能都实现的.

谈正确理解 CAP 理论[转自网络]

- - 互联网 - ITeye博客
转载自:http://www.douban.com/group/topic/11765014/. CAP 理论在搞分布式的程序员中已经是路人皆知了. 但是 CAP 理论就好比是相对论,虽然所有的人都知道,但是却没有多少人真正理解. 要真正理解 CAP 理论必须要读懂它的形式化描述. 形式化描述中最重要的莫过于对 Consistency, Availability, Partition-tolerance 的准确定义.

分布式系统之CAP理论 - DM张朋飞

- - 博客园_首页
  任老师第一节主要讲了分布式系统实现时候面临的八个问题,布置的作业就是这个,查询CAP理论.   笔者初次接触分布式,所以本文主要是一个汇总.   CAP原本是一个猜想,2000年PODC大会的时候大牛Brewer提出的,他认为在设计一个大规模可扩放的网络服务时候会遇到三个特性:一致性(consistency)、可用性(Availability)、分区容错(partition-tolerance)都需要的情景,然而这是不可能都实现的.

【分布式系统工程实现】CAP理论及系统一致性

- hikerlive - 淘宝核心系统团队博客
印象中CAP理论开始流行是从Amazon Dynamo的论文开始的,Amazon的CTO还在他的博客中介绍了最终一致性的概念,从此以后,各种会议和交流中都少不了CAP的影子. 然而,对于分布式系统工程设计和开发来说,CAP意味着什么呢. CAP 理论由 Berkerly 的 Brewer 教授提出,三者的含义如下:.

持续可用与CAP理论 – 一个系统开发者的观点

- - NOSQL Notes
本文主要针对金融数据库,认为金融数据库的持续可用包含两点:一个是强一致性;另外一个是高可用性. 数据库系统必须是强一致性的系统,这是因为数据库系统有事务ACID的基本要求,而弱一致系统无法做到. 业内也有一些流行的NOSQL系统,例如各种类Dynamo系统,如开源的Cassandra,对同一个最小数据单位(同一行数据)允许多台服务器同时写入,虽然采用NWR机制处理冲突,但是由于不可能解决多台服务器之间的时序问题,而只能支持弱一致语义.

[译]如何“打败”CAP定理

- hikerlive - Fang Jian's Personal Blog
昨天看到了Nathan Marz这篇《How to beat the CAP theorem》觉得写得很有想法,所以决定把这篇文章翻译成中文,希望能够被更多的人看到,翻译可能不是很准确,如有错误之处欢迎指出. CAP定理指出一个数据库不可能同时满足:一致性(Consistency)、可用性(Availability)和分区容错性(Partition-Tolerance).

NOSQL数据模型和CAP原理

- - 数据库 - ITeye博客
我本来一直觉得NoSQL其实很容易理解的,我本身也已经对NoSQL有了非常深入的研究,但是在最近准备YunTable的Chart的时候,发现NoSQL不仅非常博大精深,而且我个人对NoSQL的理解也只是皮毛而已,但我还算是一个“知耻而后勇”的人,所以经过一段时间的学习之后,从本系列第六篇开始,就将和大家聊聊NoSQL,而本篇将主要给大家做一下NoSQL数据库的综述.

令人迷惑的CAP与ACID用语

- - 数据库 - ITeye博客
令人迷惑的CAP与ACID用语. CAP和ACID共享相同的词汇表:原子性(Atomic)、一致性(Consistent),诸如此类. 但内有玄机:这些词语虽一样,但它们的意思是完全不同的东西. CAP来自分布式系统理论,而ACID属于数据库系统. 分布式数据库既使用CAP词汇,也使用ACID词汇,这显然造成许多混淆.

分布式事务,EventBus 解决方案:CAP【中文文档】 - Savorboard - 博客园

- -
很多同学想对CAP的机制以及用法等想有一个详细的了解,所以花了将近两周时间写了这份中文的CAP文档,对 CAP 还不知道的同学可以先看一下. 本文档为 CAP 文献(Wiki),本文献同时提供中文和英文版本,英文版本目前还在翻译中,会放到Github Wiki 中. CAP 是一个遵循 .NET Standard 标准库的C#库,用来处理分布式事务以及提供EventBus的功能,她具有轻量级,高性能,易使用等特点.