写点什么

hash 一致性算法

发布于: 2020 年 10 月 25 日

不太会写,借鉴网上的写法。

作业一:

hash一致性算法:

package learn;

import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashing {
private SortedMap<Integer, String> virtualNodes = new TreeMap<>();

public ConsistentHashing(String[] serverList, int virtualNodeCount){
for(String server: serverList) {
for(int i = 0; i< virtualNodeCount; i++){
String virtualName = server + "@" + i;
int hash = getHash(virtualName);
this.virtualNodes.put(hash, virtualName);
}
}
}
public String getServer(String key){
String virtualNode;
int hash = getHash(key);
SortedMap<Integer, String> subMap = this.virtualNodes.tailMap(hash);
if(subMap.isEmpty()){
int nodeKey = this.virtualNodes.firstKey();
virtualNode = this.virtualNodes.get(nodeKey);
}else{
virtualNode = this.virtualNodes.get(subMap.firstKey());
}
return virtualNode.substring(0, virtualNode.indexOf("@"));
}

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;
}
}




import learn.ConsistentHashing;

import java.util.*;

public class HelloWorld {
static ArrayList<String> arrayList;
public static void main(String[] args){
String[] serverList = {"192.168.3.30","192.168.3.31", "192.168.3.32", "192.168.3.33","192.168.3.34",
"192.168.3.35", "192.168.3.36", "192.168.3.37", "192.168.3.38", "192.168.3.39"};
Map<String, Integer> countMap = new HashMap<>();
ConsistentHashing consistentHashing = new ConsistentHashing(serverList, 150);
for(int i=0; i<1000000; i++){
String server = consistentHashing.getServer("test" + i);
if (countMap.containsKey(server)){
Integer count = countMap.get(server);
countMap.put(server, count+1);
}else{
countMap.put(server, 1);
}
}
double value = getStandardDeviation(countMap, 100000, 10);
System.out.println(countMap.toString());
System.out.println("标准差为:" + value);
}

public static double getStandardDeviation(Map<String,Integer> countMap, int avg, int count){
int total = 0;
for(Map.Entry<String,Integer> entry : countMap.entrySet()){
total += (entry.getValue() - avg) *(entry.getValue() - avg);
}
return Math.sqrt(total/count);
}
}



结果如下:

{192.168.3.33=94782, 192.168.3.34=104174, 192.168.3.31=109043, 192.168.3.32=95856, 192.168.3.37=90406, 192.168.3.38=91963, 192.168.3.35=102462, 192.168.3.36=87834, 192.168.3.39=109191, 192.168.3.30=114289}

标准差为:8619.510368924675

感觉分布不是很均匀。



作业二:

本周主要学习了三个方面:

1、缓存。讲述了缓存在各个领域的使用方式和原理。分析了memcached缓存的实现原理,以及盲目扩展可能引起的雪崩问题。之后讲解了hash一致性算法的原理。

2、消息队列。讲述了消息队列在实际中的作用和好处。

3、负载均衡。学习了集中负载均衡的原理和算法。

用户头像

还未添加个人签名 2020.04.23 加入

还未添加个人简介

评论

发布
暂无评论
hash一致性算法