CAP的概念

2000年，Eric Brewer 教授在 ACM 分布式计算年会上指出了著名的 CAP 理论：

分布式系统不可能同时满足一致性(C: Consistency)，可用性(A: Availability)和分区容错性(P: Tolerance of network Partition)这三个需求。大约两年后，Seth Gilbert 和 Nancy lynch 两人证明了CAP理论的正确性。

三者的含义如下：

Consistency：一致性，一个服务是一致的完整操作或完全不操作（A service that is consistent operates fully or not at all，精确起见列出原文），也有人将其简称为数据一致性，任何一个读操作总是能读取到之前完成的写操作结果，也就是在分布式环境中，多点的数据是一致的。
Availability：可用性，每一个操作总是能够在确定的时间内返回，也就是系统随时都是可用的。
Tolerance of network Partition：分区容忍性，节点 crash 或者网络分片都不应该导致一个分布式系统停止服务。

关于 CAP 理论的历史和介绍可以参考 Brewer’s CAP Theorem 和中文翻译。

基本CAP的证明思路

CAP 的证明基于 异步网络，异步网络也是反映了真实网络中情况的模型。

真实的网络系统中，节点之间不可能保持同步，即便是时钟也不可能保持同步，所有的节点依靠获得的消息来进行本地计算和通讯。这个概念其实是相当强的，意味着任何超时判断也是不可能的，因为没有共同的时间标准。之后我们会扩展 CAP 的证明到弱一点的异步网络中，这个网络中时钟不完全一致，但是时钟运行的步调是一致的，这种系统是允许节点做超时判断的。

CAP 的证明很简单，假设两个节点集{G1, G2}，由于网络分片导致 G1 和 G2 之间所有的通讯都断开了，如果在 G1 中写，在 G2 中读刚写的数据， G2 中返回的值不可能是 G1 中的写值。由于 A 的要求，G2 一定要返回这次读请求，由于 P 的存在，导致 C一定是不可满足的。

为什么不能完全保证这个三点了，个人觉得主要是因为一旦进行分区了，就说明了必须节点之间必须进行通信，涉及到通信，就无法确保在有限的时间内完成指定的行为，如果要求两个操作之间要完整的进行，肯定会存在某一个时刻只完成一部分的业务操作，在通信完成的这一段时间内，数据就是不一致性的。如果要求保证一致性，那么就必须在通信完成这一段时间内保护数据，使得任何访问这些数据的操作不可用。

如果想保证一致性和可用性，那么数据就不能够分区。一个简单的理解就是所有的数据就必须存放在一个数据库里面，不能进行数据库拆分。这个对于大数据量，高并发的互联网应用来说，是不可接受的。

这里引用 Brewer’s CAP Theorem 中的图和文字来说明。

intro

上图显示了网络中的两个节点 N1，N2，他们共享同一数据 V，其值为 V0。N1 上有一个算法 A，我们可以认为 A 是安全、无 bug、可预测和可靠的。N2 上有一个类似的算法 B。在这个例子中，A 写入 V 的新值而 B 读取 V 的值。

scenario-1

正常情况过程如下：

1) A 写入新的 V 值，我们称作 v1。
2) N1 发送信息给 N2，更新 V 的值。
3) 现在 B 读取的 V 值将会是 V1。

scenario-2

如果网络断开，意味着从 N1 无法发送信息到 N2，那么在第3步的时候，N2 就会包含一个步一致的 V 值。

即使将其扩展到几百个事务中，这也会成为一个大问题。如果 M 是一个异步消息，那么 N1 无法知道 N2 是否收到了消息。即使 M 是保证能发送的，N1 也无法知道是否消息由于分区事件的发生而延迟，或 N2 上的其他故障而延迟。即使将 M 作为同步消息也不能解决问题，因为那将会使得 N1 上 A 的写操作和 N1 到 N2 的更新事件成为一个原子操作，而这将导致同样的等待问题。Gilbert 和Lynch已经证明，使用其他的变种方式，即使是部分同步模型（每个节点上使用安排好的时钟）也无法保证原子性。

因此，CAP 告诉我们，如果想让 A 和 B 是高可用的（例如，以最小的延迟提供服务）并且想让所有的 N1 到 Nn（n的值可以是数百甚至是上千）的节点能够冗余网络的分区（丢失信息，无法传递信息，硬件无法提供服务，处理失败），那么有时我们就得面临这样的情况：某些节点认为 V 的值是 V0 而其他节点会认为 V 的值是 V1。

让我们从事务的角度分析一下。下面的图中 a 是整个过程，要具有一致性的话需要等待 a1 进行 write，然后同步到 a2，然后 a2 再进行 write，只有整个事务完成以后，a2 才能够进行 read。但是这样的话使得整个系统的可用性下降，a2 一直阻塞在那里等待 a1 同步到 a2。这个时候如果对一致性要求不高的话，a2 可以不等待 a1 数据对于 a2 的写同步，直接读取，这样虽然此时的读写不具有一致性，但是在后面可以通过异步的方式使得 a1 和 a2 的数据最终一致，达到 最终一致性。

tx-view

BASE理论

BASE 理论是 CAP 理论结合实际的产物。 BASE(Basically Available, Soft-state,Eventuallyconsistent)英文中有碱的意思，这个正好和 ACID 的酸的意义相对，很有意思。BASE 恰好和 ACID 是相对的，BASE 要求牺牲高一致性，获得可用性或可靠性。

