2007太阳成集团游戏中心

 收藏私塾在线
 

欢迎您来到私塾在线网!   

请登录! 

免费注册 

交流首页 » 数据库 »NoSQL-1 NoSQL的三大基石(CAP、BASE和最终一致性)  XML
发表人 内容
java学者
[头像]

交流经验:
总积分:205
级别:普通会员
注册时间: 2011-10-27
文章: 21
离线

CAP,BASE和最终一致性是NoSQL数据库存在的三大基石。而五分钟法则是内存数据存储了理论依据。这个是一切的源头。

CAP

 


 

  • C: Consistency 一致性
  • A: Availability 可用性(指的是快速获取数据)
  • P: Tolerance of network Partition 分区容忍性(分布式)

 

10年前,Eric Brewer教授指出了著名的CAP理论,后来Seth Gilbert 和 Nancy lynch两人证明了CAP理论的正确性。CAP理论告诉我们,一个分布式系统不可能满足一致性,可用性和分区容错性这三个需求,最多只能同时满足两个。
熊掌与鱼不可兼得也。关注的是一致性,那么您就需要处理因为系统不可用而导致的写操作失败的情况,而如果您关注的是可用性,那么您应该知道系统的read操作可能不能精确的读取到write操作写入的最新值。因此系统的关注点不同,相应的采用的策略也是不一样的,只有真正的理解了系统的需求,才有可能利用好CAP理论。

作为架构师,一般有两个方向来利用CAP理论
  1. key-value存储,如Amaze Dynamo等,可根据CAP三原则灵活选择不同倾向的数据库产品。
  2. 领域模型 + 分布式缓存 + 存储 (Qi4j和NoSql运动),可根据CAP三原则结合自己项目定制灵活的分布式方案,难度高。
我准备提供第三种方案:实现可以配置CAP的数据库,动态调配CAP。

  • CA:传统关系数据库
  • AP:key-value数据库
而对大型网站,可用性与分区容忍性优先级要高于数据一致性,一般会尽量朝着 A、P 的方向设计,然后通过其它手段保证对于一致性的商务需求。架构设计师不要精力浪费在如何设计能满足三者的完美分布式系统,而是应该进行取舍。
不同数据对于一致性的要求是不同的。举例来讲,用户评论对不一致是不敏感的,可以容忍相对较长时间的不一致,这种不一致并不会影响交易和用户体验。而产品价格数据则是非常敏感的,通常不能容忍超过10秒的价格不一致。

CAP理论的证明: Brewer's CAP Theorem

最终一致性

一言以蔽之:过程松,结果紧,最终结果必须保持一致性

 

为了更好的描述客户端一致性,我们通过以下的场景来进行,这个场景中包括三个组成部分:
  • 存储系统
存储系统可以理解为一个黑盒子,它为我们提供了可用性和持久性的保证。
  • Process A
ProcessA主要实现从存储系统write和read操作
  • Process B 和ProcessC 
ProcessB和C是独立于A,并且B和C也相互独立的,它们同时也实现对存储系统的write和read操作。


下面以上面的场景来描述下不同程度的一致性:

  • 强一致性
强一致性(即时一致性) 假如A先写入了一个值到存储系统,存储系统保证后续A,B,C的读取操作都将返回最新值
  • 弱一致性
假如A先写入了一个值到存储系统,存储系统不能保证后续A,B,C的读取操作能读取到最新值。此种情况下有一个“不一致性窗口”的概念,它特指从A写入值,到后续操作A,B,C读取到最新值这一段时间。
  • 最终一致性
最终一致性是弱一致性的一种特例。假如A首先write了一个值到存储系统,存储系统保证如果在A,B,C后续读取之前没有其它写操作更新同样的值的话,最终所有的读取操作都会读取到最A写入的最新值。此种情况下,如果没有失败发生的话,“不一致性窗口”的大小依赖于以下的几个因素:交互延迟,系统的负载,以及复制技术中replica的个数(这个可以理解为master/salve模式中,salve的个数),最终一致性方面最出名的系统可以说是DNS系统,当更新一个域名的IP以后,根据配置策略以及缓存控制策略的不同,最终所有的客户都会看到最新的值。

变体

  • Causal consistency(因果一致性)
如果Process A通知Process B它已经更新了数据,那么Process B的后续读取操作则读取A写入的最新值,而与A没有因果关系的C则可以最终一致性。
  • Read-your-writes consistency
如果Process A写入了最新的值,那么Process A的后续操作都会读取到最新值。但是其它用户可能要过一会才可以看到。
  • Session consistency
此种一致性要求客户端和存储系统交互的整个会话阶段保证Read-your-writes consistency.Hibernate的session提供的一致性保证就属于此种一致性。
  • Monotonic read consistency
