2014年2月18日
第12卷，第1期

  PDF

最终一致性：并非您所期望的那样？

量化最终一致性存储系统中一致性（或缺乏一致性）的方法

Wojciech Golab，滑铁卢大学
Muntasir R. Rahman，伊利诺伊大学厄巴纳分校厄巴纳-香槟分校
Alvin AuYoung，惠普实验室，帕洛阿尔托
Kimberly Keeton，惠普实验室，帕洛阿尔托
Xiaozhou (Steve) Li，谷歌

存储系统继续为现代互联网服务（如网络搜索、电子商务和社交网络）奠定基础。用户群和数据集的快速增长带来的压力，已推动系统设计从传统的集中式数据库转向更具可扩展性的分布式解决方案，包括简单的 NoSQL键值存储系统，以及更精细的 NewSQL 数据库，这些数据库支持大规模事务。

分布式键值存储系统是现代存储生态系统中最简单和最具可扩展性的范例之一。此类系统放弃了传统数据库的许多奢侈功能，包括 ACID（原子性、一致性、隔离性、持久性）事务、连接和引用完整性约束，但保留了表和索引等基本抽象。因此，应用程序开发人员无需关注规范化关系模式、选择最佳事务隔离级别以及处理死锁等技术细节。

尽管分布式键值存储系统具有简单的接口和数据模型，但其内部结构却很复杂，因为它们必须在两个或多个服务器上复制数据，以在面对节点或网络故障时实现更高的读取性能和更高的可用性。保持这些副本同步需要分布式复制协议，这可能会给存储操作增加大量延迟，尤其是在地理复制系统中。具体而言，写入操作必须更新一部分副本，系统才能向客户端确认写入完成；而读取操作可能会从一部分副本中获取数据，并采用观察到的最新值（例如，具有最高时间戳的值）作为响应。

事实证明，选择联系哪些副本子集进行存储操作，会对分布式存储系统的行为产生深远的影响。对于强一致性，客户端可以读取和写入大多数副本。由于大多数副本存在重叠，这确保了每次读取都能“看到”最新的写入。相比之下，最终一致性系统可能会读取和写入非重叠的子集。^26,28 一旦写入被确认，新值就会传播到其余副本；因此，除非发生故障，否则所有副本最终都会更新。与此同时，如果读取器从尚未收到更新的副本中获取数据，则可能会观察到陈旧的值。

尽管许多应用程序受益于强一致性，延迟敏感型应用程序（如电子商务网站中的购物车）选择最终一致性以获得更低的延迟。¹ 这可能会导致一致性异常，例如购物车中的商品丢失或超卖。但是，由于用户可以在结账期间检测并纠正问题，因此只要这些异常是短暂的且不频繁的，就可以容忍。因此，应用程序开发人员和系统管理员的关键任务是了解一致性和延迟如何受到各种存储和应用程序配置参数以及应用程序对存储系统施加的工作负载的影响。只有对这个微妙的问题有适当的了解，管理员和开发人员才能就存储系统的配置或给定应用程序的一致性模型的选择做出明智的决策。

本文着眼于量化最终一致性存储系统中一致性（或缺乏一致性）的方法。这些方法对于在不同的系统配置和工作负载之间进行有意义的比较是必要的。首先，本文更精确地定义了最终一致性，并将其与其他弱一致性概念联系起来。然后，深入探讨指标，重点关注陈旧性，并调查了预测和测量陈旧性的不同技术。最后，评估了这些技术的相对优点，并确定了任何剩余的未决问题。

最终一致性的定义

最终一致性可以定义为底层存储系统的属性，也可以定义为客户端应用程序观察到的行为。例如，Doug Terry 等人在 Bayou 存储系统的上下文中给出了最终一致性的以下定义：“所有副本最终都会收到所有写入（假设有足够的网络连接和合理的协调计划），并且任何两个收到相同写入集的副本都具有相同的数据库。”²⁶ 这个非正式的定义既涉及写入到副本的传播（即最终），又涉及收敛到一个明确定义的 状态—例如，通过例如，通过基于时间戳的 协调—（即，一致性）。

