一致性哈希在维基百科中，是这么定义的

一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

​这一篇借助这个主题，顺便来了解下Dynamo在一致性hash上的应用，熟悉其应用场景以及原理。

一、dynamo特点介绍

dynamo 的中文意思是发电机，意思是像发电机一样，提供源源不断的服务。它是Amazon提供的一个分布式Key/Value存储的NoSQL 数据库，完全托管在云端，支持文档和键值存储模型。

其主要特点是如下:

特点描述数据模型灵活schema freee，Nosql必然支持的，没什么说的效率（速度）数据采用SSD来进行存储，服务端平均延迟通常不超过十毫秒。随着数据量增多，DynamoDB 会使用自动分区和 SSD 技术来满足吞吐量需求，并针对任意规模的数据库提供低延迟。高可用Dynamo 为了达到高可用性和持久性，防止由于节点宕机故障或者数据丢失，将同一份数据在协调者和随后的 N-1 个节点上备份了多次高度可扩展dynamo 不会对数据规模大小进行限制，会把数据分布到各个机器上，只需为其指定目标使用率，容量便会自动根据应用程序请求数量的增加或减少而扩展或缩减，无需担心数据库的缩扩容问题完全托管无需担心数据库的管理，比如管理集群，软硬件的配置与预设以及监控、部署，省去开发者部署、监控、维护数据库的环境去中心化节点对称性、去中心化：系统采用P2P架构，每个节点都是对等的、有相同的责任ACID属性为了获得更为灵活的可水平扩展的数据模型，NoSQL 数据库通常会放弃传统关系数据库管理系统 (RDBMS) 的部分 ACID 属性，而且在保证ACID的数据存储时往往有很差的可用性。Dynamo的目标应用程序是高可用性，弱一致性(ACID中的”C”)。

我觉得dynamo最吸引人的地方就是高度扩展性，以及完全托管，这个会节省开发人员大量的运维工作。

当然了不好的地方也是它的数据一致性要求不是很高，在99.94% 左右，而且遇到了不一致问题，都抛给了上层来解决，类似于git merge操作，如果对一致性要求比较高的话，这个还是挺麻烦的，当然了这个主要看应用的选型需求了，后期再详细介绍。

dynamo的高度扩展性，就是采用了一致性hash的原理来实现，我们来着重分析一下，它是如何采用采用一致性hash而达到高扩展性的。

二、数据分布

在dynamo 中创建table的时候，必须要指定一个分区键（partition），分区键可以用hash值，也可以用户自己指定，做唯一主键的时候，不能有重复。

对于刚接触Dynamo的时候不是很明白要如何应用分区键。那么为何要用分区键？

我们回顾一下，一致性hash的实现原理，一致性hash是把数据均匀的映射到一个线性空间，以保证分配的均匀性，以及提高数据的单调性。同时为了减少由于节点数过少导致移动过多的数据项，又加入了虚拟节点。如下:

引入了“虚拟节点”后，映射关系就从【object--->node】转换成了【object--->virtual node---> node】。查询object所在node的映射关系如下图所示。

以上virtual node我们就可以称为 partition，当增加新的node服务器的时候，由于virtual node没有变化，数据的hash值也是固定不变的，因此只需要处理一下，virtual node和node的重分配，这个对数据迁移的影响是最小的。

我们看下代码实现:

我们假设有256个node(2^8)，有partition数4096(2^12)。由于MD5码是32位的，使用PARTITION_SHIFT(等于32- PARTITION_POWER)将数据项的MD5哈希值映射到partition的2^12的空间中。此处引入了partition power 。

ITEMS = 10000000
NODES = 256
PARTITION_POWER = 12
PARTITION_SHIFT = 32
PARTITION = PARTITION_SHIFT - PARTITION_POWER
node_stat = [0 for i in range(NODES)]
#获取hash值
def _hash(value):
 k = md5(str(value)).digest()
 ha = unpack_from(">I", k)[0]
 return ha
ring = []
part2node = {}
#虚拟节点和node节点做映射关系
for part in range(2 ** PARTITION_POWER):
 ring.append(part)
 part2node[part] = part % NODES
for item in range(ITEMS):
 #把32位的hash值映射到12位的空间中
 h = _hash(item) >> PARTITION
 #查找最近的partition
 partition = bisect_left(ring, h)
 n = partition % NODES
 node_stat[n] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)

这个就是为何dynamo在创建表的时候要指定分区键partition,因为要保证其数据的高扩展性，需要把数据分配到不同的node数据服务器上。

有了partition，一张表的数据，就可以分散到不同的node上，同时在数据进行扩容增加node的时候，因为数据的partition并没有发生变化，只是partition对应的node映射发生了变化，对数据的迁移影响是最小的。

三、数据冗余

在上述模型中，虽然解决的数据的扩展性问题，但数据的高可用问题，并没有去达成，每个node节点的数据都是单一的，如果这个节点出故障了，数据怎么处理？

为了让系统达到高可用性和持久性，防止由于节点宕机故障或而造成数据丢失，Dynamo中的数据被复制成N份存于多台主机中。

