技术选型一第五周作业「架构师训练营第 1 期」

用户头像
天天向善
关注
发布于: 2020 年 10 月 25 日

作业一

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

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



package com.loadbalance;
import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class OneHashV {
private List<String> serverList = new ArrayList<String>(2000);
private SortedMap<Integer,String> serverHashCycle = new TreeMap<Integer, String>();
private int vnodeLength =150;// 虚拟节点数量
public OneHashV(int nodeNum){
this.vnodeLength = nodeNum;
}
public void addServer(String server){
serverList.add(server);
}
public List<String> getServerList(){
return this.serverList;
}
public void initHashCycle(){
for (String server : serverList) {
for (int i = 0; i < vnodeLength; i++) {
String value = i+"|"+server;
int serverHashCode = getHash(value);
// System.out.println(serverHashCode);
serverHashCycle.put(serverHashCode,value);// 每个服务器节点,都有150个虚拟节点
}
}
}
public int getHash(String input){
// java默认的hashCode不够均匀,相似的字符串为连续的数据 1874591590 1874591591 1874591592等
int hash = input.hashCode();
if (hash < 0)
hash = Math.abs(hash);
hash = (int) (hash % (Math.pow(2,32)));//Math.pow(2,32) 4.294967296E9
return hash;
}
public String getServer(String key){
int keyHashcode = getHash(key);
// System.out.println("获取的:"+keyHashcode);
SortedMap<Integer, String> moreThanKeyHash = serverHashCycle.tailMap(keyHashcode);
if(moreThanKeyHash.isEmpty()){
// 没有大于key hashcode的节点,则取map第一个节点
Integer nodeIndex = serverHashCycle.firstKey();
return mapServer(serverHashCycle.get(nodeIndex));
}else{
// 大于key hashCode
Integer nodeIndex = moreThanKeyHash.firstKey();
return mapServer(moreThanKeyHash.get(nodeIndex));
}
}
// map的value值,是否要处理
public String mapServer(String serverValue){
if(serverValue != null){
String[] split = serverValue.split("\\|");
return split[1];
}
return null;
}
}



进行标准差计算

public class OneHashVTest {
public static void test(int num){
OneHashV oneHash = new OneHashV(num);
oneHash.addServer("192.168.2.1:4444");
oneHash.addServer("192.168.3.1:4445");
oneHash.addServer("192.168.4.1:4446");
oneHash.addServer("192.168.5.1:4447");
oneHash.addServer("192.168.6.1:4448");
oneHash.addServer("192.168.7.1:4449");
oneHash.addServer("192.168.8.1:4450");
oneHash.addServer("192.168.9.1:4451");
oneHash.addServer("192.168.10.1:4452");
oneHash.addServer("192.168.11.1:4453");
oneHash.initHashCycle();
Map<String,Map<String,String>> serverData = new HashMap<String,Map<String,String>>();
// 初始化
List<String> serverList = oneHash.getServerList();
for (String server : serverList) {
Map<String,String> data = new HashMap<String,String>();
serverData.put(server,data);
}
int saveTotal = 1000000;
int serverNum = serverList.size();
int average = saveTotal/serverNum;
System.out.println("存储数据:"+saveTotal+" 服务器数量:"+serverNum+" 虚拟节点:"+num);
for (int i = 0; i < saveTotal; i++) {
String key = i + "key"+i;
String value = i+"value"+i;
String server = oneHash.getServer(key);
Map<String, String> dataMap = serverData.get(server);
dataMap.put(key,value);
}
// 比较每个服务器节点存储的数据的方差
long ftaol = 0;
Iterator<Map.Entry<String, Map<String, String>>> iterator = serverData.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Map<String, String>> next = iterator.next();
String key = next.getKey();
Map<String, String> value = next.getValue();
int size = value.size();
ftaol += ((size-average)*(size-average));
System.out.println("服务器:"+key+" 数量:"+size+" 临时汇总:"+ftaol);
}
System.out.println("方差:"+ftaol);
double stand = Math.sqrt(ftaol);
System.out.println("标准差:"+stand);
System.out.println("================================");
}
public static void main(String[] args) {
test(150);
test(100);
test(50);
}
}

标准差节点如下:

存储数据:1000000服务器数量:10虚拟节点:150

服务器:192.168.7.1:4449数量:95431临时汇总:20875761

服务器:192.168.4.1:4446数量:118183临时汇总:351497250

服务器:192.168.11.1:4453数量:81284临时汇总:701785906

服务器:192.168.5.1:4447数量:108944临时汇总:781781042

服务器:192.168.10.1:4452数量:73907临时汇总:1462625691

服务器:192.168.6.1:4448数量:98723临时汇总:1464256420

服务器:192.168.2.1:4444数量:126798临时汇总:2182389224

服务器:192.168.3.1:4445数量:124693临时汇总:2792133473

服务器:192.168.8.1:4450数量:84231临时汇总:3040794834

服务器:192.168.9.1:4451数量:87806临时汇总:3189488470

方差:3189488470

标准差:56475.55639389487

================================

存储数据:1000000服务器数量:10虚拟节点:100

服务器:192.168.7.1:4449数量:101930临时汇总:3724900

服务器:192.168.4.1:4446数量:89236临时汇总:119588596

服务器:192.168.11.1:4453数量:93355临时汇总:163744621

服务器:192.168.5.1:4447数量:100200临时汇总:163784621

服务器:192.168.10.1:4452数量:87653临时汇总:316233030

服务器:192.168.6.1:4448数量:111096临时汇总:439354246

服务器:192.168.2.1:4444数量:120824临时汇总:872993222

服务器:192.168.3.1:4445数量:119364临时汇总:1247957718

服务器:192.168.8.1:4450数量:83907临时汇总:1506942367

服务器:192.168.9.1:4451数量:92435临时汇总:1564171592

方差:1564171592

标准差:39549.60925217846

================================

存储数据:1000000服务器数量:10虚拟节点:50

服务器:192.168.7.1:4449数量:84658临时汇总:235376964

服务器:192.168.4.1:4446数量:75256临时汇总:847642500

服务器:192.168.11.1:4453数量:116947临时汇总:1134843309

服务器:192.168.5.1:4447数量:76296临时汇总:1696722925

服务器:192.168.10.1:4452数量:117099临时汇总:1989098726

服务器:192.168.6.1:4448数量:99644临时汇总:1989225462

服务器:192.168.2.1:4444数量:89090临时汇总:2108253562

服务器:192.168.3.1:4445数量:112070临时汇总:2253938462

服务器:192.168.8.1:4450数量:111081临时汇总:2376727023

服务器:192.168.9.1:4451数量:117859临时汇总:2695670904

方差:2695670904

标准差:51919.85077020156

 

从结果看,虚拟节点数量为100的效果更好



发布于: 2020 年 10 月 25 日 阅读数: 9
用户头像

天天向善

关注

还未添加个人签名 2018.04.27 加入

还未添加个人简介

评论

发布
暂无评论
技术选型一第五周作业「架构师训练营第 1 期」