这个定义虽然简单而优雅，但并没有精确地说出客户端观察到了什么。相反，它涵盖了一系列行为，既包括强一致性的关系数据库，也包括可能无限期返回陈旧或乱序数据的弱一致性系统。相比之下，

Werner Vogels 以具体的方式描述了客户端观察到的一致性：“存储系统保证，如果没有对对象进行新的更新，最终所有访问都将返回最后更新的值。”²⁸ Vogels 的定义以直观的方式捕捉了副本收敛到最后更新值的过程，但仅在更新暂停而客户端读取对象的特殊情况下—这种情况与许多最终一致性系统部署的在线环境截然不同。

由于弱一致性难以推理，应用程序开发人员通常会寻求更强的属性，例如一致前缀、单调读取、“读己之写”或因果一致性。²⁵ 事实上，一些系统支持此类强于最终属性（例如，COPS [有序服务器集群²²] 和 Pileus²⁷），但 Amazon 的 Dynamo¹² 等系统的商业成功证明，最终一致性在实践中已经足够好。为了理解原因，研究人员试图用比 Terry 等人和 Vogels 风格的抽象定义更精确的术语来描述最终一致性系统的行为范围。目前在这方面的研究方法分为三类：宽松一致性指标、系统建模和预测以及经验测量工具。接下来的三节将调查每个类别的代表性工作。

宽松一致性属性

最终一致性的抽象定义对并发访问以及易出错环境中的系统行为留下了一些疑问。例如：更新在实践中传播到副本的速度有多快，副本在对象最新值上达成一致的频率有多高？当副本不一致时，这对客户端的数据视图有何影响？在分割网络的扩展故障期间，或在网络修复后不久，客户端究竟观察到了什么？

描述这些行为的一种新兴方法是将它们与称为线性化¹⁸的严格一致性形式联系起来。通俗地说，此属性声明存储系统的行为就好像它一次执行一个操作，按某种串行顺序，尽管实际上并行执行某些操作。稍后将解释，此串行顺序受到进一步约束，以禁止陈旧读取。因此，线性化是最终一致性系统可以据此判断的合适的黄金标准。换句话说，观察到的行为可以用偏离此标准的偏差来描述，在这种情况下，偏差可以被视为一致性违规。例如，当读取返回陈旧值时，即使系统仅承诺最终一致性，也可以将 Amazon 的 Dynamo 视为违反了线性化。

虽然线性化在集中式系统中很常见—例如，在多线程数据结构中—Brewer 的CAP 原则⁹指出，在始终可用(A) 和分区容错(P) 分布式系统中，无法实现如此强的 一致性属性 (C)。（数据库专家应在此上下文中将一致性理解为事务隔离。）因此，人们不能期望任何存储系统在网络分区期间接受更新并保持一致性。尽管这并不排除在无故障操作期间的强一致性，但即使在这种情况下，系统也可能配置为牺牲一致性以获得更好的延迟。¹ 例如，在 Cassandra存储中，客户端可以通过请求各种“一致性级别”来实现这种键值权衡，这些级别控制响应读取或写入的副本数量。²⁰削弱一致性的副作用是陈旧性增加，到目前为止，这一点已非正式地讨论过。更准确地说，从值写入存储系统的那一刻起，直到它被覆盖，该值被认为是新鲜的，此后则为陈旧的。因此，陈旧性描述了读取返回的值相对于最后更新值的年龄，从而量化了系统行为偏离黄金标准的程度。文献中讨论了对该概念的两种解释，^2,15 源于定义“年龄”的不同方式

• 基于版本的陈旧性通过计算对象的版本来定义年龄（例如，读取返回第 k 个最新版本）。

• 基于时间的陈旧性以

挂钟时间来定义年龄（例如，读取返回的值比最后更新的值旧 t 个时间单位）。陈旧性的概念虽然直观，但充满了技术上的微妙之处。在操作一次执行一个的简单情况下，客户端期望这些操作生效的自然顺序，因此可以轻松识别陈旧读取。但是，当操作并行执行时，从客户端的角度来看，它们的顺序可能很难确定。

为了理解最终一致性，我们转向宽松一致性

