CAP理论十二年回看

正文先发于 
Computer杂志,由InfoQ和IEEE突显给你。

CAP理论断言任何依据网络的数量共享系统,最八只好满足数码一致性、可用性、分区容忍性三要素中的五个要素。可是透过显式处理分区情状,系统设计师可以做到优化数据一致性和可用性,进而得到三者之间的平衡。

从今引入CAP理论的十几年里,设计师和探究者已经以它为理论基础探索了五光十色新颖的分布式系统,甚至到了滥用的水平。NoSQL运动也将CAP理论作为对抗传统关系型数据库的依照。

CAP理论主张任何根据网络的数码共享系统,都最五只好拥有以下三条中的两条:

  • 数量一致性(C),等同于所有节点访问同一份最新的数量副本;
  • 对数据更新具有高可用性(A);
  • 能容忍网络分区(P)。

CAP理论的抒发很好地服务了它的目标,即开展设计师的思绪,在多样化的采用方案下统筹出多样化的连串。在过去的十几年里真的涌现了洋洋洒洒的新系统,也随即在数量一致性和可用性的对峙关系上发生了一定多的争执。“三选二”的公式平昔留存着误导性,它会过分简单化各性质之间的互相关系。现在大家有要求辨析其中的底细。实际上唯有“在分区存在的前提下显现周详的数量一致性和可用性”那种很少见的情况是CAP理论不容许出现的。

固然如此设计师如故需求在分区的前提下对数码一致性和可用性做选用,但现实什么处理分区和还原一致性,那其中有不可胜举的生成方案和灵活度。当代CAP实践应将目的定为针对现实的接纳,在合理界定内最大化数据一致性和可用性的“合力”。那样的思路延伸为怎么规划分区时期的操作和分区之后的东山再起,从而诱发设计师加深对CAP的认识,突破过去由于CAP理论的表述而暴发的思想局限。

Why “2 of 3” is missleading 为何“三选二”公式有误导性

知道CAP理论的最简易方法是想象四个节点分处分区两侧。允许至少一个节点更新境况会促成数据差距,即丧失了C性质。假诺为了保险数据一致性,将分区一侧的节点设置为不可用,那么又丧失了A性质。除非多个节点能够相互通讯,才能既有限支撑C又保险A,那又会促成丧失P性质。一般的话跨区域的种类,设计师不可以舍弃P性质,那么就只可以在多少一致性和可用性上做一个不便抉择。不确切地说,NoSQL运动的大旨其实是创造各个可用性优先、数据一致性其次的方案;而传统数据库遵从ACID特性(原子性、一致性、隔离性、持久性),做的是相反的事体。下文“ACID、BASE、CAP”小节详细表达了它们的差别。

实际上,CAP理论本身就是在相近的琢磨中出生的。早在1990年间中期,我和共事构建了一名目繁多的按照集群的跨区域系统(实质上是最初的云计算),包罗搜索引擎、缓存代理以及内容分发系统1。从收入目的以及合同规定来讲,系统可用性是根本目标,因此大家例行会利用缓存或者未来校核更新日志来优化系统的可用性。即使那么些策略升高了系统的可用性,但那是以就义系统数据一致性为代价的。

至于“数据一致性 VS
可用性”的首先回合顶牛,表现为ACID与BASE之争2。当时BASE还不怎么被人们接受,紧倘若大家尊崇ACID的助益而不愿意舍弃。提出CAP理论,目的是注明有必不可少开拓更广大的统筹空间,因而才有了“三选二”公式。CAP理论最早在1998年夏季提出,1999年专业发表3,并在2000年登上Symposium
on Principles of Distributed
Computing大会的主题解说4,最终创造了该辩护的不易。

“三选二”的见解在多少个地点起了误导功用,详见下文“CAP之惑”小节的诠释。首先,由于分区很少暴发,那么在系统不设有分区的意况下没什么理由牺牲C或A。其次,C与A之间的取舍可以在一如既往系统内以那么些细小的粒度反复暴发,而每五遍的仲裁可能因为具体的操作,乃至因为牵涉到特定的数据或用户而有所不一样。最终,那三种属性都得以在档次上衡量,并不是非黑即白的有或无。可用性显著是在0%到100%中间连续变化的,一致性分很多级别,连分区也得以细分为不一致含义,如系统内的两样部分对于是还是不是存在分区可以有差距等的回味。

