CAP理论十二年回顾:”规则”变了

By admin in 亚洲必赢app在哪下载 on 2018年10月7日

本文首发于 
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, Eventually
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。但便宜是主副本就位于地面,减小操作的等候时。这个策略在实际被生实用,因为一般来讲,用户数量差不多会因用户之(日常)地理位置做分区。最美好的场景是各个一样各用户还在他的数量主副本附近。

Facebook使用了相反的国策6:主副本被固化在一个地方,因此远程用户一般访问到的凡离他于近,但或许早就不合时宜的数目副本。不过当用户更新其页面的上是直指向主副本进行更新,而且该用户的具备读操作也受急促转向自主副本读取,尽管这样延迟会比较强。20秒后,该用户的流量被再次切换回离他于近之副本,此时副本应该都联手好了方之换代。

CAP之惑

CAP理论时以不同点给人误会,对于可用性和一致性的图范围之误解尤为严重,可能致不指望见到底结果。如果用户从获取不顶劳动,那么实际上谈不达到C和A之间做选择,除非把有些劳动在客户端上运行,即所谓的无论是连接操作还是称离线模式7。离线模式正更换得越来越重要。HTML5的有特点,特别是客户端持久化存储特性,将会促进离线操作的上扬。支持离线模式之系统通常会在C和A中摘A,那么就不得不在丰富日子处于分区状态后开展回复。

“一致性的用意范围”其实反映了这般同样种植观念,即在早晚之分界外状态是同样的,但不止了分界就无从谈起。比如在一个主分区内得包完备的一致性和可用性,而于分区外服务是免可用的。Paxos算法和原子性多播(atomic
multicast)系统一般可这样的现象8。像Google的一半做法是将主分区归属于才一个多少主导内部,然后交给Paxos算法去化解越区域的问题,一方面保证全局协商一致(global
consensus)如Chubby9,一方面促成大可用之持久性存储如Megastore10

分区期间,独立且会自保证一致性的节点子集合好继续执行操作,只是无法确保全局范围的不变性约束不让损坏。数据分片(sharding)就是这样的例证,设计师先将数据划分到不同的分区节点,分区期间单个数据分片多半可以连续操作。相反,如果让分区的是外于关系密切的状态,或者出几许全局性的不变性约束非保不可,那么最好的状况是只有分区一侧可以开展操作,最可怜情况是操作了无能够拓展。

“三取舍二”的时取CA而舍P是否合理?已经来研究者指出了内部的第一——怎样才终于“舍P”含义并无明明11,12。设计师可以选不要分区为?哪怕原来选择了CA,当分区出现的时光,你为只能回头再于C和A之间又择同蹩脚。我们最好好打概率的角度去解:选择CA意味着我们要,分区出现的可能要比较其它的系统性错误(如自然灾难、并作故障)低多。

这种看法于实质上中充分有意义,因为一些故障组合或造成同时丢掉C和A,所以说CAP三单特性还是一个度的题目。实践着,大部分集团认为(位于单一地点的)数据主导间是绝非分区的,因此于单一数据核心里可以选择CA;CAP理论出现之前,系统还默认这样的规划思路,包括传统数据库在内。然而就是可能性不赛,单一数据主导完全有或出现分区的情事,一旦出现就会动摇以CA为方向的计划基础。最后,考虑到跨区域时起的强延迟,在数码一致性上服来换取更好性能的做法相对比较大。

CAP还有一个者多人数认识不穷,那即便是放弃一致性其实生隐形负担,即用明确询问系统被是的不变性约束。满足一致性的系统来同等种保持其不变性约束之本倾向,即便设计师不清楚网受到负有的不变性约束,相当一些成立的不变性约束会自行地维持下去。相反,当设计师选择可用性的时候,因为需要在分区结束晚复原给坏之不变性约束,显然要以各种不变性约束一一列举出,可想而知这桩工作特别有挑战又杀轻犯错。放弃一致性为什么难以,其主导还是“并作创新问题”,跟多线程编程比顺序编程难的故是同样的。

治本分区

哪些缓和分区对一致性与可用性的震慑是针对设计师的挑战。其重大是因稀显眼、公开的措施去管理分区,不仅需要主动意识分区的起,还得吗分区期间所有可能受重伤的不变性约束预备专门的过来过程以及计划。管理分区有三单步骤:

(点击看大图)

