[SOSP'07] Dynamo: Amazon’s Highly Available Key-value Store 论文阅读

发表于 2025-04-13 分类于 system ， database-system 阅读次数：本文字数： 20k 阅读时长 ≈ 1:13

发表于 SOSP 2007 2017 年获得 SOSP Hall of Fame Award NoSQL 领域的里程碑之作, 启发了后续众多系统的设计催生了 AWS DynamoDB 服务

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

#1. 引言

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

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

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

The major difference between a thing that might go wrong and a thing that cannot possibly go wrong is that when a thing that cannot possibly go wrong goes wrong it usually turns out to be impossible to get at or repair.
可能出错的事物与不可能出错的事物之间的主要区别是, 当一个不可能出错的事物出错时, 通常不可能修复.
Douglas Adams, Mostly Harmless（1992）

为了满足这些要求, Amazon 开发了一系列存储技术. 其中最著名的可能是 Amazon S3, AWS 对外也提供该服务. 本文介绍了 Dynamo – 另一个高可用且可扩展的分布式数据存储的设计和实现, 用于构建 Amazon 平台. Dynamo 用于管理对可靠性(reliability)要求非常高且需要严格控制可用性(availability)、一致性(consistency)、成本效益(cost-effectiveness)和性能之间权衡的服务状态. Amazon 平台上有很多不同的应用, 它们对存储的要求各不相同. 一组选定的应用需要一种足够灵活的存储技术, 以便应用开发人员可以根据这些权衡, 适当地配置他们的数据存储方式, 以最经济的方式实现高可用和有保证的性能.

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

Dynamo 综合运用了一系列众所周知的技术来实现可扩展性和可用性:

数据通过一致性哈希进行分片和复制, 通过对象版本控制来保持一致性.
更新过程中, 副本之间的一致性通过类似 quorum 的方式和去中心化的副本同步协议来维护.
Dynamo 采用基于 Gossip 的分布式故障检测和成员协议.

Dynamo 是完全去中心化的, 对手动运维的需求极低. 存储节点可以在无需任何手动分片或再分配的情况下添加或删除.

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

本文对学术界的主要贡献在于：评估了如何将不同的技术组合在一起以提供一个高可用的系统. 它证明了最终一致性的存储系统可以用于生产系统, 服务严格的应用程序. 此外, 它还提供了深入的insight, 关于如何调优这些技术以满足生产系统的严格性能需求.

#2. 背景

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

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

本文介绍了 Dynamo, 这是一种高可用的数据存储技术, 可以满足这些重要业务的要求. Dynamo 具有简单的 K/V 接口, 并且具有清晰定义的一致性窗口, 高资源利用率, 简单的横向扩展方案. 每个使用 Dynamo 的服务都运行自己的 Dynamo 实例. (即服务化部署)

#2.1 系统假设和需求

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

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

#2.2 SLA

为了确保应用能够在限定时间内完成其功能, 平台中的每个依赖关系都需要提供严格的时间边界. 客户端和服务端之间会约定一个SLA, 对几个系统相关指标达成共识, 其中最突出的是客户对特定 API 的预期请求速率分布以及在这些条件下预期的服务延迟. 一个简单的 SLA 的示例是, 一个服务承诺: 能够在峰值客户端负载为 500 RPS 的情况下, 保证 99.9% 的请求响应时间不超过 300 ms.

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

图 1 展示了 Amazon 平台架构的抽象视图, 其中动态 Web 内容由页面渲染组件生成, 而这些组件又会查询许多其他服务. 服务可以使用不同的数据存储来管理其状态, 并且这些数据存储只能在其服务边界内访问. 一些服务充当聚合器, 通过使用多个其他服务来生成复合响应. 通常, 聚合器服务是无状态的, 但它们会使用大量缓存.

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

本文多次提及 99.9 百分位分布, 这体现了亚马逊工程师从客户体验角度对性能的不懈追求. 许多论文报告的是平均值, 因此本文也仅将其纳入, 以便进行比较. 然而, 亚马逊的工程和优化工作并非专注于平均值. 一些技术, 例如负载均衡的写入 Coordinator 选择, 纯粹是为了将性能控制在 99.9 百分位.

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

#2.3 设计考虑因素

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

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

第一个重要的设计决策是决定何时解决冲突, 即是否要在读或写操作时解决冲突. 许多传统数据存储选择在写入期间执行冲突解决, 并保持读取操作简单, 因此在这种系统中, 如果写入操作在给定时间内无法到达多数副本, 则会被拒绝.

即, 当发生网络分区时放弃了写可用性

另一方面, Dynamo 的设计目标为持续可写的数据存储 (即数据存储对写入具有高度可用性). 对于亚马逊的某些服务而言, 拒绝客户更新可能会导致较差的客户体验. 例如像购物车服务必须允许客户在其购物车中添加和删除商品, 即使在网络故障和服务器故障期间也是如此. 这一要求迫使我们把冲突解决的复杂性推到读取过程中, 以确保写入永远不会被拒绝.

下一个设计决策是谁来解决冲突. 这可以由数据存储或应用完成. 如果由数据存储进行冲突解决, 其选择就比较有限. 在这种情况下, 数据存储只能使用简单的策略来解决冲突更新, 例如最后写入者获胜 (LWW). 另一方面, 由于应用程序感知数据模式, 它可以决定最合适的冲突解决方法. 例如, 维护客户购物车的应用可以选择将冲突版本合并, 并返回一个统一的购物车. 尽管具有这种灵活性, 一些应用开发人员可能不想编写自己的冲突解决机制, 并将其推送到数据存储中, 而数据存储则会选择简单的方法, 如 LWW.

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

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

#3. 相关工作

#3.1 P2P 系统

有几种对等 (P2P) 系统研究过数据存储和分发问题.

第一代 P2P 系统, 如 Freenet 和 Gnutella, 主要用作文件共享系统. 这些是非结构化 P2P 网络的例子, 在这些网络中, 对等节点之间的覆盖链接任意建立. 在这些网络中, 通常通过网络发送搜索查询以找到尽可能多的共享数据的对等节点.

第二代 P2P 系统即广为人知的结构化P2P网络. 这些网络采用全局一致的协议来确保任何节点都可以高效地将搜索查询路由到具有所需数据的某个对等节点. 像 Pastry 和 Chord 这样的系统使用路由机制来保证可以在有限的跳数内回答查询. 为了减少多跳路由引入的额外延迟, 一些 P2P 系统采用了 O(1) 路由, 每个对等节点都维护足够的路由信息, 以便它可以在常数个跳数内将请求(数据项访问)路由到适当的对等节点.

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

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

文件系统和数据库系统社区已广泛研究如何通过分散数据来提高性能、可用性和持久性. 与仅支持扁平命名空间的 P2P 存储系统相比, 分布式文件系统通常支持分层命名空间.

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

在这几个系统中, Bayou、Coda 和 Ficus 允许脱机操作, 并且对网络分区和故障等问题具有鲁棒性. 这些系统的冲突解决程序各不相同:

Coda 和 Ficus 执行系统级别的冲突解决
Bayou 则允许应用级别的解决

然而, 它们都保证了最终一致性. 与这些系统类似, Dynamo 即使在网络分区期间也允许读写操作继续进行, 并使用不同的冲突解决机制来解决更新后的冲突.

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

键值存储旨在存储相对较小的对象 (<1M),
键值存储更容易根据应用进行配置.

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

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

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

#3.3 讨论

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

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

#4. 系统架构

需要在生产环境中运行的存储系统架构非常复杂. 除了实际的数据持久化组件外, 该系统还需要具有可扩展且稳健的解决方案, 解决这些问题:

负载均衡
成员发现和故障检测
故障恢复
复制同步
过载处理
状态转移
并发性和作业调度
请求编组
请求路由
系统监控和报警
配置管理

本文重点介绍了 Dynamo 中使用的分布式系统技术的核心: 分片、复制、版本控制、成员资格、故障处理和扩缩容.

问题	采用的解决方案技术	优势	Apache Cassandra	Riak
数据分片 (partition)	一致性哈希	增量式可扩展性	√	√
持续可写 (写高可用)	向量时钟	版本大小与更新速率解耦	LWW	√
临时故障处理	宽松 Quorum 和提示 handoff	当某些副本不可用时提供高可用性和持久性保证	√	√
从永久故障中恢复	使用 Merkle 树进行反熵	在后台同步分歧的副本	√	√
成员发现和故障检测	基于 Gossip 的成员协议和故障检测	保持对称性并避免集中式注册中心来存储成员和节点存活信息	√	√

#4.1 接口

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

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

context 对对象的系统元数据进行编码, 该元数据对调用者是不透明的, 并包括诸如对象版本的信息. context 信息与对象一起存储, 以便系统可以验证提供的 context 对象的有效性.

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

#4.2 数据分片

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

传统的做法：使用 mod 函数将数据项映射到节点上.
这种方法的问题在于, 当节点数量发生变化时, 大量数据项需要重新映射到不同的节点上. 这会导致大量的数据迁移, 并且在节点频繁变化的环境中效率低下.

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

环上的每个节点的随机位置分配导致数据和负载分布不均匀.
基本算法忽略了节点的异质性.

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

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

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

一致性哈希的计算开销: 一次哈希计算和一次环上查找 (使用跳表或类似的数据结构实现), O(log N).

#4.3 数据复制

为了实现高可用性和持久性, Dynamo 在多个主机上复制其数据. 每个数据项都会存储在 N 个不同的主机上, N 是一个实例级别的配置参数.

每个键都对应一个 Coordinator 节点. Coordinator 节点负责复制数据项到它应该属于的范围. 除了本地存储每个范围内的键外, Coordinator 节点还会将这些键复制到环形中的顺时针方向上的 N-1 个节点. 最终系统中, 每个节点对其与第 N 个前驱之间的环形区域负责. 例如在图 2 中, 位于 (A, B] 之间的键 k 将被存储在节点 B、C 和 D 上. 节点 D 将存储属于范围 (A, B]、(B, C] 和 (C, D] 内的键.

Coordinator 节点: 哈希环上顺时针方向上第一个位置大于 Key 的节点.

负责存储特定 Key 的节点列表称为该 Key 的 偏好列表 (Preference list). 系统被设计为每个节点都可以确定任何特定 Key 的 Preference list. 为了应对节点故障, Preference list 包含超过 N 个节点. 注: 在使用了虚拟节点的情况下, Preference list 可能包含重复的物理节点. 在这种情况下, 会跳过环上的位置以确保列表仅包含不同的物理节点.

Preference list: 哈希环上后继 >N 个不同的物理节点.

#4.4 多版本控制

Dynamo 提供最终一致性, 更新操作会异步地传播到所有副本. 一个 put 调用可能在所有副本应用更新之前就返回给调用者, 这可能导致后续的 get 操作可能返回一个旧的对象. 如果没有发生故障, 更新在有限时间内即可完成. 然而, 在某些故障场景下(例如服务器停机或网络分区), 更新可能需要较长时间才能到达所有副本.

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

为了提供这种保证, Dynamo 将每个修改的结果视为一个新的、不可变的数据版本. 它允许系统中同时存在一个对象的多个版本. 大多数情况下, 新版本会覆盖之前的版本(语法调和 syntactic reconciliation), 并且系统本身可以确定权威版本(语义调和 semantic reconciliation). 然而, 在存在故障和并发更新的情况下可能会发生版本分叉, 从而导致对象出现冲突版本.

参考共享文档编辑系统中的冲突情况.

在这种情况下, 存储系统无法对同一对象的多个版本进行一致化处理, 客户端必须执行一致化操作以将数据演进的多个分叉合并回一个 (语义调和 semantic reconciliation). 典型的合并操作示例是“合并”不同版本的客户购物车. 使用这种调和机制, “添加到购物车”的操作永远不会丢失. 但是, 被删除的商品可能会重新出现.

对于购物车场景, 这通常是可以接受的, 因为客户可以在结账时删除不需要的商品. 也符合电商网站的商业目标, 即尽可能多地销售商品.

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

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

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

alt text

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

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

#4.5 执行 `get` 和 `put` 操作 (无故障)

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

get 和 put 都是通过使用 Amazon 的 HTTP RPC 框架进行调用. 客户端可以使用两种策略来访问 Dynamo:

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

处理读写操作的节点被称为 Coordinator, 通常是 Preference list 中的第一个成员. 在 Proxy 模式下, Proxy 会将请求随机转发给集群中的任意一个节点, 该节点再将请求转发给真正的 Coordinator 节点.

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

为了保持其副本的一致性, Dynamo 使用类似于 Quorum 系统的一致性协议. 该协议有两个关键可配置值: R 和 W.

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

将 R 和 W 设置为 R + W > N 就得到一个类似 Quorum 的系统. 在这个模型中, get/put 操作的延迟将由 R/W 中的最慢副本决定. 因此, 通常会选择小于 N 的 R + W, 以提供更好的延迟.

在收到对 Key 的 put 请求时, Coordinator 生成新版本的向量时钟, 并将新版本写入本地. 然后, Coordinator 将新版本(包括新向量时钟)发送到排名最高的 N 个可达节点. 如果至少有 W-1 个节点响应, 则这次写入操作被认为是成功的.

同样, 对于一个 get 请求, Coordinator 从 Preference list 中排名最高的 N 个可达节点请求该 Key 的所有现有版本的数据, 并且在等待 R 个响应后返回结果给客户端. 如果 Coordinator 最终收集了多个数据版本, 则它会返回所有认为与当前版本无关的版本. 然后将这些不同版本进行调和, 并将调和后的版本写回.

#4.6 处理临时故障: 提示式移交

如果 Dynamo 使用传统的 Quorum 方法, 那么在服务器故障和网络分区期间将完全不可用, 并且即使在最简单的故障条件下也会降低持久性. 为了解决这个问题, 它不强制执行严格的 Quorum 检查, 而是使用一种宽松的 Quorum: 所有读写操作都在 Preference list 中的前 N 个健康节点上进行, 这些节点不一定是哈希环中顺时针的前 N 个节点.

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

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

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

#4.7 处理永久性故障: 副本同步

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

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

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

#4.8 成员和故障检测

#4.8.1 环形成员检测

在 Amazon 的环境中, 由于故障和维护任务而导致的节点掉线通常是短暂的, 但也可能会持续更长的时间. 节点掉线很少意味着永久离开, 因此不应该分区分配重新平衡或无法访问副本的修复. 同样, 人为错误可能导致无意中启动新的 Dynamo 节点. 因此, 使用明确机制来增加和删除 Dynamo 环中的节点是合适的.

管理员通过命令行工具或浏览器连接到 Dynamo 节点, 并向该节点发出成员资格更改指令. 请求服务的节点将成员资格更改及其发布时间写入持久存储. 因为节点可以多次被添加和删除, 成员资格更改形成历史记录. 基于 Gossip 的协议会传播成员资格更改并保持最终一致的成员资格视图. 每个节点每秒会随机选择一个 Peer 进行联系, 两个节点高效地调和它们的持久成员资格更改历史记录.

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

#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. 让我们考虑一个简单的 Bootstrap 场景, 其中节点 X 添加到图 2 中所示的环之间 A 和 B. 当 X 添加到系统时, 它负责存储范围 (F, G], (G, A] 和 (A, X] 的键. 因此, 节点 B、C 和 D 不再需要存储这些相应的范围中的键. 因此, 节点 B、C 和 D 将向 X 提供相应的键值, 并在 X 确认后转移相应的键值集. 当一个节点从系统中移除时, 键值的重新分配过程将以相反的过程进行.

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

#5. 实现

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

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

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

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

请求协调组件构建于事件驱动的消息传递基础之上, 该消息处理管道被划分为多个阶段类似于 SEDA 架构. 所有通信都使用 Java NIO 通道实现. Coordinator 通过从一个或多个节点 (读取情况下) 收集数据, 或存储数据在一个或多个节点上 (写入情况下), 代表客户执行读取和写入请求.

每个客户端请求都会导致接收客户端请求的节点创建状态机. 状态机包含所有用于识别负责 Key 的节点、发送请求、等待响应、可能进行重试、处理答复并包装响应给客户的逻辑. 每个状态机实例仅处理一个客户端请求. 例如, 读操作实现以下状态机:

向节点发送读取请求
等待所需响应的最小数量 R
如果在给定时间内收到太少的回复, 则失败请求
否则收集所有数据版本, 并确定要返回的版本
如果启用版本控制, 则执行语法调和, 并生成包含所有剩余版本的不可见写 context .

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

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

如前所述, 写请求由 Preference list 中前 N 个节点中的一个协调. 尽管第一个节点协调写入操作从而在单个位置上串行所有写入操作是理想的, 但这种方法导致负载不均匀分布, 进而违反了 SLA. 这是因为请求负载不是在整个对象之间均匀分布的. 为了应对这种情况, 在 Preference list 的前 N 个节点中任何一个都可以协调写入操作. 特别是, 由于每个写通常跟随读取操作, 因此选择写入 Coordinator 为回复最快到先前读取操作的节点, 该读取操作存储在请求 context 中. 这种优化使我们能够选择读取了先前读取操作的数据所在的节点, 从而增加了获得 “read-your-writes” 的一致性机会. 它还减少了请求处理性能的变异性, 这提高了 p999 的性能.

#6. 经验和教训

Dynamo 被几个具有不同配置的服务使用. 这些实例通过版本对齐逻辑和读写 Quorum 特征各不相同. 以下是在 Dynamo 中使用的主模式:

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

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

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

传统观点认为, 持久性和可用性密不可分. 然而, 这在这里并不一定成立. 例如, 可以通过增加 W 来减少持久性的脆弱性窗口. 这可能会增加拒绝请求的概率（从而降低可用性）, 因为需要更多存储主机保持活动状态才能处理写入请求.

Dynamo 的多个实例使用的常见 (N,R,W) 配置为 (3,2,2). 选择这些值是为了满足必要的性能、持久性、一致性和可用性 SLA 要求.

本节中介绍的所有测量均在 (3,2,2) 配置的实时系统上进行, 该系统运行着数百个具有相同硬件配置的节点. 如前所述, 每个 Dynamo 实例都包含位于多个数据中心的节点. 这些数据中心通常通过高速网络链路连接. 回想一下, 为了生成成功的 get（或 put）响应, R（或 W）个节点需要响应 Coordinator. 显然, 数据中心之间的网络延迟会影响响应时间, 并且节点（及其数据中心位置）的选择应满足应用程序的目标 SLA.

#6.1 平衡性能和持久性

虽然 Dynamo 的主要设计目标是构建一个高可用的数据存储, 但性能也是亚马逊平台同样重要的考量标准. 如前所述, 为了提供一致的客户体验, 亚马逊的服务将其性能目标设定在更高的百分位（例如 99.9 或 99.99 百分位）. 对于使用 Dynamo 的服务, 一个典型的 SLA 要求是 99.9% 的读写请求在 300 毫秒内执行.

由于 Dynamo 运行在标准商用硬件组件上, 其 I/O 吞吐量远低于高端企业服务器, 因此提供持续的高性能读写操作并非易事. 读写操作涉及多个存储节点, 这使得它更具挑战性, 因为这些操作的性能受到最慢的读或写副本的限制. 图 4 显示了 Dynamo 在 30 天内读写操作的平均延迟和 99.9 百分位延迟. 从图中可以看出, 延迟呈现出明显的昼夜变化模式, 这是由于传入请求率的昼夜变化模式造成的（即白天和晚上的请求率有显著差异）. 此外, 写入延迟明显高于读取延迟, 因为写入操作总是会导致磁盘访问. 此外, 99.9 百分位延迟约为 200 毫秒, 比平均值高出一个数量级. 这是因为第 99.9 个百分位延迟受到请求负载、对象大小和局部模式的变化等多种因素的影响.

虽然这种性能水平对于许多服务来说是可以接受的, 但一些面向客户的服务需要更高的性能. 对于这些服务, Dynamo 提供了在性能和持久性之间进行权衡的能力. 在优化中, 每个存储节点在其主内存中维护一个对象缓冲区. 每个写操作都存储在缓冲区中, 并由写入线程定期写入存储. 在此方案中, 读操作首先检查请求的键是否存在于缓冲区中. 如果存在, 则从缓冲区而不是存储引擎读取对象.

这种优化使得在高峰流量期间即使对于只有一千个对象的非常小的缓冲区, 99.9 百分位延迟也降低了 5 倍（见图 5）. 此外, 如图所示, 写入缓冲可以平滑更高百分位延迟. 显然, 这种方案以持久性换取性能. 在此方案中, 服务器崩溃可能导致缓冲区中排队的写入丢失. 为了降低持久性风险, 写入操作被改进为让协调器从 N 个副本中选择一个来执行“持久写入”. 由于协调器仅等待 W 个响应, 因此写入操作的性能不受单个副本执行的持久写入操作的性能影响.

#6.2 确保均匀负载分布

Dynamo 使用一致性哈希在其副本之间划分键空间, 以确保负载均匀分布. 假设键的访问分布不是高度倾斜, 均匀的键分布可以帮助我们实现均匀的负载分配. 具体而言, Dynamo 的设计假设即使在访问分布中存在显著的倾斜, 在分布的热门端也有足够的键, 因此处理热门键的负载可以通过分区均匀地分布在各个节点上. 本节讨论 Dynamo 中出现的负载不平衡问题, 以及不同分区策略对负载分布的影响.

为了研究负载不平衡及其与请求负载的相关性, 我们测量了每个节点在 24 小时内收到的请求总数（分为 30 分钟的间隔）. 在给定的时间窗口内, 如果节点的请求负载与平均负载的偏差小于某个阈值（此处为 15%）, 则认为该节点“不平衡”. 否则, 该节点被视为“不平衡”. 图 6 显示了此时间段内“不平衡”节点的比例（以下简称“不平衡率”）. 作为参考, 还绘制了此时间段内整个系统收到的相应请求负载. 如图所示, 不平衡率随着负载的增加而降低. 例如, 在低负载期间, 不平衡率高达 20%, 而在高负载期间接近 10%. 直观地讲, 这可以解释为在高负载下, 大量常用键被访问, 并且由于键的均匀分布, 负载也均匀分布. 然而, 在低负载（负载为测量峰值负载的 1/8）期间, 访问的热门键较少, 导致负载不平衡程度更高.

本节讨论 Dynamo 的分区方案如何随着时间的推移而演变及其对负载分配的影响.

策略 1：每个节点分配 T 个随机令牌, 并按令牌值进行分区：这是生产环境中部署的初始策略（详见 4.2 节）. 在此方案中, 每个节点分配 T 个令牌（从哈希空间中均匀随机选择）. 所有节点的令牌均根据其在哈希空间中的值进行排序. 每两个连续的令牌定义一个范围. 最后一个令牌和第一个令牌构成一个范围, 该范围从哈希空间中的最高值“环绕”到最低值. 由于令牌是随机选择的, 因此范围的大小会有所不同. 随着节点加入和离开系统, 令牌集会发生变化, 范围也会随之变化. 需要注意的是, 维护每个节点成员资格所需的空间会随着系统中节点数量的增加而线性增加.

在使用此策略时, 遇到了以下问题. 首先, 当新节点加入系统时, 它需要从其他节点“窃取”其键范围. 然而, 将键范围交给新节点的节点必须扫描其本地持久化存储以检索相应的数据项集. 需要注意的是, 在生产节点上执行此类扫描操作非常棘手, 因为扫描是高度资源密集型操作, 并且需要在后台执行而不影响客户性能. 这要求我们以最低优先级运行引导任务. 然而, 这显著减慢了引导过程, 在繁忙的购物季节, 当节点每天处理数百万个请求时, 引导过程几乎需要一天才能完成. 其次, 当节点加入/离开系统时, 许多节点处理的键范围会发生变化, 需要重新计算新范围的默克尔树, 这在生产系统上执行起来并非易事. 最后, 由于键值范围的随机性, 很难对整个键值空间进行快照, 这使得归档过程变得复杂. 在该方案中, 归档整个键值空间需要我们从每个节点分别检索键值, 效率极低.

该策略的根本问题在于数据分区和数据放置方案相互交织. 例如, 在某些情况下, 为了应对不断增长的请求负载, 我们倾向于向系统添加更多节点. 然而, 在这种情况下, 添加节点不可能不影响数据分区. 理想情况下, 最好使用独立的分区和放置方案. 为此, 我们评估了以下策略：

策略 2：每个节点分配 T 个随机令牌, 并设置大小相等的分区：在此策略中, 哈希空间被划分为 Q 个大小相等的分区/范围, 每个节点分配 T 个随机令牌. Q 通常设置为 Q = N 和 Q = S*T, 其中 S 是系统中的节点数. 在此策略中, 令牌仅用于构建将哈希空间中的值映射到有序节点列表的函数, 而不用于决定分区. 从分区末端顺时针遍历一致性哈希环时遇到的前 N 个唯一节点将被放置到该节点上. 图 7 展示了 N=3 时的此策略. 在此示例中, 从包含键 k1 的分区末端遍历环时会遇到节点 A、B、C. 此策略的主要优点是：(i) 分区与分区放置解耦, 以及 (ii) 能够在运行时更改放置方案.

策略 3：每个节点 Q/S 个令牌, 大小相等的分区：与策略 2 类似, 此策略将哈希空间划分为 Q 个大小相等的分区, 并且分区的放置与分区方案无关. 此外, 每个节点分配有 Q/S 个令牌, 其中 S 是系统中的节点数. 当一个节点离开系统时, 其令牌会随机分配给剩余节点, 以保留这些属性. 同样, 当一个节点加入系统时, 它会以保留这些属性的方式从系统中的节点“窃取”令牌.

针对 S=30 和 N=3 的系统, 评估了这三种策略的效率. 然而, 公平地比较这些不同的策略并非易事, 因为不同的策略具有不同的配置来调整其效率. 例如, 策略 1 的负载分布属性取决于令牌数量（即 T）, 而策略 3 则取决于分区数量（即 Q）. 比较这些策略的一种公平方法是评估其负载分布的偏差, 同时所有策略都使用相同的空间来维护其成员信息. 例如, 在策略 1 中, 每个节点需要维护环中所有节点的令牌位置, 而在策略 3 中, 每个节点需要维护分配给每个节点的分区信息.

在我们的下一个实验中, 我们通过改变相关参数（T 和 Q）来评估这些策略. 我们针对每个节点需要维护的不同规模的成员信息, 测量了每种策略的负载均衡效率, 其中负载均衡效率定义为每个节点服务的平均请求数与最热节点服务的最大请求数之比.

结果如图 8 所示. 从图中可以看出, 策略 3 的负载均衡效率最高, 策略 2 的负载均衡效率最差. 在 Dynamo 实例从策略 1 迁移到策略 3 的过程中, 策略 2 曾短暂地充当过一个过渡阶段. 与策略 1 相比, 策略 3 的效率更高, 并且将每个节点维护的成员信息大小减少了三个数量级. 虽然存储不是主要问题, 但节点会定期交换成员信息, 因此最好尽可能保持这些信息的紧凑. 除此之外, 策略 3 还具有以下优势, 部署更简单：(i) 更快的引导/恢复：由于分区范围是固定的, 它们可以存储在单独的文件中, 这意味着只需传输文件即可将分区作为一个单元进行重新定位（避免了定位特定项目所需的随机访问）. 这简化了引导和恢复的过程. （二）易于归档：定期归档数据集是大多数亚马逊存储服务的强制性要求. 在策略 3 中, 归档 Dynamo 存储的整个数据集更为简单, 因为分区文件可以单独归档. 相比之下, 在策略 1 中, 令牌是随机选择的, 归档 Dynamo 中存储的数据需要分别从各个节点检索密钥, 这通常效率低下且速度缓慢. 策略 3 的缺点是, 更改节点成员身份需要协调, 以保留分配所需的属性.

#6.3 偏离的版本: 何时以及有多少

#6.4 客户端协调还是服务器协调

如第 5 节所述, Dynamo 有一个请求协调组件, 它使用状态机来处理传入的请求. 客户端请求由负载均衡器统一分配给环中的节点. 任何 Dynamo 节点都可以充当 get 请求的 Coordinator. 另一方面, put 请求将由键当前 Preference list 中的节点协调. 这种限制是由于这些优先节点还承担了创建新版本戳的额外责任, 该戳会因果地包含被写请求更新的版本. 需要注意的是, 如果 Dynamo 的版本控制方案基于物理时间戳, 则任何节点都可以协调写请求.

请求协调的另一种方法是将状态机移至客户端节点. 在此方案中, 客户端应用程序使用库在本地执行请求协调. 客户端会定期随机选择一个 Dynamo 节点, 并下载其当前的 Dynamo 成员状态视图. 使用此信息, 客户端可以确定哪些节点集合构成了任何给定键的 Preference list. 读取请求可以在客户端节点进行协调, 从而避免了负载均衡器将请求分配给随机 Dynamo 节点时产生的额外网络跃点. 写入操作将被转发到键的 Preference list 中的节点, 或者如果 Dynamo 使用基于时间戳的版本控制, 则可以在本地进行协调.

客户端驱动协调方法的一个重要优势是不再需要负载均衡器来均匀分配客户端负载. 通过将密钥近乎均匀地分配给存储节点, 可以隐式地保证公平的负载分配. 显然, 该方案的效率取决于客户端成员信息的新鲜度. 目前, 客户端每 10 秒轮询一个随机的 Dynamo 节点以获取成员更新. 选择基于拉取的方法而不是基于推送的方法, 因为前者在客户端数量较多的情况下扩展性更好, 并且只需要在服务器上维护很少的客户端状态. 然而, 在最坏的情况下, 客户端可能会在 10 秒内面临过时的成员信息. 如果客户端检测到其成员表已过时（例如, 当某些成员无法访问时）, 它将立即刷新其成员信息.

表 2 显示了与服务器驱动方法相比, 使用客户端驱动协调方法在 24 小时内观察到的 99.9 百分位和平均值的延迟改进. 从表中可以看出, 客户端驱动协调方法将 99.9 百分位延迟至少降低了 30 毫秒, 并将平均值降低了 3 到 4 毫秒. 延迟的改进是因为客户端驱动方法消除了负载均衡器的开销以及将请求分配给随机节点时可能产生的额外网络跃点. 从表中可以看出, 平均延迟往往明显低于 99.9 百分位的延迟. 这是因为 Dynamo 的存储引擎缓存和写缓冲区具有良好的命中率. 此外, 由于负载均衡器和网络为响应时间引入了额外的可变性, 因此 99.9 百分位的响应时间增益高于平均值.

#6.5 平衡后台任务与前台任务

除了正常的前台 put/get 操作外, 每个节点还执行不同类型的后台任务, 用于副本同步和数据交接（由于提示或添加/删除节点）. 在早期的生产设置中, 这些后台任务引发了资源争用问题, 并影响了常规 put 和 get 操作的性能. 因此, 有必要确保后台任务仅在常规关键操作不会受到显著影响时运行. 为此, 后台任务与准入控制机制集成. 每个后台任务都使用此控制器来预留资源（例如数据库）的运行时片段, 供所有后台任务共享. 采用基于对前台任务性能的监控的反馈机制来更改可供后台任务使用的片段数量.

准入控制器在执行前台 put/get 操作时, 会持续监控资源访问行为. 监控的方面包括磁盘操作的延迟、由于锁争用和事务超时导致的数据库访问失败, 以及请求队列等待时间. 这些信息用于检查给定尾随时间窗口内的延迟（或失败）百分位数是否接近期望阈值. 例如, 后台控制器会检查数据库读取的 p99 延迟（过去 60 秒内）与预设阈值（例如 50ms）的接近程度. 控制器使用此类比较来评估前台操作的资源可用性. 随后, 它会决定有多少时间片可供后台任务使用, 从而利用反馈回路来限制后台活动的侵入性. 需要注意的是, [4]中已经研究了类似的后台任务管理问题.

#6.6 讨论

本节总结了在实施和维护 Dynamo 过程中获得的一些经验. 过去两年, 许多 Amazon 内部服务都使用了 Dynamo, 它为其应用程序提供了相当高的可用性. 特别是, 应用程序对 99.9995% 的请求都收到了成功响应（没有超时）, 迄今为止没有发生过任何数据丢失事件.

此外, Dynamo 的主要优势在于它提供了必要的旋钮, 可以使用 (N, R, W) 三个参数来根据需求调整实例. 与流行的商业数据存储不同, Dynamo 将数据一致性和协调逻辑问题暴露给开发人员. 一开始, 人们可能会认为应用程序逻辑会更加复杂. 然而, 从历史上看, 亚马逊的平台是为高可用性而构建的, 许多应用程序的设计都考虑到了处理可能出现的各种故障模式和不一致性. 因此, 将这些应用程序移植到 Dynamo 是一个相对简单的任务. 对于想要使用 Dynamo 的新应用程序, 在开发的初始阶段需要进行一些分析, 以选择合适的冲突解决机制, 从而满足业务案例的需求. 最后, Dynamo 采用完全成员模型, 每个节点都知道其对等节点托管的数据. 为此, 每个节点都会主动与系统中的其他节点传播完整的路由表. 这种模型对于包含数百个节点的系统非常有效. 然而, 将这样的设计扩展到数万个节点并非易事, 因为维护路由表的开销会随着系统规模的增加而增加. 这一限制或许可以通过在 Dynamo 中引入分层扩展来克服. 另外, 值得注意的是, O(1) DHT 系统（例如 [14]）正在积极解决这个问题.

#7. 结论

本文介绍了 Dynamo, 一个高可用且可扩展的数据存储系统, 用于存储 Amazon.com 电商平台多项核心服务的状态. Dynamo 提供了所需的可用性和性能, 并成功应对了服务器故障、数据中心故障和网络分区. Dynamo 具有增量式可扩展性, 允许服务所有者根据当前请求负载进行扩展和缩减. Dynamo 允许服务所有者通过调整 N、R 和 W 参数来定制存储系统, 以满足其所需的性能、持久性和一致性 SLA.

Dynamo 在过去一年的生产环境中的应用表明, 分散式技术可以结合起来, 提供单一的高可用性系统. 它在最具挑战性的应用环境之一中的成功表明, 最终一致性存储系统可以成为高可用性应用程序的基石.

#参考资料

Amazon’s Dynamo (2007.10.2)

Dynamo 并不直接作为 Web 服务对外公开；但是, Dynamo 和类似的 Amazon 技术用于支持我们的 Amazon Web Services 的部分功能, 例如 S3.

A Decade of Dynamo: Powering the next wave of high-performance, internet-scale applications (2017.10.2)

一切始于 2004 年, 当时亚马逊正在运行 Oracle 企业版, 并配备集群和复制功能. 我们拥有一支高级 DBA 团队, 并能与 Oracle 内部的顶级专家沟通. 我们当时正在突破当时领先的商业数据库的极限, 无法满足我们日益增长的亚马逊业务对可用性、可扩展性和性能的需求. 我们基于 Oracle 的数据库基础架构已不堪重负, 这促使我们评估能否开发一个能够长期支持我们业务需求的专用数据库. 我们优先考虑能够支持亚马逊购物车等大规模、关键任务服务的需求, 并质疑关系数据库传统上持有的假设, 例如对强一致性的要求. 我们的目标是构建一个拥有无限可扩展性、一致性能和高可用性的数据库, 以支持我们快速增长的业务需求. 深入研究我们现有数据库的使用情况后发现, 它们的关系功能经常被忽略. 大约 70% 的操作属于键值类型, 即仅使用主键并返回一行. 大约 20% 的操作会返回一组行, 但仍然只对单个表进行操作. 考虑到这些需求, 并秉持着勇于挑战现状的理念, 一小群分布式系统专家齐聚一堂, 设计了一个可水平扩展的分布式数据库, 该数据库可以同时扩展读写能力, 以满足我们业务的长期需求. 这就是 Amazon Dynamo 数据库的起源. … Dynamo 的白皮书广受好评, 并成为创建分布式数据库技术类别（如今通常称为“NoSQL”）的催化剂.

论文笔记：[SOSP 2007] Dynamo: Amazon’s Highly Available Key-value Store