Dynamo: Amazon’s Highly Available Key-value Store 论文阅读

发表于 2025-04-13 更新于 2025-04-17 分类于 database-system 阅读次数：本文字数： 14k 阅读时长 ≈ 51 分钟

今天来读经典。

Dynamo 是 Amazon 在 2007 年发表于 SOSP 的 K-V 存储系统。作为电商领域的巨头, Amazon 较早面临巨大业务规模带来的技术挑战。 Dynamo 的技术方案在当时的分布式系统中是非常前沿的, 其设计思想和实现细节对后来的 NoSQL 系统产生了深远的影响。

#1. 引言

Amazon 运行一个全球范围的电子商务平台, 在高峰时段为数百万客户提供服务, 使用世界各地多个数据中心的数千台服务器。在这种环境下, Amazon 对性能、可靠性和效率有着严格的要求。可靠性是最重要的要求之一, 因为即使是最细微的停机, 也会产生巨大的财务后果, 并影响客户信任。此外, 为了支持平台的持续增长, 平台需要高度的可扩展性。

在运营 Amazon 的过程中, 我们的团队学到的一个教训是, 系统的可靠性和可扩展性取决于应用程序状态的管理方式。 Amazon 使用了一个高度去中心化、松耦合的面向服务的架构(SOA)来管理数百个服务。在这种环境中, 需要一种始终可用的数据存储技术。例如, 即使发生磁盘故障、网络路由抖动或者甚至数据中心被龙卷风摧毁的灾难, 客户也应该能够查看并添加商品到他们的购物车中。因此, 负责管理购物车的服务必须确保它总是可以写入和读取数据存储, 并且其数据需要再多个数据中心之间可用。

处理由数百万个组件组成的基础设施中的故障是我们的标准操作模式；在任意给定的时刻, 总有一些服务器和网络组件处于故障状态。因此, 亚马逊的软件系统需要以一种视失败如正常情况的方式来构建, 而不影响可用性或者性能。

为了满足这些要求, Amazon 开发了一系列存储技术。其中, Amazon S3 可能是最著名的存储系统。本文介绍了 Amazon Dynamo 系统的设计和实现, 这是另一个高可用且可扩展的分布式数据存储, 用于构建 Amazon 平台。 Dynamo 用于管理具有非常高可靠性要求的服务, 并需要严格控制在可用性、一致性、成本效益和性能之间的 Tradeoff。 Amazon 的平台有很多不同的应用程序, 它们对数据存储的要求各不相同。一组选定的应用程序需要一种灵活的技术, 以便应用设计师可以根据这些权衡配置其数据存储, 以在最有效的方式下达到最高的可用性并保证性能。

Amazon 平台上有许多服务只需要对数据存储进行主键访问, 例如畅销书列表、购物车、客户偏好、会话管理、销售排名和产品目录的服务。对于很多服务来说, 使用关系数据库的常见模式效率很低, 并且限制了规模和可用性。 Dynamo 提供了一个简单的主键访问接口来满足这些应用程序的需求。

Dynamo 使用一系列众所周知的技术来实现可扩展性和可用性: 数据通过一致性哈希进行分片和复制, 一致性由对象版本控制提供支持。在更新时, 副本之间的一致性通过类似多数表决的方法和去中心化的副本同步协议得到维护。 Dynamo 采用基于 Gossip 的分布式故障检测和成员协议。 Dynamo 是完全去中心化的, 对手动运维的需求极低。存储节点可以添加或删除, 而不需要任何手动分片或再分配。

在过去一年中, Dynamo 已经是 Amazon 电商平台中多个核心服务的底层存储技术。它在繁忙的假日购物季期间能够高效应对极端峰值负载, 并且从未停机。例如, 购物车服务处理了数百万个请求, 一天内处理了超过 300 万次结账；会话管理服务处理数十万个并发的会话请求。

本文对研究社区的主要贡献是评估了如何将不同的技术组合在一起以提供一个高可用的系统。它表明, 最终一致性的存储系统可以在生产中使用。此外, 它还提供了关于如何调优这些技术以满足生产系统需求的见解。

#2. 背景

Amazon 的电商平台由数百个协同工作的服务组成, 这些服务从推荐到订单履行再到欺诈检测, 提供各种功能。每个服务都通过良好定义的 API 进行暴露, 并且可以通过网络进行访问。这些服务托管在遍布世界各地的数据中心中的数万台服务器组成的基础设施上。其中一些服务是无状态的(聚合其他服务的服务), 其他服务则是有状态的(执行持久存储上的业务逻辑)。

传统生产系统将状态存储在关系数据库中。然而, 对于许多常见的使用模式而言, 关系数据库并不理想。 大多数这些服务通过主键存储和检索数据, 并不需要 RDBMS 提供的复杂查询和管理功能。 这种额外的功能需要昂贵的硬件和高度熟练的人力来操作, 使之成为一个非常低效的解决方案。此外, 可用的复制技术有限, 并且通常选择 Consistency 而不是 Availability。尽管近年来有一些进步, 但仍然很难拓展数据库或者使用智能分片方案进行 load balancing。

本文描述了 Dynamo, 这是一种高可用的数据存储技术, 可以满足这些重要的要求。 Dynamo 具有简单的 K/V 接口, 并且具有清晰定义的同步窗口, 资源利用率高, 横向扩展简单。每个使用 Dynamo 的服务都运行自己的 Dynamo 实例。

