摘要

为了最大限度的减少网络延迟，并且在服务器宕机或者网络分区的情况下依然提供服务，许多现代分布式数据存储系统避免使用事务功能，而事务可以为多组数据上的多组操作提供强大的语义保证。我们所做的工作是，如何提供高可用的事务（ HATs，Highly Available Transactions ）：当系统出现网络分区或者网络高时延时，在不牺牲可用性的前提下提供事务保证。我们引入了一种高可用系统的分类，并分析了现有的ACID隔离和分布式数据一致性保证，以确定哪些可以在HAT系统中实现，哪些不能。其中综合了关于弱事务隔离，副本一致性，高可用系统相关文献。我们通过分析和实验量化了HATs在广域网络上的可用性和性能优势（通常为两到三个数量级）并讨论了其必要的语义折衷。

1 介绍

过去十年见证了流行的大规模数据库系统设计发生的变化，从使用事务性RDBMS^[14,38,37]到广泛采用松散一致的（loosely consistent）分布式键值存储^[21,23,30]。造成这种转变的核心原因是2000年布鲁尔CAP定理的引入，该定理指出，在存在网络分区的情况下，高可用性系统无法提供“强”一致性保证^[16]。正如正式证明的那样^[35]，CAP理论倾向于线性一致性的数据一致性模型，即读取不同服务器上最新写入的数据副本的能力。然而，尽管CAP定理的范围很窄，但在关于提供具有高可用性的ACID数据库属性的能力^[9,16,22]上，它经常被误解为一个广泛的结果；这种误解导致了对副本一致性、事务隔离和高可用性的严重混淆。最近事务性系统的复兴表明程序员重视事务性语义，但大多数现有的事务性数据存储在存在分区的情况下不提供可用性^{[19、22、42、25、48、59、61]}。

事实上，作为传统ACID数据库的黄金标准，可串行化事务在存在网络分区的情况下无法实现高可用性^[28]。然而，数据库系统长期以来的传统是提供较弱的隔离性和一致性保证^{[2,12,37,38,43]}。由于并发和性能优势，今天的ACID和NewSQL数据库通常采用弱隔离模型；弱隔离绝大多数是这些存储的默认设置，并且经常是提供的唯一模式（见章节3）。虽然弱隔离级别不能为通用事务提供串行化能力，但它们显然也足够强大，可以为许多应用程序员提供可接受的表现，并且比当前高可用系统提供的语义强得多。这就出现了一个很自然的问题：哪些语义可以提供高可用性？

迄今为止，ACID语义和高可用两者之间的关系并没有探讨的很清楚。弱隔离起源于单服务器场景，我们对此有着很深入的理解。许多论文都提供了提供分布式串行化^{[14,25,27,42,61]}或快照隔离^[43,59]的技术。另外，分布式计算和并行硬件相关的文献也包含了许多针对多副本对象上单操作的一致性模型^{[23,41,48,49,60]}。然而，对于在高度可用的分布式环境中对多个数据项执行的多个操作提供语义保证，这方面的文献提供的线索很少。

本文的主要贡献如下。我们将以前提出的许多数据库隔离和数据一致性模型与高可用性目标联系起来，高可用性保证了在每个不会宕机的服务器之间存在任意网络分区时，每个服务器都能做出响应。我们对大量的模型做了分类归总，其中那些可以实现高可用的标记为高可用事务（HATs）。在这个过程中，我们发现，虽然很多HAT语义的实现并不是高可用的，但是这是实现的产物，而不是语义的固有属性。我们的研究表明，除了串行化，快照隔离以及可重复读隔离级别无法实现高可用之外，多数其他隔离级别都可以实现高可用。我们还证明了许多分布式系统的弱副本一致性模型都是符合HAT的，并且可以通过几个ACID属性同时实现。

我们的研究是基于一些不可能的结论以及几个建设性的概念证明算法。比如，快照隔离和可重复读隔离级别是不符合HAT的，原因是这两种隔离界别需要检测两个并发更新之间的冲突（防止出现更新丢失和写偏斜现象），这对于HAT来说是不可能实现的。然而，通过依赖多版本控制和有限的客户端缓存的算法，可以实现数据库和分布式系统的读已提交、事务原子性（第5.1.2节）和许多其他一致性模型。对于一些保证，例预防幻读和ANSI可重复读的因果一致性，我们考虑一种改进的高可用性形式，其中客户端“stick to”（即，联系密切）至少一个Server——一个在分布式系统文献^[41,48,49]中经常隐含的属性，但它需要在客户端-服务器复制的数据库上下文中明确考虑。这种粘性可用性被广泛采用^[48,64]，但与传统的高可用性相比，它的限制性更小（因此更容易实现）。

从较高的层次上讲，HATs的优点是保证来自任何副本的响应、低延迟，以及一系列语义保证，这些语义保证的作用大家是普遍认可的，如读提交。 然而，高可用性系统从根本上无法阻止对共享数据项的并发更新，也无法保证能够读到最新的数据。为了理解这些优点和局限在实践中的相关性，我们调查了从业者和学术文献，再现代云基础设施上进行了实验分析，并分析了具有代表性的应用程序的语义需求。我们在多地域副本的数据中心运行HAT协议的经验表明，与传统的分布式串行化协议相比，HAT的延迟降低了一到三个数量级，并且可以为大量的程序提供可接受的语义，尤其是那些具有单调逻辑和交替更新的应用程序^[4,58]。HAT系统还可以保证多数据更新时的任意外键约束，在某些情况下，还可以提供有限的唯一性保证。然而，HATs可能无法满足具有并发敏感操作的应用程序，这些操作需要可能造成不可用的同步协调。

最后，我们认识到，种类繁多的ACID隔离级别和分布式一致性模型（我们的分类法中的模型）可能会令人困惑；模型之间的细微差别可能会引起学术界的关注。因此，我们提供以下务实的建议：

1. 大量的数据库系统的默认配置（有时是最强的）暴露了一系列异常，可能会损害应用程序级别的一致性。
2. 如果实施得当，这些“弱隔离”模型中的许多都可以在不牺牲高可用性的情况下实现。然而，所有可实现的模型都不能避免并发修改的问题。
3. 除了提供有保证的响应是时间和水平扩展之外，这些高可用的HAT模型还能做到在当前基础设施上降低一到三个数量级的延迟。
4. 要达到最好的效果，应用程序可能需要结合使用HAT和（理想情况下避免使用）非HAT隔离级别；未来的数据库设计者应该相应地进行规划 。

