2013年08月07日

Cap理论和nwr策略


这些内容都是从网上摘抄过来,之前一直存在自己的word文档中,最近又看到这方面的内容就温习一遍,也整理一下把他贴出来,其中的NWR策略部分是当时在阅读程辉大牛介绍swift时摘抄过来的。大牛们的分享很是受用!在UnitedStack上,贴出了一篇关于网络分区的文章,大家可以看看。

CAP理论

CAP理论参考链接

CAP理论是由UC Berkerly的Eric Brewer在2000年提出的,当时是一个猜想,2年后被MIT的两个家伙证明为理论,很快被互联网大企业们(Ebay,Twitter,Amazon等)接受和拥护,到如今已经13年,成为了分布式系统设计的经典理论之一。

CAP的主要思想是“C,A, P三者不可得兼,舍一而取二者也”。这就像找对象,如果你想找到一个真实存在的女朋友,你必须先明白没有人是完美的,分布式系统也这样。

C = 一致性 (Consistency) :保证得到的都是完成状态的数据,否则直接失败。

原文是A service that is consistent operates fully or not at all,要么完整得到一个原子性操作,要么闹太套(哈哈,开个玩笑)。这个要求像个专一的妹纸,一次只和一个人谈,没什么牵扯不清的中间状态。意味着系统给出去的数据必须保证是原子操作的合格品,否则直接不给,坚决不能给半成品。你不会拿到一张被另外一个请求画了一半的图,或者是更新了上半段的说明书。

A = 可用性 (Availability) :在容忍的响应时间内,每个操作总是能够返回,不会出现所谓in_flight IO,总是能及时响应。

这意味着一个好脾气的妹纸,永远一分钟内反应。就是不想理你,她也会马上回答“我不想理你”而不是玩冷战,问她在吗?半天没声音。系统总能在指定时间段(例如15秒)内给你反馈,要么给你数据,要么告诉你失败鸟,不会告诉你正在处理中,然后把你撂一边自己下班了。

P = 分区容忍性 (Partition Tolerance) :能够保证系统是分区的。

原文是这样No set of failures less than total network failure is allowed to cause the system to respond incorrectly,比较难理解,简单的解释一下这是个反证,除非整个分布式系统所在的网络都挂掉,只要还有分区就能给出正确响应。这意味着一个会到处出没的妹纸,她可能在家,可能在office,可能在外面happy,但只要任何一个地方能上网,她就能给你反馈。(有人说那多个地方同时出现算什么,那只能说明你很花心,同时和好几个妹纸交往,她们互相之间还不反感,能够配合互为备份)这第三种特质比较罕见也比较难搞,这大概也就是跨分区(设备)的系统吸引人的地方吧。

CAP理论告诉我们,同时具有这三种特质的分布式系统是不存在的,必须在其中取舍。Amazon写了篇论文,描述了一下取舍的具体策略,就是下文的NWR了。

NWR策略

Swift中引入了Replica的概念,其默认值为3,理论依据主要来源于NWR策略(也叫Quorum协议)。 NWR是一种在分布式存储系统中用于控制一致性级别的策略。在Amazon的Dynamo云存储系统中,使用了NWR来控制一致性。其中,N代表同一份数据的Replica的份数,W是更新一个数据对象时需要确保成功更新的份数;R代表读取一个数据需要读取的Replica的份数。 公式W+R>N,保证某个数据不被两个不同的事务同时读和写;公式W>N/2保证两个事务不能并发写某一个数据。 在分布式系统中,数据的单点是不允许存在的。即线上正常存在的Replica数量为1的情况是非常危险的,因为一旦这个Replica再次出错,就可能发生数据的永久性错误。假如我们把N设置成为2,那么只要有一个存储节点发生损坏,就会有单点的存在,所以N必须大于2。N越高,系统的维护成本和整体成本就越高。工业界通常把N设置为3。例如,对于MySQL主从结构,其NWR数值分别是N= 2, W = 1, R = 1,没有满足NWR策略。而Swift的N=3, W=2, R=2,完全符合NWR策略,因此Swift系统是可靠的,没有单点故障。对于这几个公式的理解可以参考上面贴出的链接。 NWR策略是在平衡读、写、备份的效率中使用到的一个非常经典的策略,在Amazon Dynamo和Swift等分布式存储系统中都应用的很关键。

N代表N个备份

W代表要写入至少W份才认为成功

R表示至少读取R个备份(比较版本,取最新的值)

公式W+R>N,保证某个数据不被两个不同的事务同时读和写

公式W>N/2 保证两个事务不能并发写某一个数据

配置的时候要求W+R>N。 因为W+R>N,所以R>N-W,这个是什么意思呢?就是读取的份数一定要比总备份数减去确保写成功的份数的差值要大。也就是说,每次读取,都至少读取到一个最新的版本,从而不会读到一份旧数据。比如N=5,W=3,N-W=2,即保证5个备份中有3个是正确的,另外2个可能没有写成功。如果只读取2份,那么这两份有可能都不是写成功的。

当我们需要高可写的环境的时候(论文中举例,amazon的购物车的添加请求应该是永远不被拒绝的)我们可以配置W=1,如果N=3,那么R = 3。这个时候只要写任何节点成功就认为成功,但是读的时候必须从所有的节点都读出数据。如果我们要求读的高效率,我们可以配置 W=N,R=1。这个时候任何一个节点读成功就认为成功,但是写的时候必须写所有三个节点成功才认为成功。大家注意,一个操作的耗时是几个并行操作中最慢一个的耗时。比如R=3的时候,实际上是向三个节点同时发了读请求,要三个节点都返回结果才能认为成功。假设某个节点的响应很慢,它就会严重拖累一个读操作的响应速度。

不同的NWR取值代表了不同的倾向,如果设定N=3,W=3,R=1,那么强调的是强一致性,写数据的时候一定要把所有的副本刷新,杜绝中间状态。如果N=3,R=1,W=1,则代表的是可用性,这种情况下一致性就被牺牲掉了。

总结

网上有很多的关于CAP的讨论,例如这篇文章,CAP理论十二年回顾:规则变了。对于这个理论的理解,还需要更加深刻的思考与实践。

前一篇: Openstack开发者入门(二) 后一篇: 查找差值最大的两个数