亚洲必赢app在哪下载 1

  • 检测及分区开始
  • 分明进入分区模式,限制某些操作,并且
  • 当通信恢复后开行分区恢复过程

说到底一步的目的是过来一致性,以及补充在系分区期间先后来的错。

希冀1可见分区的嬗变过程。普通的操作都是各个的原子操作,因此分区总是以两笔操作中开始。一旦系统在操作停顿检测到分区发生,检测方一侧就是入分区模式。如果的确发生了分区的景,那么一般分区两侧还见面进去到分区模式,不过另一方面完成分区为是唯恐的。单方面分区要求在对方仍需通信的时节,本方要么会是响应,要么不待通信;总之操作不得毁损一致性。但不管怎么样,由于检测方可能出免雷同的操作,它要上分区模式。采取了quorum决定机制的网便为单分区的例证。其中同样在有“法定通过节点数”,因此得以实施操作,而另一样着无得以尽操作。支持离线操作的网明显地包含“分区模式”的概念,一些支撑原子多播(atomic
multicast)的体系为饱含这定义,如Java平台的JGroups。

当系统进入到分区模式,它发生零星种中的政策。其一是限制部分操作,因此会削弱可用性。其二是额外记录有便宜后面分区恢复的操作信息。系统可由此不断尝试恢复通信来察觉分区何时了。

怎么样操作可以实施?

支配限制哪些操作,主要在于系统要保障哪几宗非变性约束。在叫一定矣未变性约束原则下,设计师需要控制在分区模式下,是否坚持不动某起无变性约束,抑或以从后重操旧业也前提去冒险触犯它。例如,对于“表中键的惟一性”这项不变性约束,设计师一般都选于分区期间放宽要求,容许重复的键。重复的键很容易在恢复等检查下,假如重复键可以合,那么设计师不难恢复这项不变性约束。

对于分区期间总得保障的不变性约束,设计师应禁止或改可能触犯该不变性约束之操作。(一般而言,我们无办法知道操作是否真正会毁不变性约束,因为无法掌握分区另一侧的状态。)信用卡扣费等有着外部化特征的事件不时因为这种方法行事。适合这种情形的策略,是记录下操作意图,然后在分区恢复后再实践操作。这看似工作往往从属于有复甚之工作流,在工作流明确涵盖类似“订单处理中”状态的状况下,将操作推迟到分区结束并随便显著的流弊。设计师为用户是察觉的计牺牲了可用性。用户就懂自己生了命令,系统稍后会实行。

说得又包括一点,分区模式为用户界面提出了同等种植根本性的挑战,即如何传达“任务在拓展无完成”的消息。研究者已经由离线操作的角度对这题材开展了部分深刻的追,离线操作可以作为时间大丰富的同样不行分区。例如Bayou的日历程序用颜色来区别显示可能(暂时)不一样的条规13。工作流应用与带离线模式之出口服务着为广泛类似的唤醒,前者的例子如市被之电子邮件通知,后者的例证如Google
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)”的数学概念来代表数据,并保证相对于“格”来说,分区期间的享有操作都是干瘪递增的。

故而后同样栽艺术统一状态会集中分区两边的极致要命聚合。这种方法是对亚马逊购物车合并算法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不了解),此时同笔存款更将余额成正的。银行可以追溯产生透支费,也得坐消费者都缴纳而忽视该违情况。

总而言之,因为通信延迟的是,银行系统不靠一致性来保管是,而再多地指审计和增补。“空头支票诈骗”也是相近的例子,顾客赶在差不多小支行对账之前分别取出钱来然后逃之夭夭。透支的谬误了后才见面被发觉,对不当的续或者体现吗法律走的款式。

致谢

感谢Mike Dahlin、Hank Korth、Marc Shapiro、Justin Sheehy、Amin
Vahdat、Ben Zhao以及IEEE Computer
Society的志愿者等,感谢他们对本文的便宜反馈。

作者简介

Eric Brewer凡University of California,
Berkeley的电脑对教,在Google担任基础设备方面的VP。他的钻研兴趣包括谈计算、可伸缩的服务器、传感器网络,还有符合发展面临地区采取之技能。他还帮忙建立了美国联邦政府之门户网站USA.gov。Brewer于MIT获得电子工程及电脑是的博士学位。他是National
Academy of Engineering的院士。联系方式:brewer@cs.berkeley.edu

亚洲必赢app在哪下载 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理论十二年回顾:”规则”变了

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2018 亚洲必赢app官方下载 版权所有