2013年4月9日
第11卷，第3期

最终一致性现状：局限、扩展与超越

在最终一致性基础设施不提供安全保证的情况下，如何构建应用程序？

Peter Bailis 和 Ali Ghodsi，加州大学伯克利分校

在2000年7月的一次会议主题演讲中，现任谷歌工程副总裁兼加州大学伯克利分校教授的埃里克·布鲁尔公开提出了 CAP（一致性、可用性和分区容错性）定理，这将改变分布式存储系统的架构格局。⁸ 布鲁尔的猜想——基于他在 Inktomi 构建首批互联网搜索引擎基础设施的经验——指出，需要始终在线、高可用性运行的分布式系统，在出现网络分区（切断活动服务器之间通信）的情况下，无法保证连贯、一致的单系统操作的错觉。布鲁尔的猜想被证明具有先见之明：在接下来的十年中，随着大规模互联网服务的持续兴起，分布式系统架构师经常放弃“强”保证，转而支持较弱的模型——其中最引人注目的是最终一致性。

最终一致性提供的保证很少。非正式地讲，它保证，如果没有对给定数据项进行额外的更新，则对该项的所有读取最终将返回相同的值。这是一个特别弱的模型。在任何给定时间，用户都无法排除不一致行为的可能性：系统可以返回任何数据，并且仍然是最终一致的——因为它可能在稍后“收敛”。唯一的保证是，在未来的某个时刻，好事将会发生。然而，尽管表面上缺乏有用的保证，但许多可用的应用程序和盈利的企业都是建立在最终一致性基础设施之上的。这是如何做到的？

本文旨在通过描述最终一致性理论和实践中的几个值得注意的进展来开始回答这个问题，重点关注对在野外部署分布式系统的从业者立即适用的要点。随着生产部署越来越多地采用最终一致性等弱一致性模型，我们已经学习了一些关于如何推理、编程和加强这些弱模型的经验教训。

我们将主要关注三个问题和一些初步答案

最终一致性究竟有多“最终”？ 如果倡导最终一致性的系统架构师的数量可以作为任何指标，那么最终一致性在实践中似乎“足够好”。当它提供如此弱的保证时，这怎么可能呢？新的预测和测量技术使系统架构师能够量化真实世界最终一致性系统的行为。通过测量验证，这些系统在大多数情况下表现出强一致性。

应该如何在最终一致性下编程？ 系统架构师如何应对最终一致性提供的缺乏保证？他们如何在没有强排序保证的情况下进行编程？ 新的研究使系统架构师能够处理不一致性，可以通过系统外部的外部补偿，或者通过将自己限制在完全避免不一致性的数据结构中。

是否可以在不失去最终一致性优势的情况下提供比最终一致性更强的保证？ 除了保证最终一致性和高可用性之外，还可以提供哪些其他保证？最近的结果表明，可以在实现最终一致性优势的同时提供明显更强的保证，包括因果关系和传统数据库系统的几个 ACID（原子性、一致性、隔离性、持久性）属性，同时仍然保持高可用性。

本文并非旨在对围绕最终一致性的文献进行正式综述。相反，它是一个务实的介绍，介绍了一些关于我们对最终一致性系统理解的前沿进展。目标是为理解如何以及为什么最终一致性系统被编程、部署和发展，以及未来的系统走向何方，提供必要的背景知识。

最终一致性：历史和概念

布鲁尔的 CAP 定理指出，在出现部分故障（分区）的情况下，不可能同时实现始终在线的体验（可用性）并确保用户读取分布式数据库的最新写入版本（一致性——已被正式证明，一种称为“线性一致性”的属性¹¹）。⁸ CAP 简洁地总结了数十年的分布式系统设计中固有的权衡（例如，1975 年的 RFC 677¹⁴），并表明在分布式系统中维护 SSI（单系统映像）是有成本的¹⁰。如果分布式系统中的两个进程（或进程组）无法通信（被分区）——无论是由于网络故障还是其中一个组件的故障——那么更新就无法同步传播到所有进程而不会阻塞。在分区下，SSI 系统无法安全地完成更新，因此对部分或全部用户不可用。此外，即使没有分区，选择可用性而不是一致性的系统也享有低延迟的好处：如果服务器在与所有其他服务器分区时可以安全地响应用户的请求，那么即使在能够与其他服务器通信时，它也可以响应用户的请求，而无需联系其他服务器。¹（请注意，你不能“牺牲”分区容错性！¹² 选择是在一致性和可用性之间。）

