CAP定理

CAP定理是Eric Brewer于1998年发现，在2000发表在PODC，2002年Seth Gilbert和Nancy Lynch证明了这个理论。

CAP定理是分布式系统设计的基础，它指出：对于一个分布式数据存储系统，无法同时满足ƒ以下三个条件。

1. 一致性 Consistency：每次读要么获得最新写入的数据，要么返回错误
2. 可用性 Availability：每次请求都会返回一个非错误的响应，但是不保证获得的是最新写入的数据
3. 分区可容忍性 Partition Tolerance：任意数量的消息被节点间的网络丢弃或延迟，系统仍能继续运行

CAP定理表明：当网络发送分区时，必须要在一致性和可用性之间做出选择；而在网络没有发生分区时，一致性和可用性是可以同时满足的。

三选二：CP、AP、CA

CAP定理指出一致性、可用性和分区容忍性三个条件无法同时满足，但是可以同时满足其中任意两个条件：

• CP (Consistency + Partition Tolerance)：这样的系统关注一致性和分区容忍性。它关注的是系统里大多数节点的一致性，只要系统里大多数节点的数据是一致的，少数节点在网络发送分区时数据没有更新到最新版本，只需要将这些节点的数据标记为不可以，就可以提供部分的可用性。典型的算法包括：Paxos和Quorum。典型的系统包括：MongoDB，HBase，Memcache。
• AP (Availability + Partition Tolerance)：这样的系统关注可用性和分区容忍性。由于系统不保证数据一致性，因此数据可能会发送冲突，解决数据冲突就需要维护数据版本。典型的系统包括：Dynamo，Cassandra, RIAK，CouchDB。
• CA (Consistency + Availability)：CAP理论提出就是针对分布式数据存储系统，在分布式环境中网络分区虽然是小概率事件，但是长期看是不可避免的，所以P这个属性是必须具备的。CA系统只存在于单机环境，例如传统的关系型数据库RDBMS（Oracle、MySQL)。

十二年后的CAP

2012年Brewer发表了一篇文章，重新解释了他对CAP定理的理解：

1. 首先，网络分区的发生是小概率事件，当网络没有发生分区的时候没有任何理由放弃C或者A
2. 其次，在同一个系统中C和A的选择可能发生多次，不同的子系统可以做不一样的选择，当条件不同时做出的选择可以不一样，例如：不同的操作、数据、用户可能会导致不同的选择
3. 最后，这三个属性不是0和1的选择，而是线性的。可用性很明显可以从0%到100%，其实一致性甚至分区容忍性也是有差别的

参考

• CAP theorem – Wikipedia
• CAP Twelve Years Later: How the “Rules” Have Changed
• CAP Confusion: Problems with ‘partition tolerance’ – Cloudera博客
• Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services – Seth Gilbert & Nancy Lynch