CAP理论

CAP理论在互联网界有着广泛的知名度，知识稍微宽泛一点的工程师都会把其作为衡量系统设计的准则。大家都非常清楚地理解了CAP：任何分布式系统在可用性、一致性、分区容错性方面，不能兼得，最多只能得其二，因此，任何分布式系统的设计只是在三者中的不同取舍而已。

事实上，让人吃惊的是，CAP在国外的响力完全不如所想，相反还伴随着诸多的争论。下面我们系统地阐述一下CAP的来龙去脉。

1.CAP的历史

1985年Lynch证明了异步通信中不存在任何一致性的分布式算法（FLP Impossibility）的同时，人们就开始寻找分布式系统设计的各种因素。一致性算法既然不存在，但若能找到一些设计因素，并进行适当的取舍以最大限度满足实现系统需求成为当时的重要议题。比如，在CAP之前研究者就已经发现低延迟和顺序一致性不可能同时被满足【8】。

2000年，Eric Brewer教授在PODC的研讨会上提出了一个猜想：一致性、可用性和分区容错性三者无法在分布式系统中被同时满足，并且最多只能满足其中两个！

这个猜想首次把一致性、可用性和分区容错三个因素提炼出来作为系统设计的重要特征，断言用此三者可以划分所有的分布式系统，并指明这三个特征之间的不可能性关系。Brewer猜想比单纯的“低延迟和顺序一致性不能被同时满足”的结论更具体，对实际系统的构建也更具有可操作性！

Brewer教授当时想象的分布式场景是webservice，一组websevrice后台运行着众多的server，对service的读写会反应到后台的server集群，并对CAP进行了定义：

• C（一致性）：所有的节点上的数据时刻保持同步
• A（可用性）：每个请求都能接受到一个响应，无论响应成功或失败
• P（分区容错）：系统应该能持续提供服务，即使系统内部有消息丢失（分区）

高可用、数据一致是很多系统设计的目标，但是分区又是不可避免的事情：

• CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。
• CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。
• AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

CAP的出现仿佛是一盏明灯，它揭露了分布式系统的本质，并给出了设计的准则，而这正是1985年以来人们正在寻找的东西！所以CAP在当时的影响力是非常大的！

2. CAP被上升为定理

2002年，Lynch与其他人证明了Brewer猜想，从而把CAP上升为一个定理【2】。但是，她只是证明了CAP三者不可能同时满足，并没有证明任意二者都可满足的问题，所以，该证明被认为是一个收窄的结果。

Lynch的证明相对比较简单：采用反正法，如果三者可同时满足，则因为允许P的存在，一定存在Server之间的丢包，如此则不能保证C，证明简洁而严谨。

在该证明中，对CAP的定义进行了更明确的声明【2】：

• C：一致性被称为原子对象，任何的读写都应该看起来是“原子“的，或串行的。写后面的读一定能读到前面写的内容。所有的读写请求都好像被全局排序。
  
• A：对任何非失败节点都应该在有限时间内给出请求的回应。（请求的可终止性）
• P：允许节点之间丢失任意多的消息，当网络分区发生时，节点之间的消息可能会完全丢失

该定义比Brewer提出的概念清晰了很多，也显得更加正式化！

3.前所未有的质疑

当国内工程师对CAP痴迷的时候，国外的工程师和研究者对CAP提出了各种质疑，纷纷有用反例证明着CAP在各种场合不适用性，同时挑战着Lynch的证明结果！

纵观这些质疑，基本都是拿着一个非常具体的系统，用CAP的理论去套，最后发现要么CAP不能Cover所有的场景，要么是CAP的定义非常模糊，导致自相矛盾！一句话，把CAP接地气是非常困难的！

你是否看了CAP的概念定义后还是感觉很模糊？如果是，你并不孤独，有很多人都是如此！

CAP没有考虑不同的基础架构、不同的应用场景、不同的网络基础和用户需求，而C、A、P在这些不同场景中的含义可能完全不同，这种无视差异化的定义导致了非常大的概念模糊，同时也变成CAP被质疑的源头！

3.1 质疑1：概念混乱，废话一堆，不能作为定理