#2.1 系统假设和需求

这类服务的存储系统有如下的需求:

查询模型: 对于唯一键标识的数据项进行简单的读和写操作。状态表示为二进制对象, 并使用唯一的键进行标识。没有跨多个项的操作, 并且不需要关系型模式。对象通常较小(< 1MB)。
ACID 特性: Amazon 的经验表明, 提供 ACID 保证的存储系统往往具有较差的可用性, 这已经被业界和学术界广泛接受。 Dynamo 的目标是那些 A>C 的应用程序。Dynamo 不提供任何隔离保证, 并且仅允许单个值更新。
效率: 系统需要在商业硬件上运行。在 Amazon 的平台上, 服务有严格的延迟要求。通常是衡量 p999 延迟。鉴于状态访问在服务操作中起着至关重要的作用, 存储系统必须能够满足这些严格的 SLA。服务必须能够配置 Dynamo 的行为, 以便始终实现其延迟和吞吐量要求。权衡性能、性价比、可用性和持久性。
其他: Dynamo 仅用于 Amazon 内部服务。其运行环境是可信的, 没有身份验证和授权相关的安全要求。 Dynamo 实例的初始设计目标是达到数百台服务器的规模。

#2.2 SLA

为了保证应用程序能够在限定时间内交付其功能, 平台中的每个依赖关系都需要提供严格的边界。客户和服务商签订一个服务级别协议(SLA), 这是一个正式协商的合同, 在该合同中, 客户和服务商同意几个系统相关特性, 其中最突出的是客户对特定 API 的预期请求速率分布以及在这些条件下预期的服务延迟。一个简单的 SLA 的例子是, 一个服务承诺能够在峰值客户端负载为 500 QPS 的情况下, 保证 99.9％的请求响应时间不超过 300 ms。

在 Amazon 的去中心化面向服务的基础设施中, SLA 起着重要的作用。例如, 对一个电商网站的页面请求通常需要渲染引擎向超过 150 个服务发送请求, 然后才能返回结果。这些服务往往有多个依赖关系, 通常是其他服务, 因此应用程序的调用图中经常超过一层。为了保证页面渲染引擎能够维持页面交付的清晰界限, 调用链中的每个服务都必须遵循其 SLA。

在行业中, 构建面向性能的 SLA 的一个常见方法是使用平均值、中位数和预期方差来描述延迟。在 Amazon 中我们发现, 如果最终目标是要建立一个让所有而不是大部分客户都有良好体验的系统, 则这些指标还不够。例如, 如果广泛使用个性化技术, 则具有较长历史记录的客户则需要更多的处理, 这会影响分布位于高侧的性能。用 Average Latency 或者 Median Latency 的 SLA 无法解决这个问题。为了解决这个问题, Amazon 的 SLA 使用p999分位数。选择 p999 而不是更高的百分位数是基于成本效益分析得出的, 要继续提高性能, 成本会显著增加。亚马逊的经验证明, 这种 SLA 方案提供了更好的使用体验。

存储系统通常在确定服务的 SLA 中起着重要的作用, 尤其是在业务逻辑相对轻量级的情况下, 许多 Amazon 的服务就是这样。在这种情况下, 状态管理就成为服务 SLA 的主要组成部分之一。 Dynamo 的主要设计考虑之一是为服务提供对其系统属性(如持久性和一致性)的控制, 并让服务自行权衡功能、性能和成本效益之间的取舍。

#2.3 设计考虑因素

商业系统中使用的数据复制算法通常执行同步的副本协调, 以提供强一致的数据访问接口。为了达到这种一致性水平, 这些算法在某些故障场景下不得不牺牲交易数据的可用性。例如, 相对于处理不确定正确的结果, 直到绝对确定它是正确的为止, 数据才可以被使用。从早期复制数据库的工作开始, 就已知当处理网络故障的可能性时, 强一致性与高数据可用性不能同时实现。因此, 此类系统和应用程序需要了解在哪些条件下可以实现哪些属性。

对于容易发生服务器和网络故障的系统, 可以通过使用乐观复制技术来提高可用性, 在此过程中允许更改在后台传播到副本, 并且容忍并发、断开连接的工作。这种方法的挑战在于它可能导致修改冲突, 必须检测并解决这些更改。这种冲突解决过程引入了两个问题: 何时解决以及谁来解决。 Dynamo 设计为最终一致性的数据存储；所有更新最终都会到达所有副本。

一个重要的设计决策是决定何时执行解决更新冲突的过程, 即是否在读取或写入时解决冲突。许多传统的数据存储在写入期间执行冲突解决, 并保持读取操作简单。在这种系统中, 在给定时间点, 如果数据存储无法访问所有(或大多数)副本, 则可能拒绝写入操作。另一方面, Dynamo 目标的设计空间为持续可写的数据存储 (即数据存储对写入具有高度可用性)。对于亚马逊的某些服务而言, 拒绝客户更新可能会导致较差的客户体验。例如, 购物车服务必须允许客户在其购物车中添加和删除商品, 即使在网络故障和服务器故障期间也是如此。这一要求迫使我们把冲突解决的复杂性推到读取过程中, 以确保写入永远不会被拒绝。
下一个设计决策是冲突解决过程由谁执行。这可以由数据存储或应用程序完成。如果由数据存储进行冲突解决, 其选择就比较有限。在这种情况下, 数据存储只能使用简单的策略来解决冲突更新, 例如“最后写入者获胜”。另一方面, 由于应用程序知道数据模式, 它可以决定最适合其客户体验的冲突解决方法。例如, 维护客户购物车的应用程序可以选择将冲突版本“合并”, 并返回一个统一的购物车。尽管具有这种灵活性, 一些应用程序开发人员可能不想编写自己的冲突解决机制, 并将其推送到数据存储中, 而数据存储则会选择简单的方法, 如“最后写入者获胜”。

