..

Dynamo: Amazon's Highly Available Key-value Store

1-Abstract

Dynamo 是 Amazon 提出的高可用键值存储系统。为了保证系统的高可用，牺牲了一些特定场景下的一致性。Dynamo 使用了对象版本化（object versioning）与应用协助解决冲突（application-assisted conflict resolution）的机制。

2-Introduction

Amazon 的基础设施由数百万台设备组成，任何时刻都会有比例小但是数量不少的设备发生故障。因此，可以将故障看作是正常的，可预期的行为，软件系统不应该因为硬件设备故障影响自身的可用性与性能。

Dynamo 的目标是实现一个永远可用（always available）的系统：即使服务器故障或者网络异常，用户也能往自己的购物车里添加商品。基于以下技术保证了高可用性与高扩展性：

  • 数据通过一致性 Hash 进行分区与复制
  • 通过对象版本化实现一致性（最终一致性）
  • 数据副本之间的一致性通过“类似仲裁的技术”与“去中心化的副本同步协议”保证
  • 以 gossip 协议为基础的分布式故障检测与成员检测协议

Dynamo 系统通过组合不同的技术实现一个高度可用（high-available）的系统，并证明了最终一致性存储系统可以用于生产环境，满足应用的高可用要求。

3-Background

Amazon 电商平台由几百个服务组成，有些服务是无状态的（如聚合其他服务响应的服务），有些服务是有状态的（如基于存储在数据仓库中的状态，执行业务逻辑并产生响应的服务）。传统上，服务状态使用关系型数据库存储；但是，对很多持久状态的存储需求来说，关系型数据库有一些局限性：

  • 该类型的服务大部分情况下只需要使用主键检索，并不需要关系型数据库提供的复杂查询和管理功能
  • 关系型数据库的复制功能受限，而且通常通过牺牲可用性来换取一致性；水平扩展（scale-out）不足

针对关系型数据库的不足，Dynamo 能够做到高度可用，有定义清晰的一致性窗口（clearly defined consistency window），易用的水平扩展方案。

Dynamo 支持独立部署，不同的业务使用不同的 Dynamo 系统

3-1-System Assumptions and Requirements

对接入 Dynamo 的服务有以下假设：

  1. 查询模型（Query Model）
    1. 通过唯一 key 进行数据读写操作
    2. 任何读写操作都不会跨多个数据单元（data item）
    3. 没有关系型 schema 需求
    4. 需要存储的文件较小（< 1MB）
  2. ACID 特性（ACID Properties）
    1. 在数据库领域中，ACID 是保证事务可靠执行的保证；但是这些特性会牺牲系统的可用性。Dynamo 实现目标是：允许通过牺牲一些一致性（C）提高可用性
    2. Dynamo 不提供任何隔离保证，只允许单个key 的更新操作
  3. 效率（Efficiency）
    1. 系统需要满足严格的 SLA（通过 TP999 衡量）；并允许业务自定义配置 Dynamo 以满足吞吐量 & 延迟的需求

3-2-Design Considerations

为了达到强一致性，一般数据库会采用同步复制算法。这类算法在某些故障场景下牺牲了可用性，如当数据出现冲突，则暂时禁止对该数据的访问，直到冲突解决。

分布式系统是无法同时满足 C（强一致性），A（高可用性），P（网络故障容忍）三个特性；因此，在不同的业务场景下需要选择不同的特性：是强一致性还是高可用性。

在服务器与网络故障比较高的场景下，可以通过乐观复制（optimistic replication）提高可用性：在后台通过异步同步将数据变更复制到其他节点，能够容忍并发更新与操作异常。不过这种方式虽然能够提高可用性，但是会导致数据冲突，需要检测并修复冲突。那么：

  • 什么时候解决冲突
  • 由谁解决冲突

