一致性哈希算法 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:8999
hash=1451861892 server=192.168.0.2:8999
hash=1078738565 server=192.168.0.0.3:8999
-------------
index=582639584 hash=1309097570 server=192.168.0.2:8999
index=582639585 hash=583335179 server=192.168.0.0.3:8999
index=582639586 hash=1918263339 server=192.168.0.1:8999
index=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&&Node0
hash=2008701201 virtualNode=192.168.0.1:8999&&Node1
hash=399766123 virtualNode=192.168.0.1:8999&&Node2
hash=9572053 virtualNode=192.168.0.1:8999&&Node3
hash=310503051 virtualNode=192.168.0.1:8999&&Node4
hash=102010718 virtualNode=192.168.0.2:8999&&Node0
hash=1966288165 virtualNode=192.168.0.2:8999&&Node1
hash=1935085864 virtualNode=192.168.0.2:8999&&Node2
hash=2058939177 virtualNode=192.168.0.2:8999&&Node3
hash=1101158742 virtualNode=192.168.0.2:8999&&Node4
hash=1042841091 virtualNode=192.168.0.0.3:8999&&Node0
hash=1013102794 virtualNode=192.168.0.0.3:8999&&Node1
hash=1097523199 virtualNode=192.168.0.0.3:8999&&Node2
hash=384605107 virtualNode=192.168.0.0.3:8999&&Node3
hash=1615270737 virtualNode=192.168.0.0.3:8999&&Node4
------------------
index=582639584 hash=1309097570 server=192.168.0.0.3:8999
index=582639585 hash=583335179 server=192.168.0.0.3:8999
index=582639586 hash=1918263339 server=192.168.0.2:8999
index=582639587 hash=1873142797 server=192.168.0.2:8999
index=582639588 hash=1040353541 server=192.168.0.0.3:8999