【架构师训练营 - week5 -1】作业

发布于: 2020 年 07 月 08 日
【架构师训练营 - week5 -1】作业

一致性hash算法

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

import org.apache.commons.lang3.RandomStringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
public class ConsistentHashTest {
@Test
public void test() {
List<String> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
String key = RandomStringUtils.randomAlphanumeric(10);
list.add(key);
}
ConsistentHash consistentHash = new ConsistentHash();
consistentHash.consistent(list);
}
}

import com.google.common.hash.Hashing;
import java.nio.charset.Charset;
import java.util.*;
public class ConsistentHash {
static List<String> servers = new ArrayList<>();
static Map<Integer, Integer> map = new TreeMap<>();
public void consistent(List<String> keys) {
init();
for (String server : servers) {
for (int i = 0; i < 100; i++) {
String vm = server + "#" + i;
map.put(Hashing.murmur3_32().hashString(vm, Charset.forName("utf-8")).asInt(), 0);
}
}
for (String key : keys) {
for (Integer i : map.keySet()) {
if (Hashing.murmur3_32().hashString(key, Charset.forName("utf-8")).asInt() < i) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
}
int[] data = new int[map.keySet().size()];
int i = 0;
for (int key : map.keySet()) {
data[i++] = map.get(key);
}
System.out.println(standardDeviation(data));
}
public void init() {
for (int i = 0; i < 10; i++) {
servers.add("192.168.0." + i);
}
}
public static double standardDeviation(int[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {
sum += x[i];
}
double dAve = sum / m;
double dVar = 0;
for (int i = 0; i < m; i++) {
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return Math.sqrt(dVar / m);
}
public static void main(String[] args) {
Map<Integer, Integer> map1 = new TreeMap<>();
map1.put(5,2);
map1.put(3,2);
map1.put(1,2);
map1.put(2,2);
for (Integer i : map1.keySet()){
System.out.println(i);
}
}
}

用户头像

早睡早起

关注

还未添加个人签名 2019.09.05 加入

还未添加个人简介

评论

发布
暂无评论
【架构师训练营 - week5 -1】作业