除了本地存储其范围内的每个结点将同一份数据在协调者和随后的 N-1 个节点上备份了多次，N 是一个可以配置的值，默认情况下是3，其理论依据主要来源于NWR策略。

NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。每个字母的涵义如下：

N：同一份数据备份的份数

W：是更新一个数据对象的时候需要确保成功更新的份数

R：读取一个数据需要读取的最少节点（备份）的份数

只要满足W+R > N，就可以保证当存在不超过一台机器故障的时候，至少能读到一份有效的数据。如果应用重视读效率，可以设置W=N，R=1; 如果应用需要在读/写之间权衡，一般可设置成N=3, W=2, R=2。Dynamo推荐使用322的组合。

我们在这里称为Replica，在分布式系统中，数据的单点是不允许存在的，即线上正常存在的Replica数量是1的情况是非常危险的。

因为一旦这个Replica再次错误，就可能发生数据的永久性错误。假如我们把N设置成为2，那么，只要有一个存储节点发生损坏，就会有单点的存在。所以N必须大于2。N约高，系统的维护和整体成本就越高。工业界通常把N设置为3。

比如上图中，黄色区域的值会存储在三个节点 A、B 和 C 中，蓝色的区域会被 D、E、F 三个节点处理，负责存储某一个特定键值对的节点列表叫做偏好列表（preference list），因为虚拟节点在环中会随机存在，为了保证出现节点故障时不会影响可用性和持久性，偏好列表中的全部节点必须都为不同的物理节点。

我们来看实现方式

我们在上述代码中引入replica，数量设置为3，其中 node_ids记录的是3个replica存放的node id。part2node[part]是根据partition id 找到对应的node id，也是分区和node节点的映射关系。

ITEMS = 10000000
NODES = 100
PARTITION_POWER = 12
PARTITION_SHIFT = 32
PARTITION = PARTITION_SHIFT - PARTITION_POWER
PARTITION_MAX =2**PARTITION_POWER-1
REPLICAS = 3
node_stat = [0 for i in range(NODES)]
def _hash(value):
 k = md5(str(value)).digest()
 ha = unpack_from(">I", k)[0]
 return ha
ring = []
part2node = {}
#虚拟节点和node节点做映射关系
for part in range(2 ** PARTITION_POWER):
 ring.append(part)
 part2node[part] = part % NODES
for item in range(ITEMS):
 #把32位的hash值映射到12位的空间中
 h = _hash(item) >> PARTITION
 part = bisect_left(ring, h)
 node_ids = [part2node[part]]
 node_stat[node_ids[0]] += 1
#数据replica处理，一份数据存放临近的3个物理节点
 for replica in xrange(1, REPLICAS):
 while part2node[part] in node_ids:
 part += 1
 if part > PARTITION_MAX:
 part = 0
 node_ids.append(part2node[part])
 node_stat[node_ids[-1]] += 1
_ave = ITEMS / NODES* REPLICAS
_max = max(node_stat)
_min = min(node_stat)

四、数据一致性

1、冲突

由于加入了replica，特别是NWR 是322的情况下，一个读操作，必须得等待2个节点的数据返回对应结果，才认为当前请求结束了，也就是说会请求时间会受最慢节点的影响，写的情况也是相同。唯一的不同是，发现节点中数据出现了冲突，会对冲突尝试进行解决并将结果重新写回对应的节点。

Dynamo对数据的一致性要求没有那么高，会出现数据不一致情况，当然了多数情况下，Dynamo 都不会出现这种情况，并且即便出现了，Dynamo 能够确保一旦数据之间发生了冲突不会丢失，但是可能会有已被删除的数据重新出现的问题。

针对这种情况，Dynamo提供了向量时钟来解决，每一个对象版本中都存在一个或者多个向量时钟，每次更新数据的时候，都会更新向量时钟的版本。

如果待更新数据的向量钟的每一项都不小于本地向量钟，那么数据无冲突，新的值可以被接受。当客户端再次 请求时就会发现数据出现了冲突，由于 Dynamo 无法根据向量时钟自动解决，所以它需要客户端合并不同的数据版本。就类似git 的merge 操作，把问题抛给了调用方来解决。

2、故障

在一个节点出现临时性故障时，数据会自动进入列表中的下一个节点进行写操作，并标记为handoff数据，如果在指定的时间内该机器重新提供服务，则其他机器会通过Gossip协议发现，并将暂存的数据回传给该临时性故障的机器。

如果超时了一定的间隔，该机器还是处理宕机状态，则会认为是永久下线了，此时需要从其它副本同步数据。为了更快地检测副本之间的不一致性，并减少传输的数据量，Dynamo采用了Merkle树。Merkle树是一个哈希树，其叶子结点是各个key的哈希值，树中较高的父结点均为其各自孩子节点的哈希，通过这种方式构建的树形结构能够保证整棵树不会被篡改，任何的改动都能被立刻发现。如此检测快，数据传送的量也小，同步时只同步从根结点到叶子的所有节点值均不相同的文件。

引用:

https://draveness.me/dynamo

http://www.cnblogs.com/yuxc/archive/2012/06/22/2558312.html

end