架构师训练营 week05 作业 -- 一致性 Hash 算法

 关注
发布于: 2020 年 07 月 08 日
作业1、用你熟悉的编程语言实现一致性hash算法。
2、编写测试用例测试这个算法，测试100万KV数据，10个服务器节点的情况下，计算这些KV数据在服务器尚分布数量的标准差，以评估算法的存储负载不均衡性。
实现
public class ConsistentHash {
    // 每个虚拟节点个数
    private final int virtualNodeNumberOfReplicas;
    //哈希环  存储虚拟节点的hash值到真实节点的映射
    private final SortedMap<Integer, String> circle = new TreeMap<>();
    //保存真实服务器和请求次数
    private final TreeMap<String, Integer> servers = new TreeMap<>();
    public ConsistentHash(Collection<String> nodes, int virtualNodeNumberOfReplicas) {
        this.virtualNodeNumberOfReplicas = virtualNodeNumberOfReplicas;
        System.out.println("节点个数：" + nodes.size());
        System.out.println("每个节点虚拟节点个数：" + virtualNodeNumberOfReplicas);
        for (String node:nodes) {
            add(node);
        }
    }
    public String getKey(String nodeKey){
        if(circle.size() == 0){
            return null;
        }
        int hashCode = getHashCode(nodeKey);
        if(!circle.containsKey(hashCode)){
            // 得到大于该Hash值的所有Map
            SortedMap<Integer, String> tailMap = circle.tailMap(hashCode);
            // 第一个Key就是顺时针过去离node最近的那个节点
            hashCode = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        String server = circle.get(hashCode);
        server = server.substring(0, server.indexOf("#"));
        servers.put(server,servers.get(server) + 1);
        return server;
    }
    private int getHashCode(String key) {
        final int p = 16777619;
        int hashCode = (int)2166136261L;
        for (int i = 0; i < key.length(); i++) {
            hashCode = (hashCode ^ key.charAt(i)) * p;
            hashCode += hashCode << 13;
            hashCode ^= hashCode >> 7;
            hashCode += hashCode << 3;
            hashCode ^= hashCode >> 17;
            hashCode += hashCode << 5;
        }
        if (hashCode < 0) {
            hashCode = Math.abs(hashCode);
        }
        return hashCode;
    }
    public void add(String nodeServer){
        if(!servers.containsKey(nodeServer)){
            servers.put(nodeServer,0);
        }
        //添加虚拟节点
        for (int j = 0; j < virtualNodeNumberOfReplicas; j++) {
            String nodeKey  = (String) (nodeServer + "#" + j);
            Integer hashCode = getHashCode(nodeKey);
            circle.put(hashCode,nodeKey);
        }
    }
    public void remove(String nodeServer){
        //删除虚拟节点
        for (int j = 0; j < virtualNodeNumberOfReplicas; j++) {
            circle.remove(getHashCode((String) (nodeServer + "#" + j)));
        }
    }
    public double calcStandardDeviation(){
        Integer[] visitData = new Integer[servers.size()];
        servers.values().toArray(visitData);
        // 计算平均值
        double avg = Arrays.stream(visitData).mapToInt(value -> value).average().orElse(0);
        double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d);
        double std = Math.sqrt(avgStd);
        return std;
    }
    public static void main(String[] args) {
        //服务器节点
        String[] serverNode = {"192.168.0.1","192.168.0.2","192.168.0.3","192.168.0.4","192.168.0.5","192.168.0.6"
        ,"192.168.0.7","192.168.0.8","192.168.0.9","192.168.0.10"};
        ConsistentHash consistentHash  = new ConsistentHash(Arrays.asList(serverNode),100);
        long time = System.currentTimeMillis();
        int countKey = 1000000;
        for (int i = 0; i < countKey; i++) {
            consistentHash.getKey(UUID.randomUUID().toString());
        }
        time = System.currentTimeMillis() - time;
        System.out.println("存入时间差："+time + " ms  \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
        consistentHash  = new ConsistentHash(Arrays.asList(serverNode),1000);
        time = System.currentTimeMillis();
        for (int i = 0; i < countKey; i++) {
            consistentHash.getKey(UUID.randomUUID().toString());
        }
        time = System.currentTimeMillis() - time;
        System.out.println("存入时间差："+time + " ms  \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
        consistentHash  = new ConsistentHash(Arrays.asList(serverNode),2000);
        time = System.currentTimeMillis();
        for (int i = 0; i < countKey; i++) {
            consistentHash.getKey(UUID.randomUUID().toString());
        }
        time = System.currentTimeMillis() - time;
        System.out.println("存入时间差："+time + " ms  \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
        consistentHash  = new ConsistentHash(Arrays.asList(serverNode),3000);
        time = System.currentTimeMillis();
        for (int i = 0; i < countKey; i++) {
            consistentHash.getKey(UUID.randomUUID().toString());
        }
        time = System.currentTimeMillis() - time;
        System.out.println("存入时间差："+time + " ms  \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
        consistentHash  = new ConsistentHash(Arrays.asList(serverNode),5000);
        time = System.currentTimeMillis();
        for (int i = 0; i < countKey; i++) {
            consistentHash.getKey(UUID.randomUUID().toString());
        }
        time = System.currentTimeMillis() - time;
        System.out.println("存入时间差："+time + " ms  \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
        consistentHash  = new ConsistentHash(Arrays.asList(serverNode),6000);
        time = System.currentTimeMillis();
        for (int i = 0; i < countKey; i++) {
            consistentHash.getKey(UUID.randomUUID().toString());
        }
        time = System.currentTimeMillis() - time;
        System.out.println("存入时间差："+time + " ms  \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
    }
}
﻿
result
/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/bin/java -Dfile.encoding=UTF-8 -classpath /Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/tools.jar:/Users/chenlei/private/designpattern/out/production/designpattern com.chenlei.demo.consistenthash.ConsistentHash
节点个数：10
每个节点虚拟节点个数：100
存入时间差：2947 ms  	 ,标准差:6993
节点个数：10
每个节点虚拟节点个数：1000
存入时间差：1778 ms  	 ,标准差:2731
节点个数：10
每个节点虚拟节点个数：2000
存入时间差：1867 ms  	 ,标准差:1433
节点个数：10
每个节点虚拟节点个数：3000
存入时间差：1819 ms  	 ,标准差:1510
节点个数：10
每个节点虚拟节点个数：5000
存入时间差：1939 ms  	 ,标准差:1281
节点个数：10
每个节点虚拟节点个数：6000
存入时间差：2013 ms  	 ,标准差:917
Process finished with exit code 0
﻿
发布于: 2020 年 07 月 08 日阅读数: 33
尔东雨田

 关注
预备用枪！ 2017.12.12 加入
还未添加个人简介
发布
暂无评论