要探索这一个微小的差异,就要突破传统的分区处理方式,而那是一项根本性的挑衅。因为分区很少出现,CAP在超过半数时候允许完美的C和A。但当分区存在或可感知其影响的景观下,就要预备一种政策去探知分区并显式处理其震慑。那样的政策应分为三个步骤:探知分区发生,进入显式的分区情势以限制某些操作,启动复苏进程以平复数据一致性并补足够区时期爆发的荒唐。

ACID、BASE、CAP

ACID和BASE代表了三种截然相反的设计军事学,分处一致性-可用性分布图谱的两极。ACID器重一致性,是数据库的历史观设计思路。我和同事在1990年间前期提议BASE,目标是诱惑当时正渐渐成型的局地针对高可用性的筹划思路,并且把分歧性质之间的精选和消长关系摆上台面。现代大面积跨区域分布的种类,包涵云在内,同时采纳了这三种思路。

那七个术语都好记有余而标准不足,出现较晚的BASE硬凑的觉得更明显,它是“Basically
Available, Soft state, 伊夫ntually
consistent(基本可用、软状态、最后一致性)”的首字母缩写。其中的软状态和终极一致性那三种技术擅于对付存在分区的场馆,并因而提升了可用性。

CAP与ACID的关系更复杂一些,也就此引起更加多误解。其中一个原因是ACID的C和A字母所代表的概念不相同于CAP的C和A。还有一个缘故是拔取可用性唯有些地影响ACID约束。ACID四项特征分别为:

原子性(A)。所有的连串都受惠于原子性操作。当我们着想可用性的时候,没有理由去改变分区两侧操作的原子性。而且满意ACID定义的、高抽象层次的原子操作,实际上会简化分区苏醒。

一致性(C)。ACID的C指的是业务不可能破坏其余数据库规则,如键的唯一性。与之比较,CAP的C仅指单一副本那么些意思上的一致性,由此只是ACID一致性约束的一个严刻的子集。ACID一致性不容许在分区进度中保持,由此分区恢复生机时索要重建ACID一致性。推而广之,分区时期可能不容许维持某些不变性约束,所以有必不可少仔细考虑怎么样操作应该禁止,分区后又怎样回复这几个不变性约束。

隔离性(I)。隔离是CAP理论的着力:若是系统须求ACID隔离性,那么它在分区时期最多可以在分区一侧维持操作。事务的可串行性(serializability)须要全局的通讯,因而在分区的情况下不能够树立。只要在分区苏醒时进行补充,在分区前后保持一个较弱的不利定义是可行的。

持久性(D)。就义持久性没有意义,理由和原子性一样,就算开发者有理由(持久性开支太高)选拔BASE风格的软状态来防止完成持久性。那里有一个细节,分区复苏可能因为回退持久性操作,而无心中损坏某项不变性约束。但一旦恢复生机时给定分区两侧的持久性操作历史记录,破坏不变性约束的操作还是能被检测出来并改良的。日常来讲,让分区两侧的事情都满意ACID特性会使得后续的分区复苏变得更便于,并且为分区恢复生机时工作的增补工作奠定了主题的尺度。

CAP和延期的关系

CAP理论的经典解释,是忽视网络延迟的,但在实际上中延迟和分区紧密有关。CAP从理论变为现实的情景暴发在操作的刹车,系统须要在那段时日内做出关于分区的一个要害决定:

  • 撤除操作由此下落系统的可用性,还是

  • 后续操作,以冒险损失系统一致性为代价

看重多次尝试通讯的不二法门来落成一致性,比如Paxos算法或者两品级工作提交,仅仅是推迟了决策的时间。系统终究要做一个操纵;无限期地品尝下去,本身就是选项一致性捐躯可用性的表现。

于是以实际效果而言,分区相当于对通讯的限期须要。系统一旦不可能在定期内达到数据一致性,就意味着暴发了分区的气象,必须就近来操作在C和A之间做出抉择。那就从延迟的角度抓住了规划的主干问题:分区两侧是还是不是在无通讯的意况下继续其操作?

