作业
发布于: 2020 年 10 月 25 日
作业一（2 选 1）：
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
解析：
package org.geekbang.training.architecture;
import org.geekbang.training.architecture.domain.*;
import java.util.ArrayList;import java.util.List;import java.util.Random;
/** * 一致性hash算法 * */public class ConsistencyHashAlgorithm { /**物理节点总数*/ private int realCount=0; /**每物理节点虚拟出来的虚拟节点总数**/ private int virtualCountPerNode=0; private List<Node> realNodes = null; private List<Node> virtualNodes=null; private static final Ring ring = new HashRing();
public ConsistencyHashAlgorithm(int realCount,int virtualCountPerReal){ this.init(realCount,virtualCountPerReal); }
private void init(int realCount,int virtualCountPerReal){ this.realCount=realCount; this.virtualCountPerNode=virtualCountPerReal; this.virtualNodes = new ArrayList<Node>(); this.realNodes = new ArrayList<Node>(realCount); //1.初始化物理节点 this.initRealNodes(this.realCount); //2.初始化虚拟节点 this.initVirtualNodes(virtualCountPerReal); //3.虚拟节点分配到环上。 this.allocateVirtualNode(virtualNodes); } private void initRealNodes(int realCount){ for(int i=0;i<realCount;i++){ Node node = new RealNode(); node.setLocation(i); node.setName(node.getClass().getSimpleName()+String.valueOf(i)); node.setNode(null); this.realNodes.add(node); } }
private void initVirtualNodes(int virtualCountPerReal){ for(Node node:realNodes){ virtualizeNode(node,virtualCountPerReal); } }
private void virtualizeNode(Node node,int virtualCountPerReal){ for(int i=0;i<virtualCountPerReal;i++){ Node virtualNode = new VirtualNode(); virtualNode.setLocation(i); virtualNode.setName(virtualNode.getClass().getSimpleName()+String.valueOf(i)); virtualNode.setNode(node); this.virtualNodes.add(virtualNode); } }
/**随机分配虚拟节点到hash环上**/ private void allocateVirtualNode(List<Node> virtualNodes){ Random random = new Random(); for(Node node:this.virtualNodes){ //随机分配虚拟节点 while(true){ int index = Math.abs(random.nextInt(Integer.MAX_VALUE)); if(!ring.hasAllocated(index)){ node.setLocation(index); ring.allocate(index); break; } } } //对所有虚拟节点排序 for(int i=0;i<this.virtualNodes.size();i++){ for(int j=0;j<this.virtualNodes.size()-i;j++){ if(virtualNodes.size()<=(j+1)){ continue;} Node node1=this.virtualNodes.get(j); Node node2=this.virtualNodes.get(j+1); if(node1.getLocation()>node2.getLocation()){ Node temp=node1; this.virtualNodes.set(j,node2); this.virtualNodes.set(j+1,temp); } } } }
/**key顺时针查找里自己最近的虚拟节点，并存储*/ public void put(String key,Object value){ if(key==null||key.trim().length()<=0){ return; } //int hashCode = key.hashCode(); Random random = new Random(); int keyLocation=random.nextInt(Integer.MAX_VALUE); //System.out.println("keyLocation="+keyLocation); int theNearestNodeLocation = this.findNearestNode(keyLocation); //System.out.println("theNearestNodeLocation="+theNearestNodeLocation); Node theNearestNode=null; for(Node node:this.virtualNodes){ if(node.getLocation()==theNearestNodeLocation){ theNearestNode=node; break; } } if(theNearestNode!=null){ theNearestNode.put(key,value); } }
/**查找距离当前位置最近的节点**/ private int findNearestNode(int currentLocation){ /**判断当前位置是否在最后一个虚拟节点之后，如果是，则返回第一个节点位置。（顺时针查找）*/ Node lastNodeAtRing=this.virtualNodes.get(this.virtualNodes.size()-1); if((currentLocation-lastNodeAtRing.getLocation())==0){ return lastNodeAtRing.getLocation(); }else if((currentLocation-lastNodeAtRing.getLocation())>0){ return this.virtualNodes.get(0).getLocation(); } for(Node node:this.virtualNodes){ int result = currentLocation-node.getLocation(); if(result>0){ continue; } return node.getLocation(); } return this.virtualNodes.get(0).getLocation(); }
public List<Node> getRealNodes(){ return this.realNodes; }
public List<Node> getVirtualNodes(){ return this.virtualNodes; }
public static void main(String[] args){ test(2,50,1000000); test(2,100,1000000); test(2,150,1000000); test(2,200,1000000); test(2,250,1000000); test(2,300,1000000); System.out.println();
test(6,50,1000000); test(6,100,1000000); test(6,150,1000000); test(6,200,1000000); test(6,250,1000000); test(6,300,1000000); System.out.println();
test(10,50,1000000); test(10,100,1000000); test(10,150,1000000); test(10,200,1000000); test(10,250,1000000); test(10,300,1000000); System.out.println();
test(20,50,1000000); test(20,100,1000000); test(20,150,1000000); test(20,200,1000000); test(20,250,1000000); test(20,300,1000000); System.out.println();
test(30,50,1000000); test(30,100,1000000); test(30,150,1000000); test(30,200,1000000); test(30,250,1000000); test(30,300,1000000); System.out.println();
test(50,50,1000000); test(50,100,1000000); test(50,150,1000000); test(50,200,1000000); test(50,250,1000000); test(50,300,1000000); System.out.println();
test(100,50,1000000); test(100,100,1000000); test(100,150,1000000); test(100,200,1000000); test(100,250,1000000); test(100,300,1000000);
}
public static void test(int realCount,int virtualCountPerReal,int allKeys){ ConsistencyHashAlgorithm consistencyHashAlgorithm = new ConsistencyHashAlgorithm(realCount,virtualCountPerReal); //System.out.println(consistencyHashAlgorithm.getVirtualNodes());
for(int i=0;i<allKeys;i++){ consistencyHashAlgorithm.put("key"+i,"value"+i); } //Stream.of(consistencyHashAlgorithm.getRealNodes()).map((node)->node.d); //System.out.println(consistencyHashAlgorithm.getRealNodes());
//System.out.println(realCount+"台物理节点*"+virtualCountPerReal+"虚拟节点:方差="+ConsistencyHashAlgorithm.Variance(consistencyHashAlgorithm.getRealNodes())); System.out.println(realCount+"台物理节点*"+virtualCountPerReal+"虚拟节点：标准差="+ConsistencyHashAlgorithm.StandardDiviation(consistencyHashAlgorithm.getRealNodes()));
}
//方差s^2=[(x1-x)^2 +...(xn-x)^2]/n 或者s^2=[(x1-x)^2 +...(xn-x)^2]/(n-1) public static long Variance(List<Node> realNodes) { long m = realNodes.size(); long sum = 0; for (int i = 0; i < m; i++) {//求和 sum += realNodes.get(i).count(); } long dAve = sum / m;//求平均值 long dVar = 0; for (int i = 0; i < m; i++) {//求方差 dVar += (realNodes.get(i).count() - dAve) * (realNodes.get(i).count() - dAve); } return dVar / m; }
//标准差σ=sqrt(s^2) public static double StandardDiviation(List<Node> realNodes) { double m = realNodes.size(); double sum = 0; for (int i = 0; i < m; i++) {//求和 sum += realNodes.get(i).count(); } double dAve = sum / m;//求平均值 long dVar = 0; for (int i = 0; i < m; i++) {//求方差 dVar += (realNodes.get(i).count() - dAve) * (realNodes.get(i).count() - dAve); } return Math.sqrt(dVar/m); }}
复制代码
package org.geekbang.training.architecture.domain;
/** * 节点顶层接口 * **/public interface Node { /**节点名称**/ void setName(String name); String getName();
/**链接节点*/ void setNode(Node node); Node getNode();
/**节点所在位置*/ void setLocation(int location); int getLocation();
/***获取当前节点拥有的数据总量****/ int count();
/**存放key-value**/ void put(String key,Object value);}
复制代码
package org.geekbang.training.architecture.domain;
/**虚拟节点**/public class VirtualNode implements Node { private String name; private Node node; private int location;
public void setName(String name) { this.name=name; } public String getName() { return this.name; }
public void setNode(Node node) { this.node=node; } public Node getNode() { return this.node; }
public void setLocation(int location) { this.location=location; } public int getLocation() { return this.location; }
@Override public int count() { return 0; }
public void put(String key, Object value) { if(this.getNode()!=null){ this.getNode().put(key,value); } }
@Override public String toString() { return "VirtualNode{" + "name='" + name + '\'' + ", location=" + location + '}'+ "\n"; }}
复制代码
package org.geekbang.training.architecture.domain;
import java.util.HashMap;import java.util.Map;
/** * 真实的物理节点 * */public class RealNode implements Node { private String name; private Node node; private int location; private Map<String,Object> dataContainer = new HashMap<String, Object>();
public void setName(String name) { this.name=name; } public String getName() { return this.name; }
public void setNode(Node node) { this.node=node; } public Node getNode() { return this.node; }
public void setLocation(int location) { this.location=location; } public int getLocation() { return this.location; }
@Override public int count() { return dataContainer.size(); }
public void put(String key, Object value) { if(this.dataContainer!=null){ this.dataContainer.put(key,value); } }
@Override public String toString() { return "RealNode{" + "dataCount=" + dataContainer.size() + '}'+ "\n\r"; }}复制代码
package org.geekbang.training.architecture.domain;
/** * 环的顶层接口 * */public interface Ring { /** * 环大小 * */ int getSize();
/**环指定位置是否已经分配**/ boolean hasAllocated(int index);
/**分配指定位置，同时返回分配位置**/ int allocate(int index);}
复制代码
package org.geekbang.training.architecture.domain;import java.util.BitSet;
/*** * Hash环 * **/public class HashRing implements Ring { private final BitSet ring = new BitSet(Integer.MAX_VALUE);
public int getSize() { return ring.size(); }
public boolean hasAllocated(int index) { return ring.get(index); }
public int allocate(int index) { ring.set(index,true); return index; }}
复制代码
运算结果：
2 台物理节点*50 虚拟节点：标准差=47739.0
2 台物理节点*100 虚拟节点：标准差=30530.0
2 台物理节点*150 虚拟节点：标准差=26201.0
2 台物理节点*200 虚拟节点：标准差=13532.0
2 台物理节点*250 虚拟节点：标准差=15329.0
2 台物理节点*300 虚拟节点：标准差=1176.0
6 台物理节点*50 虚拟节点：标准差=23591.667314258793
6 台物理节点*100 虚拟节点：标准差=5808.248803784722
6 台物理节点*150 虚拟节点：标准差=13536.328576587277
6 台物理节点*200 虚拟节点：标准差=9470.317796497997
6 台物理节点*250 虚拟节点：标准差=15544.157026570037
6 台物理节点*300 虚拟节点：标准差=10657.004488441706
10 台物理节点*50 虚拟节点：标准差=13896.901043038337
10 台物理节点*100 虚拟节点：标准差=9671.903576856006
10 台物理节点*150 虚拟节点：标准差=6788.2378714950755
10 台物理节点*200 虚拟节点：标准差=7049.407875843191
10 台物理节点*250 虚拟节点：标准差=6646.349900509302
10 台物理节点*300 虚拟节点：标准差=5437.565172023228
20 台物理节点*50 虚拟节点：标准差=6711.20229914134
20 台物理节点*100 虚拟节点：标准差=6500.9868866196
20 台物理节点*150 虚拟节点：标准差=4636.415263972804
20 台物理节点*200 虚拟节点：标准差=3909.1144649395983
20 台物理节点*250 虚拟节点：标准差=2550.0566856444584
20 台物理节点*300 虚拟节点：标准差=2778.40628778442
30 台物理节点*50 虚拟节点：标准差=5740.313742877358
30 台物理节点*100 虚拟节点：标准差=3337.666929658101
30 台物理节点*150 虚拟节点：标准差=2451.4641067465514
30 台物理节点*200 虚拟节点：标准差=2062.0947521068633
30 台物理节点*250 虚拟节点：标准差=1713.2171393803726
30 台物理节点*300 虚拟节点：标准差=1848.3133482538433
50 台物理节点*50 虚拟节点：标准差=2560.6388343536464
50 台物理节点*100 虚拟节点：标准差=2461.160701782799
50 台物理节点*150 虚拟节点：标准差=1591.4937888662964
50 台物理节点*200 虚拟节点：标准差=1182.6269234209071
50 台物理节点*250 虚拟节点：标准差=1568.0779062278762
50 台物理节点*300 虚拟节点：标准差=1420.1011231598966
100 台物理节点*50 虚拟节点：标准差=1378.2455078831201
100 台物理节点*100 虚拟节点：标准差=1000.4420023169758
100 台物理节点*150 虚拟节点：标准差=729.865014917142
100 台物理节点*200 虚拟节点：标准差=780.1419486221722
100 台物理节点*250 虚拟节点：标准差=657.0750946429183
100 台物理节点*300 虚拟节点：标准差=576.6288754476313
划线
评论
复制
发布于: 2020 年 10 月 25 日阅读数: 31
张荣召
关注
还未添加个人签名 2018.05.02 加入
还未添加个人简介
评论