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那些事

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180525B1KOIJ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券