一致性hash的理解

  • 内容
  • 评论
  • 相关

一。

以前的%算法属于硬hash。在机器发生增减的时候,会有重新hash的问题。

二。Memcache的客户端引入了另一种hash算法:一致性hash:

wps_clip_image-21476

1.映射

1)将对象与Cache使用同一hash算法映射到了同一个0~2的32次-1的环中(假设环的首尾相连)

2)将环中的对象顺时针映射到最近的CACHE,这样的映射方式可以保证Cache是唯一而确定的。

2.hash平衡性。

hash的一个重要指标就是平衡性。用来将对象均衡的映射到所有的目标中。

如果环中Object1映射到了cache1,object2~objectN映射到了cache2上,通常将对象->节点的映射改成对象->虚拟节点的方式解决。“虚拟节点”(virtual node)是实际节点在hash空间的复制品(replica),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在hash空间中以hash值排列。

下图是引入虚拟节点的效果图:

wps_clip_image-7421

下图是调整后的映射关系图:

wps_clip_image-3606

3.虚拟节点hash值的算法:

“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设cache A的IP地址为192.168.99.11原来的cache的hash值:hash(“192.168.99.11”),引入虚拟节点的hash值:hash(“192.168.99.11#1”);  // cache A1 ,hash(“192.168.99.11#2”);  // cache A2