Basically Availble：基本可用(支持分区失败)
Soft-state：软状态/柔性事务(无状态连接，支持异步)
Eventual Consistency：最终一致性(不要求高一致性，只要求最终能够一致)

BASE 理论的核心是：牺牲高一致性，获得可用性或可靠性。

CAP选择

当处理 CAP 的问题时，你会有几个选择。最明显的是：

放弃 Tolerance of network Partition。如果你想避免分区问题发生，你就必须要阻止其发生。一种做法是将所有的东西（与事务相关的）都放到一台机器或者一个机架上。这样还是有可能部分失败，但你不太可能碰到由分区问题带来的负面效果。当然，这个选择会严重影响系统的扩展。
放弃 Availability。相对于放弃 Tolerance of network Partition 来说，其反面就是放弃 Availability。一旦遇到分区事件，受影响的服务需要等待数据一致，因此在等待期间就无法对外提供服务。在多个节点上控制这一点会相当复杂，而且恢复的节点需要处理逻辑，以便平滑地返回服务状态。
放弃 Consistency。放弃一致性，你的系统可能返回不太精确的数据，但系统将会变得“最终一致”，即使是网络发生分区的时候也是如此。

下面是一个使用 CAP 理论的生态系统的分布图：

任何架构师在设计分布式的系统的时候，都必须在这三者之间进行取舍。首先就是是否选择分区，由于在一个数据分区内，根据数据库的ACID特性，是可以保证一致性的，不会存在可用性和一致性的问题，唯一需要考虑的就是性能问题。对于可用性和一致性，大多数应用就必须保证可用性，毕竟是互联网应用，牺牲了可用性，相当于间接的影响了用户体验，而唯一可以考虑就是一致性了。

牺牲一致性

对于牺牲一致性的情况最多的就是缓存和数据库的数据同步问题，我们把缓存看做一个数据分区节点，数据库看作另外一个节点，这两个节点之间的数据在任何时刻都无法保证一致性的。

异常错误检测和补偿

还有一种牺牲一致性的方法就是通过一种错误补偿机制来进行

两阶段提交协议

第一阶段和第二阶段之间，数据也可不能是一致性的，也可能出现同样的情况导致异常。

CAP的反对声音

1，2008年9月CTO of atomikos写了一篇文章“A CAP Solution (Proving Brewer Wrong)”，试图达到CAP都得的效果。

这篇文章的核心内容就是放松Gilbert和Lynch证明中的限制：“系统必须同时达到CAP三个属性”，放松到“系统可以不同时达到CAP，而是分时达到”。

他设计的系统如下：

(1)程序如果能够读取数据库的话读取数据库，如果不能的话可以使用缓存代替。
(2)所有的读取操作使用版本号或者其他可以使用乐观锁的机制。
(3)客户端的所有更新操作全部放在队列中顺序处理。更新操作中要包括该更新的读取操作时的版本信息。
(4)当分区数量足够少的时候，可以处理队列中的更新操作。比较简单的方式是建立一个跨越所有分布式副本的事务，对每个副本进行更新操作（其他方式比如quorum等等也可以）。如果该更新的读取操作时的版本信息不是当前数据库中数据的版本信息，则将失败返回给客户端，否则返回成功。
(5)数据库操作结果（确认或者取消）通过异步的方式发送到客户端，可以通过邮件，消息队列或者其他异步方式。

该系统符合CAP如下：

符合C（高一致性）：读取的数据都是基于快照的，而且错误的更新操作不会执行。
符合A（高可用性）：读取和更新都会返回数据。
符合P（高分区容错性）：允许网络或者节点出错。

该设计是符合BASE理论的。

缺点：

1) 读数据可能会不一致，因为之前的写还在排队
2) partition必须在有限的时间内解决
3) update操作必须在所有的节点上保持同样的顺序

2， 2011年11月Twitter的首席工程师Nathan Marz写了一篇文章，描述了他是如何试图打败CAP定理的： How to beat the CAP theorem

本文中，作者还是非常尊重CAP定律，并表示不是要“击败”CAP，而是尝试对数据存储系统进行重新设计，以可控的复杂度来实现CAP。

Marz认为一个分布式系统面临CAP难题的两大问题就是：在数据库中如何使用不断变化的数据，如何使用算法来更新数据库中的数据。Marz提出了几个由于云计算的兴起而改变的传统概念：

1) 数据不存在update，只存在append操作。这样就把对数据的处理由CRUD变为CR
2) 所有的数据的操作就只剩下Create和Read。把Read作为一个Query来处理，而一个Query就是一个对整个数据集执行一个函数操作。

在这样的模型下，我们使用最终一致性的模型来处理数据，可以保证在P的情况下保证A。而所有的不一致性都可以通过重复进行Query去除掉。Martz认为就是因为要不断的更新数据库中的数据，再加上CAP，才导致那些即便使用最终一致性的系统也会变得无比复杂，需要用到向量时钟、读修复这种技术，而如果系统中不存在会改变的数据，所有的更新都作为创建新数据的方式存在，读数据转化为一次请求，这样就可以避免最终一致性的复杂性，转而拥抱CAP。

关于CAP理论的一些笔记