一致性哈希算法，即consistent hashing，是分布式系统中常用的算法。主要应用在分布式存储系统中解决数据的分布式保存问题。

一、基本场景

比如有N个cache服务器(后面简称cache)，那么如何将一个对象Object映射到这个N个cache中呢？

最基本的办法就是采用普通的hash算法，对Object的hash值取余。即：

hash(Object)%N

当然如果这样做可行的话也就不用向下介绍了，考虑一下两种情况

一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1)
由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1)

以上两种情况下，缓存会全部失效。所以才会有下面的一致性hash算法。

二、一致性hash算法

consistent hashing 是一种hash算法，简单的说，在移除或者添加一个cache时，它能够尽可能小的改变已存在key映射关系，尽可能的满足单调性的要求。

1、环形hash空间

在Java中，一个对象的hash方法返回的是一个int型的32位数据，所以，我们把这个空间范围0-2^32-1想象成一个首尾相接的环；

这个环是一致性hash算法的根本，下面的一系列映射都将围绕这个环展开。

2、对象映射到hash空间

有了环形的hash空间以后，我们就要考虑对象的存储问题。

通过对象的hash方法，就可以直接得到该对象在环形空间上的地址，以下面的四个对象为例：

hash(object1) = key1;

… …

hash(object4) = key4;

3、把cache映射到hash空间

Consistent hashing 的基本思想就是将对象和cache都映射到同一个hash数值空间中，并且使用相同的hash算法。

所以接下来就要把cache服务器也映射到这个hash空间之中。

以三个cache服务器为例：

hash(cache A) = key A;

… …

hash(cache C) = key C;

对于cache，可以把服务器的ip地址作为hash的输入

4、把对象映射到cache

通过上面的两个步骤，对象和cache通过相同的hash算法被映射到相同的hash空间之中了，那么接下来就是把对象映射到cache里面了。

在环形空间中，如果沿着顺时针方向从对象的key值出发，直到遇见一个cache ，那么就将该对象存储在这个cache 上，因为对象和cache的hash值是固定的，因此这个cache必然是唯一和确定的。

参照上面的图片，对象Object1将被存储到cache A 上；Object2和Object3对应到cache C ；Object4对应到cache B ；

5、cache的变动

最原始的hash方法不可行的原因就是当cache的数量发生变化时，缓存会失效，那么接下来看看一致性hash算法的好处。

5.1、移除cache

假设cache B挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿cache B逆时针遍历直到下一个cache(cache C)之间的对象，也即是本来映射到cache B上的那些对象。

因此这里仅需要变动对象Object4 ，将其重新映射到cache C上即可

5.2、增加cache

再假设添加一台新的cache D的情况，假设在这个环形hash空间中， cache D被映射在对象Object2和Object3之间。这时受影响的将仅是那些沿cache D逆时针遍历直到上一个cache(cache B)之间的对象(它们是也本来映射到 cache C 上对象的一部分)，将这些对象重新映射到cache D上即可。

可以看出，不管是增加还是移除缓存服务器，都不会对整个分布式缓存系统带来太大的影响。

6、虚拟结点

通过上面的机制解决了系统的稳定性，而接下来则可以在性能上进一步提高。

考量hash算法的另一个指标是平衡性 (Balance) ，定义如下：

平衡性：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

hash算法并不是保证绝对的平衡，如果cache较少的话，对象并不能被均匀的映射到cache上，比如在上面的例子中，仅部署cache A和cacheC的情况下，在4 个对象中， cache A仅存储了Object1 ，而cache C则存储了Object2、Object3和Object4。明显是不均衡的。

为了解决这种情况， consistent hashing引入了“虚拟节点”的概念，它可以如下定义：

“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。

再以仅部署cache A和cache C的情况为例，上面我们已经看到， cache分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了cache A ；cache C1, cache C2 代表了 cache C ；假设一种比较理想的情况，