一致性hash算法

假如我们有3台缓存服务器，缓存的 key 会根据hashcode散列分布在3台服务器上，我们来看看常规的算法是怎样的，我们假定缓存的key的hash值是10

hash = 缓存key的hash值
machineNum = 缓存服务器数

 hash % machineNum  = 缓存服务器编号；
10 % 3 = 1；

这种算法的问题在于缓存服务器的新增和减少都会导致同一个hash值计算出来的缓存服务器编号不一样，现在我们假定有4台缓存服务器

 hash % machineNum  = 缓存服务器编号；
10 % 4 = 2；

这种缓存服务器编号的改变就会导致缓存失效，当我们新增或者关闭一台缓存服务器就会导致大范围缓存失效导致雪崩效应

而一致性hash算法解决了部分服务下线导致的大量缓存失效问题，首先我们定义一个2的32次方的hash环，数据结构上可理解为首尾相连的链表, 至于为什么是2的32次方，对应的是hashcode也是2的32次方

image.png

然后3台缓存服务器根据唯一识别码(可以是服务器ip或者服务器服务名)计算出槽位

 缓存服务器唯一识别码 % 2^32 = 槽位Index

这样3台服务器就会落在对应的槽位上

image.png

现在我们要缓存的a.jpg的hash值是10，我们用同样的算法计算这个key所在的槽位

 hash % 2^32 = 槽位Index；
10 % 2^32 = 10；

image.png

这样a.jpg也落在了hash环上，但是我们要怎么判断a.jpg由哪台服务器缓存呢，我们只要顺时针查找，遇到的第一个服务器节点就是我们要缓存的服务器，如图， B缓存服务器就是我们缓存a.jpg的服务器

image.png

假如我们还有一个b.jpg 要缓存，缓存结果如下， b.jpg缓存到A缓存服务器中

image.png

然后这时B缓存服务器下线了， a.jpg 顺时针查找到C缓存服务器，a.jpg 因为服务器变了导致缓存失效，但是我们来看看b.jpg，b.jpg顺时针查找还是找到A缓存服务器，b.jpg 缓存保持正常

image.png

这就是一致性hash只会导致部分hash失效而保留了大部分缓存正常使用

hash倾斜

如图，假如服务器分布不均匀，呈现一边倒，这样假如A服务器下线，同样会导致大量缓存失效，这样就体现不出一致性hash的作用

image.png

我们可以通过虚拟节点来解决这个问题，假如A服务器的ip地址是192.168.0.1，我们可以弄多个不同唯一识别码都指向192.168.0.1， 增加虚拟节点后使服务器分布更均匀

image.png

更多demo请关注

springboot demo实战项目
java 脑洞
java 面试宝典
开源工具

公众号

五分钟了解前沿技术，大数据，微服务，区域链，提供java前沿技术干货，独立游戏制作技术分享

五分钟技术

如果这篇文章对你有帮助请给个star

image.png