分布式之DynamoDB

仔细思索分布式的CAP理论，就能发现P数据分区是分布式的特性，是必须满足的特点。如果一个系统没有数据分区的存在，那这样的系统就是单体，而不是分布式。CAP三个特性无法同时满足，那么所有的分布式系统实现都是在A(可用性)和C（一致性）之间权衡选择。

DynamoDB是Amazon的一个分布式的NOSQL数据系统，放弃了CAP的强一致性，保证高可用性。

DynamoDB是什么？

CAP只能保证满足AC中的一个，Dynamo的设计初衷是保证高可用，达到终一致性。

在分布式的环境里，强一致性协议也有很多，比如Raft就是这样的一种协议。 但是Dynamo的目标不在于强一致性，可以认为Dynamo是完全去中心化的，满足AP，保证终一致性。

Dynamo的设计是非常有意思的，他的独特的思想和实现给业界带来了很大的冲击。

Dynamo数据分布模型：一致性哈希

在分布式系统里，数据不是存放在一个单体里面，而是需要均匀安全的存放在非常多的节点上面。数据怎么分布，是分布式系统要考虑的关键问题之一。

Dynamo的数据分布（数据分片，也叫分区）使用的模型是一致性哈希模型。

一致性哈希是什么

哈希环的表示如下所示，用一个环表示0-2^32-1之间的范围。

数据分布的每个节点对应一个随机值，是环上的某个点。按照一致性方向，哈希环上的一段区间都映射到这个节点上面来（也就是说这段数据将会存储到这个节点）。

但是这样可能导致数据分布不均匀，负载量小的机器可能分配到很大的一片数值空间，负载量大的机器反而可能分配到很小的一片数值空间。

虚拟节点

为了更好的利用物理机器的异构性，一致性哈希提出了虚拟节点的设计思路：一个机器分配N个随机值（N的大小跟机器的能力有关系），对应哈希环上的N个节点，如下图所示。

Tij表示i机器的第j个虚拟节点,这个Hash Ringm目前有两个节点T1和T2，T1有三个虚拟节点T11、T12和T13，T2有两个虚拟节点T21和T22 。假设他们按照这种方式分布在环上。

全部数值区间按照一致的方向去映射， 比如T11对应的数值和T21对应数值之间的那一段的哈希值映射到虚拟节点T21上面。

Dynamo是一个纯粹的KV存储系统，这样的话每个key都会计算出一个哈希值，并存储到对应的虚拟节点上面（对应某一台机器）。

初始环

理解初始环的建立过程是虚拟节点建立一致性哈希的关键，建立过程如下图：

• T1初始化作为种子节点,生成【0，2^32-1】范围内的三个随机数，随机数对应T11、T12和T13。
• T2初始化，和种子节点联通，生成并上报自己生成的的random值序列T21、T22。
• 集群机器通过Gossip协议交换信息，这样大家都知道全局的虚拟节点地图了，也就是这个Hash Ring的分布图。

初始化的过程需要设置种子节点，各个节点通过gossip协议获得全局的哈希地图。 之后按照各自负责的区域，来处理数据请求并分片存储，以及用相应的副本保证高可用性。

新的节点加入

有新的Node T3加入到系统， T3初始化，根据自己的存储和计算 能力生成两个随机值T31和T32， 并上报给种子节点T1，也从T1 获得现有的hash ring的地图， 于是所有节点都获得新的地图

hash ring 的部分hash区间 映射到的节点发生变化， 对全局影响不大。 T12-T31之间的区间range1 原来是映射到T13, 需要从T13搬移到T31。另外一个虚拟节点那里也是类似的。

这体现了一致性哈希的好处，新增节点对数据搬移的开销小。

有节点离开

如下图，Node T2离开系统， 则需要先迁移数据。

• T11-T21之间的区间range3

原来是映射到T21, 需要从T21搬移 这区间的数据到T12

• T13-T22之间的区间range

原来是映射到T22, 需要从T22搬移到T32 后，移除T2的虚拟节点， 生成新的地图。

可以看出，迁移数据的代价也很小。这也体现了一致性哈希的好处，移除节点对数据搬移的开销小。

gossip协议

gossip协议很好懂，就是随机选择节点并传播通信交换数据，也很好实现，而且很快就可以模拟一个来了解这块的细节。

数据分片和副本

在这个数据分布的一致性哈希模型下，哈希区间自然的将数据分片存储。如果没有多副本，系统很难保证高可用性。

副本是保证数据高可用的保证，但也需要保证各个副本之间的一致性，总之是带来了更大的系统开销。

Dynamo副本的存储如规则下：

假设系统设置的副本数N=3，则T21需要存储的数据包括range1,range2和range3。

一致性哈希总结