属性—k-原子性和Δ-原子性—这 些属性精确地解释了基于版本的Δ-原子性—这基于时间的陈旧性的概念。这两个属性都是线性化¹⁸的宽松形式，但出于历史原因，它们的名称指的是 Lamport 的原子性属性²¹，这在精神上是相似的。

线性化（“黄金标准”）

考虑图 1a 中的操作跟踪，其中显示了应用于对象 X 的三个操作。首先，写入操作 W(X,1) 将 1 分配给对象 X，然后此值通过第二个写入操作 W(X,2) 更新为 2。第三个操作 R(X) 是对 X 的读取，并在两个写入操作结束后开始。在这种情况下，线性化规定 W(X,1) 应显示在 W(X,2) 之前生效，因为 W(X,1) 在 W(X,2) 开始之前结束。因此，当应用 R(X) 时，2 是 X 的最后更新值，但 R(X) 返回 1，因此跟踪不是线性化的。当操作在时间上重叠时，更复杂的情况在线性化的正式定义¹⁸中得到解决，本文对此不再赘述。

K-原子性（基于版本的陈旧性）

k-原子性 属性由 Amitanand Aiyer 等人引入。² 与线性化一样，它要求操作看起来以受其开始和结束时间约束的顺序生效；但是，在此顺序内，读取可以返回任何最后更新值的 k 个。例如，图 1a 中显示的跟踪对于 k = 2 是k-原子的 ，但对于 k = 1 则不是。Δ-原子性（基于时间的陈旧性）

Δ-原子性

k-原子性属性由 Wojciech Golab 等人提出。¹⁵ 类似于k-原子性， 它通过允许读取返回陈旧值来放松线性化。但是，陈旧性是根据时间定义的：读取可能会返回最多 Δ 时间单位的陈旧值。例如，如果 Δ 定义为 W(X,2) 和 R(X) 之间的间隙宽度，则图 1a 中的跟踪是Δ-原子的。如果两个操作在时间上重叠，如图 1b 所示，则线性化允许 R(X) 在 W(X,2) 之前生效，而在线性化中，它要求 R(X) 在 W(X,2) 之后生效。如果假设将 R(X) 向左“拉伸” Δ 时间单位（即，如果 R(X) 早 Δ 时间单位开始），如图 1b 所示，则跟踪变为线性化的。因此，在图 1a 中，R(X) 的响应仅被视为陈旧 Δ 时间单位。预测

用于表征最终一致性的另一种方法是基于系统建模和预测的组合。Peter Bailis 等人⁶提出了 PBS（概率有界陈旧性）框架，其中提出了

白盒系统模型来预测客户端应用程序观察到的数据陈旧性。PBS 模型估计 <k,t>陈旧性的概率—条件是读取（在写入结束后 t 个时间单位开始）返回由最后 k 次写入之一分配的值。此条件类似于，但仅考虑在距写入固定距离 t 处的单次读取。当 k = 1 时，它捕获读取返回最新值（即，不陈旧）的概率。 属性由 Amitanand Aiyer 等人引入。² 与线性化一样，它要求操作看起来以受其开始和结束时间约束的顺序生效；但是，在此顺序内，读取可以返回任何最后更新值的 k 个。例如，图 1a 中显示的跟踪对于 k = 2 是PBS 模型做出了两个简化的假设。首先，与 Vogels 对最终一致性的定义²⁸一样，PBS 不考虑写入在时间上与读取重叠的工作负载，在这种情况下，写入和读取之间间隙的宽度 t 没有明确定义。其次，PBS 没有显式地对故障进行建模。尽管可以使用更长的延迟来模拟存储节点故障，但 PBS 不考虑网络分区。

后续工作¹¹通过考虑节点故障来扩展 PBS 模型。经验测量

到目前为止，本文已经讨论了量化最终一致性系统中陈旧性的技术。本节讨论从系统和客户端的角度经验性地测量一致性的方法。

在“野外”测量最终一致性与精确定义它一样困难。并发操作使得难以识别操作生效的顺序，因此难以将读取分类为陈旧或不陈旧。更糟糕的是，在发生网络分区时，即使在某个时间点之后没有对对象进行新的更新，划分两侧的客户端也可能观察到不同的最后更新值。这种异常是可能的，因为在始终可用的系统中，每个分区都将继续接受写入。

