写点什么

第五周命题作业

用户头像
冯凯
关注
发布于: 2020 年 07 月 08 日
  1. 用熟悉的编程语言实现一致性Hash算法

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



由于之前没有接触过后端的内容,属于小白,现阶只能参照同学的代码进行学习。



计算哈希值 使用CRC32方法



public class ConsistentHash {
/**
* 哈希环最大位置
*/
private static final Integer MAX_HASH_POSTION = Integer.MAX_VALUE;
/**
* 节点的虚拟节点数量
*/
private final int replicasCount;
/**
* Hash环
*/
private final SortedMap<Integer, String> hashCircle = new TreeMap<>();
/**
* 构造方法
*
* @param replicasCount 虚拟节点数量
* @param nodes 节点
*/
public ConsistentHash(int replicasCount, Collection<String> nodes) {
this.replicasCount = replicasCount;
nodes.stream().forEach(node -> {
add(node);
});
}
/**
* 添加节点
*
* @param node 节点名称
*/
public void add(String node) {
for (int i = 0; i < replicasCount; i++) {
int nodeHash = hash(node + "#" + i);
hashCircle.put(nodeHash, node);
}
}
/**
* 定位节点
*
* @param key 键值
* @return
*/
public String get(String key) {
if (hashCircle.isEmpty()) {
return null;
}
int hash = hash(key);
if (hashCircle.containsKey(hash)) {
return hashCircle.get(hash);
}
SortedMap<Integer, String> tailMap = hashCircle.tailMap(hash);
return hashCircle.get(tailMap.isEmpty() ? hashCircle.firstKey() : tailMap.firstKey());
}
/**
* 使用 CRC32 算法
*
* @param key
* @return
*/
public int hash(String key) {
CRC32 crc32 = new CRC32();
crc32.update(key.getBytes());
return (int) (crc32.getValue() % MAX_HASH_POSTION);
}
}



public class ConsistentHashTest {
/**
* 服务器节点数
*/
private static final Integer SERVER_COUNT = 10;
/**
* 统计server命中情况
*/
Map<String, Integer> serverAllocateCount = new HashMap<>();
/**
* 虚拟节点个数
*/
private static final Integer VIRTURAL_NODES_COUNT = 150;
/**
* 一致性哈希算法
*/
private ConsistentHash consistentHash;
private static final String source = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
/**
* 初始化一致性哈希算法的hash环
*/
@Before
public void init() {
List<String> nodes = new ArrayList<>();
for (int i = 0; i < SERVER_COUNT; i++) {
String server = "testServer-" + i;
serverAllocateCount.put(server, 0);
nodes.add(server);
}
consistentHash = new ConsistentHash(VIRTURAL_NODES_COUNT, nodes);
}
@Test
public void testBalance() {
// 模拟1000000次KV的请求,请求的key随机
for (int i = 0; i < 1000000; i++) {
String server = consistentHash.get(randomString(8));
Integer count = serverAllocateCount.get(server);
serverAllocateCount.put(server, ++count);
}
// 打印落到各个服务器的数量
printServerAllocate(serverAllocateCount);
// 标准差
System.out.println("标准差: " + standardDeviation(serverAllocateCount.entrySet().stream().map(entry -> entry.getValue()).collect(Collectors.toList())));
}
/**
* 生成随机字符串
*
* @param length 字符串长度
* @return
*/
public String randomString(int length) {
StringBuffer sb = new StringBuffer();
Random random = new Random();
for (int i = 0; i < length; i++) {
int number = random.nextInt(62);
sb.append(source.charAt(number));
}
return sb.toString();
}
/**
* 打印分布情况
*
* @param serverAllocateCount
* @return
*/
private void printServerAllocate(Map<String, Integer> serverAllocateCount) {
System.out.println("服务器分配情况:");
for (Map.Entry<String, Integer> entry : serverAllocateCount.entrySet()) {
System.out.println(String.format("服务器 [%s] 分配到的次数:%d", entry.getKey(), entry.getValue()));
}
}
/**
* 标准差计算
* σ=sqrt(s^2/n)
*
* @param input
* @return
*/
private double standardDeviation(List<Integer> input) {
int length = input.size();
if (length == 0) {
return 0;
}
// 和
double sum = 0;
for (Integer num : input) {
sum += num;
}
// 平均值
double average = sum / length;
// 方差
double s = 0;
for (Integer num : input) {
s += ((num - average) * (num - average));
}
return Math.sqrt(s / length);
}
}



服务器分配情况:
服务器[testServer-9]分配到的次数:77199
服务器[testServer-8]分配到的次数:65765
服务器[testServer-7]分配到的次数:86737
服务器[testServer-6]分配到的次数:97315
服务器[testServer-5]分配到的次数:127551
服务器[testServer-4]分配到的次数:116312
服务器[testServer-3]分配到的次数:97729
服务器[testServer-2]分配到的次数:104425
服务器[testServer-1]分配到的次数:113640
服务器[testServer-0]分配到的次数:113327
标准差: 18134.422406021098



用户头像

冯凯

关注

还未添加个人签名 2020.05.26 加入

还未添加个人简介

评论

发布
暂无评论
第五周命题作业