一致性哈希算法JAVA实现
最近在工作中，由于接手了JAVA相关的项目代码，涉及到资源分配的相关知识，里面用到了一致性哈希进行负载均衡，于是就趁这个机会学习了下一致性哈希的相关内容，在此做一下学习总结。
一致性哈希介绍
一致性哈希的主要作用就是用来进行负载均衡，我们设想这么一个场景，我们有四台服务器，然后需要将一批资源均匀的分配到这四台服务器上。
不含虚拟节点的一致性哈希
首先我们先想象有这么一个圆环（也叫哈希环），在哈希环上有2^32个节点；
1、对服务器（能唯一标识该服务的属性，比如服务器的IP）进行求哈希值，使其落到哈希环，如图所示Node0-Node3（四个箭头所示）对应四台服务器；
2、对我们要分配的资源进行求哈希值，同样落到哈希环上，如图所示（图中的星标标识落在哈希环上的资源）；
3、规定落在哈希环上的资源，分配到该资源所在节点顺时针遇到的第一个服务节点上，如图所示；
如果服务器所在的哈希环上的节点如上图所示，均匀分布，那自然是最好的，但如果像下图所示，那么就会导致资源的分配不均。
为了解决这种情况出现的问题，出现了虚拟节点的一致性哈希。
虚拟节点的一致性哈希
所谓的虚拟节点，就是我们假想出来的节点，将这些虚拟节点映射到哈希环上，然后将这些虚拟节点与实际服务器进行关联，例如虚拟节点Node0,Node1与服务器1关联，那么分配到Node0,Node1的资源，也即是分配到实际的服务器1上。
也就是说我们实际的服务器有四台，但我们可以将N个虚拟的节点映射到哈希环上，这样就能通过调节虚拟节点与实际服务器的关联关系，来达到调节分配到不同服务器资源的数量的目的。
一致性哈希的代码实现
/** * 计算哈希值的工具类 */public class Hash { /** * 使用String自带的hashCode函数 * @param str * @return */ public static Integer stringHashcode(String str){ int hash = str.hashCode(); if (hash<0){ hash = Math.abs(hash); } return hash; } /** * 使用FNV1_32_HASH算法计算hash值 * @param str * @return */ public static Integer FNV1_32_HASH(String str){ final int p = 1677769; int hash = (int)0; int len = str.length(); for (int i=0;i<len;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 class HashTest { private static String[] servers = {"192.168.0.1:8999","192.168.0.2:8999","192.168.0.0.3:8999"}; /** * key 服务器的哈希值、 * value 服务器信息 */ private static SortedMap<Integer,String> map = new TreeMap<Integer, String>(); static { /** * 将服务器信息存放到map中 */ int size = servers.length; for (int i = 0;i<size;i++){ int hash = Hash.FNV1_32_HASH(servers[i]); map.put(hash, servers[i]); System.out.println("hash="+hash+" "+"server="+servers[i]); } } /** * 获取资源所在的节点服务器 * @param node * @return */ public static String getServer(String node){ Integer hash = Hash.FNV1_32_HASH(node); //获取大于当前node的hash值的所有服务节点 SortedMap<Integer, String> sortedMap = map.tailMap(hash); Integer key = 0; if (sortedMap.isEmpty()){ //如果没有比node节点hash值大的服务节点，则取hash值最小的服务节点 key = map.firstKey(); }else{ //获取过滤出的服务节点的第一个值，也就是从node开始顺时针遇到的第一个服务节点 key = sortedMap.firstKey(); } String server = map.get(key); return server; } public static void main(String[] args) { String[] index = {"582639584","582639585","582639586","582639587"}; System.out.println("-------------"); int size = index.length; for(int i=0;i<size;i++){ String server = getServer(index[i]); System.out.println("index="+index[i] +" hash="+Hash.FNV1_32_HASH(index[i]) +" server="+server); } }}运行结果:
hash=474459784 server=192.168.0.1:8999hash=1451861892 server=192.168.0.2:8999hash=1078738565 server=192.168.0.0.3:8999-------------index=582639584 hash=1309097570 server=192.168.0.2:8999index=582639585 hash=583335179 server=192.168.0.0.3:8999index=582639586 hash=1918263339 server=192.168.0.1:8999index=582639587 hash=1873142797 server=192.168.0.1:8999带虚拟节点的代码实现
/** * 带虚拟节点的代码实现 */public class HashVirtualNodeTest { /** * 实际的服务器 */ private static String[] servers = {"192.168.0.1:8999","192.168.0.2:8999","192.168.0.0.3:8999"}; /** *每个服务节点对应的虚拟服务节点数目 */ private final static int virtualNode = 5; /** * 哈希环上的虚拟服务节点 * key 虚拟服务节点的hash值 * value 虚拟服务节点名称 */ private static SortedMap<Integer,String> virtualNodeMap = new TreeMap<Integer, String>(); static{ /** * 将虚拟节点放到virtualNodeMap中 * 虚拟节点与实际的服务器的对应关系 * 服务器名称：server * 虚拟节点名：server&&Node0 server&&Node1 server&&Node2 ... */ int len = servers.length; for (int i=0;i<len;i++){ for(int j=0;j<virtualNode;j++){ String virtualNodeName = servers[i]+"&&"+"Node"+j; Integer hash = Hash.FNV1_32_HASH(virtualNodeName); virtualNodeMap.put(hash,virtualNodeName); System.out.println("hash="+hash+" virtualNode=" +virtualNodeName); } } } /** * 获取一个节点对应的分配到的服务节点 * @param node 待查询的节点 * @return 实际的服务节点名称 */ public static String getServer(String node){ Integer hash = Hash.FNV1_32_HASH(node); //获取大于当前节点的虚拟节点服务器 SortedMap<Integer, String> tailMap = virtualNodeMap.tailMap(hash); Integer key = 0; if(virtualNodeMap.isEmpty()){ //没有大于当前节点的虚拟服务节点时，取虚拟服务节点的第一个 key = virtualNodeMap.firstKey(); }else{ //取出大于当前节点的第一个虚拟服务节点 key = tailMap.firstKey(); } //取出对应的虚拟节点 String virtualNode = virtualNodeMap.get(key); //获取实际的服务名称 String server = virtualNode.split("&&")[0]; return server; } public static void main(String[] args){ String[] index = {"582639584","582639585","582639586","582639587","582639588"}; System.out.println("------------------"); int size = index.length; for (int i=0;i<size;i++){ String server = getServer(index[i]); System.out.println("index="+index[i]+" hash="+ Hash.FNV1_32_HASH(index[i]) +" server="+server); } }}运行结果：
hash=350621948 virtualNode=192.168.0.1:8999&&Node0hash=2008701201 virtualNode=192.168.0.1:8999&&Node1hash=399766123 virtualNode=192.168.0.1:8999&&Node2hash=9572053 virtualNode=192.168.0.1:8999&&Node3hash=310503051 virtualNode=192.168.0.1:8999&&Node4hash=102010718 virtualNode=192.168.0.2:8999&&Node0hash=1966288165 virtualNode=192.168.0.2:8999&&Node1hash=1935085864 virtualNode=192.168.0.2:8999&&Node2hash=2058939177 virtualNode=192.168.0.2:8999&&Node3hash=1101158742 virtualNode=192.168.0.2:8999&&Node4hash=1042841091 virtualNode=192.168.0.0.3:8999&&Node0hash=1013102794 virtualNode=192.168.0.0.3:8999&&Node1hash=1097523199 virtualNode=192.168.0.0.3:8999&&Node2hash=384605107 virtualNode=192.168.0.0.3:8999&&Node3hash=1615270737 virtualNode=192.168.0.0.3:8999&&Node4------------------index=582639584 hash=1309097570 server=192.168.0.0.3:8999index=582639585 hash=583335179 server=192.168.0.0.3:8999index=582639586 hash=1918263339 server=192.168.0.2:8999index=582639587 hash=1873142797 server=192.168.0.2:8999index=582639588 hash=1040353541 server=192.168.0.0.3:8999