了解的CAP和BASE等理论

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

几个名词解释：

网络分区：俗称“脑裂”。当网络发生异常情况，导致分布式系统中部分节点之间的网络延时不断变大，最终导致组成分布式系统的所有节点中，只有部分节点之间能够进行正常通信，而另一些节点则不能。当网络分区出现时，分布式系统会出现局部小集群。

三态：分布式系统的每一次请求和响应包含：成功，失败，超时三种状态。

CAP

CAP理论，指的是在一个分布式系统中，不可能同时满足Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）这三个基本需求，最多只能满足其中的两项。

1、一致性：

指数据在多个副本之间是否能够保持一致的特性。当执行数据更新操作后，仍然剋保证系统数据处于一致的状态。

2、可用性：

系统提供的服务必须一直处于可用的状态。对于用户的每一个操作请求总是能够在“有限的时间内”返回结果。这个有限时间是系统设计之初就指定好的系统运行指标。返回的结果指的是系统返回用户的一个正常响应结果，而不是“out ot memory error”之类的系统错误信息。

3、分区容错性：

分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。组成分布式系统的每个节点的加入与退出都可以看成是一个特殊的网络分区。

一个分布式系统无法同时满足这三个条件，只能满足两个，意味着我们要抛弃其中的一项。

1、CA，放弃P：将所有数据都放在一个分布式节点上。这同时放弃了系统的可扩展性。

2、CP，放弃A：一旦系统遇到故障时，受影响的服务器需要等待一段时间，在恢复期间无法对外提供正常的服务。

3、AP，放弃C：这里的放弃一致性是指放弃数据强一致性，而保留数据的最终一致性。系统无法实时保持数据的一致，但承诺在一个限定的时间窗口内，数据最终能够达到一致的状态。

对于分布式系统而言，分区容错性是一个最基本的要求，因为分布式系统中的组件必然需要部署到不通的节点，必然会出现子网络，在分布式系统中，网络问题是必定会出现的异常。因此分布式系统只能在C（一致性）和A（可用性）之间进行权衡。

BASE

BASE理论是指，Basically Available（基本可用）、Soft-state（ 软状态/柔性事务）、Eventual Consistency（最终一致性）。是基于CAP定理演化而来，是对CAP中一致性和可用性权衡的结果。

核心思想：即使无法做到强一致性，但每个业务根据自身的特点，采用适当的方式来使系统达到最终一致性。

1、基本可用：

指分布式系统在出现故障的时候，允许损失部分可用性，保证核心可用。但不等价于不可用。比如：搜索引擎0.5秒返回查询结果，但由于故障，2秒响应查询结果；网页访问过大时，部分用户提供降级服务，等。

2、软状态：

软状态是指允许系统存在中间状态，并且该中间状态不会影响系统整体可用性。即允许系统在不同节点间副本同步的时候存在延时。

3、最终一致性：

系统中的所有数据副本经过一定时间后，最终能够达到一致的状态，不需要实时保证系统数据的强一致性。最终一致性是弱一致性的一种特殊情况。

BASE理论面向的是大型高可用可扩展的分布式系统，通过牺牲强一致性来获得可用性。ACID是传统数据库常用的概念设计，追求强一致性模型。

10年前，Eric Brewer教授指出了著名的CAP理论，后来Seth Gilbert 和 Nancy lynch两人证明了CAP理论的正确性。CAP理论告诉我们，一个分布式系统不可能满足一致性，可用性和分区容错性这三个需求，最多只能同时满足两个。

而由于当前的网络硬件肯定会出现延迟丢包等问题，所以分区容忍性是我们必须需要实现的。所以我们只能在一致性和可用性之间进行权衡，没有NoSQL系统能同时保证这三点。如果你关注的是一致性，那么您就需要处理因为系统不可用而导致的操作失败的情况，而如果您关注的是可用性，那么您应该知道系统的read操作可能不能精确的读取到write操作写入的最新值。因此系统的关注点不同，相应的采用的策略也是不一样的，只有真正的理解了系统的需求，才有可能利用好CAP理论。

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

key-value存储，如Amaze Dynamo等，可根据CAP三原则灵活选择不同倾向的数据库产品。 领域模型 + 分布式缓存 + 存储 （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 Available--基本可用
• 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思想的方案在性能上还是有潜力可挖的。

其他

ACID

　　指数据库事务正确执行的四个基本要素的缩写。包含：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。

I/O的五分钟法则

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

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

不要删除数据

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 个人计算机为标准：

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 White是 Hadoop 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)的工作量。 这里没有考虑引进分布式带来的开销，比如网络和加锁。成本还是要仔细核算的，不是越分布越好。 控制算法的复杂性在常数范围之内。