设计中包含的其他关键原则是:

增量可扩展性: Dynamo 应该能够一次向外扩展一个存储主机(简称“节点”), 对系统运维和系统本身的影响最小。
对称性: Dynamo 中的每个节点都应该具有与其同级节点相同的职责集；不应该有特殊的节点或节点承担特殊角色或额外的职责。在我们的经验中, 对称性简化了系统的部署和维护过程。
去中心化: 是对称性的扩展, 设计应优先考虑分散的对等技术而不是集中控制。过去, 集中控制导致了停机, 并且目标是尽可能避免这种情况。这导致了一个更简单、更具可扩展性和可用性更强的系统。
异质性: 系统需要能够利用其运行的基础设施中的异质性。例如, 工作分配必须与单个服务器的能力成比例。这在添加具有更高容量的新节点时至关重要, 而无需一次升级所有主机。

#3. 相关工作

#3.1 P2P 系统

有几个对数据存储和分发问题进行研究的 P2P 系统。第一代 P2P 系统，如 Freenet 和 Gnutella1，主要用作文件共享系统。这些是无结构对等网络的例子，在这些网络中，对等节点之间的覆盖链接任意建立。在这些网络中，通常通过网络发送搜索查询以找到尽可能多的共享数据的对等节点。第二代 P2P 系统即广为人知的结构化对等网络。这些网络采用全局一致协议来确保任何节点都可以高效地将搜索查询路由到具有所需数据的某个对等节点。像 Pastry 和 Chord 这样的系统使用路由机制来保证可以在有限的跳数内回答查询。为了减少多跳路由引入的额外延迟，一些 P2P 系统采用了 O(1) 路由，每个对等节点都维护足够的路由信息，以便它可以在常数个跳数内将请求(访问数据项)路由到适当的对等节点。

基于这些路由覆盖层，构建了各种存储系统，例如 Oceanstore 和 PAST。 Oceanstore 提供了一个全球、事务性、持久的存储服务，支持对广泛复制数据进行序列化更新。为了允许并发更新并避免广域锁定固有的许多问题，它使用一种基于冲突解决的更新模型。冲突解决在[21]中引入以减少事务回滚的数量。 Oceanstore 通过处理一系列更新，选择它们之间的总排序，并然后按此顺序原子地应用它们。它是为一个数据在不可信基础设施上被复制的环境中设计的。相比之下，PAST 在 Pastry 之上提供了持久且不可变对象的简单抽象层。它假设应用程序可以在其上构建必要的存储语义(如可变文件)。

#3.2 分布式文件系统和数据库

为性能、可用性和持久性分配数据在文件系统和数据库系统社区中有广泛的研究。与仅支持扁平命名空间的 P2P 存储系统相比，分布式文件系统通常支持层次化的命名空间。

像 Ficus 和 Coda 这样的系统通过牺牲一致性来实现高可用性而复制文件。更新冲突通常使用专门的冲突解决程序进行管理。
Farsite 系统是一个不使用任何中央服务器(如 NFS)的分布式文件系统。Farsite 使用复制来实现高可用性和可扩展性。
Google 文件系统(GFS) 是另一个用于托管谷歌内部应用程序状态的分布式文件系统。GFS 采用简单的设计，只有一个主服务器来托管整个元数据，并将数据分成块并存储在块服务器上。
Bayou 是一个允许脱机操作且提供最终数据一致性的分布式关系型数据库系统。

在这几个系统中，Bayou、Coda 和 Ficus 允许脱机操作，并且对网络分区和故障等问题具有鲁棒性。这些系统在冲突解决程序上有所不同。 Coda 和 Ficus 执行系统级别的冲突解决，而 Bayou 则允许应用程序级别的解决。然而，它们都保证最终一致性。与这些系统类似，Dynamo 允许读写操作即使在网络分区期间继续进行，并使用不同的冲突解决机制来解决更新冲突。

类似于 FAB 这样的分布式块存储系统将大对象分成较小的块并以高可用的方式存储每个块。与其他系统相比，在这种情况下，键值存储更合适，因为：

(a) 键值存储旨在存储相对较小的对象(大小小于 1M)，
(b) 键值存储更容易根据应用进行配置。

Antiquity 是一个广域分布式的存储系统，旨在处理多个服务器故障。它使用安全日志来保存数据完整性，将每个日志复制到多台服务器以确保持久性，并使用拜占庭容错协议来确保数据的一致性。相比之下，Antiquity 不专注于数据完整性和安全性问题，并且是为可信环境构建的。

Bigtable 是一种用于管理结构化数据的分布式存储系统。它维护一个稀疏的多维排序映射，并允许应用程序通过多个属性访问其数据。与 Bigtable 相比，Dynamo 的目标是仅需要键/值访问的应用程序，并且主要关注高可用性，即使在网络分区或服务器故障的情况下也不会拒绝更新。

