前言

一致性哈希算法的设计目标是为了解决因特网中的热点问题,现在也被广泛应用在分布式系统中。

比如针对负载均衡问题,对hash值取模的算法扩展性差,当增加或者减少服务器时,映射关系可能会出现问题,采用一致性hash算法,就能较好的解决该问题。

Hash值取模算法存在的问题

比如,我们有海量的图片存储在服务器上,假如,现在有4台服务器,我们可以根据图片名称,采用hash算法,决定图片存储在哪台服务器

如果现在需要增加服务器,那么存取图片的服务器的算法就会发生改变,比如增加一台服务器后,算法变为hash(a.jpg)/5,这时候计算结果不一定还是2,那么图片的位置就要发生改变。同理,减少服务器的话,也会存在相同问题。而且,所有的服务器都会受到影响。

一致性Hash算法

一致性Hash算法将哈希值映射的空间表示成一个虚拟圆环,一般可以设置映射值的范围是0----232-1,也就是说,我们得到的hash值要对232取模。该hash环可表示如下:

假如我们有四台服务器,我们可以选择服务器的ip或主机名作为关键字进行哈希,然后取模,每台机器就能在hash环上确定固定位置。如下图所示:

例如有Object A、Object B、Object C、Object D四个数据,经过哈希运算及取模后,在环空间上的位置如下图所示:

从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。也就是说Object A定位到Node A,Object B定位到Node B,Object C定位到Node C,Object D定位到Node D。

如果Node C这台服务器出现问题宕机,那么Objcet C定位到Node D这台服务器,所以当某台服务器出问题时,只会对顺时针方向的前一台机器产生影响,本例中,只会对Node D有影响。

同理,如果增加一台服务器Node X,计算后,定位到如下图所示位置:

那么Object C就会定位到Node X,这种情况,只会对顺时针方向的Node C产生影响,不会影响其他服务器。

一致性Hash的缺点

当服务器节点比较少的时候会出现一致性hash算法倾斜的问题(大部分数据存在一台服务器上)。在不改变服务器节点个数的前提下,一般解决方案是增加虚拟节点(即对每一个服务器根据一致性hash算法计算多个值,每个计算结果在环上定位一个服务节点),在定位数据时,就可以根据虚拟节点,定位到实际服务器。

总结

一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。