架构师训练营 - 作业 - 第五讲

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



作业一:

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

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



首先定义物理机节点

package class5;
import java.util.ArrayList;
import java.util.List;
public class PhysicalNode {
/**
* 物理机名称
*/
private String name;
public PhysicalNode(String name){
this.name = name;
}
public String getName() {
return name;
}
/**
* 命中次数
*/
private int hitTimes = 0;
public void hitNode(){
hitTimes++;
}
public int getHitTimes() {
return hitTimes;
}
private List<VirtualNode> virtualNodes = new ArrayList();
public void addVirtualNode(VirtualNode virtualNode){
virtualNodes.add(virtualNode);
virtualNode.setPhysicalNode(this);
}
public List<VirtualNode> getVirtualNodeList(){
return virtualNodes;
}
}

然后定义虚拟节点

package class5;
public class VirtualNode {
private int hashCode;
public int getHashCode() {
return hashCode;
}
public VirtualNode(String name) {
this.hashCode = name.hashCode();
}
/**
* 所属服务器节点
*/
private PhysicalNode physicalNode;
public void setPhysicalNode(PhysicalNode physicalNode) {
this.physicalNode = physicalNode;
}
public PhysicalNode getPhysicalNode() {
return this.physicalNode;
}
}

主程序

package class5;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.UUID;
import java.util.stream.Collectors;
public class ConsistencyHashTest {
private static int physicalNodeNumber = 10;
private static int vitualNodeNumberPerPhysicalNode = 200;
private static int dateNumber = 1000000;
public static void main(String[] args) {
List<PhysicalNode> physicalNodeList = new ArrayList<>();
List<VirtualNode> virtualNodeList = new ArrayList<>();
//创建服务器节点
for (int i = 0; i < physicalNodeNumber; i++) {
PhysicalNode physicalNode = new PhysicalNode("物理机" + i);
for (int j = 0; j < vitualNodeNumberPerPhysicalNode; j++) {
VirtualNode virtualNode = new VirtualNode(physicalNode.getName() + "的虚拟节点" + j);
physicalNode.addVirtualNode(virtualNode);
virtualNodeList.add(virtualNode);
}
physicalNodeList.add(physicalNode);
}
//对虚拟节点按照hashcode排序
virtualNodeList.sort(Comparator.comparing(VirtualNode::getHashCode));
//生成测试数据
List<Integer> hashCodeList = new ArrayList<>();
for (int i = 0; i < dateNumber; i++) {
int value = UUID.randomUUID().toString().hashCode();
hashCodeList.add(value);
}
//测试命中
for (int data:hashCodeList) {
VirtualNode tmpVirtualNode = null;
for (VirtualNode virtualNode : virtualNodeList) {
if (virtualNode.getHashCode() >= data) {
tmpVirtualNode = virtualNode;
virtualNode.getPhysicalNode().hitNode();
break;
}
}
if(tmpVirtualNode == null){//未命中数据存入第一个节点
virtualNodeList.get(0).getPhysicalNode().hitNode();
}
}
//开始统计结果
int avg = dateNumber/10;
List<Double> hitList = new ArrayList<>();
for (PhysicalNode physicalNode:physicalNodeList) {
System.out.println(physicalNode.getName() + ":" + physicalNode.getHitTimes());
hitList.add(Double.valueOf(physicalNode.getHitTimes()));
}
double dVar=0;
for(int i=0;i<hitList.size();i++){//求方差
dVar+=(hitList.get(i)-avg)*(hitList.get(i)-avg);
}
System.out.println("标准差:" +Math.sqrt(dVar/10));
}
}

运行结果

物理机0:141427
物理机1:196323
物理机2:129137
物理机3:217167
物理机4:77759
物理机5:52309
物理机6:22027
物理机7:28890
物理机8:54787
物理机9:80174
标准差:64741.16723692893



用户头像

吕浩

关注

还未添加个人签名 2018.04.27 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 作业 - 第五讲