尽管存在这些挑战，但仍设计了许多技术来测量最终一致性，特别是数据陈旧性。本文着眼于两种根本不同的方法：主动测量，其中以人为方式练习存储系统，以确定从新值写入存储系统到客户端可见该值的时间滞后；以及被动分析，其中记录任意工作负载的操作跟踪，并进行数学分析以获得陈旧性测量值。

主动测量

主动测量是云存储系统中一致性早期研究的基础。在此类技术中，一个客户端将新值写入键，然后另一个客户端重复读取同一键，直到返回新值。与 Vogels 的最终一致性定义²⁸一样，在这种情况下，写入在时间上不与读取重叠。从写入到返回旧

值—或值的最后一次读取—或者，新值的第一次读取—值—回答了问题，“最终到什么程度？”，并且可以被视为复制协议的收敛时间的估计—将新值传播到对象的所有副本所需的时间。

在技术层面上，主动测量的主要挑战是确定在不同客户端节点—即写入和读取—上执行的操作之间的时间差。图 2 说明了如何使用客户端集合计算此差异。为了精确捕获最后一个副本接收更新值的时间，Hiroshi Wada 等人使用一个或多个客户端每秒应用 50 次读取。²⁹ Bermbach 等人更进一步，使用地理上分布的读取器集合来确保读取命中所有可能的副本。⁸

YCSB++（Yahoo!云服务基准）²³中的陈旧性测量遵循类似的方法，但使用 ZooKeeper生产者-消费者队列¹⁹来同步写入器和读取器。这种方法规避了与时钟偏差相关的问题，但引入了队列操作造成的额外延迟，这可能会限制精度。

主动测量可用于发现最终一致性系统中更新传播时间的范围。例如，在涉及 Amazon 的 SimpleDB⁴ 的实验中，Wada 等人报告称，超过 90% 的运行中收敛发生在最多一秒内，但在少数（不到 1%）情况下花费了超过四秒。另一方面，主动测量并未表明真实工作负载中读取返回陈旧值的比例，因为此数量取决于数据对象的访问方式。例如，陈旧读取的比例预计会随着应用于给定对象的操作速率而变化—当操作不频繁应用且它们之间的间隔超过收敛时间时，接近于零；当读取更紧密地跟随写入时，则更大。主动测量不会区分这两种情况，因为它基于旨在测量收敛时间的受控工作负载。

被动分析

在前面关于宽松一致性属性的部分中，讨论重点关注以精确和有意义的方式定义陈旧性的方法，并提供了如何从这些定义中导出一致性指标的提示。它从“非黑即白”一致性属性开始，例如线性化，系统或执行跟踪要么满足线性化，要么不满足线性化；接下来，通过引入一个参数来放松此属性，该参数限制了读取的陈旧性（例如，Δ-原子性）；最后一步是确定最准确地描述系统行为的参数值（例如，。如果两个操作在时间上重叠，如图 1b 所示，则线性化允许 R(X) 在 W(X,2) 之前生效，而在线性化中，它要求 R(X) 在 W(X,2) 之后生效。如果假设将 R(X) 向左“拉伸” Δ 时间单位（即，如果 R(X) 早 Δ 时间单位开始），如图 1b 所示，则跟踪变为线性化的。因此，在图 1a 中，R(X) 的响应仅被视为陈旧 Δ 时间单位。对于 ≥ 10 毫秒）。被动分析指的是最后一步，它需要检查执行跟踪中记录的操作，以确定它们看起来生效的顺序。

被动分析中最直接的技术挑战是跟踪的收集，该跟踪记录每个操作的类型、开始和结束时间，以及其参数和响应（例如，读取对象 X，在时间 t₁ 开始并在 t₂ 结束，返回值为 5）。此跟踪可以在客户端获得，如图 2 所示。

