一致性hash算法也是一种hash算法,目的是为了解决分布式缓存问题。在添加或移除服务器的时候,能尽可能的保证已存在的请求和处理请求的服务器之间的映射关系。一致性hash算法解决了简单hash算法在分布式hash表中存在的动态伸缩的问题。

假设场景

公司有3台缓存服务器,用来存储用户头像的图片,编号0,1,2。现在有9万个用户头像需要存储,现在希望能够均匀的缓存到3台服务器上,也就是每台服务器缓存3万个头像,平衡每个服务器的负载压力。

方案一

没有任何规律,将图片平均的缓存到3台服务器上。

引发的问题:在查询的时候,就没有办法知道所需数据落在哪台服务器,每次查询都要遍历所有服务器查询,效率低速度慢。

方案二

  1. 以头像图片的名字作为key进行缓存,假设图片的名字不重复。
  2. 对图片的名字做hash运算,再对服务器的数量进行取模,得到的结果就是这张图片要缓存的服务器编号。(本场景里,对图片名字做hash运算后,对3进行取模mod,得到的结果一定是0,1,2)
  3. 查询时,只要再次对图片的名字hash取模后,就能知道缓存在哪台服务器上,就不需要遍历所有服务器了。

存在的问题:这样做看似可以均匀的缓存在每台服务器上,查询也不需要遍历服务器。但是,如果服务器的数据发生了变化,若增加一台或者减少一台,那么用同样的算法进行计算后,得到的结果就不一样了。比如,hash运算后对4取模,结果就是0,1,2,3了,这样就跟图片和服务器的映射关系就乱了。

这个时候,一致性hash算法就出现了。

一致性hash算法

一致性hash算法也是hash取模运算,只不过,它不是根据上述的服务器数量进行取模,而是对232进行取模。(因为IPv4是32位的,它的最大数量就是232,这样就能保证对ip地址进行取模时不会重复,能够对应到hash环上的正数。)

由232个点组成的圆环称为hash环

计算公式:hash(服务器的ip地址) % 232

计算的结果一定是0到232-1之间的一个整数。

结合场景解释一致性hash算法

假设3台服务器被映射到如下的位置,红点为图片的位置

问题1:这个图片应该被缓存到哪个服务器上呢?

原则:按照红点在的位置,顺时针遇到的第一个服务器就是它的存储服务器,即服务器A。

问题2:如果服务器不是均匀的分布在hash环上,那么每个服务器缓存的数量不是不均匀了吗?

服务器不均匀分布在hash环上

如果是上图这样的情况,那么服务器C肯定是被分配到的图片是最多的。

hash环倾斜问题

理想状态下,是均匀的分布在hash环上,但是事实往往不会是理想状态的。

虚拟节点

虚拟节点就是实际节点(实际物理服务器)在hash环上的复制品,一个实际节点可以对应几个虚拟节点。

虚拟节点

ABC三个服务器都增加一个虚拟节点,也可以增加更多的虚拟节点,这样缓存的分布就会均匀多了,减少了hash倾斜环的问题。一般可以根据服务器ip加编号的方式给每个节点计算虚拟节点的位置(nodeA#1,nodeA#2,nodeA#3)。

一致性hash算法的优点

假设服务器B故障了,被移除了

这样根据顺时针原则,1还是被缓存到服务器A,3和4被缓存到服务器C都没有发生变化,但是2会被计算出来是缓存到服务器C,实际是缓存在服务器B。而如果是简单的hash算法,很可能,1,2,3,4被分配到的缓存服务器完全发生变化。这就是一致性hash算法的优点。

  1. 使用简单hash算法,服务器数量变化时,缓存全部失效,会出现缓存雪崩;
  2. 使用一致性hash算法,服务器数量变化时,缓存部分失效,没失效的缓存还是可以抗住大部分访问压力,失效的部分访问DB,而不至于缓存全部失效,导致瞬间压力全部落在DB上,可能打崩DB。