作者：tomwhite
链接：https://community.oracle.com/blogs/tomwhite/2007/11/27/consistent-hashing
来源：oracle community
著作权归作者所有，罐头翻译做笔记学习之。
背景
举例说明，比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢？
你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；
hash(object)%N
一个cache服务器故障了（在实际应用中是经常会发生这种问题的），这样一来，映射在该cache服务器上的object都会
失效的，怎么办？这时相对于cache服务器数目变为了N-1台，映射公式会变成：
hash(object)%(N-1)
由于访问加重，需要添加一台cache服务器，这时cache服务器数目变为N+1，映射公式会变成：hash(object)%(N+1)
hash(object)%(N+1)
这两个问题意味着什么，这意味着突然之间几乎所有的cache都失效了，对于服务器而言，这简直是灾难性的毁灭。
一致性哈希的基本思想
要是能这样就好了，当一个缓存设备加入，可以使它对其他的缓存设备分享公平。同样的，当一个缓冲设备去除，它对应的对象可以被剩下的缓存设备负载。这实际上就是一致性哈希所在做，尽可能的情况下，一致性地在映射对象到缓冲设备中。
基于一致性哈希算法背后的想法是对象o和缓冲设备n映射到同一个哈希数值空间中。做法是建立区间来管理缓冲设备，一个区间内对应一些对象，如果缓冲设备的值发生变化，那么它对应的区间将会被相邻的区间占据。
一致性哈希的算法原理
环形哈希空间
这里要引入一个新的表示方法，也就是环形哈希空间，考虑到通常的哈希算法都是将一个任意长度二进制值映射位固定长度的二进制值（一般为32位），也就是说它的取值空间为0~($2^{32}$-1)。我们可以把这个空间想象为一个首是0尾是($2^{32}$-1)相接的圆环，
如下图所示：
把object映射到哈希空间
这里举例说明，比如有四个对象object1~object4，要分别对这四个对象算出其哈希值：
Hash（object1）= point1
Hash（object2）= point2
Hash（object3）= point3
Hash（object4）= point4
把cache映射到哈希空间
这时一致性哈希与众不同的地方，cache和object使用同样的哈希算法也映射到哈市数值空间中。这里假设有3台cacheA、B、C。
如图所示：
Hash（cacheA）= pointA
Hash（cacheB）= pointB
Hash（cacheC）= pointC
把object映射到cache
在这个环形空间中，如果沿着顺时针方向从对象的 point1点出发，直到遇见一个 cache ，那么就将该对象存储在这个 cache 上，因为对象和 cache 的 hash 值是固定的，因此这个 cache 必然是唯一和确定的。
object1,object2 → cacheA
object4 → cacheB
object3 → cacheC
考察cache的变动
考虑假设 cache C 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache C 逆时针遍历直到下一个 cache （ cache B ）之间的对象， 也即是本来映射到 cacheC 上的那些对象都映射到cacheA了。
object1,object2,object3 → cacheA
object4 → cacheB
假设要在这个环形hash空间添加一台新的cacheD，放在object1和object2之间，这时沿着cacheD逆时针遍历，一直到下一个cacheC之间的对象会 重新挂载到cacheD中；
object1 → cacheA
object4 → cacheB
object3 → cacheC
object2 → cacheD
平衡性
考量到hash算法的另一个指标是平衡性：
平衡性是指哈希的结果尽可能分布到所有的cache中去，使空间得到得到充分的利用。hash算法并不能保证绝对的平衡，如果cache较少的话，对象不能均匀地映射到cache上，比如上面的例子中，当cacheC挂掉的时候，cacheA同时挂载object1, object2, object3，而cacheB只挂载object4。显然分布十分不均衡。这里引入一个“虚拟节点”的概念，可以很好解决这个问题。
仍以仅部署 cache A 和 cache B 的情况为例，在图 4 中我们已经看到， cache 分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A ； cache B1, cache B2 代表了 cache B ；假设一种比较理想的情况，参见下图 。
通过左图你可以看出副本数值对负载均衡的影响。这个图模拟在10个缓存设备内储存了10,000个对象。在x轴表示圆上缓冲点的副本的个数（用对数作为刻度），当数值很小 的时候，我们看到通过缓存设备负载对象的分配情况并不均衡。平均每个缓冲设备中的 对象数值百分比的标准偏差十分高。随着副本的数值提高， 负载对象的分配情况变得越来 越均衡。这说明了维持一两百 个副本的时候可以达到均衡（标准偏差在5%到10%之间）。