由于跟踪是通过合并来自多个客户端或存储节点在有限时间段内的数据而获得的，因此它容易出现两种类型的异常：悬空读取，它返回缺少相应写入的值（即，分配读取返回值的写入）；以及反向操作，其中读取在跟踪中出现在其相应的写入之前。如果这些异常发生，则必须删除它们；否则， 属性由 Amitanand Aiyer 等人引入。² 与线性化一样，它要求操作看起来以受其开始和结束时间约束的顺序生效；但是，在此顺序内，读取可以返回任何最后更新值的 k 个。例如，图 1a 中显示的跟踪对于 k = 2 是Δ-原子性—这属性由 Wojciech Golab 等人提出。¹⁵ 类似于属性是未定义的，不能用于计算陈旧性。

悬空读取指示缺少信息，例如，当跟踪中对对象的第一次访问是读取，而相应的写入发生在跟踪开始之前。在这种情况下，悬空读取很容易识别，可以从跟踪中删除，而不会产生不良影响。反向操作同样容易检测，但更难补救。原子钟和 GPS¹⁰ 等时钟同步技术可以完全消除反向操作。即使普通的 NTP（网络时间协议），如果时钟同步足够紧密，也足够了。或者，也可以直接从反向操作估计时钟偏差，并相应地调整跟踪。

给定一个没有悬空读取和反向操作的跟踪，下一个挑战是计算陈旧性指标。高效的算法在此上下文中至关重要，因为跟踪可能非常长，这意味着所需的空间和计算量都很高。事实上，Gibbons 和 Korach 表明，测试跟踪是否是线性化的，是难以处理的。¹³ 测试跟踪是否是 ，但对于 k = 1 则不是。或。如果两个操作在时间上重叠，如图 1b 所示，则线性化允许 R(X) 在 W(X,2) 之前生效，而在线性化中，它要求 R(X) 在 W(X,2) 之后生效。如果假设将 R(X) 向左“拉伸” Δ 时间单位（即，如果 R(X) 早 Δ 时间单位开始），如图 1b 所示，则跟踪变为线性化的。因此，在图 1a 中，R(X) 的响应仅被视为陈旧 Δ 时间单位。对于固定的 k 和 ，至少与线性化一样困难，因为当 k = 1 和 Δ = 0 时，这些属性等效于线性化。从跟踪中计算 k 和 Δ 更加困难，因此也难以处理。

幸运的是，当给定对象上的每个写入都分配一个唯一值时，难处理性结果就会中断。这种情况很容易强制执行（例如，通过在每个写入的值中嵌入唯一令牌，例如节点 ID 和时间戳），这为在实践中从跟踪中计算陈旧性指标打开了大门。对于Δ-原子性，已知这样的算法¹⁵，并且已用于分析基于时间的使用 Cassandra 获得的跟踪中的陈旧性。²⁴ 对于 它通过允许读取返回陈旧值来放松线性化。但是，陈旧性是根据时间定义的：读取可能会返回最多 Δ 时间单位的陈旧值。例如，如果 Δ 定义为 W(X,2) 和 R(X) 之间的间隙宽度，则图 1a 中的跟踪是，仅已知用于决定跟踪是否为2-原子的有效算法。 ¹⁴

一般来说，被动分析不限于陈旧性指标，如循环分析^5,30技术所示，该技术通过分析表示执行跟踪的冲突图来检测线性化违规。此类图中不存在循环表明跟踪是线性化的，因此此类循环的数量和长度可以定义为不一致性的指标。^5,30 这些指标与陈旧性的关系尚不清楚。

比较和讨论

预测、主动测量和被动分析都是研究最终一致性的有用方法。尽管每种方法都有其特定的优点和缺点，但很难直接比较它们，因为它们满足不同的目标。被动分析是 以客户端为中心 的，因为它反映了客户端应用程序与系统交互的方式。因此，被动分析可用于比较应用于同一存储系统的两个工作负载中观察到的陈旧性。另一方面，主动测量是 以系统为中心 的，因为它测量系统复制协议对于受控工作负载的收敛时间。因此，主动测量最适合在陈旧性方面比较不同的系统，或在不同的软件或硬件配置下比较同一系统。PBS 框架⁶也是围绕受控工作负载设计的，因此它被归类为以系统为中心。

