技术分享——NOSQL思想篇

公司大牛写的系列关于nosql的帖子，包括：NOSQL思想篇、NOSQL手段篇、NOSQL综合篇、NOSQL软件篇。
感觉非常详细，记录在此，深刻学习:

 

一. 思想篇

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

1.CAP

(1). 概念

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

 

 

C: Consistency( 一致性)

·      任何一个读操作总是能读取到之前完成的写操作结果。

·      对于分布式的存储系统，一个数据往往会存在多份。简单的说，一致性会让客户对数据的修改操作( 增/ 删/ 改) 要么在所有的数据副本全部成功，要么全部失败。即，修改操作对于一份数据的所有副本而言，是原子的操作。如果一个存储系统可以保证一致性，那么则客户读写的数据完全可以保证是最新的。不会发生两个不同的客户端在不同的存储节点中读取到不同副本的情况。

A: Availability( 可用性)

·      每一个操作总是能够在确定的时间内返回。

·      可用性很简单，顾名思义，就是指在客户端想要访问数据的时候，可以得到响应。但是注意，系统可用(Available) 并不代表存储系统所有节点提供的数据是一致的。比如客户端想要读取文章评论，存储系统可以返回客户端数据，但是评论缺少最新的一条。这种情况，我们仍然说系统是可用的。往往我们会对不同的应用设定一个最长响应时间，超过这个响应时间的服务我们仍然称之为不可用的。

P: Tolerance of network Partition( 分区容忍性)

·      在出现网络分区的情况下，仍然能够满足一致性和可用性。

·      如果你的存储系统只运行在一个节点上，要么系统整个崩溃，要么全部运行良好。一旦针对同一服务的存储系统分布到了多个节点后，整个存储系统就存在分区的可能性。比如，两个存储节点之间联通的网络断开( 无论长时间或者短暂的) ，就形成了分区。对当前的互联网公司来说，为了提高服务质量，同一份数据放置在不同城市乃至不同国家是非常正常的。因此节点之间形成分区也很正常。除全部网络节点全部故障以外，所有子节点集合的故障都不允许导致整个系统不正确响应。

(2).C 、A 、P 组合情况

C + P

    如果选择Partition Tolerance 和Consistency ，那么即使坏了节点，操作必须又一致，又能顺利完成。所以就必须100% 保证所有节点之间有很好的连通性。这是很难做到的。最好的办法就是将所有数据放到同一个节点中。但是显然这种设计是不满足Availability 的。

C + A

    如果要满足Availability 和Consistency ，那么为了保证可用，数据必须要有Replica 。这样，系统显然无法容忍Partition 。当同一数据的两个副本(Replica) 分配到了两个无法通信的Partition 上时，显然会返回错误的数据。

A + P

    满足Availability 和Partition Tolerance 的情况。满足可用，就说明数据必须要在不同节点中有replica 。然而还必须保证在产生Partition 的时候仍然操作可以完成。那么，必然操作无法保证一致性。

案例 - 关系型数据库(CP)

    基于ACID 的关系型数据库选择的是C 和P 。因此能够提供很高的一致性，但是却在系统繁忙的时候不可用(Service Unavailable) 。但是对于大多数互联网应用来讲，强一致性对他们来说并不一定非要满足，可用性往往是更加重要的。比如，某博客网站在北京和上海的存储服务器突然不联通，北京用户和上海用户无法看到对方的评论显然要比北京用户和上海用户访问网站都返回HTTP 500 错误要好的多。

(3). 设计实践

    作为架构师，一般有两个方向来利用CAP 理论:

·      key-value 存储，如Amaze Dynamo 等，可根据CAP 三原则灵活选择不同倾向的数据库产品。

·      领域模型 + 分布式缓存 + 存储(Qi4j 和NoSql 运动) ，可根据CAP 三原则结合自己项目定制灵活的分布式方案，难度高。

    而对大型网站，可用性与分区容忍性优先级要高于数据一致性，一般会尽量朝着A 、P 的方向设计，然后通过其它手段保证对于一致性的商务需求。架构设计师不要精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍。

不同数据对于一致性的要求是不同的。举例来讲，用户评论对不一致是不敏感的，可以容忍相对较长时间的不一致，这种不一致并不会影响交易和用户体验。而产品价格数据则是非常敏感的，通常不能容忍超过10 秒的价格不一致。

(4).CAP 理论的证明

原文: www.julianbrowne.com/article/viewer/brewers-cap-theorem

译文: http://code.alibabatech.com/blog/dev_related_728/brewers-cap-theorem.html

(5). 网帖

http://rdc.taobao.com/blog/cs/?p=631

http://ultimatearchitecture.net/index.php/2010/06/22/cap_theory/

http://blog.csdn.net/winniepu/article/details/5485899

