`

(转)Swift里的CAP理论和NWR策略应用

 
阅读更多

源地址:http://blog.sina.com.cn/s/blog_57f61b490101a8ca.html

 

最近有人讨论到swift副本数是否能够调整,3副本成本过高,如果改成2副本怎么样?多聊了几句以后发现不少人可能都是望文生义,简单的认为副本数只是多一个少一个Copy的问题,并不了解背后的理论依据。所以想写个简单的介绍,普及分布式系统设计的一些基础知识点。这个是按傻瓜版写的,已经知道的同学请自动无视。

 

  不同于传统的集中式存储,对于分布式存储系统来说,因为自身的复杂性,副本数并非简单拍脑门而来,需要找到理论支撑,它的依据实际上是来自于CAP理论和基于其上的NWR策略。

 

  CAP 理论是由UC Berkerly的Eric Brewer(没错,他也叫Eric,哈哈)在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。

 

  N = 副本数

  W = 一次成功的写操作必须完成的写副本数

  R = 一次成功的读操作需要读的副本数(是的,随便读一个副本是不行的,你必须读到一定数量的副本,再相互比较取最新的数据)

 

策略来说就有具体的公式可供运算,有两个:

 

  W > N/2

  W + R > N 

 

我们结合Swift的设定,N=3,W=2,R=2or 1,来看看这两个公式是什么意义。

 

分布式系统通常用来处理大并发请求的应用,很多请求大家同时来,有一堆在读,也有一堆想写。

假设有一个数据拥有三副本,每个副本已经同步好,原来的值都是A

 

我们看看如果不需要满足公式让W小于3/2,也就是W=1的情况下会出现什么问题,W=1,意味着每个写的请求只要写完一个副本即可成功返回。

 

假设两个进程同时来更新这份数据,进程W1要把值改写成C,进程W2要把值改写成B,那就有可能出现下图的情形,两个进程各拿到一个副本改写,都认为自己的写操作是成功的,结果却留给系统三个不同的副本,这样就出现数据副本不一致的问题。

Swift里的CAP理论和NWR策略应用

  所以公式W> N/2, 实际上变成了一个写的锁,意味着只有写了过半数副本的才算写成功,拿不到的就返回失败,解决了竞争的问题。如下图,W1的会话成功,W2的会话就返回失败。

Swift里的CAP理论和NWR策略应用

  W> N/2,同时意味着不需要把所有的副本都写完,未完成的留给系统自己后台慢慢同步,那这个时候问题就来了,一个新的会话过来读数据的时候,分配到的副本有可能是没来得及更新的。这时候R1读回去的就是过时的数据B,而非最新的数据C

Swift里的CAP理论和NWR策略应用

 2个公式变形下就是R> N-W,R=2就避免正好倒霉读到没更新的那。这样读回去C和B两个数据,再比较后取最新的C。所以W+R> N 能够保证每个读的请求至少读到一份最新的数据,

Swift里的CAP理论和NWR策略应用 


    所以你也许已经琢磨出来,这两个公式更加强调一致性,在可用性上是有所保留的。

 

当然NWR还可能取其他值,不同的取值代表了不同的倾向。如果设定N=3, W=3, R=1,那么强调的是一致性,写数据的时候一定要把所有副本都刷新,杜绝中间状态,这样一致性得到很好保证如果N=3, W=1, R=1,那强调的是可用性,这种情况下一致性是被牺牲掉了,所以上面两个保证一致性的公式在这种情况下就不再适用。之所以可用性提高是因为读和写都放低了要求,只要完成一个副本即可,这样完成时间降低,响应速度是更快的。

 

N=3, W=2, R=2是一种折中的策略。其实Amazon的Dynamo就是采用的这个参数,据说Swift是照搬S3的。 

  所以回到Swift的副本设定来看,swift的NWR值是可调的,有两种配置,一种是标准的N3W2R2,但是实际上你也可以使用N3W2R1,这个更实用点。在这种配置下,虽然一个数据拥有三副本,但是容错上读写是不一样的。网络断线,硬盘故障等意外造成一个副本失效时, 系统仍然可读可写,但两个副本失效时,受影响的这部分数据系统就变成只读,无法再写了。

 

CAP理论和NWR策略在大规模系统下是比较合理的,除了被用来设计分布式存储之外,也用来设计分布式数据库,比如很热的NOSQL。另外,这个理论问世已经不短的时间,也经常看到有人发文要挑战他,也有一些吐槽等等,那个是另外的话题,这里就不再继续了。

 

最近一个朋友在网上购物,遇到一件有意思的事,某电商有个特价抢购,是个手机移动电源,他很happy下了单,结果第2天送来了两瓶酱油。回头看订单详情,明明还是移动电源。再看促销,原来的促销已经变成了酱油。我们可以用前面的理论模拟下问题是如何产生的。朋友在查看商品的时候,他的这个会话,假设读到的库存数据是1,意思就是有货,就放到购物车里了。同时估计也有很多人在查询,读到的数据都是1,大家都认为有货。除了我朋友,至少还有一个人也下了单,下单就需要后台需要将这个库存数据减去1,常见的逻辑应该是改写库存成功才能生成订单。如果设定的W是1,那么两个会话就会有机会都认为自己成功,两个订单同时生成,但货只有一个了,导致问题出现。

至于如何变成酱油的,我不太想猜测,这件事本身实在是太搞笑了,我想起他拆开包裹的样子就想笑哈哈哈。

分享到:
评论

相关推荐

    swift介绍.pptx

    这种冗余机制遵循 NWR(Number of Writes and Reads)策略,即写操作和读操作所需的副本数,确保数据的一致性和安全性。通过这种方式,即使某个节点发生故障,Swift 也能确保数据的持久性和可用性。 综上所述,...

    云计算第三版精品课程配套PPT课件含习题(28页)第8章 OpenStack 开源虚拟化平台(四).pptx

    这种服务特别适合云环境,其中用户和应用程序需要快速、便捷地访问和管理大量的数据。 Swift的核心组件包括存储节点、代理服务器、帐户容器和对象服务器。每个组件都有其特定的功能,共同协作以实现高效的数据存储...

    分布式数据库和中间件架构设计.pptx

    理解ACID、CAP理论以及如何在实际应用中平衡这些原则,是成功设计和实施分布式解决方案的基础。同时,合理利用数据冗余、备份恢复策略和监控机制,可以有效保障系统的稳定性和业务连续性。在选择和设计分布式系统...

    S参数反演法.rar_NWR_S参数反演法_s参数_s参数反演_电 反演

    这个文档对于理解和应用S参数反演法至关重要,它会详细介绍如何设置参数、解读结果以及解决可能出现的问题。 而"freespace1.m"可能是一个附加的MATLAB脚本,用于模拟自由空间的传播条件。在S参数反演中,理解自由...

    山东大学非关系型数据库2017试题押题

    CAP理论指出,在分布式计算中,一致性(Consistency)、可用性(Availability)和分区容忍性(Partition tolerance)三个特性无法同时满足,最多只能同时实现其中的两个。 - **一致性**:所有节点在同一时刻看到...

    关于分布式系统的思考

    谈及一些分布式系统的理论和思想,包括CAP、BASE、NWR等。并简单分析一些主流数据库分布式方案的利弊,以便我们在开发时更深入全面地进行思考、选择和设计。在讨论常见架构前,先简单了解下CAP理论:CAP是...

    云存储技术应用 第六章:分布式云存储.pdf

    分片策略有随机分片、哈希分片等,可以根据数据的特性和应用场景选择合适的策略。 2. **节点选择与数据放置**:根据负载均衡和地理位置等因素,将数据块分配到不同节点上。常见的策略有一致性哈希、最接近的多副本...

    分布式协议与算法1

    10. **NWR算法**:NWR(Node,Write,Read)是关于Quorum选择的一种策略,用于平衡系统的可用性和一致性。 在分布式系统中,通常需要在CAP(Consistency、Availability、Partition Tolerance)三者之间做出权衡。...

    山东大学软件学院2017-2018年非关系型数据库题目(回忆版).docx

    本题目的核心是理解和应用NoSQL数据库的相关概念和技术。 1. 弱一致性:弱一致性是一种分布式系统中数据复制的策略,它不要求所有的副本立即达到一致的状态。在某些情况下,读操作可能返回旧的值,而不是最新的写入...

    山东大学nosql期末笔记.pdf

    本文总结了 NoSQL 数据库的核心思想、数据一致性、CAP 定理、BASE 理论、eBay 模式、NWR、两阶段提交协议、时间戳、向量时钟、Paxos 协议、HBase 等相关概念和技术。 数据一致性是分布式系统中的一致性问题的解决...

    mongodb一些笔记

    MongoDB是一种流行的开源文档数据库系统,属于NoSQL数据库的一种,以其灵活性、高性能和易扩展性在现代Web开发中被广泛应用。以下是对MongoDB的一些关键知识点的详细解释: 1. 数据模型: MongoDB采用的是键值对...

    分布式键值系统1

    Dynamo采用了**复制协议**来保证数据的冗余和容错性,即NWR策略。N表示数据的复制份数,R是读操作所需的最小活动副本数,W是写操作必须成功的最小副本数。只要满足W+R>N,就能确保在单点故障时仍能读取有效数据。...

    ili9320 应用手册

    《ILI9320 应用手册》详细解读 ili9320 是一款广泛应用在彩色液晶显示屏(LCD)上的...理解和掌握其工作原理和操作时序对于开发基于ili9320的LCD应用至关重要,能帮助开发者更好地优化显示性能,实现丰富的显示效果。

    amazon-dynamo-sosp2007.pdf

    它通过广泛采用对象版本控制和应用程序辅助的冲突解决机制,向开发者提供了一个新颖的接口。 文档中提到的关键技术包括NWR策略、Merkle树、一致性哈希分布、数据迁移、版本合并和版本冲突处理机制。NWR是一种在...

    DAC0832的简单程序

    在探讨“DAC0832的简单程序”这一主题时,我们主要关注的是如何通过单片机控制DAC0832这款数模转换器进行基本操作。...希望本文的解析能帮助读者更好地理解和应用DAC0832,为后续的电子项目开发打下坚实的基础。

    2018数据管理音频整理1

    大数据领域中,"2018数据管理音频整理1"涵盖了多个关键知识点,包括大数据的四个V(Volume、Variety、Velocity、Value),Memcached的内存替换策略,DynamoDB的高可用性和一致性模型,以及NWR理论和Vector Clock更新...

    AT91SAM9261中文_21.pdf

    - **字节写访问**:对于16位设备,SMC分别提供NWR0和NWR1信号,分别用于控制低位字节和高位字节的写操作;对于32位设备,则分别提供NWR0、NWR1、NWR2和NWR3信号,用于控制四个字节的写操作。 - **字节选择访问**:在...

    MF RC500-高集成 ISO14443A 读卡芯片 说明书

    MF RC500支持ISO14443A协议的所有层面,包括物理层、数据链接层和应用层。芯片内部集成了调制和解调电路,可以支持所有ISO14443A标准的被动非接触式通信方式,提供最高至100mm的操作距离。该芯片内置了对MIFARE产品...

Global site tag (gtag.js) - Google Analytics