架构师培训 -05 缓存、消息和负载均衡

用户头像
刘敏
关注
发布于: 2020 年 07 月 08 日

1.用代码实现一致性hash

作业题如下:

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

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

答:

通过测试代码跑下来,虚拟节点数和实际物理机器节点数越多标准差就越小,意味着也就越均匀一些。因此在物理机器几点数一定的情况下,为了使数据分布的更加均匀可以增加虚拟节点的数量。



150个虚拟节点运行结果:

"C:\Program Files\Java\jdk1.8.0_171\bin\java.exe" "-javaagent:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\lib\idea_rt.jar=64814:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_171\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\rt.jar;F:\arctrainingwp\ArcTraningCode\ConsisitencyHash\target\classes" com.lm.TestConsisitencyHash
当前节点数:10
192.168.1.107 : 100859
192.168.1.108 : 73776
192.168.1.109 : 93854
192.168.1.103 : 79809
192.168.1.104 : 102059
192.168.1.105 : 107971
192.168.1.106 : 46852
192.168.1.100 : 161547
192.168.1.101 : 67054
192.168.1.102 : 166219
标准差 : 14654.29507004687
cost time : 651ms
增加五机器:192.168.1.110~192.168.1.114
当前节点数:15
192.168.1.107 : 71577
192.168.1.108 : 44549
192.168.1.109 : 53460
192.168.1.103 : 59504
192.168.1.114 : 69621
192.168.1.104 : 62496
192.168.1.105 : 80322
192.168.1.106 : 39764
192.168.1.110 : 89252
192.168.1.100 : 100197
192.168.1.111 : 101838
192.168.1.101 : 39152
192.168.1.112 : 67212
192.168.1.102 : 84686
192.168.1.113 : 36370
标准差 : 11965.1818205993
cost time : 538ms
宕机2台:192.168.1.102,192.168.1.112
当前节点数:13
192.168.1.107 : 71974
192.168.1.108 : 124480
192.168.1.109 : 56890
192.168.1.103 : 75155
192.168.1.114 : 74784
192.168.1.104 : 71145
192.168.1.105 : 82248
192.168.1.106 : 46416
192.168.1.110 : 103847
192.168.1.100 : 105683
192.168.1.111 : 107291
192.168.1.101 : 40073
192.168.1.113 : 40014
标准差 : 12852.666999498586
cost time : 260ms

Process finished with exit code 0





300个虚拟节点运行结果:

"C:\Program Files\Java\jdk1.8.0_171\bin\java.exe" "-javaagent:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\lib\idea_rt.jar=64907:E:\Program Files\JetBrains\IntelliJ IDEA 2018.1.4\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_171\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_171\jre\lib\rt.jar;F:\arctrainingwp\ArcTraningCode\ConsisitencyHash\target\classes" com.lm.TestConsisitencyHash
当前节点数:10
192.168.1.107 : 96734
192.168.1.108 : 119056
192.168.1.109 : 103420
192.168.1.103 : 103040
192.168.1.104 : 111921
192.168.1.105 : 81119
192.168.1.106 : 101298
192.168.1.100 : 97297
192.168.1.101 : 87186
192.168.1.102 : 98929
标准差 : 10332.835719201192
cost time : 665ms
增加五机器:192.168.1.110~192.168.1.114
当前节点数:15
192.168.1.107 : 63658
192.168.1.108 : 74068
192.168.1.109 : 71250
192.168.1.103 : 54710
192.168.1.114 : 77158
192.168.1.104 : 72785
192.168.1.105 : 47065
192.168.1.106 : 60783
192.168.1.110 : 70745
192.168.1.100 : 57167
192.168.1.111 : 85572
192.168.1.101 : 56571
192.168.1.112 : 73190
192.168.1.113 : 73591
192.168.1.102 : 61687
标准差 : 9918.51304379845
cost time : 457ms
宕机2台:192.168.1.102,192.168.1.112
当前节点数:13
192.168.1.107 : 74394
192.168.1.108 : 89825
192.168.1.109 : 73495
192.168.1.103 : 62275
192.168.1.114 : 89199
192.168.1.104 : 76838
192.168.1.105 : 63574
192.168.1.106 : 75256
192.168.1.110 : 82873
192.168.1.100 : 73179
192.168.1.111 : 87903
192.168.1.101 : 64670
192.168.1.113 : 86519
标准差 : 9376.953236526244
cost time : 322ms

Process finished with exit code 0




一致性hash

package com.lm;

import java.util.*;