Dynamo 被设计为最终一致性数据仓库（eventually consistent data store），所有的数据变更最后都会同步到所有副本

  1. 什么时候解决冲突

    解决冲突的时机有两个：读时 & 写时。

    传统数据库在写时解决冲突，可以使得读操作比较简单。这种方式在系统不能访问大部分（或者全部）副本时，就会拒绝写。

    Dynamo 期望保证永远可写（always writeable），所以在数据读取时解决冲突，以保证写操作不会被拒绝。

  2. 谁解决冲突

    冲突解决方也有两个：业务服务 & 数据库。

    如果由数据库来解决，只能执行一些简单的策略，如最后写有效（last write wins）。

    由于业务服务能够更了解数据的作用，可以更加灵活地选择对用户体验最好的冲突解决算法，如合并冲突的版本。

  3. 其他设计原则

    1. 增量扩展性（Incremental scalability）：支持逐个节点扩容，并减小对系统的影响
    2. 对称性（Symmetry）：每个节点的职责应该是相同的；对称性简化了系统的运维
    3. 去中心化（Decentralization）：去中心化是对称性的进一步扩展；系统应该是去中心化，点对点的，而不是集中控制；去中心化能够使得系统更加简单，更具可扩展性 & 可用性
    4. 异构性（Heterogeneity）：负载的分布要与节点的承载能力成正比

传统复制型关系数据库将关注点都放在保证副本强一致性上；虽然强一致性可以给应用的写操作提供方便的编程模型， 但导致系统的扩展性和可用性非常受限，无法处理网络分裂的情况。

4-System Architecture

Dynamo 使用的分布式系统技术有：分区（partition），复制（replication），版本化（versioning），成员管理（membership），故障处理（failure handling），规模扩展（scaling）。

下表展示了这些技术的优势：

问题 技术 优势
数据分区 一致性 Hash 增量可扩展性
写操作高可用 读时协调（冲突解决）的向量时钟 版本大小与更新频率解耦
短时故障处理 宽松的选举和 hinted handoff 部分副本不可用时，仍然可以保证高可用性和持久性
持久故障恢复 基于 Merkle tree 的逆熵 后台同步版本不一致的副本
成员管理与故障检测 基于 Gossip 协议的成员管理协议和故障检测 保持了架构的对称性：无需一个中心组件（centralized registry）来存储成员和节点状态等信息

4-1 System Interface

Dynamo 系统提供两个简单的接口：

  • get(key)
  • put(key)

get(key) 会定位到存储系统中 key 对应的所有对象副本，返回对象（可能是单个对象，也可能是一个对象列表: 有冲突情况下，包括了所有版本），以及一个 context（ 上下文）。

put(key) 确定对象应该存放的位置，然后写到相应的磁盘（put 请求会携带 context 上报）。

context 包含了系统中对象的元数据，例如对象的版本，对调用方是不透明的（ opaque）。

上下文信息是和对象存储在一起的，这样系统容易验证 put 请求的 context 是否合法

Dynamo 将调用方提供的 key 和对象都视为不透明的字节序列（opaque array of bytes） 。它对 key 应用 MD5 Hash 得到一个 128bit 的 ID，并根据这个 ID 计算应该存储到哪些节点。

4-2 Partitioning Algorithm

Dynamo 的一个核心需求是：支持数据增量扩展（scale incrementally）。为了实现该目标，需要将数据分散到系统中的不同节点上。Dynamo 采取的方案是一致性 Hash。

在一致性哈希中，哈希函数的输出是一个固定的范围，通常作为一个循环空间，或称环（ring）。每个节点都会随机分配一个在这个循环空间内的值，这个值代表了节点在这个环上的位置。

如何确定一条数据对应的存储节点：

  1. 对 key 进行哈希得到一个哈希值
  2. 在环上沿着顺时针方向找到第一个所带的值比这个哈希值更大的节点

每个节点要负责环上从它自己到它的下一个节点之间的区域。一致性哈希的主要好处是 ：添加或删除节点只会影响相邻的节点，其他节点不受影响。

不过基础的一致性 Hash 算法有些问题：

  • 给每个节点分配一个随机位置会导致数据与负载的非均匀分配
  • 未考虑节点的异构（不同节点配置不同，对应的性能也不同）

Dynamo 使用虚拟节点（virtual node）进行优化：一个物理节点对应多个虚拟节点，每个虚拟节点分散到环上的不同位置，能够有效进行负载的均匀分配。