2 为什么要高可用？

为什么高可用性很重要？Peter Deutsch以分布式数据库系统的两个基本问题开始了他的经典著作“分布式计算谬误”（Fallacies of Distributed Computing）：“1.）网络是可靠的。2.）延迟为零”^[32]。在分布式环境中，网络故障可能会阻断数据库服务器通信，在没有故障的情况下，通信会因物理距离、网络拥塞和路由等因素而减慢。正如我们将看到的（第4节），高可用性系统设计减轻了网络分区和延迟的影响。在本节中，我们列举了了一系列证据，这些证据表明，在现实世界的部署中，分区的发生频率很高，数据中心之间的延迟非常大，通常在几百毫秒左右。

2.1 大规模网络分区

亚马逊Web服务团队的副总裁兼杰出工程师詹姆斯·汉密尔顿表示，“网络分区应该很少见，但net gear（译注：应该是指网络硬件）仍然会造成更多问题”^[39]。传闻证据证实了汉密尔顿的说法。2011年4月，网络配置错误导致亚马逊EC2和RDS服务连续12小时中断^[7]。随后的错误配置和部分故障（如2012年10月的另一次EC2宕机）导致Reddit、Foursquare和Heroku等流行web服务的网站全面中断^[33]。在全球范围内，硬件故障（如2011年北美和欧洲因路由器错误^[57]导致的互联网主干中断）以及错误配置（如2008年^[51]和2010年^[52]的BGP故障）可能会导致大范围的网络的分区行为。

我们与相关从业者（尤其是公共云基础设施运营的从业者）进行了许多讨论，以及来自谷歌等大型运营商的报告[29]都证实，分区管理是当今服务运营商的一个重要考虑因素。不考虑分区行为的系统设计可能会被证明难以大规模运行：例如，在其发布后不到一年，雅虎的PNUTS开发者明确增加了对较弱、高可用操作的支持。工程师们解释说，“严格遵守[强一致性]会导致在网络分区或服务器故障下出现困难情况……在许多情况下，应用程序需要一种宽松的方法”^[53]。

最近的几项研究严格量化了分区行为。2011年，一项针对多个微软数据中心的研究发现，超过13300个网络故障会对终端用户造成影响，每一次故障的平均数据包丢失量估计为59000个。研究发现，平均每天有40.8次网络链路故障（第95百分位：136次），平均修复时间约为5分钟（最多一周）。也许令人惊讶的是，配置冗余网络只会将故障的影响降低高达40%，这意味着网络提供商无法很容易地减少分区行为^[36]。2010年对200多台广域路由器进行的一项研究发现，平均每年每条链路发生16.2–302.0次故障，平均每年每条链路停机24–497分钟（第95百分位至少34小时）^[63]。在惠普管理的企业网络中，WAN、LAN和连接问题占所有客户支持问题的28.1%，而39%的问题与网络硬件有关。最高优先级门票的事件持续时间中位数在114-188分钟之间，所有事件的持续时间最高可达一整天^[62]。其他研究证实了这些结果，这些研究显示，WAN网络连接故障之间的平均时间约为3000秒，修复的平均时间为2到1000秒^[50]，互联网上频繁的路径路由故障也是如此^[45]。Kingsbury和Bailis最近的一份非正式报告列出了一系列其他的从业者报告[44]。毫不奇怪，隔离、量化和解释这些网络故障是网络社区积极研究的一个领域^[47]。

这些研究表明，网络分区确实发生在现代数据中心内部和之间。我们观察到，这些分区要么在某些服务器上不可用，要么像我们将要讨论的那样，在语义保证上放松。（不可用 or 放松保证）

2.2 延迟和行星地球

即使在无故障网络中，分布式系统也面临网络通信延迟的挑战，这是Deutsch的第二个“谬误”。在本节中，我们将量化往返延迟，在多数据副本中心环境中，往返延迟通常比较大——长达数百毫秒。从根本上说，两台服务器的通信速度（根据现代物理学）受光速的限制。在最好的情况下，地球两侧的两台服务器通过假设的链路通过地球核心进行通信，需要至少85.1ms的往返时间（RTT；如果在地表发送，则需要133.7ms）。随着服务被复制到多个地理位置不同的站点，这种通信成本还会增加。

image.png

在实际部署中，由于路由、拥塞和服务器端开销，消息的传输速度低于光速。为了说明数据中心内、数据中心间和星际网络之间的差异，我们在广泛使用的公共计算云Amazon的EC2上对网络性能进行了测量研究。我们测量了所有7个EC2地理“区域Region”、3个“可用性区域”（密集的位于同一位置的数据中心）和单个“可用性区域”（数据中心）之间一周的ping时间（即往返时间或RTT），粒度为1s。我们在表1中总结了网络测量研究的结果。平均而言，数据中心内部通信（表1a）比地理位置相同的数据中心（表1b）快1.82到6.38倍，比地理位置分散的数据中心（表1c）快40到647倍。广域通信的成本超过了光速：例如，从圣保罗到新加坡的光速RTT为106.7ms，而ping数据包的平均RTT为362.8ms（第95百分位：649ms）。如图1所示，链路之间的延迟分布各不相同，但趋势是明确的：远程通信成本巨大。量化和最小化通信延迟也是网络社区的一个活跃研究领域^[66]。

image.png

3 ACID in the Wild

上一节阐明了分布式系统必须解决分区和延迟问题：这对分布式数据库意味着什么？数据库研究和设计人员早就意识到，在高可用性系统中无法实现串行化[28]，这意味着，在第2节所述的环境中，数据库设计面临可用性和强语义之间的选择。然而，即使在单节点数据库中，串行化带来的相关惩罚也可能很严重，表现为并发性降低（以及随后的性能下降、可伸缩性限制，以及通常由于死锁或争用而中止）^[38]。因此，为了提高并发性，数据库系统提供了一系列弱于串行化的ACID属性：所谓弱隔离模型的主机描述了系统允许的对调度空间的不同限制^[2,5,12]。 这些弱隔离模型都不能保证可串行化，但是，如下图所示，它们的好处通常被认为超过了使用它们可能导致的一致性异常的成本。

image.png