本文讨论的技术在最终一致性的概念模型方面也有所不同。主动测量和 PBS 基于简化模型，类似于 Vogels 的定义²⁸，其中写入发生在读取之前。相比之下，被动分析考虑通用模型，其中写入可能在时间上与读取和其他写入重叠。正如 Golab 等人在另一篇文章中解释的那样，¹⁶ 当客户端遵循“R + W > N”规则²⁸时，存储系统在这两个模型中的行为可能不同，这确保了读取和写入操作访问副本的重叠子集。长期以来，后一个条件一直被认为是“强一致性”^6,28的充分条件，事实上，它在简化模型中保证了线性化，但在通用模型中允许线性化违规。

尽管分析操作的详细跟踪成本有些高昂，但被动分析在理解最终一致性方面起着重要作用。虽然对一致性的任何视角最终都会受到存储系统中副本数据状态的影响，这可以被认为是“真实情况”，但被动分析与客户端应用程序观察到的实际一致性最密切相关。具体而言，它仅在数据级别异常表现给客户端时才反映出来—例如，作为陈旧读取。

未来工作

对于现代在线服务提供商而言，延迟的少量减少已知会对用户体验以及随之而来的收入产生可衡量的影响。¹⁷ 随着弱一致性作为降低延迟的手段继续受到欢迎，清晰地推理这一点的能力，这些级别控制响应读取或写入的副本数量。²⁰将成为服务提供商的重要竞争优势。

行业已经开始采用考虑一致性的定价方案和保证。Amazon 的 DynamoDB 支持对一致性读取和最终一致性读取进行差异化定价，前者保证使应用程序开发人员的成本增加一倍。³ 最近，

Terry 等人描述了一个系统，该系统允许客户端应用程序选择不同等级的弱一致性，例如“最多200 毫秒延迟和最多5 分钟陈旧性”，通过新颖的 SLA（服务级别协议）。²⁷ 可以请求其他读取保证，例如单调读取或因果一致性，并且可以指定具有不同效用的不同组合的“愿望清单”。这为更精细的定价方案打开了大门，使用户比以往任何时候都更需要理解与一致性相关的 权衡中的不同点的效用。

虽然对最终一致性的理解预计会随着涉及测量的更多实证研究而提高，但基本的技术问题仍然有待解决。特别是，一致性验证问题仍然是一个开放且重要的挑战。存储系统设计人员需要验证技术来测试他们的实现是否正确地履行了应用程序指定的SLA，同样，应用程序开发人员可以使用此类工具来验证实际收到的服务质量。

与验证算法相关的未决问题之一是确定决定 k-原子性的计算复杂性。现有算法仅处理特殊情况 k < 3¹⁴，这限制了它们在实践中的使用。类似的技术思想可以应用于 k ≥ 3 时，但仅适用于有限类别的跟踪，并且尚不清楚是否存在用于决定 属性由 Amitanand Aiyer 等人引入。² 与线性化一样，它要求操作看起来以受其开始和结束时间约束的顺序生效；但是，在此顺序内，读取可以返回任何最后更新值的 k 个。例如，图 1a 中显示的跟踪对于 k = 2 是一般情况下的有效算法。

结论

最终一致性越来越被视为可以在各个维度上量化的行为谱，而不是存储系统要么满足要么不满足的二元属性。表征和验证这些行为的进步将使服务提供商能够提供日益丰富的差异化性能服务级别，最终改善最终用户的体验。

致谢

我们感谢 Jay J. Wylie、Indranil Gupta 和 Doug Terry 的有益反馈。

参考文献

1. Abadi, D. 2012. 现代分布式数据库系统设计中的一致性权衡：CAP 只是故事的一部分。IEEE Computer 45(2) 37-42.

2. Aiyer, A., Alvisi, L., Bazzi, R. A. 2005. 关于非严格仲裁系统的可用性。在第 19 届国际分布式计算研讨会论文集：pp. 48-62.

3. Amazon Web Services. DynamoDB；http://aws.amazon.com/dynamodb/。

4. Amazon Web Services. SimpleDB；http://aws.amazon.com/simpledb/。

5. Anderson, E., Li, X., Shah, M. A., Tucek, J., Wylie, J. J. 2010. 您的键值存储实际上提供什么一致性？在第 6 届 Usenix 系统可靠性热点主题研讨会论文集中。

