week5. 课后作业

发布于: 2020 年 07 月 08 日

用你熟悉的编程语言实现一致性 hash 算法。

package com.demo.hash;
import com.sun.xml.internal.ws.util.StringUtils;
import java.util.*;
public class hashConsistencyAlgorithm {
//10台待添加入Hash环的服务器列表
private static String[] servers = {"192.168.0.111","192.168.1.111","192.168.2.111","192.168.3.111","192.168.4.111",
"192.168.5.111","192.168.6.111","192.168.7.111","192.168.8.111","192.168.9.111"};
//真实节点列表
private static List<String> realNodes = new LinkedList<String>();
//虚拟节点列表
private static SortedMap<Integer,String> virtualMap = new TreeMap<Integer, String>();
//虚拟节点数
private static final int NUM_HOST = 10 ;
/**
* @description:使用FNV1_32_HASH算法计算服务器的Hash值
* @author:cd
* @param: str
* @return:int
* @time:2020/7/8 18:39
*/
private static int getHash(String str) {
// int hash = str.hashCode();
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;
}
/**
* @description:程序初始化把所有的服务器放入virtualMap中
* @author:cd
* @param: null
* @return:
* @time:2020/7/8 16:41
*/
static {
//添加真实节点
for(int i = 0 ; i < servers.length; i++){
realNodes.add(servers[i]);
}
//添加虚拟节点
for(String str : realNodes){
for(int i = 1; i<=NUM_HOST; i++){
String nodename = str + "VM" + String.valueOf(i);
//如果算出来的值为负数则取其绝对值
// int hash = Math.abs(nodename.hashCode());
int hash = getHash(nodename);
virtualMap.put(hash,nodename);
// System.out.println("虚拟节点hash:"+ hash +"["+nodename+"]放入");
}
}
}
/**
* @description:通过传入随机数获取应当路由到的结点的key
* @author:cd
* @param: key
* @return:
* @time:2020/7/8 16:58
*/
private static Integer getServer(String key){
//得到该key的hash值
// int hash = Math.abs(key.hashCode());
int hash = getHash(key);
//返回对应的服务器的key
Integer host_hash ;
//返回对应的服务器
String host;
//取出大于该hash值的所有Map
SortedMap<Integer,String> bigMap = virtualMap.tailMap(hash);
if(bigMap.isEmpty()){
//如果没有大于hash的值则取virtualMap第一个node
host_hash = virtualMap.firstKey();
host = virtualMap.get(host_hash);
}else {
//第一个Key就是顺时针过去离node最近的那个结点
host_hash = bigMap.firstKey();
//返回对应的服务器
host= bigMap.get(host_hash);
}
if(host != null && host.length() != 0){
//真实的服务器主机
String realHost = host.substring(0,host.indexOf("VM"));
// System.out.println(realHost);
// return realHost;
}
return host_hash;
}
/**
* @description:生成随机数来获取hash一致性算法返回的key
* @author:cd
* @param:
* @return:java.lang.String
* @time:2020/7/8 17:57
*/
private static Integer getKey() {
Random random = new Random();
int nextInt = random.nextInt(15);
nextInt = nextInt > 10 ? nextInt : 10;
char start = 'S';
String result = "";
for (int i = 0; i < nextInt; i++) {
int nextInt1 = random.nextInt(58);
result += (char)(start + nextInt1);
}
return getServer(result);
}
/**
* @description:标准差计算
* @author:cd
* @param: x
* @return:double
* @time:2020/7/7 21:06
*/
public static double StandardDiviation(Map<Integer, Integer> data) {
int machineSize = data.size();
long dataSize = 0L;
for (Integer value : data.values()) {
dataSize += value;
}
double averageSize = dataSize / machineSize;
long total = 0;
for (Integer value : data.values()) {
total += (value - averageSize) * (value - averageSize);
}
return Math.sqrt(total / (machineSize - 1));
}
/**
* @description:hash一致性标准差结果验证
* @author:cd
* @param: args
* @return:void
* @time:2020/7/7 21:08
*/
public static void main(String[] args) {
//测试100万KV数据,10个服务器节点的情况下,计算这些KV数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性
Map<Integer, Integer> data = new HashMap<Integer, Integer>();
for (int i = 0; i < 1000000; i++) {
int key = getKey();
data.put(key, key);
}
System.out.println(StandardDiviation(data));
}
}

小结:初步测试200的虚拟标准差值最低;

虚拟节点数:150,标准差: 78467344.74

虚拟节点数:200,标准差: 67994441.9

虚拟节点数:10, 标准差:305230034.7

用户头像

dj_cd

关注

还未添加个人签名 2019.08.09 加入

还未添加个人简介

评论

发布
暂无评论
week5. 课后作业