随着服务越来越多地被复制以提供容错能力（确保服务在单个服务器故障时保持在线）和容量（允许系统随着可变的请求速率进行扩展），架构师必须正面应对这些一致性-可用性和一致性-延迟的权衡。在动态、可分区的互联网中，需要保证低延迟的服务通常必须放宽对数据一致性的期望。

最终一致性作为一种可用的替代方案

鉴于 CAP 不可能性结果，分布式数据库设计者寻求更弱的一致性模型，以实现可用性和高性能。虽然自 1970 年代以来，弱一致性已经以各种形式被研究和部署，¹⁹ 但最终一致性模型已经变得突出，特别是在新兴的、高度可扩展的 NoSQL 存储中。

最终一致性的最早定义之一来自 1988 年的一篇论文，该论文描述了一个类似于今天 Google Docs 等共享文本编辑器的群组通信系统¹⁵：“……对一个副本所做的更改最终会迁移到所有副本。如果所有更新活动停止，经过一段时间后，数据库的所有副本将收敛为逻辑等价：数据库的每个副本将以可预测的顺序包含相同的文件；每个文件的副本将包含相同的字段。”

在最终一致性下，所有服务器最终“收敛”到相同的状态；在未来的某个时刻，服务器彼此之间是无法区分的。然而，这种最终的收敛并不能提供 SSI 语义。首先，“可预测的顺序”不一定对应于在 SSI 下可能出现的执行；最终一致性没有指定最终选择哪个值。其次，在达到收敛之前存在一个未指定的时间窗口，在此期间系统将不提供 SSI 语义，而是提供任意值。正如很快将看到的，这种最终收敛的承诺是一个相当弱的属性。最后，具有 SSI 的系统提供最终一致性——“最终”是立即的——但反之则不然。

为什么最终一致性有用？假设您负责社交网络的数据基础设施，用户发布新的状态更新，这些更新被发送到其关注者的时间线，时间线由单独的列表表示——每个用户一个。由于大规模和频繁的服务器故障，时间线的数据库存储在多台物理服务器上。但是，在两台服务器之间发生分区时，您无法将每个更新传递到所有时间线。你应该怎么办？你应该告诉用户他或她无法发布更新，还是应该等到分区恢复后再提供响应？这两种策略都选择了可用性而非一致性，但代价是用户体验。

相反，如果您将更新传播到可访问的关注者时间线集合，返回给用户，并延迟将更新传递给其他关注者，直到分区恢复怎么办？在选择此选项时，您放弃了所有用户在每个时间点都看到相同更新集的保证（并承认时间线重新排序的可能性，因为分区会恢复），但您获得了高可用性和（可以说）更好的用户体验。此外，由于更新最终会被传递，因此所有用户最终都会看到相同的时间线，其中包含用户发布的所有更新。

实现最终一致性

最终一致性的一个关键优势是它相当容易实现。为了确保收敛，副本必须彼此交换关于它们已看到的写入的信息。这种信息交换通常称为反熵，这是对物理系统中逆转熵或热力学随机性过程的致敬。¹⁹ 实现反熵的协议有多种形式；一种简单的解决方案是使用异步的全对全广播：当副本接收到对数据项的写入时，它立即响应用户，然后在后台将写入发送到所有其他副本，这些副本反过来更新它们本地存储的数据项。在发生对给定数据项的并发写入时，副本确定性地选择一个“获胜”值，通常使用简单的规则，例如“后写获胜”（例如，通过嵌入在每次写入中的时钟值）。²²

假设您想将单节点数据库变成最终一致的分布式数据库。当您收到请求时，您将其路由到您可以联系的任何服务器。当服务器对其本地键值存储执行写入时，它可以将写入发送到集群中的所有其他服务器。这种写入转发成为反熵过程。但是，在将写入发送到其他服务器时要小心。如果您等待其他服务器响应后再确认本地写入，那么，如果另一台服务器宕机或与您分区，则写入请求将无限期挂起。相反，您应该在后台发送请求；反熵应该是一个异步过程。隐含地，最终一致性的模型假设系统分区最终会恢复，更新最终会传播，或者分区节点最终会死亡，并且系统最终在单个分区中运行。

