一致性 Hash 算法（Consistent hashing）早在 1997 年就在论文 Consistent hashing and random trees 中被提出，目前在 cache 系统中应用越来越广泛。
应用场景
假设有 N 个 cache 服务器，那么如何将一个对象 object 映射到 N 个 cache 服务器上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache：
1 | hash(object)%N |
考虑如下的两种情况；
1）假设一个 cache 服务器 m 挂掉了，这样所有映射到 cache m
的对象都会失效。这时需要把 cache 服务器 m 从系统中移除，cache
服务器数变成 N-1 台，因此映射公式变成：
1 | hash(object)%(N-1) |
2）如果需要添加 cache 服务器 ，cache 服务器数变成 N+1 台，映射公式变成：
1 | hash(object)%(N+1) |
这两种情况的出现，使得原来的 cache 都失效了。可见上述的 Hash 算法并不能很好的适应 cache 系统，因此为了解决这两种情况我们引入一致性 Hash。
一致性 Hash 算法
算法具体步骤如下：
- 首先求出每个 Cache 服务器的 hash（可以利用 IP 来计算），并将其配置到一个 0~2^32 的圆环区间上。
- 使用同样的方法求出需要存储对象的 hash，也将其配置到这个圆环上。
- 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个 Cache
节点上。如果超过 2^32 仍然找不到 Cache 节点，就会保存到第一个 Cache
节点上。
新增 Cache 服务器
假设在这个环形哈希空间中，cache5 被映射在 Cache3 和 Cache4 之间，那么受影响的将仅是沿 Cache5 逆时针遍历直到下一个 Cache（Cache3）之间的对象（它们本来映射到 Cache4 上）。
- 移除 Cache 服务器
假设在这个环形哈希空间中，Cache3 被移除，那么受影响的将仅是沿 Cache3 逆时针遍历直到下一个 Cache（Cache2）之间的对象（它们本来映射到 Cache3 上）。
虚拟 Cache 服务器
考虑到哈希算法并不是保证绝对的平衡，尤其 Cache 较少的话，对象并不能被均匀的映射到 Cache 上。为了解决这种情况，一致性 Hash 引入了“虚拟节点”的概念： 一个实际节点对虚拟成若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在哈希空间中以哈希值排列。仍以 4 台 Cache 服务器为例，在下图中看到，引入虚拟节点，并设置“复制个数”为 2 后，共有 8 个“虚拟节点”分部在环形区域上，缓解了映射不均的情况。
引入了“虚拟节点”后，映射关系就从【对象--->Cache 服务器】转换成了【对象--->虚拟节点---> Cache 服务器】。查询对象所在 Cache 服务器的映射关系如下图所示。
参考资料
一致性 hash 算法 - consistent hashing: http://blog.csdn.net/sparkliang/article/details/5279393
一致性哈希算法（Consistent Hashing）: http://blog.csdn.net/x15594/article/details/6270242
一致性 hash 和 solr 千万级数据分布式搜索引擎中的应用: http://blog.jobbole.com/47023/"http://blog.jobbole.com/47023/>