什么是一致性hash算法,有什么用处?

一致性hash算法,是集群存储的一种实现方式。

一个经典问题:3万张图片,需要相对均匀的存储到3台服务器中去,使每台服务器存储大约1万张图片,如何实现?
image

  1. 将30000张图片按文件名按照一定算法将其转换成数字。
    js实现:
    const hash = (str) => {
    return +Array.prototype.map.call(str, (s) => s.charCodeAt()).join('')
    }
    
    每张图片文件名,都能够通过hash方法转换成数字,比如转换之前是a.png,b.png,c.png,转换为:9746112110103,9846112110103,9946112110103。
    现在怎么把这三张图片,存储到3台服务器中去呢?
    可以对这3张图片的hash分别对服务器数量取余,比如a.png:9746112110103 % 3 -> 0,b.png: 9846112110103 % 3 -> 1, c.png: 9946112110103 % 3 -> 2
    再将三张图片,依次存入三台服务器中:
    image
    这样,每次访问图片的时候,就可以根据图片的文件名hash,来计算出这张图片存在哪一台服务器中,io读取的时候,就可以直接读取目标服务器的文件,而不必去遍历所有服务器,节约了开销。这样就简单的实现了分布存储
    但是问题来了,如果3台并不能满足我们的需求时那么应该怎么做?肯定是增加几台服务器就可以了,假设我们增加1台服务器,服务器的数量由3变成了4,此时仍然用上述方法对同一张图片进行缓存,那么这张图片所在的服务器的编号必定是与原来的3台服务器所在的 编号是不同的,因为除数3变成了4,被除数不变的情况下,余数肯定不同,这情况带来的结果就是当服务器数量变动时,所有和缓存的位置都要发生改变,也就是说缓存服务器数量发生改变时,所有缓存数据在一定时间是失效的,当应用无法从缓存中和获取数据时,则会向后端服务器请求数据,同理,如果3台缓存服务器中突然有一台出现了故障,,无法进行缓存数据,那么需要移除故障机器,但是如果移除了一台缓存服务器后,数量从3变成了2,如果想访问有一张图片,这张图片缓存为位置必定发生改变,以前缓存的图片也会失去缓存的作用和意义,由于大量缓存在同一时间失效,造成了缓存的雪崩(血崩),后端服务器将会承担所有巨大压力,会导致整个系统可能会被压垮,所以为了避免这类情况的发生,一致性hash算法诞生了!

其实一致性hash算法也是取模运算,只是,上面描述的取模算法是对服务器数量进行取模,而一致性hash是对2^32取模.

首先把2^32个数字组成一个圆:
image
顺时针排列。然后再将3台服务器的ip地址的hash对2^32取余,余数是0-2^32之间的任意数,将其映射到圆上,会在圆上得到三个点与之对应:
image
然后,我们将图片也取余2^32,得到0-2^32之间的任意数,也对应着hash环上的一点。
人为规定,从图片出发,沿着hash环顺时针寻找,遇到的第一台服务器,就将图片存在这台服务器中:

image

这样做的好处是,由于被缓存对象与服务器hash后的值都是固定的,所以服务器不变的情况下,一张图片必定会被缓存到固定的服务器上,那么,当下次访问这张图片时,只要再次使用相同的算法进行计算,即可算出这张图片被缓存在那个服务器上,直接去对应的服务器上查找即可。

那么一致性hash环怎么抵抗雪崩呢?

假如现在有3张图片缓存情况如下:
image
可见,图片1缓存在server2中,图片2,3缓存在server3中,现在假设,server2崩溃了,显然,server2中的图片1就不存在了,但是图片2,3仍然存在server3中,不会因为某一节点的崩溃而存储位置发生变化,这就是一致性hash的优势,可以最小程度的减少集群节点服务器崩溃带来的灾难。