分布式集群中的一致性哈希算法
普通哈希
在wiki中这样介绍哈希：
散列函数（或散列算法，又称哈希函数，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。
在分布式集群中可通过hash(key)得到散列值，然后对节点取余hash(key)%node_number,其值即为数据存放节点。 但当删除或增加节点时，会出现有些数据未命中等情况，需重新计算，同时数据也需迁移。
一致性哈希
为解决上述问题，MIT提出了一致性哈希算法。 在网上查找资料时发现有不同说法，不过在wiki上为第2种
1.服务器拥有多个虚拟节点
数据映射到多个虚拟节点（多于服务器数），再映射到真实服务器 即hash(key)%VN数据到虚拟节点，然后平均分配节点到服务器，若服务器宕机，只需把宕机服务器管理的虚拟节点移到其它服务器（只需移到一个服务器数据），同时为防止这样会导致不同服务器负载不均衡，对故障服务器的虚拟节点重新分配（rehash，平均分配到其它服务器）
Amazon的大数据存储平台“Dynamo”使用了一致性哈希，但它并没有使用经典算法，而是使用了故障节点ReHash的思路。 系统将所有的虚拟节点和真实服务器的对应关系保存到一个配置系统，当某些虚拟节点的服务不可用时，重新配置这些虚拟节点的服务到其他真实服务器，这样既不用大量迁移数据，也保证了所有服务器的负载相对均衡。
可参考http://blog.zheezes.com/consistent-hashing-algorithm-design-principles.html
2.服务器映射为多个虚拟节点，同生共灭
- 把key哈希到环空间，数据，服务器都hash映射到环空间，按顺时针把数据存在相邻服务器，增删服务器时也也存入相邻服务器
- 但这样会导致负载不平衡，可采用虚拟节点，但不同于1中的虚拟节点。此处虚拟节点为服务器映射出的虚拟节点，以使服务器管辖区域均匀，服务器宕机虚拟节点也消失。
wiki上实现
一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。 当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。
可参考http://yikun.github.io/2016/06/09/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3%E4%B8%8E%E5%AE%9E%E8%B7%B5/
http://blog.csdn.net/cywosp/article/details/23397179/