最终一致性系统具有一些很棒的特性。它不需要编写困难的“极端情况”代码来处理诸如副本宕机或网络分区之类的复杂场景——反熵只会停滞——或者编写诸如主节点选举之类的复杂协调代码。所有操作都在本地完成，这意味着延迟将受到限制。在地理复制场景中，副本位于不同的数据中心，您不必在请求快速路径上忍受数百毫秒数量级的长途广域网延迟。刚刚描述的机制，在本地写入后立即返回，可能会使数据持久性面临风险。在持久性和可用性之间进行权衡的一个中间点是在 W 个副本确认写入后返回，从而允许写入在 W-1 个副本故障中幸存下来。反熵可以根据需要频繁或稀有地运行，而不会违反任何保证。有什么不喜欢呢？

安全性和活性

虽然最终一致性相对容易实现，但当前的定义留下了一些不幸的漏洞。首先，数据库的最终状态是什么？始终返回值 42 的数据库最终是一致的，即使从未写入过 42。亚马逊首席技术官沃纳·沃格尔的首选定义指定“最终所有访问都返回最后更新的值”；因此，数据库不能收敛到任意值。²³ 即使是这个新定义也存在另一个问题：在达到数据库的最终状态之前，可以返回哪些值？如果副本尚未收敛，可以对返回的数据做出什么保证？

这些问题源于所有分布式系统都拥有的两种属性：安全性和活性。² 安全性属性保证“不会发生坏事”；例如，读取的每个值都曾在某个时间点写入数据库。活性属性保证“好事最终会发生”；例如，所有请求最终都会收到响应。

最终一致性的困难在于它不提供任何安全性保证——最终一致性纯粹是一个活性属性。好事最终会发生——副本达成一致——但是对于发生什么没有任何保证，并且在此期间没有排除任何行为！为了获得有意义的保证，需要将安全性和活性属性结合起来考虑：没有其中一个，你可能会得到不太令人满意的结果的平凡实现。

几乎所有其他比最终一致性更强的模型都提供某种形式的安全性保证。然而，对于几乎所有生产系统，最终一致性都应被视为数据一致性的最低要求。一个不保证副本收敛的系统非常难以推理。

最终一致性究竟有多“最终”？

尽管缺乏安全性保证，但最终一致性数据存储仍被广泛部署。为什么？虽然最终一致性存储不承诺安全性，但有证据表明最终一致性在实践中效果良好。鉴于其延迟和可用性优势，最终一致性“足够好”。对于许多在最终一致性和更强一致性模型之间提供选择的存储，许多从业者都提倡最终一致性。

最终一致性存储的行为可以被量化。仅仅因为最终一致性不承诺安全性，并不意味着安全性不经常被提供——并且您可以使用最近开发并正在进入生产存储的一系列技术来测量和预测最终一致性系统的这些属性。这些技术——我们将在接下来讨论——令人惊讶地表明，最终一致性在生产存储中通常表现得像强一致性一样。

指标和机制

最终一致性的一个常见指标是时间：写入需要多长时间才能对读取器可见？这捕捉了根据挂钟时间测量的“一致性窗口”。另一个指标是版本：给定的读取将是多久之前的版本？此信息可用于确保读取器永远不会及时倒退，而是始终观察数据库的逐渐更新的版本。虽然时间和版本可能是最直观的指标，但还有一系列其他指标，例如每个数据项的“真实”值的数值漂移以及这些指标的各种组合。²⁵

量化最终一致性的两种主要机制是测量和预测。测量回答了问题“在给定的工作负载下，我的存储现在有多一致？”¹⁸ 而预测回答了问题“在给定的配置和工作负载下，我的存储将有多一致？”⁴ 测量对于运行时监控和警报或验证是否符合 SLO（服务级别目标）很有用。预测对于概率性的假设分析很有用，例如配置和工作负载更改的影响，以及动态调整系统行为。测量和预测结合在一起，形成了一个有用的工具包。

概率有界陈旧性

作为对如何量化最终一致性行为的简要深入探讨，我们将讨论我们在开发、部署和集成最先进的预测技术到流行的 NoSQL Cassandra 中的经验。概率有界陈旧性（Probabilistically Bounded Staleness，PBS）为数据项的读取提供了对新近度的期望。⁴ 这使我们能够衡量最终一致性存储的行为与强一致性、线性一致性（或正则）存储的行为之间的偏差程度。PBS 实现了以下形式的指标：“在写入完成后的 100 毫秒内，99.9% 的读取将返回最新版本”，以及“85% 的读取将返回一个版本，该版本在最新版本的两个版本之内。”

构建 PBS

