「架构师训练营」第 5 周作业 - 一致性哈希算法

发布于: 14 小时前

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

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);
}
}

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

标准差按照如下公式计算:

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

第二次输出结果:

服务器分配情况:
服务器 [testServer-9] 分配到的次数:77205
服务器 [testServer-8] 分配到的次数:65832
服务器 [testServer-7] 分配到的次数:86361
服务器 [testServer-6] 分配到的次数:97514
服务器 [testServer-5] 分配到的次数:127939
服务器 [testServer-4] 分配到的次数:116683
服务器 [testServer-3] 分配到的次数:97518
服务器 [testServer-2] 分配到的次数:103946
服务器 [testServer-1] 分配到的次数:113379
服务器 [testServer-0] 分配到的次数:113623
标准差: 18233.18947962753

第三次输出结果:

服务器分配情况:
服务器 [testServer-9] 分配到的次数:77443
服务器 [testServer-8] 分配到的次数:65788
服务器 [testServer-7] 分配到的次数:87089
服务器 [testServer-6] 分配到的次数:97279
服务器 [testServer-5] 分配到的次数:127356
服务器 [testServer-4] 分配到的次数:115884
服务器 [testServer-3] 分配到的次数:97449
服务器 [testServer-2] 分配到的次数:103711
服务器 [testServer-1] 分配到的次数:113940
服务器 [testServer-0] 分配到的次数:114061
标准差: 18073.028495523376

标准差

标准差(Standard Deviation) ,是离均差平方的算术平均数的平方根,用σ表示。在概率统计中最常使用作为统计分布程度上的测量。标准差是方差的算术平方根。标准差能反映一个数据集的离散程度。平均数相同的两组数据,标准差未必相同。

用户头像

guoguo 👻

关注

还未添加个人签名 2017.11.30 加入

还未添加个人简介

评论

发布
暂无评论
「架构师训练营」第 5 周作业 - 一致性哈希算法