一致性算法实现

用户头像
罗亮
关注
发布于: 2020 年 07 月 05 日

关键点: 存储服务器节点的容器类型决定 `一致性hash算法` 的性能。

1. ArrayList 查找的时间复杂度O(n)

2. LinkedList 查找时间复杂度O(n)

3. TreeMap 时间复杂度O(log^n)

so , 选用 TreeMap是比较好的选择



关键点: 虚拟节点 , 使用虚拟节点使得分布更加的均衡



public class ConsistenceHashWithVnNode {
private static final String VN_FLAG = "&&vn";
/** 真实节点 */
private List<String> realNodes;
/** 虚拟节点的数量 */
private int vnNodeCount;
/** 虚拟节点 */
private TreeMap<Integer,String> vnNodes = new TreeMap<Integer, String>();
public ConsistenceHashWithVnNode(List<String> realNodes,int vnNodeCount){
this.realNodes = realNodes;
this.vnNodeCount = vnNodeCount;
// 初始化
initVnNode();
}
private void initVnNode() {
for (String realNode : realNodes) {
for (int i = 0; i < vnNodeCount; i++) {
String vnNodeName = realNode + VN_FLAG;
int hash = getHash(vnNodeName);
vnNodes.put(hash,vnNodeName);
System.out.println("添加虚拟节点 hash = "+hash+", vnNodeName = "+ vnNodeName);
}
}
}
/** 使用FNV1_32_HASH算法计算服务器的Hash值 */
private 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 String getServer(String node){
int hash = getHash(node);
Map.Entry<Integer, String> entry = vnNodes.ceilingEntry(hash);
if(entry == null){
entry = vnNodes.firstEntry();
}
String vnNode = entry.getValue();
return vnNode.substring(0,vnNode.lastIndexOf(VN_FLAG));
}
}



测试代码如下:

public class Test {
public static void main(String[] args) {
List<String> servers = new LinkedList<>();
servers.add("192.168.0.1:111");
servers.add("192.168.0.2:111");
servers.add("192.168.0.3:111");
servers.add("192.168.0.4:111");
servers.add("192.168.0.5:111");
ConsistenceHashWithVnNode consistenceHashWithVnNode = new ConsistenceHashWithVnNode(servers, 10000);
int count = 1000000;
Map<String,Integer> map = new HashMap<>();
for (int i = 0; i < count; i++) {
String randomIp = getRandomIp();
String server = consistenceHashWithVnNode.getServer(randomIp);
doCount(map,server);
}
map.forEach((key,value)->{
System.out.println("server: "+key+", count = "+ value );
});
}
public static String getRandomIp() {
// ip范围
int[][] range = {
{607649792, 608174079}, // 36.56.0.0-36.63.255.255
{1038614528, 1039007743}, // 61.232.0.0-61.237.255.255
{1783627776, 1784676351}, // 106.80.0.0-106.95.255.255
{2035023872, 2035154943}, // 121.76.0.0-121.77.255.255
{2078801920, 2079064063}, // 123.232.0.0-123.235.255.255
{-1950089216, -1948778497}, // 139.196.0.0-139.215.255.255
{-1425539072, -1425014785}, // 171.8.0.0-171.15.255.255
{-1236271104, -1235419137}, // 182.80.0.0-182.92.255.255
{-770113536, -768606209}, // 210.25.0.0-210.47.255.255
{-569376768, -564133889}, // 222.16.0.0-222.95.255.255
};
Random random = new Random();
int index = random.nextInt(10);
String ip = num2ip(range[index][0] + new Random().nextInt(range[index][1] - range[index][0]));
return ip;
}
/*
* 将十进制转换成IP地址
*/
public static String num2ip(int ip) {
int[] b = new int[4];
String ipStr = "";
b[0] = (int) ((ip >> 24) & 0xff);
b[1] = (int) ((ip >> 16) & 0xff);
b[2] = (int) ((ip >> 8) & 0xff);
b[3] = (int) (ip & 0xff);
ipStr = Integer.toString(b[0]) + "." + Integer.toString(b[1]) + "." + Integer.toString(b[2]) + "." + Integer.toString(b[3]);
return ipStr;
}
private static void doCount(Map<String,Integer> map , String server) {
Integer count = map.getOrDefault(server, 0);
map.put(server,count+1);
}
}



测试效果

server: 192.168.0.1:111, count = 383832
server: 192.168.0.2:111, count = 8760
server: 192.168.0.3:111, count = 331552
server: 192.168.0.4:111, count = 199585
server: 192.168.0.5:111, count = 76271

感觉不够均衡,emm..



用户头像

罗亮

关注

种树最好的时间是十年前,其次是现在。 2017.09.10 加入

神秘的程序猿

评论

发布
暂无评论
一致性算法实现