实现一致性 hash 算法

发布于: 2020 年 07 月 08 日
实现一致性 hash 算法

作业一:

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

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


执行结果:

模拟1000000PV,10台服务器,每台设置1个虚拟节点,一致性哈希标准差:75637.51284176979
模拟1000000PV,10台服务器,每台设置10个虚拟节点,一致性哈希标准差:65129.27425598347
模拟1000000PV,10台服务器,每台设置100个虚拟节点,一致性哈希标准差:41379.10907692431
模拟1000000PV,10台服务器,每台设置1000个虚拟节点,一致性哈希标准差:38959.18034444656

测试类:

package architect.hash;
import org.apache.commons.lang3.StringUtils;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
/**
* @auther: songdewei
* @date: 2020/7/8
*/
public class Client {
//待添加入Hash环的服务器列表
private static String[] servers = {"192.168.0.0:100",
"192.168.0.1:100",
"192.168.0.2:100",
"192.168.0.3:100",
"192.168.0.4:100",
"192.168.0.5:100",
"192.168.0.6:100",
"192.168.0.7:100",
"192.168.0.8:100",
"192.168.0.9:100"};
//真实节点列表
private static List<String> realNodes = new LinkedList<>();
//虚拟节点列表
private static SortedMap<Integer, String> sortedMap;
//虚拟节点列表
private static LinkedHashMap<String, Integer> countMap;
@Before
public void before() {
//添加真实节点
for (int i = 0; i < servers.length; i++) {
realNodes.add(servers[i]);
}
}
public void init(int serverVMNum) {
//添加真实节点
countMap = new LinkedHashMap<>();
for (int i = 0; i < servers.length; i++) {
countMap.put(servers[i], 1);
}
sortedMap = new TreeMap<>();
//添加虚拟节点
for (String str : realNodes) {
for (int i = 1; i <= serverVMNum; i++) {
String nodeName = str + "VM" + String.valueOf(i);
int hash = nodeName.hashCode();
sortedMap.put(hash, nodeName);
// System.out.println("虚拟节点hash:" + hash + "【" + nodeName + "】放入");
}
}
}
private String getHost(String vmhost){
if (StringUtils.isNotBlank(vmhost)) {
String realHost = vmhost.substring(0, vmhost.indexOf("VM"));
return realHost;
}
return null;
}
public void simulateConsistentHash(int vmNum, int pv) {
init(vmNum);
for (int i = 0; i < pv; i++) {
String key = Util.getRandomString(40);
String vmhost = ConsistentHash.getServer(key, sortedMap);
String serverHost = getHost(vmhost);
Integer num = countMap.get(serverHost);
countMap.put(serverHost, num + 1);
}
double[] array = new double[countMap.size()];
for (int i = 0; i < servers.length; i++) {
array[i] = countMap.get(servers[i]);
}
double result = Util.Sample_STD_dev(array);
// System.out.println("模拟"+pv + "PV,10台服务器,每台设置"+vmNum+"个虚拟节点,一致性哈希计数:" + countMap);
System.out.println("模拟" + pv + "PV,10台服务器,每台设置" + vmNum + "个虚拟节点,一致性哈希标准差:" + result);
System.out.println();
}
@Test
public void test() {
simulateConsistentHash(1, 1000000);
simulateConsistentHash(10, 1000000);
simulateConsistentHash(100, 1000000);
simulateConsistentHash(1000, 1000000);
}
}

一致性哈希:

package architect.hash;
import java.util.SortedMap;
/**
* 一致性哈希算法
* @auther: songdewei
* @date: 2020/7/8
*/
public class ConsistentHash {
//得到应当路由到的结点
public static String getServer(String key, SortedMap<Integer, String> sortedMap) {
//得到该key的hash值
int hash = key.hashCode();
//得到大于该Hash值的所有Map
String host;
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if (subMap.isEmpty()) {
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
host = sortedMap.get(i);
} else {
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
host = subMap.get(i);
}
return host;
}
}

工具类

package architect.hash;
import java.util.Random;
/**
* 工具类
* @auther: songdewei
* @date: 2020/7/8
*/
public class Util {
// sample standard deviation 样本标准差
public static double Sample_STD_dev(double[] data) {
double std_dev;
std_dev = Math.sqrt(Sample_Variance(data));
return std_dev;
}
//sample variance 样本方差
public static double Sample_Variance(double[] data) {
double variance = 0;
for (int i = 0; i < data.length; i++) {
variance = variance + (Math.pow((data[i] - Mean(data)), 2));
}
variance = variance / (data.length - 1);
return variance;
}
public static double Mean(double[] data) {
double mean = 0;
mean = Sum(data) / data.length;
return mean;
}
public static double Sum(double[] data) {
double sum = 0;
for (int i = 0; i < data.length; i++) {
sum = sum + data[i];
}
return sum;
}
//length用户要求产生字符串的长度
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(32);
sb.append(str.charAt(number));
}
return sb.toString();
}
}

发布于: 2020 年 07 月 08 日 阅读数: 7
用户头像

戴维斯

关注

还未添加个人签名 2018.08.24 加入

还未添加个人简介

评论

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