谈谈从CAP定理到Lambda架构的演化

时间:2022-12-14 22:06:28

  CAP 定理指出数据库不能同时保证一致性、可用性和分区容错性。但是我们不能牺牲分区容错性,因此必须在可用性和一致性之间做出权衡。管理这种权衡是 NoSQL 运行的核心焦点。

  一致性意味着在成功写入之后,以后的读取将始终考虑该写入。可用性意味着可以随时读取和写入系统。在分区期间,只能拥有这些属性之一。

  选择一致性而不是可用性的系统必须处理一些棘手的问题。当数据库不可用时怎么做?可以尝试缓冲写入以备后用,但是如果丢失了带有缓冲区的机器,就有丢失这些写入的风险。此外,缓冲写入可能是一种不一致的形式,因为客户端认为写入已成功但写入尚未在数据库中。或者,可以在数据库不可用时将错误返回给客户端。但是,如果曾经使用过一种告诉“稍后再试”的产品,就会知道这会是多么令人恼火。

  另一种选择是选择可用性而不是一致性。这些系统所能提供的最好的一致性保证就是“最终一致性”。如果使用最终一致的数据库,那么有时会读取到与刚刚写入的结果不同的结果。有时多个访问者同时读取同一个密钥会得到不同的结果。更新可能不会传递到一个值的所有副本,因此最终会得到一些副本获得一些更新而其他副本获得不同的更新。一旦检测到值出现差异,就可以修复该值。这需要使用矢量时钟追溯历史并将更新合并在一起,称为“读取修复”。

  在应用层维护最终一致性对开发人员来说负担太重。读取修复代码极易受到开发人员错误的影响;如果犯了错误,错误的读取修复将给数据库带来不可逆转的损坏。因此牺牲可用性是有问题的,最终一致性太复杂以至于无法合理地构建应用程序。然而,这是唯一的两个选择, CAP 定理是自然界的事实,那么还有什么替代方案呢?还有另一种方法。你无法避免 CAP 定理,但你可以隔离它的复杂性并防止它破坏你对系统进行推理的能力。CAP 定理引起的复杂性是我们如何构建数据系统的基本问题。有两个问题特别突出:在数据库中使用可变状态以及使用增量算法来更新该状态。正是这些问题与 CAP 定理之间的相互作用导致了复杂性。

  在这篇文章中将展示一个系统的设计,该系统通过防止 CAP 定理通常引起的复杂性来突破它。CAP 定理是关于数据系统对机器故障的容错程度的结果。然而,有一种比机器容错更重要的容错形式:人为容错。如果软件开发有任何确定性,那就是开发人员并不完美,错误将不可避免地影响生产。我们的数据系统必须对写入错误数据的错误程序具有弹性,而下面将要展示的系统具有尽可能多的人为容错能力。

  这篇文章将挑战对如何构建数据系统的基本假设。但是,通过打破我们当前的思维方式并重新想象应该如何构建数据系统,出现的是一种比想象的更好的、可扩展和健壮的架构。

   什么是数据系统

  在我们谈论系统设计之前,让我们首先定义我们试图解决的问题。数据系统的目的是什么?什么是数据?除非我们可以用清楚地封装每个数据应用程序的定义来回答这些问题,否则我们甚至不需要接近 CAP 定理。

  数据应用范围从存储和检索对象、连接、聚合、流处理、连续计算、机器学习等等。目前尚不清楚是否存在如此简单的数据系统定义——似乎我们对数据所做的事情范围太广,无法用单一定义来概括。

  但是,有这么一个简单的定义。就是这个:

  Query = Function(All Data)

  而已。这个等式总结了数据库和数据系统的整个领域。该领域的一切——过去 50 年的 RDBMS、索引、OLAP、OLTP、MapReduce、ETL、分布式文件系统、流处理器、NoSQL 等——都以这种或那种方式总结为该等式。

  数据系统回答有关数据集的问题。这些问题称为“查询”。这个等式表明查询只是拥有的所有数据的函数。

  这个等式可能看起来过于笼统而无用。它似乎没有捕捉到数据系统设计的任何复杂性。但重要的是每个数据系统都属于这个等式。该等式是我们探索数据系统的起点,该等式最终将导致一种突破 CAP 定理的方法。

  这个等式中有两个概念:“数据”和“查询”。这些是在数据库领域中经常混淆的不同概念,因此让我们严格了解这些概念的含义。

   数据

  让我们从“数据”开始。一条数据是一个不可分割的单元,你认为它是真实的,除了它存在之外没有其他原因。它就像数学中的公理。

  关于数据,有两个重要的属性需要注意。首先,数据本质上是基于时间的。一条数据是知道在某个时刻是真实的事实。例如,假设张梓涵在她的社交网络资料中输入她住在北京。从该输入中获取的数据是,截至她将该信息输入她的个人资料的特定时刻,她住在北京。假设张梓涵稍后将她的个人资料位置更新为上海。然后你知道她在那段时间住在上海。她现在住在上海的事实并没有改变她曾经住在北京的事实。这两个数据都是真实的。

  数据的第二个属性紧随第一个属性:数据本质上是不可变的。由于它与时间点的联系,一条数据的真实性永远不会改变。人们无法回到过去来改变数据的真实性。这意味着只能对数据执行两个主要操作:读取现有数据和添加更多数据。CRUD变成了 CR。我省略了“更新”操作。这是因为更新对不可变数据没有意义。例如,“更新”张梓涵的位置实际上意味着正在添加一条新数据,表明她最近住在一个新位置。我也省略了“删除”操作。同样,大多数删除情况更好地表示为创建新数据。例如,如果张三停止在微博上关注李四,这不会改变他曾经关注过她的事实。因此,与其删除表示他关注她的数据,不如添加一条新的数据记录,说明他在某个时刻取消了对她的关注。

  在某些情况下,确实希望永久删除数据,例如要求在一定时间后清除数据的法规。将要展示的数据系统设计很容易支持这些情况,因此为了简单起见,我们可以忽略这些情况。

  这种数据定义几乎肯定与习惯的不同,特别是如果来自以更新为常态的关系数据库世界。有两个原因。首先,这个数据定义非常通用:很难想出一种数据不符合这个定义。其次,数据的不变性是我们在设计一个战胜 CAP 定理的人类容错数据系统时要利用的关键属性。

   查询

  等式中的第二个概念是“查询”。查询是一组数据的推导。从这个意义上说,查询就像数学中的定理。例如,“张梓涵目前的位置是什么?” 是一个查询。可以通过返回有关张梓涵 位置的最新数据记录来计算此查询。查询是完整数据集的函数,因此它们可以做任何事情:聚合、将不同类型的数据连接在一起等等。因此,可能会查询服务的女性用户数量,或者可能会查询推文数据集,了解过去几个小时的热门话题。

  我们已将查询定义为完整数据集上的函数。当然,许多查询不需要运行完整的数据集——它们只需要数据集的一个子集。但重要的是我们的定义封装了所有可能的查询,如果我们要突破 CAP 定理,我们必须能够对任何查询做到这一点。

  突破 CAP 定理

  计算查询的最简单方法是在完整数据集上逐字运行函数。如果可以在延迟限制内执行此操作,那么就完成了。没有别的东西可以建造了。

  当然,期望一个函数在一个完整的数据集上快速完成是不可行的。许多查询,例如为网站提供服务的查询,需要毫秒级的响应时间。但是,让我们假设可以快速计算这些函数,让我们看看这样的系统如何与 CAP 定理交互。正如即将看到的,像这样的系统不仅突破了 CAP 定理,而且还消灭了它。

  CAP 定理仍然适用,因此需要在一致性和可用性之间做出选择。关键之处在于,一旦决定了要做出的权衡,就完成了。通过使用不可变数据和从头开始计算查询,避免了 CAP 定理通常导致的复杂性。

  如果选择一致性而不是可用性,那么与以前相比不会有太大变化。有时将无法读取或写入数据,因为牺牲了可用性。但对于需要严格一致性的情况,这是一种选择。

  当选择可用性而不是一致性时,事情会变得更加有趣。在这种情况下,系统是最终一致的,没有任何最终一致性的复杂性。由于系统具有高可用性,可以随时编写新数据和计算查询。在失败的情况下,查询将返回不包含以前写入的数据的结果。最终,这些数据将是一致的,并且查询会将这些数据合并到它们的计算中。

  关键是数据是不可变的。不可变数据意味着没有更新这样的东西,因此一条数据的不同副本不可能变得不一致。这意味着没有不同的值、矢量时钟或读取修复。从查询的角度来看,一条数据要么存在,要么不存在。该数据上只有数据和功能。无需执行任何操作来强制执行最终一致性,并且最终一致性不会妨碍对系统进行推理。

  之前导致复杂的是增量更新和CAP定理的交互。增量更新和 CAP 定理真的不能很好地结合在一起;可变值需要在最终一致的系统中进行读取修复。通过拒绝增量更新、接受不可变数据以及每次都从头开始计算查询,可以避免这种复杂性。CAP 定理已被突破。

  当然,我们刚刚经历的是一个思想实验。虽然我们希望每次都能从头开始计算查询,但这是不可行的。然而,我们已经了解了真实解决方案的一些关键属性:

  1.该系统使存储和扩展不可变、不断增长的数据集变得容易

  2.主要的写操作是添加新的不可变数据事实

  3.系统通过从原始数据重新计算查询来避免 CAP 定理的复杂性

  4.系统使用增量算法将查询延迟降低到可接受的水平

  让我们开始探索这样一个系统是什么样的。请注意,从这里开始的一切都是优化。数据库、索引、ETL、批处理计算、流处理——这些都是优化查询功能并将延迟降低到可接受水平的技术。这是一个简单而深刻的认识。数据库通常被认为是数据管理的核心,但实际上它们是更大范围的一部分。

   批量计算

  弄清楚如何在任意数据集上快速运行任意函数是一个令人生畏的问题。所以让我们稍微放松一下这个问题。让我们假设查询过时几个小时是可以的。以这种方式放松问题会导致构建数据系统的简单、优雅和通用的解决方案。之后,我们将扩展解决方案,使问题不再宽松。

  由于查询是所有数据的函数,因此使查询快速运行的最简单方法是预先计算它们。每当有新数据时,只需重新计算所有内容。这是可行的,因为我们放宽了问题,允许查询过时几个小时。这是此工作流程的示例:  

