Dynamo：亚马逊的高可用键值对存储
概要
在大规模下的可靠性是我们在亚马逊一个大的挑战，一个世界上最大的电商系统。即便是轻微的中断也会明显的财务影响并且影响了客户的信任。亚马逊平台提供了给世界尺度的很多网站提供服务，在成千上万台基础设施上实现的，并且网络组件位于许多遍布世界的数据中心。在这个规模下，小或者大的组件连续不断的故障，面对这些故障时管理持久化状态的方式驱动了可靠的可扩展的软件系统。
这个paper提出了设计和Dynamo的实现，一个高可用的键值对存储系统，亚马逊的一些核心服务就是用它来提供永远的在线体验的。为了达到这种级别的可用性，Dynamo牺牲了在某些故障场景下的一致性。它以一种为开发人员提供新颖接口的方式，广泛使用了对象版本控制应用辅助的冲突解决，
1 介绍
亚马逊运行着世界范围的电商平台，在高峰时段为数以千万的客户提供服务，使用上万台服务器位于世界的许多数据中心。在亚马逊平台上的操作对于性能，可靠性，有效性方面有严格的要求，为了支持持续增长，平台需要具有高度可扩展性。可靠性是一个最重要的需求，因为即便是小的中断也会导致明显的经济后果和影响客户的信任。此外，为了支持持续的增长平台徐亚高扩展性。
我们团队组织从运营亚马逊平台中学到的经验之一，系统的可靠性可扩展性依赖于如何管理应用程序状态。亚马逊使用了高度去中心化的，松耦合的，面向服务体系结构，由数百个服务组成。在这个环境特别需要强大的永远可用的存储技术。例如客户有能查看和添加项目到购物车即便磁盘故障。网络线路不稳定，数据中心被龙卷风摧毁。因此，服务负责管理购物车他可以永远被读取和写入在数据存储，数据需要跨多个数据中心高可用。
处理由百万个组件组成的基础设施中的故障是我们标注的操作模式；总会有几个小的但是显著数量的服务和网络组件在一些给定时间内故障。因此亚马逊软件系统需要构建一种方式，他将异常视为正常情况而不影响可用性和性能。
为了应对可靠性和扩展性需求，亚马逊开发了几个存储技术，其中Amazon Simple storage Service (也可以在亚马逊之外访问到，被称为Amazon S3)，可能是最有名的。这篇论文提出了Dynamo的实现和设计。在亚马逊平台上构建的另一种高可用的可靠的可扩展的分布式数据存储。Dynamo被用来管理服务状态，它们对可靠性的需求非常高并且需要严格的控制，可用性，一致性成本效益和性能。amazon平台有非常多样的应用在不同的存储需求。选择一组应用需要一种存储技术，他足够弹性，以让应用设计人员根据这些权衡适当的配置数据存储以实现高可用，使用最划算的方式保证性能 。
许多在亚马逊平台上的服务他们只需要键值对访问。对于许多服务，比如提供畅销排行榜的，购物车，客户偏好，会话管理，销售排名和产品目录，使用关系型数据库的常见模式会导致低效率以及限制了规模和可用性。Dynamo提供了简单的键值对接口，以应对这些应用的需要。
Dynamo使用了一些工作的良好的技术综合以达到可扩展性和可靠性：数据被通过一致性哈希进行分区和复制。通过在更新期间保持副本的一致性通过法定人数技术和去中心化的复制同步协议。Dynamo使用了基于gossip的故障探测和成员协议。Dynamo是一个完全去中心化的系统并且最小化手动管理的需求。存储节点可以在Dynamo添加或者删除而不需要任何手动分区或者重分布。
在过去的一年中，Dynamo已经成为了亚马逊贸易平台中的几个核心服务的底层存储技术。它能够在节假日扩展到极端的峰值负载而无需任何停机时间。例如，维护购物车的服务服务于数千万的请求在同一天就有超过300万的结账，管理会话状态的服务处理数十万的活动会话。
这项工作对于学术届的主要贡献是评估了如何结合不同的技术来提供单一的高可用性系统。他展示了最终一致性的存储系统可以被用在对于有着高要求的应用。他也提供了对这些技术调优的深入理解以应对生产系统非常严苛的性能需求。
背景
亚马逊的电商平台由几百项服务组成，这些协同功能从推荐到订单履行到欺诈检测的各种功能。每个服务都通过良好定义的接口进行暴露可通过网络访问。这些服务被托管于由上万个服务谓语世界范围内的数据中心。其中的一些服务是无状态的（服务聚合从其他服务的影响）一些是有状态的（即服务在他存储在持久化系统的状态上执行业务逻辑，生成它的相应）。
传统的生成系统存储他们的状态在关系型数据库中。然而， 对于许多常见的状态持久化的使用模式，关系系数据库是非理想的解决方案。他么中的大部分服务只存储并检索数据，不需要关系型数据库管理系统提供的功能复杂的查询和管理。这种多余的功能需要昂贵的硬件和高技能的操作人员，这是一个非常低效的方案。此外，可用的复制技术是有限的，通常选择一致性而不是可用性。虽然尽管近年来取得了许多进展，横向扩展数据库依然不简单，或者使用智能的分区模式以负载均衡。
这篇论文描述了Dynamo，一个高可用的数据存储技术解决了这些重要类型的服务的需求。Dynamo有简单的键值对接口，他具有明确定义的一致性窗口的高可用，在资源存储中是有效的，并且有一个简单的扩展方案来解决数据集大小或请求率的增长。每个使用Dynamo运行自己的Dynamo实例。
2.1 系统假设和需求
此类业务对存储系统的要求如下：
查询模型：简单的读取和写入操作到到数据条目，她被通过key唯一进行标识。状态就像二进制对象一样被存储（blobs）被唯一的key定义。没有跨多个数据项的操作，也不需要关系模式。这个需求基于一个显著的观察，亚马逊的服务可以在简单的查询模型下工作，并且不需要任何关联模式。Dynamo目标一样需要存储的对象通常小于1MB。
ACID属性 ：ACID（atomicity，consistency，isolation，durability）是一组保证数据库事务处理可靠性的资源。在数据库文本中，单一逻辑的操作被叫做事务。在亚马逊用的经验已经展示了提供事务的数据存储提供了差的可用性。这已经被机构和学界所认可。Dynamo 目标一样他操作是弱一致性的（ACID中的C）如果这导致高可用性。DynamoDynamo不提供任何的隔离性保证，许可只有单个键更新的时候。
有效性：系统需要功能谓语通用的硬件基建之上。在亚马逊平台，服务有很明显的延迟要求，通常在分部99.9%处测量。鉴于状态访问在服务中扮演了重要的决策，存储系统必须能够面对这样严苛的SLA。服务必须能够配置Dynamo，这样他就能始终如一的达到延迟和吞吐量。成本效益，可用性和持久性保证之间做出权衡。
其他假设：Dynamo被用来亚马逊内部的服务。他的操作环境被假设为非敌对的，不存在认证授权等安全相关需求，此外，因为每个服务使用了Dynamo的不同实例，它最初的设计模板是多大数百台存储主机的规模。我们将会讨论Dynamo可靠性限制并且可扩展性和相关的扩展在之后讨论。
2.2 服务水平的协议（SLA）
为了保证应用可以在有限的时间内交付它的功能。平台中的每个依赖项都需要在更严格的范围内交付其他功能。客户和服务签订服务水平协议（SLA），正式协商的合同，其中客户端和服务就系统的几个特征达成一致，其中最突出的是包括客户端的预期的特定API的请求率分布以及这些条件下预期的服务延迟。一个简单的SLA的例子是服务保证了他在300ms内提供响应百分之99.99%的请求在峰值时客户端每秒负载500个请求。
在亚马逊去中心化导向的基建，SLA扮演了重要的角色。例如，一页的请求达到一个电商网站通常需要呈现引擎构造其相应，通过调用超过150个服务。这些服务通常由多个依赖，这些经常是其他的服务，因此程序调用图有多个级别并不罕见。为了确保页面呈现擎可以维护明确的界限，调用链中的每个服务都必须遵守其性能契约。
图1：亚马逊平台上面向服务的架构
图1展示了亚马逊平台的抽象架构图，其中动态的web内容被页面呈现组件，这些组件反过来查询许多其他的服务。一个服务可以使用不同的数据存储来管理他的状态，这些数据存储是只能在他的服务边界内访问。一些服务的行为像聚合器，通过使用几个其他的服务生成复合响应。通常聚合器服务是无状态的，虽然他们使用了庞大的缓存。
业界形成面向性能的SLA的常用方法是使用均值，中值和期望变量来描述它。在亚马逊我们发现了这些指标不足够好，如果想要构建一个系统让所有的用户有良好的体验，而不只是大多数。例如，如果使用广泛的个性化技术，那么具有较长历史的用户需要更多的处理，这会影响分布上端的分布性能。用中指或者均值响应时间表示SLA不能解决这一部分客户群体的表现。为了解决这个问题，在亚马逊中，SLA表达和衡量的是第99.9百分位的分布。这个选择对于99.9%或者更高的百分位已经基于成本效益分析得出，展示了提高性能成本的显著增加。亚马逊的生产环境系统已经表明，与那些满足基于平均值或中位数定义的SLA的系统相比，这种方法提供了更好的整体体验。
在这个paper中很多次提到了分布中的99.9百分位，这反应了亚马逊工程师持续的站在客户经验的角度专注于性能。许多论文都上报了平均值，所以当在有意义的情况下这些会被包含进来用于比较。然而亚马逊工程师和优化工作并不聚焦于平均值。几个技术，比如负载均衡选择了协调者，是完全具有针对性的在控制性能在99.9的百分位上
存储系统通常在建立一个服务的SLA中扮演了重要的角色，特别是业务逻辑相对轻量级的时候，亚马逊的许多其他服务器也是如此。一个主要设计的考虑是因为Dynamo是让服务控制它们的属性，比如持久性和一致性，并且让服务在功能性和性能和成本效应之间做权衡。
2.3 设计考虑
商业系统中的数据复制算法传统上执行同步副本协调以提供强大的一致性数据访问接口。为了达到这个级别的一致性，这些算法聚焦于在特定的故障场景做权衡。例如，与其处理答案是否正确的不确定性，不如让些数据是绝对正确的否则不能使用这些数据。在一个非常早起的复制数据库工作，当处理可能的网络故障时，强一致性和高可用性不可能被同时达到，这一点广为人知。这些系统和应用需要知道哪个属性可以在哪个条件下被达到。
对于容易出现网络故障的系统，通过优化复制技术可以增加可用性，允许将改变传播到后台的副本，并且允许并发的，断开连接的工作。这些方法带来的挑战可能必须检测和解决相互冲突的更改。这个冲突解决的过程导致了俩个问题：什么时候解决他们以及谁来解决它们。Dynamo被设计为最终一致性的数据存储；也就是说所有的更新最终会达到副本。
一个重要的设计考量是决定什么时候执行解决更新冲突的处理，即是否应该在读写期间解决冲突。一些传统的数据存储执行冲突解决在写入的时候并且保持读取的复杂性较低。在这样的系统中，如果数据存储不能达到所有的（或者大多数）节点在给定时间中，写入可能会被拒绝。另一方面，Dynamo的目标是“始终可写”数据存储的设计空间（即：数据存储对于写入高可用）。对于一些亚马逊的服务，拒绝客户的更新会导致糟糕的客户体验。举个例子，购物车服务必须允许用户添加或者删除购物车的项目。即便网络出现故障的情况下也是如此。这一需求强迫我们推动冲突解决的复杂性到读取去却把写入永远不会被拒绝。
下一个设计选择了谁来执行这个冲突决议。这个可以通过数据存储或者应用来完成。如果冲突决议被数据存储完成，他的选择非常有限。在这个例子中数据存储只能使用简单的策略，比如最后写入的得胜以解决冲突更新。另一方面因为应用知道数据冲突的模式他可以决策冲突决议方法，这对于客户端的体验来说是非常合适的。例如，那些管理客户购物车冲突的应用可以选择合并冲突的版本并且返回一个一致的购物车。即便有这种特性，一些应用开发者可能不想编写自己的冲突解决机制，并选择将其下推到数据存储中，这样反过来又选择了一个简单的策略，比如因为最后一次写为获胜。
设计中包含的其他关键原则是：
增量可扩展性：Dynamo应该能过横向扩展（之后称作节点）在一个时间，并且最小化对于系统操作和系统本身的影响。
对称性：每一个节点在Dynamo中应该和对等节点有相同的指责；没有特殊角色的节点或者有额外特殊职责的节点。在我们的经验中，对称性简化了系统的配置和维护过程。
去中心化：一个对称性的延伸，设计应该偏好于去中心化的p2p技术不受中心化的控制。在过去，中心化的结果导致了停机，我们的目的是尽量避免它们。这导致了简单的，可扩展的和更可靠的系统。
异质性：系统需要能够利用跑在基础设施上的异质。即工作分布必须与单个服务器的能力成比例。这是非常重要的对于添加新的高容量的节点，而无需对所有主机位进行升级。
3 相关工作
4 系统架构
存储系统需要的操作在生产环境是复杂的。除了真正的数据持久性组件，系统需要扩展和健壮解决负载均衡，成员和故障探测，复制同步，过载处理，状态转换，一致性和工作调度，请求整理，请求路由，系统监控和报警以及配置管理。描述每个解决方案是不可能的，这篇论文聚焦于核心的分布式系统技术在Dynamo中的使用：分区，复制，版本管理，成员，失败处理和扩展。
4.1 系统接口
Dynamo通过相关联的键使用简单的接口；他暴露出来了俩个操作，get()和put()。get(key)操作定位对象副本在存储系统中和key的关联，并返回冲突版本的单个对象或者对象列表以及上下文。put(key,context,object)根据关联键放置对象副本的位置，并且写入副本到磁盘。context编码了系统关于对象的元数据，他们对于调用者来说是不透明的比如对象版本等信息。上下文信息与对象一起存储，以便系统可以验证放置请求中提供的上下文对象的有效性。
Dynamo同时处理调用者提供的键并且都将对象视为不透明的数组。他使用MD5哈希来生成128位的标识符，这杯用来确定服务这个key的存储节点。
4.2 分区算法
一个对于Dynamo关键的设计是它必须逐渐的扩展。这需要机制来动态的分区数据在整个节点的集合上在系统中。Dynamo的分区模式依赖于一致性哈希以分布负载穿过多个存储主机。在一致性哈希中，哈希的函数的输出范围如同一个固定的圆空间或者环（即从最大的环绕到最小的哈希值）。系统中的每个节点指派一个在空间中的随机值他表示环上的位置。每个由键标识的数据项通过散列数据项的键来获得其在环上的位置，从而分配给节点，然后顺时针遍历环，找到一个位置大于项目位置的节点。
因此每个节点都负责他在环上和前一个节点之间的区域。一致性哈希的主要优点是一个节点离开或者只到达影响它的邻近，其他节点维持不受影响。
基础的一致性哈希算法提出了一些挑战。首先环上各个节点随机位置分配导致了负载分布的不均衡。其次基础算法忽略了节点性能之间的异质性。为了解决这个问题，Dynamo使用了一致性哈希的变体：不是将节点映射到环中的单个点，每个节点分配到环中的多个点。为了这个目的，Dynamo使用虚拟节点。一个虚拟节点就像在系统中的单个节点，但是节点可以负责超过一个的虚拟节点。实际上，当新的节点添加到系统中，它指派多个位置（之后叫做token）在环中。Dynamo分区方案的微调过程将在第6节中讨论。
使用虚拟节点有如下的优势：
- 如果一个节点不可用（由于失败或者日常维修），这个节点上处理的负载均匀的分布在剩下的可用节点上
- 当一个节点再次可用，或者新的节点被添加到系统中，新的可用节点接受和其他可用节点大致相等的负载。
- 节点负责的虚拟节点的数量可以根据节点的容量来进行确定，考虑到物理基础设施的异质性。
4.3 复制
为了实现高可用性和耐用性，Dynamo复制它的数据到多个主机上。每个数据项被复制到n个主机上，其中n是每个实例可以配置的参数。每个键k分配一个给协调器节点（在前一张描述）。协调者负责复制其范围内的数据项。除了本地存储范围内的每个键之外，协调器复制这些键在环中n-1个顺时针的后继者节点。这导致了在系统中每个节点负则它和在它之前的第n个环区域。在图2中，节点B复制在c和d上的的键key，并将其存储在本地。节点D存储落在范围(A, B], (B, C], and (C, D].中的数据。
负责存储特定键的节点列表被叫做preference偏好列表。系统的设计将会在4.8章进行解释，所以系统中的每个节点可以决定对于特定的键，哪个节点应该在列表中。为了考虑节点故障，偏好列表维护了n个节点。注意通过使用虚拟节点，对于特定键的前n个节点可能被小于n个物理节点持有（即节点可能保存前N个位置中的多个位置）。为了解决这个问题，键的偏好列表通过跳过环中的位置来进行构建以确保列表只包含不同的物理节点。
4.4 数据版本
Dynamo提供了最终一致性，这允许更新异步的传播到所有的副本。put() 调用可能在更新尚未应用到所有副本之前就返回给调用者，这可能导致后续的 get() 操作返回一个没有最新更新的对象。如果没有失败，更新的传播时间会有边界。然而，在不确定失败的场景下（即，服务退出或者网络分区），更新可能在很长的时间内不能到达所有副本。
亚马逊平台的一类应用类型可以忍受这种不一致，并且可以在这个条件下构建操作。例如，购物车应用程序要求永远不能忘记或拒绝添加购物车操作。如果最新状态不可用，并且用户对购物车的旧版本进行了更改，这种变化是有意义的，应该被保留。但是与此同时，它不应该取代购物车不可用的状态，它本身可能包含应该被保留的变化。记住无论是添加购物车还是删除购物车操作都会被翻译为put请求到Dynamo。当用户想要添加一个项目（或者删除）到购物车最后的版本是不可用的，该项目天极爱（或者从中删除）就的版本不同的版本应该在之后被调和。
为了提供这种保证，Dynamo处理每次修改的结果作为一个新的不可变的数据版本。它允许对象的多个版本在系统的不同时间被提出。大部分时候，新的版本包含了老的版本并且系统本身可以授权版本（语义调和）。然而版本可能会出现分歧，在存在故障和伴随着并发冲突更新的情况下，导致对象版本的冲突。在这个例子中，系统无法协调同一个对象的多个版本，客户端必须进行调和将数据演化的多个分支合并为一个（语义复制）。一个典型的合并操作的例子是merge客户购物车的不同版本。使用调和机制，添加到购物车操作不会丢失，然而，删除项目可能重新出现。
这对于理解特定的故障模型可能导致系统有俩个但是不同版本的相同数据很关键。在网络存在分区时和节点故障时的更新可能潜在的导致了具有不同版本子历史对象，系统将会在未来对这些进行调和。这就要求我们在设计应用程序时明确承认同一数据存在多个版本的可能性（以不丢失任何的更新）。
Dynamo使用了向量时钟以补货不同版本对于相同对象的因果关系。向量时钟是一个有效的(node，counter)对列表。一个向量时钟与每个对象的版本相关联。通过检查向量向量时钟，可以确定一个对象的俩个版本是在平行分支上还是有因果顺序，如果第一个对象的计数器是小于或者等于第二个时钟的所有节点，那么前者是后者的祖先可以被遗忘。否则，俩个变化被认为是冲突的需要调和。
在Dynamo中，当一个节点希望更新一个对象，他必须指名要更新的版本。这是通过 传递从先前读取的上下文来实现的，它结合了向量时钟的信息。在处理读请求时，如果Dynamo访问了多个分支，这在语义上是无法调和的，它会返回所有叶子上的对象，以及在上下文中对应的版本信息。使用此上下文的更新被认为已经调和了不同的版本，分支被折叠成单个新版本。
为了演示向量时钟的使用，让我们来考虑一个例子如图3所示。一个客户端写入新的对象。节点（Sx）处理这个键的写操作以增加它的序列号，并且创建了数据向量时钟。系统现在有对象D1和相关的时钟[(Sx,1)]。客户端更新对象。假设相同的节点处理这个请求。系统现在有对象D2和它相关联的时钟[(Sx, 2)]。D2从D1位置下降因此替代D1，然而可能在尚未看到D2的节点上存在D1的副本。让我们假设相同的客户端再一次更新对象并且不同的服务（Sy）处理请求。系统现在有数据D3和它相关联的时钟[(Sx, 2), (Sy, 1)]。
下面假设不同的客户端读取D2，并且尝试更新它，另一个节点（Sz）进行写入。系统现在有D4（D2的后代）它的版本时钟是[(Sx, 2), (Sz, 1)]。D1或D2的节点可以在接受时确定D4和它的时钟，D1和D2被新的数据覆盖，可以被垃圾收集。一个节点知道D3并且接收D4将会发现它们之间没有因果关系。换句话说，D3和D4的变化没有相互反应。必须保持俩个版本数据并呈现给客户（在读取时）以进行语义协调。
现在假设一些客户机读取了D3和D4（上下文将反应俩个值都是由read找到的）。读取的上下文是D3和D4的总结，即 [(Sx, 2), (Sy, 1), (Sz, 1)]。如果客户端执行调和，并且节点Sx协调了些操作，Sx将会更新它在时钟中的序号[(Sx, 3), (Sy, 1), (Sz, 1)]。
向量时钟的一个问题是向量时钟可能会增加许多服务协调写入到对象的大小。在现实中这是不可能的，因为些通常在头n个偏好列表的节点中的一个进行写入。在网络分区的例子或者多个节点失败的例子中，写入请求可能被不在topn个偏好列表中的节点进行处理导致向量时钟的增长。在这个情况下，最好限制向量时钟的大小。为此，Dynamo使用了以下的时钟截断方案：为每个（节点，计数器）对，Dynamo存储一个时间戳，它代表了节点更新数据项最后的时间。当（节点，计数器）对的数量在向量时钟达到了预制（比如10），最后的对见会被从时钟中移除。这种截断模式可能导致调和的低效后台的关系不能被准确交付。然而这个问题还没在生产环境中出现，因此还没有得到彻底的调查。
4.5 执行get()和put()操作
Dynamo中存储任何节点都有资格接受针对客户端任何秘钥的get和put操作。在这一章节中为了简单我们描述了这些操作如何在无故障的环境下进行执行，在之后的章节我们讨论操作在有故障的时候进行执行。
get和put操作执行都是通过HTTTP在亚马逊的特定基础设施处理框架调用的。客户端可以使用俩中策略来查找节点。
- 通过一般的负载均衡器路由请求它们会给予负载信息来选择节点。
- 使用了解分区的客户端库它直接路由请求到合适的协调者节点。
第一种方法的优点是，客户端不必在其应用程序中链接任何特定于Dynamo的代码，第二个策略可以达到低延迟因为它跳过了潜在的转发步骤。
一个节点处理读取和写入操作的节点称之为协调器，一般这是选项列表前N个节点的第一个。如果请求是通过负载均衡器接受的，请求节点可以路由到环中的任意一个节点。如果节点不在请求键首选列表的前N位，在这个情况下，接收请求的节点将不会协调。相反，该节点吧请求转发给首选项列表中的第一个。
在偏好列表中，读取和写入操作相关的前N个健康的节点，跳过那些已经下线的或者无法访问的。当所有节点都运行正常时，将访问键首选项列表中的前N个节点。当节点故障或者网络分区，访问优先级列表中排名较低的节点。
为了保持副本之间的一致性，Dynamo使用了一致性协议类似于法定人数系统所使用的。该协议有俩个可配置的键值：R和W。R是必须参加成功读取操作的节点最小数量。W是必须成功写入操作的节点数量。设置R和W 使得R+W>N产生一个类法定人数的系统。在这个模型中，get(或者put)操作的延迟依赖于最慢的R和W副本。处于这个原因R和W通常被配置为小于N已提供更好的延迟。
在接收到对key的put请求时，协调者生成一个新版本号的向量时钟，并且本地写入新版本。协调者之后发送新的版本（以及新的向量时钟）到N个最高的排行的可达节点。如果只少有w-1个节点响应了，那么写入被视为成功。
类似的，对于get()请求，协调器从首选列表中排名最高N个可达节点中请求该键所有现有版本的数据，然后等待R个响应，然后将结果数据返回给客户端。如果协调器收集了多个版本的数据，它返回所有它认为没有因果关系的版本。然后对不同的版本进行协调，并将取代当前版本的协调版本写回来。
4.6 处理故障：提示转交
在Dynamo中传统的法定人数方法在服务故障和分区期间，即便在最简单的失效条件下也会降低耐久性。为了解决这个问题，它不强制的执行法定人数成员作为替代使用sloppy quorum（草率法定人数）；所有的读取和写入操作在偏好列表中前N个健康的节点上执行；这可能不总是在遍历一致性哈希环遇到的前N个节点。
考虑一个Dynamo配置在图2中让N为3的例子。在这个例子中，如果节点A临时下线下线或者在写入操作中不可达，然后通常存在于节点A上的副本被发送到了节点B。这样做是为了维护所需的可用性和持久性保证。发送给D的副本将会在元数据中有提示，这表明了那个节点是预期的接受者（这个例子中的A）。接受到提示副本的节点将会吧他们保持在独立的本地数据库，并定期扫描，一旦A已经回复，D会尝试将副本交付给A。一旦转换成功，D可以删除来自本地存储的对象，而不需要减少系统中副本的总数。
使用提示转交（hinted handoff），Dynamo确保了读取和写入操作不会因为节点的临时故障而写入失败。需要最高级可用性的应用可以将w设置为1，这确保了只要一个节点在系统中持久的写入键到它的本地存储，系统就可以接受写入。因此只有系统中的所有节点都不可用时写入才会被拒绝。然而，现实中亚马逊服务大部分都在生产环境中设置更高的w以面对所需的持久性水平。我们将在第6章详细的讨论配置N、R和W。
高可用的存储有能力去处理数据中心级别的故障是非常重要的。数据中心故障可能会由于店里供应散热失效，网络故障和自然灾害。Dynamo是可以配置为每个对象都被付出在多个数据中心。本质上键的首选项列表的构造使得存储节点分布在多个数据中心。这些数据中心通过告诉的网络连接起来。这种跨多个数据中心的复制方案允许我们处理整个数据中心的故障，而不会造成数据中断。
4.7 处理永久性故障 ：副本同步
如果系统成员流失率很低并且节点故障很短暂，暗示着切换状态最好。在某些情况下，副本返回到原始副本节点之前变得不可用。为了处理这个和其他耐久性的威胁，Dynamo实现了反熵（副本同步）协议已保持副本同步。
为了快速和最小传输数据的代价，探测副本之间的不一致。Dynamo使用了merkle tree。Merkle tree是一个哈希树，其叶子是单独key的哈希值。树中较高的父节点的其他它子节点的哈希值。Merkle tree的主要优点是，每个树的树干可以单独的被检查，而不需要节点下载整个树或者数据集。此外，Merkle tree帮助减少了需要传输的数据量，同时检查不同数据副本的不一致。例如，如果俩个根节点的哈希值相同，叶子节点在树中是相同的，此时节点不需要同步。如果不是，这意味着一些副本的值是不同的。在这种情况下，节点可能会交换子节点的哈希值，这个过程一直持续到到达树的叶子，此时主机可以识别出“不同步”的键。Merkle树最小化了需要为同步传输的数据量，并且减少了磁盘读取执行在反熵过程中的次数。
Dynamo使用merkle树进行反熵如下：每个节点维护他托管key范围的merkle树（虚拟节点覆盖的键集合）。这允许节点比较，范围内的键是否是最新的。在这个模式下，俩个节点交换他们共同托管的对应键范围内的merkle树的根。随后使用树遍历之前描述的确定节点，如果有任何不同就执行同步操作。这个模式的缺点是，当节点加入或者离开系统许多键的范围会改变，因此需要重新计算树。这个问题已经通过精致的分区被解决，在6.2章中进行描述。
4.8 成员和失败探测
4.8.1 环成员
在亚马逊中节点听起（由于失败和维护任务）通常是转瞬即逝的，但可能会持续很长的间隔。节点中断很少意味着永久的离开，因此不会导致分区作业的不平衡或者副本不可达。类似的手动的错误可能导致无意识的启动新的Dynamo节点。因为这个原因，使用显示的机制来初始化添加或者删除Dynamo中的节点是合适的。管理员使用命令行工具或者浏览器以连接到Dynamo节点并且发出成员改变加入节点到环中或者删除环中的节点。节点服务于请求写入成员改变，并且他持久化存储发送时间。历史的成员改变来自历史，因为节点可以删除或者添加可以来回多次。一个基于gossip协议传播成员的改变并且维护最终一致性的成员视图。每个节点的联系人是在随机时刻被对等的选择，并且节点有效的调和成员在历史中的冲突。
当节点在第一时间启动， 他选择它的token集合（一致性哈希空间的虚拟节点）并且映射节点到他代表的token集上。映射在磁盘上持久化，初始化只包含本地节点和token集合。存储在不同节点上的映射在同一通信之间被协调，这个协调了成员之间的修改历史。因此，分区和防止信息也通过gossip协议传播，并且每个存储节点知道他对等节点处理的token的范围。这允许每个节点转发键的读取写入操作到直接到正确的节点。
4.8.2 外部发现
上面的机制可能暂时导致Dynamo环中的分区。例如，管理员可能联系节点A将A加入到环中，联系节点B将B加入到环中。在这个场景下，节点A和B每个都认为自己是环中的一员，然而双方都不会立刻意识到对方。为了维护逻辑分区，一些Dynamo节点扮演者种子的角色。种子是通过外部机制发现，并且被所有节点知道的节点。因为所有节点最终都用一个种子来调和他们成员的关系，因此逻辑分区是非常不可能的。种子可以在静态配置文件或者配置服务中得到。通常，种子在Dynamo中是彻底的功能性节点。
4.8.3 故障探测
故障探测在Dynamo中被用来避免，当传输分区时暗示副本，在不平衡的节点中的在get和put操作时的尝试通信，故障检测纯粹的局部性概念是完全足够的：如果节点B不响应节点A的信息，节点B考虑出现故障（即便节点B响应节点C的信息）。在Dynamo环中客户端请求在节点通信之间产生的稳定速率存在时，当节点B失败的回复信息，一个节点快速的发现节点B是没有反应的。之后节点A使用备份节点来处理服务请求映射到B的分区；A定期重试B以检查后者的恢复情况。在缺乏客户端节点请求驱动俩个节点之间的流量时，俩个节点都不需要知道另一个节点是可达还是不可达的。
去中心化的故障探测使用了简单的gossip风格的协议，他允许系统中的每个节点学习如何到达（或者离开）另一个节点。有关分散故障检测器和影响其精度的参数的详细信息，请参阅有兴趣的读者。更早的Dynamo的设计使用了去中心化的故障探测已维护故障视图的全局一致性。后来确定，显式节点加入或者离开方法消除了故障状态全局视图的需要。这是因为节点会收到永久性节点添加的通知，通过显式的加入节点加入和离开进行删除，当与其他节点沟通失败，通过独立的节点进行探测（同事转发请求）。
4.9 添加和删除存储节点
当一个新的节点（如X）加入了系统，他得到指派的token编号 ，这个编号在环上是随机分散的。对于每个指派给x的键的范围，可能存在多个节点（小于或者等于N），它们负责处理范围内的秘钥。由于将秘钥的范围分配给X，一些已经存在的节点不长期持有键并且这些节点传输他们的键到X。让我们来考虑简单的启动场景，其中接地那X被添加如图2所示的环中，在A和B之间。当X被添加到系统中，他负责存储范围(F, G], (G, A] 和(A, X]的秘钥。作为结果，节点B，C和D补偿器存储这个表示的范围。因此，节点B，C和D将会提供并且在确认后转移适当的秘钥。当节点在系统中删除，秘钥的再分配发生在相反的过程中。秘钥的重新分配发生在相反的过程中。
操作经历已经展示了这个方法分发键的负载一致的穿过存储节点，他对于应对延迟的徐亚和确保快速启动非常重要。最后通过在资源和目标之间添加配置圆，他确保了目标节点对一给定的key范围不会接受任何重复读传输。
5 实现
在Dynamo中每个存储节点有是哪个主要的软件组件：请求协调，成员与故障探测，以及本地持久化引擎。 所有的这些组件都是用java实现的。
Dynamo的本地持久化组件允许不同的存储引擎插入。Berkeley 数据库（BDB），传统数据存储，BDBJAVA版本，MYSQL。设计一个可插拔的持久化组件的主要原因是为了选择最适合应用访问模式的存储引擎。例如，BDB可以处理典型的十几KB大小的对象，而MySql可以处理更大的对象。应用基于他的对象大小的分布，选择Dynamo的本地持久化引擎。Dynamo大部分的生产实力使用了BDB事务数据存储。
SEDA（Staged Event-Driven Architecture，分阶段事件驱动架构）是一种高性能、可伸缩的系统架构设计模型，旨在更好地管理复杂和高并发的应用程序。SEDA 最初由 Matt Welsh 在其博士论文中提出，用于解决传统线程池模型和事件驱动模型在高负载条件下的不足。
请求协调者组件是在事件驱动的消息传递底层之上构建的。其中消息处理流水线被切分到多个状态类似于SEDA架构。所有的沟通使用Java的NIO管道进行实现。协调者通过收集一个或多个的执行读取和写入请求在客户代理上（在读取的例子中），或者存储数据在一个或者多个节点上（为写入）。在客户端请求的节点上，每一个客户端请求都会创建一个状态机。状态机包含了所有的定义节点对哪些key负责的逻辑，发送请求，等待响应，可能的进行重试，处理回复并且打包响应到客户端。每个状态机实例只处理一个客户端请求。例如，一个读取操作实现了以下的状态机
- 发送读取请求到节点
- 等待需要响应的最小数量
- 如果在给定时间范围内回复的太少，让请求失败
- 否则手收集所有的数据版本并且确定要返回的版本
- 如果版本可用，执行语法的调和并且生成不透明的写入上下文，他包含了持有剩余版本的向量时钟。为了简洁，故障处理和重试状态
在读取响应给调用者后，状态机等待一小段时间以接受任何未完成的响应。如果过期的版本已经在任何的响应中返回了，协调者更新这些节点最后的版本。这个操作被叫做read repair（读取修理），因为它在一个合适的时机修复哪些错过更新的副本，从而减少了反熵协议的负担，不必由它来完成修复工作。
如前所述，写请求通过偏好列表中的头N个节点进行协调。尽管他总是希望前N个节点中的第一个节点来协调写操作，从而在单个位置序列化所有写操作，这个方法会导致负载不均，从而违反SLA。这是因为请求负载在是不一致的分布在不同的对象之间。为了解决这个问题，允许偏好列表的前N个节点中的任何一个进行这个操作。特别地，由于每次写入通常是在一次读取操作之后进行的，因此写入的协调节点被选择为对先前读取操作响应最快的节点，该信息存储在请求的上下文信息中。这个优化允许我们选择在之前的读取操作已经写入数据的节点，从而增加“读你写的”一致性。他也减少了请求处理性能的变化，提高了99.9百分位的性能。
6 经验教训
7 结论
在这篇paper中描述了Dynamo，一个高可用的可扩展的数据存储，用来存储Amazon.com电商平台的核心服务的持久化状态。Dynamo已经提出了可用性和性能的渴望即便，并且成功的处理服务失败，数据故障和网络分区。Dynamo是增量可扩展的并且允许服务拥有者基于当前的负载扩展和下调。Dynamo允许服务拥有者，通过允许它们去调整参数N,R和W去定制存储系统以应对他需要的性能，持久性和一致性SLA。
最近几年Dynamo的成功已经展示了，去中心化的技术可以联合以提供一个高可用的系统。在最具挑战性的应用环境他成功的展示了，最终一致性存储系统可以发布高可用的应用块。