PBS 是如何工作的？直观地，不一致的程度由反熵的速率决定。如果副本不断交换它们最后写入的写入，那么不一致窗口应该受到网络延迟和每个节点本地处理延迟的限制。如果副本延迟反熵（可能是为了节省带宽或处理时间），那么此延迟会添加到不一致窗口中；许多系统（例如亚马逊的 Dynamo）在复制协议中提供设置来控制这些延迟。那么，给定反熵协议——给定配置的反熵速率、网络延迟和本地处理延迟——您可以计算预期的最终一致性。在 Cassandra 中，我们将时间信息 piggyback 在写入分发协议（反熵的主要来源）之上，并维护一个运行样本。当用户想知道给定复制配置的效果时，我们使用收集到的样本在协议的蒙特卡洛模拟中返回数据存储一致性的期望值，这与我们在伯克利 Cassandra 集群上的一致性测量非常吻合。

野外的 PBS

借助我们的 PBS 一致性预测工具，并在 LinkedIn 和 Yammer 的几位朋友的帮助下，我们量化了在生产中运行的三个最终一致性存储的一致性。PBS 模型预测，LinkedIn 的数据存储在 13.6 毫秒内返回一致的数据的概率为 99.9%，在 SSD（固态驱动器）上为 1.63 毫秒。这些最终一致性配置在第 99.9 个百分位数时分别比其强一致性对应配置快 16.5% 和 59.5%。Yammer 的数据存储在 202 毫秒的不一致窗口中经历了 99.9% 的不一致，延迟降低了 81.1%。结果证实了传闻证据：最终一致性存储通常比其强一致性对应配置更快，并且它们通常在几十或几百毫秒内保持一致。

为了使一致性预测更易于访问，在 Cassandra 社区的帮助下，我们最近在 Cassandra 1.2.0 中发布了对 PBS 预测的支持。Cassandra 用户现在可以在他们自己的生产集群上运行预测，以调整其一致性参数并执行正常情况、无故障操作的假设分析。例如，要探索向一组服务器添加 SSD 的效果，用户可以调整本地节点上读取和写入速度的预期分布。这些预测成本不高；我们创建的基于 JavaScript 的演示⁴在不到一秒的时间内完成数万次试验。

当然，预测并非没有缺陷：预测的质量仅与基础模型和输入数据一样好。正如统计学家乔治·E·P·博克斯所说，“所有模型都是错误的，但有些是有用的。” 未能考虑到系统或反熵协议的重要方面可能会导致不准确的预测。同样，预测的工作原理是假设过去的行为与未来的行为相关。如果环境条件发生变化，预测的准确性可能会受到限制。这些问题是手头问题的根本，它们提醒我们，预测最好与测量相结合以确保准确性。

最终一致性通常是强一致性

除了 PBS 之外，最近的几个项目也验证了真实世界最终一致性存储的一致性。一项研究发现，亚马逊 SimpleDB 的最终一致性读取的不一致窗口几乎总是小于 500 毫秒，²⁴ 而另一项研究发现，亚马逊 S3 的不一致窗口持续长达 12 秒。⁷ 其他最近的工作显示了与 PBS 呈现的结果相似的结果，Cassandra 在大约 200 毫秒内关闭其不一致窗口。¹⁸

这些结果证实了最终一致性通常“足够好”的传闻证据，通过为系统行为提供定量指标。随着 PBS 和一致性测量等技术继续进入更多生产基础设施，推理跨部署、故障和系统配置的最终一致性的行为将变得越来越直接。

最终一致性编程

虽然用户可以验证和预测最终一致性系统的一致性行为，但这些技术不提供绝对的安全性违规保证。如果应用程序要求始终尊重安全性怎么办？关于如何编程和推理最终一致性存储，人们的知识越来越多。

补偿、成本和收益

围绕一致性异常进行编程类似于推测：您不知道给定数据项的最新值是什么，但您可以像呈现的值是最新值一样继续进行。当您猜错时，您必须补偿在此期间采取的任何不正确的操作。实际上，补偿是一种追溯实现安全性的方法——恢复对用户的保证。¹³ 补偿确保错误最终得到纠正，但不保证不会发生错误。

作为推测和补偿的一个例子，考虑运行 ATM。^8,13 在没有强一致性的情况下，两个用户可能会同时从一个帐户中取款，最终获得的钱比该帐户曾经持有的钱还多。银行会想要这种行为吗？在实践中，是的。ATM 的取款能力（可用性）超过了在 ATM 与主银行分行的服务器分区的情况下临时不一致的成本。在帐户透支的情况下，银行有一套明确的外部补偿措施：例如，向用户收取透支费用。银行软件通常用于说明对强一致性的需求，但在实践中，银行的社会技术系统可以像处理其他错误（例如数据输入错误）一样处理数据不一致。

