文档章节

Brewer: (CAP) Theorem

Poorzerg
 Poorzerg
发布于 2014/02/08 14:56
字数 2198
阅读 21
收藏 0

       Brewer在2000年UC Berkle的发言中提出,在设计和部署一个应用程序到分布式环境中的时候,存在着三点重要的系统需求需要详细考虑的[What he said was there are three core systemic requirements that exist in a special relationship when it comes to designing and deploying applications in a distributed environment],这三点需求就是由他提出来的理论:Consistency、Availability 和Partition ,或者简称为CAP。这个理论后来一直用于指导分布式应用的设计开发。

 

Consistency:

  在传统的关系型数据库中,ACID一直作为传统关系型数据库的指导设计思想,其中的C就是指Consistency。数据的一致性一直是应用程序需要密切关注的。可以想象,如果某客户往银行卡中存入了100块,却在下次查询时发现这100块没有进入到账户中,那也许客户就要把银行告上法庭了。


Availability:

  Availability也就是指,应用程序的服务可以使用,也就是能正常提供服务。可以想象的场景为打电话时希望对方的回应,而不是听到对方无法接通或无法响应的场景

 

Partition Tolerance:

  如果应用程序只是运行在单一的主机上,那就不存在这种问题了。但当应用程序的数据分布于多台主机上的时候,如果A主机无法连接而造成应用程序无法提供服务,这是不可容忍的。将数据多份拷贝并保存在多台主机上,当某备份主机宕机后,应用程序仍然正常工作,实现数据高可靠容错性。

 

  在分布式系统中,这样的一个场景随处可见[ 正常的流程 ]:A往节点N0中修改数据将V=v0修改为V=v1,然后N0将V=v1同步到N1中,此时B节点从N1中读取V的数据,获得v1。但是,更普遍的一个场景是,N0可能无法将数据同步到N1中,导致了B读取到V=v0,这是不可容忍的。从CAP理论出发,可以这么想,保持C,只要所有节点都同步成功,这一次写操作才成功,或者是,只需要一个节点N。当然,不管是前者还是后者,这两个方案都是不可取的,前者降低了系统的可用性,后者降低了系统的容错性。

理论证明,在分布式系统中,CAP理论中的三点,只能够完整的保证其中两点。为此,在当前的分布式系统设计中,只存在了几种选择:

  • Drop Partition Tolerance

  • Drop Availability

  • Drop Consistency

  • The BASE Jump

  • Design around it

 

The BASE Jump:牺牲高一致性,保证可用性及可靠性,以保持最终一致性为目标,这样的一种架构称之为BASE (Basically Available, Soft-state,Eventually consistent)。BASE是跟ACID背道而驰的理论,这种结构通常只保证某一面的特性而牺牲另一面的特性,这是实际产品设计中常用的一种取舍方式。

 

Design around it:从字面上可以看出,就是大体上都能实现的意思,只不过存在某些方面的问题。实际上,这种结构导致了CAP中任意一个方面都不能完整保证。

 

在Consistency问题上,可以通过两种角色角度上来看待:客户端[ Client ]或服务端[ Server ]

 

从客户端[ Client ]角度上来看:

  • 强一致性:

  假如A先写入了一个值到存储系统,存储系统保证后续A,B,C的读取操作都将返回最新值。

  • 弱一致性:

  假如A先写入了一个值到存储系统,存储系统不能保证后续A,B,C的读取操作能读取到最新值。此种情况下通常叫做“不一致性窗口”,它特指从A写入值,到后续操作A,B,C读取到最新值这一段时间。

  • 最终一致性:

  最终一致性是弱一致性的一种特例。假如A首先write了一个值到存储系统,存储系统保证如果在A,B,C后续读取之前没有其它写操作更新同样的值的话,最终所有的读取操作都会读取到从A写入的最新值。此种情况下,如果没有失败发生的话,“不一致性窗口”的大小依赖于以下的几个因素:交互延迟,系统的负载,以及复制技术中replica的个数(这个可以理解为master/salve模式中,salve的个数),最终一致性方面最出名的系统可以说是DNS系统,当更新一个域名的IP以后,根据配置策略以及缓存控制策略的不同,最终所有的客户都会看到最新的值。

 

在最终一致性模型上,有一系列的变体可以参考:

  • 因果一致性[ Causal consistency]

  如果Process A通知了Process B数据v已经更新了,那么关于Process B的后续对v的读取,都将保证读取这个已经被更新了的值。而对于Process C,由于跟Process A没有Causal consistency 关系,就只能遵从最终一致性原则,在Process C中的v值没被通知更新前,将一直读取到旧的值。

  • 只读自己写的数据一致性[ Read-your-writes consistency ]

  如果Process A更新了v值,那么Process A的后续对v值的读取操作,都将获得这个已经被更新了的v值,而不会获得一个旧的数值。

  • 会话一致性[ Session consistency ]

  在客户端及服务端交互的整个Session过程中,只要Session一直存在,那么就必须保证Read-your-writes consistency。如果Session由于某种原因关闭了,新建立的Session需要保证不会与之前的Session存在重叠关系,必须保证Session的独立性。

  • 单调读一致性[ Monotonic read consistency ]

  如果Process A读取到v的某特定的值,那么关于Process A的后续操作,将不会获取到这个值之前的旧值。

  • 单调写一致性[ Monotonic write consistency ]

  系统必须保证来自同一个进程的写操作顺序执行。要是系统不能保证这种程度的一致性,就会出现难以控制的情况。

 

