【转】如何打败 CAP 定理
本文来自 Apache Storm 之父 Nathan Marz 在 2011 年写的一篇文章，大数据上 Lambda 架构的提出者，他写了本书来进一步描述 Lambda 架构《Big Data: Principles and Best Practices of Scalable Realtime Data Systems》。
CAP 定理指出数据库不能同时保证一致性（Consistency）、可用性（Availability）和分区容错性（Partition-tolerance）。但是你不能牺牲分区容错性（请参阅 You Can’t Sacrifice Partition Tolerance），因此你必须在可用性和一致性之间进行权衡。管理这种权衡是 NoSQL 运动的核心焦点。
一致性意味着在你成功写入之后，后续的读取将始终计入该写入。可用性意味着你可以随时读取和写入系统。在一个分区中，你只能拥有这两个属性之一。
选择一致性而不是可用性的系统必须处理一些尴尬的问题。数据库不可用时怎么办？你可以尝试缓冲写入以备后用，但如果你丢失带有缓冲区的机器，则可能会丢失这些写入。 此外，缓冲写入可能是一种不一致的形式，因为客户端认为写入已成功，但写入尚未在数据库中。或者，你可以在数据库不可用时将错误返回给客户端。但是，如果你曾经使用过告诉你“稍后再试”的产品，你就会知道这会带来多么严重的后果。
另一种是选择可用性而不是一致性。这些系统可以提供的最佳一致性保证是“最终一致性”。如果你使用一个最终一致的数据库，那么有时你会读到与你刚刚写的不同的结果。 有时多个读取器同时读取同一个键值会得到不同的结果。更新可能不会传播到一个值的所有副本，因此最终会导致一些副本获得一些更新，而其他副本获得不同的更新。 一旦检测到值已经分叉，就需要你来修复该值。这需要使用矢量时钟追溯历史并将更新合并在一起（称为“读取修复”）。
我认为在应用层保持最终一致性对开发人员来说负担太重了。“读取修复”的代码极易受到开发者错误的影响；如果你犯了个错，错误的读取修复会在数据库上引入不可以逆的损坏。
所以牺牲可用性是有问题的，最终一致性太复杂而无法合理地构建应用。然而这里只有两种选项，好像就处于一种左右为难的状态。CAP 定理是一种自然事实，那么可能有什么替代方案吗？
还有一种办法。你无法避免 CAP 定理，但是你能隔离它的复杂性，阻止它损害你构建合理系统的能力。CAP 定理引起的复杂性问题是我们如何构建数据系统的基础性问题的一个症状。两个问题特别突出：使用数据库中的可变状态和使用增量算法去更新那个状态。这些问题和 CAP 定理交互作用引起了复杂性。
这篇文章中我会展示一个系统的设计来打败 CAP 定理，它阻止了 CAP 定理通常会引起的复杂性。但我不会止步于此。CAP 定理是一个关于数据系统对机器故障的容错程度的结果。但是有一种形式的容错比机器容错更重要：人为容错。如果关于软件开发有什么确定性的东西，那就是开发人员的不完美，bugs 将不可避免地进入生产环境。我们的数据系统必须对写入糟糕数据的带漏洞的程序具有弹性，我准备展示的系统将尽可能地具有人类容错能力。
这篇文章将会挑战你关于数据系统是如何构建地基本假设。但是通过打破我们当前的思考方式，重新想象数据系统应该如何构建，将会出现一个比你之前想过的更优雅，可扩展和健壮的架构。
什么是数据系统
在我们谈论系统设计之前，我们先定义下我们要解决的问题。数据系统的目的是什么？什么是数据？除非我们能用一个清晰的封装每个数据应用的定义来回答这些问题，否则我们甚至无法开始研究 CAP 定理。
数据应用范围从存储和检索对象，关联，聚合，流处理，连续计算，机器学习等等。目前尚不清楚数据系统是否有如此简单的定义 – 我们对数据所做的事情的范围似乎过于多样化，无法用一个单一的定义来捕捉。
但是，这有一个如此简单的定义：
\[Query = Function(All Data)\]就这样。这个等式概括了数据库和数据系统的所有领域。该领域的一切，过去 50 年的 RDBMS，索引，OLAP，OLTP，MapReduce，ETL，分布式文件系统，流处理器，NoSQL 等等都被这个等式以这样或那样的方式概括了。
一个数据系统回答关于数据集的问题。这些问题被称为“queries”。这个等式描述了一个查询仅仅是你所拥有的所有数据的一个函数。
这个等式似乎太笼统而没有帮助。它似乎没有捕捉到数据系统设计的任何复杂性。但重要的是每个数据系统都会落入这个等式中。这个等式是我们能探索数据系统的起点，它也最终会导出一个打败 CAP 定理的方法。
这个等式中有两个概念：“数据”和“查询”。这些是数据库领域经常混为一谈的概念，所以让我们严格了解这些概念的含义。
数据
让我们从“数据”开始。一份数据是一个不可分割的单位，你认为它是真实的，除了它的存在之外没有其他原因。这就像数学中的一个公理。
关于数据有两个重要的属性。首先，数据本质上是基于时间的。一份数据是你知道在某个时刻是真实的事实。例如，假设 Sally 在社交网络的个人资料中输入她住在芝加哥的。你从该输入中获取的数据是，在她将该信息输入到她的个人资料中的特定时刻，她住在芝加哥。假设 Sally 稍后将她的个人资料位置更新为亚特兰大。然后你知道她在那个特定时间住在亚特兰大。她现在住在亚特兰大的事实并没有改变她曾经住在芝加哥的事实。两条数据都是真实的。
数据的第二个属性紧随其后：数据本质上是不可变的。由于它与时间点的联系，一条数据的真实性永远不会改变。人们无法及时回溯来改变一条数据的真实性。这意味着你只能对数据执行两个主要操作：读取现有数据和添加更多数据。CRUD 变成了 CR。
我省略了“更新”操作。这是因为更新对不可变数据没有意义。例如，“更新” Sally 的位置实际上意味着你正在添加一条新数据，表明她最近住在一个新位置。
我也省略了“删除”操作。同样，大多数删除情况更好地表示为创建新数据。例如，如果 Bob 停止在 Twitter 上关注 Mary，这并不会改变他过去关注她的事实。因此，与其删除表明他关注她的数据，不如添加一条新的数据记录，表明他在某个时刻取消关注她。
在某些情况下，你确实希望永久删除数据，例如要求你在一定时间后清除数据的法规。我将要展示的数据系统设计很容易支持这些案例，因此为了简单起见，我们可以忽略这些案例。
这种数据定义几乎肯定与你习惯的不同，尤其是如果你来自以更新为常态的关系数据库世界。有两个原因。首先，这个数据的定义是非常通用的：很难想出一种不符合这个定义的数据。其次，数据的不变性是我们将在设计一个超越 CAP 定理的人类容错数据系统时要利用的关键属性。
查询
等式中的第二个概念是“查询”。查询是对一组数据的派生。从这个意义上说，查询就像数学中的定理。例如，“莎莉的当前位置是什么？” 是一个查询。你将通过返回有关 Sally 位置的最新数据记录来计算此查询。查询是完整数据集的函数，因此它们可以做任何事情：聚合、连接不同类型的数据等等。因此，你可以查询服务的女性用户数量，或者你可以查询推文数据集以了解过去几个小时内的热门话题。
我已将查询定义为完整数据集上的函数。当然，许多查询不需要运行完整的数据集，它们只需要数据集的一个子集。但重要的是我的定义封装了所有可能的查询，如果我们要击败 CAP 定理，我们必须能够对任何查询这样做。
打败 CAP 定理
计算查询的最简单方法是在完整数据集上运行函数。如果你能在你的延迟限制内做到这一点，那么你就完成了。没有其他东西可以建造。
当然，期望一个完整数据集上的函数快速完成是不可行的。许多查询，例如服务于网站的查询，需要毫秒级的响应时间。但是，让我们假设你可以快速计算这些函数，让我们看看像这样的系统如何与 CAP 定理相互作用。正如你将要看到的，这样的系统不仅击败了 CAP 定理，而且还消灭了它。
CAP 定理仍然适用，因此你需要在一致性和可用性之间做出选择。美妙之处在于，一旦你决定了你想要做出的权衡，你就完成了。通过使用不可变数据和从头开始计算查询，可以避免 CAP 定理通常导致的复杂性。
如果你选择一致性而不是可用性，那么与以前相比没有太大变化。有时你将无法读取或写入数据，因为你牺牲了可用性。但是对于需要严格一致性的情况，这是一种选择。
当你选择可用性而不是一致性时，事情会变得更加有趣。在这种情况下，系统最终是一致的，没有任何最终一致性的复杂性。由于系统高度可用，你始终可以编写新数据和计算查询。在失败的情况下，查询将返回不包含以前写入的数据的结果。最终，这些数据将是一致的，并且查询会将这些数据合并到他们的计算中。
关键是数据是不可变的。不可变数据意味着没有更新之类的东西，因此一条数据的不同副本不可能变得不一致。这意味着没有分歧值、矢量时钟或读取修复。从查询的角度来看，一条数据要么存在，要么不存在。该数据上只有数据和功能。你无需执行任何操作来强制执行最终一致性，并且最终一致性不会妨碍对系统进行推理。
之前导致复杂性的原因是增量更新和 CAP 定理之间的相互作用。增量更新和 CAP 定理真的不能很好地结合在一起； 可变值需要在最终一致的系统中进行读取修复。通过拒绝增量更新、接受不可变数据以及每次从头开始计算查询，你可以避免这种复杂性。CAP 定理被打败了。
当然，我们刚刚经历的是一个思想实验。尽管我们希望每次都能从头开始计算查询，但这是不可行的。但是，我们已经了解了真正解决方案的一些关键属性：
- 该系统使存储和扩展不可变的、不断增长的数据集变得容易；
- 主要的写入操作是添加新的不可变数据事实；
- 该系统通过从原始数据重新计算查询来避免 CAP 定理的复杂性；
- 系统使用增量算法将查询延迟降低到可接受的水平；
让我们开始探索这样一个系统的样子。请注意，从这里开始的一切都是优化。数据库、索引、ETL、批处理计算、流处理——这些都是优化查询功能并将延迟降低到可接受水平的技术。这是一个简单而深刻的认识。数据库通常被认为是数据管理的核心，但实际上它们是更大图景的一部分。
批量计算
弄清楚如何在任意数据集上快速运行任意函数是一个令人生畏的问题。所以让我们稍微放松一下这个问题。让我们假设查询过时几个小时是可以的。以这种方式放宽问题会导致构建数据系统的简单、优雅和通用的解决方案。之后，我们将扩展解决方案，使问题不再放松。
由于查询是所有数据的函数，因此使查询快速运行的最简单方法是预先计算它们。每当有新数据时，你只需重新计算所有内容。这是可行的，因为我们放宽了问题以允许查询过时几个小时。这是此工作流程的说明：
要构建它，你需要一个系统：
- 可以轻松存储大型且不断增长的数据集
- 可以以可扩展的方式计算该数据集上的函数
存在这样的系统。它已经成熟，经过数百个组织的实战考验，并且拥有庞大的工具生态系统。它被称为 Hadoop。Hadoop 并不完美，但它是进行批处理的最佳工具。
很多人会告诉你，Hadoop 只适用于“非结构化”数据。这是完全错误的。Hadoop 非常适合结构化数据。使用 Thrift 或 Protocol Buffers 等工具，你可以使用丰富的、可演化的模式来存储数据。
Hadoop 由两部分组成：分布式文件系统 (HDFS) 和批处理框架 (MapReduce)。HDFS 擅长以可扩展的方式跨文件存储大量数据。MapReduce 擅长以可扩展的方式对该数据运行计算。这些系统完全符合我们的需求。
我们将数据存储在 HDFS 上的平面文件中。一个文件将包含一系列数据记录。要添加新数据，你只需将包含新数据记录的新文件附加到包含所有数据的文件夹中。在 HDFS 上存储这样的数据可以解决“存储大量且不断增长的数据集”的需求。
从该数据中预计算查询同样简单。MapReduce 是一个足够有表现力的范例，几乎任何功能都可以作为一系列 MapReduce 作业来实现。工具 Cascalog、Cascading 和 Pig 使实现这些功能变得更加容易。
最后，你需要索引预计算的结果，以便应用程序可以快速访问结果。有一类数据库非常擅长这一点。ElephantDB 和 Voldemort read-only 专门用于从 Hadoop 导出键/值数据以进行快速查询。这些数据库支持批量写入和随机读取，不支持随机写入。随机写入导致数据库的大部分复杂性，因此由于不支持随机写入，这些数据库非常简单。例如，ElephantDB 只有几千行代码。这种简单性导致这些数据库非常健壮。
让我们看一个批处理系统如何组合在一起的示例。假设你正在构建一个跟踪页面浏览量的 Web 分析应用程序，并且你希望能够查询任何时间段内的页面浏览量，粒度为一小时。
实现这一点很容易。每个数据记录都包含一次页面访问。这些数据记录存储在 HDFS 上的文件中。按小时汇总每个 URL 的页面浏览量的功能被实现为一系列 MapReduce 作业。该函数发出键/值对，其中每个键是一个 [URL, hour] 键值对，每个值都是页面浏览次数的计数。这些键值对被导出到 ElephantDB 数据库中，以便应用程序可以快速获取任何值 [URL, hour]。当应用程序想知道某个时间范围内的页面浏览量时，它会向 ElephantDB 查询该时间范围内每小时的页面浏览量，并将它们相加得到最终结果。
批处理可以在任意数据上计算任意函数，但缺点是查询会过时几个小时。这种系统的“任意性”意味着它可以应用于任何问题。更重要的是，它简单、易于理解且完全可扩展。你只需考虑数据和功能，Hadoop 负责并行化。
批处理系统、CAP 和人为容错
到目前为止，一切都很好。那么我描述的批处理系统如何与 CAP 保持一致，它是否符合我们人类容错的目标？
让我们从 CAP 开始。批处理系统最终以最极端的方式保持一致：写入总是需要几个小时才能合并到查询中。但这是一种很容易推理的最终一致性形式，因为你只需要考虑数据和该数据上的函数。无需考虑读取修复、并发性或其他复杂问题。
接下来，我们来看看批处理系统的人为容错能力。批处理系统的人为容错能力已尽善尽美。在这样的系统中，人类只会犯两个错误：部署有缺陷的查询实现或写入错误数据。
如果你部署一个有缺陷的查询实现，你所要做的就是修复错误、部署固定版本并从主数据集中重新计算所有内容。这是有效的，因为查询是纯函数。
同样，写入坏数据有一条清晰的恢复路径：删除坏数据并再次预先计算查询。由于数据是不可变的并且主数据集是仅追加的，因此写入不良数据不会覆盖或以其他方式破坏良好数据。这与几乎所有传统数据库形成鲜明对比，在传统数据库中，如果你更新密钥，则会丢失旧值。
请注意，MVCC 和类似 HBase 的行版本控制并不接近这种人为容错水平。MVCC 和 HBase 行版本控制不会永远保留数据：一旦数据库压缩行，旧值就消失了。只有不可变的数据集才能保证你在写入错误数据时有恢复路径。
实时层
信不信由你，批处理解决方案几乎解决了对任意数据实时计算任意函数的完整问题。任何早于几个小时的数据都已合并到批处理视图中，因此剩下要做的就是补偿最后几个小时的数据。弄清楚如何对几个小时的数据进行实时查询比对完整数据集进行查询要容易得多。这是一个批判性的见解。
为了弥补这几个小时的数据，你需要一个与批处理系统并行运行的实时系统。实时系统预先计算最后几个小时数据的每个查询函数。要解析查询函数，你查询批处理视图和实时视图并将结果合并在一起以获得最终答案。
实时层是你使用 Riak 或 Cassandra 等读/写数据库的地方，而实时层依赖于增量算法来更新这些数据库中的状态。
用于实时计算的 Hadoop 类似物是 Storm 。我编写 Storm 是为了让以可扩展和健壮的方式轻松进行大量实时数据处理。Storm 在数据流上运行无限计算，并为数据处理提供强有力的保证。
让我们通过返回查询某个时间范围内 URL 的页面浏览量的运行示例来查看实时层的示例。
批处理系统和以前一样：基于 Hadoop 和 ElephantDB 的批处理工作流预先计算除最后几个小时数据之外的所有内容的查询。剩下的就是构建实时系统来补偿最后几个小时的数据。
我们将过去几个小时的统计数据汇总到 Cassandra，我们将使用 Storm 来处理页面浏览流并将更新并行化到数据库中。每个网页浏览都会导致一个计数器 [URL, hour] 在 Cassandra 中递增的键。就是这样 – Storm 让这些事情变得非常简单。
批处理层 + 实时层、CAP 定理和人为容错
在某些方面，我们似乎回到了开始的地方。实现实时查询需要我们使用 NoSQL 数据库和增量算法。这意味着我们又回到了不同值、矢量时钟和读取修复的复杂世界。
不过有一个关键的区别。由于实时层仅补偿最后几个小时的数据，因此实时层计算的所有内容最终都会被批处理层覆盖。因此，如果你在实时层中犯了错误或出现问题，批处理层会纠正它。所有这些复杂性都是短暂的。
这并不意味着你不应该关心实时层中的读取修复或最终一致性。你仍然希望实时层尽可能一致。但是，当你犯了错误时，你不会永久损坏你的数据。这消除了你肩上巨大的复杂性负担。
在批处理层中，你只需要考虑该数据的数据和函数。批处理层的推理非常简单。另一方面，在实时层中，你必须使用增量算法和极其复杂的 NoSQL 数据库。将所有这些复杂性隔离到实时层中，对于构建健壮、可靠的系统会产生巨大的影响。
此外，实时层不会影响系统的人为容错能力。批处理层中的 append-only 不可变数据集仍然是系统的核心，因此任何错误都可以像以前一样恢复。
让我分享一个关于在实时层中隔离复杂性的巨大好处的个人故事。我有一个非常像我在这里描述的系统：批处理层的 Hadoop 和 ElephantDB，实时层的 Storm 和 Cassandra。由于我的监控不善，有一天我醒来发现 Cassandra 已经用完了空间并且每次请求都超时。这导致我的 Storm 拓扑失败并且数据流备份到队列中。相同的消息不断被重播（并且不断失败）。
如果我没有批处理层，我将被迫扩展和恢复 Cassandra。这是不平凡的。更糟糕的是，由于多次重播相同的消息，许多数据库可能不准确。
幸运的是，所有这些复杂性都在我的实时层中被隔离了。我将备份的队列刷新到批处理层并创建了一个新的 Cassandra 集群。批处理层像发条一样运行，在几个小时内一切恢复正常。没有数据丢失，我们的查询也没有错误。
垃圾收集
我在这篇文章中描述的一切都是建立在一个不可变的、不断增长的数据集的基础上的。那么，如果你的数据集非常大，以至于无法始终存储所有数据，即使使用水平可扩展的存储，你会怎么做？ 这个用例会破坏我所描述的一切吗？ 你应该回到使用可变数据库吗？
不，很容易用“垃圾收集”扩展基本模型来处理这个用例。垃圾收集只是一个函数，它接收主数据集并返回主数据集的过滤版本。垃圾收集摆脱了低价值的数据。你可以使用任何你想要的垃圾收集策略。你可以通过仅保留实体的最后一个值来模拟可变性，或者你可以保留每个实体的历史记录。例如，如果你正在处理位置数据，你可能希望每人每年保留一个位置以及当前位置。可变性实际上只是垃圾收集的一种不灵活的形式（它也与 CAP 定理交互不佳）。
垃圾收集是作为批处理任务实现的。这是你偶尔运行的东西，也许每月一次。由于垃圾收集作为离线批处理任务运行，它不会影响系统如何与 CAP 定理交互。
结论
使可扩展数据系统变得困难的不是 CAP 定理。这是对增量算法和可变状态的依赖，导致我们的系统变得复杂。直到最近随着分布式数据库的兴起，这种复杂性才失控。但这种复杂性一直存在。
我在这篇文章的开头说过，我会挑战你关于如何构建数据系统的基本假设。我将 CRUD 变成了 CR，将持久性拆分为单独的批处理和实时系统，并且痴迷于人类容错的重要性。多年来，我花了很多来之不易的经验来打破我的旧假设并得出这些结论。
批处理/实时架构有很多我还没有涉及的有趣功能。现在值得总结其中的一些：
- 算法灵活性：一些算法难以增量计算。例如，如果唯一性集变大，计算唯一性计数可能会具有挑战性。批处理/实时拆分使你可以灵活地在批处理层上使用精确算法，在实时层上使用近似算法。批处理层不断覆盖实时层，因此近似值得到纠正，你的系统表现出“最终准确性”的属性。
- 模式迁移很容易：模式迁移困难的日子已经一去不复返了。由于批量计算是系统的核心，因此很容易在完整的数据集上运行函数。这使得更改数据或视图的架构变得容易。
- 轻松的临时分析：批处理层的任意性意味着你可以对数据运行任何你喜欢的查询。由于所有数据都可以在一个位置访问，因此这很容易和方便。
- 自审核：通过将数据视为不可变的，你可以获得自审核数据集。数据集记录了它自己的历史。我已经讨论过这对于人类容错有多么重要，但它对于进行分析也非常有用。
我并没有声称已经“解决”了大数据领域，但我已经制定了思考大数据的框架。批处理/实时架构高度通用，可以应用于任何数据系统。我没有给你一条鱼或一根钓鱼竿，而是向你展示了如何为任何种类的鱼和任何种类的水制作钓鱼竿。
要提高我们应对大数据问题的集体能力，还有很多工作要做。以下是一些关键的改进领域：
- 可批量写入、随机读取数据库的扩展数据模型： 并非每个应用程序都支持键/值数据模型。这就是为什么我的团队正在投资扩展 ElephantDB 以支持搜索、文档数据库、范围查询等。
- 更好的批处理原语：Hadoop 并不是批处理计算的全部。对于某些类型的计算，它可能效率低下。Spark 是一个重要的项目，在扩展 MapReduce 范式方面做着有趣的工作。
- 改进的读/写 NoSQL 数据库：有更多具有不同数据模型的数据库的空间，这些项目通常会受益于更加成熟。
- 高级抽象：未来工作最有趣的领域之一是映射到批处理组件和实时处理组件的高级抽象。没有理由不具备声明式语言的简洁性和批处理/实时架构的稳健性。
很多人想要一个可扩展的关系数据库。我希望你在这篇文章中意识到你根本不想要那个！大数据和 NoSQL 运动似乎使数据管理比使用 RDBMS 更复杂，但这仅仅是因为我们试图以与使用 RDBMS 处理数据相同的方式处理“大数据”：通过将数据和视图合并并依赖关于增量算法。大数据的规模让你能够以完全不同的方式构建系统。通过将数据存储为一组不断扩展的不可变事实并将重新计算构建到核心中，大数据系统实际上比关系系统更容易推理。它可以扩展。