图解一致性hash算法

在单机服务器状态下所有的对象都会存储到一台服务器上，如果要存储的对象很多，一台服务器的硬盘肯定存储不下，而且也会给资源的查找增加一定的时间，
所以为了减低服务器的压力，提高响应速度，服务器集群便诞生了。但是请求分配出现了问题。怎么分配才能比较均匀？谈到均匀立马就会想到HashMap处理节点的方式：拉链法
请求过来的时候通过hash函数计算的出hash值，将hash值%服务器节点的数量，那么就会将请求比较均匀的分布到每台服务器上。
比如说有四台服务器节点，有20个对象，计算后，请求的分配结果如下：

服务器的节点数为4，对象有20个
但是如果服务器的节点发生变化后，会使得很多缓存都不会命中，原先缓存在缓存中的数据由于取模服务器节点的数量发生变化而访问不到，导致直接访问数据库中的资源，给数据库造成压力

一致性hash算法

1.环形的hash空间

环形hash空间

环上有2^32-1个位置。

2.对对象计算hash后映射到环上相应的位置

image.png

3.将服务器节点计算hash值，映射到环上相应的位置

image.png

4.对象顺时针查找服务器节点，那么第一个遇到的服务器即是存储该对象的服务器。

image.png
使用一致性hash算法后，如果服务器的节点有调整，比如减少一台服务器，那么只会影响该服务器存储的数据丢失，该服务器节点存放的对象会被重新分配到他顺时针相邻的服务器节点上
减少服务器节点
添加服务器节点

一致性hash算法改良

从上面的描述中可以看出，一致性hash算法的对象存储是通过顺时针找到最近的服务器节点上进行存储，所以要求hash算法足够分散，并且服务器节点的分布处于均匀分布再环上的状态，这样每台服务器存储的对象才能相对均匀，如图：

image.png
但是实际上服务器节点很难均匀分布在环上，大多数处于聚集分布
导致对象分配不均匀，称为hash倾斜
image.png

改进

为了减少hash倾斜，给每台服务器增加虚拟节点，对象进行hash计算后，通过虚拟节点映射到相应的真实节点，

image.png image.png