架构师训练营 - 作业 5

关注
发布于: 2020 年 07 月 08 日
作业：用你熟悉的语言实现一致性 hash 算法，编写测试用例测试此算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算服务器分布数量的标准差，以评估算法的存储负载的不均衡性
/** * Create By lhu on 7/7/2020 */public class ConsistentHashTest {    // 物理节点    private Set<String> physicalNodes = new TreeSet<String>() {};
    //虚拟节点    private int VIRTUAL_COPIES = 150; // 物理节点至虚拟节点的复制倍数    private TreeMap<Long, String> virtualNodes = new TreeMap<>();

    /**     * hash算法，输出64位的值     */    public long hash(final byte[] data, int length, int seed) {        final long m = 0xc6a4a7935bd1e995L;        final int r = 47;        long h = (seed & 0xffffffffl) ^ (length * m);        int length8 = length / 8;
        for (int i = 0; i < length8; i++) {            final int i8 = i * 8;            long k = ((long) data[i8 + 0] & 0xff)                    + (((long) data[i8 + 1] & 0xff) << 8)                    + (((long) data[i8 + 2] & 0xff) << 16)                    + (((long) data[i8 + 3] & 0xff) << 24)                    + (((long) data[i8 + 4] & 0xff) << 32)                    + (((long) data[i8 + 5] & 0xff) << 40)                    + (((long) data[i8 + 6] & 0xff) << 48)                    + (((long) data[i8 + 7] & 0xff) << 56);            k *= m;            k ^= k >>> r;            k *= m;            h ^= k;            h *= m;        }
        switch (length % 8) {            case 7:                h ^= (long) (data[(length & ~7) + 6] & 0xff) << 48;            case 6:                h ^= (long) (data[(length & ~7) + 5] & 0xff) << 40;            case 5:                h ^= (long) (data[(length & ~7) + 4] & 0xff) << 32;            case 4:                h ^= (long) (data[(length & ~7) + 3] & 0xff) << 24;            case 3:                h ^= (long) (data[(length & ~7) + 2] & 0xff) << 16;            case 2:                h ^= (long) (data[(length & ~7) + 1] & 0xff) << 8;            case 1:                h ^= (long) (data[length & ~7] & 0xff);                h *= m;        }
        h ^= h >>> r;        h *= m;        h ^= h >>> r;        return h;    }


    public long hash(final byte[] data, int length) {
        return hash(data, length, 0xe17a1465);
    }
    public long Hash(final String data) {        byte[] bytes = toBytesWithoutEncoding(data);        return hash(bytes, bytes.length);    }
    private byte[] toBytesWithoutEncoding(String str) {        int len = str.length();        int pos = 0;        byte[] buf = new byte[len << 1];        for (int i = 0; i < len; i++) {            char c = str.charAt(i);            buf[pos++] = (byte) (c & 0xFF);            buf[pos++] = (byte) (c >> 8);        }        return buf;    }
    // 根据物理节点，构建虚拟节点映射表,使用默认的虚拟节点数量1    public ConsistentHashTest(Set<String> physicalNodes) {        this(physicalNodes,0);    }
    // 根据物理节点，构建虚拟节点映射表    public ConsistentHashTest(Set<String> physicalNodes, int virtualCopyCount) {        for (String nodeIp : physicalNodes) {            addPhysicalNode(nodeIp);        }        if (virtualCopyCount>=1)            VIRTUAL_COPIES = virtualCopyCount;    }
    // 添加物理节点    public void addPhysicalNode(String nodeIp) {        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {            long hash = Hash(nodeIp + "#" + idx);            virtualNodes.put(hash, nodeIp);        }        physicalNodes.add(nodeIp);    }
    // 删除物理节点    public void removePhysicalNode(String nodeIp) {        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {            long hash = Hash(nodeIp + "#" + idx);            virtualNodes.remove(hash);        }        physicalNodes.remove(nodeIp);    }
    // 查找对象映射的节点    public String getObjectNode(String object) {        long hash = Hash(object);        SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点        Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();        return virtualNodes.get(key);    }
    // 统计对象与节点的映射关系    public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {        // 统计        Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT        for (int object = objectMin; object <= objectMax; ++object) {            String nodeIp = getObjectNode(Integer.toString(object));
            Integer count = objectNodeMap.get(nodeIp);            objectNodeMap.put(nodeIp, (count == null ? 1 : count + 1));        }
        // 打印        double totalCount = objectMax - objectMin + 1;        System.out.println("======== " + label + " ========");        double[] counts4StandardDiviation = new double[objectNodeMap.entrySet().size()];        int i = 0;        for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
            int count = entry.getValue();            counts4StandardDiviation[i] = count;            System.out.println("IP=" + entry.getKey() + ": count=" + count + "");            i++;        }        System.out.println("Physical node count: "+physicalNodes.size()+", Virtual node count per physical node: "+VIRTUAL_COPIES+", standard deviation: "+StandardDeviation(counts4StandardDiviation));    }
    //方差s^2=[(x1-x)^2 +...(xn-x)^2]/n 或者s^2=[(x1-x)^2 +...(xn-x)^2]/(n-1) 标准差σ=sqrt(s^2)    public static double StandardDeviation(double[] x) {        int m=x.length;        double sum=0;        for(int i=0;i<m;i++){//求和            sum+=x[i];        }        double dAve=sum/m;//求平均值        double dVar=0;        for(int i=0;i<m;i++){//求方差            dVar+=(x[i]-dAve)*(x[i]-dAve);        }        //reture Math.sqrt(dVar/(m-1));        return Math.sqrt(dVar/m);    }

    public static void main(String[] args) {        Set<String> physicalNodes = new TreeSet<String>() {            {                add("192.168.1.101");                add("192.168.1.102");                add("192.168.1.103");                add("192.168.1.104");                add("192.168.1.105");                add("192.168.1.106");                add("192.168.1.107");                add("192.168.1.108");                add("192.168.1.109");                add("192.168.1.110");            }        };
        ConsistentHashTest ch = new ConsistentHashTest(physicalNodes,180);        // 初始情况        ch.dumpObjectNodeMap("初始情况", 1, 1000000);
        // 删除物理节点        ch.removePhysicalNode("192.168.1.103");        ch.dumpObjectNodeMap("删除物理节点", 1, 1000000);
        // 添加物理节点        ch.addPhysicalNode("192.168.1.111");        ch.addPhysicalNode("192.168.1.112");        ch.dumpObjectNodeMap("添加物理节点", 1, 1000000);    }}