6. Bailis, P., Venkataraman, S., Franklin, M. J., Hellerstein, J. M., Stoica, I. 2012. 实用部分仲裁的概率有界陈旧性。在VLDB（超大型数据库）捐赠基金会论文集 5(8)中 776-787.

7. Bermbach, D., Zhao, L., Sakr, S. 2013. 面向云托管数据存储服务的一致性保证的全面测量。在第 5 届 TPC（事务处理性能委员会）性能评估和基准测试技术会议论文集中。

8. Bermbach, D., Tai, S. 2011. 最终一致性：最终是多久？Amazon S3 一致性行为的评估。在第 6 届面向服务计算中间件研讨会论文集中。

9. Brewer, E. A. 2000. 迈向健壮的分布式系统 (特邀报告)。在第19届 会议论文集 SIGACT-SIGOPS 分布式计算原理研讨会.

10. Corbett, J. C. 等. 2012. Spanner：Google 的全球分布式数据库。在第10届 Usenix 操作系统设计与实现会议论文集 251-264.

11. Davidson, A., Rubinstein, A., Todi, A., Bailis, P., Venkataraman, S. 2012. 实际环境中的自适应混合仲裁； http://www.cs.berkeley.edu/~kubitron/courses/cs262a-F12/projects/reports/project12_report_ver2.pdf .

12. Decandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W. 2007. Dynamo：Amazon 的高可用性键值商店。在第21届 操作系统原理研讨会论文集。

13. Gibbons, P. B., Korach, E. 1997. 测试共享内存。SIAM（工业与应用数学学会）计算杂志 26(4) 1208-1244.

14. Golab, W., Hurwitz, J., Li, X. 2013. 关于 k-原子性验证问题。在第33届 IEEE 国际分布式计算系统会议论文集。

15. Golab, W., Li, X., Shah, M. A. 2011. 分析一致性属性以获得乐趣和收益。在第30届 年度 SIGACT-SIGOPS 分布式计算原理研讨会论文集 197-206.

16. Golab, W., Rahman, M. R., AuYoung, A., Keeton, K., Gupta, I. 2013。以客户端为中心云存储系统最终一致性的基准测试。手稿正在提交中。

17. Hamilton, J. 2009. 延迟的成本； http://perspectives.mvdirona.com/2009/10/31/TheCostOfLatency.aspx。

18. Herlihy, M., Wing, J. M. 1990. 线性化：并发对象的正确性条件。 编程语言和系统事务 (TOPLAS) 12(3) 463-492.

19. Hunt, P., Konar, M., Junqueira, F. P., Reed, B. 2010. ZooKeeper无等待互联网规模系统的协调。在2010 年 Usenix 年度技术会议论文集 11-25.

20. Lakshman, A., Malik, P. 2010. Cassandra：一种去中心化的结构化存储系统。 SIGOPS 操作系统评论 44(2) 35-40.

21. Lamport, L. 1986. 关于进程间通信。第一部分：基本形式主义；第二部分：算法。分布式计算 1(2) 77-101.

22. Lloyd, W., Freedman, M. J., Kaminsky, M., Andersen, D. G. 2011. 不要满足于最终一致性：可扩展的因果一致性，用于广域带有 COPS 的存储。在第23届 操作系统原理研讨会论文集 401-416.

23. Patil, S., Polte, M., Ren, K., Tantisiriroj, W., Xiao, L., López, J., Gibson, G., Fuchs, A., Rinaldi, B. 2011. YCSB++：可扩展表存储中高级功能的基准测试和性能调试。在第2届 云计算研讨会论文集 9:1-9:14.

24. Rahman, M. R., Golab, W., AuYoung, A., Keeton, K., Wylie, J. J. 2012. 迈向一致性基准测试的原则性框架。在第8届 Usenix 系统可靠性热点问题研讨会论文集。

25. Terry, D. 2013. 通过棒球解释复制数据一致性。 通讯。

26. Terry, D. B., Petersen, K., Spreitzer, M. J., Theimer, M. M. 1998. 以下情况的案例非透明复制：来自 Bayou 的示例。IEEE 数据工程公告 21(4) 12-20.