从那一个实用的观赛角度出发可以导出若干重点的测算。第一,分区并不是整套节点的同样意见,因为有些节点检测到了分区,有些可能没有。第二,检测到分区的节点即进入分区格局——那是优化C和A的着力环节。

最后,这几个观望角度还意味着设计师可以根据期望中的响应时间,有意识地设置时限;时限设得越短,系统进入分区形式越频仍,其中有些时候并不一定真的发生了分区的情状,可能只是网络变慢而已。

偶尔在跨区域的系统,舍弃强一致性来避免保持数据一致所带来的高延迟是充足有含义的。Yahoo的PNUTS系统因为以异步的艺术维护远程副本而带来多少一致性的题材5。但利益是主副本就坐落地面,减小操作的守候时间。那个政策在其实中很实用,因为一般来讲,用户数据大概会根据用户的(日常)地理地点做分区。最突出的光景是每一位用户都在他的多少主副本附近。

脸书使用了反而的政策6:主副本被一定在一个地点,由此远程用户一般访问到的是离他较近,但恐怕早就不合时宜的数目副本。可是当用户更新其页面的时候是一直对主副本进行更新,而且该用户的装有读操作也被短暂转向从主副本读取,即使那样延迟会比较高。20秒后,该用户的流量被重新切换回离他较近的副本,此时副本应该早就一起好了刚刚的立异。

CAP之惑

CAP理论常常在差别方面被人误会,对于可用性和一致性的功效范围的误解尤为严重,可能引致不指望见到的结果。如若用户根本获取不到服务,那么实际上谈不上C和A之间做接纳,除非把部分服务放在客户端上运行,即所谓的无连接操作或称离线方式7。离线情势正变得愈加主要。HTML5的片段特性,越发是客户端持久化存储特性,将会助长离线操作的进步。接济离线形式的系统常常会在C和A中接纳A,那么就不得不在长日子处在分区状态后举办苏醒。

“一致性的效用范围”其实反映了如此一种观念,即在必然的分界内景况是平等的,但不止了界线就无从谈起。比如在一个主分区内足以确保完备的一致性和可用性,而在分区外服务是不可用的。Paxos算法和原子性多播(atomic
multicast)系统一般符合那样的气象8。像谷歌的一半做法是将主分区归属在单一个多少焦点内部,然后提交Paxos算法去化解跨区域的问题,一方面保险全局协商一致(global
consensus)如Chubby9,一方面完结高可用的持久性存储如Megastore10

分区时期,独立且能自我有限支撑一致性的节点子集合可以继续执行操作,只是不可以确保全局范围的不变性约束不受破坏。数据分片(sharding)就是这么的事例,设计师预先将数据划分到差别的分区节点,分区时期单个数据分片多半可以继承操作。相反,倘若被分区的是内在提到密切的图景,或者有几许全局性的不变性约束非维持不可,那么最好的景况是唯有分区一侧可以拓展操作,最坏情况是操作完全无法举办。

“三选二”的时候取CA而舍P是不是站得住?已经有探讨者提议了里面的重中之重——怎么着才算“舍P”含义并不醒目11,12。设计师可以挑选不要分区吗?哪怕原来选了CA,当分区出现的时候,你也不得不回头重新在C和A之间再选五次。大家最好从概率的角度去了然:采纳CA意味着大家尽管,分区出现的可能性要比任何的系统性错误(如自然磨难、并发故障)低很多。

这种观点在实际上中很有意义,因为某些故障组合可能导致同时丢掉C和A,所以说CAP多少个特性都是一个度的问题。实践中,大部分团队认为(位于单一地方的)数据主导内部是从未分区的,因而在单一数据主旨之内可以选用CA;CAP理论出现往日,系统都默许那样的布置思路,包蕴传统数据库在内。不过就是可能性不高,单一数据基本完全有可能出现分区的动静,一旦出现就会动摇以CA为主旋律的设计基础。最终,考虑到跨区域时出现的高延迟,在数量一致性上和解来换取更好性能的做法相相比较广泛。

CAP还有一个上边许四个人认识不清,那就是割舍一致性其实有藏身负担,即须求肯定驾驭系统中存在的不变性约束。知足一致性的系统有一种保持其不变性约束的本来倾向,尽管设计师不了然系统中拥有的不变性约束,非凡部分客观的不变性约束会活动地维持下去。相反,当设计师接纳可用性的时候,因为须要在分区截止后重操旧业被毁坏的不变性约束,明显必须将种种不变性约束一一列举出来,总而言之那件工作很有挑衅又很不难犯错。废弃一致性为何难,其主干仍旧“并发革新问题”,跟四线程编程比顺序编程难的原故是同一的。

