3.4 服务器增加的情况
假设由于业务需要，我们需要增加一台服务器 cs4，经过同样的 hash 运算，该服务器最终落于 t1 和 t2 服务器之间，具体如下图所示：
对于上述的情况，只有 t1 和 t2 服务器之间的对象需要重新分配。在以上示例中只有 o3 对象需要重新分配，即它被重新到 cs4 服务器。在前面我们已经分析过，如果使用简单的取模方法，当新添加服务器时可能会导致大部分缓存失效，而使用一致性哈希算法后，这种情况得到了较大的改善，因为只有少部分对象需要重新分配。
3.5 服务器减少的情况
假设 cs3 服务器出现故障导致服务下线，这时原本存储于 cs3 服务器的对象 o4，需要被重新分配至 cs2 服务器，其它对象仍存储在原有的机器上。
3.6 虚拟节点
到这里一致性哈希的基本原理已经介绍完了，但对于新增服务器的情况还存在一些问题。新增的服务器 cs4 只分担了 cs1 服务器的负载，服务器 cs2 和 cs3 并没有因为 cs4 服务器的加入而减少负载压力。如果 cs4 服务器的性能与原有服务器的性能一致甚至可能更高，那么这种结果并不是我们所期望的。
针对这个问题，我们可以通过引入虚拟节点来解决负载不均衡的问题。即将每台物理服务器虚拟为一组虚拟服务器，将虚拟服务器放置到哈希环上，如果要确定对象的服务器，需先确定对象的虚拟服务器，再由虚拟服务器确定物理服务器。
图中 o1 和 o2 表示对象，v1 ~ v6 表示虚拟服务器，s1 ~ s3 表示物理服务器。
四、一致性哈希算法实现
这里我们只介绍不带虚拟节点的一致性哈希算法实现：
import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHashingWithoutVirtualNode { //待添加入Hash环的服务器列表 private static String[] servers = {"192.168.0.1:8888", "192.168.0.2:8888", "192.168.0.3:8888"}; //key表示服务器的hash值，value表示服务器 private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(); //程序初始化，将所有的服务器放入sortedMap中 static { for (int i = 0; i < servers.length; i ) { int hash = getHash(servers[i]); System.out.println("[" servers[i] "]加入集合中, 其Hash值为" hash); sortedMap.put(hash, servers[i]); } } //得到应当路由到的结点 private static String getServer(String key) { //得到该key的hash值 int hash = getHash(key); //得到大于该Hash值的所有Map SortedMap<Integer, String> subMap = sortedMap.tailMap(hash); if (subMap.isEmpty()) { //如果没有比该key的hash值大的，则从第一个node开始 Integer i = sortedMap.firstKey(); //返回对应的服务器 return sortedMap.get(i); } else { //第一个Key就是顺时针过去离node最近的那个结点 Integer i = subMap.firstKey(); //返回对应的服务器 return subMap.get(i); } } //使用FNV1_32_HASH算法计算服务器的Hash值 private static int getHash(String str) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < str.length(); i ) hash = (hash ^ str.charAt(i)) * p; hash = hash << 13; hash ^= hash >> 7; hash = hash << 3; hash ^= hash >> 17; hash = hash << 5; // 如果算出来的值为负数则取其绝对值 if (hash < 0) hash = Math.abs(hash); return hash; } public static void main(String[] args) { String[] keys = {"semlinker", "kakuqo", "fer"}; for (int i = 0; i < keys.length; i ) System.out.println("[" keys[i] "]的hash值为" getHash(keys[i]) ", 被路由到结点[" getServer(keys[i]) "]"); } }
以上代码成功运行后，在控制台会输出以下结果：
[192.168.0.1:8888]加入集合中, 其Hash值为1326271016 [192.168.0.2:8888]加入集合中, 其Hash值为1132535844 [192.168.0.3:8888]加入集合中, 其Hash值为115798597 [semlinker]的hash值为1549041406, 被路由到结点[192.168.0.3:8888] [kakuqo]的hash值为463104755, 被路由到结点[192.168.0.2:8888] [fer]的hash值为1677150790, 被路由到结点[192.168.0.3:8888]
上面我们只介绍了不带虚拟节点的一致性哈希算法实现，如果有的小伙伴对带虚拟节点的一致性哈希算法感兴趣，可以参考 一致性Hash(Consistent Hashing)原理剖析及Java实现 这篇文章。
五、总结
本文通过示例介绍了传统的哈希取模算法在分布式系统中的局限性，进而在针对该问题的解决方案中引出了一致性哈希算法。一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。在介绍完一致性哈希算法的作用和优点等相关知识后，我们以图解的形式生动介绍了一致性哈希算法的原理，最后给出了不带虚拟节点的一致性哈希算法的 Java 实现。
