成为作者

一致性 hash 的理解与实现

用户头像
dongge
关注
发布于: 2020 年 07 月 07 日
一致性hash的理解与实现

概述



在维基百科中，是这么定义的



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



引出



我们在上文中已经介绍了一致性Hash算法的基本优势，我们看到了该算法主要解决的问题是：当slot数发生变化时，能够尽量少的移动数据。那么，我们思考一下，普通的Hash算法是如何实现？又存在什么问题呢？

那么我们引出一个问题：



假设有1000w个数据项，100个存储节点，请设计一种算法合理地将他们存储在这些节点上。



看一看普通Hash算法的原理：



算法的核心计算如下



for item in range(ITEMS):
    k = md5(str(item)).digest()
    h = unpack_from(">I", k)[0]
    # 通过取余的方式进行映射
    n = h % NODES
    node_stat[n] += 1



具体的完整实现为

from hashlib import md5
from struct import unpack_from
ITEMS = 10000000
NODES = 100
node_stat = [0 for i in range(NODES)]
for item in range(ITEMS):
    k = md5(str(item).encode('utf-8')).digest()
    h = unpack_from(">I", k)[0]
    n = h % NODES
    node_stat[n] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print("Ave: %d" % _ave)
print("Max: %d\t(%0.2f%%)" % (_max, (_max - _ave) * 100.0 / _ave))
print("Min: %d\t(%0.2f%%)" % (_min, (_ave - _min) * 100.0 / _ave))



输出是这样的：



Ave: 100000 Max: 100695 (0.69%) Min: 99073 (0.93%)



从上述结果可以发现，普通的Hash算法均匀地将这些数据项打散到了这些节点上，并且分布最少和最多的存储节点数据项数目小于1%。之所以分布均匀，主要是依赖Hash算法（实现使用的MD5算法）能够比较随机的分布。



然而，我们看看存在一个问题，由于该算法使用节点数取余的方法，强依赖node的数目，因此，当是node数发生变化的时候，item所对应的node发生剧烈变化，而发生变化的成本就是我们需要在node数发生变化的时候，数据需要迁移，这对存储产品来说显然是不能忍的，我们观察一下增加node后，数据项移动的情况：



for item in range(ITEMS):
    k = md5(str(item)).digest()
    h = unpack_from(">I", k)[0]
    # 原映射结果
    n = h % NODES
    # 现映射结果
    n_new = h % NEW_NODES
    if n_new != n:
        change += 1



详细实现代码

from hashlib import md5
from struct import unpack_from
from bisect import bisect_left
ITEMS = 10000000
NODES = 100
NEW_NODES = 101
def _hash(value):
    k = md5(str(value).encode("utf-8")).digest()
    ha = unpack_from(">I", k)[0]
    return ha
ring = []
new_ring = []
for n in range(NODES):
    ring.append(_hash(n))
    ring.sort()
for n in range(NEW_NODES):
    new_ring.append(_hash(n))
    new_ring.sort()
change = 0
for item in range(ITEMS):
    h = _hash(item)
    n = ring[bisect_left(ring, h) % NODES]
    new_n = new_ring[bisect_left(new_ring, h) % NEW_NODES]
    if new_n != n:
        change += 1
print("Change: %d\t(%0.2f%%)" % (change, change * 100.0 / ITEMS))



输出是这样的：



Change: 58897 (0.59%)



翻译一下就是，如果有100个item，当增加一个node，之前99%的数据都需要重新移动。



这显然是不能忍的，普通哈希算法的问题我们已经发现了，如何对其进行改进呢？没错，我们的一致性哈希算法闪亮登场。



登场



我们上节介绍了普通Hash算法的劣势，即当node数发生变化（增加、移除）后，数据项会被重新“打散”，导致大部分数据项不能落到原来的节点上，从而导致大量数据需要迁移。



那么，一个亟待解决的问题就变成了：当node数发生变化时，如何保证尽量少引起迁移呢？即当增加或者删除节点时，对于大多数item，保证原来分配到的某个node，现在仍然应该分配到那个node，将数据迁移量的降到最低。



