一致性哈希在分布式系统中应该是实现负载平衡的首选算法，它的实现比拟灵便，既能够在客户端实现，也能够在中间件上实现，比方日常应用较多的缓存中间件memcached和redis集群都有用到它；

memcached 的集群比拟非凡，严格来说它只能算是伪集群，因为它的服务器之间不能通信，申请的散发路由齐全靠客户端来的计算出缓存对象应该落在哪个服务器上，而它的路由算法用的就是一致性哈希；

还有 redis 集群中哈希槽的概念，尽管实现不尽相同，但思维万变不离其宗，看完本篇的一致性哈希，你再去了解 redis 槽位就轻松多了；

一致性哈希算法在九七年由麻省理工学院提出，是一种非凡的哈希算法，在移除或者增加一个服务器时，可能尽可能小地扭转已存在的服务申请与解决申请服务器之间的映射关系；

一致性哈希解决了简略哈希算法在分布式哈希表中存在的动静伸缩等问题；

一致性哈希算法实质上也是一种取模算法；

　哈希是一种通过对数据进行压缩,从而提高效率的一种解决办法，但因为哈希函数无限，数据增大等缘故，哈希抵触成为数据无效压缩的一个难题。

不过，不同于上边按服务器数量取模，一致性哈希是对固定值 2^32 取模；

IPv4 的地址是 4 组 8 位 2 进制数组成，所以用 2^32 能够保障每个 IP 地址会有惟一的映射；

①哈希环

咱们能够将这2^32个值形象成一个圆环，圆环的正上方的点代表 0，顺时针排列，以此类推：1、2、3…直到2^32-1，而这个由 2 的 32 次方个点组成的圆环统称为哈希环；

② 服务器映射到哈希环

在对服务器进行映射时，应用哈希（服务器ip）% 2^32，即：

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

而这个整数映射在哈希环上的地位代表了一个服务器，顺次将node0、node1、node2三个缓存服务器映射到哈希环上；

③ 对象 key 映射到服务器

在对对应的 Key 映射到具体的服务器时，须要首先计算 Key 的哈希值：哈希（key）% 2^32；

注：此处的哈希函数能够和之前计算服务器映射至哈希环的函数不同，只有保障取值范畴和哈希环的范畴雷同即可（即：2^32）；

将 Key 映射至服务器遵循上面的逻辑：

从缓存对象 key 的地位开始，沿顺时针方向遇到的第一个服务器，便是以后对象将要缓存到的服务器；

假如咱们有四个对象，别离简写为 1、2、3 和 4；

首先，应用哈希函数计算这个对象的哈希值，值的范畴是 [0, 2^32-1]：

图中对象的映射关系如下：

哈希(1) = k1; 哈希(2) = k2;

哈希(3) = k3; 哈希(4) = k4;

同时4台缓存服务器，别离为 CS1、CS2 、CS3和CS4：

则可知，各对象和服务器的映射关系如下：

K1 => CS1

K2 => CS2

K3 => CS3

K4 => CS4

以上便是一致性哈希的工作原理；

能够看到，一致性哈希就是：将本来单个点的哈希映射，转变为了在一个环上的某个片段上的映射！

如果应用简略的取模办法，当新增加服务器时可能会导致大部分缓存生效，而应用一致性哈希算法后，这种状况失去了较大的改善，因为只有少部分对象须要重新分配！

各个服务器简被均摊到哈希环上；

然而在理论场景中很难选取到一个哈希函数这么完满的将各个服务器散列到哈希环上；

此时，在服务器节点数量太少的状况下，很容易因为节点散布不平均而造成数据歪斜问题；

如下图被缓存的对象大部分缓存在node-4服务器上，导致其余节点资源节约，零碎压力大部分集中在node-4节点上，这样的集群是十分不衰弱的：

同时，还有另一个问题：

在下面新增服务器 CS4 时，CS4 只分担了 CS1 服务器的负载，服务器 CS2 和 CS3 并没有因为 CS4 服务器的退出而缩小负载压力；如果 CS4 服务器的性能与原有服务器的性能统一甚至可能更高，那么这种后果并不是咱们所冀望的；

针对这些问题，咱们可以通过引入虚构节点来解决负载不平衡的问题：

先将每台物理服务器虚构为一组虚构服务器，将虚构服务器搁置到哈希环上，如果要确定对象的服务器，需先确定对象的虚构服务器，再由虚构服务器确定物理服务器；

调配的虚构节点个数越多，映射在哈希环上才会越趋于平均，节点太少的话很难看出成果；

引入虚构节点的同时也减少了新的问题，要做虚构节点和实在节点间的映射，对象key->虚构节点->理论节点之间的转换。