管制分区

怎么缓和分区对一致性和可用性的熏陶是对设计师的挑衅。其利害攸关是以那些掌握、公开的方法去管理分区,不仅必要积极发现分区的暴发,还索要为分区时期具有可能受侵蚀的不变性约束预备专门的死灰复燃进度和安排。管理分区有七个步骤:

(点击看大图)

必发bifa88手机客服端 1

  • 检测到分区初阶
  • 精通进入分区方式,限制某些操作,并且
  • 当通讯復苏后开行分区恢复生机进度

终极一步的目标是回复一致性,以及补充在系统分区时期先后暴发的一无所长。

图1凸现分区的演变进度。普通的操作都是逐一的原子操作,因而分区总是在两笔操作之间开始。一旦系统在操作停顿检测到分区暴发,检测方一侧即进入分区情势。若是确实发生了分区的状态,那么一般分区两侧都会跻身到分区形式,可是另一方面落成分区也是可能的。单方面分区要求在对方按必要通讯的时候,本方要么能科学响应,要么不必要通讯;总而言之操作不得毁损一致性。但无论是怎样,由于检测方可能有分化的操作,它必须进入分区方式。采用了quorum决定机制的种类即为单方面分区的例证。其中一方拥有“法定通过节点数”,由此得以实施操作,而另一方不可以举行操作。协理离线操作的系列明显地蕴藏“分区方式”的定义,一些支持原子多播(atomic
multicast)的连串也富含那一个概念,如Java平台的JGroups。

当系统进入到分区情势,它有三种有效的方针。其一是限量部分操作,由此会削弱可用性。其二是额外记录一些便宜后边分区復苏的操作新闻。系统可透过不断尝试復苏通讯来察觉分区哪天甘休。

何以操作可以执行?

操纵限制哪些操作,主要在于系统必要保持哪几项不变性约束。在给定了不变性约束原则之后,设计师必要控制在分区情势下,是或不是持之以恒不激动某项不变性约束,抑或以事后复原为前提去冒险触犯它。例如,对于“表中键的惟一性”那项不变性约束,设计师一般都采用在分区时期放宽须要,容许重复的键。重复的键很不难在平复阶段检查出来,若是重复键可以统一,那么设计师简单恢复生机那项不变性约束。

对此分区期间必须维持的不变性约束,设计师应当禁止或转移可能触犯该不变性约束的操作。(一般而言,大家不可能知道操作是还是不是真正会破坏不变性约束,因为无法知道分区另一侧的状态。)信用卡扣费等具有外部化特征的事件常以那种措施工作。适合那种情景的政策,是记录下操作意图,然后在分区复苏后再实施操作。那类事务往往从属于有些更大的工作流,在工作流明确涵盖类似“订单处理中”状态的景色下,将操作推迟到分区截止并无显明的弊端。设计师以用户正确察觉的措施就义了可用性。用户只略知一二自己下了指令,系统稍后会举行。

说得更囊括一点,分区格局给用户界面提出了一种根本性的挑衅,即什么传达“职分正在拓展尚未成功”的音信。研讨者已经从离线操作的角度对此题材开展了有些深深的探索,离线操作可以当做时间很长的三次分区。例如Bayou的日历程序用颜色来分化显示可能(暂时)不同的条条框框13。工作流应用和带离线方式的云服务中也普遍类似的提醒,前者的例证如交易中的电子邮件布告,后者的事例如谷歌Docs。

在分区情势的座谈中,大家将关注点放在有肯定意义的原子操作而非单纯的读写,其中一个原因是操作的抽象级别越高,对不变性约束的震慑普通就越不难分析清楚。大体来说,设计师要确立一张保有操作与持有不变性约束的叉乘表格,观察并规定里头每一处操作可能与不变性约束相争论的地方。对于那么些争辨景况,设计师必须决定是还是不是禁止、推迟或改动相应的操作。在实践中,那类决定还面临分区前意况和/或环境参数的影响。例如有些系统为一定的数量设立了主节点,那么一般允许主节点实施操作,差距意任何节点操作。