此种一致性要求如果Process A已经读取了对象的某个值,那么后续操作将不会读取到更早的值。
  • Monotonic write consistency
此种一致性保证系统会序列化执行一个Process中的所有写操作。

BASE

说起来很有趣,BASE的英文意义是碱,而ACID是酸。真的是水火不容啊。

  • Basically Availble --基本可用
  • Soft-state --软状态/柔性 事务
"Soft state" 可以理解为"无连接"的, 而 "Hard state" 是"面向连接"的
  • Eventual Consistency --最终一致性
最终一致性, 也是是 ACID 的最终目的。

BASE模型反ACID模型,完全不同ACID模型,牺牲高一致性,获得可用性或可靠性: Basically Available基本可用。支持分区失败(e.g. sharding碎片划分数据库) Soft state软状态 状态可以有一段时间不同步,异步。 Eventually consistent最终一致,最终数据是一致的就可以了,而不是时时一致。

BASE思想的主要实现有
1.按功能划分数据库
2.sharding碎片 

BASE思想主要强调基本的可用性,如果你需要高可用性,也就是纯粹的高性能,那么就要以一致性或容错性为牺牲,BASE思想的方案在性能上还是有潜力可挖的。

其他


I/O的五分钟法则

在 1987 年, Jim Gray 与 Gianfranco Putzolu 发表了这个"五分钟法则"的观点,简而言之,如果一条记录频繁被访问,就应该放到内存里,否则的话就应该待在硬盘上按需要再访问。这个临界点就是五分钟。 看上去像一条经验性的法则,实际上五分钟的评估标准是根据投入成本判断的,根据当时的硬件发展水准,在内存中保持 1KB 的数据成本相当于硬盘中存据 400 秒的开销(接近五分钟)。这个法则在 1997 年左右的时候进行过一次回顾,证实了五分钟法则依然有效(硬盘、内存实际上没有质的飞跃),而这次的回顾则是针对 SSD 这个"新的旧硬件"可能带来的影响。







不要删除数据


Oren Eini(又名Ayende Rahien)建议开发者尽量避免数据库的软删除操作,读者可能因此认为硬删除是合理的选择。作为对Ayende文章的回应,Udi Dahan强烈建议完全避免数据删除。

所谓软删除主张在表中增加一个IsDeleted列以保持数据完整。如果某一行设置了IsDeleted标志列,那么这一行就被认为是已删除的。Ayende觉得这种方法“简单、容易理解、容易实现、容易沟通”,但“往往是错的”。问题在于:

删除一行或一个实体几乎总不是简单的事件。它不仅影响模型中的数据,还会影响模型的外观。所以我们才要有外键去确保不会出现“订单行”没有对应的父“订单”的情况。而这个例子只能算是最简单的情况。……

当采用软删除的时候,不管我们是否情愿,都很容易出现数据受损,比如谁都不在意的一个小调整,就可能使“客户”的“最新订单”指向一条已经软删除的订单。

如果开发者接到的要求就是从数据库中删除数据,要是不建议用软删除,那就只能硬删除了。为了保证数据一致性,开发者除了删除直接有关的数据行,还应该级联地删除相关数据。可Udi Dahan提醒读者注意,真实的世界并不是级联的:

假设市场部决定从商品目录中删除一样商品,那是不是说所有包含了该商品的旧订单都要一并消失?再级联下去,这些订单对应的所有发票是不是也该删除?这么一步步删下去,我们公司的损益报表是不是应该重做了?

没天理了。

问题似乎出在对“删除”这词的解读上。Dahan给出了这样的例子:

我说的“删除”其实是指这产品“停售”了。我们以后不再卖这种产品,清掉库存以后不再进货。以后顾客搜索商品或者翻阅目录的时候不会再看见这种商品,但管仓库的人暂时还得继续管理它们。“删除”是个贪方便的说法。

他接着举了一些站在用户角度的正确解读:


订单不是被删除的,是被“取消”的。订单取消得太晚,还会产生花费。

员工不是被删除的,是被“解雇”的(也可能是退休了)。还有相应的补偿金要处理。

职位不是被删除的,是被“填补”的(或者招聘申请被撤回)。

在上面这些例子中,我们的着眼点应该放在用户希望完成的任务上,而非发生在某个
实体身上的技术动作。几乎在所有的情况下,需要考虑的实体总不止一个。

为了代替IsDeleted标志,Dahan建议用一个代表相关数据状态的字段:有效、停用、取消、弃置等等。用户可以借助这样一个状态字段回顾过去的数据,作为决策的依据。

删除数据除了破坏数据一致性,还有其它负面的后果。Dahan建议把所有数据都留在数据库里:“别删除。就是别
删除。”