为了了解弱隔离的普遍性，我们最近调查了18个数据库提供的默认和最大隔离保证，通常声称提供了“ACID”或“NewSQL”功能^[9]。如表2所示，默认情况下，18个数据库中只有3个提供了串行化的隔离级别，8个数据库根本不提串行化选项。当我们考虑许多非可串行化数据库（如Oracle 11G）的广泛部署时，这一点尤其令人惊讶。鉴于这些弱事务模型经常被使用，我们无法在任意的HATs中提供串行化能力对于实际应用来说似乎不是致命的。如果应用程序编写者和数据库供应商已经决定，弱隔离的好处大于潜在的应用程序不一致性，那么，在一个非串行化的高可用环境中，类似的决定可能是站得住脚的。

目前尚不清楚这些隔离性保证中哪些可以提供高可用性，哪些是符合HAT的。提供弱隔离的现有算法通常是针对单个节点环境设计的，据我们所知，由于依赖于并发控制机制（如锁）而导致不可用，这些机制无解决抗部分故障问题（第6.1节）。此外，我们还不知道之前有任何文献为弱隔离和高可用性之间的关系提供了指导：之前的工作研究了可串行化和高可用性^[28]之间的关系，以及一般的弱隔离^[2,12,38]，但没有同时研究弱隔离和高可用性之间的关系。本文剩余部分的主要目标是了解哪些模型符合HAT。

4 High Availability

为了理解高可用性可以提供哪些保证，我们必须首先定义高可用性的含义。在本节中，我们将制定一个模型，该模型包含一系列可用性模型，包括高可用性、具有粘性的可用性和事务可用性。

非正式地说，高可用性算法确保了“始终开启”操作，并且作为一种副作用，保证了低延迟。如果高可用性系统的客户端能够与系统中的（一组）服务器通信，则保证他们会得到响应；这意味着服务器不需要与其他服务器同步通信。如果服务器彼此隔离，它们不需要暂停，以便为客户端提供对操作的“安全”响应。缺失快速路径协调也意味着高可用性系统也提供低延迟（译注：不用协调成本就很小）^[1]；在广泛的使用环境中，高可用系统的客户端不需要等待跨数据中心通信。为了正确地描述事务系统是否高度可用，我们需要描述客户端必须联系哪些服务器，以及服务器可以提供哪些类型的响应，尤其是考虑到中止的可能性。

传统上，如果能够与正确（无故障）的服务器通信的每个客户端最终都会收到来自该服务器的响应，即使服务器之间存在任意、无限长的网络分区^[35]，系统就会提供高可用性（High Availability）。就像在标准的分布式数据库中一样，特定的服务器可能会对不同的数据项执行操作。能够处理给定数据项操作的服务器称为该数据项的副本。

4.1 Sticky Availability

除了允许在任何副本上进行操作的高可用性之外，分布式算法通常假定一种模型，在该模型中，客户端总是在后续操作中与相同的逻辑副本通信，每个客户端之前的操作（但不一定是其他客户端的操作）都反映在它们观察到的数据库状态中。正如我们将在第5节中讨论的那样，客户端可以通过保持与服务器或服务器组的密切联系或“粘性”来确保操作之间的连续性（例如，读取之前对数据项的更新）^[64]。在完全复制的系统中，所有服务器都是所有数据项的副本，粘性很简单：客户机可以通过为其每个请求都请求到同一服务器上来保持粘性。然而，为了在部分复制系统中保持“粘性”，其中服务器是数据项集子集的副本（我们在本文中考虑），客户端必须保持与数据库的单个逻辑副本的粘性，其可以由多个物理服务器组成。我们对粘性可用性（sticky availability）的定义如下，如果每当客户端的事务操作（反映了客户机之前所有操作的）数据库状态副本执行时，它最终会收到响应，即使存在无限长的分区。（译注：在每个没有故障的节点上都可用，只要客户端只与相同的服务器通信，而不是切换到新的服务器。要求单个副本可以反映之前的所有操作。）。客户机可以选择通过充当服务器（译注：如缓存，自己给自己提供数据）来变得粘性可用；例如，客户机可能会缓存其读写操作^[11,60,67]。在高可用性系统中可以实现的任何保证都可以在粘性高可用性系统中实现，但反之亦然。（粘性可用性：每次请求都和同一个服务器通信，并且操作可以被响应）

4.2 Transactional Availability

到目前为止，我们一直在考虑单个对象、单个操作的可用性。这是分布式系统文献中的标准（例如，串行化的分布式注册模型都涉及单个对象^[41]），但数据库文献主要关注事务：多个对象上的多个操作组。因此，高可用性的传统定义本身不足以描述事务的可用性保证。此外，考虑到提交和中止响应的选择——它们向客户机发出事务成功或失败的信号——我们必须慎重定义事务可用性。

如果一个事务可以为它试图访问的每个数据项联系到至少一个副本，我们就说它具有副本可用性；这可能导致比非事务性可用性需求（例如，单个项目可用性）更“低可用性”。此外，考虑到系统启动的中止的可能性，我们需要确保有用的向前进展：系统可以通过总是中止所有事务来保证客户端的响应。然而，这是一个不令人满意的系统，因为从来没有好的（事务提交）发生过；我们需要一个liveness属性^[54]。

一个系统不能保证每个事务都会提交——事务可以选择自行中止，但我们需要确保系统不会自动随意地中止事务。由于事务自身的选择（例如，作为事务本身的操作或由于可能违反声明的完整性约束），我们将事务自身中止称为内部中止，而由于系统实现或操作而中止称为外部中止。我们说，如果给定事务中每个数据项的副本可用性，事务最终提交（可能在多次客户端重试后）或在内部中止，系统将提供事务可用性（Transactional availability）^[9]。如果给定粘性可用性，事务最终提交或在内部中止，系统将提供粘性事务可用性。（事务可用性：有副本可用性的事务可以最终提交或在内部中止）

5 Highly Available Transactions

HAT（Highly Available Transactions）系统为事务提供事务可用性或粘性事务可用性。与传统的分布式数据库相比，它们提供了延迟和可用性优势，但它们无法实现所有可能的语义。在本节中，我们将介绍ACID、分布式副本一致性和会话一致性级别，这些级别可以通过高可用性（读承诺隔离、可重复读的变体、原子读和许多会话保证）实现，也可以通过粘性可用性（读写、PRAM和因果一致性）实现。我们还讨论了HAT系统中无法提供的属性（防止更新丢失和写倾斜或保证最近性的属性）。我们在第5.3节中对这些结果进行了全面总结。