对分区两侧跟踪操作历史的特等办法是选择版本向量,版本向量可以突显操作间的报应重视关系。向量的因素是(节点,
逻辑时间)数值对,分别对应一个立异了指标的节点和它说到底更新的年月。对于同样对象的三个给定的版本A和B,当有着结点的本子向量一致有A的时辰大于或等于B的小时,且至少有一个节点的本子向量有A的时刻较大,则A新于B。

要是不能对版本向量排序,那么更新操作是出现的,而且有可能出现分歧等的气象。只要了解分区两侧版本向量的沿革。系统不难断定哪些操作的实践各样是确定的,哪些操作是出现的。近日的研商成果表明14,当设计师选用可用性优先,一般最四只可以将一致性收紧到这么的档次。

分区恢复生机

到了某个时刻,通讯苏醒,分区甘休。由于每一侧在分区时期都是可用的,其场地仍蝉联上前进展,可是分区会推迟某些操作并侵略一些不变性约束。分区截至的随时,系统精通分区两侧的当前事态和历史记录,因为它在分区方式下记录了详细的日记。当前情况不如历史记录有价值,因为通过历史记录,系统可以看清哪些操作违反了不变性约束,爆发了何种外在的结果(如发送了响应给用户)。在分区苏醒过程中,设计师必须解决八个问题:

  • 分区两侧的图景最后必须保持一致,
  • 再就是必须补偿分区时期产生的不当。

一般说来状态,纠正当前情况最简易的缓解方法是回退到分区早先时的场所,以一定措施推进分区两侧的一多级操作,并在进度中直接保持一致的气象。Bayou就是以此完结机制,它会回滚数据库到正确的时刻并按无歧义的、确定性的次第重新履行所有的操作,最后使拥有的节点达到平等的意况15。同样地,并发版本决定连串CVS在集合分支的时候,也是从从一个共享的状态一致点先导,稳步将履新合并上去。。

多数系统都存在不能自动合并的龃龉。比如,CVS时不时有些争执须求手动出席,带离线方式的wiki系统连接把顶牛留在爆发的文档里给用户处理16

反而,有些系统用了限定操作的主意来担保抵触总能合并。一个例证就是谷歌(Google)Docs将其文本编辑操作17简短为利用样式、添加文(加文)本和删除文本。由此,纵然总的来说顶牛问题不可解,但具体中设计师可以挑选在分区时期限制使用部分操作,以便系统在復苏的时候可以自行合并状态。若是要实践那种政策,推迟有风险的操作是相对简便易行的落到实处形式。

再有一种艺术是让操作可以沟通顺序,那种措施最相近于形成一种缓解机关状态合并问题的通用框架。此类系统将线性合并各日志仁同一视排操作的次第,然后实施。操作满意交流率,意味着操作有可能重新排列成一种全局一致的特等顺序。不幸的是,只允许满意调换率的操作那几个想法兑现起来没那么简单。比如加法操作能够交流顺序,不过进入了越界检查的加法就充足了。

Marc
Shapiro及其INRIA同事近期的办事18,19对于可调换顺序的操作在场馆合并方面的拔取起了很大的促进成效。该集体提议一种从理论上证实方可确保分区后联合的数据类型,称为可互换多副本数据类型(commutative
replicated data types,CRDTs)。他们介绍了怎么运用此类数据结构来

  • 管教分区时期开展的具有操作都是可沟通顺序的,或者
  • 用“格(lattice)”的数学概念来代表数据,并保险相对于“格”来说,分区时期的有所操作都是乏味递增的。

用后一种方法统一状态会集中分区两边的最大聚合。那种办法是对Amazon购物车合并算法20的方式化统计和考订,合并后的多寡是两边购物车的并集,而并运算是一种干燥的成团运算。那种策略的弊端是删掉的购物车货物有可能再一次现身。