RAM是硬盘,硬盘是磁带


Jim Gray在过去40年中对技术发展有过巨大的贡献,“内存是新的硬盘,硬盘是新的磁带”是他的名言。“实时”Web应用不断涌现,达到海量规模的系统越来越多,这种后浪推前浪的发展模式对软硬件又有何影响?

Tim Bray早在网格计算成为热门话题之前,就 讨论过以RAM和网络为中心的硬件结构的优势,可以用这种硬件建立比磁盘集群速度更快的RAM集群。
对于数据的随机访问,内存的速度比硬盘高几个数量级(即使是最高端的磁盘存储系统也只是勉强达到1,000次寻道/秒)。其次, 随着数据中心的网络速度提高,访问内存的成本更进一步降低。通过网络访问另一台机器的内存比访问磁盘成本更低。就在我写下这段话的时候,Sun的 Infiniband产品线中有一款具备9个全互联非阻塞端口 交换机,每个端口的速度可以达到30Gbit/sec!Voltaire产品的端口甚至更多;简直不敢想象。(如果你想了解这类超高性能网络的最新进展,请关注Andreas Bechtolsheim在Standford开设的课程。)
各种操作的时间,以2001年夏季,典型配置的 1GHz 个人计算机为标准:
执行单一指令 1 纳秒 从L1 高速缓存取一个字 2 纳秒 从内存取一个字 10 纳秒 从磁盘取连续存放的一个字 200 纳秒 磁盘寻址并取字 8 毫秒 以太网 2GB/s



Tim还指出Jim Gray的
名言中后半句所阐述的真理:“对于随机访问,硬盘慢得不可忍受;但如果你把硬盘当成磁带来用,它吞吐连续数据的速率令人震惊;它天生适合用来给以RAM为主的应用做日志(logging and journaling)。” 

时间闪到几年之后的今天,我们发现硬件的发展趋势在RAM和网络领域势头不减,而在硬盘领域则止步不前。Bill McColl提到用于并行计算的 海量内存系统已经出现
内存是新的硬盘!硬盘速度提高缓慢,内存芯片容量指数上升,in-memory软件架构有望给各类数据密集的应用带来数量级的性能提升。小型机架服务器(1U、2U)很快就会具备T字节、甚至更大量的内存,这将会改变服务器架构中内存和硬盘之间的平衡。硬盘将成为新的磁带,像磁带一样作为顺序存储介质使用(硬盘的顺序访问相当快速),而不再是随机存储介质(非常慢)。这里面有着大量的机会,新产品的性能有望提高10倍、100倍。
Dare Obsanjo指出 如果不把这句真言当回事,会带来什么样的恶劣后果—— 也就是Twitter正面临的麻烦。论及Twitter的内容管理,Obsanjo说,“如果一个设计只是简单地反映了问题描述,你去实现它就会落入磁盘 I/O的地狱。不管你用Ruby on Rails、Cobol on Cogs、C++还是手写汇编都一样,读写负载照样会害死你。”换言之,应该把随机操作推给RAM,只给硬盘留下顺序操作。 

Tom WhiteHadoop Core项目的提交者,也是Hadoop项目管理委员会的成员。他对Gray的真言中“硬盘是新的磁带”部分作了更深入地探讨。White在讨论MapReduce编程模型的时候指出,为何对于Hadloop这类工具来说, 硬盘仍然是可行的应用程序数据存储介质:
本质上,在MapReduce的工作方式中,数据流式地读出和写入硬盘,MapReduce是以硬盘的传输速率不断地对这些数据进行排序和合并。 与之相比,访问关系数据库中的数据,其速率则是硬盘的寻道速率(寻道指移动磁头到盘面上的指定位置读取或写入数据的过程)。为什么要强调这一点?请看看寻道时间和磁盘传输率的发展曲线。寻道时间每年大约提高5%,而数据传输率每年大约提高20%。寻道时间的进步比数据传输率慢——因此采用由数据传输率决定性能的模型是有利的。MapReduce正是如此。
虽然固态硬盘(SSD)能否改变寻道时间/传输率的对比还有待观察, White文章的跟贴中,很多人都认为 SSD会成为RAM/硬盘之争中的平衡因素。 

