1. 介绍

Dynamo：高可用、高可扩展（水平扩展）的分布式K-V存储系统，它综合了下面的技术

• 利用一致性散列，进行数据分区和复制
• 利用版本控制提供一致性
• 使用quorum-like技术以及去中心化的副本同步协议，实现副本更新的一致（最终一致）
• 基于gossip，实现分布式的错误探测和成员协议
• 集群完全去中心化（无主架构），节点可随时加入/删除，不需要再次对数据进行手动划分或重新分配

2. 背景

2.1. 系统假设和要求

查询模型：一个主键作为唯一标识，值为二进制对象，没有多个数据项操作，没有关系方案

ACID属性：提供高可用、弱一致，不提供隔离性

效率：能在普通机器上运行，延时要求要度量到99.9百分位，满足严格是SLA（下面会说）

其它假设：内部使用，操作环境无恶意，无安全要求，集群规模达到上百个

2.2. 服务水平协议（SLA）

Amazon的平台架构图：

通常SLA使用平均数、中位数和预期变化，而Amazon使用99.9百分位进行测量。

2.3. 设计考虑

• 使用无主复制（所有副本都可接受写

  入，会导致冲突，见此），保证最终一致性

• 目标是永远可写，冲突解决推迟到读取

• 冲突解决可选择自定义合并，也可使用“最后一次写入获胜”等简单策略

• 不需要支持分层命名空间或者关系模式

• 基于可信基础设施，不需考虑安全

• 延时要求很高（因此路由使用zero-hop的DHT，避免像Chord的多节点路由）

• 其它原则：

  • 增量可扩展：增加一个节点，对系统影响很小
  • 对称性：类似对等网络，节点拥有一样的责任
  • 去中心化：对称性的延伸，避免集中控制
  • 异质性：系统能利用异质性的基础设施运行

3. 系统架构

技术概要：

3.1. 系统接口

暴露2个操作：

• get(key)：给定一个键，返回一个对象，或者一个包含版本冲突的对象列表和对应上下文

• put(key, context, object)：将键和值关联起来，并保存在磁盘上

  上下文包含了关于该对象的系统元数据（且包含对象的版本信息），对调用者不透明

  上下文信息和对象一起存储

Dynamo使用MD5对键进行散列，生成128位的ID，决定它处于那个分区。

3.2. 数据分区算法

划分基于一致性散列，优势在于：节点进进出出，只影响邻居节点。

此外，Dynamo使用虚拟节点，缓解分区不均匀的问题。它有以下优点：

• 若节点不可用，负载可以均匀分散到其它节点
• 若节点再次可用，或加入新节点，新的节点接受的负载和其它节点差不多
• 虚拟节点数目可根据物理节点的处理能力决定，可利用到物理基础设施的异质性

Dynamo经历了下面3个数据分区策略：

• 每个节点$T$个虚拟节点，并根据虚拟节点的散列值分区（即上面的分区方式）
  • 集群变动，键范围会被“窃取”（即环分割），需要数据重新平衡
  • 重新平衡需要扫描数据，很耗性能；Merkle tree需要重新计算；键范围的随机性难以对整个键空间做快照，使得归档复杂化
• 每个节点$T$个虚拟节点，每个分区的大小相同
  • 整个环分为$Q$个相同大小的分区，$N$为复制因子，$S$为节点个数，需要$Q » N$和$Q » S * T$
  • 当key落入环上的某个分区时，从分区尾部开始，沿顺时针遍历$N$个不同节点，这些节点就是首选列表中的节点
  • 好处
    • 数据的分区与分区的布局解耦
    • 运行时，可以改变数据安置方案
• 每个节点$Q/S$个虚拟节点，每个分区的大小相同（第二个方案的延伸）
  • 节点离开时，原有的虚拟节点会分配到其它节点；节点加入时，新节点会从其它节点的虚拟节点中“窃取”虚拟节点
  • 分片固定大小，可对应单个文件，因此容易加入或删除节点，且容易备份
  • 改变节点成员时，维护分配所需的属性需要协调

3.3. 数据复制

数据被复制到$N$（可配置）个节点：

• 客户端从首选列表中选取一个节点（即协调者），将请求发给它

  首选列表包含负责该数据的所有节点，且是去重的

  首选列表可包含多于$N$个，以容错

• 协调者将数据保存，并复制到其它$N-1$个节点

  即向首选列表的所有节点发送复制，并使用仲裁（quorum）机制

  实际上，散列环总体上看是连续的

3.4. 数据版本化

Dynamo对每次修改的结果都当成一个新的不可变的数据版本，允许同时出现多个版本对象。

多版本下，一般，新版本会包含旧版本，服务端可合并版本，决定权威版本。但可能出现冲突，则需要客户端合并并解决冲突。

Dynamo使用向量时钟捕捉版本的因果关系，向量时钟为[(node, counter), (node, counter), ...]的列表，比较方式如下所示，当出现“并发”时则认为冲突，需要协调：

更新时，需要指定更新到哪个版本，版本由上下文参数决定（可从读取中获得）。

若读取到的内容，服务端无法协调（产生多个版本分支，出现多个叶节点)，则需要将所有叶节点返回，让客户端协调。如下面的D3,D4，最后被客户端协调成D5并写回：

向量时钟可能会过度增长，使用截断方案解决。Dynamo会设置一个阈值（如10），超过阈值后，最早的一对时钟将会被删除。

