前言

假设现在有一个分布式系统，比如创建一个Tomcat集群部署一个web项目，采用Nginx服务器进行负载均衡。我们知道，nginx常见的负载均衡策略有：

• 轮询（一个一个来）
• 权重（访问比率参照分配给各个服务器的权重）
• URL hash（server_id = hash(request_url)%server_num），对请求的URL进行哈希，再对服务器个数进行取模，得到相应的服务器序号。

之所以出现URL hash，一般情况下是因为对于一个url（或其他的资源），我们希望快速定位到他所在的服务器。如果不采用哈希，效率最低的办法是挨个访问服务器，查看是否存在该资源，时间复杂度是O(N)（N为服务器个数），而哈希的时间复杂度是O(1)。

如果采用URL hash策略，那么在比较理想的情况下（服务器个数恒定不变），对于同一个请求（URL），每次处理请求的都是同一个服务器。如果我们只是希望服务器帮我们处理一下某种业务，那请求打到任何一个服务器上对于客户来说都是没有区别的。但是如果这是一个分布式缓存系统，我们自然希望当一个资源存到机器a上以后，下次再取的时候能直接找到机器a，而不是再去找机器c、机器d再存一遍。那么简单的URL hash策略能保证在分布式缓存系统中，对于同一资源（同一个key）的请求能每次都打到同一服务器上吗？

答案是不能。理由很简单：当服务器个数为5个的时候，请求的服务器id是hash(key)%5。当一个服务器宕机了，同样的key请求的服务器id变成了hash(key)%4；又或者处于业务需要扩展了集群，新增了一个服务器，这个时候请求的服务器id又变成了hash(key)%6。大量的请求打到了新的地方，相当于原有的大量缓存失效，请求打到了存储层，发生缓存穿透甚至缓存雪崩。

因此，简单的URL hash无法保证对于同一个key的请求始终打到同一服务器上。为了实现这个功能，我们需要的是一致性哈希算法

一致性哈希算法简介

hash(key)，即哈希函数的结果是一个unsigned int类型，所占的大小为4个字节32位，取值范围为0 ~ $2^{32}-1$232−1 。我们可以把哈希空间想象成一个环，任何哈希后的结果都可以映射到这个环上：

一般来说，我们可以用ip地址作为一台服务器的唯一标识。图中的Server A代表是的hash(ServerA.ip)，Server B代表的是hash(ServerB.ip)，key a代表的是hash(keya)，key b同理。一致性哈希算法规定，一个key对应的服务器就是这个key沿着环顺时针走碰到的第一个服务器，图中key a对应的是Server A，key b对应的是Server B。

其实严格的来说这并不是一个环，因为0和$2^{32}-1$232−1 并不重叠。事实上这个空间是一条线段，每一个key对应的是右边离他们最近的server。但是对于最后一个server右边的key来说，根据我们的规定，他们对应的其实是第一个server。逻辑上来说，key到server的映射关系是首尾相接的，因此我们把这个空间想象成一个环。

服务器数目变化——局部迁移

现在我们来看一看，一致性哈希算法是如何解决服务器数目变化引发的不一致问题的呢？

想象上面那个图中的Server A宕机了，这时候所有Server B到Server A之间的数据（key a）就要由Server A迁移到B中。

当新增服务器时，比如下图中新增了Server C，此时Server A到Server C之间的key本来都存在Server B上，现在需要迁移到C上。图中需要迁移的是key b。而Server C到Server B之间如果有key的话，是不需要迁移的，仍然是存在B上。

可见当服务器数目发生变化时，部分数据需要迁移，但是大部分数据是不用改动的，比最初的URL hash（大部分数据对应的服务器都发生变化）要好得多。

数据倾斜问题——虚拟节点技术

当服务器个数比较少的时候，非常容易发生的一个问题是：哈希空间中服务器的分布不均等，比如刚才画的图里面，Server A对应的key空间就比Server B对应的key空间要明显的大一些，这样就导致了服务器压力不均，在更极端的情况下（两个服务器靠的很近）一个很闲，一个很忙。这样的现象我们称之为数据倾斜。

为了解决数据倾斜问题，常用的方法是虚拟节点技术：对于每一个服务器，我们创建他对应的若干个ip，并把这些ip映射到hash环空间上。当这样的虚拟ip足够多，虽然原节点分布不均，但是原节点的虚拟ip在环上的分布是大抵均匀的。在hash环中，我们不再考虑物理结点，只考虑虚拟节点。对于一个key，我们沿着顺时针找到离他最近的服务器，访问该节点对应的真实服务器。（图就不画了，还是挺容易理解的）

哈希冲突

key发生哈希冲突——两个不同的key映射到了环上的同一地址，这个没什么影响，把他们俩存到同一个服务器上就行。
Server ip发生哈希冲突——两台不同的服务器映射到了环上的同一地址，对应的key不知道存在哪台上。这个问题可以通过虚拟节点技术解决。