「架构师训练营第 1 期」第五周作业

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



作业一(2 选 1):

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

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



import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
* * 带虚拟节点的一致性哈希算法
*/
public class ConsistentHashingWithVirtualNode {
/**
* * 真实节点类
*/
static class ServerNode {
String name;
volatile AtomicInteger requestHit = new AtomicInteger(0); //计算请求次数
public ServerNode(String name) {
this.name = name;
}
public void request() {
requestHit.incrementAndGet();
}
}
/**
* * 虚拟节点类
*/
static class VirtualNode {
String name;
ServerNode serverNode;
int hash;
public VirtualNode(int i, ServerNode serverNode) {
this.serverNode = serverNode;
this.name = "VirtualNode-" + i + "-" + serverNode.name;
}
public void request() {
serverNode.request();
}
public void setHash(int hash) {
this.hash = hash;
}
}
/**
* * 真实节点
*/
private static List<ServerNode> serverNodes = new ArrayList<>();
/**
* * 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点
*/
private static SortedMap<Integer, VirtualNode> virtualNodes = new TreeMap<>();
/**
* * 真实节点的数目
*/
private static final int SERVER_NODE_NUM = 10;
/**
* * 虚拟节点的数目
*/
private static final int VIRTUAL_NODES = 150;
static {
// 初始化真实服务器节点
for (int i = 0; i < SERVER_NODE_NUM; i++) {
serverNodes.add(new ServerNode("ServerNode-" + i));
}
// 添加虚拟节点
for (ServerNode serverNode : serverNodes) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
VirtualNode virtualNode = new VirtualNode(i, serverNode);
//确保所有的虚拟节点都能被初始化
int j = 0;
while (virtualNodes.containsKey(getHash(virtualNode.name + j))) {
j++;
}
int hash = getHash(virtualNode.name + j);
virtualNode.setHash(hash);
virtualNodes.put(hash, virtualNode);
// System.out.println("虚拟节点[" + virtualNode.name + "]被添加, hash值为" + hash);
}
}
}
/**
* 哈希算法,可扩展
*/
private static int getHash(String str) {
int hashCode = str.hashCode();
return Math.floorMod(Math.abs(hashCode), SERVER_NODE_NUM * VIRTUAL_NODES);
}
/**
* 发起请求
*/
private static void request(String requestkey) {
// 计算路由Key
int hash = getHash(requestkey);
// 得到大于该Hash值的所有Map
SortedMap<Integer, VirtualNode> subMap = virtualNodes.tailMap(hash);
int i = subMap.firstKey();
VirtualNode virtualNode = virtualNodes.get(i);
virtualNode.request();
}
/**
* 计算平均值
*/
public static double average(List<Double> hits) {
double sumHit = 0;
for (Double hit : hits) {
sumHit += hit;
}
return sumHit / hits.size();
}
/**
* 计算方差
* 方差s^2=[(x1-x)^2+(x2-x)^2+......(xn-x)^2]/(n)(x为平均数)
*/
public static double variance(List<Double> hits) {
double avg = average(hits); //求平均值
double var = 0;
for (double i : hits) {
var += (i - avg) * (i - avg); //(x1-x)^2+(x2-x)^2+......(xn-x)^2
}
return var / hits.size();
}
/**
* 计算标准差
* 标准差σ=sqrt(s^2),即标准差=方差的平方根
*/
public static double standardDiviation(List<Double> hits) {
return Math.sqrt(variance(hits));
}
public static String getRandomString(int length) {
String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
Random random = new Random();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < length; i++) {
int number = random.nextInt(62);
sb.append(str.charAt(number));
}
return sb.toString();
}
public static void main(String[] args) {
int requestTimes = 1000000;
for (int i = 0; i < requestTimes; i++) {
String requestKey = getRandomString(100);
request(requestKey);
}
List<Double> hits = new ArrayList<>();
for (ServerNode serverNode : serverNodes) {
// System.out.println(serverNode.requestHit);
hits.add(Double.valueOf(serverNode.requestHit.get()));
}
System.out.println("测试环境:");
System.out.println("真实节点数:" + SERVER_NODE_NUM + " 虚拟节点数:" + VIRTUAL_NODES + " 请求次数:" + requestTimes);
System.out.println("测试结果:");
System.out.println("平均值:" + average(hits) + " 方差:" + variance(hits) + " 标准差:" + standardDiviation(hits));
}
}



测试环境:
真实节点数:10 虚拟节点数:150 请求次数:1000000
测试结果:
平均值:100000.0 方差:41570.4 标准差:203.88820466128



用户头像

张国荣

关注

还未添加个人签名 2018.06.26 加入

还未添加个人简介

评论

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