谈谈从CAP定理到Lambda架构的演化

  要构建它,需要一个系统:

  1.可以轻松存储庞大且不断增长的数据集

  2.可以以可扩展的方式计算该数据集上的函数

  这样的系统是存在的。它成熟,经过数百个组织的实战测试,并且拥有庞大的工具生态系统。它叫做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 分析应用程序,并且希望能够查询任何时间段内的页面浏览量,精确到一小时。  

谈谈从CAP定理到Lambda架构的演化

  实现这个很容易。每个数据记录都包含一个页面视图。这些数据记录存储在 HDFS 上的文件中。按小时汇总每个 URL 的页面浏览量的功能是作为一系列 MapReduce 作业实现的。该函数发出键/值对,其中每个键都是一[URL, hour]对,每个值都是页面浏览量的计数。这些键/值对被导出到 ElephantDB 数据库中,以便应用程序可以快速获取任何[URL, hour]对的值。当应用程序想知道某个时间范围内的页面浏览量时,它会向 ElephantDB 查询该时间范围内每小时的页面浏览量,并将它们相加得到最终结果。

  批处理可以计算任意数据上的任意函数,缺点是查询会过时几个小时。这种系统的“任意性”意味着它可以应用于任何问题。更重要的是,它简单、易于理解并且完全可扩展。只需要从数据和功能的角度考虑,Hadoop 负责并行化。

  批处理系统、CAP 和人为容错

  那么批处理系统如何与 CAP 保持一致,它是否满足我们的人类容错目标?

  让我们从 CAP 开始。批处理系统以最极端的方式实现最终一致性:写入总是需要几个小时才能合并到查询中。但这是一种易于推理的最终一致性形式,因为只需考虑数据和数据上的函数。无需考虑读取修复、并发或其他复杂问题。

  接下来,我们来看看批处理系统的人为容错能力。批处理系统的人为容错能力是你能得到的最好的。在这样的系统中,人类只会犯两个错误:部署有缺陷的查询实现或写入错误数据。

  如果你部署了一个有问题的查询实现,你要做的就是修复这个问题,部署修复后的版本,然后从主数据集中重新计算所有内容。这是可行的,因为查询是纯函数。

  同样,写入坏数据有一条清晰的恢复路径:删除坏数据并再次预计算查询。由于数据是不可变的并且主数据集是仅附加的,因此写入错误数据不会覆盖或以其他方式破坏良好数据。这与几乎所有传统数据库形成鲜明对比,在传统数据库中,如果更新密钥,就会丢失旧值。

  请注意,MVCC和类似 HBase 的行版本控制并没有接近这种水平的人为容错。MVCC 和 HBase 行版本控制不会永远保留数据:一旦数据库压缩行,旧值就消失了。只有不可变的数据集才能保证在写入错误数据时有恢复路径。

  实时层

  批处理解决方案几乎解决了实时计算任意数据的任意函数的完整问题。任何早于几个小时的数据都已合并到批处理视图中,因此剩下要做的就是补偿最后几个小时的数据。弄清楚如何对几个小时的数据进行实时查询比对完整数据集进行实时查询要容易得多。这是一个重要的见解。

  为了补偿那几个小时的数据,需要一个与批处理系统并行运行的实时系统。实时系统针对最近几个小时的数据预先计算每个查询函数。要解决查询功能,查询批处理视图和实时视图并将结果合并在一起以获得最终答案。  