引用了虚拟节点之后：

  • 节点不可用时，其负载会均匀分散到其他可用节点上
  • 新增节点会获得与其他节点大致相同的负载
  • 一个物理节点对应的虚拟节点数目可以根据其实际性能来决定，可以充分考虑机器的异构性

4-3 Replication

为了实现高可用性和持久性，Dynamo 将数据复制到 N 台机器上（N 可配）。

每个 key k，会被分配一个 Coordinator（协调者）节点。 Coordinator 负责落到它管理的范围内的数据的复制。Coordinator 除了自己存储一份之外，还会在环上顺时针方向的其他 N-1 个节点复制一份副本。因此在系统中，每个节点要负责从它自己往后的一共 N 个节点。

在图中，K 不仅存储在节点 B 中，还存储在节点 C，D 中。由于每个节点会保存其前继节点中的数据，所以节点 D 中包含的 Key 范围为 (A, D]，C 的范围为 (A, C]。

在 Dynamo 中有一个优先列表（preference list）概念：存储某个特定 key 的所有节点组成一个列表。对于给定的 key，每个节点都能决定哪些节点可以进入这个列表。为了应对节点失效的情况，preference list 会包含超过 N 个节点。

every node in the system can determine which nodes should be in this list for any particular key. To account for node failures, preference list contains more than N nodes.

由于引入了虚拟节点，存储一个 key 的 N 个节点，实际上对应的物理节点可能少于 N 个（例如，一个节点可能会占用环上的不止一个节点）。为了避免这个问题 ，preference list 在选择节点的时候会跳过一些位置，以保证 list 里面的节点都在不同的物理节点上。

4-4 Data Versioning

Dynamo 提供最终一致性，所有数据变更操作会在后台异步传递给其他副本。

在这种情况下，当 put(key) 返回时，最新数据可能还没有复制到 preference list 中的所有副本。此时进行 get(key) 操作可能不会获取到最新的数据，那么之后的更新操作会在旧数据上进行。

异步更新在没有故障的情况下会有一个耗时上限，但是如果存在故障（如网络分区），所有副本的更新耗时可能会无限大

Dynamo 为了保证始终可写的特性，需要容忍这种不一致性，将不同更新结果都保留，并在之后的步骤中处理更新冲突。

加入用户向购物车中添加商品 A，之后查询购物车为空并重新添加商品 B，此时 Dynamo 需要将 A，B 两个商品都保留并在之后解决冲突

4-4-1 How to Fix Conflicts

为了实现该目标，Dynamo 将每次更新结果都作为一个新的，不可变更的版本，则系统中会同时存在多个不同的版本。

在大部分情况下，新版本都包含旧版本的数据，而且系统自己可以判断哪个是权威版本 （syntactic reconciliation）；但是，在发生故障并且存在并发更新的场景下，版本会发生分叉（version branching），导致对象版本冲突。系统本身无法处理这种情况，需要客户端介入，将多个分支合并成一个。

冲突的版本可能会有多个，并且每个版本都有自己的子历史版本，这些版本都需要系统来将其一致化。

4-4-2 Vector Clock

Dynamo 使用向量时钟（vector clock）来跟踪同一对象不同版本之间的因果性。

一个向量时钟就是一个 (node, counter) 列表，如 D [(node-1, 2), [node-2, 3], [node-3, 1]]。一个向量时钟关联了一个对象的所有版本，可以通过其来判断对象的两个版本是否在并行的分支上，或者它们是否有因果关系。如果对象的第一个时钟上的所有 counter 都小于它的第二个时钟上的 counter，那第一个时钟就是第二的祖先，可以安全的删除；否则，这两个修改就是有冲突的，需要解决冲突。

客户端更新对象时，必须要先指定基于哪个版本进行更新：

  1. 执行 get(key) 操作获取 context 信息：包含了 vector clock
  2. 基于指定的版本进行更新：携带 context

Dynamo 在收到客户端的读请求后，如果能够获取到多个版本，并且无法解决这些版本之间的冲突，那么 Dynamo 会返回所有的版本，并在 context 中携带各个版本对应的 vector clock 信息。客户端在收到多个版本之后，解决冲突，并基于指定版本更新，将多个分支重新合并为一个新分支。