27. Terry, D. B., Prabhakaran, V., Kotla, R., Balakrishnan, M., Aguilera, M. K.,Abu-Libdeh,H. 2013。基于一致性 服务级别云存储协议。在第24届 操作系统原理研讨会论文集。

28. Vogels, W. 2008. 最终一致性； https://queue.org.cn/detail.cfm?id=1466448。 队列 6(6) 14-19.

29. Wada, H., Fekete, A., Zhao, L., Lee, K., Liu, A. 2011. 商业云存储中的数据一致性属性和权衡：消费者的视角。在第5届创新数据系统研究双年会议论文集 134-143.

30. Zellag, K., Kemme, B. 2012. 您的云应用程序有多一致？在第3届 云计算研讨会论文集。

Wojciech Golab 是滑铁卢大学电气与计算机工程系的助理教授。他目前的研究重点是分布式计算中的算法问题，应用于存储、事务处理和大数据分析。在加入滑铁卢大学之前，他曾在惠普帕洛阿尔托实验室担任存储系统研究员，并在卡尔加里大学担任理论博士后研究员。他于 2010 年获得多伦多大学计算机科学博士学位。

Muntasir Raihan Rahman 是伊利诺伊大学香槟分校分布式协议研究组的计算机科学博士生。厄巴纳-香槟分校。他目前的研究重点是分布式系统中的一致性。他于 2006 年获得孟加拉国工程技术大学计算机科学与工程学士学位，并于 2010 年获得滑铁卢大学计算机科学硕士学位。

Alvin Auyoung 是惠普实验室系统组的研究员。他目前的工作重点是设计内存分布式存储系统和大规模数据分析。过去，他还研究了经济学和计算机科学交叉领域的问题，特别是将市场和拍卖的思想应用于分布式系统。他获得了加利福尼亚大学圣地亚哥分校计算机科学博士学位。

Kimberly Keeton 是惠普实验室的首席研究员。她最近的研究领域是 NoSQL 数据库、一致性模型和信息管理。她还曾在存储管理、存储可靠性、工作负载特征分析和智能存储等领域工作。她获得了加利福尼亚大学伯克利分校计算机科学博士学位，并且是 杰出科学家和 IEEE 高级会员。

Xiaozhou (Steve) Li 是 Google 的一名软件工程师。过去，他曾在惠普实验室担任研究员，并在微软担任软件设计工程师。他的主要兴趣在于分布式计算的理论和实践。他获得了德克萨斯大学奥斯汀分校计算机科学博士学位。

喜欢还是讨厌？请告诉我们 [email protected]

© 2014 1542-7730/14/0100 $10.00

最初发表于 Queue vol. 12, no. 1—
在 数字图书馆 中评论这篇文章

---

更多相关文章

Qian Li, Peter Kraft - 事务和无服务器是天作之合
数据库支持的应用程序是无服务器计算令人兴奋的新领域。通过紧密集成应用程序执行和数据管理，事务性无服务器平台能够实现许多在现有无服务器平台或基于服务器的部署中不可能实现的新功能。

Pat Helland - 任何其他名称的身份
新兴的系统和协议既收紧又放松了我们对身份的概念，这很好！它们使完成工作变得更容易。REST、IoT、大数据和机器学习都围绕着故意保持灵活且有时模棱两可的身份概念。身份的概念是我们分布式系统的基本机制的基础，包括可互换性、幂等性和不变性。

Raymond Blum, Betsy Beyer - 实现数字永久性
当今的信息时代正在为世界所依赖的数据创造新的用途和新的管理方式。世界正在从熟悉的物理人工制品转向更接近其本质信息的新的表示方式。我们需要流程来确保知识的完整性和可访问性，以保证历史将被了解和真实。

Graham Cormode - 数据草图
您是否曾感到被无休止的信息流淹没？似乎源源不断的新电子邮件和短信需要持续关注，还有电话要接听、文章要阅读、门要敲。将这些碎片拼凑在一起以跟踪重要内容可能是一个真正的挑战。为了应对这一挑战，流数据处理模型越来越受欢迎。其目的不再是捕获、存储和索引每一分钟的事件，而是快速处理每个观察结果，以便创建当前状态的摘要。

---

---

© 保留所有权利。