决定是否使用最终一致性的应用程序设计者面临一个选择。实际上，设计者需要权衡弱一致性的收益B（就高可用性或低延迟而言）与成本C乘以每个不一致性异常的成本乘以异常率R:

最大化 B-CR

这个决定必然是特定于应用程序和部署的。异常的成本由补偿的成本决定：过多的透支可能会导致客户离开银行，而状态更新传播太慢可能会导致用户离开社交网络。异常率——如前所述——取决于系统架构、配置和部署。同样，弱一致性的收益本身也可能是一个复合项，由通信故障和通信延迟等因素组成。

其次，应用程序设计者实际上必须为补偿而设计。编写极端情况补偿代码并非易事。确定正确的业务应用程序逻辑来处理每种类型的一致性异常是一项艰巨的任务。仔细推理每种可能的不一致性异常序列以及为每种异常向用户做出正确的“道歉”可能会比设计强一致性解决方案更繁琐。一般来说，当不一致性的成本很高，并且具有切实的货币后果（例如，ATM）时，补偿更有可能被深思熟虑。此外，根据应用程序的不同，可能已经存在一些补偿协议。例如，即使数据库完全一致，叉车也可能会碾过仓库中的托盘库存，或者包裹可能会在运输途中丢失。¹³

然而，对于某些应用程序，异常率可能足够低，或者不一致性的成本可能足够小，以至于应用程序设计者可能会选择完全放弃包含补偿。如果发生不一致性的机会足够低，则用户可能只会在少数情况下遇到异常。传闻称，许多在线服务（例如社交网络）在很大程度上以弱一致性配置运行：如果用户的状态更新需要几秒甚至几分钟才能传播给关注者，他们不太可能注意到甚至在意。在这种规模下运行强一致性服务的复杂性可能超过了收益，例如，防止贾斯汀·比伯在 Twitter 上的关注者数量出现一位数的错误。

通过设计进行补偿

补偿容易出错且费力，并且它使程序员（有时是应用程序）暴露于复制的影响。如果可以不进行补偿就进行编程怎么办？最近的研究为许多最终一致性应用程序提供了“无补偿”编程。

通过设计实现一致性的最终一致性程序的正式基础由 CALM 定理捕获，该定理指示哪些程序在最终一致性下是安全的，并且（保守地）哪些程序不是安全的。³ 从形式上讲，CALM 意味着作为逻辑单调性的一致性；非正式地讲，它意味着单调的程序，或者计算不断增长的事实集的程序（例如，通过接收新消息或代表客户端执行操作），并且从不“撤回”它们发出的事实（即，程序已经做出的决策的基础不会改变），始终可以在最终一致性存储上安全运行。（完全披露：CALM 是由我们在加州大学伯克利分校的同事开发的）。因此，CALM 告诉程序员哪些操作和程序在最终一致性系统中使用时可以保证安全性。任何未通过 CALM 测试的代码都是更强协调机制的候选者。

作为这种逻辑单调性的具体示例，考虑构建一个用于查询股票交易的数据库。一旦完成，交易就无法更改，因此任何仅基于不可变的历史数据的答案将保持为真。但是，如果您的数据库跟踪最新交易的价值，那么新信息（例如新的股票价格）可能会撤回旧信息，因为新的股票价格会覆盖数据库中的最新价格。在副本之间没有协调的情况下，第二个数据库可能会返回不一致的数据。

通过分析程序的单调性，您可以将单调程序“祝福”为在最终一致性下“安全”，并鼓励在存在非单调性的情况下使用协调协议（即，强一致性）。作为一般规则，诸如初始化变量、累积集合成员和测试阈值条件之类的操作是单调的。相反，诸如变量覆盖、集合删除、计数器重置和否定（例如，“不存在这样的交易……”）之类的操作通常在逻辑上不是单调的。

CALM 捕获了广泛的设计模式，有时称为 ACID 2.0（关联性、交换性、幂等性和分布式）¹³。关联性意味着您可以按任何顺序应用函数

f(a,f(b,c)) = f(f(a,b),c)

交换性意味着函数的参数对顺序不敏感

f(a,b) = f(b,a)

可交换和关联程序对顺序不敏感，并且可以容忍消息重新排序，就像在最终一致性中一样。幂等性意味着您可以对相同的输入多次调用函数并获得相同的结果

f(f(x))=f(x) (例如，max(42, max(42, 42)) = 42)