传统的复制关系型数据库系统专注于保证复制数据的强一致性问题。尽管强一致性为应用程序编写者提供了方便的编程模型，但这些系统在可扩展性和可用性方面受到限制。由于它们通常提供强一致性的保证，因此这些系统无法处理网络分区。

#3.3 讨论

Dynamo 与上述去中心化存储系统在目标要求方面有所不同。

Dynamo 主要针对需要持续可写的数据存储应用程序，这些应用程序不允许由于故障或并发写入而拒绝更新。这对于许多 Amazon 应用程序至关重要。
如前所述，Dynamo 是为单个管理域内的基础设施构建的，在该基础设施中所有节点都被假设为可信的。
使用 Dynamo 的应用程序不需要支持层次化的命名空间(许多文件系统的规范)或复杂的关联模式(由传统数据库支持)。
Dynamo 是为了满足对读取和写入操作至少 99.9％的要求，这些操作必须在几毫秒内完成。 为了满足这些严格的延迟要求，我们避免通过多个节点路由请求(这是几个分布式哈希表系统，例如 Chord 和 Pastry 所采用的典型设计)，这是因为多跳路由会增加响应时间的变异性，并且在更高百分位数时增加延迟。 Dynamo 可以被描述为零跳 DHT，其中每个节点在其本地维护足够的路由信息以直接将请求路由到适当的节点。

#4. 系统架构

需要在生产环境中运行的存储系统架构非常复杂。除了实际的数据持久化组件外，该系统还需要具有可扩展且稳健的负载均衡、成员和故障检测、故障恢复、复制同步、过载处理、状态转移、并发性和作业调度、请求编排、请求路由、系统监控和报警以及配置管理解决方案。描述每个解决方案的细节是不可能的，因此本文重点介绍了 Dynamo 中使用的分布式系统技术的核心：分片、复制、版本控制、成员资格、故障处理和缩放。

问题	采用的解决方案技术	优势
分片	一致性哈希	渐进可扩展性
持续可写(写高可用)	向量时钟	Version size isdecoupled fromupdate rates.
处理临时故障	Sloppy Quorum andhinted handoff	Provides highavailability anddurability guaranteewhen some of thereplicas are notavailable.
从永久故障中恢复	使用 Merkle 树的反熵	Synchronizesdivergent replicas inthe background.
成员和故障检测	基于 Gossip 的成员协议和故障检测	Preserves symmetryand avoids having acentralized registryfor storingmembership andnode livenessinformation.

#4.1 系统接口

Dynamo 通过简单的接口存储与键关联的对象；它暴露了两个操作：get()和 put()。

get(key)操作在存储系统中定位与键相关的对象副本，并返回单个对象或带有冲突版本的列表，以及上下文。
put(key，context，object)操作根据关联的键确定对象的副本应放置的位置，并将副本写入磁盘。

上下文编码的是对象的系统元数据，对调用者是透明的，并包括诸如对象版本的信息。上下文信息与对象一起存储，以便系统可以验证提供的上下文对象的有效性。

Dynamo 将由调用者提供的键和对象都视为字节的不透明数组。它对键应用 MD5 散列以生成 128 位标识符，该标识符用于确定负责服务键的存储节点。

#4.2 数据分片算法

alt text

Dynamo 的关键设计要求之一是它必须按增量方式扩展。这需要一种机制来动态地将数据分布在系统中的节点(即存储主机)上。 Dynamo 的分片方案依赖于一致性哈希来在多个存储主机之间分配负载。在一致性哈希中，哈希函数输出范围被处理为固定圆环空间或“环”(即最大哈希值会循环到最小哈希值)。每个系统中的节点都被分配一个随机值在这个空间内，代表其“位置”在环上。每个由键标识的数据项通过将数据项的键进行哈希以获得其在环上的位置，并然后顺时针沿着环找到第一个位置大于该数据项的位置的第一个节点而分配给一个节点。

因此，每个节点都负责环上其前一个节点和它之间的区域。

一致性哈希的优点是，节点的离开或到达仅影响其直接邻居，而其他节点不受影响。

基本一致性哈希算法存在一些挑战。

环上的每个节点的随机位置分配导致数据和负载分布不均匀。
基本算法对节点性能差异视而不见。

为了应对这些问题，Dynamo 使用了一种一致性哈希变体(类似于在[10, 20]中使用的那种)——虚拟节点：相对于将一个节点映射到圆圈中的单个点上，每个节点被分配到多个环上的点上。为此，Dynamo 使用了“虚拟节点”的概念。一个虚拟节点看起来像系统中的一个节点，但每个节点可以负责多个虚拟节点。简而言之，在系统中添加一个新的节点时，它会被分配到环上的多个位置(以后称为“令牌”)。 Dynamo 分区方案的微调过程将在第 6 节讨论。

使用虚拟节点具有以下优点：

如果一个节点变得不可用(由于故障或例行维护)，由该节点处理的负载将均匀地分散到剩余可用节点上。
当一个节点再次可用或系统中添加了一个新节点时，新的可用节点将从其他可用节点接收大致相同数量的负载。
节点负责的虚拟节点数量可以根据其容量来决定，以考虑物理基础设施的异构性。

