架构师训练营 第五周 基于虚拟节点的一致性 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,标准差为:2484
Process finished with exit code 0

关键点

1、hashcode计算算法;

2、标准差算法,参考:apache.commons.math3.stat.descriptive.moment.StandardDeviation算法类;

2、基于指定的虚拟节点个数初始化服务器的虚拟节点;

3、初始化待缓存查找命中数据hashCode集合;

4、计算指定数据命中的虚拟节点所属的服务器节点;

注意点

基于指定的虚拟节点个数初始化服务器的虚拟节点的hashcode需要保持不变,可以通过固定的名称格式循环生成hashcode。

发布于: 2020 年 07 月 08 日 阅读数: 51
用户头像

且听且吟

关注

没有绝世高手 2018.06.30 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 第五周 基于虚拟节点的一致性Hash算法作业