http://www.sigma.me/2011/06/13/nosql-cap-theorem.html

http://www.spnguru.com/2010/07/cap%E7%90%86%E8%AE%BA%E5%92%8C%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F%E8%AE%BE%E8%AE%A1/

http://vvggsky.iteye.com/blog/574443

http://www.cnblogs.com/mmjx/archive/2011/12/19/2290540.html

http://www.hellodb.net/2010/05/voltdb_mysql_cluster.html

http://hi.baidu.com/pkugsis/blog/item/fdc5ca5cf3abe759faf2c0fa.html

http://leoncom.org/?p=650333

http://www.click2earth.com/post/119.html

http://blog.csdn.net/godfrey90/article/details/6754884

http://www.uml.org.cn/sjjm/201009152.asp

http://blog.sina.com.cn/s/blog_3e48b19f0100zk5z.html

http://www.cnblogs.com/highriver/archive/2011/09/15/2176833.html

http://www.52analysis.com/index.php?mod=group_thread&code=view&id=15194

http://space.itpub.net/58054/viewspace-660826

http://m.udpwork.com/item/1677.html

http://www.orczhou.com/index.php/2010/05/all-about-cap-i-learn/

 

 

2. 最终一致性

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

(1). 客户端一致性

    为了更好的描述客户端一致性，我们通过以下的场景来进行。

A. 场景中三个组成部分

·      存储系统

    存储系统可以理解为一个黑盒子，它为我们提供了可用性和持久性的保证。

·      Process A

    ProcessA 主要实现从存储系统write 和read 操作。

·      Process B 和ProcessC

    ProcessB 和C 是独立于A ，并且B 和C 也相互独立的，它们同时也实现对存储系统的write 和read 操作。

B. 描述不同程度的一致性

·      强一致性

    强一致性( 即时一致性) 。假如A 先写入了一个值到存储系统，存储系统保证后续A 、B 、C 的读取操作都将返回最新值。

·      弱一致性

    假如A 先写入了一个值到存储系统，存储系统不能保证后续A 、B 、C 的读取操作能读取到最新值。此种情况下有一个" 不一致性窗口" 的概念，它特指从A 写入值，到后续操作A 、B 、C 读取到最新值这一段时间。

·      最终一致性

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

(2). 变体

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 中的所有写操作。

 

3.BASE

    有一种架构的方法(approach) 称作BASE(Basically Available, Soft-state, Eventually consistent) 支持最终一致概念的接受。说起来很有趣，BASE 的英文意义是碱，而ACID 是酸，真的是水火不容啊。但如果认为任何架构应该完全基于一种(BASE) 或完全基于另一种(ACID) ，就大错特错。

(1).ACID

概念

    ACID 是关系型数据库的最基本原则。但是在遵守ACID 原则规定的强一致性的同时，会对性能造成很大的影响。对于大多数的互联网应用来讲，强一致性并不是非常重要的。和一致性比起来，可用性更加重要性一些。最终一致性简单的讲就是在某一个短暂的时间内数据可以不一致，但是在无限长的时间内，所有节点上的replica 最终会达到完全一致。

对比

·      和ACID 完全不同，BASE 的基本思想就是牺牲强一致性，以便获得可用性或可靠性。

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

(2).BASE 特征

Basically Availble( 基本可用)

    和完全可用的区别是：在分布式系统部分损坏的时候，允许部分内容不可用，但是其他部分仍旧可用。因此称这种系统为" 基本可用" 。比如，一个数据存储系统由五个节点构成。其中一个发生了损坏，这个时候，只有20% 的数据不能访问，其他80% 数据仍旧可用。那么就可以称这种系统为基本可用的。

Soft-state( 软状态/ 柔性事务)

    "Soft state" 可以理解为" 无连接" 的，而 "Hard state" 是" 面向连接" 的。

    Soft state 可以和Hard State 和Stateless 对比着去理解。Stateless 是指无状态。在分布式系统中，如果每一个Server 都是无状态的，那么这个系统的可靠性是非常高的。因为即使坏了任何一个server ，都不会影响到整体的运行情况。如果一个Server 是Hard State 的。那么，这个系统保留了所有客户端发过来的状态，系统整体的某些状态会因为某一台保存了状态的服务器挂掉而丢失。系统是非常不可靠的。在很多资料中都写到，Soft State 只会保留客户端的状态一段时间，在这段时间过后，如果客户端没有再次发送刷新状态的请求时，这个状态就会消失。这个概念最先来自于计算机网络领域。最近被应用于服务器的设计。