Nati Shalom对 内存和硬盘在数据库部署和使用中的角色作了一番有理有据的评述。 Shalom着重指出用数据库集群和分区来解决性能和可伸缩性的局限。他说,“数据库复制和数据库分区都存在相同的基本问题,它们都依赖于文件系统/硬盘 的性能,建立数据库集群也非常复杂”。他提议的方案是转向In-Memory Data Grid(IMDG),用Hibernate二级缓存或者GigaSpaces Spring DAO之类的技术作支撑,将持久化作为服务(Persistence as a Service)提供给应用程序。Shalom解释说,IMDG
提供在内存中的基于对象的数据库能力,支持核心的数据库功能,诸如高级索引和查询、事务语义和锁。IMDG还从应用程序的代码中抽象出了数据的拓扑。通过这样的方式,数据库不会完全消失,只是挪到了“正确的”位置。
IMDG相比直接RDBMS访问的优势列举如下:
  • 位于内存中,速度和并发能力都比文件系统优越得多
  • 数据可通过引用访问
  • 直接对内存中的对象执行数据操作
  • 减少数据的争用
  • 并行的聚合查询
  • 进程内(In-process)的局部缓存
  • 免除了对象-关系映射(ORM)
你是否需要改变对应用和硬件的思维方式,最终取决于你要用它们完成的工作。但似乎公论认为,开发者解决性能和可伸缩性的思路已经到了该变一变的时候。

Amdahl定律和Gustafson定律

这里,我们都以S(n)表示n核系统对具体程序的加速比,K表示串行部分计算时间比例。

Amdahl 定律的加速比:S(n) = 使用1个处理器的串行计算时间 / 使用n个处理器的并行计算时间S(n) = 1/(K+(1-K)/n) = n/(1+(n-1)K)Gustafson定律的加速比:S(n) = 使用n个处理器的并行计算量 / 使用1个处理器的串行计算量S(n) = K+(1-K)n
有点冷是不是?

通俗的讲,Amdahl 定律将工作量看作1,有n核也只能分担1-K的工作量;而Gustafson定律则将单核工作量看作1,有n核,就可以增加n(1-K)的工作量。

这里没有考虑引进分布式带来的开销,比如网络和加锁。成本还是要仔细核算的,不是越分布越好。

控制算法的复杂性在常数范围之内。

 转载自【NoSQL数据库笔谈

这篇文章被编辑了 4 次. 最近一次更新是在 2011-10-27 14:37:28


推广链接
精品视频课程推荐

深入浅出学Zookeeper
内容概述:本课程深入浅出的讲解Hadoop 体系下的分布式协调组件-Zookeeper,向大家介绍了Zookeeper的原理与使用,深入浅出,结合生动实例,具有很高的实战意味 技术要点:Zookeepr 原理,Zookeeper 架构,Zookeeper 简单使用,Zookeeper Watch等

Hadoop实战-中高级部分视频教程
Hadoop中高级精品课程,帮助学员快速掌握Hadoop HDFS的原理;MapReduce的原理;MapReduce高级编程;Hadoop的IO机制,如序列化、压缩;Hadoop的RPC,RESTFul API等高级特性;彻底理解Hadoop,成为一名合格的云计算开发者。并掌握一些云端基本的运维知识,从而实现开发和运维兼修的高级人才。

高级软件架构师实战培训阶段一
内容概述:本课程专注于构建:高可扩展性、高性能、大数据量、高并发、分布式的系统架构。 从零开始、全面系统、成体系的软件架构课程,循序渐进的讲述构建上述系统架构所需要的各种技术知识和技能。
技术要点: 1:构建基本的业务功能块,基于Maven+Git+Spring mvc+spring+mybatis+ehcache+mysql+X-gen代码生成
 2:高扩展性的分布式体系架构(基于Nginx+Varnish+Memcache+ActiveMQ)
 3:NoSQL的合理使用和架构优化(基于MongoDB)
 4:分布式文件存储和架构优化(基于MogileFS)

Weblogic实战视频教程
WebLogic基础知识:WebLogic基本概念、正确安装WebLogic、建域、应用部署于JDBC选择、对WebLogic的监控和日志查看、集群的高可用性;课程目标:彻底掌握WebLogic的基本概念,在理解基本概念的基础上做到正确的安装WebLogic,根据不同的需求创建域,合理选择应用部署和JDBC配置。熟练掌握WebLogic的console监控,了解各种性能和运行指标,以及对监控结果的分析,运用集群的高可用性,对集群架设。

深入浅出学Spring Data JPA视频教程
系统、完整的学习Spring Data JPA开发的知识。包括:Spring Data JPA入门;JpaRepository基本功能 ;JpaRepository的查询;客户化扩展JpaRepository;Specifications查询。

zhouygjp
[头像]

交流经验:
总积分:3
级别:普通会员
注册时间: 2012-03-10
文章: 1
离线

I/O的五分钟法则
非常有道理


个性签名:hi
 
交流首页 » 数据库
前往:   

关于我们 | 联系我们 | 用户协议 | 私塾在线服务协议 | 版权声明 | 隐私保护

版权所有 Copyright(C)2009-2012 私塾在线学习网