As Brewer states, “systems and database communities are separate but overlapping (with distinct vocabulary)” [16]. With this challenge in mind, we build on existing properties and definitions from the database and distributed systems literature, providing a brief, informal explanation and example for each guarantee. The database isolation guarantees require particular care, since different DBMSs often use the same terminology for different mech-anisms and may provide additional guarantees in addition to our implementation-agnostic definitions. We draw largely on Adya’s dissertation [2] and somewhat on its predecessor work: the ANSI SQL specification [5] and Berenson et al.’s subsequent critique [12].

正如布鲁尔所说，“系统和数据库社区是分开的，但相互重叠（具有不同的词汇表）”[16]。考虑到这一挑战，我们以数据库和分布式系统文献中的现有属性和定义为基础，为每个保证提供一个简短、非正式的解释和示例。数据库隔离保证需要特别小心，因为不同的DBMS通常对不同的机制使用相同的术语，除了我们的实现无关定义之外，还可能提供额外的保证。我们在很大程度上借鉴了Adya的论文[2]，并在一定程度上借鉴了它的前身工作：ANSI SQL规范^[5]和Berenson等人随后的评论^[12]。

For brevity, we provide an informal presentation of each guarantee here (accompanied by appropriate references) but give a full set of formal definitions in our extended Technical Report [8]. In our examples, we exclusively consider read and write operations, denoting a write of value v to data item d as wd(v) and a read from data item d returning v as rd(v). We assume that all data items have the null value, 􏰀, at database initialization, and, unless otherwise specified, all transactions in the examples commit.
为简洁起见，我们在此提供了每种担保的非正式陈述（附有适当的参考资料），但在我们的扩展技术报告中给出了一整套正式定义^[8]。在我们的例子中，我们专门考虑读取和写入操作，将数据v写入item为d的数据计为，并从数据项d中读取v作为。我们假设所有数据项都有空值，在数据库初始化时，除非另有规定，否则示例中的所有事务都会提交。

5.1 Achievable HAT Semantics

首先，我们介绍了可以在HAT系统中实现的众所周知的语义。在本节中，我们的主要目标是可行性，而不是性能。因此，我们提供了概念验证的高可用性算法，这些算法不一定是最优的，甚至不是高效的：挑战在于证明是否存在提供高可用性的算法。然而，我们在第6节中简要研究了它们的性能影响。

5.1.1 ACID Isolation Guarantees

首先，Adya将读取未提交隔离级别（Read Uncommited）定义为PL-1。在这个模型中，对每个对象的写入是完全有序的，与它们在数据库中的提交（译注：原文用installed）顺序相对应。在分布式数据库中，不同的副本可能会在不同的时间接收对其本地数据副本的写入，但应根据每个项目的总顺序处理并发更新（即覆盖）。PL-1要求在事务之间对不同对象的写入顺序一致，禁止Adya的G0现象（也称为“脏写入”^[12]）。如果我们构建一个从一个事务到另一个事务的边的事务图，并且在前者覆盖后者对同一对象的写入时，则在“读取未提交”隔离级别下，该图不应包含循环^[2]。考虑下面的例子：

在本例中，在“读取未提交”下，数据库不可能同时做到这种事：T1的排在T2的之前，但T2的在T1的之前（译注：两个事务内部操作不能交叉运行）。Read Uncommitted（读取未提交）通过使用相同的时间戳标记事务的每一次写入（在所有事务中都是唯一的；例如，将客户端ID与序列号结合起来作为事务id），并在每个副本上应用“last writer wins”（最后一个写入方获胜）冲突协调策略来轻松实现。以后的属性将加强读取未提交。

读提交隔离（Read Commited）在实践中尤其重要，因为它是许多DBMS的默认隔离级别（第3节）。集中式实现有所不同，一些基于长时间独占锁和短时间读锁^[38]，也有一些基于多个版本控制的。这些实现通常提供的最近性和单调性属性超出了名称“Read Committed”所暗示的内容，以及实现无关定义所捕获的内容：在Read Committed下，事务不应访问未提交或中间版本的数据项。这既禁止如上所述的“脏写”，也禁止“脏读”现象。这种隔离是Adya的PL-2，并通过禁止Adya的G1{a-c}（或ANSI的P1，或Berenson等人的“board”P1^[2.2]）而形式化。例如，在下面的示例中，T3不应该看到a=1，如果T2中止，T3不应该读取a=3：

HAT系统很容易防止“脏读”：如果每个客户端不将未提交的数据写入数据的共享副本，那么事务将永远不会读取彼此的脏数据。作为一个简单的解决方案，客户机可以缓存其写操作，直到它们提交，或者，也可以将它们发送到服务器，服务器在收到写操作已提交的通知之前不会将其值传递给其他读者（译者注：两阶段提交）。与基于锁的实现不同，此实现不提供最近性（recency）或单调性保证，但满足implementation-agnostic（译注：应该是实现不拘泥于某种技术的意思）的定义。

几个不同的属性被标记为可重复读取隔离（Repeatable Read）。正如我们将在第5.2.1节中所示，其中一些在HAT系统中无法实现。然而，ANSI标准化的实现不可知定义^[5]是可以实现的，它直接抓住了这个术语的精神：如果一个事务多次读取相同的数据，它每次都会看到相同的值（防止“模糊读取”，或P2）。在本文中，为了消除“可重复读取”的其他定义之间的歧义，我们将此属性称为“快照隔离（Cut Isolation）”，因为每个事务的读取都来自于数据项上的非更改版本或快照。如果这个属性保留了离散数据项（discrete data item）的读取，我们称之为数据项快照隔离（Item Cut Isolation），如果我们还期望基于谓词的读取（例如，select where；防止幻读^[38]，或Berenson等人的P3/A3），我们就有更强的谓词切割隔离属性。在下面的示例中，在两个快照隔离级别下，T3的读数必须为a=1：

通过让事务在客户端上存储任意读取数据的副本，以便它们为每个数据项读取的值永远不会更改，除非它们自己覆盖，这样就可以满足具有高可用性的item快照隔离。这些存储值可以在每个事务结束时丢弃，也可以通过多版本控制在（粘性）副本上完成。在HAT系统中，除了基于项的读取之外，还可以通过类似的缓存中间件或跟踪谓词整个逻辑范围的多版本控制来实现谓词快照隔离。

5.1.2 ACID Atomicity Guarantees

