【架构思维学习】 week05

发布于: 2020 年 07 月 08 日

一致性哈希,含虚拟节点

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

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

1.基本实现

创建TreeMap<Integer,Server>存放虚拟节点,其中不同的Integer可以指向同一个server;

问题:如果有新的server加入,如何扩容?

构建方法:sortedMap,顺时针找到hashcode对应的server节点

1 使用java内置的String.hashcode(),没有对hashcode取绝对值

hash算法

private int hash(String s) {
return s.hashCode();
}

server node counts:10000
max:999940
min:2
sum:1000000
server:192.168.50.106 contains 7 clinets
server:192.168.50.105 contains 10 clinets
server:192.168.50.104 contains 9 clinets
server:192.168.50.103 contains 6 clinets
server:192.168.50.109 contains 8 clinets
server:192.168.50.108 contains 4 clinets
server:192.168.50.107 contains 2 clinets
server:192.168.50.102 contains 8 clinets
server:192.168.50.101 contains 6 clinets
server:192.168.50.100 contains 999940 clinets
stdev:299980.0000083339

2 使用java内置的String.hashcode(),对hashcode取绝对值

hash算法

private int hash(String s) {
return Math.abs(s.hashCode());
}

server node counts:10000
max:999891
min:7
sum:1000000
server:192.168.50.106 contains 8 clinets
server:192.168.50.105 contains 12 clinets
server:192.168.50.104 contains 7 clinets
server:192.168.50.103 contains 18 clinets
server:192.168.50.109 contains 999891 clinets
server:192.168.50.108 contains 10 clinets
server:192.168.50.107 contains 14 clinets
server:192.168.50.102 contains 15 clinets
server:192.168.50.101 contains 13 clinets
server:192.168.50.100 contains 12 clinets
stdev:299963.6666824834

3 使用google 的guava工具的hash方法

server node counts:10000
max:103727
min:96225
sum:1000000
server:192.168.50.106 contains 98174 clinets
server:192.168.50.105 contains 98903 clinets
server:192.168.50.104 contains 101552 clinets
server:192.168.50.103 contains 96225 clinets
server:192.168.50.109 contains 98639 clinets
server:192.168.50.108 contains 103427 clinets
server:192.168.50.107 contains 101423 clinets
server:192.168.50.102 contains 103727 clinets
server:192.168.50.101 contains 96306 clinets
server:192.168.50.100 contains 101624 clinets
stdev:2588.2838716029587

可见hash方法的好坏是决定算法 好坏的关键。

2. 全部代码

import java.util.*;
import com.google.common.base.Charsets;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
public class ConsistentHash2 {
private int serverCounts = 10;
private int serverVirtualNodes = 1000;
public int getServerCounts() {
return serverCounts;
}
public void setServerCounts(int serverCounts) {
this.serverCounts = serverCounts;
}
public int getServerVirtualNodes() {
return serverVirtualNodes;
}
public void setServerVirtualNodes(int serverVirtualNodes) {
this.serverVirtualNodes = serverVirtualNodes;
}
private int hash(String s) {
HashFunction hashFunction = Hashing.murmur3_128(13);
return hashFunction.hashString(s, Charsets.UTF_8).hashCode();
}
public static void main(String[] args) {
ConsistentHash2 consistentHash = new ConsistentHash2();
SortedMap<Integer, String> serverMap = new TreeMap<>();
Map<String, Integer> countsMap = new HashMap<>();
String[] servers = new String[consistentHash.getServerCounts()];
for (int i = 0; i < servers.length; i++) {
String server = "192.168.50.10" + i;
servers[i] = server;
countsMap.put(server, 0);
for (int j = 0; j < consistentHash.getServerVirtualNodes(); j++) {
int hash = consistentHash.hash(server + j);
serverMap.put(hash, server);
}
}
System.out.println("server node counts:" + serverMap.size());
int clientCounts = 1000* 1000;
for (int i = 0; i < clientCounts; i++) {
String clientIp = UUID.randomUUID().toString();
// int clientHash = Math.abs(clientIp.hashCode());
int clientHash = consistentHash.hash(clientIp);
// System.out.println(clientHash);
SortedMap<Integer, String> integerStringSortedMap = serverMap.tailMap(clientHash);
Integer firstKey;
if(integerStringSortedMap.isEmpty()) {
// 取哈希环上的顺时针第一台服务器
firstKey = serverMap.firstKey();
// System.out.println("==========>>>>客户端:" + client + " 被路由到服务器:" + hashServerMap.get(firstKey));
}else{
firstKey = integerStringSortedMap.firstKey();
// System.out.println("==========>>>>客户端:" + client + " 被路由到服务器:" + hashServerMap.get(firstKey));
}
String server = serverMap.get(firstKey);
countsMap.put(server, countsMap.get(server) + 1);
}
double mean = clientCounts / consistentHash.getServerCounts();
Collection<Integer> values = countsMap.values();
System.out.println("max:" + Collections.max(values));
System.out.println("min:" + Collections.min(values));
System.out.println("sum:" + values.stream().mapToInt(v -> v.intValue()).sum());
double powSum = 0.0;
Object[] counts = values.toArray();
for (String key: countsMap.keySet()) {
double powi = Math.pow(Math.abs(countsMap.get(key) - mean), 2);
powSum += powi;
System.out.println("server:" + key + " contains " + countsMap.get(key) + " clinets");
}
double stdev = Math.sqrt(powSum / consistentHash.getServerCounts());
System.out.println("stdev:" + stdev);
}
}

用户头像

chun1123

关注

还未添加个人签名 2018.03.09 加入

还未添加个人简介

评论

发布
暂无评论
【架构思维学习】 week05