一致性哈希算法

背景

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

算法思路

  • 将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下:
一致性哈希算法
  • 整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到232-1,也就是说0点左侧的第一个点代表232-1, 0和232-1在零点中方向重合,我们把这个由232个点组成的圆环称为Hash环。

  • 下一步将各个服务器使用Hash进行一个哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置

一致性哈希算法
  • 接下来使用如下算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器!

    例如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:

    一致性哈希算法
  • 根据一致性Hash算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

负载均衡

普通哈希

扩缩容后,命中率大大降低,带来了缓存穿透的问题。

倍增扩容

成倍扩容能有效解决扩容后带来的缓存穿透问题,但这样做会造成资源的浪费。

一致性哈希

扩缩容后,只会影响其中的一个节点的数据,命中率只降低1/N。

数据倾斜

一致性哈希算法要得到较好的效果,取决于各个实体节点在哈希环的分布情况,是否能分散。

为了解决数据很可能分布不均匀的情况,对一致性哈希算法,提出了改进,引入了虚拟节点的,可以设置一个哈希环中存在多少个虚拟节点,然后将虚拟节点映射到实体节点,从而解决数据分布吧均衡的问题。

不过,也带来了如下问题:

  1. 虚拟节点映射到实体节点。
  2. 节点过多,性能降低。

节点hash值计算方法:

真实节点:hashcode(keyA)、hashcode(keyB)

虚拟节点:hashcode(keyA#1)、hashcode(keyB#1) 、hashcode(keyA#2)、hashcode(keyB#2)

优缺点

优点:分布式扩容、缩容能有效避免缓存穿透的问题。

缺点:实现复杂,性能低下,运维管理复杂。

负载均衡算法选择

如果服务是无状态的,选择:轮循、加权轮循、随机、加权随机算法。

如果服务是有状态的,选择:一致性哈希算法。

目前来说,一致性哈希算法有点被滥用的趋势。

上一篇:粤嵌科技毕业实习Day7


下一篇:【Java-笔试面试】hashCode() 与 equals () 详解