写点什么

架构师训练营作业 (第五周)

用户头像
王海
关注
发布于: 2020 年 07 月 06 日

作业一

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

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



0 添加依赖

计算hash采用了hutool工具包的方法,计算标准差使用了common-lang3工具中的方法

<dependencies>
<dependency>
<groupId>cn.hutool</groupId>
<artifactId>hutool-all</artifactId>
<version>5.3.7</version>
</dependency>
<!-- https://mvnrepository.com/artifact/org.apache.commons/commons-lang3 -->
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.10</version>
</dependency>
</dependencies>



  1. 定义Hash算法接口

/**
* Hash 算法
*/
public interface HashAlgorithm {
/**
* 计算字符串key的哈希值
* @param key
* @return
*/
public int getHash(String key);
}
  1. Hash算法的几种常见实现

public class BernsteinHash implements HashAlgorithm{
@Override
public int getHash(String key) {
return HashUtil.bernstein(key);
}
}
public class DekHash implements HashAlgorithm{
@Override
public int getHash(String key) {
return HashUtil.dekHash(key);
}
}
public class FnvHash implements HashAlgorithm{
@Override
public int getHash(String key) {
return HashUtil.fnvHash(key);
}
}
public class JavaDefaultHash implements HashAlgorithm{
@Override
public int getHash(String key) {
return HashUtil.javaDefaultHash(key);
}
}
public class SdbmHash implements HashAlgorithm{
@Override
public int getHash(String key) {
return HashUtil.sdbmHash(key);
}
}
  1. 一致性hash类

/**
* 带虚拟节点的一致性Hash算法
*/
public class ConsistentHash {
private HashAlgorithm algorithm;
//待添加入Hash环的服务器列表
private String[] servers ;
//真实结点列表
private List<String> realNodes = new LinkedList<String>();
//虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
private SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
/**
* 虚拟节点数,每个服务器节点增加虚拟服务器的个数
*/
private int virtualNum;
/**
* 各节点分布计数
*/
private static Map<String, AtomicLong> countMap = new ConcurrentHashMap<String, AtomicLong>();
/**
*
* @param hashAlgorithm 指定Hash算法
* @param virtualNum 虚拟节点个数
*/
public ConsistentHash(HashAlgorithm hashAlgorithm,int virtualNum,String [] serverList){
this.algorithm = hashAlgorithm;
this.virtualNum = virtualNum;
this.servers = serverList;
this.init();
}
/**
* 初始化哈希环
*/
private void init() {
//先把原始的服务器添加到真实结点列表中
for (int i = 0; i < servers.length; i++){
realNodes.add(servers[i]);
countMap.put(servers[i],new AtomicLong(0));
}
//再添加虚拟节点
for (String str : realNodes) {
for (int i = 0; i < virtualNum; i++) {
String virtualNodeName = str + "#node" + String.valueOf(i);
int hash = algorithm.getHash(virtualNodeName);
virtualNodes.put(hash, virtualNodeName);
}
}
}
//得到应当路由到的结点
private String put(String key,String value) {
//得到该key的hash值
int hash = algorithm.getHash(key);
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = this.virtualNodes.tailMap(hash);
String virtualNode;
if (subMap.isEmpty()) {
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = virtualNodes.firstKey();
//返回对应的服务器
virtualNode = virtualNodes.get(i);
} else {
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
virtualNode = subMap.get(i);
}
//virtualNode虚拟节点名称要截取一下
if (StringUtils.isNotBlank(virtualNode)) {
String node = virtualNode.substring(0, virtualNode.indexOf("#node"));
AtomicLong atomicLong = countMap.get(node);
atomicLong.incrementAndGet();
countMap.put(node,atomicLong);
return node;
}
return null;
}
public StandardDeviationResult standardDeviation(){
for (int i = 0; i < 1000000; i++) {
put(RandomStringUtils.randomAlphanumeric(20),RandomStringUtils.randomAlphanumeric(6));
}
double[] values = new double[this.servers.length];
int index = 0;
for(Map.Entry<String,AtomicLong> entry : countMap.entrySet()){
values[index] = Double.valueOf(entry.getValue().get()).doubleValue();
index++;
}
double standardDeviation = new StandardDeviation().evaluate(values);
double mean = new Mean().evaluate(values);
return new StandardDeviationResult(algorithm.getClass().getSimpleName(),mean,standardDeviation,this.servers.length,this.virtualNum);
}
}



  1. 标准差计算结果类