上图展示了 vector clock 的用法：

  1. 客户端 A 创建一个新的对象，并且该 put 请求被节点 Sx 处理。Sx 增加该对象的序列号 1，并使用该序列号创建该对象的 vector clock。系统中此时存在对象 D1 及对应的 clock: [(Sx, 1)]
  2. 客户端 A 更新该对象，假设更新请求被同一个节点 Sx 处理，那么系统中新增另一个对象 D2 [(Sx, 2)]。由于 D2 继承自 D1，因此可以覆盖 D1。Dynamo 异步复制数据，所以可能存在节点包含了 D1，但是并没有 D2。
  3. 客户端 A 再次更新该对象（会先读并获取 D2），并且更新请求被另一个节点 Sy 处理；那么系统中就会存在对象 D3 [(Sx, 2), (Sy, 1)]
  4. 客户端 B 读取了 D2 并尝试更新，并且该请求被另一个节点 Sz 处理；那么系统中就会存在对象 D4 [(Sx2, 2),(Sx, 1)]
  5. 现在 Dynamo 系统中存在多个版本的对象：D1, D2, D3, D4
    1. 如果一个节点知道了 D1 或 D2 的存在，那么当其接收到 D4 时，能够判断 D1 或 D2 被新的数据（D4）覆盖了，此时可以直接回收 D1, D2
    2. 如果一个节点知道 D3 的存在，那么当其收到 D4 时，会发现 D3, D4 是冲突的（没有因果关系）。这两个版本都应该被保留，并且待客户端下次读的时候全部返回，交给客户端解决冲突
  6. 客户端读取到了 D3, D4，返回的 context 综合了 D3, D4 的 clock: [(Sx, 2),(Sy, 1),(Sz, 1)]。如果客户端解决冲突并在节点 Sx 进行协调写操作，那么 Sx 会更新自己的序列号，生成的新对象 D5 [(Sx, 3),(Sy, 1),(Sz, 1)]

vector clock 存在一个问题：如果多个节点先后执行同一个对象的写操作，那么该对象的时钟向量就会变得很长。

一般写操作只会被 preference list 中的前 N 个节点执行，长度可控

4-5 Execution of Get () and Put () Operations

在 Dynamo 中，任意节点都可以处理任意 key 的 get() & put() 请求。

操作请求路由有两种方式：

  1. 由负载均衡器根据节点的负载选择一个节点进行请求
  2. 使用能够感知分区的客户端，将请求直接路由到 coordinator 节点

负责处理读写请求的节点被称为 coordinator。一般情况下 coordinator 是 preference list 中前 N 个节点中的第一个（注意 list 中的节点数大于 N）。

如果请求是通过负载均衡器转发的，那么可能会被路由到任意一个节点上。此时，如果被路由的节点不是 preference list 中前 N 个节点的第一个节点，那么它不会处理该请求，而是将请求转发到 list 中第一个节点

读写操作需要 preference list 中前 N 个节点都处于健康状态：

  • 如果前 N 个节点均健康，则取前 N 个节点
  • 如果前 N 个节点中存在不可用节点，则跳过，优先访问 list 中编号较小的节点

4-5-1 Quorum Algrithom

为了保证副本的一致性，Dynamo 使用了一种类似仲裁系统（quorum systems）的一致性协议。 这个协议有两个配置参数：R 和 W：

  • R：允许执行一次读操作所需的最少投票者
  • W：允许执行一次写操作所需的最少投票者
  • 并且  R + W > N

这种情况下， get or put 的延迟由 R（或 W）个副本中最慢的一个决 定。因此，为了降低延迟，R 和 W 通常设置的比 N 小。

4-5-2 Get () and Put () Operations

Put() 操作流程 ：

  1. coordinator 收到 put() 请求后，创建新的 vector clock，并将其保存在本地
  2. coordinator 将最新的版本对象发送给 preference list 中前 N 个健康节点
  3. 前 N 个节点中如果有至少 W-1 个节点返回成功，则该 put() 请求成功

Get() 操作流程 ：

  1. coordinator 收到 get() 请求后，向 preference list 中前 N 个健康节点查询该 key 对应的数据版本
  2. coordinator 收到 R 个响应之后，将结果返回给客户端
    1. 如果 coordinator 获取到了多个版本，会将没有因果关系的版本返回给客户端，客户端需要对该结果进行冲突解决，合并成最新版本，然后将结果重新回写 Dynamo

