了解下一致性哈希算法

一致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1])，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

基本场景

现在互联网分布式系统应用越来越普遍，不可避免的要碰到集群中单节点破坏后系统负载的问题hash(object)%N一切都运行正常，再考虑如下的两种情况；1一个cache服务器m down掉了（在实际应用中必须要考虑这种情况），这样所有映射到cache m的对象都会失效，怎么办，需要把cache m从cache中移除，这时候cache是N-1台，映射公式变成了hash(object)%(N-1)；2由于访问加重，需要添加cache，这时候cache是N+1台，映射公式变成了hash(object)%(N+1)；1和2意味着什么？这意味着突然之间几乎所有的cache都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；比如你N个cache服务器（后面简cache），那么如何将一个对象object映射到N个cache上呢，你很可能会采用类似下面的通用方法计算object的hash值，然后均匀的映射到到N个cache；有什么方法可以改变这个状况呢，这就是consistent hashing...

Hash算法的一个衡量指标是单调性（Monotonicity），定义如下：

再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的hash算法也做不到。

　　单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到，上面的简单hash算法hash(object)%N难以满足单调性要求。

　　但是一致性哈希的路由算法尚有不足之处。在查询过程中，查询消息要经过O(N)步(O(N)表示与N成正比关系，N代表系统内的节点总数)才能到达被查询的节点。不难想象，当系统规模非常大时，节点数量可能超过百万，这样的查询效率显然难以满足使用的需要。换个角度来看，即使用户能够忍受漫长的时延，查询过程中产生的大量消息也会给网络带来不必要的负荷。