原子性是ACID保证的核心，它非正式地保证所有或任何事务的变动影响都会成功。尽管在ACID的首字母缩写中，原子性不是一个“隔离”属性，但原子性属性也会限制其他事务可见的更新。因此，在这里，我们考虑原子性的隔离效应，我们称之为Monotonic Atomic View(MAV) 隔离。在MAV下，一旦一个事务Ti的一些影响被另一个事务Tj观察到，此后，Ti的所有影响都被Tj观察到。也就是说，如果事务Tj读取事务Ti写入的对象的版本，那么由Tj稍后读取的对象无法返回由Ti写入的更新的版本（ if a transaction Tj reads a version of an object that transaction Ti wrote, then a later read by Tj cannot return a value whose later version is installed by Ti，译注：应该也是不存在上文所说的环）。与item快照隔离一起，MAV可以防止读取倾斜异常（Berenson等人的A5A），并且在多种情况下都很有用，例如维护外键约束、一致的全局二次索引和维护派生数据。在下面的示例中，在MAV下，由于T2已读取T1对y的写入，T2必须遵守b=c=1（或每个键的更高版本）：

T2也可以观察到a=null，a=1，或更高版本的x。在现有隔离性的层次结构中，我们将MAV置于Adya的PL-2L之下（因为它不一定强制要求可传递的读写依赖项），但置于读提交之上（PL−2)。 值得注意的是，MAV要求不允许读取中间写入（Adya的G1b）：隐含的意思是看到事务的所有影响意味着观察事务的最终（已提交）影响。

令人为难的是，现有的弱隔离方案中没有对MAV的讨论。这可能再次归因于之前开发工作的单节点环境：在单个服务器（或完全复制的数据库）上，可以通过轻量级锁定和/或对数据项的本地并发控制来实现MAV^[26,43]。相比之下，在分布式环境中，在高可用性的情况下，在任意组的非同址（non-co-located）数据项上实现MAV要困难得多。

作为straw man（稻草人？），副本可以存储写入每个数据项的所有版本。副本可以传播有关他们观察到的版本的信息，并对每个副本上可以找到的版本构造一个下限（可以用版本列表表示，或者更现实地说，用向量时钟表示）。在每个事务开始时，客户机可以选择一个小于或等于此全局下限（译注：小于或等于说明在此之前）的读取时间戳，并且在事务执行期间，副本返回每个项目的最新版本，该版本不大于客户机选择的时间戳。如果这个下限沿着事务边界向前推进，那么客户机将观察MAV。该算法在文献^[20,67]中有几个变体，旧版本可以异步垃圾收集。

We have developed a more efficient MAV algorithm, which we sketch（粗略，草图） here and provide greater detail in our extended Technical Report [8]. We begin with our Read Committed algorithm, but replicas wait to reveal（揭示、展示、表示） new writes to readers until all of the replicas for the final writes in the transaction have received their respective writes (are pending stable). Clients include additional metadata with each write: a single timestamp for all writes in the transaction (e.g., as in Read Uncommitted) and a list of items written to in the transaction. When a client reads, the return value’s timestamp and list of items form a lower bound on the versions that the client should read for the other items. When a client reads, it attaches a timestamp to its request representing the current lower bound for that item. Replicas use this timestamp to respond with either a write matching the timestamp or a pending stable write with a higher timestamp. Servers keep two sets of writes for each data item: the write with the highest timestamp that is pending stable and a set of writes that are not yet pending stable. This is entirely master-less and operations never block due to replica coordination.

我们开发了一种更高效的MAV算法，我们在这里对其进行了概述，并在扩展的技术报告^[8]中提供了更详细的信息。我们从读提交算法开始，但副本会等待事务中最终写操作的所有副本都已收到各自的写操作（待处理）之后才会向读请求方展示最新的写入。客户端在每次写入时都包含额外的元数据：事务中所有写入的单个时间戳（例如，在Read Uncommitted中）和事务中写入的项目列表。当客户机读取时，返回值的时间戳和项目列表构成了客户机应该为其他数据项读取的版本的下限（译注：不能读取比这个下限更低的数据，这个低可以理解为时效性低）。当客户端读取时，它会在其请求上附加一个时间戳，表示该项的当前下限。复制副本使用此时间戳响应与时间戳匹配的写操作，或者使用更高时间戳的挂起稳定写操作。服务器为每个数据项保留两组写操作：具有最高时间戳的写操作处于挂起稳定状态，以及一组尚未处于挂起稳定状态的写操作。这完全是无主的，而且由于副本协调，操作永远不会阻塞。

5.1.3 Session Guarantees

A useful class of safety guarantees refer to real-time or client-centric ordering within a session, “an abstraction for the sequence of...operations performed during the execution of an application” [60]. These “session guarantees” have been explored in the distributed systems literature [60, 64] and sometimes in the database literature [27]. For us, a session describes a context that should persist between transactions: for example, on a social networking site, all of a user’s transactions submitted between “log in” and “log out” operations might form a session.

Several session guarantees can be made with high availability:

一类有用的安全保障是指会话中的实时或以客户端为中心的排序，Session: “应用程序执行期间执行的操作序列的抽象”^[60]。分布式系统文献^[60,64]和数据库文献^[27]中都探讨了这些“会话保证”。对我们来说，会话描述了一个应该在事务之间保持的上下文：例如，在社交网站上，用户在“登录”和“注销”操作之间提交的所有事务都可能形成一个会话。

在高可用性的情况下，可以提供几种会话保证：

Monotonic reads requires that, within a session, subsequent reads to a given object “never return any previous values”; reads from each item progress according to a total order (e.g., the order from Read Uncommitted).

Monotonic writes requires that each session’s writes become visible in the order they were submitted. Any order on transactions (as in Read Uncommitted isolation) should also be consistent with any precedence that a global observer would see.

Writes Follow Reads requires that, if a session observes an effect of transaction T1 and subsequently commits transaction T2, then another session can only observe effects of T2 if it can also observe T1’s effects (or later values that supersede T1’s); this corresponds to Lamport’s “happens-before” relation [46]. Any order on transactions should respect this transitive order.

单调读（Monotonic reads）要求在会话中，对给定对象的后续读取“从不返回任何以前的值”；根据全局顺序（例如，读取未提交的顺序）读取每个item。

单调写（Monotonic writes）要求每个会话的写入内容按照提交顺序可见。事务的任何顺序（如在Read Uncommitted isolation中）也应该与全局观察者看到的任何优先级一致。