• 学习一致性哈希
• 分布式存储的基础
• 多台机器存数据
• 数据分片可扩张
• 多个备份能可靠
• 每个节点一范围
• 真实节点多虚拟
• 均匀散落哈希环
• 手拉手围一个环
• 数据存取也不难
• 哈希取模来映射
• 指定节点来存储
• 这些数据的备份
• 在接下来的节点
• 机器宕机也不怕
• 数据转移且均匀
• 节点心跳来交流
• Gossip协议得全局

请求处理流程

DynamoDB系统是一个KV系统，客户端的请求很简单，基本是两类：PUT和GET。

PUT的时候考虑可用性和一致性的问题：

• 可用性就是说要多副本存储
• 一致性，数据一致性，多副本并发写能否保持一致

GET的时候也要考虑可用性和一致性的问题：

• 可用性就是说要选择一个可用的节点返回需要的数据？
• 一致性，数据一致性，如果有多个可用的数据，怎么合并解决冲突？

技术没有银弹，AC不可得兼。

可以发现所有的考量都是围绕可用性和一致性，下面详细说说这些过程和要考虑的一些问题。

put数据的处理流程？

客户端发送请求时，会选择协调模式。有两种：

• 客户端SDK协调
• 使用负载均衡服务器协调

不管是客户端协调还是负载均衡的协调，都要先选择一个节点作为主要负责put请求的逻辑，这个节点如果不可达，就换下一个可用的节点。

基本步骤：

• SDK获取集群metadata信息，选择一个处理请求的节点。
• 处理请求的节点计算hash(key),如图，key和值要存储到T13， 并且复制到T31和T12，所以处理节点将请求发给这三个节点，T1是处理节点，发送put指令给T13、T31和T12三个节点。
• 假设设置的W=2，则等待至少有一个replica复制成功才返回response给客户端。

当然在使用了Merkle Tree(后面会讲到这是优化一致性的一个数据结构)的情况下，会重新计算这棵树。

get数据的处理流程

同理，不管是客户端协调还是负载均衡的协调，都要先选择一个节点作为主要负责get的逻辑。

如图，这里使用负载均衡服务器

GET的时候，设置读R个节点可返回。

get(key=100)：

• 计算出key在T13，副本在T31和T12，处理节点T1给这些节点发送get指令
• 假设设置的R=2，则复制至少等这三个replica的其中两返回数据
• 根据策略合并结果返回response给客户端或直接返回全部让客户端去处理

向量时钟

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

一个向量时钟关联了一个对象的所有版本，可以通过它来判断对象的两个版本是否在并行的分支上，或者它们是否有因果关系。  如果对象的个时钟上的所有 counter 都小于它的第二个时钟上的 counter，那个 时钟就是第二的祖先，可以安全的删除；否则，这两个修改就是有冲突的，需要 reconciliation。

一个向量时钟就是一个 (node, counter) 列表。node表示处理数据的节点，如上面GET、PUT流程中说到的T1。

下图显示了一个场景：

在T1故障的时候，T2和T3可能都写入了数据，之后T1恢复解决冲突数据。

• D1、D2..表示vector clocks,[T2,1]表示T2处理的个版本

• 出现冲突写：D3([T1,2],[T2,1])和D4([T1,2],[T3,1])

• 再下次client get数据的时候，假设T1恢复，由T1处理冲突，得到的新的版本是3

• 冲突处理且删除D3([T1,2],[T2,1])和D4([T1,2],[T3,1])的数据，得到D5([T1,3],[T2,1],[t3,1])的数据

一致性检测的Merkle tree数据结构

为什么想知道replica data 数据是否一致？那是必须要有的，分布式系统至少保证起码的已一致性，也就是终一致性。

可能系统会有巡检，看看各副本是不是都一致。因为可能有些更新丢失了，或者磁盘内存硬件异常导致的数据错误。

以及一般的通用的数据处理过程

• put：写数据，同时复制数据到W个replcias
• get：读数据从R个replica中去读

Dynamo使用Merkle tree这种数据结构来比较副本之间的一致性，这是一种逆熵（anti entropy）的思想，如下图所示:

DynamoDB的每个节点 为每个数据分区都 维护了一个Merle Tree，通过Root的hash值就可以 验证同一片数据是否相同， 则不用比较所有数据。如果相等，则认为两个副本完全一样，如果不相等，则递归往下看哪里不相等，移动数据解决冲突。

分布式环境的故障检测和宕机处理

故障检测是各个节点之间gossip出来的，一个节点push数据的时候如果联不通就认为它peer不可用，如果大家就这个事情达成一致，则整体认为这个节点不可用，然后将数据转移，需要把上面的数据分片均匀分配给相邻的几个节点。

乐观多版本处理

上面已经提到了，是数据高可用性保证的处理过程中的一个思想。

相关文章