幂等性允许使用至少一次消息传递，而不是最多一次传递（这更难保证）。分布式主要是首字母缩略词中 D 的占位符（！），但象征着 ACID 2.0 完全是关于分布式系统的。仔细应用这些设计模式可以实现逻辑单调性。

最近关于 CRDT（可交换、复制数据类型）的工作将 CALM 和 ACID 2.0 原则体现在各种标准数据类型中，提供了可证明最终一致的数据结构，包括集合、图和序列。²⁰ 任何正确使用这些预定义、明确指定的数据结构的程序都保证永远不会产生任何安全性违规。

要理解 CRDT，请考虑构建一个在两台服务器上复制的仅递增计数器。我们可能会通过首先读取一个副本上的计数器值，将该值递增 1，然后将新值写回每个副本来实现递增操作。如果计数器最初为 0，并且两个不同的用户同时在不同的服务器上发起递增操作，则两个用户都可能读取 0，然后将值 1 分发到副本；计数器最终的值为 1 而不是正确的值 2。相反，我们可以使用 G-counter CRDT，它依赖于递增是可交换操作的事实——两个递增操作的应用顺序无关紧要，只要它们最终在所有站点都应用即可。对于 G-counter，当前的计数器状态表示为不同递增调用的计数，类似于在小学级别引入计数的方式：通过为每个递增做一个 tally 标记，然后将总数相加。在我们的示例中，不是读取和写入计数器值，而是每个调用都分发一个递增操作。所有副本最终都得到两个递增操作，总和为正确的值 2。这之所以有效，是因为副本理解递增操作的语义，而不是提供通用的读/写操作，而读/写操作是不可交换的。

这些进展的关键属性是它们分离了数据存储和应用程序级别的一致性问题。虽然底层存储可能在读取和写入级别返回不一致的数据，但 CALM、ACID 2.0 和 CRDT 诉诸于更高级别的一致性标准，通常以应用程序维护的应用程序级别不变量的形式。应用程序不必要求对数据存储的每次读取和写入都是强一致的，而只需确保语义保证（例如“计数器严格递增”）——在如何处理读取和写入方面给予相当大的自由度。应用程序级别和读/写一致性之间的这种区别通常是模糊且定义不明确的（例如，数据库 ACID “一致性”与“强一致性”有什么关系？）。幸运的是，通过识别一大类容忍弱一致性的程序和数据类型，程序员可以享受“强”应用程序一致性，同时获得“弱”分布式读/写一致性的好处。

总而言之，CALM 定理和 CRDT 构成了一个强大的工具包，用于实现“无并发控制的一致性”，这正在进入真实世界的系统。我们团队在 Bloom 语言³ 上的工作体现了 CALM 原则。Bloom 鼓励使用对顺序不敏感的无序编程，这是构建最终一致性系统的关键。我们最近的一些工作侧重于构建自定义的最终一致性数据类型，其正确性基于形式数学格理论。同时，一些开源项目（例如 Statebox²¹）将类似 CRDT 的原语作为最终一致性存储的客户端扩展提供，而一个最终一致性存储——Riak——最近宣布了对 CRDT 作为一流服务器端原语的 alpha 支持。⁹

比最终更强

虽然补偿操作和 CALM/CRDT 提供了一种绕过最终一致性的方法，但它们自身也存在缺点。前者需要在系统外部处理不一致性，而后者限制了应用程序编写者可以使用的操作。然而，事实证明，在仍然提供可用性的同时，为通用操作提供甚至比最终一致性更强的保证——尽管比 SSI 弱——是可能的。

CAP 理论指出，在存在分区的情况下，强一致性 (SSI) 和可用性是不可兼得的。但是，为了保证可用性，一致性模型必须有多弱？显然，最终一致性仅仅提供活性保证，是可用的。是否有可能在不丧失最终一致性优势的前提下，通过增加安全保证来加强最终一致性？

突破极限

德克萨斯大学奥斯汀分校最近的一份技术报告声称，在存在分区的情况下，没有比因果一致性更强的一致性模型是可用的。¹⁷ 因果一致性保证每个进程的写入操作都按顺序可见，写入操作遵循读取操作（如果用户读取值 A=5，然后写入 B=10，则另一个用户不能读取 B=10，随后读取比 5 更旧的 A 值），并且传递数据依赖性成立。这种因果一致性在确保例如评论线程以正确的顺序可见、没有悬空回复以及用户的隐私设置应用于适当的数据方面非常有用。德克萨斯大学奥斯汀分校的报告表明，如果没有违反高可用性或放弃以下保证，即如果两台服务器通信，它们将就其数据项的同一组值达成一致，那么不可能拥有比因果一致性更强的模型（接受更少结果的模型）。虽然许多其他可用模型既不比因果一致性更强也不比它弱，但这个不可能的结果很有用，因为它为一个非常熟悉的一致性模型设定了上限。