写后读（Writes Follow Reads ）要求，如果一个会话观察到事务T1的影响并随后提交事务T2，那么另一个会话只能观察到T2的影响，如果它也能观察T1的影响（或观察到取代T1的后续值）；这对应于lamport的“happens-before”关系[46]。任何事务顺序都应遵守此传递顺序。

The above guarantees can be achieved by forcing servers to wait to reveal（展示） new writes (say, by buffering them in separate local storage) until each write’s respective dependencies are visible on all replicas. This mechanism effectively ensures that all clients read from a globally agreed upon lower bound on the versions written. This is highly available because a client will never block due to inability to find a server with a sufficiently（充分的，足够的） up-to-date version of a data item. However, it does not imply that transactions will read their own writes or, in the presence of partitions, make forward progress through the version history. The problem is that under non-sticky availability, a system must handle the possibility that, under a partition, an unfortunate client will be forced to issue its next requests against a partitioned, out-of-date server.

可以通过强制服务器等待显示新的写入（例如，通过在独自的本地存储中缓冲这些写入），直到每个写入各自的依赖关系在所有副本上都可见，从而实现上述保证。这种机制有效地确保所有客户机都能从全局一致同意的版本下限中读取所编写的版本。这是高度可用的，因为客户端永远不会因为无法找到具有足够最新版本的数据项的服务器而阻塞。然而，这并不意味着事务将读取它们自己的写操作，或者在存在分区的情况下，在版本历史中向前推进。问题是，在非粘性可用性的情况下，系统必须处理这样一种可能性：在分区下，一个不幸的客户端将被迫对一个分区的过时服务器发出下一个请求。

A solution to this conundrum（难题，令人迷惑的难题） is to forgo（放弃、停止） high availability and settle for sticky availability. Sticky availability permits three additional guarantees, which we first define and then prove are unachievable in a generic highly available system:
Read your writes requires that whenever a client reads a given data item after updating it, the read returns the updated value (or a value that overwrote the previously written value).
PRAM (Pipelined Random Access Memory) provides the illusion（幻觉、错觉） of serializing each of the operations (both reads and writes) within each session and is the combination of monotonic reads, monotonic writes, and read your writes [41].
Causal consistency [3] is the combination of all of the session guarantees [17] (alternatively, PRAM with writes-follow-reads) and is also referred to by Adya as PL-2L isolation [2]).
Read your writes is not achievable in a highly available system. Consider a client that executes the following two transactions:

解决这个难题的一个办法是放弃高可用性，而满足于粘性可用性。粘性可用性允许三个额外的保证，我们首先定义，然后证明在通用的高可用性系统中是无法实现的：

读所写（Read your writes）要求当客户端在更新给定数据项后读取该数据项时，读取返回更新后的值（或重写以前写入的值的值）。

流水线RAM（Pipelined Random Access Memory）提供在每个会话中序列化每个操作（读取和写入）的错觉，是单调读取、单调写入和读写操作的组合^[41]。

因果一致性（Causal consistency）是所有会话保证^[17]的组合（或者，PRAM具有写跟随读），Adya也将其称为PL-2L隔离[2]）。

在高可用性系统中无法实现Read your writes。考虑执行以下两个事务的客户端：

如果客户端对与其他服务器分区的服务器执行T1，那么为了事务可用性，服务器必须允许T1提交。如果同一客户机随后在同一会话中对同一（分区的）服务器执行T2，那么它将能够读取其写操作。但是，如果网络拓扑发生变化，并且客户端只能在与执行T1的副本分区的另一个副本上执行T2，那么系统将不得不无限期暂停以允许客户端读取它的写入（违反事务可用性），或者必须牺牲读写保证。但是，如果客户机与执行T1的服务器保持粘性，那么我们可以禁止这种情况。因此，read your write，通过代理，因果一致性和PRAM需要粘性。在粘性系统中，默认情况下会提供read your write。因果关系和PRAM保证可以通过我们之前介绍的会话保证算法的著名变体^{[3,11,48,60,67]}来实现：只有在客户机（各自的、特定于模型的）依赖关系被展示时，才向客户机展示新的写入。

5.1.4 Additional HAT Guarantees

In this section, we briefly discuss two additional kinds of guarantees that are achievable in HAT systems.
Consistency A HAT system can make limited application-level consistency guarantees. It can often execute commutative and logically monotonic [4] operations without the risk of invalidating application-level integrity（正直、诚实、完整） constraints and can maintain limited criteria（标准、准则、尺度） like foreign key constraints (via MAV). We do not describe the entire space of application-level consistency properties that are achievable (see Section 7) but we specifically evaluate TPC-C trans- action semantics with HAT guarantees in Section 6.

Convergence Under arbitrary (but not infinite delays), HAT systems can ensure convergence, or eventual consistency: in the absence of new mutations（变异） to a data item, all servers should eventually agree on the value for each item [49, 64]. This is typically accomplished by any number of anti-entropy protocols, which periodically update neighboring servers with the latest value for each data item [31]. Establishing a final convergent value is related to determining a total order on transaction updates to each item, as in Read Uncommitted.

在本节中，我们将简要讨论在HAT系统中可以实现的另外两种保证。

一致性（Consistency）。HAT系统可以提供有限的应用程序级一致性保证。它通常可以执行交换的和逻辑上单调的^[4]操作，而不存在使应用程序级完整性约束失效的风险，并且可以维护有限的标准，如外键约束（通过MAV）。我们没有描述可实现的应用程序级一致性属性的整个空间（参见第7节），但我们在第6节中具体评估了TPC-C事务语义和HAT保证。

收敛（Convergence）。在任意（但不是无限延迟）的情况下，HAT系统可以确保收敛，或最终的一致性：在一个数据项没有新的突变的情况下，所有服务器最终应该就每个数据项的值达成一致^[49,64]。这通常由任意数量的反熵协议来实现，这些协议定期用每个数据项的最新值更新相邻服务器^[31]。建立最终收敛值与确定每个项目的事务更新的总顺序有关，如Read Uncommitted。

5.2 Unachievable HAT Semantics

While there are infinitely many HAT models (Section 7), at this point, we have largely exhausted the range of achievable, previously defined (and useful) semantics that are available to HAT systems. Before summarizing our possibility results, we will present impossibility results for HATs, also defined in terms of previously identified isolation and consistency anomalies. Most notably, it is impossible to prevent Lost Update or Write Skew in a HAT system.

