转自（http://www.programmer.com.cn/9260/ ）

英文原文：How to beat the CAP theorem

?

CAP定理是数据系统设计的基本理论，目前几乎所有的数据系统的设计都遵循了这个定理。但CAP定理给目前的数据系统带来了许多复杂的、不可控的问题，使得数据系统的设计越来越复杂。Twitter首席工程师、Storm的作者Nathan Marz在本文中通过避开CAP定理带来的诸多复杂问题，展示了一个不同于以往的数据系统设计方案，给我们的数据系统设计带来了全新的思路。

CAP定理指出，一个数据库不可能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition-Tolerance）。

一致性（Consistency）是指执行了一次成功的写操作之后，未来的读操作一定可以读到这个写入的值。可用性（Availability）是指系统总是可读可写的。Yammer的Coda Hale和Cloudera的Henry Robinson都阐述过，分区容错性是不能牺牲的，因此只能在一致性和可用性上做取舍，如何处理这种取舍正是目前NoSQL数据库的核心焦点。

选择一致性而不是可用性的系统将面临一些尴尬的问题，当系统不可用时怎么办？你可以对写操作进行缓冲处理，但如果存储缓冲数据的机器出现故障，客户端将丢失写入的值。同样地，缓冲写也可以被认为是一种非一致性的操作，因为客户端认为成功的写入实际上并没有写入到实际的数据库中。当然，系统可以在机器不可用时向客户端返回错误，但可以想象，一个经常告诉客户端“请重试”的产品是多么令人讨厌。

另一个方案是选择可用性放弃一致性。这种情况下最好的一致性保障是“最终一致性”（Eventually Consistency）。当使用最终一致性的系统时，客户端有时会读到与刚刚写入数据不同的数据。有时候，同一时间同一个key的多个请求有可能返回不同的结果。数据更新并不能及时在所有的复制节点上生效，所以不同的复制节点上可能读取到的是不同的值。当你检测到数据不一致性时，你需要进行修复（Repair）操作，这就需要使用矢量时钟（vector clock）记录数据的版本历史并合并不同的数据更新（这称为读取修复，read repair）。

我相信在应用层维护最终一致性对开发人员负担太重，开发人员极易弄错读取修复的代码，而一旦开发人员犯错，有问题的读取修复将对数据库系统造成不可逆的损坏。

所以牺牲可用性时问题会很多，牺牲一致性时构建和维护系统的复杂度又很高，但这里又只有两个选择，不管怎样做都会不完美。CAP定理是改不了的，那么还有什么其他可能的选择吗？

实际上，还有一个办法：你并不能避开CAP定理，但可以把复杂的问题独立出来，免得你丧失对整个系统的掌控能力。CAP定理带来的复杂性，其实是我们如何构建数据系统这一根本问题的体现。其中有两点特别重要：数据库中可变状态和更新状态的增量算法。复杂性正是这两点和CAP定理之间的相互作用导致的。

本文将通过一个数据库系统的设计，来说明如何解决CAP定理通常会造成的复杂性问题。但我要做的不仅仅如此，CAP定理是一个针对机器发生错误时系统容错性的一个定理，而这里有比机器容错性更加重要的容错性——人为操作容错性。在软件开发中一个确定的事实是，开发人员都并非完人，产品中难免有一些Bug，我们的系统必须对有Bug的程序写入的错误数据有足够的适应能力，我要展示的系统将是这样一个可以容忍人为错误的系统。

本文将挑战你对数据系统如何构建这一问题的假设，通过颠覆传统数据系统构建方法，我会让大家看到一个前所未见的优雅、扩展性强、健壮的数据系统。

什么是数据系统？

在开始介绍系统设计之前，让我们先来看看我们要解决的问题：数据系统的目的在于什么？ 什么是数据？ 在我们考虑CAP定理之前，我们必须给出一个可以适用于所有数据应用程序的定义来回答上述问题。

数据应用程序种类很多，包括存入和提取数据对象、连接、聚合、流处理、机器学习等。似乎并不存在一个对数据系统的明确定义，数据处理的多样性使得我们很难用一个定义来描述。

