一致性哈希在维基百科中,是这么定义的
这一篇借助这个主题,顺便来了解下Dynamo在一致性hash上的应用,熟悉其应用场景以及原理。
一、dynamo特点介绍
dynamo 的中文意思是发电机,意思是像发电机一样,提供源源不断的服务。它是Amazon提供的一个分布式Key/Value存储的NoSQL 数据库,完全托管在云端,支持文档和键值存储模型。
其主要特点是如下:
我觉得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映射发生了变化,对数据的迁移影响是最小的。
三、数据冗余
为了让系统达到高可用性和持久性,防止由于节点宕机故障或而造成数据丢失,Dynamo中的数据被复制成N份存于多台主机中。
除了本地存储其范围内的每个结点将同一份数据在协调者和随后的 N-1 个节点上备份了多次,N 是一个可以配置的值,默认情况下是3,其理论依据主要来源于NWR策略。
NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中,就应用NWR来控制一致性。每个字母的涵义如下:
我们在这里称为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的哈希值,树中较高的父结点均为其各自孩子节点的哈希,通过这种方式构建的树形结构能够保证整棵树不会被篡改,任何的改动都能被立刻发现。如此检测快,数据传送的量也小,同步时只同步从根结点到叶子的所有节点值均不相同的文件。
引用:
关注游戏研发和个人成长,致力于游戏技术社区的推进,扫描二维码,关注更多原创文章。