其实CRDTs完全可以兑现同时支持增、删操作的分区耐受集合。此措施的本来面目是保证多个聚众:一个放扩充的花色,一个放删除的档次,两集合之差即为真正的聚合成员。增集合、删集合分别合并起来都不困难,因此增删集合之差合并起来也不困难。在某个时刻点上,系统能够从两个汇聚中清理掉删除的多少项。如果根据一般的宏图,像那种清理操作仅在系统没分区的时候才有效,属于设计师必须在分区时期不准或延迟的特定操作,可是CRDTs的清理操作并不会对可用性发生外在的震慑。因而通过CRDTs来完毕情形,设计师既有限支撑了可用性,又确保了分区后系统活动合并状态。

增补错误

比揣测分区后情形更难解决的题目是怎么弥补分区时期造成的一无所能。跟踪和限量分区方式下的操作,那三种艺术可以使设计师确知哪些不变性约束可能被违反,然后分别为它们制定苏醒策略。一般系统在分区恢复生机时期检查违反景况,修复工作也必须在那段日子内成功。

光复不变性约束的方法有成百上千,粗陋一点的法子如“最终写入者胜”(由此会忽略部分更新),聪贝因美点的办法如合并操作和人为跟进事态(human
escalation)。人为跟进事态的事例如飞机航班“超售”的情形:可以把游客登机看作是对后边售票情况的分区苏醒,必须恢复生机“座位数不少于游客数”那项不变性约束。那么当游客太多的时候,有些乘客将失去座位,客服最好能想法补偿他们。

航班的事例揭穿了一个外在错误(externalized
mistake):若是航空公司没说过游客一定有坐席,这些问题会好解决得多。因而大家见到推迟有高风险的操作的又一个说辞——到了分区恢复生机的时候,我们才了然真实的情况。考订此类错误的主旨概念是“补偿(compensation)”;设计师必须设置补偿操作,除了回复不变性约束,还要改进外在错误。

技巧上CRDTs只同意一些可验证的不变性约束,所以没有补偿的须求,纵然那种范围下降了CRDTs方法本身的力量。用了CRDTs来拍卖情形合并的设计方案可以允许临时违反全局性的不变量约束,分区停止后才统一状态,以及履行须求的互补。

卷土重来外在错误平时要求领悟有些关于外在输出的野史新闻。以“喝醉酒打电话”为例,一位老兄不记得自己明晚喝高了的时候打过多少个电话,纵然她第二天白天卷土重来了正常情形,但打电话日志上的笔录都还在,其中有些通话很可能是不对的。拨出的电话就是那位兄长的情形(喝高了)的外在影响。而出于这位兄长不记得打过什么电话,也就很难补偿其中可能引致的麻烦。

又以机械为例,电脑可能在分区时期把一份订单执行了两遍。假设系统能分别两份一样的订单是蓄意的要么重新了,它就能收回掉一份重复的订单。假若本次错误发生了外在影响,补偿政策可以是自动生成一封电子邮件,向消费者解释系统竟然将订单执行了两遍,现在错误已经被矫正,附上一张打折券下次可以用。如果没有两全的历史记录,就不得不靠顾客亲自去发现错误了。

已经有人专业商讨过将补偿性事务作为处理长寿命事务(long-lived
transactions)的一种手段21,22。长日子运作的事务会合临另一种形象的分区决策:是长日子持有锁来有限支撑一致性相比好吧?依然赶紧释放锁向此外事情暴光未提交的数据,进步并发能力相比可以吗?比如在单笔事务中创新具有的员工记录就是一个出色例子。按照一般的法子串行化那笔业务,将造成所有的笔录都被锁定,阻止并发。而补偿性事务选择另一种方法,它将大事务拆成多少个分级交由的子事务。若是要暂停大事务,系统必须发起一笔新的、起校正效率的工作,逐一取消所有曾经付出的子事务,那笔新工作就是所谓的补偿性事务。

如上所述,补偿性事务的目的是幸免中止其余用了未正确提交数据的工作(即不允许级联废除)。那种方案不借助串行化或切断的手腕来有限支撑科学,其不易取决于事务种类对意况和输出所爆发的净影响。那么,经过补充,数据库的气象究竟是还是不是一定于那多少个子事务根本没执行过千篇一律啊?考虑卓殊必须连外在表现也包蕴在内;举个例子,把重复扣取的交易款退还给顾客,很难说成等于一上马就没多收顾客的钱,但从结果上看勉强算扯平了。分区復苏也三番五次同样的思路。尽管服务不自然总能直接注销其错误,但起码认可错误并做出新的互补作为。如何在分区复苏中动用这种思路效果最好,这么些题目从未永恒的答案。“自动柜员机上的补充问题”小节以一个很小的应用领域为例点出了有的思想方向。