事实却并非如此，下面这个简单的定义：

Query = Function(All Data)

概括了数据库和数据系统的所有领域。每一个领域——有50年历史的RDBMS、索引、OLAP、OLTP、MapReduce、EFL、分布式文件系统、流处理器、NoSQL等——都可以被概括进这个方程。

所谓数据系统就是要回答数据集问题的系统，这些问题我们称之为“查询”。上面的方程表明，查询就是数据上的一个函数。

上述方程对于实际使用来说太过于笼统，几乎对复杂的数据系统设计不起什么作用。但如果所有的数据系统都遵循这个方程又会怎样呢？这个方程是探索我们数据系统的第一步，而它最终将引导我们找到“打败”CAP定理的方法。

这个方程里面有两个关键概念：数据、查询。这两个完全不同的概念经常被混为一谈，所以下面来看看这两个概念究竟是什么意思。

数据

我们先从“数据”开始。所谓数据就是一个不可分割的单位，它肯定存在，就跟数学里面的公理一样。

关于“数据”有两个关键的性质。首先，数据是跟时间相关的，一个真实的数据一定是在某个时间点存在于那儿。比如，假如Sally在她的社交网络个人资料中写她住在芝加哥，你拿到的这个数据肯定是她某个时间在芝加哥填写的。假如某天Sally把她资料里面居住地点更新为亚特兰大，那么她肯定在这个时候是住在亚特兰大的，但她住在亚特兰大的事实无法改变她曾经住在芝加哥这个事实——这两个数据都是真实的。

其次，数据无法改变。由于数据跟某个时间点相关，所以数据的真实性是无法改变的。没有人可以回到那个时间去改变数据的真实性，这说明了对数据操作只有两种：读取已存在的数据和添加更多的新数据。那么CRUD就变成了CR【译者注：CRUD是指Create Read Update Delete，即数据的创建、读取、更新和删除】。

我去掉了“更新”操作，因为更新对于不可改变的数据没有任何作用。例如，更新Sally的位置信息本质上就是在她住的地方数据中新加一条最近的位置信息而已。

我同样去掉了“删除”操作，因为绝大部分删除操作可以更好地表述为新加一条数据。比如Bob在Twitter上不再关注Mary了，这并不能改变他曾经关注过Mary这个事实。所以与其删除Bob关注Mary这个数据，还不如新加一条Bob在某个时间点不再关注Mary这个数据。

这里只有很少数的情况需要永久“删除”数据，例如规则要求你每隔一段时间清掉数据，这个情况在我将要展示的系统中有很好的解决方案，所以为了简洁，我们暂不考虑这些情况。

查询

查询是一个针对数据集的推导，就像是一个数学里面的定理。例如，你可以通过计算“Sally现在的位置在哪里”这个查询来得到Sally最新的位置数据。查询是整个数据集合上的函数，可以做一切事情：聚合、连接不同类型的数据等。因此，你可以查询系统中女性用户的数量，可以查询最近几小时热门的Twitter内容。

前面我已经定义查询是整个数据集上的函数，当然，不是所有的查询都需要整个数据集，它们只需要数据集的一个子集。但我的定义是涵盖了所有的查询类型，如果想要“打败”CAP定理，我们需要能够处理所有的查询。

打败CAP定理

计算查询最简单的办法就是按照查询语义在整个数据集上运行一个函数。如果这可以满足你对延迟的要求，那么就没有其他需要构建的了。

可想而知，我们不能指望在整个数据集上的查询能够很快完成，特别是那些服务大型网站、需要每秒处理几百万次请求的系统。但假如这种查询可以很快完成，让我们来看看像这样的系统和CAP定理的PK结果：你将会看到，这个系统不仅打败了CAP定理，而且还消灭了它。

CAP定理仍然适用，所以你需要在可用性和一致性上做出选择，这里的漂亮之处在于，一旦你权衡之后做出了选择，你就做完了所有的事情。通常的那些因为CAP定理带来的问题，都可以通过不可改变的数据和从原始数据中计算查询来规避。

如果你选择一致性而不是可用性，那么跟以前并没有多大的区别，因为