Werner Vogels on December 23, 2008
http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
这篇文章是Werner Vogel在2008年发布在ACM Queue上的一篇数据库方面的重要文章，阐述了NoSQL数据库的理论基石－－最终一致性，对传统的关系型数据库（ACID，Transaction）做了较好的补充。国内已有很多相关方面的介绍，比如InfoQ在2009年的介绍，但基本没有完整翻译的版本。在这里做一个完整的翻译，供初学者参考。
最终一致性－－在世界范围内构建可靠的分布式系统要求在一致性和可用性之间做出权衡。
在Amazon的云计算基本原理中，计算（Computing）是基础设施服务，比如Amazon S3（基本存储服务），SimpleDB和EC2（弹性计算云），它们提供资源来建造互联网级的计算平台和大规模应用。对这些基础设施服务的需求是严格的：它们需要在安全，可伸缩性，可用性，性能和性价比上都有好的表现；它们也需要有能力来不间断的为全球上百万的用户服务。
在背后，这些服务是在世界范围运作的庞大的分布式系统。这种规模也带来了额外的挑战，因为当一个系统处理数以万亿的请求时，正常情况下的小概率事件也会被认为一定发生，因而需要在系统的设计和架构时考虑到。考虑到这些系统是世界范围的，我们到处采用冗余技术来保证稳定的性能和高可用性。虽然冗余让我们离目标更近，但它不能以一个非常清晰的形式达到目标。在一些情况下，这些服务的用户会面临服务内部荣誉技术带来的后果。
一种解决方法存在于系统提供的数据一致性的类型中，尤其是底层的分布式系统为数据冗余提供了最终一致性模型的时候。当Amazon设计这些大规模系统时，我们使用了一系列与大规模数据冗余相关的指导原则和抽象方法，并着眼于高可用性和数据一致性之间的权衡取舍。在这篇文章里，我介绍了一些相关背景，描述了我们的方法可以提交一个可靠的分布式系统在全球范围内运作。本文的一个较早版本出现在All Things Distributed博客上，在读者的帮助下有了很大的提高。
历史的观点
理想情况下应该只有唯一的一致性模型：当一条更新出现时，所有的观察者都应该看到这个更新。第一次认为这个模型很难实现是在70年代末期的数据库系统中。当时在这 个领域具有指导意义的一篇文章是Bruce Lindsay写的《Notes on Distributed Databases》，这篇文章阐述了数据库冗余的基本原理并讨论了大量解决一致性问题的技术。这些技术中的很大一部分都试图获得分布式透明化，也就是让用户感觉到只有一个系统，而非若干个协同的系统。在那个时期，许多系统宁可放弃系统完整性而不破坏其透明度。
在90年代中期，随着更大的互联网系统的出现，这些实践都需要被重新审视。那时人们开始考虑可用性或许才是这些系统作重要的特性，但人们争论的话题是应该拿什么来与可用性进行权衡取舍。伯克利大学教授Eric Brewer，当时的lnktomi带头人，在2000年1月的PODC（Priciples of Distributed Computing）会议主题说明上把各种需要权衡的特性合并。他展示了CAP理论，这个理论陈述了三个数据共享系统的性质——数据一致性，系统可用性和网络分割容忍性，任何一个系统只能同时达到其中两个特性。更多的严谨的证明可以在一篇2002年Seth Gilbert和Nancy Lynch发表的论文中找到。
一个不能兼容网络分割的系统可以获取数据一致性和系统可用性，并且经常会通过使用事务协议来获取。为了做到这一点，客户端和存储系统必须在相同的环境里；在这种情况下系统可能会陷入整体崩溃的困境，而且在这样的系统中客户端是无法观察到网络分割的。一个很重要的现象是在更大规模的分布式系统中，网络分割是必然的；因此， 数据一致性和系统可用性就无法同时得到保障。这就意味着必须放弃一些特性，有两个选择：放松一致性可以让系统在可分割情况下保持高可用性，或优先考虑一致性，也就是说在某些情况下系统会不可用。
两种选择都要求客户端开发者了解系统到底提供什么。如果系统重视一致性，那么开发者就必须处理系统可能出现的不可用的情况。例如一个写操作。如果由于系统不可用写操作失败了，那么开发者就必须思考如何处理写的数据。如果系统重视可用性，它可以保证数据始终被正确写入；但在某些情况下，读取操作将不能反映最近一次写操作的结果。开发者就必须决定客户端是否请求了一个最新版本的数据。有一些应用程序可以巧妙的处理这些陈旧的数据，并且他们在这个模型下运行得很好。
原理上，ACID特性（atomicity, consistency, isolation, durability）中定义的事务系统的一致性特性是另外一种截然不同的一致性保障。在ACID中，一个事务完成，数据库被认为处于一致状态。例如，当从一个帐户向另一个帐户转账的时候，两个帐户的总额不应该有变化。在基于ACID的系统中，这种一致性经常是编写事务代码的开发人员的责任，但可以通过数据库管理的完整性约束来辅助解决问题。
一致性——客户端与服务端
有两种方式来看待一致性。一是从开发者/客户端的角度看：如何监测数据更新。第二种方法是从服务端的角度：更新如何通过系统和系统如何保证处理更新。
客户端一致性
客户端有这些组件：
· 存储系统：它在本质上是大规模且高度分布的系统，其创建目的是为了保证耐用性和可用性。
· 进程A：对存储系统进行读写。
· 进程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，那么系统在没有收到更新的节点上执行读操作是不准确的。
“读己之所写”，会话，还是单调一致性能否达到，基本取决于客户端和服务器之间的黏性（stickiness），用于执行它们之间的分布式协议。如果每一次请求的服务端都是一样的，那么保证“读己之所写”和单调读一致性就相对简单。虽然这会使得管理负载均衡和容错有点困难，但这仍是一个简单的解决方案。会话具有很强的黏性，使用会话就使这个问题非常清晰，而且可以给客户端提供一个可参考的明确的等级。
有时客户端会实现“读己之所写”和单调读一致性。通过在数据写操作上加版本控制，客户端忽略最新版本之前的所有数据。
分割（Partition）发生在系统中的部分节点无法到达其他节点时，但对于客户组来说这些节点都是可达的。如果使用经典多数仲裁法，那么有W个节点副本集合的分区就可以在其他分区失效的情况下进行正常更新。读集合也是如此。假设这两个集合有重叠，根据定义少数集合会不可用。分区不会经常出现，但的确会在数据中心之间发生，数据中心内部也会发生。
在一些应用程序中，任何一个无效分区不可访问都是不可接受的，而且让到达分区的客户端有所进展是非常重要的。在这种场景下两方面都分配一个新的存储节点来接收数据，并在分区恢复后进行数据合并。例如，Amazon购物车是一个高写入的系统；在出现分区的情况下，客户可以继续把货物放进购物车，即使原来的购物车信息存放在另一个分区中。一旦分区恢复，购物车程序就协助存储系统合并购物车数据。
Amazon’s Dynamo
Amazon’ Dynamo将这些特性显示地纳入应用框架的控制中。Amazon电子商务平台上的许多服务，连同Amazon Web服务都使用了一个“键－值”存储系统。Dynamo的一个设计目标就是允许应用服务的主人，也就是创建这个跨数据中心Dynamo实例的人，在一致性，持久性，可用性和性能上权衡找到一个平衡点。
完。