一致性Hash算法原理！

假如有三台服务器编号node0、node1、node2，现在有3000万个key，希望可以将这些个key均匀的缓存到三台机器上？

可以使用取模算法hash（key）% N，对key进行hash运算后取模，N是机器的数量。

但服务器数量N发生变化后hash（key）% N计算的结果也会随之变化。

一致性hash算法本质上也是一种取模算法，不过不同于上边按服务器数量取模，一致性hash是对固定值2^32取模。

IPv4的地址是4组8位2进制数组成，所以用2^32可以保证每个IP地址会有唯一的映射。

将这2^32个值抽象成一个圆环，圆环的正上方的点代表0，顺时针排列。

以此类推，1、2、3、4、5、6……直到2^32-1，而这个由2的32次方个点组成的圆环统称为hash环。

服务器映射到hash环:

使用服务器IP地址进行hash计算，用哈希后的结果对2^32取模，结果一定是一个0到2^32-1之间的整数。

而这个整数映射在hash环上的位置代表了一个服务器，依次将node0、node1、node2三个缓存服务器映射到hash环上。

一致性hash的优势：

假如业务量激增，系统需要进行扩容增加一台服务器node-4，刚好node-4被映射到node-1和node-2之间。

沿顺时针方向对象映射节点，发现原本缓存在node-2上的对象key-4、key-5被重新映射到了node-4上。

而整个扩容过程中受影响的只有node-4和node-1节点之间的一小部分数据。

假如node-1节点宕机，沿顺时针方向对象映射节点，缓存在node-1上的对象key-1被重新映射到了node-4上。

此时受影响的数据只有node-0和node-1之间的一小部分数据。

数据偏斜问题：

在服务器节点数量太少的情况下，很容易因为节点分布不均匀而造成数据倾斜问题。

被缓存的对象大部分缓存在node-4服务器上，导致其他节点资源浪费，系统压力大部分集中在node-4节点上。

这样的集群是非常不健康的。

一致性Hash算法引入了一个虚拟节点机制：

即对每个服务器节点计算出多个hash值，它们都会映射到hash环上，映射到这些虚拟节点的对象key，最终会缓存在真实的节点上。

一致性hash的应用场景：

一致性hash在分布式系统中应该是实现负载均衡的首选算法。

比如日常使用较多的缓存中间件memcached和redis集群都有用到它。