架构师训练营 - 作业 - 第五周

用户头像
Max2@12
关注
发布于: 2020 年 10 月 25 日
  1. 用你熟悉的编程语言实现一致性 hash 算法。

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



一致性Hash算法实现

package love.luke.architect.demo;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.UUID;
import java.util.Map.Entry;
import lombok.extern.slf4j.Slf4j;
@Slf4j
public class ConsistentHashRouter {
/**
* 虚拟节点的放大比例,真实节点数:虚拟节点数 = 1:virtualTime
*/
private int virtualTimes;
/**
* 真实节点的IP清单列表,真实节点的位置餐宿格式为ip:prot
*/
private String[] serversIp;
/**
* 由serversIps 真实节点的IP清单列表转换而来的List, 后续便于增删
*/
private List<String> realNodes;
/**
* 虚拟节点构成的哈希环,使用TreeMap,后续查找节点方便
*/
private TreeMap<Integer, String> virtualNodes;
public ConsistentHashRouter(int virtualTimes, String[] serversIp) {
if (null == serversIp || serversIp.length == 0)
throw new IllegalArgumentException("输入服务器清单不能为空");
this.serversIp= serversIp;
this.virtualTimes = virtualTimes;
realNodes = new LinkedList<String>();
for(String ip : serversIp ) {
realNodes.add(ip);
}
//为每个固定节点,生成哈希环上的虚拟节点
virtualNodes = new TreeMap<Integer, String>();
for(String realNode : realNodes) {
for (int i=0; i<virtualTimes; i++) {
// 采用随机UUID的hash为虚拟节点位置
int key = getHash(UUID.randomUUID().toString());
virtualNodes.put(key, realNode);
}
}
}
/**
* 计算输入字符串对应的hash值
* @param str
* @return 哈希值
*/
private int getHash(String str) {
// 先暂时使用内置的Hash算法,后续可以更换算法以达到更好的效果
return str.hashCode();
}
/**
* 根据传入的Key,得到对应的实际服务节点
* @param key
* @return
*/
public synchronized String getServer(String key) {
// 计算查询Key的hash
int hashOfKey = getHash(key);
// 在哈希环上向后找到大于查询Key的hash 的最近的一个虚拟节点
Entry<Integer, String> entry = virtualNodes.ceilingEntry(hashOfKey);
// 因为是哈希环,所以当向后上找不到比当前查询Key hash大的节点,则循环返回第一个虚拟节点
if (null == entry) {
entry = virtualNodes.firstEntry();
}
return entry.getValue();
}
/**
* 增加实际真实节点
* @param newServerIp
*/
public synchronized void addServer(String newServerIp) {
realNodes.add(newServerIp);
for (int i=0; i<virtualTimes; i++) {
int key = getHash(UUID.randomUUID().toString());
virtualNodes.put(key, newServerIp);
}
}
}



测试用例

import static org.junit.Assert.*;
import java.util.HashMap;
import java.util.UUID;
import java.util.Map.Entry;
import love.luke.architect.demo.ConsistentHashRouter;
import org.junit.Test;
public class ConsistentHashRouterTest {
@Test
public void test() {
final int TEST_CASE_AMOUNT = 1000000;
String seversIp[] = { "10.0.0.0", "10.0.0.1", "10.0.0.2", "10.0.0.3",
"10.0.0.4", "10.0.0.5", "10.0.0.6", "10.0.0.7",
"10.0.0.8", "10.0.0.9" };
// 10个实体服务器,每个服务器对应100个虚拟节点
ConsistentHashRouter router = new ConsistentHashRouter(10, seversIp);
// 计数器,统计每个真实Server被命中的次数
HashMap<String, Long> counterMap = new HashMap<>();
// 随机生成100万个UUID作为key进行测试,记录分实际存储节点被命中选取出来的数量
for (int i = 0; i < TEST_CASE_AMOUNT; i++) {
String key = UUID.randomUUID().toString();
String ip = router.getServer(key);
Long counter = counterMap.get(ip);
if (counter == null)
counterMap.put(ip, 1L);
else
counterMap.put(ip, counter + 1);
}
// 计算10个实际节点被命中次数的方差
long sum = 0;
double average = 0;
for (Entry<String, Long> counterEntry : counterMap.entrySet()) {
System.out.println(counterEntry.getKey() + " :"
+ counterEntry.getValue());
sum = sum + counterEntry.getValue();
}
average = sum / counterMap.keySet().size() ;
System.out.println("average:" + average);
double deviation = 0;
for (Entry<String, Long> counterEntry : counterMap.entrySet()) {
deviation = deviation + Math.pow(counterEntry.getValue() - average, 2);
}
System.out.println("Standard Deviation:" + Math.sqrt(deviation/counterMap.keySet().size()));
}
}



测试结果

当 实际节点:虚拟节点 = 1:10, 测试结果如下

10.0.0.8 :106954
10.0.0.7 :53143
10.0.0.9 :106018
10.0.0.4 :85179
10.0.0.3 :109442
10.0.0.6 :100047
10.0.0.5 :87724
10.0.0.0 :151591
10.0.0.2 :128801
10.0.0.1 :71101
Standard Deviation:26581.8542656452




当 实际节点:虚拟节点 = 1:100, 测试结果如下。 标准差明显变小,数据分布更加均匀了

10.0.0.8 :106176
10.0.0.7 :104553
10.0.0.9 :81190
10.0.0.4 :99238
10.0.0.3 :93703
10.0.0.6 :112491
10.0.0.5 :103025
10.0.0.0 :91412
10.0.0.2 :101293
10.0.0.1 :106919
average:100000.0
Standard Deviation:8610.433194677256



用户头像

Max2@12

关注

还未添加个人签名 2018.12.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 作业 - 第五周