#4.3 数据复制

为了实现高可用性和持久性，Dynamo 在多个主机上复制其数据。每个数据项都在 N 个主机上进行复制，其中 N 是一个实例级别的配置参数。每个键 k 都分配给一个协调器节点(如前所述)。协调器节点负责复制数据项到它应该属于的范围。除了本地存储每个范围内的键外，协调器节点还会将这些键复制到环形中的顺时针方向上的 N-1 个节点。最终系统中，每个节点对其与第 N 个前驱之间的环形区域负责。

负责存储特定键的节点列表称为偏好列表。系统被设计为每个节点都可以确定任何特定键的偏好列表。为了应对节点故障，偏好列表包含超过 N 个节点。注：在使用虚拟节点的情况下，可能第一个 N 继任者位置对于特定键由少于 N 个不同的物理节点拥有(即一个节点可能持有前 N 个位置中的多个)。为此，通过跳过环上的位置来构建偏好列表以确保列表仅包含不同的物理节点。

#4.4 数据版本控制

Dynamo 提供最终一致性，允许更新异步传播到所有副本。一个 put()调用可能在所有副本应用更新之前就返回给调用者，这可能导致后续的 get()操作可能返回一个旧的对象。如果没有失败，则有更新传播时间的上限。然而，在某些故障场景下(例如服务器停机或网络分区)，更新可能不会在一段时间内到达所有副本。

Amazon 平台中有一类应用程序可以容忍这种不一致，并且可以在这些条件下运行。例如，购物车应用程序要求“添加到购物车”的操作永远不会被遗忘或拒绝。如果最新的购物车状态不可用，并且用户对较旧版本的购物车进行了更改，则该更改仍然有意义并且应该保留。但同时它不应该取代当前不可用的购物车状态，而该状态本身可能包含应保留的变化。注：“添加到购物车”和“从购物车删除商品”操作都被翻译成 Dynamo 中的 put 请求。当客户想要将增加/删除购物车中的商品时，而且最新版本不可用，该变更会被施加到较旧版本中，并且不同的版本稍后会进行合并。

为了提供这种保证，Dynamo 将每个修改的结果视为数据的新的而且不可变的版本。它允许系统中同时存在多个对象的版本。大多数情况下，新版本会覆盖之前的版本(语法一致)，并且系统本身可以确定权威版本(语义一致)。然而，在失败和并发更新的情况下可能会发生分支版本，导致对象出现冲突版本。 在这种情况下，存储系统无法对同一对象的多个版本进行一致化处理，客户端必须执行一致化操作以将数据演进的多个分支合并回一个(语义一致)。 典型的合并操作示例是“合并”不同版本的客户购物车。使用这种一致化机制，“添加到购物车”的操作永远不会丢失。但是，被删除的商品可能会再次出现。

重要的是要理解某些故障模式可能会导致系统不仅有两份，而是多份相同的数据。在存在网络分区和节点故障的情况下进行更新可能导致对象具有不同的版本子历史记录，而该系统将来需要解决这个问题。这要求我们设计应用程序来明确承认同一数据的多个版本的可能性(以避免丢失任何更新)。

Dynamo 使用向量时钟来捕获同一对象的不同版本之间的因果关系。一个向量时钟实际上是一个(节点，计数器)对的列表。每个对象的所有版本都与一个向量时钟相关联。通过检查它们的向量时钟，可以确定两个对象的版本是否在并行分支上或具有因果顺序。如果第一个对象的时钟上的计数器小于等于第二个时钟中的所有节点，则第一个是第二个的祖先，并且可以被遗忘。否则，这两个更改被认为是冲突并且需要进行协调。

在 Dynamo 中，当客户端希望更新对象时，它必须指定正在更新哪个版本。这是通过传递先前读取操作获得的上下文来完成的，该上下文中包含向量时钟信息。处理读请求时，如果 Dynamo 访问了多个无法语法上协调的分支，它将返回所有叶子对象，并在上下文中包含相应的版本信息。使用此上下文进行更新被认为是已协调了不同的版本，并且分支会合并为一个新版本。

alt text

