写点什么

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

用户头像
王海
关注
发布于: 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

版权声明: 本文为 InfoQ 作者【王海】的原创文章。

原文链接:【http://xie.infoq.cn/article/f82534b6c1d464444d37880a9】。未经作者许可，禁止转载。

极客大学架构师训练营
用户头像

王海

关注

还未添加个人签名 2018.06.17 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
架构师训练营作业 (第五周)