架构师训练营 - 第五周课后练习

public class HashUtils {
    /**
     *  MurMurHash算法，是非加密HASH算法，性能很高，
     *  比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免）
     *  等HASH算法要快很多，而且据说这个算法的碰撞率很低.
     *  http://murmurhash.googlepages.com/
     */
    public static Long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;
        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);
        long m = 0xc6a4a7935bd1e995L;
        int r = 47;
        long h = seed ^ (buf.remaining() * m);
        long k;
        while (buf.remaining() >= 8) {
            k = buf.getLong();
            k *= m;
            k ^= k >>> r;
            k *= m;
            h ^= k;
            h *= m;
        }
        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }
        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;
        buf.order(byteOrder);
        return h;
    }
}

public class Node {
    private String ip;
    private Map<String, Object> kvPairs = new HashMap<>();

    public Node(String ip) {
        this.ip = ip;
    }

    public void put(String k, Object v) {
        kvPairs.put(k, v);
    }

    public int size() {
        return kvPairs.size();
    }

    public String getIp() {
        return ip;
    }

    @Override
    public String toString() {
        return this.ip;
    }
}

public class ConsistentHash {

    private TreeMap<Long, String> virtualNodes = new TreeMap<>();

    public ConsistentHash(List<Node> nodeList, int virtualCount) {
        for (Node n : nodeList) {
            for (int i=0; i<=virtualCount; i++) {
                long hash = HashUtils.hash(n.getIp() + "#" + i);
                virtualNodes.put(hash, n.getIp());
            }
        }
    }

    public String dispatch(String key) {
        long hash = HashUtils.hash(key);
        Map.Entry<Long, String> entry = virtualNodes.ceilingEntry(hash);
        if (entry == null) {
            entry = virtualNodes.firstEntry();
        }
        return entry.getValue();
    }

    public void printAllNodesWithIndexes() {
        for(Iterator<Long> it = virtualNodes.keySet().iterator();it.hasNext();){
            Long key = it.next();
            System.out.println("hash("+key+")连接到主机->"+virtualNodes.get(key));
        }
    }

    public static void main(String[] args) {
        // 10个物理节点
        int nodeCount = 10;
        // 1百万个KV
        int kvCount = 1000000;
        // 每个物理节点的初始虚拟节点个数，每轮增加个数,最大虚拟节点个数
        int virtualCount = 0;
        int increaseInterval = 100;
        int maxVirtualCount = 1000;
        // 每轮计算次数
        int batchCount = 1;
        for (;virtualCount<=maxVirtualCount;) {
            double standardDeviation = 0.0;
            for (int b=0; b<batchCount; b++) {
                //System.out.println("Batch " + (b+1));
                List<Node> nodeList = new ArrayList<>();

                for (int i = 1; i <= nodeCount; i++) {
                    nodeList.add(new Node("192.168.1." + i));
                }
                Map<String, Node> nodeMap = nodeList.stream().collect(Collectors.toMap(Node::getIp, node -> node));

                ConsistentHash consistentHash = new ConsistentHash(nodeList, virtualCount);
                //consistentHash.printAllNodesWithIndexes();
                for (int i = 0; i < kvCount; i++) {
                    String key = UUID.randomUUID().toString();
                    String value = key;
                    String ip = consistentHash.dispatch(key);
                    nodeMap.get(ip).put(key, value);
                }

                double average = kvCount / nodeCount;
                double variance = 0;
                for (Node node : nodeList) {
                    variance += (node.size() - average) * (node.size() - average);
                }
                //System.out.println("standardDeviation: " + Math.sqrt(variance / nodeCount));
                standardDeviation += Math.sqrt(variance / nodeCount);
            }
            System.out.println("当虚拟节点个数为" + virtualCount + "时, 标准差为" + standardDeviation/batchCount);
            virtualCount += increaseInterval;
        }
    }
}