/**
* @author lm
* @description 一致性hash
* @date 2020/7/8 14:54
*/
public class ConsisitencyHash {
private final static Integer VIRTUAL_NUM = 150;
static SortedMap<Integer, String> virtualNodeMap = new TreeMap<Integer, String>();
static List<String> relServers;

public static void init(List<String> relServers) {
ConsisitencyHash.relServers = relServers;
List<Integer> virtualNodeList = new ArrayList<Integer>();
//初始化150个虚拟节点
for (int i = 0; i < VIRTUAL_NUM; i++) {
String key = UUID.randomUUID().toString();
Integer hash = hash(key);
virtualNodeList.add(hash);
}

//将虚拟节点分配给实体节点
assignVirtualNode(virtualNodeList, relServers);

}

/**
* 路由到具体的节点
*
* @param key
* @return
*/
public static String router(String key) {
int hash = hash(key);
SortedMap<Integer, String> subMap = virtualNodeMap.tailMap(hash);
Integer firstKey = null;
if (subMap.isEmpty()) {
firstKey = virtualNodeMap.firstKey();
} else {
firstKey = subMap.firstKey();
}
return virtualNodeMap.get(firstKey);
}

/**
*移出服务器
* @param servers
*/
public static void removeServers(List<String> servers) {
List<Integer> removeHashs = new ArrayList<Integer>();
for (SortedMap.Entry<Integer, String> virtualNode : virtualNodeMap.entrySet()) {
if (servers.contains(virtualNode.getValue())) {
removeHashs.add(virtualNode.getKey());
}
}
if (removeHashs.size() == 0) {
return;
}

//删除拿出来的key
for(Integer key : removeHashs) {
virtualNodeMap.remove(key);
}

for (String server : servers) {
relServers.remove(server);
}

assignVirtualNode(removeHashs, relServers);
}


/**
* 添加服务器
* @param servers
*/
public static synchronized void addServers(List<String> servers) {

int relNodeNum = relServers.size() + servers.size();
int virtualNum = virtualNodeMap.size();
int preAssignableNodeNum = virtualNum / relNodeNum;
int newServerWaitAssignNum = preAssignableNodeNum * servers.size();
int waitGetVirtualNodeNum = newServerWaitAssignNum / relServers.size();

Set<Map.Entry<Integer, String>> set = virtualNodeMap.entrySet();
List<Integer> waitAssignVirtualNode = new ArrayList<Integer>();
for (String relServer : relServers) {
for (SortedMap.Entry<Integer, String> entry : set) {
if(relServer.equals(entry.getValue())) {
waitAssignVirtualNode.add(entry.getKey());
if (waitAssignVirtualNode.size() % waitGetVirtualNodeNum == 0) {
break;
}
}

}
}


//将新增节点加入到节点列表中
relServers.addAll(servers);

//将拿出来的节点分配给新加入的节点
assignVirtualNode(waitAssignVirtualNode, servers);

}

private static void assignVirtualNode(List<Integer> waitAssignVirtualNodes, List<String> assignableRelNode) {
int virtualNum = waitAssignVirtualNodes.size();
int relNodeNum = assignableRelNode.size();

int assignableNodeNum = virtualNum / relNodeNum;

for (int i = 0; i < virtualNum; i++) {
int relNodeIndx = i / assignableNodeNum;
if (relNodeIndx >= relNodeNum) {
relNodeIndx = virtualNum % relNodeNum;
}
virtualNodeMap.put(waitAssignVirtualNodes.get(i), assignableRelNode.get(relNodeIndx));
}
}


private static int hash(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++) {
hash = (hash ^ key.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;
}
}




测试代码

package com.lm;

import java.util.*;

/**
* @author lm
* @description 测试一致性hash
* @date 2020/7/8 16:35
*/
public class TestConsisitencyHash {
private final static Integer DATA_SIZE = 1000000;

public static void main(String[] args) {
List<String> relServers = getServers();
List<String> dataList = generateData();
ConsisitencyHash.init(relServers);

test(dataList);

System.out.println("增加五机器:192.168.1.110~192.168.1.114" );
List<String> addServers = new ArrayList<String>();
addServers.add("192.168.1.110");
addServers.add("192.168.1.111");
addServers.add("192.168.1.112");
addServers.add("192.168.1.113");
addServers.add("192.168.1.114");
ConsisitencyHash.addServers(addServers);

test(dataList);


System.out.println("宕机2台:192.168.1.102,192.168.1.112" );
List<String> removeServers = new ArrayList<String>();
removeServers.add("192.168.1.102");
removeServers.add("192.168.1.112");
ConsisitencyHash.removeServers(removeServers);
test(dataList);



}

private static void test(List<String> dataList) {
long startTime = System.currentTimeMillis();
System.out.println("当前节点数:"+ ConsisitencyHash.relServers.size() );
Map<String, Integer> vistNumMap = new HashMap<String, Integer>(ConsisitencyHash.relServers.size());
for (String key : dataList) {
String server = ConsisitencyHash.router(key);
Integer vistNum = vistNumMap.get(server);
if (vistNum == null) {
vistNum = 0;
}
vistNumMap.put(server, vistNum + 1);

}

for (Map.Entry<String, Integer> entry : vistNumMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
double standardDeviation = standardDiviation( vistNumMap);
System.out.println("标准差 : " +standardDeviation);

long endTime = System.currentTimeMillis();

System.out.println("cost time : " + (endTime - startTime));
System.out.println(" " );
}

public static List<String> getServers() {
List<String> relServers = new LinkedList<String>();
relServers.add("192.168.1.100");
relServers.add("192.168.1.101");
relServers.add("192.168.1.102");
relServers.add("192.168.1.103");
relServers.add("192.168.1.104");
relServers.add("192.168.1.105");
relServers.add("192.168.1.106");
relServers.add("192.168.1.107");
relServers.add("192.168.1.108");
relServers.add("192.168.1.109");
return relServers;
}


public static List<String> generateData() {
List<String> dataList = new ArrayList<String>(DATA_SIZE);
for (int i = 0; i < DATA_SIZE; i++) {
dataList.add(UUID.randomUUID().toString());
}
return dataList;
}

public static double standardDiviation(Map<String,Integer> vistNumMap) {
int size = vistNumMap.size();
long sum = 0;
for(Map.Entry<String,Integer> entry :vistNumMap.entrySet()) {
sum += entry.getValue();
}
double average = sum / size;
int total = 0;
for(Map.Entry<String,Integer> entry :vistNumMap.entrySet()) {
total += (entry.getValue() - average) * (entry.getValue()- average);
}
double standardDeviation = Math.sqrt(total /size);

return standardDeviation;
}
}




用户头像

刘敏

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

发布
暂无评论
架构师培训 -05 缓存、消息和负载均衡