zz from：http://bbs.sciencenet.cn/home.php?mod=space&uid=449420&do=blog&id=480749
【原题】Dynamo: Amazon’s Highly Available Key-value Store
【译文】发电机：亚马逊的高可用键值对存储
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati,
Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall
and Werner Vogels（译注：链接为主要作者的博客）
Amazon.com
摘要
大尺度上的可靠性我们在Amazon.com里面所面对的最重要挑战之一，世界上最大的商务操作之一；即便是最轻微的运行中断都会导致严重的金融恶果并影响到客户信用。Amazon.com这个平台，为许多遍布全球的网站提供服务， 它是在“数以万计的（tens of thousands）的服务器以及位于遍布世界的许多数据中心里头的网络组件”的架构之上构建的。在这么一个尺度上，大大小小的组件总是出毛病，以直面这些失效来进行管理的持续状态（persistent state）方式，驱动了软件系统的可靠性和扩展性（reliability and scalability ）。
该文献提供了有关称之为“发电机”（Dynamo）的“一个高可用键值对存储系统”设计和实现，亚马逊的某些 核心服务使用它来提供随时的经验（an“always-on” experience）。为了达到这个程度的可用性， Dynamo牺牲了在某些失效情形下的一致性。它对“对象版本控制（ object versioning），以及辅助应用冲突解决（application-assisted conflict resolution）”之使用作了“提供一个全新接口给开发者使用”的扩展（makes extensive use of）。
分类和主题描述
D.4.2 【操作系统】：存储管理（Storage Management）；
D.4.5 【操作系统】：可靠性（Reliability）；
D.4.2 【操作系统】: 性能 （Performance）；
通用词（General Terms）
算法(Algorithms)，管理（Management）， 度量（Measurement）， 性能（Performance）， 设计（Design）， 可靠性（Reliability）。
1.介绍（INTRODUCTION）
亚马逊运行了一个世界范围的商业平台，可以对峰值时数以千万计的客户，同时用遍布全球的数据中心理的上万服务器进行服务。亚马逊的平台考虑到“性能，可靠性，效率，以及为了支持储蓄增长从而平台需要高度的可扩展”，故对之有严苛的操作需要。可靠性是最重要的需求之一（译注：还有那几个最重要的需求？），那是因为即便是最轻微的运行中断都会对客户信用造成影响并有引发的金融后果。而且，为了支持持续增长， 平台需要高度可扩（scalable）。
我们的组织从操纵亚马逊的平台（operating Amazon’s platform）中得到的一个经验是就：一个系统的可靠性和扩展性是建基于其应用状态是怎样管理的（how its application state is managed）。亚马逊使用了一个高度去中心化，松耦合， 由数百台服务器组成的面向服务的架构（service oriented architecture）。这种环境下，总是存在一个对存储技术的特定需求（there is a particular need for storage technologies that are always available ）。这么比方吧， 客户希望能够看到以及添加项到它们的购物车，即便磁盘失效，网络路由颠簸不稳（network routes are flapping），或者数据中心被龙卷风给毁了。因此，对购物车进行管理的服务就需要它总是从其数据存储中可写可读，而且其数据需要跨多个数据中心而可得。
我们的标准操作模型就是用来应对在一由“数以百万计的组件”组成的架构中的失效的； 在任何给定的时间总会有小的但却是显著数量的（a small but significant number of）服务器会宕机。就像亚马逊的软件系统需要以“把错误处理当成常见情况，不能影响可用性或者是性能”方式构建。
为了满足可用性和可扩性需要，亚马逊已经发展出了一系列存储技术， 其中有所谓“亚马逊简单存储服务（Amazon Simple Storage Service ）”（从亚马逊外面也可以获得，即称 Amazon S3），是最有名的一个。该文献提供了Dynamo的设计和实现， 这是另外一个高度可用以及可扩的分布式数据存储，用于亚马逊的平台构建。Dynamo 用于管理“有非常高的可靠性（reliability）需求的”服务状态（state of services），而且需要在“可用性（availability），一致性（consistency），成本效益（costeffectiveness ）以及性能（performance）”这些之间作紧密的控制。亚马逊的平台有各种各样差异极大的有不同存储需求的应用集。一个应用选择集（A select set of applications）需要这样的存储技术：该技术足够的灵活（flexible ），可以使得应用设计师能够合宜的基于上述权衡，以成本效益最高的方式去配置其数据存储。
亚马逊平台里的许多服务只需要对数据存储做到主键可达就行了（only need primary-key access to a data store.）。对许多服务而言， 比如那些提供了最佳供应商列表、购物车、客户偏好、会话管理、销售排名以及产品分类的服务， 使用关系数据库的通用模式（the common pattern of using a relational database）会导致效率低下，并限制了扩展性以及可用性。Dynamo 提供了一个唯一简单主键接口（a simple primary-key only interface）以因应这些应用之需求。
Dynamo 利用了一个众所周知的技术的综合以达致可扩展性以及可用性（scalability and availability）：数据是分区的，且重复使用一致性哈希（consistent hashing）【参见：10】， 而且一致性是由所谓“对象版本控制（object versioning）” 促成的（is facilitated by）【参见：12】 。在复制期间的复制件之间的一致性（The consistency among replicas during updates）是由“类似法定人数（quorum-like），以及一个去中心化复制件同步协议（a decentralized replica synchronization protocol）”这样的技术去维护的。Dynamo 采用了一个基于传闻的分布式错误探测与成员协议（a gossip based distributed failure detection and membership protocol.）。Dynamo 是一个对手动管理只有最小介入需求的完全去中心化系统。存储节点可以被添加进Dynamo 以及从中移除，无需任何手动分区（manual partitioning）或者再分配（redistribution）。
在过去几年里，Dynamo 已经成为亚马逊电子商务平台中的一系列核心服务的基础性存储技术。它可以伸张达到极限峰值装载效率（scale to extreme peak loads efficiently），而可以在繁忙的假期购物季（译注：据称美国的这种消费倾向是二战后在布雷顿森林体系经过设计的，但无论这种需求在我们中国人看来如何，需求决定创造是不变的道理）无任何故障停机时间耗费（downtime）。比如，维持购物车的服务（Shopping Cart Service）对千万计的请求进行服务，这就导致了单日中的超过3百万的签出，以及管理着“成百上千的并发动态会话”的会话状态服务。
该工作对于研究社团的主要贡献在于对“不同的技术是如何得以组合，以提供一个单独高可用系统（the evaluation of how different techniques can be combined to provide a single highly-available system）”作了评估。该文献强调了最终 ，一致存储系统可以应用于有高要求应用的产品之中。该文献同样提供了对这些技术进行调优的深入洞察，以符合有非常严格性能需求的产品系统之需求。
该篇文献的结构如下。节2提供了背景，节3提供了相关工作。节4提供了系统设计，节5描述了实现。节6深化了经验与洞见，这是通过在产品中运行Dynamo 获得的，节7对文献作了总结。该文献中有好几处实际上有更多的有用的话要说（where additional information may have been appropriate），但是为了保护亚马逊的商业利益，我们不得不降低对细节的描述程度。为了这个原因， 节六中数据系统内部以及之间的延迟， 节6.2中的绝对请求速率（absolute request rates），节 6.3中的运行中断时长与工作负载是通过合计度量来代替绝对细节的（aggregate measures instead of absolute details）。
2. 背景（BACKGROUND）
亚马逊的电子商务平台由数以百计的服务（services）组成，能顺利的进行“从推荐到实现订购到欺骗检测 ” 工作。每个服务都通过一个良好定义的接口进行暴露，并可以在网络上进行获取。这些服务驻留于这样的基础设施中：由遍布全球的许多数据中心中的数万服务器（servers）组成。这些服务中有些是无状态的（stateless）（即， 对来自其它一些服务进行聚合响 应的服务 services which aggregate responses from other services）有些是有状态的（stateful ）（即，通过对其存储在持久存储上的状态去执行业务逻辑，从而生成其响应的那么一种服务 a service that generates its response by executing business logic on its state stored in persistent store ）。
传统的生产系统把它们的状态存储在关系型数据库中。但是对于许多“更惯用的状态持续模式（usage patterns of state persistence）”而言，关系数据库所能提供的解决方案不甚理想。这些服务大多仅仅经由主键来存储、检索数据，并且不需要RDBMS提供的复杂查询和函数管理功能。这种过度的功能化，需要昂贵的硬件设备以及需要高度技巧化的人员进行操控，这就使得它成为了一个非常低效的解决方案。而且，可用的复制技术是有限的，典型的是牺牲可用性而选取一致性（choose consistency over availability. ）（译注：据Eric Brewer 研究， CAP理论说明 无可能同时满足 一致性 Consistency、可用性Availability、分区容仍性 Partition tolerance）。尽管近几年中取得了许多进步， 仍旧是不容易扩展（scale-out）数据库，或者为了负载平衡（load balancing）而使用的智能分区方案（smart partitioning schemes）。
该片文献描述了Dynamo， 这是一种高可用数据存储技术，强调了这些重要类型的服务之需求。Dynamo 有一个简单的键值接口， 高度可用且带有清晰定义的一致性窗口（is highly available with a clearly defined consistency window），在资源使用方面是有效率的，且有一个简单的扩展方案（scale out scheme）以应对数据集大小的增长或者请求速率的增长。每个使用了Dynamo 的服务在跑的是它自己的Dynamo实例。
2.1 系统假设和需求（System Assumptions and Requirements）
与这个类型的服务适应的存储系统有如下需要：
查询模型（Query Model）：到一个数据项目的简单读写操作唯一的由一个键进行识别。状态以“由唯一键来识别的”二进制对象存储（即 blobs ）。没有操作会跨越多个数据项（data items）而且没有之于关系模式（relational schema）的需要。这个需求是基于对“亚马逊服务的一个重要部分配以该简单查询模型进行工作，而且无需任何关系模式”的观察而来的。Dynamo 针对的都是些，“需要存储的是相对较小的对象（通常小于1MB）”的应用。
ACID 属性：ACID （原子性 Atomicity， 一致性 Consistency， 隔离性 Isolation，持久性 Durability ）
是一些列的属性，确保了数据库的事务能够可靠的运行。在数据库上下文语境中，所谓“事务 transaction”是指在数据上的一个单独逻辑操作。亚马逊的经验显示说提供了ACID保护的数据存储，在可用性方面表现贫乏（tend to have poor availability. ）。这一点已经广为工业界和学术界所承认了【参见：5】。Dynamo 所针对的应用，如果在结果是高可用的情形下，就以较弱的一致性方式进行操作（ACID里面的C）。Dynamo 不会提供任何隔离性防护，并仅仅允许单独键更新（permits only single key updates.）（译注：组合键更新没了？）。
效率（Efficiency）：系统需要在商业硬件基础设施上展开工作。在亚马逊平台上，服务有严苛的延迟性（latency）需求：通常是以99.9%的分布进行衡量。假定（Given that）“状态可达（state access）”在服务操作中扮演了一个关键的角色话，那么存储系统必须能因应这种严苛的SLAs（见节2.2）。服务必须能够对Dynamo进行配置，从而它们可以一致的获取其延迟以及吞吐量需求（consistently achieve their latency and throughput requirements.）。权衡需要在“性能，成本效益，可用性以及持久性保证”之间作出。
其它假设（Other Assumptions）：Dynamo 仅仅在亚马逊的内部服务中使用。其操作环境被认为是无敌意的（non-hostile）并且没有类似“认证和授权（as authentication and authorization）”的安全相关需求。而且，由于每个服务使用了自己的Dynamo特定实例，其初始设计目标能覆盖至多数百存储宿主（targets a scale of up to）。我们会讨论Dynamo 的可扩展性（scalability）限制，以及可能的“相关于其后章节扩展的”可扩展性（scalability ）。
2.2 服务层契约 Service Level Agreements (SLA)
为了确保应用可以可以在受限时间内传递其功能，在该平台中的所有的从属（dependency）即便在约束变紧了，仍需要传递功能（needs to deliver its functionality with even tighter bounds.）。介入一“服务层契约 （Service Level Agreement , SLA）”的客户和服务（Clients and services），一客户和服务都同意的，在多个系统相关的特性之正式协商合同（a formally negotiated contract where a client and a service agree on several system-related characteristics），这很显著的包含了客户期望的请求率的之于特定API的分布，以及在那些条件下之期望的服务延迟。一简单的SLA 例子是，一个保证说它会提供“就每秒500请求的峰值客户装载而言，在300毫秒内对其99.9%的请求进行响应（provide a response within 300ms for 99.9% of its requests for a peak client load of 500 requests per second.）”的服务。
在亚马逊的去中心化面向服务的基础架构中，SLAs 扮演了一个重要的角色。比如，一请求“电子商务站点中的一个”的页面，典型的需要表现引擎（the rendering engine）通过“发送请求到超过150个服务”去构建其反馈。这些服务常常有多个依赖（dependencies），这些依赖常常是其它的服务， 且它对于“有多于一个层级的应用之调用图”而言，并非不常见。为了确保页面表现引擎可以维持页面递送（page delivery）的一个清晰的约束，在调用链中的每个服务必须遵循其性能契约（performance contract）。
图一显示了亚马逊平台体系架构的一个抽象视图， 其中动态网络内容是通过页面表现组件（page rendering components）来生成的，这些组件相继会查询许多其它服务。一个服务可以使用不同的数据存储去管理其状态，并且这些数据存储只有在其服务约束内（within its service boundaries）才是可达的。某些服务通过使用数个其它的服务，表现为聚合器（aggregators）以生成复合响应。典型的，聚合器服务是无状态的（the aggregator services are stateless）， 尽管它们使用了扩展高速缓存（extensive caching）。
业界之用于“形成面向性能的SLA ”一常见方式是描述其使用的如下值：平均值（average）， 中位值（median ）以及期望方差（expected variance）。在亚马逊我们发现，如果目标是构建一个“处于任意地方的客户都能有良好体验的”系统话， 这些度量（metrics）不是足够的好，甚至连一般般都谈不上（rather than just the majority）。比如说，如果使用了扩展个性化技术（extensive personalization techniques ），那么有更长历史的客户需要更多的“影响分布的高端方面的性能（impacts performance at the high-end of the distribution）”处理。一个以均值或者中位值的响应时间作为开始的SLA ，不会关心该重要客户段的性能（will not address the performance of this important customer segment）。为了应对该议题（issue）， 在亚马逊， SLAs 据称且度量是该分布的99.9%（译注：？）。所以选择了99.9%而不是更高的百分率，是在考虑分析了成本效益的基础上作出的，这种分析宣称为了在那的基础上提升性能，成本方面会急剧增加（a significant increase in cost to improve performance that much）。亚马逊产品系统的经验已经显示说这种方法提供了一个更好的全面的相对于“在均值或者中位值基础上能满足SLAs 定义的系统”而言的体验（experience ）。
在这篇文献中有许多对这个分布为99.9百分率(this 99.9th percentile of distributions)的引用，这反映了亚马逊工程师的 来自客户体验立场的（from the perspective of ）不间断的对性能的关注。许多文献都报告了均值，所以这些在“对出于比较的目的而言也是有意义”时也要被包含进来。不过，亚马逊的工程学（engineering）以及优化努力并不看重均值（not focused on averages）。多个技术，诸如负载平衡的写协调器选择（the load balanced selection of write coordinators），都纯粹定位于把性能控制在99.9%的比率。
存储系统常常在“建立起一个服务的SLA”中扮演了一个重要的角色，特别是在如果业务逻辑相对是轻量级之时， 就像是许多亚马逊服务中的一个例子。状态管理然后就变为一个服务的SLA之主要组件。Dynamo 的一个主要设计考虑是：让服务能控制它们的系统属性（to give services control over their system properties），诸如持久性以及一致性， 以及让服务自己去在“功能 functionality、性能 performance 以及成本效益 costeffectiveness”之间作出权衡。
2.3 设计考量（Design Considerations）
用于商业系统的数据复制算法，传统的会执行同步复制协调（synchronous replica coordination ），以提供强一致性数据可达接口（a strongly consistent data access interface）。为了达到这种层次的一致性，这些算法不得不牺牲掉“在某些特定失效场景中的”数据可用性。比如（For instance），远非是处理“一个答案之正确性”的不确定 ，数据在直至“绝对必定正确（it is absolutely certain that it is correct）”之前是不可以获得的（译注：怎么提前于可达之前获悉这种正确性？）。在非常早期的复制数据库工作中，当应对网络失效的可能性时， 强一致性（strong consistency）以及高数据可用性（high data availability ）两者鱼与熊掌不可同时兼得（cannot be achieved simultaneously ），这一点是非常著名的【参见：2，11】。像这样的系统与应用需要知晓何属性可以在何条件下获取。
对于有服务和网络宕机倾向的系统而言，可用性可以通过使用优化复制技术（optimistic replication techniques）来增加，这种增加的改变被允许散布到后台的复制件，可接受并发、非连接方式的工作（concurrent, disconnected work is tolerated）。这种方式（译注：指使用优化复制技术来增加可用性的方式）的挑战是它会导致有冲突的改变，而这是必须被检测到并解决的。该种冲突处理解决方案（process of conflict resolution）引入了两个问题：何时以及谁去解决这些冲突。Dynamo 被设计成一个最终一致数据存储（eventually consistent data store）；是即所有的更新在所有的复制件中最终可以显现出来（all updates reach all replicas eventually）。
一个重要的设计考量是去决定何时执行“解决更新冲突的处理 （ the process of resolving update conflicts）”，在读或写期间是否应当去解决冲突。许多传统数据库是在写期间执行冲突解决方案的（execute conflict resolution during writes），并使得读的复杂性简单化（keep the read complexity simple ）【参见7】。在这样的系统中，写操作可能会被拒绝，如果数据存储在给定时间内不能达到所有的复制件（或者是一大部分）。就另一方面而言，Dynamo 专注于（targets）所谓“总是可写（always writeable）的数据存储（即，该数据存储对写而言是高可用的）”之设计空间。对一系列的亚马逊服务而言， 拒绝客户更新会导致客户的一个恶劣体验。比如，购物车服务必须允许，即便出于网络和服务失效情况，客户能够从他们的购物车中添加或者移除项。该需求迫使我们把冲突解决方案的复杂性（the complexity of conflict resolution）推向（push to ）有序读操作（reads in order ），从而确保写永远不会被拒绝。
下一个设计决策就是谁执行该冲突解决方案的流程（who performs the process of conflict resolution）。这一点可以通过数据存储或应用来完成。如果冲突解决方案是由数据存储完成的，它的选择就相当的有限了（译注：它指数据存储么？）。在这种情形下， 数据存储只可以使用简单的策略（policies），比如一种叫做“最后写胜出 last write wins”【参见22】（译注：迟来的和尚喝浓粥）的解决更新冲突方式。从另一方面看，既然应用对数据模式是很清楚的（the application is aware of the data schema），它就可以决定何种冲突解决方案的方法对客户体验来说是最好的（decide on the conflict resolution method that is best suited for its client’s experience）。比如，维护了客户购物车的那个应用可以选择对冲突版本“合并 merge”并返回一个单独统一的购物车。即便是不考虑这种灵活性（flexibility），一些应用开发者可能不想写他们自己的冲突解决方案机制（conflict resolution mechanisms），而是选择把它推到（push it down to）数据中心去，这将会继续选择一个类似“最后写胜出 last write wins”的简单策略。
其它被包含进设计的关键原则是：
增加扩展性（Incremental scalability）：Dynamo 应当能够从一个存储宿主（storage host）（以后都用“节点”来指称）向外扩展（scale out），同时对“系统的操作员以及系统本身”有最小的影响。
对称性（Symmetry）：Dynamo 中每个节点就像其同伴（peers）一样应当有相同的责任集；不应当有出跳的（distinguished ）节点或者有特殊角色的节点或者有额外的责任集。在我们的经验中， 对称性能简化系统调试以及维护的处理（symmetry simplifies the process of system provisioning and maintenance）。
去中心化（Decentralization）：一个对称性的扩展，该设计的品位，较之中心化控制（centralized control）更倾向于去中心化的端到端技术（decentralized peer-to-peer techniques）。在过去， 中心控制导致了运行中断，而目标就是尽量的避免它。这导向了一个更加简单，更加可扩展， 更加可用的系统。
异质性（Heterogeneity）：系统需要能够在其运行的架构中开拓异质性（be able to exploit heterogeneity in the infrastructure it runs on.），比如，工作分布必须和和单独服务器的能力相适应（the work distribution must be proportional to the capabilities of the individual servers）。这在”添加一个新节点获取更高容量，无需在一次中就更新所有的宿主”中是本质重要的。
3.相关工作RELATED WORK
3.1 端到端系统 （Peer to Peer Systems）
有数个端到端(P2P)系统已经注意到了(look at)数据存储以及分布中的问题了。
第一代P2P系统，例如Freenet 以及Gnutella【旁注1】，都主要作为文件共享系统（file sharing systems）来使用。这些都是非结构化（unstructured）的P2P网络的例子，这里端到端之间的覆盖链接都是任意连接的（the overlay links between peers were established arbitrarily.）。在这些网络中，一查找询问（search query）常常会在网络上泛溢（is usually flooded through the network）以找到尽可能多的共享数据的端。P2P系统进化到下一代，就是众所周知的结构化P2P网络。这些网络使用了（employ）所谓的“全球一致协议（globally consistent protocol ）”以确保任意节点可以有效的对一个查找询问（search query）进行路由（route），以达到某些有期望之数据的端。类似Pastry 【参见16】以及Chord 【参见20】一样的系统使用了路由机制（routing mechanisms）以保证询问可以在一个受到约束的跳转（hops）数量内得到答复。为了降低由多跳转路由引入的附加延迟性（the additional latency introduced by multi-hop routing），某些P2P系统（比如，【参见14】）使用了O(1)路由，其每一个端都在本地含有足够的路由信息（where each peer maintains enough routing information locally），从而它可以将请求“在常量跳转数内”路由到合宜的端。
【旁注1 http://freenetproject.org/, http://www.gnutella.org】
各异的存储系统，诸如大洋存储（Oceanstore）【参见9】以及帕斯特（PAST）【参见17】，都构建于这些路由之上（built on top of these routing overlays.）。“大洋存储”提供了一个全球、事物、持续的存储服务，能支持序对广泛复制序列化更新（serialized updates）。为了允许并发更新，同时又许多随广域锁（wide-area locking）而来的内在问题，它所用了一个基于冲突解决方案的更新模型。冲突解决方案在【21 管理每周连接复制的河口存储系统之更新冲突 】中有介绍，用于减少丢弃事务的数目（the number of transaction aborts）。大洋存储是通过“处理一系列的更新（by processing a series of updates），选择它们之内的一个总序（choosing a total order among them），以及其后将它们原子性的以前述之顺序来应用”解决冲突的。这是为了“ 其中的数据在一个非受信基础架构中进行复制（the data is replicated on an untrusted infrastructure）”的环境构建的。来比较一下，帕斯特（PAST）为了“持久性以及不变对象（persistent and immutable objects）”，在Pastry 顶端（on top of ）提供了的一个简单抽象层（simple abstraction layer）。它假设应用可以在其上对必要的存储语义（storage semantics）（例如可变文件 mutable files）进行构建。
3.2 分布式文件系统与数据库 （Distributed File Systems and Databases）
分布式数据的性能、可用性以及持续性在文件系统以及数据库系统社区得到了广泛的研究学习。相较于“仅仅支持平面名字空间（only support flat namespaces）的”P2P存储系统，分布式文件系统典型的支持层次体系的名字空间（hierarchical namespaces）。像Ficus【参见15】 和Coda【参见19】 这样的系统，在复制文件中，以牺牲一致性获取了高可用性。更新冲突（Update conflicts ）典型是通过使用“专门化的冲突解决流程（specialized conflict resolution procedures.）”来管理的。远地系统（The Farsite system ）【参见1】是一个分布式系统，不似NFS一般使用任何中心化服务（does not use any centralized server like NFS.）。“远地”使用复制（replication），达到了高可用性以及扩展性。谷歌文件系统【参见6】是另一个分布式文件系统，构建用来管理（hosting）谷歌内部应用的状态。GFS使用了一个带单独master服务的简单设计，用于管理“整个元数据以及数据在何处被分片到大块以及存储在何种大块服务器”。“河口”（Bayou ）是一个分布式关系数据库系统，允许非连接操作（disconnected operations）并提供最终数据一致（eventual data consistency）【参见21】。
在这些系统之中，河口（Bayou），终曲（Coda）以及无花果（Ficus）都允许非连接操作，以及对“网络分离以及运行中断”议题是有弹性的（resilient to issues such as network partitions and outages.）（译注：指可以灵活的应用这些挑战？）。这些系统在冲突解决程序（conflict resolution procedures）方面各有差异。比如，终曲（Coda ）以及无花果（Ficus）执行的是系统级别的冲突解决，河口（Bayou）允许的是应用级别的解决方案。不过它们都保证了最终一致性（eventual consistency）。和这些系统类似，Dynamo允许即便在“网络分离，以及使用各异的冲突解决机制去解决更新冲突”之时，读和写操作仍旧得以持续。分布式块存储系统，比如FAB 【参见18】把大的对象分隔到小的块中（split large size objects into smaller blocks）并把每个块以一个高可用性方式来存储。来比较一下这几种系统， 在该情形下（译注：何情形？）一个键值存储更加的适合，其原因是：
它倾向于存储相对而言较小的对象（大小小于1M）
键值存储更容易基于每个应用进行配置（译注：指可以个性化定制？）。
古物（Antiquity）是一个广域分布式存储系统，设计用于因应多服务失效（multiple server failures） 【参见23】。它使用了一个安全日志来存储数据完整性， 在多个服务器上为了持久性（durability）原因，复制每个日志，使用拜占庭容错协议（Byzantine fault tolerance protocols）来确保数据一致性（data consistency）。相较于古物（Antiquity）而言，Dynamo 并不把注意力放在“数据一致性，安全，以及用于构建受信系统”上面。Bigtable 是一个用于管理结构化数据的分布式存储系统（a distributed storage system for managing structured data. ）。它使用了一个稀疏的，多维的分类拣选映射（a sparse, multi-dimensional sorted map）允许应用使用多属性去获取其数据【参见2】。较之大表（Bigtable），Dynamo 关注的应用是这样的：仅需配以“关注高可用性的主键”的键值可达（key/value access），这种可达性指的是“即便在网络分离或服务宕机发生，更新都不会被拒绝”（require only key/value access with primary focus on high availability where updates are not rejected even in the wake of network partitions or server failures.）。
传统的复制关系数据库系统专注于“对复制数据确保强一致性（strong consistency to replicated data）”问题。尽管强一致性提供给应用写操作一个方便的编程模型， 不过这些系统都在“扩展性和可用性”方面受到限制【参见7】。在处理网络分离方面，这些系统有软肋，是因为它们典型的提供强一致性保证（strong consistency guarantees）。
3.3 讨论（Discussion）
Dynamo是在“目标关注需求（target requirements）”的意义上区别于前述提及的（aforementioned）去中心化（decentralized）存储系统的（译注：何种目标关注需求？）。首先，Dynamo 主要关注的是需要“持续可写（always writeable）的数据存储”的应用，这之中没有更新会由于“失效，或并发写（failures or concurrent writes）”而被拒绝。这对许多亚马逊应用而言是一个关键需求（译注：指上述的强更新）。其次，就像早前注意到的，Dynamo 是为了“在单一管理域中的基础设施（infrastructure），之中所有节点都认为是可信的”构建的。再次，使用了Dynamo的应用无需支持层级化的名字空间（hierarchical namespaces）（这在许多文件系统中是常常需要的），亦无需支持复杂关系模式（complex relational schema）（这种模式被传统数据库所支持）。最后，Dynamo 是为对延迟敏感的应用（latency sensitive applications）构建的，需要至少99.9%的读写操作在数百毫秒（milliseconds）时间内被执行。为复合这些严苛的延迟性需求，对我们而言“避免通过多个节点的路由请求（avoid routing requests through multiple nodes ）”是必要的（这是典型的设计，被诸如和弦 Chord 以及 酥点 Pastry 这样的分布式哈希表系统所采纳）。这是因为多跳转（multihop ）路由会增加响应时间的变数（variability），进而在更高比率上增加了延迟性（thereby increasing the latency at higher percentiles. ）。Dynamo 可以这样来描述：一个0跳转的DHT（a zero-hop DHT）（译注：DHT 指 分布式哈希表），这之中每个节点维护了足够的本地路由信息，可以直接把一个请求路由给合宜的节点。
4. 系统架构（SYSTEM ARCHITECTURE）
“需要在一个产品中进行设置的操作”之存储系统的体系结构是复杂的。除了实际的数据持久化组件外，系统还需要之于“负载平衡（load balancing）、成员资质（membership ）、错误检测（failure detection）、错误恢复（failure recovery）、复制件同步（replica synchronization）、 超载处理（overload handling）、状态转换（ state transfer）、 并发和作业排产（concurrency and job scheduling）、请求编集（request marshalling）、请求路由（request routing）、系统监控和报警 （system monitoring and alarming）和配置管理（configuration management） ”有扩展性以及鲁棒性解决方案。描述各个的解决方案是不可能的，所以这篇文献就专注于Dynamo用到的核心分布式系统的技术：分区（partitioning）,复制（ replication）,版本控制（ versioning）, 成员资质（membership）,错误处理（failure handling）与 扩展性（scaling）。
4.1 系统接口（System Interface）
Dynamo 通过ygie简单接口来存储相关于一个键的对象；该接口暴露了两个操作：get()与put()。get(key)操作会定位相关于在该存储系统中的键的对象复制件（locates the object replicas associated with the key in the storage system），并返回一个单一对象，或带有冲突版本控制的“带上下文的”对象列表（a list of objects with conflicting versions along with a context.）。put(key, context, object) 操作确定了“基于相关键”对象的复制件应当被放在何处，并将复制件写到磁盘。之于该对象的“内容编码系统元数据（The context encodes system metadata）”对调用者而言是不透明的（is opaque to），并且包含了诸如对象的版本这样的信息。上下文信息随对象一起存储（The context information is stored along with the object），从而系统可以验证“put请求提供的”上下文对象之正确性。
Dynamo 把“键和由调用者提供的对象（the key and the object supplied by the caller）”两者都认为是，一个不透明的字节数组（an opaque array of bytes）。它对键使用了MD5 哈希，从而生成一个128字节的标识符， 这可以用于决定“要对键进行服务负责的”存储节点。
4.2分区算法（ Partitioning Algorithm）
Dynamo 的一个关键设计需求在于它必须可以“逐渐可扩”（scale incrementally）。这需要一种能动态对“分布在节点集(即，存储宿主 storage hosts)上的（over the set of nodes）”数据分区的机制。Dynamo的分区机制依赖于一致性哈希（consistent hashing）去把负载分布到多个存储宿主上去（distribute the load across multiple storage hosts. ）。就一致性哈希而言【参见10 一致哈希和随机树：减轻万维网热点的分布式高速缓存协议】， 哈希函数的输出范围（the output range of a hash function）被当作是一个固定的圆形空间（a fixed circular space）或者说是“环（ring）”（最大的哈希值围绕着最小的哈希值 wraps around to）。系统中的每个节点被赋予了一个随机值，以这样的形态（within this space ）来表达其在环上的“位置”。各个被一个键所标识的数据项将通过“对该数据项的键进行哈希以产生环上的位置”赋予一个节点，在这之后（译注：数据项被赋予了节点之后），以顺时针遍历该环从而找到第一个“其位置大于项的位置（the first node with a position larger than the item’s position）”节点。（译注：节点也即存储宿主，其位置是先前提及的随机值；数据项的位置译者认为是通过“对该数据项的键进行哈希以产生环上的位置”生成的）。从而，每个节点变得会对环中的介于“节点本身以及其在环中的前驱（predecessor）节点”之间的区域负责。一致性哈希（consistent hashing）的本质优势在于：一个节点的来去（departure or arrival）仅会影响它的直接邻域（immediate neighbors）其他节点不受此影响。
基本的一致性哈希算法提出了一些挑战（presents some challenges）。首先，对环上的各个节点赋予一个随机的位置，这会导致非统一的数据和负载分布（non-uniform data and load distribution）。其次， 基础算法在执行节点时明显表现出异质性（heterogeneity ）。为了因应这些议题， Dynamo 使用了一致性哈希的一个变体（类似于在【参见：10 一致哈希和随机树：减轻万维网热点的分布式高速缓存协议 ，20 和弦：英特网应用的一个可扩展端到端查询服务 】中的使用）。为此计（To this end），Dynamo 使用了所谓的“虚拟节点（virtual nodes）”概念。一个虚拟节点看上去好似系统中的单独节点，但是每个节点可以对多于一个的虚拟节点负责。实际上（Effectively），当一个新的节点被添加到系统时，它被赋予到这个环里头的多个位置（以后用令牌 tokens 指代）。对Dynamo’s 分区模式的微调（fine-tuning Dynamo’s partitioning scheme）过程将在节6中讨论。
使用虚拟节点带来了以下几个好处：
如果一个节点变得不可用了（由于宕机或者路由维护），由该节点把控的负载将最终散布到剩余的可达节点中去。
当一个节点变得再次可用时，或者一个新的节点添加到系统中来时，新的可用节点会接受一个粗略相等的（ roughly equivalent amount of）来自各个其它可用节点的装载（load from each of the other available nodes.）。
一个节点可以负责的虚拟节点数量，可以基于其容量来决定，可以对物理架构的异质性负责。
4.3 复制（Replication）
为了达到高可用性和持久性，Dynamo 在多个宿主上对其数据进行复制（replicates its data on multiple hosts）。每个数据项在N个宿主上复制， 这里N是基于实例可配的（a parameter configured “per-instance”.）。每个键，K，被赋予一个协调器节点（a coordinator node）（在前面的节中描述过）。该协调器管理着“在其范围内减弱的（fall within its range）”数据项之复制。除“本地存储各个在各自范围内的键”之外， 协调器会用“ 环中的顺时针后继的第N-1个节点”重复（译注：重复为译者加，译者认为是指第某个元素而不是相继的某些元素）复制这些键 （In addition to locally storing each key within its range, the coordinator replicates these keys at the N-1 clockwise successor nodes in the ring. ）。这样做的结果就是在系统中每个节点对环的介于“它与它的第N个前驱之间的”范围负责（is responsible for the region of the ring between it and its Nth predecessor）。在图2中，节点B在节点C和节点D处复制了键K，而且对它进行了本地存储。节点D会存储那些“在(A, B], (B, C], 和(C, D] 范围内减弱”的键。
对存储某个特定键负责的节点列表（The list of nodes ）称之为偏好列表（the preference list）。系统被设计成，将在节4.8中讨论，在该系统中的每个节点可以决定哪些节点，就任意特定键而言， 应当在这个列表中。为了对节点失效负责（account for）， 偏好列表包含了多于N个的节点。要注意到虚拟节点的使用，“对某个特定键而言的前N个后继位置，可能为少于N个的直接物理节点所有（即是说 一个节点可能对第N个位置的把控多于一个 a node may hold more than one of the first N positions）”这是可能的。为了说明这一点（To address this），一个键的偏好列表通过“略去环中的位置（skipping positions in the ring）”被构建起来，以保证说，该列表仅包含了直接物理节点。
表一： Dynamo使用到的技术以及各自优势总结
4.4 数据版本控制（Data Versioning）
Dynamo 提供了最终一致性（eventual consistency）， 即允许更新异步的被散布到所有的复制件中。一个对put()的调用可能在“更新被应用到所有复制件”之前返回其调用者，这就导致了这么一个场景：一个接下来的 get()操作可能返回一个“不是最近更新过的那个”对象。在没有失效的情况下，那么就有一个对更新散布时间的限制（a bound on the update propagation times）。不过，在某些失效场景中（比如服务器运行中断或者网络分离），更新在一个扩大了的时间周期中下，可能不会到达所有的复制件（updates may not arrive at all replicas for an extended period of time）。
在亚马逊平台中有一类应用就可以容忍这种不一致性（tolerate such inconsistencies），并可以在这些条件下被构建起来进行操作（be constructed to operate under these conditions）。比如，购物车应用需要使“添加购物车”操作不会被遗漏或者拒绝。如果该购物车的最新状态是不可用的，且一个用户对该购物车的老旧版本作了更新， 那么这种更改仍旧是有意义的，应当被保留下来。但是在同时，它又不能对当前不可用的购物车状态取而代之， 因为它本身可能包含了应当被保留的改变。注意到“添加购物车”与“从购物车中删除项”操作都被转化为（be translated into）对Dynamo提出请求（put requests to）。当一个客户希望添加一个项到一购物车，同时最新的版本是不可用的，这个项就被添加到较老的版本中去了，而且有差异的版本将在后来进行调和。
为了提供这种类型的保证， Dynamo 把每个修改（modification ）的结果当作“数据新的、不可变的版本”对待。它允许一个对象的多版本在系统中的同一时间里呈现出来。在大多数时候， 新的版本把先前的版本纳入期内， 而且系统本身就可以决定何为权威版（the authoritative version ）（语法调和 syntactic reconciliation）。然而，在和当前更新合并过程中出现失效时，版本分支（version branching ）可能会发生，这将会导致一个对象的有冲突版本生成。在这些例子中， 系统不能对相同对象的多个版本调和，客户必须施行该调和，从而将数据演变的多分支消减而成为一个(语义调和 semantic reconciliation)（译注：定于一）。一个典型的毁减（collapse）操作的例子是对一客户的购物车的不同版本进行归并（merging）。使用了该调和机制，一个“添加到购物车”的操作就永远不会丢失了。然而，被删除的项会重新浮出水面（译注：？）。
理解以下这一点是很重要的，特定的失效模式可以潜在的导致系统中存有数据的不是两个而是多个的版本。目前的网络分离（network partitions ）中的更新以及节点失效可以潜在的导致一个对象有直接版本子历史（an object having distinct version sub-histories），这使得系统需要在未来进行调和（reconcile ）。这就要求我们设计应用显式的对相同数据的多版本之可能性进行承认（explicitly acknowledge the possibility of multiple versions of the same data）（为了永不丢失任何更新之故）。
Dynamo 使用了所谓的向量钟（vector clocks ）技术【参见12】（译注：即表1中提及的Dynamo使用的针对写操作高可用性问题的“读期间带调和向量钟”技术）。一个所谓的“向量钟”实际上是一个对（节点，计数值）的列表（A vector clock is effectively a list of [node, counter] pairs ）。一个向量钟和每个对象的每个版本相关。可以去决定某对象的两个版本是否“是在互相平行的分支之上，或者之间有因果顺序”，这是通过检查它们的向量钟做到的。若第一个对象的钟之计数器小于等于第二个钟里面的所有节点话（If the counters on the first object’s clock are less-than-or-equal to all of the nodes in the second clock），那么第一个就是第二个向量钟的祖先（ancestor）因而可以被忘记。不若此， 则这两个改变被认为是有冲突的，并需要调和（reconciliation）。
在Dynamo中，当一个客户期望更新一个对象，必须说明它在更新的是何种版本。这是通过“传递它从先前的读操作获取的上下文（passing the context it obtained from an earlier read operation）”做到的，这种读操作包含了向量钟的信息。基于对一个读请求的处理，若Dynamo 到达了“不能同步的去调和”的多分支，他就会返回所有的在叶子处的对象， 以及上下文中相应的版本信息。一个使用了该上下文的更新被认为是已调和了有差异的版本（have reconciled the divergent versions）且分支已近塌缩为一个单一的新版本（the branches are collapsed into a single new version）。
为了说明使用向量钟，让我们考虑这样一个例子（在图3中显示）。一个客户写了一个新对象。设有一个叫做Sx的“控制了对这个键的写操作”的节点，增加了其序列号（sequence number）并且使用它来生成数据的向量钟。系统现在有一个叫做D1的对象以及相关的钟[(Sx, 1)]。客户更新了该对象。假设相同的节点也控制了该请求。系统现在同样有叫做D2的对象，其相关的钟为[(Sx, 2)]。D2 继承自 D1，因此会 重写（over-writes）D1，然而可能存在D1的“驻留在还未见D2的节点（lingering at nodes that have not yet seen D2）”的复制件。让我们假设相同的客户端再次更新对象，而且一个不同的服务器，叫做Sy，去处理该请求。系统现在有数据D3及其相关的钟[(Sx, 2), (Sy, 1)]。
下一步是假设一个不同的客户读取了D2并试图去更新它， 而且另一个节点，叫做Sz是作了这个写操作。系统现在有D4对象（是D2对象的子孙），其版本钟是[(Sx, 2), (Sz, 1)]（译注：版本钟应指向量钟）。一个了解D1和D2的节点可以根据收到的D4及其钟去决定，D1 和 D2被新数据重写了（overwritten ）并可以被垃圾回收（garbage collected）。一个知晓D3的节点并收到D4 将会发现在它们之间没有临时的关联（causal relation）。换言之，在D3和D4中都存在互相不可见的改变（there are changes in D3 and D4 that are not reflected in each other）。数据的两种版本为了“语义调和（semantic reconciliation）”的原因，必须被保存下来并提供给一客户（根据一次读操作）。
现在来假设某些客户读取了D3 以及 D4两者（上下文会反映出两者值都被该读操作所发现 the context will reflect that both values were found by the read）。读取器的上下文是对D3和D4的钟之一个总结，名为[(Sx, 2), (Sy, 1), (Sz, 1)]。如果客户执行了调和，且节点Sx协调了写操作，Sx 就会更新自己的在这个钟里面的序列号。新数据D5将有下面的钟：[(Sx, 3), (Sy, 1), (Sz, 1)]。
针对向量钟的一个可能的议题是：如果许多服务器把写操作协调到一个对象之中的话，向量钟的大小可能会增大。在实践中， 这是不太可能的，这是因为写操作常常是由“偏好列表中的最上面的N个节点中的某一个（one of the top N nodes in the preference list）”把控的（译注：偏好列表的结构应该是一个栈）。在网络隔离和多服务器失效的情况下，写请求可能由不是在“偏好列表中的最上面的N个节点中的某一个”的节点把控，引发了向量钟的大小的增长。在这些场景中，限制向量钟的大小是值得期待的。为了这个目的（To this end），Dynamo 使用了下列钟阶段模式（clock truncation scheme）：伴随着每个对（节点，计数器），Dynamo 存储了一个“反映了该节点最后一次更新数据项的”时间戳。当向量钟里头的（节点，计数器）对的数量达到了一个阈值（比如说10），最老的对被从钟里头移除。很明显，这个截断模式会导致在调和时的低效（inefficiencies in reconciliation），因为下降的关系（the descendant relationships）不能被精确的推导出来（derived accurately）。然而，该问题并没有在产品中浮现过，因此，该议题没有被全面的研究过。
4.5 get 和put操作的执行 （Execution of get () and put () operations）
在Dynamo 中任何存储节点都可以接受客户之于任何键的get和put操作。在本节， 为了进行简化（for sake of simplicity），我们描述了这些操作是如何在无故障环境（failure-free environment）中被执行的，在其后的章节中我们描述了读和写操作是怎样在故障期间执行的。
get和put两者的操作 都使用了在HTTP之上的亚马逊基础架构之请求处理框架（using Amazon’s infrastructure-specific request processing framework over HTTP）。在客户选择一个节点上，有两种策略：
对请求通过“ 将会基于负载信息去选择一个节点的，所谓通用负载平衡器（a generic load balancer）”进行路由。
使用一个分离感知客户库（a partition-aware client library），将请求直接路由到合宜的协调器接节点。
第一种选择方式的优势是客户不必将在应用中把任何特定代码链接到Dynamo ，反之，第二种方案达到了较低的延迟率，这是因为它跳过了潜在的转递步骤（can achieve lower latency because it skips a potential forwarding step）。
一个把空了读或者写操作的节点就被叫做是协调器（coordinator）。典型的，这是偏好列表中在前N个节点中的第一个。如果请求是通过一个负载平衡器（load balance）进行接收的， 那么请求以获取一个键的过程就可能被路由到环中的任意随机节点。在该场景中， 接收到请求的节点，如果不在请求键的偏好列表之顶端的N个元素中 ，就 不会对它（译注：应指该请求）协调。取而代之的是，那个节点会递送请求到偏好列表中在前N个节点中的第一个（forward the request to the first among the top N nodes in the preference list）。
“涉及到偏好列表中前N个健康的节点的”读和写操作会略去那些下沉或不可达的节点（skipping over those that are down or inaccessible）。当所有节点都是健康之时， 一个键的偏好列表的顶端N个元素是可达的。当存在节点故障或者网络分离时， 在偏好列表中排名考后的节点才是可达的（nodes that are lower ranked in the preference list are accessed）。
为了维护其复制件之间的一致性，Dynamo 使用了一个“类似那些在 法定人数系统（quorum systems）中使用的”一致性协议（ consistency protocol ）。这个协议有两个键配置值：R 和 W。 R是 为了进行一次成功的读操作必须参与进来的节点数的最小值（译注：R应指一次成功读之节点下限阈值）。W是为了进行一次成功的写操作必须参与进来的节点数的最小值（译注：W应指一次成功的写之节点下限阈值）。这样设置R和W，R + W > N 会导生一个类似quorum一样的系统。在这个模型中，一个get (或者 put)操作的延迟（latency ）取决于（is dictated by）这R（或W）个复制件中最慢的那个。为了这个原因， R和W(译注：似指R和W之和) 常常被配置成小于N， 以提供更好的延迟性（latency）。
一旦（Upon ）收到了对某个键的一个put()请求，协调器就会为新版本生成向量钟，且在本地写下这个新的版本。协调器然后就发送新的版本（和新的向量钟相伴生）到N个由高到低排序方式下可达节点（to the N highest-ranked reachable nodes）。如果至少W-1个节点有反馈，就可以认为写操作是成功的了。
类似的， 对一个get（）请求，协调器会对就那个来自“ 对那个键而言的偏好列表中的N个由高到低排序方式下可达节点的键”而言的数据之所有现存版本进行请求。如果协调器结束于收集数据的多个版本（ends up gathering multiple versions of the data），它就会返回 所有被其认为是无因果相关的节点（deems to be causally unrelated）。有差异的版本然后才被调和（reconciled），调和后的“取代了（superseding）当下版本的”那个版本被回写（written back）。
4.6故障处理：提示移交（ Handling Failures: Hinted Handoff）
如果Dynamo 使用了传统的quorum 方式，那么它会在服务器故障以及网络分离时不可用， 并会即便在最简单的故障情况下缩减持久性（reduced durability）。为了对这点进行补救，它不强求严苛的法定成员资质，取而代之的是，使用了“随意的法定人”（sloppy quorum）；所有的读和写操作都是在“来自偏好列表的前N个健康的节点”上施行的（译注：设计关键点之一），当在一致哈希环上遍历（walking the consistent hashing ring）之时这可能不总是遭遇到的前N个节点。
考虑Dynamo 配置的在图2中给出的例子，其中N=3（译注：指有B、C、D三个节点）。在这个例子中， 如果节点A临时性的下去了，或者在写操作期间不可达，那么一个“寄居在A上的（that would normally have lived on A）”复制件现在就被发送给节点D。这样做得以维持期望的可用性以及持久性保证（the desired availability and durability guarantees）。被发送到D的复制件会在其元数据中有一个提示（hint）说何节点才是该复制件的意向接受对象（which node was the intended recipient of the replica ）（本例中是A节点）。收到了提示复制件的那些节点（Nodes that receive hinted replicas ）会在一隔离的“周期性进行扫描的”本地数据库里面保留它们（译注：它们指被发送的那些复制件，场景提及的被发送制件是一个，现在已经是多个了，是什么造成了这种转化？）。一旦（Upon ）检测到A已经恢复了（译注：前述场景假设“节点A临时性的下去了”），则D会试图去把复制件递送给A。一旦传递得以成功， D就可以从其本地存储中删除该对象，而无需减少系统中复制件的总量。
使用所谓的“提示移交（hinted handoff）”，Dynamo 能确保读和些操作不会由于“临时节点或网络故障”而失效。需要可用性方面最高优先级的那些应用，可以把W设为1， （译注：用于写的节点可以只有1个，译者认为由于明显的，写操作吃力了，导致了一致性下降，这种高优先级的可用性是牺牲了一致性换来的）。因此， 写请求只有在“在系统中所有节点都不可用”时才被拒绝（？）。然而在实际中， 大多数亚马逊产品集中的服务会设置一个更高的W，以期符合持久性级别（to meet the desired level of durability）。一个更加详细的有关N,R和W 配置的描述出现在节6中。
“一高可用存储系统能够处理一整个数据中心失效”这一点势在必行。数据中心失效源自于能源中断（power outages）， 制冷故障（cooling failures）， 网络故障（network failures）以及天灾（natural disasters）。Dynamo 被配置成，每个对象都在多个数据中心之间被复制。本质上， 一个键的偏好列表被以“存储节点在多个数据中心之间被散布（the storage nodes are spread across multiple data centers）”方式构建起来。这些数据中心通过高速网络链接互联。这种“在多个数据中心之上的复制（replicating across multiple datacenters）”模式允许我们控制整个数据中心失效而无一个数据中断运行。
4.7 处理持久失效：复制件同步（Handling permanent failures: Replica synchronization）
提示移交在“系统的成员资质流失低（membership churn is low ），节点故障是很短暂的”情况下工作最佳。在某些场景中，被提示的复制件会在“它们可以返回到初始复制件节点”之前变的不可用。为了把控这样那样的对待持久性的方式， Dynamo 使用了一种所谓的“逆熵协议 anti-entropy protocol ”（复制件同步） 来保证复制件同步（译注：表一技术总结之从长久失效中恢复问题的对策使用到了逆熵， anti-entropy 可参考信息熵）
为了快速的检测到复制件之间的不一致性，以及最小化需要传输的数据量，Dynamo使用了erkle 树【参见13】。所谓的Merkle 树是一棵哈希树，其中叶子节点是各自键之值的哈希。 这棵树中更高的父节点是它们各自的子节点的哈希。Merkle 树的本质优势在于：这棵树的每个分支都可以被独立的检测，无需节点去下载整棵树或者整个数据集。更有甚者，Merkle 树帮助减少了在“核查复制件之间的不一致性”时的需要被传输的数据量。比如，两棵树的根之哈希值一致的话，那么叶节点的值也一样，且节点之间无需同步（译注：何意？）。若不如此，就是说某些复制件的值是不同的。在这种情况中（译注：这种情况指根哈希值不一样），节点可以改变子（children）的哈希值，且这个过程持续直至到达该树的叶子，当此之时，宿主就可以确定该键“不是同步的 out of sync”了。Merkle 树最小化了为了同步的原因，而需要传输的数据的量，并且减少了“在逆熵处理中执行”之磁盘读的量。
Dynamo 使用了Merkle 树实现逆熵，如下：每个节点“对它所寄宿在的每个键范围（键集被一虚拟节点覆盖）”维护了一个独立的Merkle树。这就允许节点去比较在一个键范围中的那些键是否是最新的。在这个图景中（scheme），两个节点交换Merkle 树的，相应于“它们常常寄宿在里头的”键范围的根（two nodes exchange the root of the Merkle tree corresponding to the key ranges that they host in common）。随其后至， 使用了如上描述的树遍历计划（the tree traversal scheme），那些节点会决定它们是否有任何什么不同，进而执行合宜的同步动作。这种计划的劣势是在一个节点在系统中来去之时，许多键范围会更改，因而就要求树（译注：指Merkle 树）。被重计评估（recalculated）。不过，该议题会通过“精巧分离计划（refined partitioning scheme ）”在节6.2中述及。
4.8 成员资质与失效检测 （Membership and Failure Detection）
4.8.1 环的成员资质（Ring Membership）
在亚马逊，节点中断运行环境（由于故障以及维护任务之故）的情况常常是临时的，不过会持续一段时间（extended intervals）。一节点中断运行很少意味着永久分离，从而不应导致指派划分的再平衡（rebalancing of the partition assignment）或者对不在可达的复制件的修复（repair of the unreachable replicas.）。类似的，手动操作可以导致无意的启动一个新的Dynamo 节点。由于这些原因， “使用一个显式的机制去对添加的节点作初始化，以及从Dynamo 环中移除一个节点 ”这点被认为是适当的。一管理员使用了命令行工具或者通过浏览器去连接到一个Dynamo 节点，并对一成员资质之“添加一个节点到一个环，或者从一个环中移除一个节点”变更进行发布。对请求进行服务的那个节点对成员资质变更进行写操作（writes the membership change ），且要发布进行持久存储 （its time of issue to persistent store）。对历史的一个成员资质的变更，是因为一个节点可以被多次的移除以及回添。一基于传闻的协议（gossip-based protocol）对成员资质的变更进行散布（propagates membership changes），并维护一有关成员资质的最终一致视图（maintains an eventually consistent view of membership）。每个节点和一个端相联系，这个端是每秒钟随机选取的，而且这两个节点有效率的对它们的持续成员资质变更历史进行调和（efficiently reconcile their persisted membership change histories）。
当一个节点第一次启动时，它会选取它的令牌集（set of tokens ）（处于一致哈希空间中的虚拟节点 virtual nodes in the consistent hash space）并把节点（译注：应指那些虚拟节点）映射到它们各自的令牌集（maps nodes to their respective token sets）。映射操作被保留在“磁盘上”（The mapping is persisted on disk ），且最初仅包含本地节点以及令牌集（initially contains only the local node and token set）。存储在不同的Dynamo 节点上的映射会在“调和了成员资质变更历史的同一个通讯交换 （during the same communication exchange）”期间被调和。因此，分区和分布配置信息（partitioning and placement information）也经由“基于闲聊的协议”进行散布，并且各个存储节点对其相应端（译注：应指和该节点进行通讯的另外一个节点）控制的令牌环是一清二楚的（each storage node is aware of the token ranges handled by its peers）。这就允许每个节点直接的转递一个键的读写操作到正确的节点集。
4.8.2 外部发现（External Discovery）
前述的机制可以临时的导致一个逻辑分隔的Dynamo环（a logically partitioned Dynamo ring）。比如， 管理员可以 把节点A联系添加入该环， 然后就是把节点B联系添加到该环。在这个场景中，节点A和节点B各自都会把自己看作是环中的一个成员， 不过它们对互相的存在却不是立即就知晓的(yet neither would be immediately aware of the other. )（译注：在什么情况下会确认对方的存在？）。为了放置逻辑分隔， 一些Dynamo节点扮演了种子的角色（play the role of seeds）。所谓“种子”是指这样的节点：通过外部机制被发现（discovered via an external mechanism ）且会被所有节点知悉。由于所有的节点最终会将它们的成员资质和“种子”相调和，所以逻辑分隔就很不受待见（highly unlikely）（？）。种子可以通过来自静态配置的方式获得，也可以通过一个配置服务的方式获得。典型的种子是Dynamo 环中的全功能节点（fully functional nodes ）。
4.8.3 失效侦测（ Failure Detection）
Dynamo 中的错误侦测用来避免“在get和put操作，传输划分以及提示移交期间的”和不可达端的通讯企图（avoid attempts to communicate with unreachable peers）。为了避免通讯尝试的失效之目的，一个失效侦测的纯粹逻辑概念完全能够满足：如果节点B并不对节点A的消息进行响应的话（甚至即便节点B对节点C的消息进行了响应），节点A就可以把节点B视作是失效（failed）。在提供了一个稳定速率的“生成Dynamo中的内部节点通讯”客户请求时，如果B没有对这条消息进行响应的话，一个节点A很快会发现说节点B没有反映（译注：应是在节点A 和节点B都互相知悉对方的存在场景下）。节点A然后就使用代替的（alternate ）节点（译注：什么样的节点有资格作为代替的节点？）对“映射到B的那些分区（map to B’s partitions）”的请求进行服务：在“客户请求以驱动两个节点之间的通讯（client requests to drive traffic between two nodes）”之缺位情形下，这两个节点都无需知悉对方是否可达以及能够响应。
去中心化的失效检测协议（Decentralized failure detection protocols）使用了一个简单的闲聊风格的协议（gossip-style），这允许系统中的各个节点能够了解（learn about）其它节点的去任（the arrival or departure ）。如果需要对“去中心化的失效检测（decentralized failure detectors），以及参数如何影响了其精确性” 细节进行了解，可以参考【8 可扩有效分布式失效探测器 】。Dynamo 的早期设计使用了一个去中心化的失效检测器（a decentralized failure detector ）以维护“失效状态的”一个全局一致视图（a globally consistent view）。其后关于“排除了关于失效状态的全局视图需求之外部节点去任方式（he explicit node join and leave methods obviates the need for a global view of failure state）”作出了决定。这是因为节点就“经由外部节点之去任的持久节点的去任”被通知，且临时节点失效经由“当各自独立的节点之间的通讯（在转递请求时）失效时”被检测到。
4.9存储节点的去任（Adding/Removing Storage Nodes）
当一个新的节点，就叫X，添加到系统中时，它就获取了“随机散布在环上的”若干令牌。对赋予节X的每一个键范围而言， 可能会存在若干节点（少于等于N）(译注：根前文，据每个数据项至多在N个宿主上复制，N可配，似可认为键范围是一种数据项)，这些节点当前尚能对“在其令牌范围内减弱的键”（keys that fall within its token range）有效把控。由于“键范围到X的分配（the allocation of key ranges to X）”， 一些已经存在的节点无需对它们键中的一些个再留着了（some existing nodes no longer have to some of their keys），且这些节点会把那些键传到X。然我们来考虑一个简单的自举（bootstrapping）场景，其中节点X被添加到环中，在图2中显示，介于A与B之间。当X被添加到系统中后，它（译注：指被添加进来后的X节点）就要对“在范围(F, G], (G, A] and (A, X]中存储键”负责（译注：前文提及每个节点对环的介于“它与它的第N个前驱之间的”范围负责 ）。其结果就是， 节点B，C，以及D不再需要在各自的范围内存储键了（no longer have to store the keys in these respective ranges）（译注：？）。因此，节点B，C以及D就要对“传输合宜的键集”进行基于来自X的确认下的偿还（will offer to and upon confirmation from X transfer the appropriate set of keys）（译注：？）。当一个节点从系统中移除后，键的再分配就会以逆向过程的面目出现（happens in a reverse process）。
操作经验显示说，该方式下对“键分配的装载（he load of key distribution）”之分布，在诸存储节点上是不一致的，只一点对“应因延迟性需求以及确保快速自举”是很重要的。最后， 通过对源以及目的之间的一轮确认的添加，那就能确保说： 目的节点就“一给定的键范围”而言，没有收到任何复本传输。
5.实现（IMPLEMENTATION）
在Dynamo， 每个存储节点都有三个软件组件：请求协调（request coordination）， 成员资质与失效侦测（membership and failure detection）， 以及一个本地持久引擎（a local persistence engine）。所有这些组件都是用JAVA实现的。
Dynamo的本地持久组件允许不同的存储引擎以可插拔方式工作。目前在使用的引擎是伯克利数据库（Berkeley Databas， short for BDB）事务数据存储【旁注 2】， BDB Java编辑器， MySQL， 以及一个带持久备份存储的内存缓存器（an in-memory buffer with persistent backing store）。之所以要设计一个可插拔的持久组件是为了选择最适合应用的可达模式的那么一个存储引擎（to choose the storage engine best suited for an application’s access patterns.）。比方说吧，BDB 可以把控“典型的是按照数万字节的顺序（typically in the order of tens of kilobytes）”的对象，虽然MySQL可以处理更大的对象。应用基于“它们对象大小的分布”之上，选取Dynamo的本地存储引擎（local persistence engine）。Dynamo的产品实例（production instances）中的大多数使用了所谓的BDB 事务数据存储。
【旁注2 http://www.oracle.com/us/products/database/berkeley-db/index.html 译注：原链接失效】
请求协调组件是构建在底层为事件驱动消息之上的（is built on top of an eventdriven messaging substrate），这个底层中消息处理管道被分割为多个阶段，类似SEDA 体系结构【参见24 SEDA: 一为了良态、可扩缩的英特网服务之架构 】。所有的通讯都是用JAVA的 NIO 频道实现的（译注：指 java.nio.channel 包）。协调器为了客户而执行读和写请求，通过收集来自一个或者更多节点的数据（这是在读的情况下发生的）或者在一个或者多个节点上存储数据（这是在写的情况下发生的）。每个客户请求会导致生成一个“处于收到了客户请求的节点上”的状态机。状态机存有所有的逻辑，服务于“用于确认对一个键负责的节点（identifying the nodes responsible for a key）， 发送请求（sending the requests），写应答（waiting for responses），潜在的重试（potentially doing retries），对响应进行处理以及对客户的响应进行打包（processing the replies and packaging the response to the client） ”。每个状态机实例仅执行一个客户请求。比如，一个读操作实现了以下状态机：(1) 把读请求发送给节点（the nodes），(2) 对所必需的响应的最小数量进行等待，(3) 如果在一给定时间约束内接收到的响应太少， 请求视为失败，(4) 否则就收集所有的数据版本，并决定将要被送还到何节点（译注：determine the ones to be returned ）,(5) 如果版本被激活（译注：怎样才算是被激活？），就执行语法调和（syntactic reconciliation），并生成一个包含了“把所有剩余版本进行归入的”向量钟的，不透明的写上下文。为失效处理的简洁之缘故，重试状态就不考虑了（For the sake of brevity the failure handling and retry states are left out.）（译注：设计权衡之一）。
对读的响应被返回到调用者后，状态机会等待一小会儿以接收任何显著的反馈。若陈旧的版本被返回到任何反馈中， 那么协调器就以最新的版本取更新这些节点。这个过程叫做读修复（read repair ）， 这是因为该过程能见缝插针的（at an opportunistic time）修复错过最近更新的复制件，缓解了逆熵协议对该过程的实行（relieves the anti-entropy protocol from having to do it）。
先前就注意过，写请求是由“偏好列表中的顶端N个节点中的一个”来协调的。尽管“让在顶端N个节点中的第一个节点取对写操作进行协调，从而把所有的写操作序列化在一个单独的位置当中”是很理想的，但是这种方式会导致SLA中产生出不均匀的负载分布（led to uneven load distribution resulting in SLA violations）。这是因为该请求装载（the request load）本身就不是一致的分布在诸对象上的（译注：有果必有因）。其因对就是（译注：希望消除不均匀负载分布）， 在偏好列表的顶端N个节点中的任何一个被允许对写操作进行协调。特别要提的是， 由于每个写操作通常都是随着一个读操作来的， 就写操作而言的额协调器就被选为“对先前读操作（这被存储在请求的上下文信息中）响应最快的”节点。这种优化允许我们对“有由前一个读操作读取过的数据 ” 的节点进行拣选，从而就“读取你所写的”而言，增加了获取一致性方面的可能性。这种优化同样减低了执行请求处理的变异性，把性能提升到99.9%。
6.经验教训（ EXPERIENCES & LESSONS LEARNED）
Dynamo 用于多个有不同配置的服务。这些实例的差异是由“它们的版本调和逻辑，以及读写quorum特征”引起的。以下是Dynamo 使用的主要模式：
业务逻辑细节调和（Business logic specific reconciliation）：这是Dynamo常见的用例。每个数据对象在诸节点上复制。在差异版本的情况下， 客户应用执行其自己的调和逻辑。先前讨论过的购物车服务就是这种分类的一个主要例子。是业务逻辑通过“对一客户的购物车之不同版本进行归并” 调和了对象。
基于时间戳的调和（Timestamp based reconciliation）：这个机制和前一个机制（译注：指Business logic specific reconciliation）的不同仅仅在于调和的机制。在差异版本的情况下，Dynamo 执行了简单的基于时间戳的调和逻辑，即所谓的“最后写胜出（last write wins）”；亦即，有最大物理时间戳值的对象会被选为正确的版本。维护了客户的会话信息的服务是一个关于“使用该模式的服务”的好例子。
高性能读引擎（High performance read engine）：既然Dynamo 声称要构建为一个“总是可写的（always writeable）”数据存储，少许服务就调整其quorum 特征，且把它（译注：指Dynamo）作为高性能读引擎来使用（译注：题指的高可用和这里的高性能似乎变为一回事了）。典型的， 这些服务有一个高的读请求速率（a high read request rate ）以及少许的更新。在这个配置中， 典型的R被设置成1，W被设置为N。(译注：据前文， R是 为了进行一次成功的读操作必须参与进来的节点数的最小值, W是为了进行一次成功的写操作必须参与进来的节点数的最小值)。对这些服务而言， Dynamo 提供了分区和于诸节点上复制它们的数据的能力（the ability to partition and replicate their data across multiple nodes），从而，提供了所谓的“增加扩展性（incremental scalability）”。这些实例中的一些以“为在更重量级的备份存储中的数据存储的，正式持久高速缓存（the authoritative persistence cache for data stored in more heavy weight backing stores）”面貌出现。维护产品分类以及促销项这类服务归入此类。
Dynamo 的主要优势是，其客户端应用可以对 N, R 以及W的值进行调整，从而可以获得它们期望的“性能、可用性、持久性”级别。打个比方，N的值决定了每个对象的持久性。Dynamo用户所使用的典型的N取值为3。
而 W和 R的值影响了对象的可用性，持久性以及一致性。比如，如果把W设成1（ 译注： W是为了进行一次成功的写操作必须参与进来的节点数的最小值）， 则只要系统中还存在一个可以成功的对写请求进行处理的节点，就永不会拒绝一次写请求（译注：但是这样写操作费时就很长了，给终端造成了一个可用性很差的体验）。然而， W和R 的值设的这么低会增加不一致性的风险，因为“即便它们不会被大多数复制件处理，写请求（write requests ）会被认为是成功的并并返回客户”（译注：得赶紧处理掉，否则就可能会出现不一致性，但是这种低设置下大所复制件无能为力）。这同样会在当“即便它只是在小数量的节点上持续着，一次写操作请求成功的返回给客户（ when a write request is successfully returned to the client even though it has been persisted at only a small number of nodes） ”时，引入一个对持久性（durability ）而言的易损窗口（ a vulnerability window）。
传统智慧是让可用性与持久性其头并经（holds that durability and availability go hand-in-hand）。不过，这一点在这里就不是必须的了。比方说吧，对持久性而言的易损窗口（the vulnerability window for durability）可以通过增加W来下降。这可能会增加“拒绝请求”的可能性（从而增加了可用性 availability）（译注：作者理解的可用性）。这是因为更多的存储宿主需要工作才能处理一个写操作请求（more storage hosts need to be alive to process a write request）。
Dynamo 中多个实例的常用(N,R,W) 配置是(3,2,2). （译注：这些实例被配置成，每个数据项在3个宿主上复制，参与到写的最小节点数是2，参与到读的最小节点数也是2）。这些值被选取以因对“性能（performance）、持久性（durability）、一致性（consistency）以及可用性（ availability）”方面的SLAs之必要级别。
在这一节中所提供的所有测量来自于一个活动的系统操作，其配置是(3,2,2)，且运行数个以百计的节点且配以同质（homogenous）硬件配置（译注：所以可认为没有测量SLA在异构体系架构中的扩展性方面的额能力）。在早先体积过的，Dynamo 的每个实例包含了位于多个数据中心中的节点。这些数据中心典型的是通过高速网络链接（high speed network links）来连接的。回忆一下“为生成一个成功的对R (或 W)个节点响应的get (或put)”需要对协调器进行响应。很显然， 数据中心之间的网络延迟性影响到了响应时间，以及节点（以及它们所在的数据中心）的选取，如此以至于（such that）SLAs 的应用目标遇到了挑战（are met）。
6.1 平衡性能与持久性（Balancing Performance and Durability）
由于Dynamo 是运行在标准商业硬件组件之上，其I/O吞吐量远较之高端商用服务器（high-end enterprise servers）为低，故为读和写操作提供持续的高性（consistently high performance）能并非不重要。多个存储节点涉及到读和写操作中来使得这更具挑战性，这是因为这些操作的性能是受到R或W个复制件中最慢的那个限制的。图4显示了均值以及99.9th比率的Dynamo在30天内的读写操作之延迟性。如图所示， 延迟性表现为一个清晰的日间模型，其是在到达的请求速率中的日间模型之结果（the latencies exhibit a clear diurnal pattern which is a result of the diurnal pattern in the incoming request rate）（即， 在白天和晚上在请求速率方面有显著差异）。更有甚者， 写延迟性较之读延迟性为高，这明显的是因为写操作总是会导致磁盘获取动作（disk access）。而且，这个99.9th 百分比的延迟性是在200毫秒附件发生的，且是以数量级（order of magnitude）的方式高于均值。这是因为 99.9th 百分比延迟性是受到诸多因素影响的，诸如请求装载时的可变性（variability in request load），对象大小， 位置模式（locality patterns）。
图4：于2006年12月请求的峰值季节，就读和写操作而言的均值以及99.9百分比的延迟性 。 The intervals between consecutive ticks in the x-axis correspond to 12 hours.X轴的连贯运转间距相当于12小时（译注：约为12个波形）。随一日间模型而来的延迟性与请求速率相当，以及99.9百分率的延迟性是较之均值而言的数量级提高（an order of magnitude higher than averages）。
如图所示， 延迟性表现为一个清晰的日间模型，其是在到达的请求速率中的日间模型之结果（the latencies exhibit a clear diurnal pattern which is a result of the diurnal pattern in the incoming request rate）（即， 在白天和晚上在请求速率方面有显著差异）。更有甚者， 写延迟性较之读延迟性为高，这明显的是因为写操作总是会导致磁盘获取动作（disk access）。而且，这个99.9th 百分比的延迟性是在200毫秒附件发生的，且是以数量级（order of magnitude）的方式高于均值。这是因为 99.9th 百分比延迟性是受到诸多因素影响的，诸如请求装载时的可变性（variability in request load），对象大小， 位置模式（locality patterns）。
在这个级别的性能对一系列的服务都是可达的，面向客户的少量服务需要更高级别的性能。对这些服务而言， Dynamo 提供了对“之于性能的持久性保证而言”的权衡方面之能力。在优化中，各个存储节点在其主存中维护了一个对象缓存。各个写操作被存储在该缓存中，并通过一个写线程（writer thread）被周期性的写到存储。在该图景下（scheme）， 读操作第一次检查被请求的键是否在这个缓存中出现。果如此，则对象就从取代“存储引擎”的缓冲器中读取。
这种优化会导致“在峰值通讯期间即便是对一个非常小的有数千对象的缓存而言 ”低于 99.9th的百分比延迟，其因子是5（lowering the 99.9th percentile latency by a factor of 5 during peak traffic even for a very small buffer of a thousand objects）（见图5）。而且，如图所见， 写缓存器会平滑的导致一个更高比率的延迟性（write buffering smoothes out higher percentile latencies）。显见， 该图景用持久性对性能作了交换（this scheme trades durability for performance. ）。该图景中， 所谓一个“服务碰撞”（ a server crash）会导致对“已经在缓存中排上队了”的写操作之遗失。为了减少持久性风险，写操作被重定义成由协调器去选择 N个复制件的一个以执行“可持续写”（have the coordinator choose one out of the N replicas to perform a “durable write”）。由于协调器只对W个响应进行等待， 写操作的性能不会被“由单一的复件执行的持久写操作方面的性能（by the performance of the durable write operation performed by a single replica）” 影响。
6.2 确保一致装载分布（Ensuring Uniform Load distribution）
Dynamo 使用了一致性哈希（consistent hashing ）去对其存在于诸复制件上的键空间进行分割（partition its key space across its replicas），并且保证统一装载分布（uniform load distribution）。一个统一键分布（uniform key distribution ）可以帮助我们达到统一装载分布（uniform load distribution），假设键的可达分布不是高度倾斜的 （assuming the access distribution of keys is not highly skewed）（译注：指这种分布比较的均匀？）。特别而言，Dynamo的设计作了以下假设：即便“在某处对获取分布而言，有一个显著的倾斜（even where there is a significant skew in the access distribution）”，还是在 分布的繁忙端有足够的键（there are enough keys in the popular end of the distribution），从而繁忙键的装载（the load of handling popular keys）可以通过分区（partitioning）被一致的散布到节点（be spread across the nodes uniformly）。这一节讨论了Dynamo见到的装载平衡，以及有关装载分布的不同分区策略的影响（impact of different partitioning strategies on load distribution.）。
为了对这个装载平衡（load imbalance）以及其响应的请求装载（request load）进行研究，各节点收到的请求之总数被以24小时，这被裂解为30分为一个间隔（broken down into intervals of 30 minutes
），为一个周期进行了衡量。在一个给定的时间窗口， 一个节点被认为是“处于平衡”（inbalance）的，如果该节点的请求装载偏离了由小于特定阈值的那么一个值导致的装载均值的话。（the node’s request load deviates from the average load by a value a less than a certain threshold ）。否则，该节点被视为是“不平衡的”（out-of-balance）。图6显示了在该时间周期中的那些 “不平衡的（out-of-balance）(以后就用不平衡率 “imbalance ratio”标识)”的节点的一小部分（译注：注意inbalance与imbalance ）。作为参考（For reference），整个系统所收到的相应的请求装载，在这个时间周期中也被标绘出来（the corresponding request load received by the entire system during this time period is also plotted.）。如在图中所见，不平衡率（the imbalance ratio）随着增加的装载而减少（the imbalance ratio decreases with increasing load ）。比如，在低装载时的不平衡率可高大20%（during low loads the imbalance ratio is as high as 20% ），在高装载时它就接近到10%了。很直观的， 这可以这样作出解释：在高装载的事实下，一个大数量的繁忙键被获取，且由于键的统一分布而使得这种装载能均匀的进行分布（ the fact that under high loads, a large number of popular keys are accessed and due to uniform distribution of keys the load is evenly distributed.）。然而，在低装载期间（此时装载只是被测量到的峰值装载的1/8），更少的繁忙键得以获取（fewer popular keys are accessed），这产生了一个更高的装载不平衡。
该节讨论了Dynamo的分区图景如何随着时间而逐步改变，以及其对装载分布的影响。
策略1：每个节点有T个随机令牌，且由令牌值分隔：这是部署于产品中的初始策略（而且在4.2节中有描述）。在这个图景中， 每个节点被赋予了T个令牌（这是从哈希空间中随机的统一选取的 chosen uniformly at random from the hash space）。所有节点的令牌以它们在哈希空间中的值排序。每两个连续的令牌定义了一个范围（a range）。最后一个以及第一个令牌形成了一个包裹在“哈希空间中的最高值以及最低值”的外面的所谓“范围 （range）”。由于令牌是随机选取的，范围的大小也就各异了。当节点在系统去留时，令牌集亦改变，相应的范围（the ranges ）也要作改变。注意到空间需要维护每个节点的成员资质，其是随着系统中的节点数的增长而线性增长的。
当采用了这个策略， 会遭遇到以下问题。首先，当一个新的节点添加到系统中时， 它需要从其它节点中“偷取”其键范围（it needs to “steal” its key ranges from other nodes）（译注：其它节点为什么不给呢？译者觉得这里有必要用罗尔斯的无知之幕的观念来看待，无它）。然而， 控制键范围脱离新节点的那些节点（the nodes handing the key ranges off to the new node）。必须扫描它们的本地持久存储（local persistence store）以检索数据项的合宜集（retrieve the appropriate set of data items）。要注意到，执行这样的一次在产品节点上的扫描操作是很困难的（is tricky），因为扫描是高度资源密集型操作（ highly resource intensive operations ）且它们需要在后台执行，不能影响到客户性能。这就需要我们以最低优先级别运行自举任务（run the bootstrapping task at the lowest priority）。然而，这会显著的减缓自举处理（slows the bootstrapping process ），且在繁忙的购物季，当节点要在一天中处理百万计的请求时， 自举需要费上几乎一整天才能完成（the bootstrapping has taken almost a day to complete）。遇到的第二个问题是，当一个节点连接到或离开系统时，键范围由许多节点变更来控制（the key ranges handled by many nodes change），且之于新范围的Merkle 树需要重估，这不是于一个生产系统的执行之无关紧要的操作。遇到的最后一个问题是，由于键范围中的随机性，没有一种容易的方式可以对整个键空间取得一张快照，这使档案的处理变得复杂。在这个图景中， 对整个键空间进行归档（archiving the entire key space）需要我们分别从各个节点中独立的去对键进行检索，这是很没有效率的。
这种策略的本质议题在于“数据分区的图景（schemes）和数据配置被纠缠在一起了（the schemes for data partitioning and data placement are intertwined. ）”。这么比方吧，在某些情形下，倾向于对一个系统添加更多的节点，以应对请求装载方面的增加（to handle an increase in request load. ）。然而，在这个场景下，不大可能只添加节点而无对数据分区（data partitioning）方面的影响。理想情况下， 为分区和配置使用各自独立的图景（it is desirable to use independent schemes for partitioning and placement）.。为了这个目的（译注：目的是，配置和分区各自使用不相干扰的独立图景）来评估一下以下策略：
策略2：每个节点有T个随机令牌，且分区大小相同：在这个策略中，哈希空间被分割为Q个大小相当的分区/范围，且每个节点被赋予T个随机令牌。Q常常是被这样设置的 Q >> N且 Q >> S*T，这里S是系统中的节点数。在这个策略下， 令牌仅用于构建“将哈希空间中的值映射到节点的有序列表 ”的功能（build the function that maps values in the hash space to the ordered lists of nodes）以及不用于决定分区（not to decide the partitioning）。一个分区是放置“当从分区的尾端顺时针的遍历一致性哈希环时所遭遇到的头N个唯一节点中”（A partition is placed on the first N unique nodes that are encountered while walking the consistent hashing ring clockwise from the end of the partition. ）。图7展示了N=3时的该策略。比如，在从包含了键K1的分区之尾端进行环的遍历时，会遭遇到 节点A，B，C。这种策略的主要优势在于1）对分区和分区配置作了解耦，2）.使在运行时改变配置（placement）成为可能。
策略 3：每节点有Q/S个令牌，等量分割（equal-sized partitions）：类似于策略2， 这个策略会把哈希空间分隔到Q个大小相等的分区（equally sized partitions），且分区的配置（the placement of partition）从分区的图景中解耦出来了。更进一步说，每个节点被赋予Q/S个令牌，这里S是系统中节点的数目。当一个节点离开系统时， 其令牌将随机的分布到剩余的节点之上，从而这些属性得以保留。类似的， 当一个节点添加到系统中来，它会从系统中的其它节点处以一种保留属性的方式（in a way that preserves these properties）去“偷（steals）”令牌。
这三种策略的效率经过 S=30 以及 N=3方式设置下（译注：即系统有30个节点，每个数据会在3个宿主上复制）的系统评估。然而，以一种公平的方式去比较这些不同的策略是很难的，这是因为不同的策略有不同的配置去对其效率调优。这么比方吧，策略1的装载分布属性（the load distribution property）依赖于令牌的数量（就是T），与此同时，策略3是基于分区的数量（即Q）。一种公平的比较这些策略的方式是，在所有的策略都使用相同数量的空间去维护其各自的成员资质信息时，评估它们装载分布的各自倾斜（evaluate the skew in their load distribution ） 。比如，在策略1中每个节点都需要维护所有节点在环中的令牌位置（each node needs to maintain the token positions of all the nodes in the ring），在策略3中，每个节点需要维护“关于赋予到各个节点的分区”的信息（each node needs to maintain the information regarding the partitions assigned to each node）。
在我们的下一个试验中，这些策略被通过有差异但相关的参数（T与Q）所评估。各个策略的装载平衡效率被以“需要在各个节点中维护的不同大小的成员资质信息”参数配置方式测量，这里装载平衡效率被定义为一个比率：由“每个节点服务的请求的均值”（average number of requests）对“由最热节点进行服务的请求的最大值”的比率（as the ratio of average number of requests served by each node to the maximum number of requests served by the hottest node.）。
结果在图8中给出。如图所见，策略3达到了最佳的装载平衡效率，而策略2的装载平衡效率是最差的。在一小会儿内（For a brief time），策略2在“处理Dynamo 实例的从策略1使用到策略3的使用之迁移”期间，以临时安装面貌出现（served as an interim setup）。较之策略1，策略3获得了更好的效率，且对各个节点维护的成员资质信息之大小降低了3个数量级（reduces the size of membership information maintained at each node by three orders of magnitude.）。当存储不是主要的议题时，节点就周期性的把成员资质信息作为闲聊对象（gossip the membership information periodically），且同样的，期望把这种信息尽可能的保持紧凑。对这一点多说一句，策略3有利的且对由于以下原因，故更加便于部署：(i)更快的自举/恢复（Faster bootstrapping/recovery）：由于分区范围（partition ranges）是固定的，它们可以存储在独立的文件中，这就意味这一个分区可以作为一个单元通过简单的传输该文件去重定位（be relocated ）（避免了定位特定项所需要的随机存取 avoiding random accesses needed to locate specific items）。这就简化了自举和恢复的处理。 (ii)解出归档（Ease of archival）：周期性的对数据集之归档对大多数亚马逊存储服务而言是一个强制需求。对通过Dynamo 进行存储的整个数据集进行归档在策略3下是很容易的（Archiving the entire dataset stored by Dynamo is simpler in strategy 3），这是因为分区文件可以被独立的归档。作为对比，在策略1中，令牌是被随机选取的，对存储在Dynamo中的数据进行归档需要把键从独立节点中分别捡取出来（retrieving the keys from individual nodes separately ），这通常是很慢而且低效的。策略3的劣势在于对节点的成员资质进行变更需要进行协调，以对赋值所需要的属性作保存。
6.3 差异版本：何时与 多少（Divergent Versions: When and How Many）?
我们先前注意过，Dynamo 被设计成一致性与可用性两者的权衡（tradeoff consistency for availability）。为了对之“基于一致性之上的，于不同失效之精确影响（the precise impact of different failures on consistency）”有所理解，需要对多个因素取得精确数据，这些因素有：运行中断长度（outage length），失效类型（type of failure）， 组件可靠性（component reliability），工作负载（workload ）等等。提供这些具体的细节数字超出了这篇文章覆盖的范围。然而，该节会讨论一个良好的度量总结（a good summary metric）：活跃产品环境中的应用可见之“有差异的版本数”。
一个数据项的有差异版本在两种场景下会浮现出来。第一种场景是当系统面临失效场景时（facing failure scenarios），譬如，节点失效（node failures），数据中心失效（data center failures），网络隔离（network partitions）。第二个场景是当“系统把控了之于单独数据项的大数量并发写操作（the system is handling a large number of concurrent writers to a single data item）， 以及多个节点结束对并发更新的协调（multiple nodes end up coordinating the updates concurrently）”时发生的。从可用性（usability ）以及效率两种角度来看，倾向于在任何给定的时间内尽可能低的保留差异版本数（it is preferred to keep the number of divergent versions at any given time as low as possible. ）。如果版本不能仅仅基于向量钟去单独的在句法上调和（syntactically reconciled）的话，那么它们就需要被传递到业务逻辑以进行语义调和（semantic reconciliation）。语义调和（semantic reconciliation ）引入了对服务的附加装载，故最小化对语义调和的需要是值得期待的。
在我们的下一个试验中，返回到购物车服务的版本数以24小时为周期被描绘下来（was profiled for a period of 24 hours）。在这个周期中， 99.94%的请求会见到正确的那个版本（saw exactly one version）；0.00057% 的请求会见到2个版本； 0.00047%的请求会见到3个版本，0.00009%的请求会见到4个版本。这表明差异版本很少会被生成。
经验显示说“有差异的版本数的增加”（the increase in the number of divergent versions）不是建基在“失效（failures ）” 之上的，而是由于“并发写操作的数量之增加（increase in number of concurrent writers）”之故。并发写操作的数量之增加，常常是由繁忙的机器人（即，自动客户端程序）触发的，而不是人。这个议题的细节不会被讨论，是因为这涉及到了本故事的敏感细节（译注：科学论文无细节保留，为了复制验证之故，但是工程论文在这点上就显示出不同了）。
6.4 客户驱动或服务驱动（Client-driven or Server-driven）
如在节5中提到过的调和（Coordination ），Dynamo 有一个请求调和组件（request coordination component），该组件使用了状态机来处理输入的请求（uses a state machine to handle incoming requests）。客户请求是统一的通过一装载平衡器（load balancer）赋予到环中的节点。任何Dynamo 节点都可以表现为一个“就一读请求（a read request）而言的”调和器（Coordination ）。另一方面而言，写请求（Write requests）会通过一个“处在键的当前偏好列表中的”节点来调和。之所以有这种约束，那是因为以下事实之故：这些偏好节点有“生成一个新的，把该通过写操作更新的版本有理归入的，版本戳 ”的附件职责 （these preferred nodes have the added responsibility of creating a new version stamp that causally subsumes the version that has been updated by the write request.）。注意到如果Dynamo的版本图景（versioning scheme）若是建基在物理时间戳之上的话，则任意节点都可以对一写请求进行调和(any node can coordinate a write request.)。
一个对请求调和（request coordination）的代替方式就是把状态机移动到客户节点中去。在这个图景中，客户应用使用了一个库在本地执行请求调和。一客户会周期性的拣选一随机Dynamo节点，且把它的“对Dynamo成员资质信息的当前视图”作下载。使用这个信息，客户就可以决定何种节点集形成了之于任意给定键的偏好列表。如果请求通过负载平衡器（load balancer）被赋予一随机Dynamo节点的话，读请求可以在客户节点被调和，从而避免了招来的额外网络跳跃（avoiding the extra network hop）。写操作或者被转递到一个处于键的偏好列表中的节点，或者在本地被调和，如果Dynamo 在使用基于版本的时间戳的话。
这种客户驱动的调和方式（the client-driven coordination approach）的一个显著优势在于：一负载平衡器（load balancer）无需再被要求“统一分布客户负载（uniformly distribute client load）”了。公正的负载分布（Fair load distribution）由“键到存储节点的接近统一分配的方式 （the near uniform assignment of keys to the storage nodes.）” 间接的保证了（is implicitly guaranteed）。很显然，