一致性Hash算法的原理是这样的：



for n in range(NODES):
    h = _hash(n)
    ring.append(h)
    ring.sort()
    hash2node[h] = n
for item in range(ITEMS):
    h = _hash(item)
    n = bisect_left(ring, h) % NODES
    node_stat[hash2node[ring[n]]] += 1



我们依然对其进行了实现，

from hashlib import md5
from struct import unpack_from
from bisect import bisect_left
ITEMS = 10000000
NODES = 100
node_stat = [0 for i in range(NODES)]
def _hash(value):
    k = md5(str(value)).encode("utf-8").digest()
    ha = unpack_from(">I", k)[0]
    return ha
ring = []
hash2node = {}
for n in range(NODES):
    h = _hash(n)
    ring.append(h)
    ring.sort()
    hash2node[h] = n
for item in range(ITEMS):
    h = _hash(item)
    n = bisect_left(ring, h) % NODES
    node_stat[hash2node[ring[n]]] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print("Ave: %d" % _ave)
print("Max: %d\t(%0.2f%%)" % (_max, (_max - _ave) * 100.0 / _ave))
print("Min: %d\t(%0.2f%%)" % (_min, (_ave - _min) * 100.0 / _ave))



并且观察了数据迁移的结果：



Change: 58897 (0.59%)



虽然一致性Hash算法解决了节点变化导致的数据迁移问题，但是，我们回过头来再看看数据项分布的均匀性，进行了一致性Hash算法的实现consist_hash.py：



Ave: 100000 Max: 596413 (496.41%) Min: 103 (99.90%)



这结果简直是简直了，确实非常结果差，分配的很不均匀。我们思考一下，一致性哈希算法分布不均匀的原因是什么？从最初的1000w个数据项经过一般的哈希算法的模拟来看，这些数据项“打散”后，是可以比较均匀分布的。但是引入一致性哈希算法后，为什么就不均匀呢？数据项本身的哈希值并未发生变化，变化的是判断数据项哈希应该落到哪个节点的算法变了。



因此，主要是因为这100个节点Hash后，在环上分布不均匀，导致了每个节点实际占据环上的区间大小不一造成的。

改进-虚节点



当我们将node进行哈希后，这些值并没有均匀地落在环上，因此，最终会导致，这些节点所管辖的范围并不均匀，最终导致了数据分布的不均匀。



核心算法如下：

for n in range(NODES):
    for v in range(VNODES):
        h = _hash(str(n) + str(v))
        # 构造ring
        ring.append(h)
        # 记录hash所对应节点
        hash2node[h] = n
ring.sort()
for item in range(ITEMS):
    h = _hash(str(item))
    # 搜索ring上最近的hash
    n = bisect_left(ring, h) % (NODES*VNODES)
    node_stat[hash2node[ring[n]]] += 1



详细实现：



rom hashlib import md5
from struct import unpack_from
from bisect import bisect_left
ITEMS = 10000000
NODES = 100
VNODES = 1000
node_stat = [0 for i in range(NODES)]
def _hash(value):
    k = md5(str(value).encode("utf-8")).digest()
    ha = unpack_from(">I", k)[0]
    return ha
ring = []
hash2node = {}
for n in range(NODES):
    for v in range(VNODES):
        h = _hash(str(n) + str(v))
        ring.append(h)
        hash2node[h] = n
ring.sort()
for item in range(ITEMS):
    h = _hash(str(item))
    n = bisect_left(ring, h) % (NODES*VNODES)
    node_stat[hash2node[ring[n]]] += 1
print(sum(node_stat), node_stat)
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print("Ave: %d" % _ave)
print("Max: %d\t(%0.2f%%)" % (_max, (_max - _ave) * 100.0 / _ave))
print("Min: %d\t(%0.2f%%)" % (_min, (_ave - _min) * 100.0 / _ave))



输出结果是这样的：