当系统中存在分区,系统设计师不该盲目地捐躯一致性或可用性。运用以上琢磨的点子,设计师通过细致入微地管理分区时期的不变性约束,两上面的性质都得以收获最佳的显现。随着版本向量和CRDTs等相比新的技术逐步被纳入一些简化其用法的框架,这下面的优化手段会获得相比较普遍的利用。但引入CAP实践毕竟不像引入ACID事务那么粗略,实施的时候需要对过去的政策进行周详的设想,最佳的实施方案极大地借助于具体服务的不变性约束和操作细节。

机关柜员机上的补偿问题

以自动柜员机(ATM)的规划来说,强一致性看似符合逻辑的取舍,但现实景况是可用性远比一致性主要。理由很不难:高可用性意味着高收入。不管什么样,商讨什么补丰裕区期间被毁掉的不变性约束,ATM的安插性很适合当作例子。

ATM的基本操作是存款、取款、查看余额。关键的不变性约束是余额应当先或等于零。因为唯有取款操作会触犯那项不变性约束,也就只有取款操作将碰着更加对待,其余二种操作随时都足以实施。

ATM系统设计师可以挑选在分区时期不准取款操作,因为在那段时光里无法知道真实的余额,当然如此会危害可用性。现代ATM的做法正相反,在stand-in形式下(即分区情势),ATM限制净取款额不得高于k,比如k为$200。低于限额的时候,取款完全正常;当跨越限额的时候,系统拒绝取款操作。那样,ATM成功将可用性限制在一个客观的档次上,既允许取款操作,又限定了风险。

分区甘休的时候,必须有一对措施来平复一致性和互补分区时期系统所导致的一无可取。状态的过来比较不难,因为操作都是符合交流率的,补偿就要分三种景况去考虑。最终的余额低于零违反了不变性约束。由于ATM已经把钱吐出去了,错误成了表面实在。银行的补给办法是吸收透支费并期望顾客偿还。因为风险已经碰着限制,问题并不严重。还有一种情状是分区时期的某说话余额已经低于零(但ATM不知道),此时一笔存款重新将余额变为正的。银行可以追溯暴发透支费,也可以因为消费者曾经缴纳而忽视该违反情形。

一言以蔽之,因为通信延迟的留存,银行种类不借助于一致性来担保科学,而越来越多地依靠审计和增补。“空头支票诈骗”也是看似的例子,顾客赶在多家分行对账从前分别取出钱来然后桃之夭夭。透支的失实过后才会被察觉,对错误的补偿或者展现为法律行动的款型。

致谢

必发bifa88手机客服端,感谢迈克(Mike) Dahlin、汉克 Korth、Marc Shapiro、Justin Sheehy、Amin
Vahdat、Ben Zhao以及IEEE Computer
Society的志愿者们,感谢他们对本文的有益反馈。

小编简介

Eric Brewer是University of California,
贝克莱(Berkeley)(Berkeley)的电脑科学讲师,在谷歌(Google)担任基础设备方面的VP。他的商量兴趣包括云统计、可伸缩的服务器、传感器网络,还有符合发展中地区使用的技能。他还拉扯建立了美联邦政坛的门户网站USA.gov。Brewer从MIT得到电子工程和电脑科学的博士学位。他是National
Academy of Engineering的院士。联系方式:brewer@cs.berkeley.edu

必发bifa88手机客服端 2Computer杂志是IEEE
Computer
Society的旗舰刊物,发布经过同行评议的高水准文章,读者和作者都是致力各种统计科学技术相关领域的专业人士,作品包涵的限量包罗软硬件的新商量和新利用。那本杂志比经贸杂志更偏重技术内涵,比探讨期刊更讲求实用思维。Computer为你传递工作中用得上的信息。