虽然有无限多的HAT模型（第7节），但在这一点上，我们已经基本上耗尽了可用于HAT系统的可实现的、先前定义的（和有用的）语义范围。在总结我们的可能性结果之前，我们将给出HATs的不可能性结果，也根据之前确定的隔离和一致性异常进行定义。最值得注意的是，在HAT系统中不可能防止更新丢失或写倾斜。

5.2.1 Unachievable ACID Isolation

In this section, we demonstrate（证明、示范、展示） that preventing Lost Update and Write Skew—and therefore providing Snapshot Isolation, Repeatable Read, and one-copy serializability—inherently（固有的，本身的） requires foregoing（前述的，前面的） high availability guarantees.

在本节中，我们将演示如何防止更新丢失和写倾斜，从而提供快照隔离、可重复读取和单拷贝可序列化性，这本身就需要前面提到的高可用性保证。

Berenson et al. define Lost Update as when one transaction T 1 reads a given data item, a second transaction T 2 updates the same data item, then T 1 modifies the data item based on its original read of the data item, “missing” or “losing” T 2’s newer update. Consider a database containing only the following transactions:

Berenson等人将更新丢失（Lost Update）定义为当一个事务T1读取给定数据项时，第二个事务T2更新相同的数据项，然后T1根据其对数据项的原始读取修改数据项，“错过”或“丢失”T2的更新。考虑只包含以下事务的数据库：

If T1 reads a = 1 but T2’s write to x precedes（领先，先于） T1’s write operation, then the database will end up with a = 3, a state that could not have resulted in a serial execution due to T2’s “Lost Update.”

如果T1读取a=1，但T2对x的写操作先于T1的写操作，数据库将以a=3结束，由于T2的“丢失更新”，这种状态不可能是串行执行。

It is impossible to prevent Lost Update in a highly available environment. Consider two clients who submit the following T1 and T2 on opposite sides of a network partition:

在高可用性环境中，不可能防止更新丢失。考虑在处在不同网络分区的两个客户端提交以下T1和T2：

Regardless of whether x = 120 or x = 130 is chosen by a replica, the database state could not have arisen（出现，升起） from a serial execution of T1 and T2.4 To prevent this, either T1 or T2 should not have committed. Each client’s respective server might try to detect that another write occurred, but this requires knowing the version of the latest write to x. In our example, this reduces to a requirement for linearizability, which is, via Gilbert and Lynch’s proof of the CAP Theorem, provably at odds with high availability [35].

无论副本选择的是x=120还是x=130，数据库状态都不可能由T1和T2的串行执行产生。为了防止这种情况发生，T1或T2都不应该提交。每个客户端各自的服务器可能尝试检测到发生了另一次写入，但这需要知道对x的最新写入的版本。在我们的示例中，这就降低了对线性化的要求，即通过Gilbert和Lynch对CAP定理的证明，可证明与高可用性不符^[35]。

Write Skew is a generalization of Lost Update to multiple keys. It occurs when one transaction T1 reads a given data item x, a second transaction T 2 reads a different data item y, then T 1 writes to y and commits and T 2 writes to x and commits. As an example of Write Skew, consider the following two transactions:

写倾斜（Write Skew）是对多个键更新丢失的概括。当一个事务t1读取给定的数据项x，第二个事务t2读取不同的数据项y，然后t1写入y并提交，t2写入x并提交时，就会发生这种情况。作为写倾斜的一个例子，考虑下面两个事务：

As Berenson et al. describe, if there was an integrity constraint between x and y such that only one of x or y should have value 1 at any given time, then this write skew would violate the constraint (which is preserved in serializable executions). Write skew is a somewhat esoteric anomaly—for example, it does not appear in TPC-C [34]—but, as a generalization of Lost Update, it is also unavailable to HAT systems.

正如Berenson等人所描述的，如果x和y之间存在完整性约束：使得在任何给定的时间，x或y中只有一个值为1，那么这种写倾斜将违反该约束（在可序列化执行中保留）。写倾斜是一种有点深奥的异常现象，例如，它没有出现在TPC-C[34]中，但作为丢失更新的推广，它也不适用于HAT系统。

Consistent Read, Snapshot Isolation (including Parallel Snapshot Isolation [59]), and Cursor Stability guarantees are all unavailable because they require preventing Lost Update phenomena. Repeatable Read (defined by Gray [38], Berenson et al. [12], and Adya [2]) and One-Copy Serializability [6] need to prevent both Lost Update and Write Skew. Their prevention requirements mean that these guarantees are inherently unachievable in a HAT system.

一致读取、快照隔离（包括并行快照隔离[59]）和Cusor Stability保证都不可用，因为它们需要防止丢失更新现象。可重复读取（由Gray[38]、Berenson等人[12]和Adya[2]定义）和单拷贝序列化[6]需要防止丢失更新和写入倾斜。它们的预防要求意味着这些保证在HAT系统中本质上是无法实现的

5.2.2 Unachievable Recency Guarantees

Distributed data storage systems often make various recency guarantees on reads of data items. Unfortunately, an indefinitely long partition can force an available system to violate（违反，侵犯，打扰）any recency bound, so recency bounds are not enforceable by HAT systems [35]. One of the most famous of these guarantees is linearizability [41], which states that reads will return the last completed write to a data item, and there are several other (weaker) variants such as safe and regular register semantics. When applied to transactional semantics, the combination of one-copy serializability and linearizability is called strong (or strict) one-copy serializability [2] (e.g., Spanner [25]). It is also common, particularly in systems that allow reading from masters and slaves, to provide a guarantee such as “read a version that is no more than five seconds out of date” or similar. None of these guarantees are HAT-compliant.

分布式数据存储系统通常对数据项的读取做出各种最近保证（recency guarantees）。不幸的是，无限长的分区可能会迫使可用系统违反任何近邻界限（recency bound），因此近邻界限不能由HAT系统强制执行^[35]。这些保证中最著名的一个是线性化（linearizability）^[41]，它表示读取将返回对数据项最后完成的写入，还有其他几个（较弱的）变体，如安全和常规寄存器语义。当应用于事务语义时，单拷贝可序列化性（one-copy serializability）和线性化性（linearizability）的组合称为强（或严格）单拷贝可序列化性^[2]（例如，Spanner^[25]）。它也很常见，尤其是在允许从主设备和从设备读取数据的系统中，提供诸如“读取过期不超过5秒的版本”或类似的保证。这些保证都不符合HAT标准。

