week5

用户头像
张兵
关注
发布于: 2020 年 10 月 25 日



作业一:

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

  2. 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。



package test;
import java.util.*;
public class HashTest {
private static List<String> cluster = new ArrayList<>();
private static int virtualNodeNum = 150;
private static Set<VirtualNode> virtualNodeSet = new TreeSet<>();
public static void main(String[] args) {
addRedisAddr("redis0");
addRedisAddr("redis1");
addRedisAddr("redis2");
addRedisAddr("redis3");
addRedisAddr("redis4");
addRedisAddr("redis5");
addRedisAddr("redis6");
addRedisAddr("redis7");
addRedisAddr("redis8");
addRedisAddr("redis9");
Map<String, Integer> countMap = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
String randomKey = getRandomString(10);
VirtualNode node = fetchVirtualNode(randomKey);
countMap.put(node.realAddr, countMap.getOrDefault(node.realAddr, 0)+1);
}
System.out.println(countMap);
System.out.println("标准差 = " + StandardDiviation(countMap.values()));
}
private static VirtualNode fetchVirtualNode(String key) {
VirtualNode firstNode = null;
Integer hash = stringToHash(key);
for (VirtualNode node : virtualNodeSet) {
if (node.hashValue > hash) return node;
if (firstNode == null) firstNode = node;
}
return firstNode;
}
private static void addRedisAddr(String addr) {
for (int i = 0; i < virtualNodeNum; i++) {
String virtualNodeId = "virtual-" + addr + "-" + i;
virtualNodeSet.add(new VirtualNode(virtualNodeId, addr, stringToHash(virtualNodeId)));
}
}
public static Integer stringToHash(String data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash > 0 ? hash : (0-hash);
}
//随机字符串
public static String getRandomString(int length){
String str="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
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();
}
//标准差σ=sqrt(s^2)
public static double StandardDiviation(Collection<Integer> x) {
int m=x.size();
double sum=0;
for(Integer i : x){//求和
sum+=i;
}
double dAve=sum/m;//求平均值
double dVar=0;
for(Integer i : x){//求方差
dVar+=(i-dAve)*(i-dAve);
}
//reture Math.sqrt(dVar/(m-1));
return Math.sqrt(dVar/m);
}
}
class VirtualNode implements Comparable<VirtualNode>{
public String nodeId;
public String realAddr;
public Integer hashValue;
public VirtualNode(String nodeId, String realAddr, Integer hashValue) {
this.nodeId = nodeId;
this.realAddr = realAddr;
this.hashValue = hashValue;
if (hashValue < 0)
System.out.println(this.toString());
}
@Override
public int compareTo(VirtualNode o) {
if (o == null) return 1;
return hashValue - o.hashValue;
}
@Override
public String toString() {
return "VirtualNode{" +
"nodeId='" + nodeId + '\'' +
", realAddr='" + realAddr + '\'' +
", hashValue=" + hashValue +
'}';
}
}



用户头像

张兵

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

发布
暂无评论
week5