Eventual Consistency( 最终一致性)

    最终一致性也是ACID 的最终目的。

    最终一致性相对于其他两个概念而言还是比较好解释的。除了最终一致性，强一致性之外，还有一个弱一致性。简单的说，一致性的不同类型主要是区分在高并发的数据访问操作下，后续操作是否能够获取最新的数据。不同的策略决定了不同的一致性类型。当一次更新操作之后，后续的读操作如果全部保证是更新后的数据，那么就是强一致性。如果不能保证后续访问读到的都是更新后的，那么就是弱一致性。最终一致性是弱一致性的一种特例。最终一致性规定，后续的访问操作可以暂时不返回更新后的数据，但是经过一段时间之后，必须返回更新后的数据。也就是最终保持一致。最终一致性还有很多变体，比如Casual Consistency 、Session Consistency 、Read-your-writes Consistency 等。

(3).BASE 思想

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

·      按功能划分数据库

·      sharding 碎片

 

4. 其他

(1).I/O 的五分钟法则

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

 

 

随着闪存时代的来临，五分钟法则一分为二: 是把SSD 当成较慢的内存(extended buffer pool) 使用还是当成较快的硬盘(extended disk) 使用。小内存页在内存和闪存之间的移动对比大内存页在闪存和磁盘之间的移动。在这个法则首次提出的 20 年之后，在闪存时代，5 分钟法则依然有效，只不过适合更大的内存页( 适合64KB 的页，这个页大小的变化恰恰体现了计算机硬件工艺的发展，以及带宽、延时) 。

(2). 不要删除数据

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

软删除的概念

    所谓软删除主张在表中增加一个IsDeleted 列以保持数据完整。如果某一行设置了IsDeleted 标志列，那么这一行就被认为是已删除的。

软删除的问题

    Ayende 觉得这种方法" 简单、容易理解、容易实现、容易沟通" ，但" 往往是错的" 。问题在于: 删除一行或一个实体几乎总不是简单的事件。它不仅影响模型中的数据，还会影响模型的外观。所以我们才要有外键去确保不会出现" 订单行" 没有对应的父" 订单" 的情况。而这个例子只能算是最简单的情况。当采用软删除的时候，不管我们是否情愿，都很容易出现数据受损，比如谁都不在意的一个小调整，就可能使" 客户" 的" 最新订单" 指向一条已经软删除的订单。

理解" 删除"

    如果开发者接到的要求就是从数据库中删除数据，要是不建议用软删除，那就只能硬删除了。为了保证数据一致性，开发者除了删除直接有关的数据行，还应该级联地删除相关数据。

可Udi Dahan 提醒读者注意，真实的世界并不是级联的:

    假设市场部决定从商品目录中删除一样商品，那是不是说所有包含了该商品的旧订单都要一并消失？

    再级联下去，这些订单对应的所有发票是不是也该删除？

    这么一步步删下去，我们公司的损益报表是不是应该重做了？

    没天理了。

    问题似乎出在对" 删除" 这词的解读上。

Dahan 给出了这样的例子:

    我说的" 删除" 其实是指这产品" 停售" 了。我们以后不再卖这种产品，清掉库存以后不再进货。以后顾客搜索商品或者翻阅目录的时候不会再看见这种商品，但管仓库的人暂时还得继续管理它们。" 删除" 是个贪方便的说法。他接着举了一些站在用户角度的正确解读:

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

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

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

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

软删除的替代

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

建议

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

(3)."RAM 是硬盘、硬盘是磁带"

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

    Tim Bray 早在网格计算成为热门话题之前，就讨论过以RAM 和网络为中心的硬件结构的优势 ，可以用这种硬件建立比磁盘集群速度更快的RAM 集群。

内存、网络与硬盘访问对比

    对于数据的随机访问，内存的速度比硬盘高几个数量级( 即使是最高端的磁盘存储系统也只是勉强达到1,000 次寻道/ 秒) 。其次， 随着数据中心的网络速度提高，访问内存的成本更进一步降低。通过网络访问另一台机器的内存比访问磁盘成本更低。就在我写下这段话的时候，Sun 的 Infiniband 产品线中有一款具备9 个全互联非阻塞端口交换机，每个端口的速度可以达到30Gbit/sec ！Voltaire 产品的端口甚至更多；简直不敢想象。

典型操作时间

    各种操作的时间，以2001 年夏季，典型配置的1GHz 个人计算机为标准:

 

执行单一指令	1 纳秒
从 L1 高速缓存存取一个子	2 纳秒
从内存取一个字	10 纳秒
从磁盘去连续存放的一个字	200 纳秒
磁盘寻址并取字	8 毫秒
以太网	2GB/s

 

磁盘顺序访问的优势

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

内存系统

    时间闪到几年之后的今天，我们发现硬件的发展趋势在RAM 和网络领域势头不减，而在硬盘领域则止步不前。BillMcColl 提到用于并行计算的海量内存系统已经出现:

内存是新的硬盘！硬盘速度提高缓慢，内存芯片容量指数上升，in-memory 软件架构有望给各类数据密集的应用带来数量级的性能提升。小型机架服务器(1U 、2U) 很快就会具备T 字节、甚至更大量的内存，这将会改变服务器架构中内存和硬盘之间的平衡。硬盘将成为新的磁带，像磁带一样作为顺序存储介质使用( 硬盘的顺序访问相当快速) ，而不再是随机存储介质( 非常慢) 。这里面有着大量的机会，新产品的性能有望提高10 倍、100 倍。

海量内存系统: http://www.computingatscale.com/?p=54

案例-Twriter

    Dare Obsanjo 指出如果不把这句真言当回事，会带来什么样的恶劣后果 —— 也就是Twitter 正面临的麻烦。论及Twitter 的内容管理，Obsanjo 说，" 如果一个设计只是简单地反映了问题描述，你去实现它就会落入磁盘I/O 的地狱。不管你用Ruby on Rails 、Cobol on Cogs 、C++ 还是手写汇编都一样，读写负载照样会害死你。" 换言之，应该把随机操作推给RAM ，只给硬盘留下顺序操作。

http://www.25hoursaday.com/weblog/2008/05/23/SomeThoughtsOnTwittersAvailabilityProblems.aspx

MapReduce 适合磁盘的原因

    Tom White 是Hadoop Core 项目的提交者，也是Hadoop 项目管理委员会的成员。他对Gray 的真言中" 硬盘是新的磁带" 部分作了更深入地探讨。White 在讨论MapReduce 编程模型的时候指出，为何对于Hadloop 这类工具来说，硬盘仍然是可行 的应用程序数据存储介质:

    本质上，在MapReduce 的工作方式中，数据流式地读出和写入硬盘，MapReduce 是以硬盘的传输速率不断地对这些数据进行排序和合并。与之相比，访问关系数据库中的数据，其速率则是硬盘的寻道速率( 寻道指移动磁头到盘面上的指定位置读取或写入数据的过程) 。为什么要强调这一点? 请看看寻道时间和磁盘传输率的发展曲线。寻道时间每年大约提高5% ，而数据传输率每年大约提高20% 。寻道时间的进步比数据传输率慢 —— 因此采用由数据传输率决定性能的模型是有利的。MapReduce 正是如此。

固态硬盘的影响

    虽然固态硬盘(SSD) 能否改变寻道时间/ 传输率的对比还有待观察，White 文章的跟贴 中，很多人都认为SSD 会成为RAM/ 硬盘之争中的平衡因素。

IMDG - In-Memory Data Grid

    Nati Shalom 对内存和硬盘在数据库部署和使用中的角色作了一番有理有据的评述 。Shalom 着重指出用数据库集群和分区来解决性能和可伸缩性的局限。他说，" 数据库复制和数据库分区都存在相同的基本问题，它们都依赖于文件系统/ 硬盘的性能，建立数据库集群也非常复杂" 。他提议的方案是转向In-Memory Data Grid(IMDG) ，用Hibernate 二级缓存或者GigaSpaces Spring DAO 之类的技术作支撑，将持久化作为服务(Persistence as a Service) 提供给应用程序。Shalom 解释说，IMDG 提供在内存中的基于对象的数据库能力，支持核心的数据库功能，诸如高级索引和查询、事务语义和锁。IMDG 还从应用程序的代码中抽象出了数据的拓扑。通过这样的方式，数据库不会完全消失，只是挪到了" 正确的" 位置。

IMDG 相比直接RDBMS 访问的优势

·      位于内存中，速度和并发能力都比文件系统优越得多

·      数据可通过引用访问

·      直接对内存中的对象执行数据操作

·      减少数据的争用

·      并行的聚合查询

·      进程内(In-process) 的局部缓存

·      免除了对象- 关系映射(ORM)

你是否需要改变对应用和硬件的思维方式，最终取决于你要用它们完成的工作。但似乎公论认为，开发者解决性能和可伸缩性的思路已经到了该变一变的时候。

(4).Amdahl 定律和Gustafson 定律

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

Amdahl 定律的加速比: S(n) = 1/(K+(1-K)/n) = n/(1+(n-1)K)  // 使用1 个处理器的串行计算时间/ 使用n 个处理器的并行计算时间

Gustafson 定律的加速比: S(n) = K+(1-K)n  // 使用n 个处理器的并行计算量 / 使用1 个处理器的串行计算量

* 通俗的讲，Amdahl 定律将工作量看作1 ，有n 核也只能分担1-K 的工作量；而Gustafson 定律则将单核工作量看作1 ，有n 核，就可以增加n(1-K) 的工作量。这里没有考虑引进分布式带来的开销，比如网络和加锁。成本还是要仔细核算的，不是越分布越好。控制算法的复杂性在常数范围之内。

(5). 万兆以太网

      自行研究