转帖：一致性哈希算法
Consistent Hashing算法早在1997年就在论文《Consistent hashing and random trees》 (https://dl.acm.org/citation.cfm?id=258660)中被提出，目前在cache系统中应用越来越广泛。
基本场景
比如你有N个cache服务器（后面简称cache），那么如何将一个对象object映射到N个cache 上呢，你很可能会采用类似下面的通用方法计算object的hash值，然后均匀的映射到到N个cache；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)
意味着什么？这意味着突然之间几乎所有的cache都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；
再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash算法也做不到。
有什么方法可以改变这个状况呢，这就是Consistent Hashing。