参考文献

  1. E. Brewer, “Lessons from Giant-Scale Services,” IEEE Internet
    Computing
    , July/Aug. 2001, pp. 46-55.
  2. A. Fox et al., “Cluster-Based Scalable Network Services,” Proc. 16th
    ACM Symp. Operating Systems Principles (SOSP 97), ACM, 1997, pp.
    78-91.
  3. A. Fox and E.A. Brewer, “Harvest, Yield and Scalable Tolerant
    Systems,” Proc. 7th Workshop Hot Topics in Operating Systems (HotOS
    99), IEEE CS, 1999, pp. 174-178.
  4. E. Brewer, “Towards Robust Distributed Systems,” Proc. 19th Ann. ACM
    Symp.Principles of Distributed Computing
    (PODC 00), ACM, 2000, pp.
    7-10; on-line
    resource
    .
  5. B. Cooper et al., “PNUTS: Yahoo!’s Hosted Data Serving Platform,”
    Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288.
  6. J. Sobel, “Scaling Out,” Facebook Engineering Notes, 20 Aug. 2008;
    on-line
    resource
    .
  7. J. Kistler and M. Satyanarayanan, “Disconnected Operation in the Coda
    File System” ACM Trans. Computer Systems, Feb. 1992, pp. 3-25.
  8. K. Birman, Q. Huang, and D. Freedman, “Overcoming the ‘D’ in CAP:
    Using Isis2 to Build Locally Responsive Cloud Services,” Computer,
    Feb. 2011, pp. 50-58.
  9. M. Burrows, “The Chubby Lock Service for Loosely-Coupled Distributed
    Systems,” Proc. Symp. Operating Systems Design and Implementation
    (OSDI 06), Usenix, 2006, pp. 335-350.
  10. J. Baker et al., “Megastore: Providing Scalable, Highly Available
    Storage for Interactive Services,” Proc. 5th Biennial Conf. Innovative
    Data Systems Research
    (CIDR 11), ACM, 2011, pp. 223-234.
  11. D. Abadi, “Problems with CAP, and Yahoo’s Little Known NoSQL
    System,” DBMS Musings, blog, 23 Apr. 2010; on-line
    resource.
  12. C. Hale, “You Can’t Sacrifice Partition Tolerance,” 7 Oct. 2010;
    on-line
    resource
    .
  13. W. K. Edwards et al., “Designing and Implementing Asynchronous
    Collaborative Applications with Bayou,” Proc. 10th Ann. ACM Symp. User
    Interface Software and Technology
    (UIST 97), ACM, 1999, pp. 119-128.
  14. P. Mahajan, L. Alvisi, and M. Dahlin, Consistency, Availability,
    and Convergence
    , tech. report UTCS TR-11-22, Univ. of Texas at Austin,
  15. D.B. Terry et al., “Managing Update Conflicts in Bayou, a Weakly
    Connected Replicated Storage System,” Proc. 15th ACM Symp. Operating
    Systems Principles
    (SOSP 95), ACM, 1995, pp. 172-182.
  16. B. Du and E.A. Brewer, “DTWiki: A Disconnection and Intermittency
    Tolerant Wiki,” Proc. 17th Int’l Conf. World Wide Web (WWW 08), ACM,
    2008, pp. 945-952.
  17. “What’s Different about the New Google Docs: Conflict Resolution”
    blog.
  18. M. Shapiro et al., “Conflict-Free Replicated Data Types,” Proc.
    13th Int’l Conf. Stabilization, Safety, and Security of Distributed
    Systems
    (SSS 11), ACM, 2011, pp. 386-400.
  19. M. Shapiro et al., “Convergent and Commutative Replicated Data
    Types,” Bulletin of the EATCS, no. 104, June 2011, pp. 67-88.
  20. G. DeCandia et al., “Dynamo: Amazon’s Highly Available Key-Value
    Store,” Proc. 21st ACM SIGOPS Symp. Operating Systems Principles (SOSP
    07), ACM, 2007, pp. 205-220.
  21. H. Garcia-Molina and K. Salem, “SAGAS,” Proc. ACM SIGMOD Int’l
    Conf. Management of Data
    (SIGMOD 87), ACM, 1987, pp. 249-259.
  22. H. Korth, E. Levy, and A. Silberschatz, “A Formal Approach to
    Recovery by Compensating Transactions,” Proc. VLDB Endowment (VLDB
    90), ACM, 1990, pp. 95-106

原稿链接:CAP Twelve Years Later: How the “Rules” Have
Changed

粤语原文链接:CAP理论十二年回看:”规则”变了

相关文章