以上特性,是可以联合在一起使用的,例如Monotonic write consistency和Session consistency,以及monotonic reads和read-your-writes。

 

从服务端[ Server]角度来看[ NRW理论 ]:

为了说明服务端中一致性的问题,先说明几个相关术语:

  • N= 系统中存储数据的备份数

  • W= 某个数据的写操作被执行完毕前,需要更新的数据备份数

  • R=在某个读操作执行时,需要交互的数据备份数

  当W+R>N时,那么关于读操作与写操作将会在备份的数据节点上产生重叠,一个成功的读操作总能在某个备份节点上获得最新的写操作,保证了数据的一致性。

  当W+R =< N时,数据一致性的特性就无法保证了。可以有这样的一个场景,当N中的W个节点中的数据v被更新后,一个读操作从剩余的N-W节点中读取数据v,此读出出来的v值,将是一个过期的数值。此时的数据一致性将只能由异步更新来保证。

  在某些极端的情况下,有W=N的使用场景。虽然这种场景能保证冗余数据达到高度的一致性,但是这种场景存在着极大的弊端,当N中某些个节点不可用时,将会导致所有的写操作无法成功。在一些数据一致性要求不高的使用场景,可以配置一个很高的N值,而R=1,这能提供高效率的读操作。对一些写操作效率要求很高的场景,可以配置成N=R、W=1。

  在(N+1)/2>W的场景,可能导致两个不同的写操作没有重叠的节点,使得N个节点备份中存在着两份无法识别先后顺序的数据。

  常用的使用场景是N=3,W=2,R=2。

 

  CAP是一个完美的指导理论,但是在实际的系统开发应用中,却只能保证Consistency,Availability和Partition Tolerance中的两方面。对于不同的需求功能,分布式系统的设计需要根据实际情况作出取舍。

 

参考引用:

http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

http://www.allthingsdistributed.com/2008/12/eventually_consistent.html


© 著作权归作者所有

上一篇: Vector Clock
Poorzerg
粉丝 12
博文 21
码字总数 23485
作品 0
深圳
程序员
私信 提问
浅谈 CAP 理论

原文同步至 本文介绍了介绍了分布式系统著名的 CAP 理论。什么是 CAP 理论?为什么说 CAP 只能三选二?了解 CAP 对于系统架构又有什么指导意义?本文将一一作答。 什么是 CAP 理论 在计算机科...

waylau
2016/02/28
3.9K
10
NoSQL 数据库不应该放弃 Consistency

本文发于infoq,https://www.infoq.cn/article/rhzs0KI2G*Y2r9PMdeNv 。转回自己的博客。 谈到 NoSQL,一定会提及一致性(Consistency),按照 CAP 定理,有些 NoSQL 数据库放弃了一致性,但...

cadem
2019/06/11
0
0
MongoDB

NoSQL(NoSQL = Not Only SQL ),意即"不仅仅是SQL"。 在现代的计算系统上每天网络上都会产生庞大的数据量。 这些数据有很大一部分是由关系数据库管理系统(RDMBSs)来处理。 1970年 E.F.Codd...

5431039
2016/04/17
0
0
分布式存储系统设计的若干原则

1、CAP理论 2000年Eric Brewer教授提出了著名的CAP理论,即:一个分布式系统不可能满足一致性,可用性和分区容错性这三个需求,最多只能同时满足两个。2002年MIT的Seth Gilbert 和 Nancy ly...

红薯
2011/08/10
422
1
「系统架构」CAP 定理的含义

分布式系统(distributed system)正变得越来越重要,大型网站几乎都是分布式的。 分布式系统的最大难点,就是各个节点的状态如何同步。CAP 定理是这方面的基本定理,也是理解分布式系统的起...

Java填坑之路
2018/07/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

应急广播户户通平台

一、平台概述 应急广播户户通平台为软硬一体化广播服务解决方案。实现了应急广播、视音频及图片文字信息、调频及数字广播FM、天气预报信息接收功能,以及视音频播放、智能机器人、电子日历等...

neocean
26分钟前
39
0
如何为Apache 2.2启用mod_rewrite

我已经在我的Vista机器上安装了新的Apache 2.2,一切正常,除了mod重写。 我没有注释 LoadModule rewrite_module modules/mod_rewrite.s 但是我的重写规则都没有,即使是简单的重写规则 Re...

javail
32分钟前
23
0
移除Python unicode字符串中的重音符号的最佳方法是什么?

我在Python中有一个Unicode字符串,我想删除所有的重音符号(变音符号)。 我在网上发现了一种用Java实现此目的的优雅方法: 将Unicode字符串转换为长规范化格式(带有单独的字母和变音符号)...

技术盛宴
48分钟前
48
0
ActiveMQ学习之SpringBoot整合ActiveMQ------>主题生产者和消费者

一、pom <!--聚合工程集成关系--> <!--统一整合第三方框架依赖信息--> <parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</a......

冥焱
今天
75
0
两周自制脚本语言-第11天 优化变量读写性能

第11天 优化变量读写性能 以变量值的读写为例,向读者介绍基于这种理念的语言处理器性能优化方式。 11.1 通过简单数组来实现环境 假如函数包含局部变量x与y,程序可以事先将x设为数组的第0个...

果汁分你一半
今天
52
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部