面试宝典系列 - 一致性hash的实现
为什么要使用一致性hash？
一致性hash主要应用于分布式、负载均衡等。
例如：你有 N 个 cache 服务器，那么如何将一个对象object 映射到 N 个 cache 上呢，你很可能会采用取模（key%N）的方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache服务器。当一个服务器挂了或者增加了一个，那么得到的hash值=key%(N-1)（或者key%(N+1)），造成的后果就是所有的缓存都失效了，这不是我们想看到的。
此时就要考虑一致性hash了。
一致性hash的实现
1、首先计算出每个节点的hash值，并将其配置到0～（2的32次方）的圆（continuum）上。
2、用同样的hash函数计算出存储数据的hash值，并映射到相同的圆上。
3、然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个节点上。如果超过（2的32次方）仍然找不到服务器，就会保存到第一台memcached服务器上
如果增加一个节点，观察下影响范围
由图可以看出，影响范围缩小至node2和node5之间的数据
推荐：https://www.cnblogs.com/lpfuture/p/5796398.html
转载于:https://my.oschina.net/suyain/blog/1863877