尤其是在这个结果的背景下，值得注意的是，几种新的数据存储设计提供了因果一致性。普林斯顿大学、卡内基梅隆大学和英特尔研究院的一个团队开发的 COPS 和 Eiger 系统¹⁶ 提供了因果一致性，而不会在地理位置遥远的数据中心之间产生高延迟，也不会在数据中心发生故障时损失可用性。与最终一致性相比，这些系统表现特别出色，性能成本几乎可以忽略不计；在 Facebook 的一个工作负载中，在 Cassandra 系统中进行原型设计的 Eiger 产生的开销不到 7%。在我们最近的工作中，我们演示了如何使用因果关系作为额外的安全保证来增强已经部署在生产环境中但提供最终一致性的现有数据存储。⁶ 因果关系可以附加在不影响高可用性的前提下，从而实现系统设计，其中安全性和活性被清晰地分解为单独的架构层。

除了因果关系之外，我们还可以考虑 ACID 事务和 CAP 理论之间的关系。虽然不可能提供 ACID 隔离的黄金标准——可串行化或 SSI——但事实证明，许多 ACID 数据库提供了较弱形式的隔离，例如读取已提交，通常是默认设置，在某些情况下，也是提供的最大隔离级别。我们最近的一些结果表明，许多这些较弱的模型可以在高可用性的情况下在分布式环境中实现。⁵ 当前提供这些弱隔离模型的数据库不可用，但这仅仅是因为它们是使用不可用的算法实现的。

我们——以及其他几个人——正在开发事务算法，这些算法表明不必如此。通过重新思考并发控制机制并从头开始重新架构分布式数据库，我们可以提供事务原子性、ANSI SQL 读取已提交和可重复读取以及事务之间的因果关系形式的安全保证——匹配许多现有的 ACID 数据库——而不会违反高可用性。这有点令人惊讶，因为过去许多人认为，在高可用系统中，任意多对象事务是不可能的。

认识到局限性

虽然这些结果突破了高可用性所能达到的极限，但一个弱一致性系统永远无法提供一些属性；保持高可用性（并提供保证的低延迟）存在根本性的成本。CAP 理论指出，在高可用性系统中，陈旧性保证是不可能的。指定数据新鲜度约束的读取（例如，“给我最新值”或“给我 10 分钟前的最新值”）在存在长期网络分区的情况下通常不可用。同样，我们无法维护数据项集合上的任意全局正确性约束，例如唯一性要求（例如，“如果帐户不存在，则创建 ID 为 50 的银行帐户”），并且在某些情况下（例如，任意读取和写入），即使是单个数据项上的正确性约束也是无法实现的（例如，“银行帐户余额应为非负数”）。这些挑战是选择弱一致性（无论是最终一致性还是更强但仍然“弱”的模型）的固有成本。

结论

通过简化分布式服务的设计和操作，最终一致性以牺牲对应用程序的语义保证为代价，提高了可用性和性能。虽然最终一致性是一个特别弱的属性，但最终一致性存储通常提供一致的数据，并且用于测量和预测的新技术使我们能够深入了解最终一致性存储的行为。同时，用于构建最终一致性数据类型和程序的新研究和原型正在减轻推理分布式系统中无序性的负担。这些技术，加上突破高可用性系统边界的新结果——包括因果关系和事务——为继续采用弱一致性系统提供了强有力的理由。虽然最终一致性及其弱一致性表亲并非完美适用于所有任务，但它们的性能和可用性在未来可能会继续赢得赞赏者和拥护者。

致谢

作者要感谢 Peter Alvaro、Carlos Baquero、Neil Conway、Alan Fekete、Joe Hellerstein、Marc Shapiro 和 Ion Stoica 对本文早期草稿的反馈。

这项工作得到了 Google、SAP、Amazon Web Services、Blue Goji、Cloudera、Ericsson、通用电气、惠普、华为、IBM、英特尔、MarkLogic、微软、NEC 实验室、NetApp、NTT 多媒体通信实验室、Oracle、Quanta、Splunk 和 VMware 的捐赠支持。本材料基于国家科学基金会研究生研究奖学金（资助号 DGE 1106400）、国家科学基金会资助项目 IIS-0713661、CNS-0722077 和 IIS-0803690、空军科学研究办公室资助项目 FA95500810352 以及 DARPA 合同 FA865011C7136 支持的工作。

