作业 -05-java 实现一致性 hash 算法

用户头像
梦子说
关注
发布于: 2020 年 07 月 08 日



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

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



package com.example.demo;
import java.util.*;
/**
* hash一致性算法
*/
public class HashUniformity {
public static String[] service = { "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"};
public static Map<Integer, String> nodeMap = new TreeMap<>();
static {
int vmNum = 200;//虚拟节点数量
//虚拟5个节点
for (int i = 0; i < service.length; i++) {
for (int j = 0; j < vmNum; j++) {
String vmService = service[i] + "&vm" + j;
int hash = getHash(vmService);
if (hash < 0)
hash = Math.abs(hash); //取绝对值
nodeMap.put(hash, vmService);
}
}
}
/**
* 获取服务地址
*
* @param url
* @return
*/
public static String getService(String url) {
int hash = getHash(url);
String service = "";
for (Integer key : nodeMap.keySet()) {
if (hash < key) {
service = nodeMap.get(key).substring(0, nodeMap.get(key).lastIndexOf("&vm"));
break;
}
}
return service;
}
/**
* 获取hash
*
* @param str
* @return
*/
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;
}
/**
* 生成随机字符串
* @param length
* @return
*/
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();
}
/**
* 求标准差
* @param array
* @return
*/
public static double getStandardDeviation(int[] array){
int sum = 0;
for(int i=0;i<array.length;i++){
sum += array[i]; //求出数组的总和
}
double average = sum/array.length; //求出数组的平均数
int total=0;
for(int i=0;i<array.length;i++){
total += (array[i]-average)*(array[i]-average); //求出方差,如果要计算方差的话这一步就可以了
}
double standardDeviation = Math.sqrt(total/array.length); //求出标准差
return standardDeviation;
}
public static void main(String[] arg) {
//统计每个服务器存储kv数量
int[] serviceCount = new int[service.length];
int count = 0;
for (int i = 0; i < 1000000; i++) {
String kv = getRandomString(20)+i;
String ser = getService(kv);
for(int j=0;j<service.length;j++){
if(ser.equals(service[j])){
++serviceCount[j];
}
}
}
for(int i=0;i<service.length;i++){
System.out.println(service[i]+"-->"+serviceCount[i]);
}
double standardDeviation = getStandardDeviation(serviceCount);
System.out.println("标准差:"+standardDeviation);
}
}

输出结果:

192.168.0.0:111-->92765

192.168.0.1:111-->107852

192.168.0.2:111-->117286

192.168.0.3:111-->97275

192.168.0.4:111-->93531

192.168.0.5:111-->99091

192.168.0.6:111-->96614

192.168.0.7:111-->92772

192.168.0.8:111-->99670

192.168.0.9:111-->102822

标准差:7312.154196951812



用户头像

梦子说

关注

还未添加个人签名 2018.12.01 加入

还未添加个人简介

评论

发布
暂无评论
作业-05-java实现一致性hash算法