谈谈从CAP定理到Lambda架构的演化

  实时层是使用读/写数据库(如 Riak 或 Cassandra)的地方,实时层依赖于增量算法来更新这些数据库中的状态。

  用于实时计算的 Hadoop 模拟是Storm。Storm 是为了以一种可扩展且健壮的方式进行大量实时数据处理。Storm 对数据流进行无限计算,并为数据处理提供强有力的保证。

  让我们通过返回查询某个时间范围内 URL 的页面浏览量的运行示例来查看实时层的示例。  

谈谈从CAP定理到Lambda架构的演化

  批处理系统与以前相同:基于 Hadoop 和 ElephantDB 的批处理工作流预先计算除最近几个小时数据之外的所有内容的查询。剩下的就是构建实时系统来补偿最后几个小时的数据。

  我们会将过去几个小时的统计数据汇总到 Cassandra 中,我们将使用 Storm 处理页面浏览流并将更新并行化到数据库中。[URL, hour]在 Cassandra 中,每次页面浏览都会导致一个密钥计数器递增。这就是它的全部——Storm 使这些事情变得非常简单。

  批处理层 + 实时层、CAP 定理和人类容错

  在某些方面,我们似乎又回到了起点。实现实时查询需要我们使用 NoSQL 数据库和增量算法。这意味着我们回到了不同值、矢量时钟和读取修复的复杂世界。

  但是有一个关键的区别。由于实时层仅补偿最后几个小时的数据,实时层计算的所有内容最终都会被批处理层覆盖。因此,如果在实时层中犯了错误或出了什么问题,批处理层会纠正它。所有这些复杂性都是短暂的。

  这并不意味着不应该关心实时层中的读取修复或最终一致性。仍然希望实时层尽可能保持一致。但是,当犯错时,不会永久损坏数据。这减轻了巨大的复杂性负担。

  在批处理层,你只需要考虑数据和数据上的函数。批处理层的推理非常简单。另一方面,在实时层,必须使用增量算法和极其复杂的 NoSQL 数据库。将所有这些复杂性隔离到实时层中,对于构建健壮、可靠的系统有很大的不同。

  此外,实时层不会影响系统的人为容错能力。批处理层中的 append-only 不可变数据集仍然是系统的核心,因此任何错误都可以像以前一样从中恢复。

  让我们看一个关于在实时层中隔离复杂性的案例。有一个与这里描述的系统非常相似的系统:用于批处理层的 Hadoop 和 ElephantDB,以及用于实时层的 Storm 和 Cassandra。由于监控不力,有一天发现 Cassandra 空间不足并且每次请求都超时。这导致 Storm 拓扑失败,数据流在队列中备份。相同的消息不断被重播并不断失败。

  如果没有批处理层,将不得不扩展和恢复 Cassandra。这很重要。更糟糕的是,由于多次重播相同的消息,许多数据库可能不准确。

  幸运的是,所有这些复杂性都隔离在实时层中。将备份的队列刷新到批处理层并创建了一个新的 Cassandra 集群。批处理层像发条一样运行,几个小时内一切恢复正常。没有数据丢失,查询也没有不准确之处。

   垃圾收集

  我们描述的一切都建立在一个不变的、不断增长的数据集的基础上。那么,如果的数据集太大以至于无法一直存储所有数据,即使使用水平可扩展存储,会怎么做?这个用例是否破坏了所描述的一切?你应该回去使用可变数据库吗?

  不。很容易用“垃圾收集”扩展基本模型来处理这个用例。垃圾收集只是一个函数,它接受主数据集并返回主数据集的过滤版本。垃圾收集摆脱了低价值的数据。可以使用任何想要的策略来进行垃圾回收。可以通过仅保留实体的最后一个值来模拟可变性,或者可以保留每个实体的历史记录。例如,如果要处理位置数据,可能希望每年为每个人保留一个位置以及当前位置。可变性实际上只是一种不灵活的垃圾收集形式,它与 CAP 定理的交互也很差。

  垃圾收集是作为批处理任务实现的。这是偶尔运行的东西,也许每月一次。由于垃圾收集作为离线批处理任务运行,因此它不会影响系统与 CAP 定理的交互方式。

   小结

  使可伸缩数据系统变得困难的不是 CAP 定理。正是对增量算法和可变状态的依赖导致了我们系统的复杂性。随着分布式数据库的兴起,这种复杂性才开始减弱。但这种复杂性一直存在。

  批处理/实时架构还有许多其他功能。现在值得总结其中的一些:

  算法灵活性:一些算法难以增量计算。例如,如果唯一值集变大,计算唯一值可能会很困难。批处理/实时拆分使可以灵活地在批处理层上使用精确算法,在实时层上使用近似算法。批处理层不断覆盖实时层,因此近似值得到纠正,系统表现出“最终准确性”的特性。

  模式迁移很容易:由于批处理计算是系统的核心,因此很容易在完整的数据集上运行函数。这使得更改数据或视图的模式变得容易。

  轻松的临时分析:批处理层的任意性意味着可以对数据运行任何喜欢的查询。由于所有数据都可以在一个位置访问,因此简单方便。

  自审计:通过将数据视为不可变的,可以获得自审计数据集。数据集记录了它自己的历史。这对于人类容错非常重要,它对于进行分析也非常有用。

  批处理/实时架构具有很高的通用性,可以应用于任何数据系统。要提高我们解决大数据问题的集体能力,还有很多工作要做。以下是一些关键的改进领域:

  批量可写、随机读取数据库的扩展数据模型:并非每个应用程序都受键/值数据模型支持。这就是为什么我的团队正在投资扩展 ElephantDB 以支持搜索、文档数据库、范围查询等。

  更好的批处理原语:Hadoop 不是批处理计算的终极目标。对于某些类型的计算,它可能效率低下。Spark是一个重要的项目,在扩展 MapReduce 范例方面做了有趣的工作。

  改进的读/写 NoSQL 数据库:有更多具有不同数据模型的数据库的空间,这些项目通常会从更成熟的过程中受益。

  高级抽象:未来工作中最有趣的领域之一是映射到批处理组件和实时处理组件的高级抽象。没有理由不让声明性语言的简洁性和批处理/实时架构的健壮性结合起来。

  很多人都想要一个可扩展的关系数据库。大数据和 NoSQL 运动似乎使数据管理比 RDBMS 更复杂,但这只是因为我们试图像对待 RDBMS 数据一样对待“大数据”:通过合并数据和视图并依赖关于增量算法。大数据的规模让能够以完全不同的方式构建系统。通过将数据存储为一组不断扩展的不可变事实并将重新计算构建到核心中,大数据系统实际上比关系系统更容易推理。

  以上便是Lambda 架构的想法,架构如下图所示:  

谈谈从CAP定理到Lambda架构的演化

  它的工作方式是捕获不可变的记录序列并将其并行输入到批处理系统和流处理系统中。实现转换逻辑两次,一次在批处理系统中,一次在流处理系统中。在查询时将两个系统的结果拼接在一起以产生完整的结果。