在论文【4】中，作者对CAP发起了强烈的挑战，强烈谴责了CAP模糊不一致的概念：

1. 在CA中的C代表的是本地一致性；CP中的代表的是全局一致性，AP中直接没有C；这些C的含义在不同的场景根本就不同
2. 终端用户agent该不该引入到CAP中？CAP到底是说一个agent的多次更新，还是多个用户的一次更新？没有agent参与的系统谈什么一致性？
3. 如果分区发生在系统内部（水平分区），对agent而已并没有影响；若分区发生在agent与系统间（垂直分区），这种情况对DNS系统架构的可用性根本没有任何影响；但对银行事务架构却有巨大影响。也就是说，可用性、分区容错，是两个相关切无法独立切分的概念

一句话：CAP说了一些永远不存在的废话！作为一个严格的数学定理，一定要概念清晰并且可自证明，CAP显然不具备这个条件，并声称“绝不承认其为一个定理”！

【4】的作者对相对论有相当的理解，从相对论来看，每个节点都只知道自己的结果，永远无法得知其他节点的情况，系统整体是否一致我怎么会知道？

并且作者对一致性、可用性归结为一个非常深刻的见解：一切都是时间视图！多长时间返回结果算可用？多长时间返回认为不可用？多长时间数据同步算一致？因此，一切的本质是时间！

根据时间特性和相对论，作者提出了一个独创的promise系统模型，每个节点都对自己的行为在有限时间内进行承诺，其他节点根据这个承诺和自己的状态决定本地如何处理。。。

作者还上传了自己的笔记拍照，我大体看了下，基本上是构建了一个基于时间同步的有限状态机，实际上Lynch早就证明，在同步环境的一致性是可以达到的！

3.2 质疑2：不适用于数据库事务架构

【6】的作者，把详细地列举了分布式事务中可能的分区情况，比如说应用因为更新一些错误的数据而导致失败，此时无论使用什么样的高可用方案都是徒劳，因为数据发生了无法修正错误！作者还列举了其他一些情况，虽然分区发生但无法保持高可用。这就说明了CAP并不能不被用来完全解释数据库事务架构！

作者还建议，应该放弃分区容错，因为在局域网中分区很少发生；而在广域网中，有各种备选方案，导致实际上的分区也较少发生。

3.3 质疑3：应该构建不可变模型避免CAP的复杂性

【7】的文章标题就是锤死CAP，作者对CAP的不屑溢于言表！

作者认为CAP的困境在于允许数据变更，每次变更就得数据同步，保持一致性，这样系统非常复杂。

他认为数据就是客观存在的，不可变，只能增、查。传统的CURD变为CR。这个概念非常类似Cassandra中的顺序写的概念，任何的变更都是增加记录。通过对所有记录的操作进行合并，从而得到最终记录。

因此，作者认为任何的数据模型都应该抽象为：Query=Function(all data)，任何的数据试图都是查询，查询是对全体数据施加了某个函数的结果。这个定义清晰简单，完全抛弃了CAP那些繁琐而又模糊的语义。因为每次操作都是队所有数据进行全局计算，也就没有了一致性问题！

有这样的系统吗？有，Hadoop便是！作者认为，Hadoop的HDFS只支持数据增加，而Mapeduce却进行全局计算，完美地符合了他对数据处理的期望！

Hadoop也存在某个节点数据丢失的问题，但随着流式计算，丢失的数据终究会随着系统的正常而被最终合并，因此数据最终是一致的。

Hadoop不能进行实时计算咋办？作者又构建了一套基于Cassandra和ElephantDB的实时数据处理系统。。。。搞的无比复杂！

3.4 质疑4：分区容错概念有误导

【5】的作者主要质疑【6】，但比较清晰得揭露了CAP的概念之间的模糊。

【5】认为，可用性和一致性是分布式系统的属性，而分区却是网络的一个属性。不能再问题发生时是否选择要不要分区，而是应该在分区既定的情况下选择要一致性还是可用性。网络分区会发生在两种情况：

• 交换机失败，导致网络发生【6】中描述的情况，网络被分成几个子网
• 机器延迟或死机，导致某些server失去联系

