CAP定理(CAP theorem)是由大牛 Eric Brewer 在2000年PODC上首次提出的。起先它是个猜想,Brewer 认为在分布式计算系统中对某个数据不存在一个算法同时满足数据一致性(consistency),读操作是否总能读到前一个写操作的结果,即是说在分布式环境中,多点读出的数据是否是同一份最新的数据副本;可用性(Availability),时刻能进行对数据的读写访问,所有的请求都应该成功并且收到返回;分区容错(partition-tolerance),无论任何消息丢失,系统都可用。2002年 Gilbert 和 Lynch 证明了 Brewer 的猜想使之成为了定理。

NoSQL 一定程度上就是基于这个理论提出来的,因为传统的关系型数据库都具有 ACID (原子性、一致性、隔离性、持久性)属性,对一致性要求很高。NoSQL 数据库都以水平扩展著称,为了提高系统性能和可扩展性,所以在 CAP 的选择上面,都倾向于坚持P,牺牲C(consistency)或牺牲A(Availability)来进行设计。

CAP选择
考虑CA:放弃 partition-tolerance 意味着把所有的机器搬到一台机器内部,一旦某个操作失败,整个系统就出错。代表是传统的关系型数据库、Vertica(Column-oriented)等,这些数据库对于分区容忍性方面比较不感冒,主要采用复制(Replication)来保证数据的安全性。
考虑CP:这种系统将数据分布在多个网络分区的节点上,并保证这些数据的一致性,但是对于可用性的支持方面有问题。一旦遇到 partition 事件,受影响的服务需要等待数据一致,因此在等待期间就无法对外提供服务,只能对部分数据进行读写。在多个节点上控制这一点会相当复杂,像 Google 的一般做法是将主分区归属在单一个数据中心里面,然后交给 Paxos 算法去解决跨区域的问题。代表有 BigTable(Column-oriented)、HBase(Column-oriented)、MongoDB(Document)、Redis(Key-value)。
考虑AP:系统只要每次对写都返回成功,对读都返回固定的某个值。Werner Vogel(Amazon CTO)认为不一致是可以容忍的,这有两个理由:一是可以在高并发条件下提高读写性能;二是处理一些分区状况——多数决模型(majority model)有可能使系统的一部分表现为不可用,虽然那些节点正运行良好。他在2008年发布在 ACM Queue上 的一篇数据库方面的重要文章,阐述了 NoSQL 数据库的理论基石——最终一致性(Eventual Consistency)。Quorum NRW策略和Gossip协议可以用来维护最终一致性。这类系统的代表有 Dynamo(Key-value)、Voldemort(Key-value)、Cassandra(Column-oriented)。

CAP 的三选二也不是绝对的非黑即白的有或无,这三种性质都可以在程度上衡量:可用性在0%到100%之间连续变化的,一致性分很多级别,连分区也可以细分为不同含义。虽然不可能在同一时刻满足 Consistency、Availability 和 Partition-tolerance 全部的3个要求,但是 Guy Pardon 的文章 A CAP Solution(Proving Brewer Wrong 将条件放松到系统可以分时达到 CAP,提出了一个满足 CAP 的解决方案。Twitter 的首席工程师 Nathan Marz 的文章 How to beat the CAP theorem 提出正是因为要不断的更新数据库中的数据,再加上 CAP ,才导致那些即便使用最终一致性的系统也会变得无比复杂。如果系统中不存在会改变的数据(append-only immutable data),所有的更新都作为创建新数据的方式存在,数据的处理由 CRUD 变为 CR,把读数据转化为一次请求(对整个数据集执行一个函数操作),这样就可以避免最终一致性的复杂性,转而拥抱 CAP。