一致性哈希

出现的起因

在分布式系统中，我们通常需要对相同服务器做负载均衡，或者者将某些请求打到同一台服务器上，这是我们使用哈希算法，比方通过用户端的ip，对服务器个数进行取模，如下图所示：

弊端：上述方案存在显著的弊端，当需要对服务器进行扩容，或者者有服务宕机后，则经过Hash的结果必然会发生问题。

一致性哈希

一致性哈希也是使用取模的形式，但是不是对服务器个数进行取模了，而是对2^32 -1取模。即将0 ~ 2^32-1 的无符号整型分布在一个圆形的环上。从正上方的0开始顺时针旋转，一直到2^32-1，哈希环如下图所示：

模拟三台服务器在哈希环上的情况：
这时候来了三个用户端经哈希取模分别访问三个服务器，具体如下图所示：

如上图所示，有三个服务器，分别是Server1、Server2、Server3，有三个用户端进行访问，分别是client1，client2，client3。
1）三个用户端经过哈希取模，如图分别落在了哈希环的三个节点上。
2）三个用户端的节点会进行顺时针寻觅，知道发现服务器为止。
client1 -> Server1；
client2 -> Server2；
client3 -> Server3；

模拟一台服务器宕机的情况：
如果说Server2这时候宕机了，那么client2的请求经过顺时针寻觅，最终会落在Server3上，如下图所示：

模拟添加一台服务器的情况：
这时候服务器添加了一台ServerN，这个ServerN处于Server2和Server3之间，那么最终可能导致流下Server3的请求落在ServerN上，而Server1和Server2没有影响，如下图所示：

数据倾斜问题

细心的同学应该发现了，当哈希环节点很少的时候，很难做到像轮一样一人一次的效果，可能会导致大量的请求打在同一个server上，client1、client4、client5、client6的请求一律落在Server1上，如下图所示：

数据倾斜问题处理方案：
一致性哈希为理解决数据倾斜的问题，引入了虚拟哈希的处理方案。即在哈希环上放置很多服务节点的虚拟节点，相当于添加了节点数量，而内部只要要做每个虚拟节点到实际节点的映射就可，以Server1举例，如下图所示：

一点结论：
当物理节点越多，虚拟节点就越多，服务可用性就越高。