4-6 Handling Failures: Hinted Handoff

传统的仲裁算法无法保证 Dynamo 系统在节点失效或者网络分区的情况下仍然可用，持久性也会降低。

因此，Dynamo 采用宽松的仲裁机制（sloppy quorum）：所有读写操作在 preference list 的前 N 个健康节点执行（前 N 个健康节点不一定是前 N 个节点，如果遇到不健康的节点，会顺延）。

在之前数据分区的例子中，N =3。

  • 如果 A 节点临时不可用，那么本应该发送给 A 的更新请求会被发送到 D
  • 发送到 D 的副本的元数据中会提示 (hint) 这个副本本应该发送给 A
  • 该数据被 D 保存到本地一个独立的数据库中
    • D 有一个定时任务不断扫描，如果发现 A 重新变得可用了，就将数据发送给 A
    • 成功发送回 A 之后，D 可以将该数据从本地数据库中删除；以保证系统内的副本数保持不变

通过 hinted handoff 机制，保证了在节点或者网络发生临时故障时，读写操作不会失败，提高了可用性与持久性。

通过配置不同的 R 与 W，可以满足不同级别的可用性与持久性；W = 1 可用性最高，但是持久性较低

为了提高容灾等级，保证整个数据中心挂掉的情况下系统仍然可用，可以将 preference list 中的节点分散到不同的数据中心。

4-7 Handling Permanent Failures: Replica Synchronization

hinted handoff 机制在短时故障的场景下运行良好，但是对于长期故障的场景无法保证持久性：在 hinted 副本移交给本应该存储该副本的节点之前，该副本就不可用了，那么系统中的副本就会出现不一致的情况。

为了保证不同副本之间的一致性，Dynamo 实现一种逆熵（副本同步）协议来保证副本之间是同步的。

为了快速检测副本之间的不一致性，以及最小转移的数据量，Dynamo 使用了 Merkle tree。

Merkle tree 是一个 Hash tree：叶子节点是 key 对应的 value 的 hash 值；父节点是子节点的 hash

如果两棵树的根节点 hash 值相同，那么这两棵树的叶子节点肯定相同，则这两棵树是一致的；否则这两棵树存在不一致的数据，需要继续比较其子节点的 hash 值，直到找到不一致的子树。

Dynamo 系统的每个节点为每段 key range 维护了一个单独的 Merkle tree。不同节点之间可以比较其维护的 key range 内的 key 是否一致。

key range: 一致性 hash 环中每个节点维护的范围

这种方案的缺点是：每当有节点加入或离开系统时，一些 key range 会变，因此对应的 tree 需要重新计算。

4-8 Membership and Failure Detection

4-8-1 Ring Membership

Dynamo 使用显示机制来向 hash ring 中增删节点。

通常情况下节点不可用持续的时间都比较短，一个节点的临时不可用不能说明这个节点永久离开了系统，因此不应该在节点不可用时立即进行 re-partiton，或者修复无法访问的副本

管理员通过命令行手动添加或者删除节点，负责处理该请求的节点将成员变动的信息持久化到本地，并通过 gossip-based 算法广播成员变动信息，保证成员信息的一致性。

每个节点周期性地随机选择另一个节点，这两个节点互相交换自己拥有的成员信息，维护成员信息的一致性。

  1. 节点启动时，计算自己的 token 集合（一致性 hash ring 上的 token range）
  2. 将节点映射到 token 集合中（包含虚拟节点）
  3. 将映射关系持久化到本地
  4. 与其他节点交换自己维护的成员信息，从而不同节点保持一致
  5. 通过 gossip-based 协议多次交换后，每个节点都会知道其他节点负责的 token 范围

成员信息的交换，既能保证维护信息的一致性，也能够使得每个节点都可以将任意 key 的读写操作直接发送给正确的节点处理。

4-8-2 External Discovery

上述成员信息维护流程啃根会导致 Dynamo 在逻辑上的临时分裂：管理员添加 A 节点，A 维护了自己的 token 集合；之后管理员又将 B 添加到系统中，B 也维护了自己的 token 集合；但是 A，B 两个节点无法感知对方的存在，就无法进行信息交换。

