架构师训练营 No.5 周作业

用户头像
连增申
关注
发布于: 2020 年 07 月 08 日
  • 用熟悉的编程语言实现一致性 hash 算法。

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



一致性Hash算法是对2^32取模。简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下:



整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1, 0和2^32-1在零点中方向重合,我们把这个由2^32个点组成的圆环称为Hash环

一致性Hash算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题,例如系统中只有两台服务器,其环分布如下: 



 

此时必然造成大量数据集中到Node A上,而只有极少量会定位到Node B上。为了解决这种数据倾斜问题,一致性Hash算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。

代码_Hash算法:

public class HashUtils {
private static final long PSART = 16777619L;
private static final long PMULT = 2166136261L;
public static long getHash(String str) {
long p = PSART;
long hash = PMULT;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
}

代码_标准差:

public class MathUtils {
public static double standardDiviation(int[] x) {
int m = x.length;
int sum = 0;
// 求和
for (int i = 0; i < m; i++) {
sum += x[i];
}
// 求平均值
int dAve = sum / m;
int dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += Math.pow(x[i] - dAve, 2);
}
return Math.sqrt(dVar / m);
}
}

一致性HASH算法:

public class ConsistentHashing {
private List<String> realNodes = new LinkedList<String>();
private SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
private int virtualNum = 0;
public ConsistentHashing() {
}
public ConsistentHashing(List<String> nodes, int virtualNum) {
realNodes.addAll(nodes);
this.virtualNum = virtualNum;
init();
}
public ConsistentHashing(Map<String, Integer> nodes) {
realNodes.addAll(nodes.keySet());
}
public void init() {
sortedMap.clear();
for (String node : realNodes) {
String realNode = node + "_0";
sortedMap.put((int) HashUtils.getHash(realNode), realNode);
for (int i = 1; i <= virtualNum; i++) {
String virtualNode = node + "_" + String.valueOf(i);
sortedMap.put( (int) HashUtils.getHash(virtualNode), virtualNode);
}
}
}
public String getServer(String node) {
int hash = (int) HashUtils.getHash(node);
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if(!subMap.isEmpty()) {
Integer i = subMap.firstKey();
String virtualNode = subMap.get(i);
return virtualNode.substring(0, virtualNode.indexOf("_"));
}
return realNodes.get(0);
}
public int getVirtualNum() {
return virtualNum;
}
public void setVirtualNum(int virtualNum) {
this.virtualNum = virtualNum;
}
public List<String> getRealNodes() {
return realNodes;
}
public void addNode(String node) {
realNodes.add(node);
}
public void removeNode(String node) {
realNodes.remove(node);
}
}



测试代码:

public class AppTest extends TestCase {
private ConsistentHashing consistentHashing;
private static Map<String, Integer> nodes = new HashMap<String, Integer>();
public AppTest(String testName) {
super(testName);
for(int i=0;i<10;i++) {
nodes.put( "192.168.0."+(i+1), i);
}
consistentHashing = new ConsistentHashing(nodes);
}
public static Test suite() {
return new TestSuite(AppTest.class);
}
public void testHash() {
goHash(0);//无虚拟节点
goHash(10);//10虚拟节点
goHash(100);
goHash(1000);
}
public void goHash(int virNUm) {
consistentHashing.setVirtualNum(virNUm);
consistentHashing.init();
int[] counters = new int[nodes.size()];
for (int i = 0; i < 1000000; i++) {
String node = UUID.randomUUID().toString();
String serverIp = consistentHashing.getServer(node);
counters[nodes.get(serverIp)]++;
}
for (int i = 0; i < counters.length; i++) {
System.out.println("路由到结点[192.168.0."+(i+1)+"] "+ counters[i]+"次");
}
double dsv = MathUtils.standardDiviation(counters);
System.out.println(virNUm + "虚拟节点标准差:"+ dsv);
assertTrue(true);
}
}



测试结果:

路由到结点[192.168.0.1] 73711次
路由到结点[192.168.0.2] 88132次
路由到结点[192.168.0.3] 38560次
路由到结点[192.168.0.4] 81524次
路由到结点[192.168.0.5] 102842次
路由到结点[192.168.0.6] 213723次
路由到结点[192.168.0.7] 36849次
路由到结点[192.168.0.8] 53248次
路由到结点[192.168.0.9] 273023次
路由到结点[192.168.0.10] 38388次
0虚拟节点 标准差:14654.29507004687

路由到结点[192.168.0.1] 148980次
路由到结点[192.168.0.2] 95794次
路由到结点[192.168.0.3] 86326次
路由到结点[192.168.0.4] 36654次
路由到结点[192.168.0.5] 89828次
路由到结点[192.168.0.6] 110975次
路由到结点[192.168.0.7] 93610次
路由到结点[192.168.0.8] 84907次
路由到结点[192.168.0.9] 105570次
路由到结点[192.168.0.10] 147356次
10虚拟节点 标准差:14654.29507004687

路由到结点[192.168.0.1] 104468次
路由到结点[192.168.0.2] 105734次
路由到结点[192.168.0.3] 86492次
路由到结点[192.168.0.4] 95853次
路由到结点[192.168.0.5] 103345次
路由到结点[192.168.0.6] 97413次
路由到结点[192.168.0.7] 112574次
路由到结点[192.168.0.8] 87883次
路由到结点[192.168.0.9] 102369次
路由到结点[192.168.0.10] 103869次
100虚拟节点 标准差:7719.426986506188

路由到结点[192.168.0.1] 95187次
路由到结点[192.168.0.2] 97355次
路由到结点[192.168.0.3] 103488次
路由到结点[192.168.0.4] 97147次
路由到结点[192.168.0.5] 104259次
路由到结点[192.168.0.6] 97661次
路由到结点[192.168.0.7] 100685次
路由到结点[192.168.0.8] 106974次
路由到结点[192.168.0.9] 98206次
路由到结点[192.168.0.10] 99038次
1000虚拟节点 标准差:3568.2843216313354




用户头像

连增申

关注

还未添加个人签名 2020.04.02 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 No.5 周作业