第五周 - 作业 1

 关注

发布于: 2020 年 07 月 05 日

﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
public class ConsistencyHash {
    /**
     * key:hash值 , value：虚拟节点host
     */
    final static SortedMap<Integer, String> virtualNode = new TreeMap<>();
    /**
     * key:hostname , value : 分布个数
     */
    final static Map<String, Integer> targetNodeMap = new HashMap<>();
    public static void main(String[] args) {
        //初始化虚拟节点，假设host名称后缀序列是连续的
        int physicsNodeNum = 10;
        int perVirtualNum = 10;
        initVirtualNodes(physicsNodeNum, perVirtualNum);
        //测试数据分布
        int kvNumber = 1000_000;
        testKvDistribution(kvNumber);
        //打印标准差
        printStdevp(kvNumber, physicsNodeNum);
    }
    public static void initVirtualNodes(int physicsNodeNum, int perVirtualNum) {
        //10个node
        String[] hosts = new String[physicsNodeNum];
        for (int i = 0; i < physicsNodeNum; i++) {
            hosts[i] = "hostname" + i;
        }
        //每台有10个虚拟节点
        for (String host : hosts) {
            for (int i = 0; i < perVirtualNum; i++) {
                String vhostName = host.concat("#").concat(String.valueOf(i));
                int hash = getHash(vhostName);
                virtualNode.put(hash, vhostName);
            }
        }
        //打印虚拟节点的hash值与虚拟host
//        for (Map.Entry<Integer, String> entry : virtualNode.entrySet()) {
//            System.out.println(entry.getKey() + "=" + entry.getValue());
//        }
        System.out.println("初始化完成！");
    }
    /**
     * 测试100万条随机key在节点上的分布情况分布
     */
    public static void testKvDistribution(int kvNum) {
        for (int i = 0; i < kvNum; i++) {
            String key = UUID.randomUUID().toString();
            String host = getServer(key);
            if (!targetNodeMap.containsKey(host)) {
                targetNodeMap.put(host, 0);
            }
            targetNodeMap.put(host, targetNodeMap.get(host) + 1);
        }
    }
    public static String getServer(String key) {
        int hash = getHash(key);
        SortedMap<Integer, String> subMap = virtualNode.tailMap(hash);
        String targetNode = "";
        if (!subMap.isEmpty()) {
            targetNode = virtualNode.get(subMap.firstKey());
        } else {
            targetNode = virtualNode.get(virtualNode.firstKey());
        }
        return targetNode.substring(0, targetNode.indexOf("#"));
    }
    public static void printStdevp(int kvNum, int physicsNodeNum) {
        double avg = kvNum / (physicsNodeNum + 0.0d);
        double stdev = 0L;
        for (Map.Entry<String, Integer> entry : targetNodeMap.entrySet()) {
            stdev += Math.pow(entry.getValue() - avg, 2);
        }
        double result = Math.sqrt(stdev / (targetNodeMap.size() + 0.0d));
        System.out.println("标准差为：" + String.format("%.2f", result));
    }
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
        }
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }
    //效果很差，节点不够离散
    private static int getHash2(String str) {
        return str.hashCode() > 0 ? str.hashCode() : Math.abs(str.hashCode());
    }
}
﻿