[NoSQL] CAP定理

博客首页 » NoSQL CAP定理

发布于 26 Nov 2015 09:24
标签 blog
这几篇关于CAP定理的介绍不错

http://www.cnblogs.com/netfocus/p/4385347.html

另外,除了CAP本身的介绍以外,需要注意CAP也不是非黑即白的问题,可以有不同层次的多种妥协。

Twitter首席工程师:如何“打败”CAP定理 - 主要使用不可修改Copy Only的特性
http://kb.cnblogs.com/page/124567/

其他两篇介绍文章

CAP理论基础
http://blog.sina.com.cn/s/blog_493a8455010161hi.html

CAP理论
http://blog.csdn.net/chen77716/article/details/30635543

CAP定理简介

在理论计算机科学中,CAP定理(CAP theorem),又被称作布鲁尔定理(Brewer's theorem),它指出对于一个分布式计算系统来说,不可能同时满足以下三点:

一致性(Consistency):同一个数据在集群中的所有节点,同一时刻是否都是同样的值。
可用性(Availability):集群中一部分节点故障后,集群整体是否还能处理客户端的更新请求。
分区容忍性(Partition tolerance):是否允许数据的分区,分区的意思是指是否允许集群中的节点之间无法通信。
我的个人理解

我觉得,理解CAP可以从两个阶段去考虑。

只考虑CP

如果我们只考虑CP,我发现很有意思。因为此时,我们就是关注,当可能存在A,B两个节点网络不通的情况下,能否做到A,B两个节点之间的数据在任何时刻总是一致的。

我认为是不行的。因为:假如一开始A,B两个节点之间是连通的,然后一个数据写入请求过来,由于是分布式的,我们无法做到A,B同时写入。所以,不管是哪个先写入,当一个先写入后,假设此时网络突然断开了,那另一个节点就不会自动写入。从而最终导致A,B的数据不一致。大家想想是不是这样呢?

把A也考虑进来

上面,我们讨论了,在不关注A的时候,我们已经无法绝对保证A,B两个节点之间的数据在任何时刻都是一致的了。那如果再考虑A,也就是CAP同时考虑,那不是更加不可能同时做到了?如果我们此时,希望系统继续可用,那就要让用户看到这种不一致,即牺牲了C(其实不能说牺牲,因为C我们上面分析过,一定是做不到的(已经牺牲了!)。所以,应该说选择了向用户暴露这种不一致)。如果我们不允许系统继续写入或被读取,那就是牺牲了A,此时相当于:数据不一致了,且同时系统不可用了;

用户想要的一致性是什么?

难道我们集群中,某些节点挂了后,就不能继续为用户提供服务了吗?不是的。因为有NRW算法的存在。

我们想一下,用户关心集群中节点的数据一致性吗?不关心!那用户关心什么?用户关心的是,我只要写入数据成功了,那我下次读取该数据时,总是能读取到最新写入的数据。所以,只要我们的数据库做到了这一点,那数据库里的数据对于用户而言,就是具有一致性的。注意:这里的一致性是针对用户而言的,不是CAP定理中的数据副本之间的一致性概念。

那要做到这种一致性,要怎么做呢?答案就是NRW算法。

NRW算法

假设总共有五个节点(N),我们只要保证写入数据的节点数(W)+ 读取数据的节点数(R)大于总节点数即可。即保证W+R>N,那就能保证对客户端而言,总是能读取到它最新写入的数据。比如,总节点数为5,写入节点数为3,读取节点数为3,那我们就能保证客户端总是能读取到它最新写入的数据。有了这样的数据公式的作为理论保证。我们就可以根据情况灵活选择W,R了。由于我们不需要保证5台机器全部都写入成功,只需要保证3台写入成功即可。这就意味着,我们允许5台机器中的2台出现问题,也就是提高了系统的可用性。这样的设计,虽然集群节点之间,也许有些节点的数据不是最新的,也就是没有做到CAP中的C,但对用户来说,数据总是一致的。

所以,有了NRW算法,我们就能做到,在满足AP的前提下,我们完全还可以做到对用户而言的数据一致性。

CAP原理的证明

逍遥冲

CAP原理的证明

CAP概述

CAP.png

C: Consistency 一致性
A: Availability 可用性
P:Partition Tolerance分区容错性
CAP理论的核心是:一个分布式系统不可能同时很好的满足一致性,可用性和分区容错性这三个需求,最多只能同时较好的满足两个。

CAP的定义
1、C: Consistency 一致性
对于一致性,可以分为从客户端和服务端两个不同的视角。从客户端来看,一致性主要指的是多并发访问时更新过的数据如何获取的问题。从服务端来看,则是更新如何复制分布到整个系统,以保证数据最终一致。一致性是因为有并发读写才有的问题,因此在理解一致性的问题时,一定要注意结合考虑并发读写的场景。
从客户端角度,多进程并发访问时,更新过的数据在不同进程如何获取的不同策略,决定了不同的一致性。对于关系型数据库,要求更新过的数据能被后续的访问都能看到,这是强一致性。如果能容忍后续的部分或者全部访问不到,则是弱一致性。如果经过一段时间后要求能访问到更新后的数据,则是最终一致性。
2、A: Availability 可用性
对于一个可用性的分布式系统,每一个非故障的节点必须对每一个请求作出响应。也就是,该系统使用的任何算法必须最终终止。当同时要求分区容忍性时,这是一个很强的定义:即使是严重的网络错误,每个请求必须终止。
好的可用性主要是指系统能够很好的为用户服务,不出现用户操作失败或者访问超时等用户体验不好的情况。可用性通常情况下可用性和分布式数据冗余,负载均衡等有着很大的关联。
3、P:Partition Tolerance分区容错性
分区容错性和扩展性紧密相关。在分布式应用中,可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求能够使应用虽然是一个分布式系统,而看上去却好像是在一个可以运转正常的整体。比如现在的分布式系统中有某一个或者几个机器宕掉了,其他剩下的机器还能够正常运转满足系统需求,或者是机器之间有网络异常,将分布式系统分隔未独立的几个部分,各个部分还能维持分布式系统的运作,这样就具有好的分区容错性。

CAP原理的证明

场景
intro_thumb.png
如上图,是我们证明CAP的基本场景,网络中有两个节点N1和N2,可以简单的理解N1和N2分别是两台计算机,他们之间网络可以连通,N1中有一个应用程序A,和一个数据库V,N2也有一个应用程序B2和一个数据库V。现在,A和B是分布式系统的两个部分,V是分布式系统的数据存储的两个子数据库。
在满足一致性的时候,N1和N2中的数据是一样的,V0=V0。在满足可用性的时候,用户不管是请求N1或者N2,都会得到立即响应。在满足分区容错性的情况下,N1和N2有任何一方宕机,或者网络不通的时候,都不会影响N1和N2彼此之间的正常运作。scenario1_thumb.png
如上图,是分布式系统正常运转的流程,用户向N1机器请求数据更新,程序A更新数据库Vo为V1,分布式系统将数据进行同步操作M,将V1同步的N2中V0,使得N2中的数据V0也更新为V1,N2中的数据再响应N2的请求。
这里,可以定义N1和N2的数据库V之间的数据是否一样为一致性;外部对N1和N2的请求响应为可用行;N1和N2之间的网络环境为分区容错性。这是正常运作的场景,也是理想的场景,然而现实是残酷的,当错误发生的时候,一致性和可用性还有分区容错性,是否能同时满足,还是说要进行取舍呢?scenario2_thumb.png
作为一个分布式系统,它和单机系统的最大区别,就在于网络,现在假设一种极端情况,N1和N2之间的网络断开了,我们要支持这种网络异常,相当于要满足分区容错性,能不能同时满足一致性和响应性呢?还是说要对他们进行取舍。
假设在N1和N2之间网络断开的时候,有用户向N1发送数据更新请求,那N1中的数据V0将被更新为V1,由于网络是断开的,所以分布式系统同步操作M,所以N2中的数据依旧是V0;这个时候,有用户向N2发送数据读取请求,由于数据还没有进行同步,应用程序没办法立即给用户返回最新的数据V1,怎么办呢?有二种选择,第一,牺牲数据一致性,响应旧的数据V0给用户;第二,牺牲可用性,阻塞等待,直到网络连接恢复,数据更新操作M完成之后,再给用户响应最新的数据V1。
这个过程,证明了要满足分区容错性的分布式系统,只能在一致性和可用性两者中,选择其中一个。
CAP实践中的取舍
1、满足一致性,可用性的系统,通常在可扩展性上不太强大,例如下面的产品:
Traditional RDBMSs like Postgres,MySQL, etc (relational)
Vertica (column-oriented)
Aster Data (relational)
Greenplum (relational)
2、满足一致性,分区容忍必的系统,通常用户操作响应上不太稳定,例如下面的产品:
BigTable (column-oriented/tabular)
Hypertable (column-oriented/tabular)
HBase (column-oriented/tabular)
MongoDB (document-oriented)
Terrastore (document-oriented)
Redis (key-value)
Scalaris (key-value)
MemcacheDB (key-value)
Berkeley DB (key-value)
3、满足可用性,分区容忍性的系统,通常可能对一致性要求低一些,例如下面的产品:
Dynamo (key-value)
Voldemort (key-value)
Tokyo Cabinet (key-value)
KAI (key-value)
Cassandra (column-oriented/tabular)
CouchDB (document-oriented)
SimpleDB (document-oriented)
Riak (document-oriented)

参考资料:
CAP原理与最终一致性
佳文分享:CAP定理
Brewer’s CAP Theorem
NoSQL学习笔记(二)之CAP理论
CAP定理
本文固定链接: http://www.xiaoyaochong.net/wordpress/index.php/2013/07/27/cap%e5%8e%9f%e7%90%86%e7%9a%84%e8%af%81%e6%98%8e/ | 逍遥冲


本页面的文字允许在知识共享 署名-相同方式共享 3.0协议和GNU自由文档许可证下修改和再使用,仅有一个特殊要求,请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。


系列文章

文章列表

  • NoSQL CAP定理

这篇文章对你有帮助吗,投个票吧?

rating: 0+x

留下你的评论

Add a New Comment