一致性哈希算法的理解与实践

[Yikun]

0. 概述

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

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

1. 引出

我们在上文中已经介绍了一致性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

具体的完整实现请参考normal_hash.py，输出是这样的：

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

详细实现代码在normal_hash_add.py输出是这样的：

Change: 9900989 (99.01%)

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

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

2. 登场

我们上节介绍了普通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

我们依然对其进行了实现consist_hash_add.py，并且观察了数据迁移的结果：

Change: 58897 (0.59%)

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

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

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

3. 改进-虚节点

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

详细实现请见virtual_consist_hash.py

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

输出结果是这样的：

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

因此，通过增加虚节点的方法，使得每个节点在环上所“管辖”更加均匀。这样就既保证了在节点变化时，尽可能小的影响数据分布的变化，而同时又保证了数据分布的均匀。也就是靠增加“节点数量”加强管辖区间的均匀。 同时，观察增加节点后数据变动情况，详细的代码请见virtual_consist_hash_add.py：

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%)

3. 另一种改进

然而，虚节点这种靠数量取胜的策略增加了存储这些虚节点信息所需要的空间。在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%)

可以看到，数据分布是比较理想的。如果节点数刚好和分区数相等，理论上是可以均匀分布的。而观察下增加节点后的数据移动比例，代码实现见part_consist_hash_add.py

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

结果如下所示：

Change: 2190208 (21.90%)

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

参考链接：

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

[zchen36]

多谢总结～ 最后一个链接好像应该是part_consist_hash_add.py

[coderlu]

讲得很到位

[wangxiyuan]

Cool

[zhangxiaojie]

分析的很透彻啊，不过最后一个不是很理解：

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

这里 part2node[part] = part % NODES 最后又是取 n = part2node[p] % NODES 那是不是没有必要存part2node[part] ， 直接可以取 n = part % NODES呢？

另外，这个方案似乎会导致删除一个节点，这个节点的所有压力都会重定向到这个节点前面的那一个节点里。

[Yikun]

@zchen36 是的，感谢指正，已经修改

[Yikun]

@zhangxiaojie

那是不是没有必要存part2node[part] ， 直接可以取 n = part % NODES呢？

是的，这块只是为了和上文其他的实现保持一致。先存映射，然后映射其实不用取余了。

另外，这个方案似乎会导致删除一个节点，这个节点的所有压力都会重定向到这个节点前面的那一个节点里。

没错，普通节点的负载压力在1/N，这个会变为2/N，N比较大的时候就可以忽略了。一般情况下，某个节点挂掉，后续会再up，就可以恢复了。最后一种，相对来说实现更简单，也保证了影响最小。

[decode-life]

文中未把具体的虚节点，及另一种解决分布不均的方法详细说明，感觉只是在论证分布性，全面性不够

[my-yangming]

大佬画图的软件用的啥呀

[lleiyyang]

你的代码貌似有问题啊， 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()

1：每次for循环都要sort吗？ 2：不应该sort吧，ring和new_ring的下标是有含义有意义的，具体代表着那台实体node，你是通过item做hash之后和ring[]做比较看这个应该存放到那台实体，而你一旦排序就会打乱下标。

[Yikun]

@lleiyyang 写这个的时间比较旧了，我刚看了下，如果没记错的话：

1. 每次for循环都要sort吗？没必要，在for外面循环就好了，只要保证最终的环是有序的就好（这个举例只是为了好说明，其实也有其他的方式去造这个环，根本目的是通过某种计算，让数据每次落到同一节点上）。

2. 在这个例子中，Sort是应该的，因为需要对节点的hash值做排序，这样才能用类似bisect_left的方法，去判断新来的数据落到哪个区间，而这个环是提前生成好的。 在真实环境中，环确定后，同样的数据每次还是落到同样的区间，在增加节点的时候，有2种方法： a. 要么通过某种算法让新数据落到新节点，老数据不能变化。 b. 要么需要根据新的规则进行数据迁移，让所有数据适配新的节点分布。

[Yikun]

@my-yangming omnigraffle @decode-life 感谢，写文只是记录了我认为有疑惑的地方，所以，有其他详细想法欢迎补充~

[lleiyyang]

该进了一下，请大佬指导一下

!/usr/bin/env python

-- coding: utf-8 --

一致性hash计算失效率

from future import division from md5 import * import struct node = 100#原来的节点0-99 addnode = 100#增加的节点名字--100 item = 10000000

hashnode=[] new_hashnode=[]#hash(node)--->node的映射 def _hash(key): k = md5(str(key)).digest() h = struct.unpack_from(">I",k)[0] return h

for i in range(node): hashnode.append(_hash(i))

hashnode.sort() addhash=_hash(addnode) fronthash=max(hashnode)#存在环上逆时钟距离addhash最近的hash值 for i in hashnode: if addhash >i: fronthash = i

分情况： if(fronthash > addhash) 失效节点的hash满足：hash>fronthash 或者 hash<addhash

if(addhasn>fronthash) 满足：hash>fronthash && hash <addhash

计算失效率

num = 0 if fronthash > addhash : for i in range(item): hashi = _hash(i) if(hashi>fronthash or hashi<addhash): num+=1 elif addhash > fronthash: for i in range(item): hashi = _hash(i) if(hashi>fronthash and hashi<addhash): num+=1

print("失效率为：",num/item)

[lleiyyang]

排序绝对是有问题的，第一次排序没毛病，但是增加节点之后又排序这就有问题了 做个假设：ring[]: 10,20,30,40,50 new_ring 10 20 30 35 40 50 对ring来说 本来40 和下标2对应，也就意味这hash之后的item如果在(30,40)都会存放在下标2这里 但是你对new_ring 一排序就会打乱对应关系，40和3对应，也就是说在（35，40）之间的hash值都会去3里面取？？？这肯定有问题啊，难道35-40之间也失效了吗？？？

[ZhengZhenyu]

神仙打架 不明觉厉

[bzhaoopenstack]

四仙群架， 毁天灭地

[Yikun]

@lleiyyang 没错，我理解你的意思，新增的节点只需要重新迁移箭头区域的数据到新节点：

另外，我也明白你的意思了。你的意思是下标排序后变化了。我举个例子说明下：

from bisect import bisect_left
ring = [1,2,3,4]
new_ring = [1,2,3,3.5,4]

data = [0.5, 1.5, 2.5, 3.5, 4.5]

# 新旧下标
for x in data:
    print x, bisect_left(ring, x), bisect_left(new_ring, x)

#  新旧下标对应的ring上的值
for x in data:
    print x, ring[bisect_left(ring, x) % 4], new_ring[bisect_left(new_ring, x) % 5]

问题就出在bisect_left(new_ring, 4.5)和bisect_left(ring, 4.5)的差异上，这个其实不是sort的问题，是最后下标转换的问题，我们需要比较的是新旧下标对应的ring上的值而不是新旧下标，即：

ring[bisect_left(ring, h) % len(ring)]
new_ring[bisect_left(new_ring, h) % len(new_ring)]

所以实际比较的代码是：

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

对应的结果是：

Change: 58897 (0.59%)

已更新文章。