ACM通信
实践
最终一致
插图:Dave Bollinger
Amazon云计算的基础是基础设施服务，如Amazon的S3(简单存储服务)、SimpleDB和EC2(弹性计算云)，它们为构建internet级计算平台和各种应用程序提供资源。对这些基础设施服务的要求非常严格;他们需要在安全性、可伸缩性、可用性、性能和成本效益方面获得高分，他们需要满足这些需求，同时持续地为全球数百万客户提供服务。
在这些服务的背后是在全球范围内运行的大规模分布式系统。这种规模带来了额外的挑战，因为当系统处理数以万亿计的请求时，通常发生概率很低的事件现在肯定会发生，并且必须在系统的设计和架构中预先考虑到这些事件。考虑到这些系统的全球范围，我们普遍使用复制技术来保证一致的性能和高可用性。虽然复制使我们更接近我们的目标，但它不能以完全透明的方式实现它们;在许多情况下，这些服务的客户将面临在服务内部使用复制技术的后果。
这种情况的表现方式之一是所提供的数据一致性类型，特别是当许多广泛分布的系统提供一个最终一致性在数据复制上下文中建模。在Amazon设计这些大规模系统时，我们使用了一组与大规模数据复制相关的指导原则和抽象，并关注高可用性和数据一致性之间的权衡。在这里，我将介绍一些相关的背景知识，这些知识为我们提供了交付必须在全球范围内运行的可靠分布式系统的方法。(本文的早期版本出现在“分布式所有事物”Weblog上，在读者的帮助下得到了极大的改进。)
历史的角度
在理想的世界中，只有一个一致性模型:当更新完成时，所有观察者都会看到更新。第一次出现这种难以实现的情况是在20世纪70年代末的数据库系统中。关于这个主题最好的“历史文章”是Bruce Lindsay等人的《分布式数据库笔记》。5本文列出了数据库复制的基本原则，并讨论了一些用于实现一致性的技术。这些技术中的许多都试图实现分配的透明度也就是说，对于系统的用户来说，似乎只有一个系统，而不是许多协作的系统。在此期间，许多系统采取了这样一种方法:与其破坏这种透明性，不如让整个系统失灵。2
在20世纪90年代中期，随着大型互联网系统的兴起，这些做法被重新审视。那时，人们开始认为可用性可能是这些系统最重要的属性，但他们一直在努力权衡该用什么来换取可用性。Eric Brewer是加州大学伯克利分校的系统教授，同时也是Inktomi的负责人，他在2000年的分布式计算原则(PODC)会议上发表了一个主题演讲，将不同的权衡结合在一起。1他提出了上限定理，它说明了共享数据系统的三个属性:数据一致性、系统可用性和对网络分区的容忍度，在任何给定的时间只有两个可以实现。Seth Gilbert和Nancy Lynch在2002年的一篇论文中给出了更正式的证实。4
不能容忍网络分区的系统可以实现数据一致性和可用性，通常通过使用事务协议来实现这一点。要做到这一点，客户机和存储系统必须是同一环境的一部分;在某些场景下，它们会整体失效，因此客户机无法观察分区。一个重要的现象是，在较大的分布式系统中，网络分区是给定的;因此，一致性和可用性不能同时实现。这意味着有两种选择:放松一致性将允许系统在可分区条件下保持高可用性;将一致性作为优先级意味着在某些条件下系统将不可用。
这两种选择都要求客户端开发人员知道系统提供了什么。如果系统强调一致性，开发人员就必须处理这样的事实:系统可能不可用，例如，写。如果由于系统不可用而导致写入失败，那么开发人员将不得不处理如何处理要写入的数据。如果系统强调可用性，它可能总是接受写操作，但在某些条件下，读操作不会反映最近完成的写操作的结果。然后，开发人员必须决定客户端是否需要一直访问绝对最新的更新。有一些应用程序可以处理稍微过时的数据，它们在这个模型下得到了很好的服务。
原则上，在ACID属性中定义的事务系统的一致性属性(原子性、一致性、隔离性、持久性)是一种不同的一致性保证。在ACID中，一致性与保证事务完成时数据库处于一致状态有关;例如，当从一个账户转账到另一个账户时，两个账户的总金额不应该改变。在基于acid的系统中，这种一致性通常由编写事务的开发人员负责，但数据库管理完整性约束可以帮助实现。
ConsistencyClient和服务器
有两种方法来看待一致性。一种是从开发人员/客户端的角度:他们如何观察数据更新。另一个问题来自服务器端:更新如何通过系统，以及系统对更新能提供什么保证。
客户端组件包括:
- 一个存储系统。现在我们把它当作一个黑盒子，但是我们应该假设它是一个大规模的、高度分布的东西，并且它是为了保证持久性和可用性而构建的。
- 一个过程。这是一个对存储系统进行读写的进程。
- 过程B和C。这两个进程独立于进程A，对存储系统进行读写操作。它们是同一个进程中的进程还是线程是无关紧要的;重要的是他们是独立的，需要交流来共享信息。
客户端一致性与观察者(在本例中是进程A、B或C)如何以及何时看到存储系统中对数据对象的更新有关。在下面说明不同类型一致性的例子中，进程A更新了一个数据对象:
- 强烈的一致性。更新完成后，任何后续访问(A、B或C)将返回更新后的值。
- 弱一致性。系统不保证后续访问将返回更新后的值。在返回值之前，需要满足许多条件。从更新到保证任何观察者都能看到更新值的这段时间被称为不一致窗口。
- 最终一致性。这是弱一致性的一种特殊形式;存储系统保证，如果没有对对象进行新的更新，最终所有访问都将返回最后更新的值。如果没有发生故障，可以根据通信延迟、系统负载和复制方案中涉及的副本数量等因素确定不一致窗口的最大大小。实现最终一致性的最流行的系统是域名系统(DNS)。对名称的更新根据配置的模式并与时间控制的缓存相结合进行分发;最终，所有客户端都将看到更新。
最终一致性模型有许多重要的变化需要考虑:
- 因果一致性。如果进程A已经通知进程B它已经更新了一个数据项，进程B的后续访问将返回更新后的值，并且保证一次写入将取代先前的写入。与进程A没有因果关系的进程C的访问遵循正常的最终一致性规则。
- “读己之所写”一致性。这是一个重要的模型，在此模型中，进程A在更新了一个数据项之后，总是访问更新的值，而不会看到旧的值。这是因果一致性模型的一个特例。
- 会话一致性。这是前一个模型的实用版本，其中进程在会话上下文中访问存储系统。只要会话存在，系统就保证读写一致性。如果会话因为某个故障场景而终止，则必须创建一个新的会话，并且保证不重叠会话。
- 单调读一致性。如果进程看到了该对象的特定值，那么后续访问将永远不会返回之前的值。
- 单调写一致性。在这种情况下，系统保证同一个进程序列化写操作。不能保证这种一致性的系统是出了名的难以编程。
这些属性中的许多都可以组合使用。例如，可以结合会话级一致性获得单调读取。从实用的角度来看，这两个属性(单调读和读你的写)在最终一致性系统中是最理想的，但并不总是必需的。这两个属性使开发人员更容易构建应用程序，同时允许存储系统放松一致性并提供高可用性。
正如您可以从这些变化中看到的，可能会有很多不同的场景。人们能否处理其后果取决于具体的应用。
最终一致性并不是极端分布式系统的某些深奥属性。许多提供主备份可靠性的现代rdbms(关系数据库管理系统)以同步和异步模式实现其复制技术。在同步模式下，副本更新是事务的一部分。在异步模式下，更新以延迟的方式到达备份，通常通过日志传送。在后一种模式下，如果主服务器在发送日志之前失败，则从提升的备份中读取将产生旧的、不一致的值。为了支持更好的可伸缩读取性能，rdbms已经开始提供从备份中读取的能力，这是提供最终一致性保证的典型情况，其中不一致窗口取决于日志传送的周期。
在服务器端，我们需要更深入地研究系统中的更新流程，以理解使用系统的开发人员能够体验到的不同模式的驱动因素。在开始之前，让我们先建立一些定义:
- N =存储数据副本的节点数。
- W =在更新完成之前需要确认收到更新的副本数量。
- R =通过读操作访问数据对象时所接触的副本数量。
如果W+R > N，则写集和读集总是重叠的，可以保证强一致性。在实现同步复制的主备份RDBMS场景中，N=2, W=2, R=1。不管客户端从哪个副本读取数据，它总是会得到一致的答案。在启用从备份读取数据的异步复制情况下，N=2, W=1, R=1。此时R+W=N，无法保证一致性。
这些基本仲裁协议配置的问题在于，当系统由于故障无法写入W节点时，写入操作必须失败，标志着系统不可用。当N=3和W=3且只有两个节点可用时，系统将不得不使写操作失败。
在高性能和高可用性的分布式存储系统中，副本的数量一般都在2个以上。只关注容错的系统通常使用N=3 (W=2和R=2配置)。必须提供非常高读负载的系统通常会复制超出容错所需的数据;N可以是数十甚至数百个节点，将R配置为1，这样一次读取就会返回一个结果。关注一致性的系统在更新时设置为W=N，这可能会降低写成功的概率。对于这些关心容错而不关心一致性的系统，一种常见的配置是使用W=1运行，以获得最小的更新持久性，然后依靠一种延迟(流行)技术来更新其他副本。
当系统处理数以万亿计的请求时，通常发生概率很低的事件现在肯定会发生，并且必须在系统的设计和体系结构中预先考虑。
如何配置N、W、R取决于常见情况以及需要优化的性能路径。在R=1和N=W的情况下，我们优化读取的情况，在W=1和R=N的情况下，我们优化非常快的写入。当然，在后一种情况下，在出现故障时，持久性不能得到保证，如果W < (N+1)/2，当写集不重叠时，就有可能发生冲突的写操作。
弱/最终一致性出现在W+R <= N时，这意味着读写集有可能不重叠。如果这是一个有意的配置，并且不是基于失败的情况，那么将R设为1以外的任何值都没有意义。这种情况在两种非常常见的情况下都会发生:第一种是前面提到的用于读取扩展的大规模复制;第二个是数据访问更复杂的地方。在简单的键值模型中，比较版本很容易确定写入系统的最新值，但在返回对象集的系统中，要确定正确的最新集应该是什么就比较困难了。在大多数写入集小于副本集的系统中，存在一种机制，以惰性方式将更新应用于副本集中的剩余节点。更新所有副本之前的周期就是前面讨论的不一致窗口。如果W+R <= N，则系统很容易从还没有收到更新的节点读取数据。
能否实现“读己所写”一致性、会话一致性和单调一致性，通常取决于客户端对为其执行分布式协议的服务器的“粘性”。如果每次都是相同的服务器，那么保证“读己写”和“单调读”就相对容易了。这使得管理负载平衡和容错稍微困难一些，但这是一个简单的解决方案。使用会话，这是粘性的，使此显式，并提供了一个暴露级别，客户端可以进行推理。
有时客户端实现“读你的”和“单调读取”。通过在写操作中添加版本，客户端将丢弃对最后看到的版本之前版本的值的读取。
当系统中的某些节点无法到达其他节点时，就会发生分区，但这两组客户端都是可达的。如果使用经典的多数仲裁方法，那么拥有W个副本集节点的分区可以在另一个分区不可用时继续进行更新。对于读集也是如此。如果这两个集合重叠，根据定义，少数集就不可用了。分区并不经常发生，但在数据中心之间以及数据中心内部确实会发生分区。
在某些应用程序中，任何一个分区不可用都是不可接受的，重要的是能够到达该分区的客户机要取得进展。在这种情况下，双方都分配一组新的存储节点来接收数据，并在分区修复时执行合并操作。例如，在Amazon中，购物车使用这样一个总是写的系统;在分区的情况下，客户可以继续将商品放入购物车，即使原来的购物车位于其他分区上。一旦分区修复，购物车应用程序将帮助存储系统合并购物车。
亚马逊的发电机
亚马逊的Dynamo系统将所有这些属性都置于应用程序架构的显式控制之下，这是一个键值存储系统，用于组成亚马逊电子商务平台的许多服务内部，以及亚马逊的Web服务。Dynamo的设计目标之一是允许创建通常跨多个数据中心的Dynamo存储系统实例的应用程序服务所有者在某个成本点上在一致性、持久性、可用性和性能之间进行权衡。3.
总结
必须容忍大规模可靠分布式系统中的数据不一致，原因有二:提高高并发条件下的读写性能;以及处理分区情况，其中大多数模型会使系统的一部分不可用，即使节点已经启动并运行。
不一致是否可以接受取决于客户端应用程序。在所有情况下，开发者都必须意识到存储系统提供的一致性保证，在开发应用程序时必须考虑到这一点。对最终一致性模型有许多实际的改进，例如会话级一致性和单调读取，它们为开发人员提供了更好的工具。很多时候，应用程序能够处理存储系统的最终一致性保证而没有任何问题。一个特别流行的例子是，在Web站点中，我们可以拥有用户感知一致性的概念。在此场景中，不一致窗口必须小于客户返回进行下一个页面加载的预期时间。这使得更新可以在下一次读取之前在系统中传播。
本文的目标是提高对工程系统复杂性的认识，这些系统需要在全球范围内运行，并且需要仔细调整，以确保它们能够交付其应用程序所需的持久性、可用性和性能。系统设计者拥有的工具之一是一致性窗口的长度，在此期间系统的客户端可能暴露在大规模系统工程的现实中。
参考文献
1.迈向稳健的分布式系统(抽象)。在第19届ACM分布式计算原理年会论文集(2000年7月19日，波特兰)
2.布鲁斯·林赛对话。ACM队列2,8(2004)， 2233。
3.迪坎迪亚，G.等。迪纳摩:亚马逊的高可用键值存储。在第21届ACM操作系统原理研讨会论文集(Stevenson, WA, 2007年10月)。
4.Gilbert, S.和Lynch, N. Brewer的猜想以及一致的、可用的、允许分区的Web服务的可行性。ACM SIGACT新闻332(2002)。
5.林赛，B.G.等人。分布式数据库的注意事项。分布式数据基地．I.W.德拉凡和F.普尔，编辑。剑桥大学出版社，马萨诸塞州剑桥，1980,247284。IBM Research Report RJ2517, San Jose, CA(1979年7月)。
©2009 acm 0001-0782/09/0100 $5.00
允许制作本作品的全部或部分的数字或硬拷贝用于个人或课堂使用，但前提是该拷贝不是为了盈利或商业利益而制作或分发，并且该拷贝在第一页上带有本通知和完整引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM有限公司
没有发现记录