写点什么

作业

用户头像
张荣召
关注
发布于: 2020 年 10 月 25 日



作业一(2 选 1):

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

  2. 编写测试用例测试这个算法,测试 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 加入

还未添加个人简介

评论

发布
暂无评论
作业