本文参考资源：

一致性哈希算法概述

分布式系统中，常常听到一种算法叫一致性哈希算法，而最常用的领域相信大家也有所耳闻——负载均衡。负载均衡有许多算法，例如轮询、随机、加权轮询/随机、最小连接数。但是假如我们需要会话粘滞（session sticky）呢？

什么是会话粘滞：给同一个客户提供服务的服务器永远是同一台，就能实现每次连接都是上次的session。例如我去银行办手续，谈到一半发现自己身份证忘带了，需要回家拿身份证，那么我拿完身份证回来之后希望还是同一个业务员来接待我。

一致性哈希算法就保证了分布式系统中每次给同一台客户机服务的主机都是同一台，而分辨是否是同一台客户机的依据就是客户机的IP。那么如何根据这个IP来选取同一台服务器来服务呢，如果使用哈希算法获取同一个哈希值，则这个哈希值的生成必须不能和服务器的个数相关，否则一旦服务器增加或者减少，最终生成的哈希值都会变化。

一致性哈希算法原理

环形hash空间

按照常用的hash算法来将对应的key哈希到一个具有2^32次方个节点的空间中，即0 ~ (2^32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。

映射服务器节点

将各个服务器进行一个哈希，具体可以选择服务器的ip或唯一主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置。假设我们将四台服务器使用ip地址哈希后在环空间的位置如下：

映射数据

现在我们将objectA、objectB、objectC、objectD四个对象（代表客户机的IP）通过特定的Hash函数计算出对应的key值，然后散列到Hash环上,然后从数据所在位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

服务器的删除与添加

如果此时NodeC宕机了，此时Object A、B、D不会受到影响，只有Object C会重新分配到Node D上面去，而其他数据对象不会发生变化。

这时可能就有问题了，不是说能保证每次给同一个客户服务的都是同一台服务器吗？那现在把C重新分配给Node D是怎么回事？

我们只能尽可能地保证每次给同一个客户服务的都是同一台服务器，但是Node C宕机了也没办法啊?而且影响到的只有之前分配给Node C的客户机，对于A、B、D都没有影响到。

如果在环境中新增一台服务器Node X，通过hash算法将Node X映射到环中，通过按顺时针迁移的规则，那么Object C被迁移到了Node X中，其它对象还保持这原有的存储位置。

虚拟节点

前面部分讲述到的都是节点较多和节点分布较为均衡的情况，当服务器节点比较少的时候，会出现一个问题，就是此时必然造成大量数据集中到一个节点上面，极少数数据集中到另外的节点上面。

为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以先确定每个物理节点关联的虚拟节点数量，然后在ip或者主机名后面增加编号。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：