作业
作业一(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

张荣召
还未添加个人签名 2018.05.02 加入
还未添加个人简介
评论