为了避免逻辑分裂，可以通过外部机制配置一些 Dynamo 节点作为种子节点：所有节点都知道种子节点的存在，并和种子节点交换自己的信息，最终所有节点都会感知对方的存在，避免逻辑分裂的可能。

种子节点只是一个普通的 Dynamo 节点，不过是提前配置在配置中心或者配置文件中

4-8-3 Failure Detection

故障检测是一个纯本地概念（pure local notion）的检测机制：只要节点 B 没有应答 A 的请求，那么 A 就认为 B 发生故障，不可访问。

如果 A 认为 B 是故障的，那么可以选择与 B 拥有同一个 partition 的其他节点（preference list 中的其他节点）来处理请求，并定期检查 B 是否再次可用。

故障检测的目的是为了避免尝试与不可访问的节点持续通信，如：

  • get(), put() 操作访问的节点
  • 转移 partition 和 临时副本(hinted replica) 时的目标节点

在没有客户端请求的情况下，节点之间并不需要知道对方是否故障；在客户端持续请求下，不同节点间会持续交互，此时如果对方不可访问，当前节点也会立马知道。

4-9 Adding/Removing Storage Nodes

当新节点 X 添加到系统中后，它会获得一些随机分散在 hash ring 上的 token 集合。

如 X 加入 A, B 节点之间，X 就会负责(F, G], (G, A] and (A, X] 之间的 key。相应地，B, C, D 节点就不需要负责相应的 range 了。在收到 X 转移 key 的请求之后，B, C, D 会向 X 转移相应的 key。

节点移除的分配顺序相反

通过这种方式，可以使得 key 在存储节点上均匀分布。同时，为了不重复转移 key range，需要在源节点与目标节点间添加确认机制。

5-Implementation

Dynamo 系统中的每个节点上有 3 个组件：

  1. request coordination（请求协调）组件
  2. 成员验证 & 故障检测组件
  3. 本地持久化存储引擎

5-1 Local Storage

存储引擎组件设计为可插拔：为不同访问类型选择合适的存储引擎。如 BDB 适合处理几十 KB 大小的对象，MySQL 适合处理更大的对象

5-2 Request Coordination

Coordinator 构建在事件驱动的消息系统上，用于代替客户端执行读写请求：

  • 读操作会从一个或者多个节点收集数据
  • 写操作会向一个或者多个节点存储数据

Coordinator 会为每个请求创建一个状态机：包含了识别 key 对应的节点，发送请求，等待响应，重试，处理响应，组合响应，返回给客户端等逻辑。

每个状态机只会处理一个客户端请求，读操作流程为：

  1. 发送读请求给其他 Dynamo 节点
  2. 等待最少数量的响应
    1. 如果在一定时间内收到的响应数少于规定的，则认为请求失败
    2. 如果满足规定数量，则收集对象的所有版本，并确定返回版本
    3. 如果收到过期版本，则需要合并版本并回写给对应节点 —— 读修复(read repair)
  3. 生成上下文 context：包含版本向量时钟

即使读操作的结果已经响应给客户端，状态机也会等待一段时间，用于接受剩余节点可能的有效响应。

对于写操作，如果总是选择 preference list 中的第一个健康节点作为 coordinator，可以完成写操作的序列化，但是会导致负载不均衡（操作请求的 key 不一定是均匀分布的）。为了解决这个问题，preference list 中的前 N 个健康节点都可以作为 coordinator。

并且，每个写操作请求前都会先进行一次读操作，所以写操作的 coordinator 可以选择前一次读操作返回最快的节点（该信息存储在读操作的 context 中）。

该策略同时提高了“读取刚写入数据”的概率

6-Conclusions

Dynamo 作为一个高可用，高可扩展的数据仓库，提供了期望的可用性和性能等级，可以正确地处理服务器故障、数据中心故障和网络分裂；支持增量扩展；允许客户端应用可以通过对 N、R 和 W 三个参数进行调优来达到期望的性能、可用性和持久性等级。

Dynamo 表明了最终一致性存储系统可以作为高可用应用（highly available applications）的一块基石。