package com.suke.hystrix;
import java.util.*;
/**
* 带虚拟节点的一致性Hash算法
*/
public class ConsistentHashingWithoutVirtualNode {
static String str="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
static int KEY_LENGTH = 10;
static int KEY_COUNT = 1000000;
//待添加入Hash环的服务器列表
private static String[] servers = {
"192.168.0.0:111",
"192.168.0.1:111",
"192.168.0.2:111",
"192.168.0.3:111",
"192.168.0.4:111",
"192.168.0.5:111",
"192.168.0.6:111",
"192.168.0.7:111",
"192.168.0.8:111",
"192.168.0.9:111"};
//真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
private static List<String> realNodes = new LinkedList<String>();
//虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
//虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应10个虚拟节点
private static final int VIRTUAL_NODES = 10;
static{
//先把原始的服务器添加到真实结点列表中
for(int i=0; i<servers.length; i++)
realNodes.add(servers[i]);
//再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
for (String str : realNodes){
for(int i=0; i<VIRTUAL_NODES; i++){
String virtualNodeName = str + "&&VN" + String.valueOf(i);
int hash = getHash(virtualNodeName);
System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
System.out.println();
}
//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
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;
}
//得到应当路由到的结点
private static String getServer(String key){
//得到该key的hash值
int hash = getHash(key);
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNode;
if(subMap.isEmpty()){
//如果没有比该key的hash值大的，则从第一个node开始
Integer i = virtualNodes.firstKey();
//返回对应的服务器
virtualNode = virtualNodes.get(i);
}else{
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
virtualNode = subMap.get(i);
}
//virtualNode虚拟节点名称要截取一下
if(virtualNode != null && !"".equals(virtualNode)){
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
return null;
}
public static void main(String[] args){
Map<String,Integer> db = new HashMap<>();
for(int i = 0;i < KEY_COUNT;i ++){
String key = getRandomString(KEY_LENGTH);
String server = getServer(key);
Integer count = db.getOrDefault(server,0);
db.put(server,count+1);
}
double[] valArr = db.values().stream().mapToDouble(value -> value.doubleValue()).toArray();
System.out.println("节点hash分布:");
db.forEach((key,val)->{
System.out.println(" server: " + key+" 数据量:"+val);
});
System.out.println("数据分布标准差:" + StandardDiviation(KEY_COUNT,valArr));
}
public static double StandardDiviation(double sum ,double[] x) {
int m=x.length;
double dAve=sum/m;//求平均值
double dVar=0;
for(int i=0;i<m;i++){//求方差
dVar+=(x[i]-dAve)*(x[i]-dAve);
}
//reture Math.sqrt(dVar/(m-1));
return Math.sqrt(dVar/m);
}
public static String getRandomString(int length){
Random random=new Random();
StringBuffer sb=new StringBuffer();
for(int i=0;i<length;i++){
int number=random.nextInt(62);
sb.append(str.charAt(number));
}
return sb.toString();
}
}
评论