【6】中所谓的分区就是情况1，每个独立的子网还能正常运作，作者认为这种分区条件非常苛刻，更倾向于认为这只是分区可用性的一种度量方式（发给每个子网的请求都有正确的response）。

而实际上，因为机器原因发生的分区的情况更常见一些，如果“很多”机器都发生故障，系统会因为一个“多数派”的丢失而导致不可用（比如，因为多数不存在，最新的读可能无法读取到上一次的写）。一句话：分区也同时蕴涵着不可用，这两个概念之间存在重叠。

作者认为，CAP比较合理的表达方式应该是：在一个允许网络发生故障的系统中，该选择一致性还是可用性？

当系统的机器数量持续增加时，一致性会加剧时延，维护一致性的成本会非常之高，因此我们基本就剩下一种选择：在允许网络失败的系统中，更多地是选择可用性。而Zookeeper、Hadoop之所以选择一致性，是因为这些系统多数是有在同一集群的少数节点构成！

【5】的作者其实间接地否认了“3个中同时满足2个”这样的误解，而是从更深层次探讨了CAP的本质，但并没有试图推翻CAP。

4.对质疑的回应

面对大量的质疑，Brewer和Lynch终于坐不住了，因此两人纷纷出来澄清：

Brewer于2012年重申【1】：

• ”3个中的2个“这个表述是不准确的，在某些分区极少发生的情况下，三者能顺畅地在一起配合
• CAP不仅仅是发生在整个系统中，可能是发生在某个子系统或系统的某个阶段

该声明并不否认像质疑3那种三个因素协同工作的情况，并把CAP应用在一些更细粒度的场景中。

Lynch也在10年后的2012年重写了论文【3】，该论文主要做了几件事：

• 把CAP理论的证明局限在原子读写的场景，并申明不支持数据库事务之类的场景
• 一致性场景不会引入用户agent，只是发生在后台集群之内
• 把分区容错归结为一个对网络环境的陈述，而非之前一个独立条件。这实际上就是更加明确了概念
• 引入了活性(liveness)和安全属性(safety)，在一个更抽象的概念下研究分布式系统，并认为CAP是活性与安全熟悉之间权衡的一个特例。其中的一致性属于liveness，可用性属于safety
• 把CAP的研究推到一个更广阔的空间：网络存在同步、部分同步；一致性性的结果也从仅存在一个到存在N个（部分一致）；引入了通信周期round，并引用了其他论文，给出了为了保证N个一致性结果，至少需要通信的round数。也介绍了其他人的一些成果，这些成果分别都对CAP的某一个方面做出了特殊的贡献！

其实Lynch的论文主要就是两件事：缩小CAP适用的定义，消除质疑的场景；展示了CAP在非单一一致性结果下的广阔的研究结果！并顺便暗示CAP定理依旧正确！

从此论文还是可以看出，Lynch的功力高出其他质疑者好多！

5. 该如何看待CAP？

首先肯定的是，CAP并不适合再作为一个适应任何场景的定理，它的正确性更加适合基于原子读写的NoSQL场景。质疑虽然很多，但很多质疑者只是偷欢概念，并没有解决各个因素之间的取舍问题。而无论如何C、A、P这个三个概念始终存在任何分布式系统，只是不同的模型会对其有不同的呈现，可能某些场景对三者之间的关系敏感，而另一些不敏感。在所有的质疑当中，质疑4是分析的比较中肯的，其清晰的概念分析该让我们对CAP有更深入的理解！

就像Lynch所说，现在分布式系统有很多特性，比如扩展性、优雅降级等，虽然时间的发展，或许这些也会被纳入研究范畴，而作为开发者，这都是我们需要考虑的问题，而不仅是CAP三者！

6.参考资料 

【1】

【2】

【3】

【4】http://markburgess.org/blog_cap.html

【5】http://blog.cloudera.com/blog/2010/04/cap-confusion-problems-with-partition-tolerance/

【6】http://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext

【7】http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html

【8】http://highscalability.com/blog/2011/11/23/paper-dont-settle-for-eventual-scalable-causal-consistency-f.html