“打败”CAP定理

“打败”CAP定理

标签：网站建设 网站制作 成都网站制作  CAP定理

       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定理带来的问题，都可以通过不可改变的数据和从原始数据中计算查询来规避。

如果你选择一致性而不是可用性，那么跟以前并没有多大的区别，因为你放弃了可用性，所以一些时候你将无法读取或者写入数据。当然这只是针对对强一致性有要求的系统。

如果你选择可用性而不是一致性，在这种情况下，系统可以达到最终一致性而且规避了所有最终一致性带来的复杂问题。由于系统总是可用的，所以你总可以写入新数据或者进行查询。在出错情况下，查询可能返回的不是最近写入的数据，但根据最终一致性，这个数据最终会一致，而查询函数最终会把这个数据计算进去。

这里的关键在于数据是不可变的。不可变数据意味着这里没有更新操作，所以不可能出现数据复制不同这种不一致的情况，也意味着不需要版本化的数据、矢量时钟或者读取修复。在一个查询场景中，一个数据只有存在或者不存在两种情况。这里只有数据和在数据之上的函数。这里没有需要你为确保最终一致性额外做的事情，最终一致性也不会因此使你的系统变得复杂。

之前的复杂度主要来自增量更新操作和CAP定理之间的矛盾，在最终一致性系统中可变的值需要通过读取修复来保证最终一致性。通过使用不可变数据，去掉增量更新，使用不可变数据，每次从原始数据计算查询，你可以规避那些复杂的问题。CAP定理就被打败了。

当然，现在讲的只不过是想法而已，而且每次从原始数据计算查询基本上不可能。但我们从中可以学到一些在实际解决方案中的关键点。

数据系统因为不可变数据和不断增长的数据集变得简单了。 基本的写入操作就是写入一条新的不可变数据。 数据系统通过重新从原始数据计算查询规避了CAP定理带来的复杂度。 数据系统利用增量算法使得查询的返回延迟降低到一个可以接受的程度。

让我们开始探索这个数据系统应该如何设计。请注意从这里开始我们所描述都是针对系统优化、数据库、索引、EFL、批量计算、流处理——这些技术都是对查询函数的优化，让查询返回时间降低到一个可以接受的程度。这很简单，但也是数据系统所面对的现实。数据库通常是数据管理的核心，但它们是更大蓝图中的一部分。

批量计算

“如何让任意一个函数可以在任意一个数据集上快速执行完成”这个问题太过于复杂，所以我们先放宽了一下这个问题依赖条件。首先假设，可以允许数据滞后几小时。放宽这个条件之后，我们可以得到一个简单、优雅、通用的数据系统构建解决方案。之后，我们会通过扩展这个解决方案使得它可以不用放宽条件来解决问题。

由于查询是所有数据的一个函数，让查询变快的最简单的方法就是预先计算好这些查询。只要这里有新的数据，你就重新计算这些查询。这是可能的，因为我们放宽了条件使得我们的数据可以滞后几个小时。图1展示了这个工作流程。

文章标题：“打败”CAP定理
当前URL：/news33/184733.html

成都网站建设公司_创新互联，为您提供外贸网站建设、面包屑导航、网站内链、电子商务、响应式网站、手机网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联