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

标签: 分布式架构 | 发表时间:2010-11-06 11:52 | 作者:日照 hikerlive
出处:http://rdc.taobao.com/blog/cs

印象中CAP理论开始流行是从Amazon Dynamo的论文开始的,Amazon的CTO还在他的博客中介绍了最终一致性的概念,从此以后,各种会议和交流中都少不了CAP的影子。然而,对于分布式系统工程设计和开发来说,CAP意味着什么呢?

CAP 理论由 Berkerly 的 Brewer 教授提出,三者的含义如下:

  • 一致性 ( Consistency) :任何一个读操作总是能读取到之前完成的写操作结果;
  • 可用性 ( Availability) :每一个操作总是能够在确定的时间内返回;
  • 分区可容忍性 (Tolerance of network Partition) :在出现网络分区的情况下,仍然能够满足一致性和可用性;

CAP 理论认为,三者不能同时满足,并给出了证明,简单阐述如下:假设系统出现网络分区为 G1 和 G2 两个部分,在一个写操作 W1 后面有一个读操作 R2 , W1 写 G1 , R2 读取 G2 ,由于 G1 和 G2 不能通信,如果读操作 R2 可以终结的话,必定不能读取写操作 W1 的操作结果。

由于CAP三者无法同时满足,Amazon Dynamo论文中引入了用户可配置的NWR策略,在CAP三个特性中作出权衡。比如N=3, W=3, R=1强调一致性;N=3, W=1, R=1强调可用性;N=3, W=2, R=2是一种折衷的策略。另外,还有一些NOSQL系统把CAP理论当成一种借口,认为既然我们不能同时满足一致性和可用性,那NOSQL系统就牺牲一致性。这些说法本身虽然不能说有错,但我们至少需要思考两个问题:

  1. CAP理论在工程的角度意味着什么?
  2. 一致性的具体含义?

笔者认为,最初的CAP理论只是粗略地告诉我们”天下没有免费的午餐”,对于NOSQL系统设计指导意义不大。原始的CAP理论描述有如下缺陷:

  1. 缺少时间因素。比如对于可用性描述,10s中停服务和1个小时停服务完全是两个概念,只停写服务和同时停读写服务的影响也是很不一样的。
  2. 一致性描述问题。每个读操作虽然能够读取到之前写操作结果,但是假设某些写操作发生在机器A,某些写操作发生在机器B,一致性依赖于对机器A和机器B上写操作的合并,操作的顺序是无法保证的。比如Dynamo&Cassandra系统中由于可能出现同一个<key, value>对被多个节点同时修改的情形,即使在NWR策略中配置W + R > N,也需要依赖冲突合并来保证一致性,这从理论上是没有完美做法的。
  3. 网络分区描述过于模糊。工程上容易出现的网络问题一般是机房之间网络不通,某个机房停电,某台机器故障或者某些机器因为机架电源或者交换机的原因发生故障。单个机器故障也可以认为是网络分区,但这和机房网络不通对系统设计带来的挑战差别是很大的。

一般可以认为:工程上网络分区总是存在,比如机器故障或者网络异常,一致性和可用性不能同时满足。且工程上从来不要求绝对的一致性或者可用性,而是寻求一种平衡,可以将一致性和可用性分别重定义为HarvestYield

  • Harvest (对应一致性):percent of required data actually included in the responses (请求结果的真实程度);
  • Yield (可用性):percent of requests answered successfully (成功请求占的百分比);

CAP理论可以演化为在工程上寻找一种方法,在”成功请求占的百分比”和”请求结果的真实程度”之间取得一个权衡,详细描述可以参考Coda的博客。然而,这个描述仍然不够具体,下面我们就有总控节点的系统(如GFS+Bigtable)和P2P系统(如Amazon Dynamo)两类系统的CAP含义分别进行说明。

