ACM通信
实践
今天的最终一致性:限制、扩展和超越
图片来源:JNT Visual / Shutterstock.com
在2000年7月的一次会议上，现在是谷歌工程副总裁、加州大学伯克利分校教授的Eric Brewer公开假设了CAP(一致性、可用性和分区容差)定理，该定理将改变分布式存储系统的架构方式。8
Brewer根据他在inktom.com为第一批互联网搜索引擎构建基础设施的经验做出的推测是，分布式系统需要始终在线、高可用性操作，在存在网络分区的情况下，不能保证连贯一致的单系统操作的幻觉，因为网络分区切断了活动服务器之间的通信。Brewer的猜想被证明是有先见之明的:在接下来的十年里，随着大规模互联网服务的持续兴起，分布式系统架构师经常放弃“强”保证，而青睐较弱的模型——最值得注意的是最终一致性．
最终的一致性并不能保证什么。非正式地，它保证，如果没有额外的对给定的数据项进行更新，对该数据项的所有读取最终将返回相同的值。这是一个特别弱的模型。在任何给定的时间，用户都不能排除不一致行为的可能性:系统可以返回任何数据最终仍然是一致的，因为它可能在以后的某个点“收敛”。唯一能保证的是，在未来的某个时刻，会有好事发生。然而，由于明显缺乏有用的保证，许多可用的应用程序和盈利的业务都是建立在最终一致的基础设施之上的。如何?
本文通过描述最终一致性的理论和实践中的几个值得注意的发展来回答这个问题，并将重点放在立即适用于在野外运行分布式系统的从业者的收获上。随着生产部署越来越多地采用弱一致性模型(如最终一致性)，我们已经学习了一些关于如何推理、编程和加强这些弱模型的经验教训。
综上所述，我们将主要关注三个问题和一些初步的回答:
最终的一致性是怎样的?如果主张最终一致性的系统架构师的分数是某种暗示的话，最终一致性在实践中似乎“足够好”。当它提供如此薄弱的担保时，这怎么可能?新的预测和测量技术允许系统架构师量化现实世界中最终一致的系统的行为。当通过测量进行验证时，这些系统在大多数时候表现出很强的一致性．
一个程序应该如何达到最终的一致性?系统架构师如何应对最终一致性所提供的缺乏保证?他们如何在没有强顺序保证的情况下进行编程?新的研究使系统架构师能够处理不一致，或者通过系统外的外部补偿，或者通过将自己限制在完全避免不一致的数据结构中．
是否有可能提供比最终一致性更强的保证而不失去其好处?除了保证最终的一致性和高可用性之外，还可以提供哪些保证?最近的结果表明，在提供更强的保证(包括因果关系和来自传统数据库系统的几个ACID(原子性、一致性、隔离性、持久性)属性同时仍然保持高可用性)的同时，可以实现最终一致性的好处．
这篇文章是不旨在作为围绕最终一致性的文献的正式调查。相反，它是对我们对最终一致的系统的理解的前沿的几个发展的实用介绍。目的是为理解两者提供必要的背景知识如何而且为什么最终，一致的系统被编程、部署和发展，以及未来系统的发展方向。
最终一致性的历史和概念
布鲁尔的CAP定理表明，不可能同时获得永远在线的体验(可用性)，并确保用户阅读分布式数据库的最新编写版本(一致性经过正式证明，一个被称为"线性性"的特性11)在出现部分故障的情况下(分区)。8CAP简洁地总结了几十年来分布式系统设计中固有的权衡(例如，RFC 677)14从1975年)，并表明在分布式系统中维护SSI(单系统映像)是有成本的。10如果分布式系统中的两个(或一组)进程不能通信分区)，要么因为网络故障，要么因为某个组件的故障，那么更新就不能同步地传播到所有进程而不阻塞。在分区下，SSI系统不能安全地完成更新，因此对部分或所有用户来说不可用。此外，即使没有分区，选择可用性而不是一致性的系统也可以享受低延迟的好处:如果一个服务器在与所有其他服务器进行分区时能够安全地响应用户的请求，那么它就可以也在不联系其他服务器的情况下响应用户请求，即使它能够这样做。1(注意，您不能“牺牲”分区容限!12在一致性和可用性之间做出选择。)
随着越来越多的服务被复制以提供容错(确保服务在单个服务器故障时仍然在线)和容量(允许系统根据不同的请求率进行扩展)，架构师必须面对这些一致性、可用性和延迟之间的权衡。在动态的、可分区的Internet中，需要保证低延迟的服务通常必须放松对数据一致性的期望。
最终的一致性是一种可用的替代方案．鉴于CAP不可能的结果，分布式数据库设计者寻求更弱的一致性模型，以实现可用性和高性能。尽管自20世纪70年代以来，人们以各种形式对弱一致性进行了研究和应用，19最终的一致性模型已经变得突出，特别是在新兴的、高度可伸缩的NoSQL存储中。
最终一致性的最早定义之一来自1988年一篇描述群通信系统的论文15与今天的谷歌Docs等共享文本编辑器类似:“……对一个副本所做的更改最终会迁移到所有副本。如果所有更新活动都停止，那么经过一段时间后，数据库的所有副本将收敛到逻辑上等价:数据库的每个副本将以可预测的顺序包含相同的文档;每个文档的副本将包含相同的字段。”
在最终一致性下，所有服务器最终“收敛”到相同的状态;在未来的某个时刻，服务器之间将无法区分。然而，这种最终的收敛并不提供SSI语义。首先，“可预测的顺序”不一定对应于在SSI下可能出现的执行;最终一致性并不指定最终选择哪个值。其次，在达到收敛之前有一个未指定的窗口，在此期间系统将不提供SSI语义，而是提供任意值。正如我们将要说明的，这种最终趋同的承诺是一个相当弱的性质。最后，一个具有SSI的系统提供了最终的一致性，即“可能性”是即时的，而非反之。
为什么最终的一致性有用?假设你负责一个社交网络的数据基础设施，在这个网络中，用户发布的新状态更新被发送到他们的追随者的时间轴上，每个用户用单独的列表表示。由于大规模且频繁的服务器故障，时间线数据库存储在多个物理服务器上。但是，如果两个服务器之间存在分区，则不能将每个更新交付到所有时间线。你应该怎么做?您是应该告诉用户他或她不能发布更新，还是应该等到分区愈合后再提供响应?这两种策略都以用户体验为代价，选择了一致性而非可用性。
相反，如果您将更新传播到可到达的追随者的时间线集，返回给用户，并延迟向其他追随者交付更新，直到分区愈合，会怎样呢?在选择这个选项时，您放弃了所有用户在每个时间点都看到同一组更新的保证(并承认随着分区修复时间轴重新排序的可能性)，但您获得了高可用性和(可以说)更好的用户体验。此外，由于更新最终会交付，所有用户最终都会看到用户发布的所有更新的同一时间轴。
实现最终的一致性．最终一致性的一个关键好处是实现起来相当简单。为了确保收敛，副本之间必须交换关于它们所看到的写的信息。这种信息交换通常被称为anti-entropy这是对物理系统中熵或热力学随机性倒转过程的致敬。19实现反熵的协议有多种形式;一个简单的解决方案是使用异步全对全广播:当一个副本收到对数据项的写操作时，它立即响应用户，然后在后台将写操作发送给所有其他副本，这些副本依次更新它们本地存储的数据项。在对给定数据项进行并发写入的情况下，副本确定地选择一个“获胜”值，通常使用“最后一个写入者获胜”这样的简单规则(例如，通过在每次写入中嵌入一个时钟值)。22
在最终一致性下，所有服务器最终“收敛”到相同的状态;在未来的某个时刻，服务器之间将无法区分。
假设您想将一个单节点数据库变成一个最终一致的分布式数据库。当您收到一个请求时，您将它路由到您可以联系的任何服务器。当服务器对其本地键值存储区执行写操作时，它可以将写操作发送到集群中的所有其他服务器。这种写转发变成了反熵过程。但是，在将写操作发送到其他服务器时要小心。如果在确认本地写操作之前等待其他服务器响应，那么，如果另一个服务器关闭或从您分区，则写请求将无限期挂起。相反，你应该在后台发送请求;反熵应该是一个异步过程。隐式地，最终一致性模型假设系统分区最终被修复，更新最终被传播，或者分区的节点最终死亡，系统最终在单个分区中运行。
最终一致的系统有一些很好的性质。它不需要编写困难的“角落情况”代码来处理复杂的场景，如停机的副本或网络分区，反熵将简单地拖延或编写复杂的代码来协调，如主选。所有操作都在本地完成，这意味着延迟是有限的。在地理复制场景中，副本位于不同的数据中心，您不必忍受请求快速路径上数百毫秒量级的长途广域网络延迟。刚刚描述的机制在本地写操作时立即返回，可能会危及数据的持久性。在持久性和可用性之间进行交易的中间点是在W个副本已经确认写操作后返回，从而允许写操作在W-1副本故障后存活。反熵可以根据需要经常或尽可能少地运行，而不违反任何保证。为什么不喜欢呢?
安全与活力．虽然最终的一致性很容易实现，但当前的定义留下了一些不幸的漏洞。首先，数据库的最终状态是什么?一个总是返回值42的数据库最终是一致的，即使42从未被写入。Amazon CTO Werner Vogels的首选定义是“最终所有访问都返回最后更新的值”;因此，数据库不能收敛到任意值。23即使是这个新的定义也有另一个问题:在到达数据库的最终状态之前可以返回什么值?如果副本还没有聚合，那么如何保证返回的数据?
这些问题源于所有分布式系统所具有的两种特性:安全性和活性。2一个安全属性保证“不会发生糟糕的事情”;例如，读取的每个值都在某个时间点写入数据库。一个活性属性保证“好事最终会发生”;例如，所有请求最终都会收到响应。
最终一致性的困难在于它没有安全保证，最终一致性纯粹是一种活性属性。
最终一致性的困难在于它没有安全保证，最终一致性纯粹是一种活性属性。好的事情最终会发生，复制品同意，但没有保证会发生什么，在此期间没有行为被排除!对于有意义的保证，安全性和活性属性需要放在一起:如果没有其中之一，您可能会有提供不太令人满意的结果的琐碎实现。
几乎每一个比最终更强的模型都提供了某种形式的安全保证。然而，对于几乎所有的生产系统，最终一致性应该被视为数据一致性的最低要求。一个不保证副本收敛的系统是非常难以推理的。
最终的一致性是怎样的?
尽管缺乏安全保证，最终一致的数据存储被广泛部署。为什么?虽然最终的一致性存储不能保证安全，但有证据表明，最终的一致性在实践中很有效。考虑到延迟和可用性的好处，最终的一致性“足够好了”。对于许多在最终一致性和更强的一致性模型之间提供选择的商店，许多实践者主张最终一致性。
最终一致存储的行为可以被量化。仅仅因为最终的一致性不能保证安全性并不意味着不经常提供安全性，而且您可以使用最近开发的一系列技术来测量和预测最终一致性系统的这些特性，这些技术正在进入生产存储。我们接下来讨论的这些技术令人惊讶地表明，最终一致性通常表现为生产存储中的强一致性。
度量和机制．最终一致性的一个常见指标是时间:要花多长时间写才能被读者看到?这就抓住了根据挂钟测量的“一致性窗口”。另一个指标是版本:一个给定的读取将有多少个版本?这些信息可以用来确保读者不会回到过去，观察数据库的更新版本。虽然时间和版本可能是最直观的指标，但还有其他一些指标，比如每个数据项的“真实”值的数值偏移和这些指标的组合。25
量化最终一致性的两种主要机制是测量和预测。测量回答了这个问题，“在当前给定的工作负载下，我的存储的一致性如何?”18而预测回答了这个问题，“在给定的配置和工作负载下，我的存储的一致性如何?”4度量对于运行时监视和警报或验证是否符合服务级别目标(SLOs)非常有用。预测对于概率假设分析(例如配置和工作负载更改的影响)和动态调优系统行为非常有用。综合起来，测量和预测形成了一个有用的工具箱。
概率有界老化．作为对如何量化最终一致行为的一个简短深入研究，我们将讨论我们在开发、部署和将最先进的预测技术集成到Cassandra(一个流行的NoSQL)中的经验。概率有界老化，或PBS，提供了一个期望读取数据项的近时性。4这允许我们测量一个最终一致的存储的行为与一个强烈一致的、线性的(或常规的)存储的行为有多大的偏差。PBS支持这样的度量:“写操作完成100毫秒后，99.9%的读操作将返回最新的版本”，“85%的读操作将返回距离最新版本不到两个的版本”。
建筑PBS．PBS是如何运作的?直观地说，不一致的程度是由反熵率决定的。如果副本不断地交换它们最近的写操作，那么不一致的窗口应该受到每个节点上的网络延迟和本地处理延迟的限制。如果副本延迟反熵(可能是为了节省带宽或处理时间)，那么这个延迟被添加到不一致窗口;许多系统(例如Amazon的Dynamo)在复制协议中提供设置来控制这些延迟。给定反熵协议，然后给定配置的反熵速率，网络延迟和本地处理延迟，你可以计算预期的一致性。在Cassandra中，我们在写分布协议(反熵的主要来源)之上装载计时信息，并维护一个运行的样本。当用户想要知道给定复制配置的效果时，我们使用协议的蒙特卡洛模拟中收集的样本来返回数据存储一致性的期望值，这与我们在Berkeley的Cassandra集群上的一致性度量非常匹配。
野外的PBS．使用PBS一致性预测工具，在LinkedIn和Yammer的几个朋友的帮助下，我们量化了生产中运行的三个最终一致的商店的一致性。PBS模型预测，LinkedIn的数据存储在13.6ms内99.9%的时间内返回一致的数据;在ssd上，在1.63毫秒内。这些最终一致的配置比强一致的配置(99.9)快16.5%和59.5%th百分位。Yammer的数据存储经历了99.9%的202ms不一致窗口，降低了81.1%的延迟。结果证实了坊间传闻的证据:最终一致的存储通常比强一致的存储更快，而且它们经常在几十或几百毫秒内一致。
为了使一致性预测更容易实现，在Cassandra社区的帮助下，我们最近在Cassandra 1.2.0中发布了对PBS预测的支持。Cassandra用户现在可以在他们自己的生产集群上运行预测，以调整一致性参数，并对正常情况下无故障的操作执行假设分析。例如，为了探索向一组服务器添加固态驱动器(ssd)的效果，用户可以调整本地节点上预期的读和写速度分布。这些预测并不昂贵;我们已经创建了一个基于javascript的演示4在不到一秒的时间内完成成千上万的试验。
当然，预测并非没有缺点:预测的好坏取决于基础模型和输入数据。正如统计学家George E.P. Box的名言所说:“所有的模型都是错误的，但有些是有用的。”未能说明系统或反熵协议的一个重要方面可能导致不准确的预测。类似地，预测是通过假设过去的行为与未来的行为相关来实现的。如果环境条件发生变化，预测的准确性可能会有限。这些问题是当前问题的基础，它们提醒我们预测最好与测量相结合，以确保准确性。
最终一致性通常是强一致性．除了PBS之外，最近的几个项目也验证了现实世界最终一致存储的一致性。一项研究发现，Amazon SimpleDB最终一致读取的不一致窗口几乎总是小于500ms，24而另一项研究发现Amazon S3的不一致窗口持续了长达12秒。7最近的其他工作显示了与PBS类似的结果，Cassandra在大约200毫秒内关闭了不一致窗口。18
这些结果通过为系统行为提供量化指标，证实了最终一致性通常“足够好”的传闻证据。随着诸如PBS和一致性度量等技术继续进入更多的生产基础设施，对跨部署、故障和系统配置的最终一致性行为的推理将变得越来越直接。
编程最终的一致性
虽然用户可以验证和预测最终一致系统的一致性行为，但这些技术并不能绝对保证不违反安全规定。如果应用程序要求始终尊重安全性呢?关于如何对最终一致的存储进行编程和推理的知识越来越多。
报酬、成本和收益．围绕一致性异常进行编程类似于推测:您不知道给定数据项的最新值是多少，但可以继续进行，就好像显示的值是最新的一样。当你猜错了的时候，你必须为在此期间所采取的任何错误行动作出补偿。实际上，补偿是一种实现安全追溯的方式，以恢复对用户的保证。13补偿可以确保错误最终得到纠正，但不能保证错误不会发生。
作为投机和补偿的一个例子，考虑运行一台ATM机。8，13如果没有很强的一致性，两个用户可能同时从一个账户中取钱，最终得到的钱比该账户曾经持有的钱还要多。银行会想要这种行为吗?实际上，是的。在ATM与主银行分支机构的服务器被分区的情况下，ATM分发钱的能力(可用性)超过了临时不一致的成本。在账户透支的情况下，银行有一个明确的外部补偿行动系统:例如，向用户收取透支费。银行软件通常用于说明对强一致性的需要，但在实践中，银行的社会技术系统可以处理数据不一致，就像处理其他错误(如数据输入错误)一样。
应用程序设计人员在决定是否使用最终的一致性时面临一个选择。实际上，设计师需要权衡弱一致性的好处B(在高可用性或低延迟方面)对比成本C每一个不一致异常乘以异常率R：
这个决策必须是特定于应用程序和部署的。异常的成本由补偿成本决定:过多的透支可能导致客户离开银行，而状态更新传播太慢可能导致用户离开社交网络。之前所见的异常率取决于系统架构、配置和部署。同样，弱一致性的好处本身可能是由通信失败的发生率和通信延迟等因素组成的复合词。
第二，应用程序设计人员实际上必须为补偿进行设计。编写极端情况下的补偿代码并非易事。确定正确的业务应用程序逻辑来处理每种类型的一致性异常是一项困难的任务。仔细地推理每个可能的异常序列，并为每个异常向用户做出正确的“道歉”，这可能比设计一个具有强一致性的解决方案更加繁重。一般来说，当不一致的成本很高，有有形的金钱后果(例如，自动提款机)时，补偿更可能是经过深思熟虑的。
然而，对于某些应用程序，异常率可能足够低，或者不一致的代价足够小，以至于应用程序设计人员可以选择完全放弃包含补偿。如果不一致的几率足够低，用户可能只在少数情况下遇到异常。有趣的是，许多在线服务，如社交网络，在很大程度上是在弱一致性配置下运行的:如果用户的状态更新需要几秒钟甚至几分钟才能传播给关注者，他们不太可能注意到，甚至不太可能在意。大规模运营一项高度一致的服务的复杂性，可能超过了防止贾斯汀•比伯(Justin Bieber)在Twitter上的追随者数量少出一个错误的好处。
设计补偿．补偿很容易出错，而且很费力，它将程序员(有时是应用程序)暴露在复制的影响之下。如果不用它也能编程呢?最近的研究为许多最终一致的应用程序提供了“无补偿”编程。
最终一致的程序的形式基础是由CALM定理捕获的，该定理指出哪些程序在最终一致下是安全的，以及(保守地)哪些是不安全的。3.形式上，CALM的意思是一致性就是逻辑单调性；非正式地说，它意味着程序是单调的，或者计算一个不断增长的事实集(例如，通过接收新消息或代表客户端执行操作)，并且永远不会“收回”它们发出的事实(也就是说，它已经做出的决策的基础不会改变)，这些程序总是可以在最终一致的存储上安全地运行。(完全披露:CALM是由加州大学伯克利分校的同事开发的)。因此，CALM告诉程序员在最终一致的系统中使用哪些操作和程序可以保证安全性。任何未能通过CALM测试的代码都可以使用更强的协调机制。
作为这种逻辑单调性的一个具体例子，考虑为股票交易查询构建一个数据库。交易一旦完成，就不能改变，所以任何给出的答案都是基于不可变的历史数据将保持真实。但是，如果数据库跟踪最新的交易时，新的信息，比如新的股票价格，可能会收回旧的信息，因为新的股票价格会覆盖数据库中的最新股票价格。如果没有副本副本之间的协调，第二个数据库可能返回不一致的数据。
通过分析程序的单调性，您可以“称赞”单调程序在最终一致性下是“安全的”，并鼓励在出现非单调性时使用协调协议(如强一致性)。作为一般规则，初始化变量、累积集合成员和测试阈值条件等操作都是单调的。相比之下，诸如变量重写、集删除、计数器重置和否定(例如，“不存在这样的交易……”)等操作在逻辑上通常不是单调的。
CALM捕获了广泛的设计模式空间，有时称为ACID 2.0(结合性、交换性、幂等性和分布式)。13结合性意思是你可以以任何顺序应用函数: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原则，提供了可证明的最终一致的数据结构，包括集、图和序列。20.任何正确使用这些预定义的、指定良好的数据结构的程序都保证永远不会出现任何安全违规。
大规模运营一项高度一致的服务的复杂性，可能超过了防止贾斯汀•比伯(Justin Bieber)在Twitter上的追随者数量少出一个错误的好处。
要理解crdt，可以考虑构建在两台服务器上复制的仅增量计数器。我们可以先在一个副本上读取计数器的值，将该值加1，然后将新值写回每个副本，从而实现递增操作。如果计数器初始值为0，而两个不同的用户同时分别在两个不同的位置发起增量操作，那么两个用户都可以读取0，然后将值1分配给副本;计数器最终得到的值是1，而不是正确的值2。相反，我们可以使用G-counter CRDT，它依赖于增量是交换运算吗?两者的顺序无关紧要增量只要两种操作最终都应用于所有站点，就可以应用它们。对于g计数器，当前计数器状态表示为distinct计数增量调用，类似于在小学级别引入计数的方式:对每个增量做一个计数标记，然后将总数相加。在我们的例子中，不是读和写计数器值，每次调用分配一个增量操作．所有副本最后都有两个增量操作，它们的和为正确的值2。这是因为副本理解增量操作的语义，而不是提供通用的读/写操作，后者是不可交换的。
这些改进的一个关键特性是，它们将数据存储和应用程序级一致性问题分离开来。虽然底层存储可能在读写级别返回不一致的数据，但CALM、ACID 2.0和CRDT适用于此更高级的一致性标准，通常以应用程序维护的应用程序级不变量的形式出现。应用程序不要求对数据存储的每次读写都是强一致的，而是只需确保语义保证(例如，“计数器严格增加”)，在如何处理读写方面授予相当大的灵活性。应用程序级和读/写一致性之间的区别通常很模糊，定义也很差(例如，数据库ACID“一致性”与“强一致性”有什么关系?)幸运的是，通过确定容忍弱一致性的大量程序和数据类型，程序员可以享受“强”应用程序一致性，同时获得“弱”分布式读/写一致性的好处。
CALM定理和crdt共同构成了一个强大的工具包，用于实现“无并发控制的一致性”，它正在进入现实系统中。我们团队对布鲁姆语言的研究3.体现了冷静的原则。Bloom鼓励使用顺序不敏感的无序编程，这是最终构建一致系统的关键。我们最近的一些工作集中于构建自定义的最终一致的数据类型，其正确性基于形式的数学晶格理论。同时，一些开源项目，如Statebox21提供类似crdt的原语作为最终一致存储的客户端扩展，而一家最终一致存储公司最近宣布了对crdt的alpha支持，将其作为一级服务器端原语。9
比最终更强
虽然补偿动作和CALM/ crdt提供了一种解决最终一致性的方法，但它们也有自己的缺点。前者需要处理系统外部的不一致，而后者限制了应用程序作者可以使用的操作。然而，事实证明，在提供可用性的同时，可以为通用操作提供比最终一致性更强的保证，尽管比ssid更弱。
CAP定理表明，强一致性(SSI)和可用性在存在分区的情况下是无法实现的。但是一致性模型要有多弱才能让它可用呢?显然，最终的一致性是可行的，它只是提供了一个活跃的保证。是否有可能通过增加安全保障而不丧失其好处来加强最终的一致性?
挑战极限．得克萨斯大学奥斯汀分校(University of Texas at Austin)最近的一份技术报告称，在存在分区的情况下，没有比因果一致性更强的一致性模型。17因果一致性保证了每个进程的写是按照写和读的顺序进行的(如果一个用户读取一个值a =5，然后写入B=10，那么另一个用户不能读取B=10，然后读取一个比5更老的值a)，传递数据依赖保持不变。这种因果一致性有助于确保，例如，评论线程以正确的顺序显示，没有悬空的回复，以及将用户的隐私设置应用到适当的数据。UT Austin的报告表明，不可能有比因果一致性(接受更少的结果)更强大的模型，而不违背高可用性或确保(如果两台服务器通信，它们将对其数据项的相同值集达成一致)。虽然许多其他可用的模型既不强于也不弱于因果一致性，但这个不可能性结果是有用的，因为它为非常熟悉的一致性模型设置了一个上限。
通过分析程序的单调性，您可以“祝福”单调程序在最终一致性下是“安全的”，并鼓励在非单调性存在的情况下使用协调协议。
根据UT Austin的结果，一些新的数据存储设计提供了因果一致性。COPS和Eiger系统16它由来自普林斯顿大学、CMU和英特尔研究中心的团队开发，提供了因果一致性，而不会在地理位置遥远的数据中心之间产生高延迟，也不会在数据中心故障时丧失可用性。这些系统的性能特别好，与最终的一致性相比，其性能成本几乎可以忽略不计;Eiger是在Cassandra系统中开发的原型，在Facebook的工作负载中，Eiger的开销不到7%。在我们最近的工作中，我们演示了如何使用因果关系来增强已部署在生产中但提供最终一致性的现有数据存储，以作为额外的安全保证。6因果关系可以是螺栓在不影响高可用性的情况下，使系统设计能够将安全性和活性干净地分解到独立的体系结构层中。
除了因果关系之外，我们还可以考虑ACID事务和CAP定理之间的关系。虽然不可能提供ACID隔离序列化性的黄金标准，但事实证明，许多ACID数据库提供了一种较弱的隔离形式，如读提交，这通常是默认的，在某些情况下是提供的最大值。我们最近的一些研究结果显示了许多这种较弱的模型可以在分布式环境中实现，同时提供高可用性。5目前提供这些弱隔离模型的数据库不可用，但这只是因为它们是用不可用的算法实现的。
我们和其他几家公司正在开发事务性算法，表明情况并非如此。通过重新思考并发控制机制和从头开始重新构建分布式数据库，我们可以以事务原子性、ANSI SQL Read Committed和Repeatable Read的形式提供安全保证，以及匹配许多现有ACID数据库的事务之间的因果关系，而不违反高可用性。这有点令人惊讶，因为过去许多人都认为，在高可用性系统中，任意多对象事务是不可能的。
认识到局限性．虽然这些结果突破了高可用性所能达到的极限，但仍有一些弱一致性系统永远无法提供的特性;保持高可用性(并提供有保证的低延迟)有一个基本成本。CAP定理指出，在高可用性系统中不可能保证过期。指定数据近时性约束(例如，“给我最新的值”，“给我10分钟前的最新值”)的读取在存在长时间网络分区的情况下通常不可用。类似地，我们不能在数据项集上维护任意的全局正确性约束，例如惟一性需求(例如，“如果账户不存在，则创建ID为50的银行账户”)，并且，在某些情况下(例如，任意读和写)，甚至对单个数据项的正确性约束都是不可实现的(例如，“银行账户余额应该是非负的”)。这些挑战是选择弱一致性的固有成本，无论是最终还是更强但仍然“弱”的模型。
结论
通过简化分布式服务的设计和操作，最终的一致性以牺牲应用程序的语义保证为代价，提高了可用性和性能。虽然最终一致性是一个特别弱的属性，但最终一致存储通常提供一致的数据，而用于测量和预测的新技术使我们能够深入了解最终一致存储的行为。同时，构建最终一致的数据类型和程序的新研究和原型正在减轻对分布式系统中无序的推理负担。这些技术，加上新的结果，推动了高可用性系统的边界，包括因果关系和事务，为持续采用弱一致性系统提供了强有力的理由。虽然最终的一致性和它的弱一致性表亲并不是对每个任务都是完美的，但它们的性能和可用性含义在未来可能会继续获得崇拜者和倡导者。
致谢
作者感谢Peter Alvaro、Carlos Baquero、Neil Conway、Alan Fekete、Joe Hellerstein、Marc Shapiro和Ion Stoica对本文早期草稿的反馈。
相关文章
在queue.acm.org
最终一致
Werner Vogels
http://queue.acm.org/detail.cfm?id=1466448
碱:一种酸的替代品
丹普里切特
http://queue.acm.org/detail.cfm?id=1394128
可伸缩的SQL
迈克尔一
http://queue.acm.org/detail.cfm?id=1971597
参考文献
1.现代分布式数据库系统设计中的一致性权衡:CAP只是故事的一部分。IEEE计算机(2012年2月)。
2.阿尔彭，B.和施耐德，f .定义生活。信息处理信件21(1985年10月)。
3.Alvaro, P, Conway, N, Hellerstein, J.和Marczak, W. 2011。Bloom的一致性分析:一种冷静和镇定的方法。创新数据系统研究会议论文集(2011)。
4.贝利斯，文卡塔拉曼，富兰克林，M，赫勒斯坦，J.和斯托伊卡，I.实际部分法定量的概率有界老化。在超大数据库学报(2012)。(演示来自文本:http://pbs.cs.berkeley.edu/#demo）
5.Bailis, P.， Fekete, A.， Ghodsi, A.， Hellerstein, J.和Stoica, I. HAT，而不是CAP:高可用事务。arXiv:1302.0309(2013年2月)。
6.Bailis, P.， Ghodsi, A.， Hellerstein, J.和Stoica, I. bolon因果一致性。在ACM SIGMOD论文集(2013)中。
7.Bermbach, D.和Tai, S.最终一致性:什么时候是最终?对Amazon S3一致性行为的评估。《面向服务计算的中间件研讨会论文集》(2011)。
8.12年后:“规则”是如何改变的。IEEE计算机(2012年2月)。
9.Brown, R.和Cribbs, S. Riak中的数据结构(2012);https://speakerdeck.com/basho/data-structures-in-riak．理光会议。
10.Davidson, S, Garcia-Molina, H.和Skeen, D.分区网络的一致性:一个调查。ACM计算调查173(1985)。
11.吉尔伯特，S.和林奇。布鲁尔的猜想和一致的、可用的、允许分区的web服务的可行性。ACM SIGACT新闻332(2002年6月)。
12.Hale, C.你不能牺牲分区容忍度(2010);http://codahale.com/you-cant-sacrifice-partition-tolerance/
13.赫兰，P.和坎贝尔，D.流沙上的建筑。在创新数据系统研究会议论文集(2009)。
14.约翰逊P. R.托马斯R. H.重复数据库的维护;RFC 677 (1975);http://www.faqs.org/rfcs/rfc677.html．
15.小卡维尔，L.，贝克哈特，T.，哈尔沃森，奥齐，R.和格雷夫，I.群通信系统中的复制文档管理。在1988年ACM计算机支持的协同工作会议论文集: 395;http://dl.acm.org/citation.cfm?id=1024798．
16.Lloyd, W.， Freedman, M.， Kaminsky, M.和Andersen, D.低延迟地理复制存储的更强语义。在网络化系统设计与实现(2011)。
17.Mahajan, P.， Alvisi, L.和Dahlin, M.一致性，可用性，收敛性。德克萨斯大学奥斯汀分校TR-11-22(2011年5月)。
18.Rahman, M.， Golab, W.， AuYoung, A.， Keeton, K.和Wylie, J.建立基准一致性的原则框架。系统可靠性热点专题研讨会(2012)。
19.Saito, Y.和Shapiro, M.乐观复制。ACM计算调查371(2005年3月)。http://dl.acm.org/citation.cfm?id=1057980
20.Shapiro, M.， Preguiça, N.， Baquero, C.和Zawirski, M.对收敛和交换复制数据类型的全面研究。INRIA技术报告RR-7506(2011年1月)。
21.Statebox;https://github.com/mochi/statebox．
22.Terry, D.， Theimer, M.， Petersen, K.， Demers, A.， Spreitzer, M.和Hauser, C.管理Bayou(弱连接复制存储系统)中的更新冲突。在操作系统原理研讨会论文集(1995)。
23.Vogels, w，最终一致。ACM队列,(2008)。
24.Wada, H.， Fekete, A.， Zhao, L.， Lee, K.， A.和Liu, A.商业云存储中的数据一致性和权衡:消费者的视角。创新数据系统研究会议论文集(2011)。
25.Yu H.和Vahdat .基于conit的复制服务连续一致性模型的设计与评估。ACM反式。有关电脑系统(2002)。
©2013 acm 0001-0782/13/05
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2013 ACM, Inc.
没有找到条目