Ave: 100000 Max: 116902 (16.90%) Min: 9492 (90.51%)



因此，通过增加虚节点的方法，使得每个节点在环上所“管辖”更加均匀。这样就既保证了在节点变化时，尽可能小的影响数据分布的变化，而同时又保证了数据分布的均匀。也就是靠增加“节点数量”加强管辖区间的均匀。



for item in range(ITEMS):
    h = _hash(str(item))
    n = bisect_left(ring, h) % (NODES*VNODES)
    n2 = bisect_left(ring2, h) % (NODES2*VNODES)
    if hash2node[ring[n]] != hash2node2[ring2[n2]]:
        change += 1



同时，观察增加节点后数据变动情况，详细的代码：



100000

101000

Change: 104871 (1.05%)

另一种改进



然而，虚节点这种靠数量取胜的策略增加了存储这些虚节点信息所需要的空间。在OpenStack的Swift组件中，使用了一种比较特殊的方法来解决分布不均的问题，改进了这些数据分布的算法，将环上的空间均匀的映射到一个线性空间，这样，就保证分布的均匀性。

代码实现见part_consist_hash.py



for part in range(2 ** LOG_NODE):
    ring.append(part)
    part2node[part] = part % NODES
for item in range(ITEMS):
    h = _hash(item) >> PARTITION
    part = bisect_left(ring, h)
    n = part % NODES
    node_stat[n] += 1



Ave: 100000 Max: 157298 (57.30%) Min: 77405 (22.59%)



可以看到，数据分布是比较理想的。如果节点数刚好和分区数相等，理论上是可以均匀分布的。

for part in range(2 ** LOG_NODE):
    ring.append(part)
    part2node[part] = part % NODES
    part2node2[part] = part % NODES2
change = 0
for item in range(ITEMS):
    h = _hash(item) >> PARTITION
    p = bisect_left(ring, h)
    p2 = bisect_left(ring, h)
    n = part2node[p] % NODES
    n2 = part2node2[p] % NODES2
    if n2 != n:
        change += 1



而观察下增加节点后的数据移动比例，代码实现：



from hashlib import md5
from struct import unpack_from
from bisect import bisect_left
ITEMS = 10000000
NODES = 100
LOG_NODE = 7
MAX_POWER = 32
PARTITION = MAX_POWER - LOG_NODE
node_stat = [0 for i in range(NODES)]
def _hash(value):
    k = md5(str(value).encode("utf-8")).digest()
    ha = unpack_from(">I", k)[0]
    return ha
ring = []
part2node = {}
for part in range(2 ** LOG_NODE):
    ring.append(part)
    part2node[part] = part % NODES
for item in range(ITEMS):
    h = _hash(item) >> PARTITION
    part = bisect_left(ring, h)
    n = part % NODES
    node_stat[n] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print("Ave: %d" % _ave)
print("Max: %d\t(%0.2f%%)" % (_max, (_max - _ave) * 100.0 / _ave))
print("Min: %d\t(%0.2f%%)" % (_min, (_ave - _min) * 100.0 / _ave))



结果如下所示：



Change: 2190208 (21.90%)



可以看到，移动也是比较理想的。



参考链接：



深入云存储系统Swift核心组件：Ring实现原理剖析

Basic Hash Ring

Partition Ring vs. Hash Ring

https://github.com/Yikun/yikun.github.com/issues/53

https://github.com/Yikun/hashes



本地缓存



分布式对象缓存



Memcached分布式缓存访问模型



分布式

水平伸缩



集群 是 分布式的子集 一组提供同样功能的程序构建的分布式系统。



负载均衡的选择，技术讨论的关键点。集群增加新服务器怎么加？



Memcached 分布式缓存访问模型



划线
评论
复制
发布于: 2020 年 07 月 07 日 阅读数: 31
用户头像

dongge

关注

还未添加个人签名 2017.10.19 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2020, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 |  京 ICP 备 16027448 号 - 5 京公网安备 京公网安备 11010502039052号
一致性hash的理解与实现