首先我们必须明确一致性的概念。NOSQL系统经常提到最终一致性模型:假如客户端A写入一个值到存储系统,客户端B最终总是能够读取到A写入的最新值,这里有一个时间窗口,依赖于交互延迟,系统负载以及复制技术中的replica的个数。Amazon CTO宣称Dynamo为最终一致性系统,然而,这里的最终一致性具有很大的欺骗性,因为虽然客户端B能够读到其它客户端写入的所有数据,但是可能出现多个节点更新同一个值的情况,需要依赖冲突合并来解决多机操作顺序问题。后续的文章中,我们都会把Amazon Dynamo这种需要依赖操作合并,可能会丢失数据的模型从最终一致性模型中排除出去。最终一致性模型要求同一份数据同一时刻只能被一台机器修改,也就是说机器宕机时需要停很短时间写服务。

对于带有总控节点的系统,将CAP理论的定义做出适当的调整如下:

  • 一致性:读操作总是能读取到之前完成的写操作结果,且不需要依赖于操作合并
  • 可用性:读写操作总是能够在很短的时间内返回,即使某台机器发生了故障,也能够通过其它副本正常执行,而不需要等到机器重启或者机器上的服务分配给其它机器以后才能成功;
  • 分区可容忍性:能够处理机器宕机,机房停电或者出现机房之间网络故障等异常情况;

带有总控节点的NOSQL系统一般是最终一致性系统,允许机器宕机时停止很短时间,比如10s的部分数据写服务,但是不允许停读服务,且服务恢复时间越短越好。大多数NOSQL系统都是对一份数据保留多个备份,同一时刻只有一个备份为主,提供写服务,其它备份为辅,同步主备份的写操作,所有的备份都可以提供读取服务,且主备份提供保证强一致性的读服务。当主备份所在机器发生故障时,需要等一段时间才能由原来的辅备份接替主备份提供写服务。

类似Amazon的P2P去中心化系统提供需要依赖冲突合并的一致性,比如Cassandra中的“last write wins”冲突合并策略,虽然并不完美但确实能够解决很多问题。这样的系统能够通过用户配置NWR策略来权衡一致性和可用性,可以做到单台机器宕机时读写服务都不停止。

最后,再次提醒大家设计系统时:不要过分迷恋CAP,认清最终一致性,理智对待NWR。

相关 [分布 系统工程 cap] 推荐:

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

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

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

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

CAP 理论

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

【分布式系统工程实现】Bigtable Merge-Dump存储引擎

- XiaoHui - NOSQL Notes
单机存储引擎解决单机读写问题,Merge-Dump存储引擎设计成一种通用的存储引擎,同时支持数据写入,随机读取和顺序扫描功能. 顺序扫描功能应用很广,比如MapReduce批处理,同一个广告主的所有关键词广告统计,用户浏览所有的收藏信息,淘宝卖家管理大量的商品等. 简单的KV系统只需要支持随机读取,而类似Bigtable这样的通用表格系统需要考虑基于主键的顺序扫描功能.

【分布式系统工程实现】GFS&Bigtable设计的优势

- hikerlive - 淘宝核心系统团队博客
目前,知名度比较高的通用存储系统包括:Google GFS&Bigtable,Amazon Dynamo,Microsoft Azure存储系统及Yahoo PNUTS. 其中,GFS&Bigtable,Azure存储系统及Yahoo PNUTS都有总控节点,Amazon Dynamo采用去中心化的P2P设计.

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

- hikerlive - Fang Jian&#39;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词汇,这显然造成许多混淆.

【分布式系统工程实现】如何检测一台机器是否宕机?

- Michael Liao - 淘宝核心系统团队博客
检测一台机器是否宕机的应用场景如下:. 1, 工作机器宕机,总控节点需要能够检测到并且将原有服务迁移到集群中的其它节点. 2, 总控节点宕机,总控节点的备份节点(一般称为Slave)需要能够检测到并替换成主节点继续对外服务. 检测一台机器是否宕机必须是可靠的. 在大规模集群中,机器可能出现各种异常,比如停电,磁盘故障,过于繁忙导致假死等.