3.5. get()和put()的执行——宽松的quorum

路由策略：

• 使用一个负载均衡器，选择节点（优点：客户端不会与Dynamo服务端有任何耦合）
• 客户端对分区敏感，直接路由（优点：延时较低）

但最终都会落到协调节点上，以处理数据的复制。协调节点通常是首选列表的第一个节点。

节点的选取：

• 协调节点通常是首选列表的第一个
• 访问时，选取列表的前$N$个健康节点，不可用的节点会被跳过

读写操作都基于仲裁（quorum），满足$R+W>N$，具体见此——宽松quorum：

为何是宽松的？

因为$N$的选取，可能会取到首选列表的第$N$项后面的节点，以提高可用性。

但是严格的quorum是不允许这么做，只能选取前$N$个（即散列环上遇到的那前$Ｎ$个节点）。

宽松的quorum会导致读取的数据不是最新的，需要暗示提交/数据回传。

• get()：
  • 从首选列表的前$N$个可达地点发送请求
  • 等待$R-1$个响应
  • 协调者将自己数据和响应数据收集起来，处理因果关系（合并），返回所有没有因果关系的数据（若有多个，即产生冲突，服务端无法协调合并，需要客户端协调合并）
  • 协调后（解决冲突并获得最新版本），取代当前版本，重新写回到所有副本（即读修复）
• put()：
  • 协调者生成新的向量时钟，并本地写入新版本
  • 将新版本数据（包含向量时钟）发给首选列表的前$N$个可达地点
  • 若收到$W-1$个响应，则返回写入成功

3.6. 临时故障处理：提示移交/数据回传

由于Dynamo使用sloppy quorum，读取时可能读不到最新数据。因此需要提示移交/数据回传。

在这种情况下（如故障）：

• 请求中会附带一个预期的节点，指明正确的接收者
• 当某节点接收到不属于自己的写数据，它会单独存储
• 后台会周期扫描，将数据回传给正确的节点

若写入需要最高的可用性，$W$可设为1（即本地成功即可）；若写入需要更高的持久性，$W$需要高一些。

一般$N$设为3，$R=W=2$，这种情况下大多数能满足性能、可用性和数据的持久性。

数据回传完成之前，数据本质上是不可用的/可能过时的。

3.7. 永久故障的处理：副本同步/反熵

Dynamo使用Merkle Tree，检测副本的不一致性，并降低数据量传输，并基于此实现反熵（后台同步数据）。

Merkle Tree：一个散列树，叶子为各个键的散列值。父节点为子节点的散列值。它可对树的每个分支进行独立检查，不需要传输整个树，降低数据的传输量。

检测方法：

• 每个节点为每个键范围（即一段由虚拟节点构成的散列环）维护一个Merkle tree
• 两节点交换树根（需要相应的键范围相同），比较散列值是否相同，若不同，则遍历树，并继续交换节点，确定不同的范围，并执行同步操作（即反熵）

3.8. 成员与错误检测

3.8.1. 环上成员

由于集群中节点的离开通常是暂时的，集群中节点的加入往往是意外的，因此需要显式添加/删除环上的成员，即：管理员需要手动发出“成员改变”指令以加入/删除节点。

手动操作以让节点永久性加入/离开集群

指令发出后：

• 接收指令者将变更写入持久性存储
• 基于Gossip协议，将变更传播到其它节点上

而分区和散列环上布局信息，也通过Gossip传播，因此每个节点都有足够的路由信息，可以对请求重定向。

3.8.2. 外部发现

由于Gossip协议，当节点加入到集群后，其它节点可能无法感知到它的存在（这里叫做逻辑分区）。

因此，一些节点会作为种子（seed），它的发现是通过外部机制实现的，其它所有节点都能马上知道它（因为它是配置好的）。节点最终都会和种子一起，协调成员关系。

3.8.3. 故障检测

纯本地的故障检测就足够了：每个节点都维护当前集群的成员及不可达的节点等信息

实现的时候，这些信息通过Gossip传播到集群。

协调者发现有不可达的节点时，会将请求发给备用节点，对方会触发数据回传（见提示移交/数据回传）。同时自己也会周期性检查暂时离开的节点是否又一次可达。

3.9. 添加/删除存储节点

节点加入后，环会变化，节点会有一部分区域不需要负责。

其它节点收到新加入节点的确认信号时，将适当的数据传给（offer）新节点。

节点离开时，执行一个相反的过程。

4. 系统实现

三个核心组件，几乎都由Java实现：

• 请求协调：

  • 基于事件驱动通信的基础上，基于Java NIO Channel；

  • 每个客户端的请求会让协调者创建一个状态机，执行：标识负责key的节点、发送请求、等待回应、重试处理、加功和包装返回客户端响应。状态机只处理一个客户端请求；

  • 首选列表的前$N$项都能作为协调者，防止负载不均

    由于写通常跟随在一个读操作之后，选择最快答复之前的读操作的节点，作为写的协调者。之前的读操作信息会保存在上下文中。

    这种优化能提高“读己之所写”的一致性。

• 成员与故障检测

• 本地持久化引擎：存储引擎可替换，如Berkeley DB、MySQL等等，并包含内存缓冲

• Previous
  BitTorrent: DHT Protocol
• Next
  论文阅读-Bitcoin: A Peer-to-Peer Electronic Cash System