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, 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还有一个地方许多人口认不到底,那便是舍弃一致性其实有藏身负担,即需要明白了解系统面临留存的不变性约束。满足一致性的网出平等栽保持其莫变性约束的当然倾向,即便设计师不知情网受装有的不变性约束,相当一部分客观之不变性约束会自动地维持下去。相反,当设计师选择可用性的下,因为急需以分割区结束后恢复吃摔的不变性约束,显然要用各种非变性约束一一列举出,可想而知这宗工作好有挑战又异常爱犯错。放弃一致性为什么难以,其中心要“并作创新问题”,跟多线程编程比顺序编程难之原委是一律的。

管住分区

如何缓和分区对一致性与可用性的影响是针对设计师的挑战。其利害攸关是坐大醒目、公开的方式去管理分区,不仅需要主动意识分区的起,还索要为分区期间有所可能让重伤的不变性约束预备专门的过来过程与计划。管理分区有三独步骤:

(点击看大图)

必发bifa88手机客服端 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

必发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理论十二年回顾:”规则”变了

相关文章