什么是一致性hash算法？

一、什么是hash算法？

以分布式缓存为例，假设现在有3台缓存服务器(S0，S1，S2)，要将一些图片尽可能平均地分配到不同的服务器上，hash算法的做法是：

(1) 以图片的名称作为key，然后对其做hash运算。

(2) 将hash值对服务器数量进行求余，得到服务器编号，最后存入即可。

举个栗子：

csdn.jpg 需要存入， 我们就得到hash(csdn.jpg) = 5 ——-> 5%3 = 2 得到数据存入S2

思考:

上面的算法好像可以把图片均衡地分配到不同的服务器，当获取数据的时候也可以根据同样的思路访问对应的服务器，避免全局扫描。但是，这个时候服务器进行了扩容，加入了S4，我们还能否正常获取数据呢？

假设还是根据同样的思路获取csdn.jpg，我们就会得到 hash(csdn.jpg)%4 = 1。显然，我们去S1是无法获取数据的，这个时候就有可能会引发缓存的血崩，大量的请求落到数据库上。

那应该怎么办呢？

二、一致性hash算法

一致性hash算法会建立一个有2^32个槽点(0 – 2^32-1)的hash环，假设现在有A、B、C三台服务器，以A为栗，会进行hash(A)%2^32，得到一个0 – 2^32-1之间的数，然后映射到hash环上，如图所示：

 接下来，我们同样以csdn.jpg为例，我们照样算出hash(csdn.jpg)%2^32的值，然后映射到hash环上，然后以该点出发，顺时针遇到的第一个服务器，即为数据即将存储的服务器。

 这时增加了服务器D又会发生什么事情呢?

如果这个时候在A – C之间插入了服务器D，请求获取getKey(csdn.jpg)时，顺时针获得的服务器是D，从D上获取数据理所当然会失败，因为数据存在A上缓存。这样看缓存好像还是失效了。

那么做成hash环有什么好处呢？

虽然增加了节点D后，csdn.jpg的缓存失效了，但是，分布在 A-B，B-C 以及 D-A上面的数据仍然有效，失效的只是C-D段的数据(数据存在A节点，但是顺时针获取的服务器是D)。这样就保证了缓存数据不会像hash算法那样大面积失效，同样起到减轻数据库压力的效果。

思考：

既然hash环能保证在服务器节点发生变化的情况下，数据只会部分失效，那一致性hash是不是就结束了呢？

什么是hash偏斜?

A、B、C服务节点，如果像上图那样接近于将hash环平均分配那固然理想，但是如果他们hash值十分相近，会发生什么呢?

 上图这种情况称之为hash偏斜，在这种情况下，大部分数据都会分部在C-A段，这个时候去A节点被删除，会有大量请求涌向B节点，给B节点带来巨大的压力，同时这部分缓存也会全部失效，有可能引发缓存雪崩。

怎么办呢?

这个时候我们可能会想到一句老话: 人多力量大。

如果我们的节点足够多，就应该可以防止服务器节点分布不均的问题了。

所以引入了虚拟节点的概念，以A节点为例，虚拟构造出(A0,A1,A2….AN)，只要是落在这些虚拟节点上的数据，都存入A节点。读取时也相同，顺时针获取的是A0虚拟节点，就到A节点上获取数据，这样就能解决数据分布不均的问题。如图所示：    

虚拟节点读写大概流程为:   数据读写 -> 虚拟节点 -> 真实节点 -> 读写

至此，一致性hash算法已经介绍完毕~ 感谢阅读

END-