Hash算法那点事

关键时刻，第一时间送达！

我们引出一个问题：

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

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

我们研究一下哈希算法的分布性，即分布到每个Node的数据数目，算法的Python代码如下：

fromhashlibimportmd5

fromstructimportunpack_from

ITEMS =10000000

NODES =100

node_stat = [foriinrange(NODES)]

foriteminrange(ITEMS):

k = md5(str(item)).digest()

h = unpack_from(">I",k)[]

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(%0.2f%%)"% (_max,(_max - _ave) *100.0/ _ave))

print("Min: %d(%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后，数据项移动的情况：

Python代码如下：

fromhashlibimportmd5

fromstructimportunpack_from

ITEMS =10000000

NODES =100

NEW_NODES =101

node = [foriinrange(NODES)]

change =

foriteminrange(ITEMS):

k = md5(str(item)).digest()

h = unpack_from(">I",k)[]

n = h % NODES

n_new = h % NEW_NODES

ifn_new != n:

change +=1

print("Change: %d(%0.2f%%)"% (change,change *100.0/ ITEMS))

运行结果如下：

Change: 9900989(99.01%)

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

这显然是不能忍的。那么有什么设计方法呢？敬请期待一致性哈希算法。

来自：python那些事

程序员共读整理发布，转载请联系作者获得授权