java简单实现一致性哈希算法

什么是一致性哈希算法
一种特殊的哈希算法，这种算法使得哈希表、集群的规模在伸缩时尽可能减少重映射（remap）。

为什么需要它
一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑（集群）中分布存储和路由。每个节点仅需维护少量相邻节点的信息，并且在节点加入/退出系统时，仅有相关的少量节点参与到拓扑的维护中。

两种常见的一致性哈希算法
余数hash
hash_ip（请求者的ip的hashCode） % slot_Num（节点数） = n，n为节点的序号假设现在有3台缓存服务器，现在有20个ip来访问缓存集群，假设3个节点的序号为0~2，20个ip的hashCode为0~19，那么路由情况如下：如果扩展到4台服务器，那么只有标红色能命中缓存，并且随着服务器的增加，缓存的命中率递减
hash_ip   0   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19  
路由到的节点   0   1   2   0   1   2   0   1   2   0   1   2   0   1   2   0   1   2   0   1  
红色的为命中的缓存，黑色的缓存都shixiao hash_ip   0   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19  
路由到的节点   0   1   2   3   0   1   2   3   0   1   2   3   0   1   2   3   0   1   2   3  
从上面的例子中可以看出余数hash的伸缩性不好，当我们进行扩容时，多数缓存失效，压力全部移到数据库上，有可能导致数据库宕机。
这个问题的解决方案：
1.在网站访问量低的时候，比如凌晨，进行扩容
2.发送模拟请求进行缓存预热，使数据在缓存集群上重新分布

一致性hash算法
原理：先构造一个长度为232的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2的32次方-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 2的32次方-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。
下图的大环表示hash环，蓝色点表示hashCode[node_ip]在环上的分布，小点表示hashCode[client_ip]，顺时针寻找第一个大于hashCode[client_ip]的节点哈希值，即路由到该节点，由该节点处理请求。这种情况基本解决了伸缩性差的问题，我们随时可以添加删除节点到哈希环上。

但是节点的扩容又导致了一个问题：负载不均。如下图

当我们增加了node4节点时，那些本来会转发给node3的请求会被路由到node4上，导致node3处于空闲状态，而node4压力较大，这时，虚拟节点出现了，此时哈希环上的节点都是虚拟节点，多个虚拟节点映射到一个物理节点，也就是说，当我们添加一个节点时，我们不再把物理节点作为一个节点存到哈希环上，而是用多个虚拟节点来替代一个物理节点，路由到某个虚拟节点后再映射到物理节点。而这多个虚拟节点是分散的，很大程度可以弥补负载不均的缺点。

下图的黄色节点为新添加的虚拟节点，这3个节点实际上值对应一个物理节点，比如物理节点：10.0.0.101:1111，自定义虚拟节点（我在物理节点后加virtual node+序号）：10.0.0.101:1111vn1、10.0.0.101:1111vn2、10.0.0.101:1111vn3，这样映射到哈希环上分散的，不会像一个节点那样导致扩容后负载不均，只要虚实节点的比例合理。

从网上找的，物理节点和虚拟节点的比例图，纵坐标表示物理节点数，横坐标表示虚拟节点数，比如物理节点只有10个时，需要100~200个虚拟节点

附带虚拟节点的一致性hash的java实现
1.使用FNV_1哈希算法来散列ip（java的hashCode值太集中，不适合）
2.用treeMap来存储节点的hash值，使用tail方法获取比hashCode[client_ip]大的子集，取子集的第一个节点
就是我们要的节点。

3.简单起见，一个物理节点对应4个虚拟节点

package consistence_hash_algorithm; import java.util.SortedMap; import java.util.TreeMap; /** * writer: holien * Time: 2017-10-20 21:07 * Intent: 使用虚拟节点的一致性哈希算法 */ public class ConsistentHashingWithVirtualNode { // 4个物理节点 private static String[] servers = {"168.10.10.101:6386", "168.10.10.101:6387", "168.10.10.101:6388", "168.10.10.101:6389"}; // 使用SortedMap可以排序，再使用tailMap获取key比hashCode[client_ip]大的子map private static SortedMap virtualNodes; private static final int VIRTUAL_NODE_NUM = 4; // 模拟线上的4台服务器对应的16个虚拟节点 static { virtualNodes = new TreeMap<Integer, String>(); for (int i = 0, len = servers.length ; i < len; i++) { int hashCode; String vitualNode; for (int j = 0; j < VIRTUAL_NODE_NUM; j++) { // 计算节点的哈希值作为key，节点ip("168.10.10.101:6386vni")作为value vitualNode = servers[i] + "vn" + j; // 计算虚拟节点的hashCode hashCode = getHashCode(vitualNode); virtualNodes.putIfAbsent(hashCode, vitualNode); System.out.println("添加了虚拟节点：" + vitualNode + ", hashCode：" + hashCode); } } } // 使用32位FNV_1计算节点的hashCode private static int getHashCode(String node) { final int p = 16777619; int hash = (int)2166136261L; for (int i = 0; i < node.length(); i++) hash = (hash ^ node.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; } // 通过client_ip的哈希值路由一个虚拟节点，再映射到物理节点 public static String routeServer(String node) { int hashCode = getHashCode(node); SortedMap subMap = virtualNodes.tailMap(hashCode); int firstKey = (Integer)subMap.firstKey(); String virtualNode = (String)subMap.get(firstKey); // 模拟寻找物理节点，把vni去掉 String actualNode = virtualNode.substring(0, virtualNode.length() - 3); System.out.println(node + "的hashCode为" + hashCode + "，被路由到虚拟节点：" + virtualNode + "，映射到物理节点：" + actualNode); return actualNode; } public static void main(String[] args) { String[] nodes = {"10.112.11.252:1111", "221.226.0.1:2222", "10.211.0.1:3333"}; for (int i = 0, len = nodes.length; i < len; i++) { routeServer(nodes[i]); } } }

运行结果：