架构师培训 -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当前节点数：10192.168.1.107 : 100859192.168.1.108 : 73776192.168.1.109 : 93854192.168.1.103 : 79809192.168.1.104 : 102059192.168.1.105 : 107971192.168.1.106 : 46852192.168.1.100 : 161547192.168.1.101 : 67054192.168.1.102 : 166219标准差 ： 14654.29507004687cost time : 651ms 增加五机器：192.168.1.110~192.168.1.114当前节点数：15192.168.1.107 : 71577192.168.1.108 : 44549192.168.1.109 : 53460192.168.1.103 : 59504192.168.1.114 : 69621192.168.1.104 : 62496192.168.1.105 : 80322192.168.1.106 : 39764192.168.1.110 : 89252192.168.1.100 : 100197192.168.1.111 : 101838192.168.1.101 : 39152192.168.1.112 : 67212192.168.1.102 : 84686192.168.1.113 : 36370标准差 ： 11965.1818205993cost time : 538ms 宕机2台：192.168.1.102,192.168.1.112当前节点数：13192.168.1.107 : 71974192.168.1.108 : 124480192.168.1.109 : 56890192.168.1.103 : 75155192.168.1.114 : 74784192.168.1.104 : 71145192.168.1.105 : 82248192.168.1.106 : 46416192.168.1.110 : 103847192.168.1.100 : 105683192.168.1.111 : 107291192.168.1.101 : 40073192.168.1.113 : 40014标准差 ： 12852.666999498586cost 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当前节点数：10192.168.1.107 : 96734192.168.1.108 : 119056192.168.1.109 : 103420192.168.1.103 : 103040192.168.1.104 : 111921192.168.1.105 : 81119192.168.1.106 : 101298192.168.1.100 : 97297192.168.1.101 : 87186192.168.1.102 : 98929标准差 ： 10332.835719201192cost time : 665ms 增加五机器：192.168.1.110~192.168.1.114当前节点数：15192.168.1.107 : 63658192.168.1.108 : 74068192.168.1.109 : 71250192.168.1.103 : 54710192.168.1.114 : 77158192.168.1.104 : 72785192.168.1.105 : 47065192.168.1.106 : 60783192.168.1.110 : 70745192.168.1.100 : 57167192.168.1.111 : 85572192.168.1.101 : 56571192.168.1.112 : 73190192.168.1.113 : 73591192.168.1.102 : 61687标准差 ： 9918.51304379845cost time : 457ms 宕机2台：192.168.1.102,192.168.1.112当前节点数：13192.168.1.107 : 74394192.168.1.108 : 89825192.168.1.109 : 73495192.168.1.103 : 62275192.168.1.114 : 89199192.168.1.104 : 76838192.168.1.105 : 63574192.168.1.106 : 75256192.168.1.110 : 82873192.168.1.100 : 73179192.168.1.111 : 87903192.168.1.101 : 64670192.168.1.113 : 86519标准差 ： 9376.953236526244cost 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; }}
复制代码
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 57
刘敏
关注
还未添加个人签名 2018.04.25 加入
还未添加个人简介
评论