云计算：Dynamo实现

Dynamo是Amazon提供的一款高可用的分布式Key-Value存储系统，其最大特点是去中心化。整个Dynamo存储平台由多个物理异构的机器组成（可以是廉价的普通机器），每台机器角色一样，可以随意添加或去除，并且不需要太多人为的干预。每台机器存放一部分数据，这些数据的备份同步完全由系统自己完成，单台机器故障甚至一个数据中心的断电故障都不会影响系统的可用性。因此，Dynamo是一个具有高可用性和高扩展性的分布式数据存储系统。

作为一类分布式系统的典型代表，Dynamo所使用的众多关键技术也给其带来一系列的优势，具体参看表7-5。

表7-5　Dynamo使用的技术和优势

续表

1）数据分区

为了达到增量可伸缩性的目的，Dynamo采用一致性哈希（Consistent Hashing）来完成数据分区，将数据分布到多个存储节点中。概括来说，就是给系统中的每个节点分配一个随机token，这些token构成一个哈希环（图7-10）。执行数据存放操作时，先计算主键Key的哈希值^[3]，然后存放到顺时针方向的第一个大于或者等于该哈希值的token所在的节点。

图7-10　Dynamo的分区与Key复制

一致性哈希最大的优点在于节点的扩容／缩容（加入／删除）只影响其直接的邻居节点，而对其他节点没有影响。这样看似很完美，但其实还存在两个问题：节点数据分布不均匀以及无视节点性能的异质性。为了解决这两个问题，Dynamo对一致性哈希进行了改进：每个物理节点根据其性能的差异分配多个token，每个token对应一个虚拟节点，每个虚拟节点的处理能力基本相当，并随机分布在哈希空间中。存储时，数据按照哈希值落到某个虚拟节点负责的区域，然后被存储到该虚拟节点所对应的物理节点。

2）数据复制

每个数据对象有N个副本，分别存放在N个不同的节点上面（N的建议值为3）。某个数据对象在地址环上顺时针找到N个不同的节点，这N个节点被称为这个数据的首选节点列表（Preference List）。如图7-10所示，Key为K的数据对象，它的首选节点列表为节点B、C、D。

Dynamo保证最终一致性而非强一致性。主要思路是对于一个写操作，系统将这个写请求发给所有N个副本，只要W个写请求返回成功，就认为写成功；对于一个读操作，系统将这个读请求发给N个副本，只要R个请求返回成功，就认为读成功。为了保证最终一致性，必须保证R＋W＞N。可以简单理解为读操作至少能读到一个最新的数据副本。不同的应用可以根据自己的需求设置不同的R、W、N。因为读写操作的延迟取决于R（or W）个副本中最慢的一个，所以通常将R和W设置为小于N的数来达到提高性能的效果。R、W、N是Dynamo的一个亮点。

3）数据版本和冲突处理

由前文可知，一个写操作只要成功写了W个副本就被认为写成功，且通常W＜N，所以接下来的读操作可能读到没有及时更新的数据，也可能由于网络问题，有些节点上的节点根本就没有收到写请求，这个时候读操作会读到几个版本不同的数据副本。通常来说，系统能区分数据的新版本和老版本并自动地合并它们，但是节点失效时的写操作可能会造成多个版本分支，即版本冲突。这种冲突只有应用层才能解决。总的来说，Dynamo保证所有的写操作都写到了某W个副本，应用层负责版本冲突的合并。

Dynamo用向量时钟（Vector Clocks）来确定数据版本。向量时钟实际上就是一个列表，列表的每个节点是一个对（node，counter）。其中，node是发送写请求的节点，即首选节点列表的第一个节点；counter代表写操作的时间，即clocks。数据版本之间的关系要么是因果关系，要么是平行关系，关系判断依赖于counter值大小。如果数据对象的一个版本中的所有向量时钟的counter值都小于或等于另一个版本中的，则是因果关系，那么因是果的祖先，可以认为是旧版数据而直接忽略；否则是平行关系，那么就认为数据版本产生了冲突，需要协调并合并。

图7-11是一个向量时钟应用的例子，D1是D2的祖先，D3和D4是两个分支版本，形成版本冲突，在下次写操作时，应用层将它们合并。目前Amazon的购物车应用采用了这种合并方式。(www.xing528.com)

图7-11　向量时钟应用

4）故障容错

Dynamo把故障分为两种类型：临时故障和永久故障。有一些故障是临时性的，比如偶然性的宕机、网络不通；其他故障，如硬盘保修或机器报废，由于其持续时间太长，称为永久性的。针对这两种故障类型，其容错机制如下：

（1）临时故障处理

为了保证每次都能写到W个副本，读到R个副本，每次读和写都是发送给N个节点。如果这N个节点有节点失效，那么往后继续找一个不同的节点，暂时代替失效的节点。例如N＝3，某个数据的首选节点列表是节点A、B、C。这时A节点失效，那么对于该数据的写请求将发送到节点B、C、D上。D暂时取代了A的角色，那些原本应该写到A上的数据存放在D中的一个特定的文件夹中，放在这个特定文件夹中意味着这些数据不是D本该拥有的，而是别的节点的。D上会启动一个线程，定期检查A的状态，当发现A恢复后，就将D上存放的那些A上的数据写回到A。这个技术被称为Hinted Handoff（数据回传）。这种策略，保证了节点失效时系统的高可用性和数据持久性。

（2）永久故障恢复

在节点永久故障时，需要进行副本同步。为了快速检测副本间的差异并最小化数据传输量，Dynamo使用Merkle哈希树技术，每个虚拟节点保存三棵Merkle树，即每个键值区间建立一个Merkle树。Dynamo中Merkle哈希树的叶子节点是存储每个数据分区内所有数据对应的哈希值，父节点是其所有子节点的哈希值。图7-12是两棵不同的Merkle哈希树A和B。

图7-12　Merkle哈希树

系统比较两棵同一键值区的Merkle哈希树时，首先査看根节点，如果相同则说明数据一致，不需要进行数据同步，否则需要继续比较，直到出现哈希值不同的叶子节点为止，快速定位差异。例如，图7-12中A和B的根节点不同，说明需要进行数据同步。紧接着比较A和B的子节点，发现右子树的根节点2≠15，继续比较右子树根节点的子节点，按同样的步骤一直进行下去，发现需要同步的数据位置。Merkle树最大特点是只要比较某个子树就可以完成数据同步检测和定位，进而进行同步，大大减少了同步过程中所需传输数据量，提高了系统效率。

5）成员资格及错误检测

（1）成员资格

Dynamo中的每个节点就是Dynamo的一个成员，Amazon为了使系统间数据的转发更加迅速（减少数据传送时延、增加响应速度），规定每个成员节点都要保存其他节点的路由信息。由机器或人为的因素，系统中成员的加入或撤离时常发生。为了保证每个节点保存的都是Dynamo中最新的成员信息，Dynamo使用一个基于Gossip的协议传播成员变动，每个节点每间隔一秒随机选择另一个节点，两个节点协调它们保存的成员变动历史。

（2）错误检测

在节点之间交换信息的过程中，如果节点失效，则会产生无效的传送信息，加重系统的传输负担，因此引入错误检测机制是很有必要的。Dynamo采用的错误检测机制非常简单、实用，一旦发现对方没有回应，就认为该节点失效，立刻选择别的节点进行通信。同时定期向失效节点发出消息，如果对方有回应则可以重新建立通信。去中心化的故障检测协议使用简单的Gossip式协议，使系统中的每个节点可以了解其他节点到达或离开。