架构师训练营 第五周 作业

import java.util.*;
public class ConsistentHash {
    /** 真实节点列表 */
    private List<String> nodes = new ArrayList<>();
    /** 每个物理节点对应虚拟节点个数 */
    private int replicaCount = 1;
    /** hash环 */
    private SortedMap<Integer, String> circle = new TreeMap<>();
    public ConsistentHash(List<String> nodes, int replicaCount) {
        this.replicaCount = replicaCount;
        for(String node : nodes) {
            addNode(node);
        }
    }
    // 增加节点
    public void addNode(String node) {
        for(int i = 0; i < replicaCount; i++) { // 使用虚拟节点计算hash值
            circle.put(hash(node + "&" + i), node);
        }
        nodes.add(node);
    }
    public String getNode(String key) {
        // 如果没有大于key的hash值，则取第一个节点；否则取大于key的hash值最近的一个节点
        int hash = hash(key);
        SortedMap<Integer, String> subMap = circle.tailMap(hash);
        return subMap.isEmpty() ? circle.get(circle.firstKey()) : subMap.get(subMap.firstKey());
    }
    // hash值计算: FNV132 算法
    private static int hash(String key) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            hash = (hash ^ key.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash < 0 ? Math.abs(hash) : hash;
    }
    @Override
    public String toString() {
        return "ConsistentHash{" +
                "nodes=" + nodes +
                ", replicaCount=" + replicaCount +
                ", circle=" + circle +
                '}';
    }
    public static void main(String[] args) {
        String[] servers = {"10.0.0.1:80", "10.0.0.2:80", "10.0.0.3:80", "10.0.0.4:80", "10.0.0.5:80",
                "10.0.0.6:80", "10.0.0.7:80", "10.0.0.8:80", "10.0.0.9:80", "10.0.0.10:80"};
        final int KV_COUNT = 1000000;
        for(int i = 1; i <= 10000; i *= 10) { // 测试1,10,100,1000,10000个虚拟节点的标准差
            test(servers, i, KV_COUNT);
        }
    }
    private static void test(String[] servers, int replicaCount, int kvCount) {
        ConsistentHash hash = new ConsistentHash(Arrays.asList(servers), replicaCount);
        // System.out.println(hash);
        Map<String, Integer> nodeCount = new HashMap<>();
        for(int i = 0; i < kvCount; i++) {
            String key = "test" + i;
            String node = hash.getNode(key);
            // 累计每个节点上的缓存个数
            if (nodeCount.containsKey(node)) {
                nodeCount.put(node, nodeCount.get(node) + 1);
            } else {
                nodeCount.put(node, 1);
            }
        }
        System.out.println(nodeCount);
        System.out.println(replicaCount + "个虚拟节点的标准差: " + standardDevition(nodeCount.values()));
    }
    public static double standardDevition(Collection<Integer> arrays) {
        if (arrays.isEmpty()) {
            return 0;
        }
        double sum = 0;
        for(Integer i : arrays) {
            sum += i;
        }
        double average = sum / arrays.size();
        sum = 0;
        for(Integer i : arrays) {
            sum += ((double)i - average) * ((double)i - average);
        }
        return Math.sqrt(sum / arrays.size());
    }
}