5.2.3 Durability

A client requiring that its transactions’ effects survive F server faults requires that the client be able to contact at least F + 1 non-failing replicas before committing. This affects availability and, according to the Gilbert and Lynch definition we have adopted, F > 1 fault tolerance is not achievable with high availability.

如果客户机要求其事务的影响在F个服务器故障后仍然有效，则要求客户机在提交前至少能够联系F+1无故障副本。这会影响可用性，根据我们采用的Gilbert和Lynch定义，高可用性无法实现F>1容错。

5.3 Summary

As we summarize in Table 3, a wide range of isolation levels are achievable in HAT systems. With sticky availability, a system can achieve read your writes guarantees and PRAM and causal consistency. However, many other prominent semantics, such as Snapshot Isolation, One-Copy Serializability, and Strong Serializability cannot be achieved due to the inability to prevent Lost Update and Write Skew phenomena.

正如我们在表3中总结的那样，在HAT系统中可以实现广泛的隔离级别。有了粘性可用性，系统可以实现读写保证、PRAM和因果一致性。然而，由于无法防止丢失更新和写倾斜现象，许多其他突出的语义，例如快照隔离、单拷贝可序列化性和强可序列化性，都无法实现。

We illustrate（说明，举例说明，插图说明） the hierarchy of available, sticky available, and unavailable consistency models we have discussed in Figure 2. Many models are simultaneously（同时地） achievable, but we find several particularly compelling. If we combine all HAT and sticky guarantees, we have transactional, causally consistent snapshot reads (i.e., Causal Transactional Predicate Cut Isolation). If we combine MAV and P-CI, we have transactional snapshot reads. We can achieve RC, MR, and RYW by simply sticking clients to servers. We can also combine unavailable models—for example, an unavailable system might provide PRAM and One-Copy Serializability [27].

我们展示了图2中讨论的可用、粘性可用和不可用一致性模型的层次结构。许多模型都可以同时实现，但我们发现有几个模型特别引人注目。如果我们将所有的HAT和sticky保证结合起来，我们就有了事务性的、因果一致的快照读取（即因果事务谓词切割隔离）。如果我们将MAV和P-CI结合起来，就可以进行事务性快照读取。我们可以通过简单地将客户端粘贴到服务器上来实现RC、MR和RYW。我们还可以组合不可用的模型，例如，一个不可用的系统可能会提供PRAM和单拷贝序列化功能^[27]。

To the best of our knowledge, this is the first unification（联合、一致） of transactional isolation, distributed consistency, and session guarantee models. Interestingly, strong one-copy serializability entails all other models, while considering the (large) power set of all compatible models (e.g., the diagram depicts 144 possible HAT combinations) hints at the vast expanse of consistency models found in the literature. This taxonomy（分类学） is not exhaustive（详尽的，彻底的） (Section 8), but we believe it lends substantial clarity to the relationships between a large subset of the prominent ACID and distributed consistency models. Additional read/write transaction semantics that we have omitted should be classifiable based on the available primitives and HAT-incompatible anomaly prevention we have already discussed.

据我们所知，这是事务隔离、分布式一致性和会话保证模型的首次统一。有趣的是，强大的单拷贝序列化能力需要所有其他模型，而考虑到所有兼容模型的（大）幂集（例如，图表描绘了144种可能的HAT组合），这暗示了文献中发现的大量一致性模型。这种分类法并非详尽无遗（第8节），但我们认为，它极大地澄清了重要的ACID和分布式一致性模型之间的关系。我们省略的其他读/写事务语义应该可以根据我们已经讨论过的可用原语和HAT不兼容异常预防进行分类。

In light the of current practice of deploying weak isolation levels (Section 3), it is perhaps surprising that so many weak isolation levels are achievable as HATs. Indeed, isolation levels such as Read Committed expose and are defined in terms of end-user anomalies that could not arise during serializable execution. However, the prevalence of these models suggests that, in many cases, applications can tolerate these their associated anomalies（异常现象）. Given our HAT compliance results, this in turn hints that–despite idiosyncrasies（特质、个性） relating to concurrent updates and data recency–highly available database systems can provide sufficiently strong semantics for many applications. Indeed, HAT databases may expose more anomalies than a single-site database operating under weak isolation (particularly during network partitions). However, for a fixed isolation level (which, in practice, can vary across databases and may differ from implementation-agnostic definitions in the literature), users of single-site database are subject to the same (worst-case) application-level anomalies as a HAT implementation. The necessary (indefinite) visibility penalties (i.e., the right side of Figure 2) and lack of support for preventing concurrent updates (via the upper left half of Figure 2) mean HATs are not well-suited for all applications (see Section 6): these limitations are fundamental. However, common practices such as ad-hoc, user-level compensation and per-statement isolation “upgrades” (e.g., SELECT FOR UPDATE under weak isolation)—commonly used to augment weak isolation—are also applicable in HAT systems (although they may in turn compromise availability).

鉴于目前部署弱隔离级别的实践（第3节），可能令人惊讶的是，有这么多弱隔离级别可以像HATs一样实现。实际上，隔离级别（如Read Committed expose和？）是根据在可序列化执行期间不会出现的最终用户异常来定义的。然而，这些模型的流行表明，在许多情况下，应用程序可以容忍这些异常及其相关异常。鉴于我们的HAT-compliance结果，这反过来暗示，尽管存在与并发更新和数据更新相关的特性，但高可用性数据库系统可以为许多应用程序提供足够强的语义。事实上，HAT数据库可能会暴露更多异常，相比于在弱隔离（尤其是在网络分区期间）下运行的单站点数据库。然而，对于固定隔离级别（在实践中，不同数据库的隔离级别可能不同，并且可能不同于文献中的实现无关定义），单站点数据库的用户与HAT实现的应用程序级别异常情况相同（最坏情况）。必要的（不确定的）可见性惩罚（即图2的右侧）以及缺乏防止并发更新的支持（通过图2的左上半部分），意味着HATs并不适合所有应用程序（参见第6节）：这些限制是根本性的。然而，通常用于增强弱隔离的常用做法，如ad-hoc、用户级补偿和per-statement隔离“upgrades”（例如，在弱隔离性下SELECT FOR UPDATE ），也适用于HAT系统（尽管它们可能反过来损害可用性）。

image.png