1
架构师训练营 第五周 基于虚拟节点的一致性 Hash 算法作业
发布于: 2020 年 07 月 08 日
作业
1、用你熟悉的编程语言实现一致性hash算法。
2、编写测试用例测试这个算法,测试100万KV数据,10个服务器节点的情况下,计算这些KV数据在服务器尚分布数量的标准差,以评估算法的存储负载不均衡性。
源代码
package com.xianyanyang.consistency.arithmetic;import com.xianyanyang.consistency.servernode.ServerNode;import com.xianyanyang.consistency.servernode.VirtualNode;import com.xianyanyang.consistency.util.MatchNearestServerUtils;import org.apache.commons.math3.stat.descriptive.moment.StandardDeviation;import java.math.BigDecimal;import java.math.RoundingMode;import java.util.ArrayList;import java.util.Collection;import java.util.Comparator;import java.util.List;import java.util.stream.Collectors;/** * 基于虚拟节点的一致性hash算法类 */public class VirtualNodeConsistencyHashArithmetic { /** * 服务器节点个数 */ private Integer serverNodeCount; /** * 每个服务器的虚拟节点的个数 */ private Integer virtualNodeNumber; /** * 服务器节点名称模板 */ private String serverNodeTemplate; /** * 虚拟节点名称模板 */ private String virtualNodeTemplate; /** * 构造函数 * * @param serverNodeCount 服务器节点个数 * @param virtualNodeNumber 每个服务器的虚拟节点的个数 * @param serverNodeTemplate 服务器节点名称模板 * @param virtualNodeTemplate 虚拟节点名称模板 */ public VirtualNodeConsistencyHashArithmetic(Integer serverNodeCount, Integer virtualNodeNumber, String serverNodeTemplate, String virtualNodeTemplate) { this.serverNodeCount = serverNodeCount; this.virtualNodeNumber = virtualNodeNumber; this.serverNodeTemplate = serverNodeTemplate; this.virtualNodeTemplate = virtualNodeTemplate; } /** * 服务器节点在设置不同虚拟节点个数下缓存命中的次数的标准差计算 * * @param dataList 待查找命中缓存数据hashCode清单 * @return 标准差 */ public BigDecimal calculateStandardDeviation(Collection<Integer> dataList) { Collection<ServerNode> serverNodes = this.initVirtualNodes(); List<VirtualNode> sortedVirtualNodes = this.getSortedVirtualNodes(serverNodes); dataList.forEach(data -> MatchNearestServerUtils.hitServerNode(data, sortedVirtualNodes)); return calculateServerNodeStandardDeviation(serverNodes); } /** * 初始化虚拟节点 * * @return 服务器节点集合 */ private Collection<ServerNode> initVirtualNodes() { Collection<ServerNode> result = new ArrayList<>(); for (int i = 0; i < serverNodeCount; i++) { ServerNode serverNode = new ServerNode(serverNodeTemplate + i); for (int j = 0; j < virtualNodeNumber; j++) { VirtualNode virtualNode = new VirtualNode(serverNode.getName() + virtualNodeTemplate + j); serverNode.addVirtualNode(virtualNode); } result.add(serverNode); } return result; } /** * 计算标准差值 * * @param serverNodes 服务器节点集合 * @return 标准差值 */ private BigDecimal calculateServerNodeStandardDeviation(Collection<ServerNode> serverNodes) { double doubleValues[] = new double[serverNodeCount]; int i = 0; for (ServerNode serverNode : serverNodes) { doubleValues[i] = serverNode.getHitTimes(); i++; System.out.println(String.format("虚拟节点数量为 %s,服务器 %s 的命中次数为" + serverNode.getHitTimes(), virtualNodeNumber, serverNode.getName(), serverNode.getHitTimes())); } StandardDeviation standardDeviation = new StandardDeviation(); return new BigDecimal(standardDeviation.evaluate(doubleValues)).setScale(0, RoundingMode.HALF_UP); } /** * 所有的虚拟节点清单 * * @param serverNodes 服务器节点清单 * @return 虚拟节点清单 */ private List<VirtualNode> getSortedVirtualNodes(Collection<ServerNode> serverNodes) { List<VirtualNode> allVirtualNodes = new ArrayList<>(); serverNodes.forEach(serverNode -> allVirtualNodes.addAll(serverNode.getVirtualNodes())); return allVirtualNodes.stream().sorted(Comparator.comparing(VirtualNode::getHashCode)).collect(Collectors.toList()); }}
package com.xianyanyang.consistency.servernode;import org.apache.commons.collections4.CollectionUtils;import java.util.ArrayList;import java.util.Collection;import java.util.Collections;/** * 服务器节点 */public class ServerNode { /** * 构造函数 * * @param name 名称 */ public ServerNode(String name) { this.name = name; } /** * 命中次数 */ private int hitTimes = 0; /** * 服务器名称 */ private String name; /** * 虚拟节点清单 */ private Collection<VirtualNode> virtualNodes = Collections.emptyList(); /** * 获取命中次数 * * @return 命中次数 */ public int getHitTimes() { return hitTimes; } /** * 获取服务器名称 * * @return 服务器名称 */ public String getName() { return name; } /** * 获取虚拟节点清单 * * @return 虚拟节点清单 */ public Collection<VirtualNode> getVirtualNodes() { return virtualNodes; } /** * 添加虚拟节点 * * @param virtualNode 虚拟节点 */ public void addVirtualNode(VirtualNode virtualNode) { if (CollectionUtils.isEmpty(virtualNodes)) { virtualNodes = new ArrayList<>(); } virtualNodes.add(virtualNode); virtualNode.setServerNode(this); } /** * 缓存命中,次数累积 */ public void hit() { this.hitTimes += 1; }}
package com.xianyanyang.consistency.servernode;import com.xianyanyang.consistency.util.HashCodeUtils;/** * 虚拟节点 */public class VirtualNode { /** * 构造函数 * * @param name 节点名称 */ public VirtualNode(String name) { this.hashCode = HashCodeUtils.getHash(name); } /** * hashCode值 */ private int hashCode; public int getHashCode() { return hashCode; } /** * 所属服务器节点 */ private ServerNode serverNode; /** * 设置所属服务器节点 * * @param serverNode 所属服务器节点 */ public void setServerNode(ServerNode serverNode) { this.serverNode = serverNode; } /** * 查看所属服务器节点 * * @return 所属服务器节点 */ public ServerNode getServerNode() { return this.serverNode; }}
package com.xianyanyang.consistency.util;/** * hash算法通用类 */public class HashCodeUtils { /** * FNV1_32_HASH算法 * * @param value 数据 * @return hash值 */ public static int getHash(String value) { final int p = 16777619; int result = (int) 2166136261L; for (int i = 0; i < value.length(); i++) { result = (result ^ value.charAt(i)) * p; } result += result << 13; result ^= result >> 7; result += result << 3; result ^= result >> 17; result += result << 5; return Math.abs(result); }}
package com.xianyanyang.consistency.util;import com.xianyanyang.consistency.servernode.ServerNode;import com.xianyanyang.consistency.servernode.VirtualNode;import java.util.List;/** * 命中缓存的服务器节点算法类 */public class MatchNearestServerUtils { /** * 查找命中缓存的服务器节点 * * @param dataHashCode 数据的hashcode * @param sortedVirtualNodes 虚拟节点清单 * @return 命中缓存的服务器节点 */ public static ServerNode hitServerNode(Integer dataHashCode, List<VirtualNode> sortedVirtualNodes) { ServerNode serverNode = sortedVirtualNodes.get(0).getServerNode(); for (VirtualNode sortedVirtualNode : sortedVirtualNodes) { if (sortedVirtualNode.getHashCode() >= dataHashCode) { serverNode = sortedVirtualNode.getServerNode(); break; } } serverNode.hit(); return serverNode; }}
单元测试用例
package com.xianyanyang.consistency.arithmetic;import com.xianyanyang.consistency.util.HashCodeUtils;import junit.framework.TestCase;import org.junit.Test;import java.math.BigDecimal;import java.util.*;/** * 基于虚拟节点的一致性hash算法类单元测试 */public class VirtualNodeConsistencyHashArithmeticTest extends TestCase { /** * 基于虚拟节点的一致性hash算法 */ private VirtualNodeConsistencyHashArithmetic virtualNodeConsistencyHashArithmetic; /** * 服务器节点个数 */ private int serverNodeCount = 10; /** * 待查找命中缓存数据个数 */ private int keyNumber = 1000000; /** * 待查找命中缓存数据hashCode清单 */ private Collection<Integer> dataList; /** * 服务器节点名称模板 */ private String serverNodeTemplate = "serverNode"; /** * 虚拟节点名称模板 */ private String virtualNodeTemplate = "-virtual-"; /** * 待测试每个服务器的虚拟节点的个数清单 */ private List<Integer> virtualNodeNumbers = Arrays.asList(1, 5, 100, 120, 140, 150, 180, 200, 250, 300, 400, 500, 1000, 1500, 2000, 2500); @Override public void setUp() { this.dataList = this.initDataToHit(); System.out.println("总数据个数为 " + this.dataList.size()); } /** * 服务器节点在设置不同虚拟节点个数下缓存命中的次数的标准差测试 */ @Test public void testServerNodeTitTimesStandardDeviationByVirtualNode() { SortedMap<Integer, BigDecimal> standardDeviations = new TreeMap<>(); virtualNodeNumbers.forEach(virtualNodeNumber -> { virtualNodeConsistencyHashArithmetic = new VirtualNodeConsistencyHashArithmetic(serverNodeCount, virtualNodeNumber, serverNodeTemplate, virtualNodeTemplate); BigDecimal standardDeviation = virtualNodeConsistencyHashArithmetic.calculateStandardDeviation(dataList); standardDeviations.put(virtualNodeNumber, standardDeviation); }); standardDeviations.entrySet().forEach(standardDeviation -> { System.out.println(String.format("虚拟节点数量为 %s,标准差为:%s", standardDeviation.getKey(), standardDeviation.getValue())); }); } /** * 初始化待缓存查找命中数据hashCode集合 * * @return hashCode集合 */ private Collection<Integer> initDataToHit() { Collection<Integer> result = new ArrayList<>(); for (int i = 0; i < keyNumber; i++) { int value = HashCodeUtils.getHash(UUID.randomUUID().toString()); result.add(value); } return result; }}
单元测试用例执行结果
"D:\Program Files\Java\jdk-10\bin\java.exe" -ea -Didea.test.cyclic.buffer.size=1048576 "-javaagent:D:\Program Files\JetBrains\IntelliJ IDEA 2018.1.5\lib\idea_rt.jar=62287:D:\Program Files\JetBrains\IntelliJ IDEA 2018.1.5\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\JetBrains\IntelliJ IDEA 2018.1.5\lib\idea_rt.jar;D:\Program Files\JetBrains\IntelliJ IDEA 2018.1.5\plugins\junit\lib\junit-rt.jar;D:\Program Files\JetBrains\IntelliJ IDEA 2018.1.5\plugins\junit\lib\junit5-rt.jar;E:\book\architect-design\target\test-classes;E:\book\architect-design\target\classes;F:\repository\org\apache\commons\commons-collections4\4.4\commons-collections4-4.4.jar;F:\repository\org\apache\commons\commons-math3\3.6.1\commons-math3-3.6.1.jar;F:\repository\junit\junit\4.13\junit-4.13.jar;F:\repository\org\hamcrest\hamcrest-core\1.3\hamcrest-core-1.3.jar" com.intellij.rt.execution.junit.JUnitStarter -ideVersion5 -junit4 com.xianyanyang.consistency.arithmetic.VirtualNodeConsistencyHashArithmeticTest,testServerNodeTitTimesStandardDeviationByVirtualNode总数据个数为 1000000虚拟节点数量为 1,服务器 serverNode0 的命中次数为18091虚拟节点数量为 1,服务器 serverNode1 的命中次数为93498虚拟节点数量为 1,服务器 serverNode2 的命中次数为138346虚拟节点数量为 1,服务器 serverNode3 的命中次数为125955虚拟节点数量为 1,服务器 serverNode4 的命中次数为251444虚拟节点数量为 1,服务器 serverNode5 的命中次数为80248虚拟节点数量为 1,服务器 serverNode6 的命中次数为86331虚拟节点数量为 1,服务器 serverNode7 的命中次数为83109虚拟节点数量为 1,服务器 serverNode8 的命中次数为30474虚拟节点数量为 1,服务器 serverNode9 的命中次数为92504虚拟节点数量为 5,服务器 serverNode0 的命中次数为69689虚拟节点数量为 5,服务器 serverNode1 的命中次数为110432虚拟节点数量为 5,服务器 serverNode2 的命中次数为117781虚拟节点数量为 5,服务器 serverNode3 的命中次数为139406虚拟节点数量为 5,服务器 serverNode4 的命中次数为105956虚拟节点数量为 5,服务器 serverNode5 的命中次数为160808虚拟节点数量为 5,服务器 serverNode6 的命中次数为68508虚拟节点数量为 5,服务器 serverNode7 的命中次数为76904虚拟节点数量为 5,服务器 serverNode8 的命中次数为82952虚拟节点数量为 5,服务器 serverNode9 的命中次数为67564虚拟节点数量为 100,服务器 serverNode0 的命中次数为96720虚拟节点数量为 100,服务器 serverNode1 的命中次数为82489虚拟节点数量为 100,服务器 serverNode2 的命中次数为102851虚拟节点数量为 100,服务器 serverNode3 的命中次数为105271虚拟节点数量为 100,服务器 serverNode4 的命中次数为86321虚拟节点数量为 100,服务器 serverNode5 的命中次数为115586虚拟节点数量为 100,服务器 serverNode6 的命中次数为95967虚拟节点数量为 100,服务器 serverNode7 的命中次数为99938虚拟节点数量为 100,服务器 serverNode8 的命中次数为107690虚拟节点数量为 100,服务器 serverNode9 的命中次数为107167虚拟节点数量为 120,服务器 serverNode0 的命中次数为100449虚拟节点数量为 120,服务器 serverNode1 的命中次数为87321虚拟节点数量为 120,服务器 serverNode2 的命中次数为96675虚拟节点数量为 120,服务器 serverNode3 的命中次数为109501虚拟节点数量为 120,服务器 serverNode4 的命中次数为89149虚拟节点数量为 120,服务器 serverNode5 的命中次数为117394虚拟节点数量为 120,服务器 serverNode6 的命中次数为94694虚拟节点数量为 120,服务器 serverNode7 的命中次数为94182虚拟节点数量为 120,服务器 serverNode8 的命中次数为107916虚拟节点数量为 120,服务器 serverNode9 的命中次数为102719虚拟节点数量为 140,服务器 serverNode0 的命中次数为99061虚拟节点数量为 140,服务器 serverNode1 的命中次数为90210虚拟节点数量为 140,服务器 serverNode2 的命中次数为99894虚拟节点数量为 140,服务器 serverNode3 的命中次数为109684虚拟节点数量为 140,服务器 serverNode4 的命中次数为91641虚拟节点数量为 140,服务器 serverNode5 的命中次数为106980虚拟节点数量为 140,服务器 serverNode6 的命中次数为95212虚拟节点数量为 140,服务器 serverNode7 的命中次数为96201虚拟节点数量为 140,服务器 serverNode8 的命中次数为107526虚拟节点数量为 140,服务器 serverNode9 的命中次数为103591虚拟节点数量为 150,服务器 serverNode0 的命中次数为96129虚拟节点数量为 150,服务器 serverNode1 的命中次数为98890虚拟节点数量为 150,服务器 serverNode2 的命中次数为100752虚拟节点数量为 150,服务器 serverNode3 的命中次数为106121虚拟节点数量为 150,服务器 serverNode4 的命中次数为93052虚拟节点数量为 150,服务器 serverNode5 的命中次数为100995虚拟节点数量为 150,服务器 serverNode6 的命中次数为98416虚拟节点数量为 150,服务器 serverNode7 的命中次数为95503虚拟节点数量为 150,服务器 serverNode8 的命中次数为105785虚拟节点数量为 150,服务器 serverNode9 的命中次数为104357虚拟节点数量为 180,服务器 serverNode0 的命中次数为93677虚拟节点数量为 180,服务器 serverNode1 的命中次数为105712虚拟节点数量为 180,服务器 serverNode2 的命中次数为91158虚拟节点数量为 180,服务器 serverNode3 的命中次数为102599虚拟节点数量为 180,服务器 serverNode4 的命中次数为88419虚拟节点数量为 180,服务器 serverNode5 的命中次数为104504虚拟节点数量为 180,服务器 serverNode6 的命中次数为101752虚拟节点数量为 180,服务器 serverNode7 的命中次数为101238虚拟节点数量为 180,服务器 serverNode8 的命中次数为104498虚拟节点数量为 180,服务器 serverNode9 的命中次数为106443虚拟节点数量为 200,服务器 serverNode0 的命中次数为90950虚拟节点数量为 200,服务器 serverNode1 的命中次数为103385虚拟节点数量为 200,服务器 serverNode2 的命中次数为97234虚拟节点数量为 200,服务器 serverNode3 的命中次数为102631虚拟节点数量为 200,服务器 serverNode4 的命中次数为93978虚拟节点数量为 200,服务器 serverNode5 的命中次数为104147虚拟节点数量为 200,服务器 serverNode6 的命中次数为105113虚拟节点数量为 200,服务器 serverNode7 的命中次数为95829虚拟节点数量为 200,服务器 serverNode8 的命中次数为99913虚拟节点数量为 200,服务器 serverNode9 的命中次数为106820虚拟节点数量为 250,服务器 serverNode0 的命中次数为98526虚拟节点数量为 250,服务器 serverNode1 的命中次数为101342虚拟节点数量为 250,服务器 serverNode2 的命中次数为94742虚拟节点数量为 250,服务器 serverNode3 的命中次数为100396虚拟节点数量为 250,服务器 serverNode4 的命中次数为92264虚拟节点数量为 250,服务器 serverNode5 的命中次数为100791虚拟节点数量为 250,服务器 serverNode6 的命中次数为100405虚拟节点数量为 250,服务器 serverNode7 的命中次数为103708虚拟节点数量为 250,服务器 serverNode8 的命中次数为99175虚拟节点数量为 250,服务器 serverNode9 的命中次数为108651虚拟节点数量为 300,服务器 serverNode0 的命中次数为100753虚拟节点数量为 300,服务器 serverNode1 的命中次数为93545虚拟节点数量为 300,服务器 serverNode2 的命中次数为98792虚拟节点数量为 300,服务器 serverNode3 的命中次数为104058虚拟节点数量为 300,服务器 serverNode4 的命中次数为98847虚拟节点数量为 300,服务器 serverNode5 的命中次数为101067虚拟节点数量为 300,服务器 serverNode6 的命中次数为108313虚拟节点数量为 300,服务器 serverNode7 的命中次数为95196虚拟节点数量为 300,服务器 serverNode8 的命中次数为95128虚拟节点数量为 300,服务器 serverNode9 的命中次数为104301虚拟节点数量为 400,服务器 serverNode0 的命中次数为101257虚拟节点数量为 400,服务器 serverNode1 的命中次数为95115虚拟节点数量为 400,服务器 serverNode2 的命中次数为102976虚拟节点数量为 400,服务器 serverNode3 的命中次数为98993虚拟节点数量为 400,服务器 serverNode4 的命中次数为99645虚拟节点数量为 400,服务器 serverNode5 的命中次数为96352虚拟节点数量为 400,服务器 serverNode6 的命中次数为102896虚拟节点数量为 400,服务器 serverNode7 的命中次数为98898虚拟节点数量为 400,服务器 serverNode8 的命中次数为95614虚拟节点数量为 400,服务器 serverNode9 的命中次数为108254虚拟节点数量为 500,服务器 serverNode0 的命中次数为101416虚拟节点数量为 500,服务器 serverNode1 的命中次数为99406虚拟节点数量为 500,服务器 serverNode2 的命中次数为98750虚拟节点数量为 500,服务器 serverNode3 的命中次数为98956虚拟节点数量为 500,服务器 serverNode4 的命中次数为104897虚拟节点数量为 500,服务器 serverNode5 的命中次数为96789虚拟节点数量为 500,服务器 serverNode6 的命中次数为101142虚拟节点数量为 500,服务器 serverNode7 的命中次数为97345虚拟节点数量为 500,服务器 serverNode8 的命中次数为96938虚拟节点数量为 500,服务器 serverNode9 的命中次数为104361虚拟节点数量为 1000,服务器 serverNode0 的命中次数为100336虚拟节点数量为 1000,服务器 serverNode1 的命中次数为101254虚拟节点数量为 1000,服务器 serverNode2 的命中次数为103192虚拟节点数量为 1000,服务器 serverNode3 的命中次数为102724虚拟节点数量为 1000,服务器 serverNode4 的命中次数为101556虚拟节点数量为 1000,服务器 serverNode5 的命中次数为98522虚拟节点数量为 1000,服务器 serverNode6 的命中次数为99052虚拟节点数量为 1000,服务器 serverNode7 的命中次数为95294虚拟节点数量为 1000,服务器 serverNode8 的命中次数为97556虚拟节点数量为 1000,服务器 serverNode9 的命中次数为100514虚拟节点数量为 1500,服务器 serverNode0 的命中次数为95616虚拟节点数量为 1500,服务器 serverNode1 的命中次数为101178虚拟节点数量为 1500,服务器 serverNode2 的命中次数为101698虚拟节点数量为 1500,服务器 serverNode3 的命中次数为103219虚拟节点数量为 1500,服务器 serverNode4 的命中次数为102527虚拟节点数量为 1500,服务器 serverNode5 的命中次数为101089虚拟节点数量为 1500,服务器 serverNode6 的命中次数为99898虚拟节点数量为 1500,服务器 serverNode7 的命中次数为96997虚拟节点数量为 1500,服务器 serverNode8 的命中次数为97749虚拟节点数量为 1500,服务器 serverNode9 的命中次数为100029虚拟节点数量为 1,标准差为:64621虚拟节点数量为 5,标准差为:32485虚拟节点数量为 100,标准差为:10056虚拟节点数量为 120,标准差为:9514虚拟节点数量为 140,标准差为:6799虚拟节点数量为 150,标准差为:4456虚拟节点数量为 180,标准差为:6483虚拟节点数量为 200,标准差为:5286虚拟节点数量为 250,标准差为:4493虚拟节点数量为 300,标准差为:4679虚拟节点数量为 400,标准差为:4024虚拟节点数量为 500,标准差为:2907虚拟节点数量为 1000,标准差为:2431虚拟节点数量为 1500,标准差为:2484Process finished with exit code 0
关键点
1、hashcode计算算法;
2、标准差算法,参考:apache.commons.math3.stat.descriptive.moment.StandardDeviation算法类;
2、基于指定的虚拟节点个数初始化服务器的虚拟节点;
3、初始化待缓存查找命中数据hashCode集合;
4、计算指定数据命中的虚拟节点所属的服务器节点;
注意点
基于指定的虚拟节点个数初始化服务器的虚拟节点的hashcode需要保持不变,可以通过固定的名称格式循环生成hashcode。
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 100
版权声明: 本文为 InfoQ 作者【且听且吟】的原创文章。
原文链接:【http://xie.infoq.cn/article/9786ccf5b35d2c8d4767cfb7b】。未经作者许可,禁止转载。
且听且吟
关注
没有绝世高手 2018.06.30 加入
还未添加个人简介
评论