参考文献

1. Abadi, D. 2012. 现代分布式数据库系统设计中的一致性权衡：CAP 只是故事的一部分。IEEE 计算机（二月）。

2. Alpern, B., Schneider, F.B. 1985. 定义活性。信息处理快报 21（十月）。

3. Alvaro, P., Conway, N., Hellerstein, J., Marczak, W. 2011. Bloom 中的一致性分析：一种 CALM 和收集的方法。CIDR（创新数据系统研究会议）。

4. Bailis, P., Venkataraman, S., Franklin, M., Hellerstein, J., Stoica, I. 2012. 实用部分仲裁的概率有界陈旧性。VLDB（超大型数据库）。（来自文本的演示：http://pbs.cs.berkeley.edu/#demo)

5. Bailis, P., Fekete, A., Ghodsi, A., Hellerstein, J., Stoica, I. 2013. HAT，而不是 CAP：高可用性事务。arXiv:1302.0309 [cs.DB]（二月）。

6. Bailis, P., Ghodsi, A., Hellerstein, J., Stoica, I. 2013. 附加因果一致性。 SIGMOD。

7. Bermbach, D., Tai, S. 2011. 最终一致性：最终有多快？Amazon S3 一致性行为的评估。MW4SOC（面向服务计算的中间件研讨会）。

8. Brewer, E. 2012. CAP 十二年后：“规则”如何改变。IEEE 计算机（二月）。

9. Brown, R., Cribbs, S. 2012. Riak 中的数据结构； https://speakerdeck.com/basho/data-structures-in-riak。RICON 会议。

10. Davidson, S., Garcia-Molina, H., Skeen, D. 1985. 分区网络中的一致性：一项调查。计算调查卷 17，第 3 期。

11. Gilbert, S., Lynch. N. 2002. Brewer 的猜想以及一致、可用、容错分区的 Web 服务的可行性。 SIGACT 新闻卷 33，第 2 期（六月）。

12. Hale, C. 2010. 你不能牺牲分区容错性。http://codahale.com/you-cant-sacrifice-partition-tolerance/

13. Helland, P., Campbell, D. 2009. 在流沙上构建。CIDR（创新数据系统研究会议）。

14. Johnson, P. R., Thomas, R. H. 1975. 维护重复数据库；RFC 677；http://www.faqs.org/rfcs/rfc677.html。

15. Kawell Jr., L., Beckhardt, S., Halvorsen, T., Ozzie, R., Greif, I. 1988. 组通信系统中的复制文档管理。1988 年计算机支持的协同工作会议论文集：395；http://dl.acm.org/citation.cfm?id=1024798。

16. Lloyd, W., Freedman, M., Kaminsky, M., Andersen, D. 2013. 低延迟地理复制存储的更强语义。NSDI（网络系统设计与实现）。

17. Mahajan, P., Alvisi, L., Dahlin, M. 2011. 一致性、可用性、收敛性。德克萨斯大学奥斯汀分校 TR-11-22（五月）。

18. Rahman, M., Golab, W., AuYoung, A., Keeton, K., Wylie, J. 2012. 迈向一致性基准测试的原则性框架。HotDep（系统可靠性热点问题研讨会）。

19. Saito, Y., Shapiro, M. 2005. 乐观复制。计算调查卷 37 第 1 期（三月）。 http://dl.acm.org/citation.cfm?id=1057980

20. Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M. 2011. 收敛和可交换复制数据类型的综合研究。INRIA 技术报告 RR-7506（一月）。

21. Statebox；https://github.com/mochi/statebox。

22. Terry, D., Theimer, M., Petersen, K., Demers, A., Spreitzer, M. Hauser, C. 1995. 在弱连接的复制存储系统 Bayou 中管理更新冲突。SOSP（操作系统原理研讨会）。

23. Vogels, W. 最终一致性。2008. 。

24. Wada, H., Fekete, A., Zhao, L., Lee, K., A. Liu, A. 2011. 商业云存储中的数据一致性和权衡：消费者的视角。CIDR（创新数据系统研究会议）。

25. Yu, H., Vahdat, A. 2002. 基于 conit 的复制服务连续一致性模型的设计与评估。 TOCS（计算机系统事务）。