public class StandardDeviationResult {
/**
* 算法
*/
private String algorithm;
/**
* 真实节点个数
*/
private int realNodesNum;
/**
* 每个真实节点虚拟节点个数
*/
private int virtualNum;
/**
* 平均值
*/
private double mean;
/**
* 标准差
*/
private double startDeviation;
public StandardDeviationResult(String algorithm,double mean, double startDeviation,int realNodesNum,int virtualNum) {
this.algorithm = algorithm;
this.mean = mean;
this.startDeviation = startDeviation;
this.realNodesNum = realNodesNum;
this.virtualNum = virtualNum;
}
public double getMean() {
return mean;
}
public void setMean(double mean) {
this.mean = mean;
}
public double getStartDeviation() {
return startDeviation;
}
public void setStartDeviation(double startDeviation) {
this.startDeviation = startDeviation;
}
public String getAlgorithm() {
return algorithm;
}
public void setAlgorithm(String algorithm) {
this.algorithm = algorithm;
}
public int getRealNodesNum() {
return realNodesNum;
}
public void setRealNodesNum(int realNodesNum) {
this.realNodesNum = realNodesNum;
}
public int getVirtualNum() {
return virtualNum;
}
public void setVirtualNum(int virtualNum) {
this.virtualNum = virtualNum;
}
@Override
public String toString() {
return "StandardDeviationResult{" +
"algorithm='" + algorithm + '\'' +
", realNodesNum=" + realNodesNum +
", virtualNum=" + virtualNum +
", mean=" + mean +
", startDeviation=" + startDeviation +
'}';
}
}



  1. 测试代码

public class Starter {
public static void main(String[] args) throws Exception {
String [] servers = {
"192.168.31.101",
"192.168.31.102",
"192.168.31.103",
"192.168.31.104",
"192.168.31.105",
"192.168.31.106",
"192.168.31.107",
"192.168.31.108",
"192.168.31.109",
"192.168.31.110"
};
List<HashAlgorithm> hashAlgorithmList = new ArrayList<>();
hashAlgorithmList.add(new JavaDefaultHash());
hashAlgorithmList.add(new FnvHash());
hashAlgorithmList.add(new DekHash());
hashAlgorithmList.add(new BernsteinHash());
hashAlgorithmList.add(new SdbmHash());
for(HashAlgorithm hashAlgorithm : hashAlgorithmList){
ConsistentHash consistentHash = new ConsistentHash(hashAlgorithm,200,servers);
System.out.println(consistentHash.standardDeviation());
}
}
}



  1. 测试结果

StandardDeviationResult{algorithm='JavaDefaultHash', realNodesNum=10, virtualNum=200, mean=100000.0, startDeviation=45656.40662601471}
StandardDeviationResult{algorithm='FnvHash', realNodesNum=10, virtualNum=200, mean=100000.0, startDeviation=9478.64732496737}
StandardDeviationResult{algorithm='DekHash', realNodesNum=10, virtualNum=200, mean=100000.0, startDeviation=190343.8529935875}
StandardDeviationResult{algorithm='BernsteinHash', realNodesNum=10, virtualNum=200, mean=100000.0, startDeviation=39476.91099307994}
StandardDeviationResult{algorithm='SdbmHash', realNodesNum=10, virtualNum=200, mean=100000.0, startDeviation=43083.28226947328}



发布于: 2020 年 07 月 06 日阅读数: 82
用户头像

王海

关注

还未添加个人签名 2018.06.17 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营作业 (第五周)