为了说明向量时钟的使用，让我们考虑上图所示的例子。客户端写入新对象。处理此键的节点(假设是 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(上下文将反映这两个值都是通过读取找到的)。读取的上下文是 D3 和 D4 时钟的摘要，即[(Sx, 2)，(Sy, 1)，(Sz, 1)]。如果客户端执行协调并节点 Sx 协调写入，则 Sx 会更新其时钟中的序列号。新数据 D5 将具有以下时钟：[(Sx,3)，(Sy, 1)，(Sz, 1)]。

向量时钟的一个可能的问题是，如果许多服务器协调对同一个对象的写入，则向量时钟的大小可能会增长。在实践中，这不太可能，因为写操作通常由偏好列表中前 N 个节点中的一个处理。在网络分区或多个服务器故障的情况下，写请求可能会由不在偏好列表中前 N 个节点的节点处理，导致矢量时钟的大小增长。在这种情况下，限制矢量时钟的大小是可取的。为此，Dynamo 采用了以下计时器截断方案：与每个(node，counter)对一起，Dynamo 存储一个时间戳，指示节点最后一次更新数据项的时间。当矢量时钟中的(node，counter)对的数量达到阈值(例如 10)时，最旧的一对将从时钟中删除。显然，这种截断方案会导致合并过程中的效率低下，因为后代关系无法准确推导出来。然而，在生产环境中尚未出现这个问题，因此这个问题还没有得到彻底调查。

#4.5 执行 get() 和 put()操作

Dynamo 中的任何存储节点都可接收客户端的 get 和 put 操作。在本节中，为了简单起见，我们描述了这些操作如何在无故障环境中执行，并且在下一节中我们将描述在发生故障期间读写操作是如何执行的。

两种操作(获取和放置)都是通过使用 Amazon 的基础设施特定请求处理框架通过 HTTP 进行调用。客户端可以使用的两个策略是：

将其请求路由到一个通用 Proxy，该 Proxy 将根据负载信息选择节点
- 👍 客户端不需要在应用程序中链接任何与 Dynamo 相关的代码
使用分区感知客户端库直接将请求路由到适当的协调节点。
- 👍 可以实现更低的延迟，因为它跳过了可能的转发步骤

处理读写操作的节点被称为协调节点。通常，这是偏好列表中前 N 个节点中的第一个。如果请求通过 Proxy 接收，则访问密钥的请求可能会路由到环形结构中的任何随机节点。在这种情况下，如果请求的密钥的偏好列表中没有该节点，则接收到请求的节点不会协调它。相反，该节点将请求转发给偏好列表中前 N 个节点中的第一个。

读写操作涉及首选列表中的前 N 个健康节点，跳过那些已下线或不可访问的节点。当所有节点都处于健康状态时，会访问一个键的首选列表中排名最高的 N 个节点。在出现节点故障或网络分区的情况下，会访问首选列表中排名较低的节点。

为了保持其副本的一致性，Dynamo 使用类似于在多数系统中使用的同步协议。该协议有两个关键可配置值：R 和 W。

R 是必须参与成功读取操作的节点的最小数量
W 是必须参与成功写入操作的节点的最小数量

将 R 和 W 设置为 R + W > N 会生成一个类似多数系统的系统。在这个模型中，get(或 put)操作的延迟由 R(或 W)中的最慢副本决定。因此，通常配置时会选择 R + W < N，以提供更好的延迟。

在收到对键的 put()请求时，协调器生成新版本的向量钟，并将新版本本地写入。然后，协调器发送新版本(包括新向量时钟)发送到 N 个最高排名的可访问节点。如果至少有 W-1 个节点响应，则写入操作被认为是成功的。

同样，对于一个 get()请求，协调器从首选列表中该键的 N 个最高排名可访问节点中请求该键的所有现有版本的数据，并且在等待 R 响应后返回结果给客户端。如果协调器最终收集了多个数据版本，则它会返回所有认为与当前版本无关的版本。然后将这些不同版本进行合并，并将合并后的版本写回。

#4.6 处理失效: 提示式移交

如果 Dynamo 使用传统的多数派方法，那么在服务器故障和网络分区期间将不可用，并且即使在最简单的故障条件下也会降低持久性。为了纠正这一点，它不强制执行严格的多数派成员资格，而是使用“松散的多数派”；所有读写操作都在首选列表中的前 N 个健康节点上进行，这些节点可能不是一致哈希环中遇到的第一个 N 个节点。

考虑图 2 中 N = 3 的 Dynamo 配置示例。在此示例中，如果在写操作期间节点 A 暂时不可用或无法访问，则原本在 A 上的数据的副本将被发送到节点 D。这是为了保持所需的可用性和持久性保证而进行的操作。发送给 D 的副本将在其元数据中包含一个提示，建议哪个节点是该副本的预期接收者(在这种情况下为 A)。接收到暗示副本的节点将将其保存在一个单独的地方，该地方定期扫描。检测到 A 已恢复后，D 会将尝试向 A 交付副本。一旦传输成功，D 可以从其本地存储中删除对象，而不必减少系统中的总副本数量。

使用提示式移交，Dynamo 确保读写操作不会因临时节点或网络故障而失败。需要最高可用性的应用程序可以将 W 设置为 1，这保证只要系统中的单个节点持久地将密钥写入其本地存储器，则写请求就会被接受。因此，只有所有节点都不可用，才会拒绝写入请求。然而，在实践中，大多数亚马逊服务在生产环境中设置了更高的 W 以满足所需的耐用性水平。有关配置 N、R 和 W 的更详细讨论请参见第 6 节。

高可用存储系统必须能够处理整个数据中心的故障。数据中心故障可能由于停电、冷却失败、网络故障或自然灾害引起。 Dynamo 通过配置，使得每个对象在多个数据中心进行复制。本质上，键的首选列表被构造以使存储节点分布在多个数据中心中。这些数据中心通过高速网络连接起来。这种跨多个数据中心复制的方法允许我们处理整个数据中心的故障而不会出现数据中断。

#4.7 处理永久性失效: 副本同步

提示式移交在系统成员流失率低且节点故障是暂时的情况下效果最好。有些场景下，提示副本可能在移交给原始节点之前也不可用。为了处理持久性方面的其他威胁，Dynamo 实现了一个反熵(复制同步)协议来保持复制节点同步。

为了更快地检测副本之间的不一致性和最小化传输的数据量，Dynamo 使用 Merkle 树。 Merkle 树是一种哈希树，其中叶子是单个键值的哈希。树中更高层次的父节点是其子节点的哈希。 Merkle 树的主要优点在于每个分支可以独立检查而无需节点下载整个树或整个数据集。此外，Merkle 树有助于减少在检查副本之间的一致性时需要传输的数据量。例如，如果两个树根的哈希值相等，则树中的叶节点的值也相等，并且节点不需要同步。否则，这意味着某些副本的值不同。在这种情况下，节点可能交换孩子的哈希值并继续进行直到达到树的叶子，在这一点上主机可以识别“脱节”的密钥。 Merkle 树减少了用于同步所需传输的数据量，并降低了反熵过程中读取磁盘的数量。

Dynamo 使用 Merkle 树来反熵，如下所示：每个节点维护一个单独的 Merkle 树，以覆盖它所托管的关键范围(虚拟节点所涵盖的一组密钥)。这允许节点比较它们是否在关键范围内具有最新的密钥。在这个方案中，两个节点交换它们共同拥有的密钥范围对应的 Merkle 树根。随后，通过上面描述的树遍历方案，节点确定是否有任何差异并执行适当的同步操作。这种方案的一个缺点是，在节点加入或离开系统时，许多关键范围会发生变化，因此需要重新计算树。然而，这个问题可以通过第 6.2 节中描述的细化分区方案得到解决。

#4.8 成员和故障检测

#4.8.1 环形成员检测

在亚马逊的环境中，由于故障和维护任务而导致的节点中断通常是短暂的，但也可能会持续更长的时间。节点中断很少意味着永久离开，因此不应该导致分区分配重新平衡或无法访问副本的修复。 同样，人为错误可能导致无意中启动新的 Dynamo 节点。因此，使用明确机制来增加和删除 Dynamo 环中的节点是合适的。管理员通过命令行工具或浏览器连接到一个 Dynamo 节点，并向该节点发出加入或离开环的成员资格更改指令。请求服务的节点将成员资格更改及其发布时间写入持久存储。成员资格更改形成历史记录，因为节点可以多次被添加和删除。基于 Gossip 协议传播成员资格更改并保持最终一致的成员资格视图。每个节点每秒都会随机选择一个 Peer 进行联系，两个节点高效地协调它们的持久成员资格更改历史记录。

当 Dynamo 节点首次启动时，它先选择其令牌集(一致哈希空间中的虚拟节点)并映射节点到各自的令牌集中。该映射会持久化在磁盘上，最初仅包含本地节点和令牌集。在相同通信交换中，不同 Dynamo 节点存储的映射会进行合并以解决成员变更历史记录。因此，分片和放置信息也会通过基于 Gossip 协议传播，并且每个存储节点都了解其 Peer 处理的令牌范围。这使每个节点能够直接将键的读写操作转发到正确的节点集合。

#4.8.2 外部发现

上述机制可能会暂时导致逻辑上分区的 Dynamo 环。例如，管理员可以联系节点 A 以将 A 加入到环中，然后联系节点 B 以将 B 加入到环中。在这种情况下，节点 A 和 B 都会认为自己是环的一部分，但它们都不会立即意识到对方的存在。为了防止逻辑分区，一些 Dynamo 节点扮演种子的角色。种子是通过外部机制发现的节点，并且所有节点都知道这些种子。因为最终所有节点都将与种子进行成员身份匹配，因此逻辑分区的可能性极低。种子可以从静态配置或配置服务中获取。通常，种子节点是 Dynamo 环中的完全正常工作的节点。

#4.8.3 失败检测

在 Dynamo 中失败检测用于避免在 get()、put()、分片迁移和提示副本传输期间尝试与不可达的对等方进行通信。为了防止通信失败，使用纯粹本地的故障检测概念完全足够：节点 A 可能认为节点 B 已失败，即使 B 对节点 C 的消息响应。当 Dynamo 环中有稳定的客户端请求速率时，在节点 B 失败且不响应消息的情况下，节点 A 很快就会发现节点 B 是无响应的；然后节点 A 使用备用节点来服务映射到 B 的分片的请求；定期重试 B 以检查其恢复情况。在没有客户端请求驱动两个节点之间的流量的情况下，任何节点都不需要知道另一个是否可达和响应。

去中心化故障检测协议使用一种简单的 Gossip 式协议，使系统中的每个节点都能了解到其他节点的到达(或离开)。有关去中心化故障检测器及其影响准确性的参数的详细信息，请参阅[8]。 Dynamo 的早期设计使用去中心化故障检测器来维护全局一致的失败状态视图。后来确定了明确的节点加入和离开方法消除了对全局失败状态视图的需求。这是因为通过明确的节点加入和离开方法通知节点永久性节点添加和删除，并且当节点无法与其他节点通信时(在转发请求时)，由单个节点检测临时节点故障。

#4.9 添加/删除存储节点

当一个新的节点(例如 X)被添加到系统中时，它会分配一些随机散落在环上的令牌。对于分配给节点 X 的每个键范围，可能有多个节点(小于或等于 N)目前负责处理其令牌范围内的键。由于将键范围分配给 X，一些现有节点不再需要某些键，并且这些节点将这些键转移到 X。让我们考虑一个简单的自举场景，其中节点 X 添加到图 2 中所示的环之间 A 和 B。当 X 添加到系统时，它负责存储键在范围(F,G], (G,A] 和 (A,X] 。因此，节点 B、C 和 D 不再需要存储这些相应的范围中的键。因此，节点 B、C 和 D 将提供并确认从 X 转移适当的键集。当一个节点从系统中删除时，键的重新分配发生在相反的过程。

操作经验表明，这种方法将密钥分发的负载均匀地分布在存储节点上，这对于满足延迟要求和确保快速启动至关重要。最后，在源和目的地之间添加确认轮次，以确保目的地节点不会接收给定密钥范围内的任何重复传输。

#5. 实现

在 Dynamo 中，每个存储节点都有三个主要的软件组件：请求协调、成员资格和故障检测以及本地持久性引擎。所有这些组件都是用 Java 实现的。

Dynamo 的本地持久性组件允许使用不同的存储引擎。正在使用的引擎包括：

Berkeley 数据库（BDB）事务数据存储
BDB Java 版
MySQL
具有持久存储后端的内存缓冲区

设计可插拔持久性组件的主要原因是选择最适合应用程序访问模式的存储引擎。例如，BDB 可以处理通常在数十 KB 范围内的对象，而 MySQL 则可以处理更大的对象。应用程序根据其对象大小分布选择 Dynamo 的本地持久性引擎。大多数 Dynamo 生产实例都使用 BDB 事务数据存储。

请求协调组件建立在事件驱动的消息基础结构之上，该消息处理管道被划分为多个阶段类似于 SEDA 架构。所有通信都使用 Java NIO 通道实现。协调器通过从一个或多个节点（读取情况下）收集数据或存储数据在一个或多个节点上（写入情况下），代表客户执行读取和写入请求。每个客户端请求都会导致接收客户端请求的节点创建状态机。状态机包含所有用于识别负责键的节点、发送请求、等待响应、可能进行重试、处理答复并包装响应给客户的逻辑。每个状态机实例仅处理一个客户端请求。例如，读操作实现以下状态机：

向节点发送读取请求
等待所需响应的最小数量
如果在指定的时间范围内收到太少的回复，则失败请求
否则收集所有数据版本，并确定要返回的版本
如果启用版本控制，则执行语法一致性和生成包含所有剩余版本的不可见写上下文。

为了简洁起见，错误处理和重试状态被省略了。

在读响应已返回给调用者后，状态机等待一小段时间以接收任何未响应的响应。如果在任何响应中返回了过期版本，协调器会更新这些节点的最新版本。此过程称为读取修复，因为它会在机会时间修复错过最近更新的副本，并且可以减轻反熵协议不必执行该操作的压力。

如前所述，写请求由首选列表中前 N 个节点中的一个协调。尽管总是希望将第一个节点作为前 N 个节点来协调写入操作从而在单个位置上序列化所有写入操作是理想的，但这种方法导致负载不均匀分布，进而违反了服务水平协议（SLA）。这是因为请求负载不是在整个对象之间均匀分布的。为了应对这种情况，在首选列表中的任何前 N 个节点都可以协调写入操作。特别是，由于每个写通常跟随读取操作，因此选择写入协调器为回复最快到先前读取操作的节点，该读取操作存储在请求上下文中。这种优化使我们能够选择读取了先前读取操作的数据所在的节点，从而增加了获得“读取你的写入”的一致性机会。它还减少了请求处理性能的变异性，这提高了 p999 的性能。

Dynamo 被几个具有不同配置的服务使用。这些实例通过版本对齐逻辑和读写多数特征而有所不同。以下是在 Dynamo 中使用的主模式：

业务逻辑特定的对齐：这是 Dynamo 的一个流行用例。每个数据对象在多个节点上进行复制。如果版本不同，客户端应用程序会执行自己的对齐逻辑。前面讨论过的购物车服务就是一个此类别中的典型例子。其业务逻辑通过合并客户购物车的不同版本来对齐对象。
基于时间戳的对齐：此案例与前面的一个案例不同之处仅在于对齐机制。在存在分歧版本的情况下，Dynamo 会执行简单的基于时间戳的“最后写入胜出”逻辑；即选择物理时间戳值最大的对象作为正确版本。维护客户会话信息的服务是一个使用这种模式的好例子。
高性能读取引擎：虽然 Dynamo 是为“始终可写入”的数据存储而构建的，但一些服务正在调整其共识特性并将其用作高性能读取引擎。通常，这些服务具有较高的读请求率和少量更新。在这种配置中，通常 R 设置为 1，W 设置为 N。对于这些服务，Dynamo 提供将数据在多个节点之间分区和复制的能力，从而实现增量扩展。其中一些实例充当了存储在更重负载后备存储中的数据的权威持久缓存。维护产品目录和服务项目的服务属于此类别。

Dynamo 的主要优势在于，其客户端应用程序可以调整 N、R 和 W 的值以达到所需的性能、可用性和持久性水平。例如，N 的值决定了每个对象的持久性。Dynamo 用户通常使用的 N 值为 3。

W 和 R 的值会影响对象可用性、耐用性和一致性。例如，如果将 W 设置为 1，则只要系统中至少有一个节点可以成功处理写入请求，系统就不会拒绝任何写入请求。然而，低值的 W 和 R 可能会增加不一致的风险，因为即使大多数副本未处理写入请求，也会认为写入请求成功并将其返回给客户端。这也引入了一个持久性的脆弱窗口，当写入请求成功返回给客户端时，尽管它仅在少数节点上被持久化。