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

1、环形空间

考虑通常的hash算法都是将value映射到一个32维的key值，也即是0~2^32-1次方的数值空间；我们可以将这个空间想象成一个首（0）尾（2^32-1）相接的圆环。
E81F5D085BD044F76C02D76F2107775A.jpg

2、把对象映射到hash空间

接下来考虑4个对象object1~object4，通过hash函数计算出的hash值key在环上的分布如图：

  1. hash(object1) = key1
  2. hash(object2) = key2
  3. hash(object3) = key3
  4. hash(object4) = key4

B3EF014D7A0EEA8F8D52FC0BE140E2FA.jpg

3、把cache映射到hash空间

Consistent Hashing的基本思想就是将对象和cache都映射到同一个hash数值空间中，并且使用相同的hash算法。
假设当前有A、B和C共3台cache，那么其映射结果如图：

  1. hash(cache A) = key A
  2. hash(cache B) = key B
  3. hash(cache C) = key C

48E61BC2B89DDD9E05CFB3B654C31D95.jpg
说到这里，顺便提一下cache的hash计算，一般的方法可以使用cache机器的IP地址或者机器名作为hash输入

4、把对象映射到cache

在这个环行空间中，如果沿着顺时针方向从对象的key值出发，直到遇见一个cache，那么就将该对象存储在这个cache上，因为对象和cache大hash值是固定的，因此这个cache必然是唯一和确定的。这样不就找到了对象和cache大映射方法了吗？！
根据上面的方法，如上图所示：object1存储在cacheA上，object2和object3存储在cacheC上，object4存储在cacheB上。

5、考察cache的变动

前面讲过，通过hash然后求余的方法带来的最大问题就在于不能满足单调性，当cache有所变动时，cache会失效，进而对后台服务器造成巨大的冲击。现在就来分析Consistent Hashing算法

  • 移除cache

考虑假设cacheB挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿着cacheB逆时针遍历直到下一个cache（cacheC）之间的对象，也即是本来映射到cacheB上的那些对象。因此这里仅需要变动对象object4，将其重新映射到cacheC上即可
34D3C0AB84F5E646FC2AD9CB77D52079.jpg

  • 添加cache

再考虑添加一台新的cacheD的情况.假设在这个环行空间中，cacheD被映射到在对象object2和object3之间，这时受影响的将仅仅是那些沿objectD逆时针遍历直到下一个cache（cacheB）之间的对象（它们是也本来映射到cacheC上对象的一部分），将这些对象重新映射到cacheD上即可。因此这里仅需变动对象object2，将其重新映射到cacheD上
89EC1038D2F14D037B0448E7EE58F924.jpg
考量hash算法的另一个重要指标是平衡性（Balance）

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

hash算法并不是保证绝对的平衡，如果cache较少的话，对象并不能被均匀的映射到cache上。比如图3.17