一致性Hash算法

余数Hash

最简单、常用的Hash算法。
hash(i) = i mod n
缺点：伸缩性差，使用余数Hash的路由算法，在扩容的时候会造成大量的数据无法正确命中（其实不仅仅是无法命中，那些大量的无法命中的数据还在原缓存中在被移除前占据着内存）。
解决方案为：
（1）在网站访问量低谷，通常是深夜，技术团队加班，扩容、重启服务器
（2）通过模拟请求的方式逐渐预热缓存，使缓存服务器中的数据重新分布

一致性Hash

维基百科定义

一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

原理

一致性Hash算法通过一个叫做一致性Hash环的数据结构实现Key到缓存服务器的Hash映射。

先构造一个长度为2³²的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2³²-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 2³²-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。

环形Hash空间

环形Hash空间

把数据通过一定的hash算法处理后映射到环上
现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值，然后散列到Hash环上。如下图：

    Hash(object1) = key1；
    Hash(object2) = key2；
    Hash(object3) = key3；
    Hash(object4) = key4；

数据Hash

将节点通过hash算法映射到环上
在采用一致性哈希算法的分布式集群中将新的节点加入，其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中（一般情况下对机器的hash计算是采用节点的IP或者机器唯一的别名作为输入值），然后以顺时针的方向计算，将所有对象存储到离自己最近的节点中。
假设现在有NODE1，NODE2，NODE3三台节点，通过Hash算法得到对应的KEY值，映射到环中，其示意图如下：

Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;

节点Hash

新的问题：负载不均

解决办法：引入虚拟节点
其工作原理是：将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。

虚拟节点

实现

可以采用红黑树实现
注意：

1. String重写的hashCode()方法在一致性Hash算法中没有任何实用价值，要重写。因为通过它计算出来的Hash值只分布在一个很小的范围里。这种重新计算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH(MemCache推荐)等
2. TreeMap, TreeSet是Java中对红黑树的实现。
3. 如何添加虚拟节点？要有思路。比如起码要考虑：一个真实结点如何对应成为多个虚拟节点？虚拟节点找到后如何还原为真实结点？一个简单的解决方案如：给每个真实结点后面根据虚拟节点加上后缀再取Hash值，比如”192.168.0.0:111″就把它变成”192.168.0.0:111&&VN0″到”192.168.0.0:111&&VN4″，VN就是Virtual Node的缩写，还原的时候只需要从头截取字符串到”&&”的位置就可以了。

优点

在节点的添加和删除时，一致性哈希算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力。

1. 节点（机器）的删除
   以上面的分布为例，如果NODE2出现故障被删除了，那么按照顺时针迁移的方法，object3将会被迁移到NODE3中，这样仅仅是object3的映射位置发生了变化，其它的对象没有任何的改动。如下图：

   
   节点（机器）的删除

2. 节点（机器）的添加
   如果往集群中添加一个新的节点NODE4，通过对应的哈希算法得到KEY4，并映射到环中，如下图：

   
   节点（机器）的添加

   通过按顺时针迁移的规则，那么object2被迁移到了NODE4中，其它对象还保持这原有的存储位置。

引用
一致性Hash算法的深入理解
每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
一致哈希