「架构师训练营」第 5 周作业 - 一致性哈希算法

public class ConsistentHash {
    /**
     * 哈希环最大位置
     */
    private static final Integer MAX_HASH_POSTION = Integer.MAX_VALUE;
    /**
     * 节点的虚拟节点数量
     */
    private final int replicasCount;
    /**
     * Hash环
     */
    private final SortedMap<Integer, String> hashCircle = new TreeMap<>();
    /**
     * 构造方法
     *
     * @param replicasCount 虚拟节点数量
     * @param nodes         节点
     */
    public ConsistentHash(int replicasCount, Collection<String> nodes) {
        this.replicasCount = replicasCount;
        nodes.stream().forEach(node -> {
            add(node);
        });
    }
  
    /**
     * 添加节点
     *
     * @param node 节点名称
     */
    public void add(String node) {
        for (int i = 0; i < replicasCount; i++) {
            int nodeHash = hash(node + "#" + i);
            hashCircle.put(nodeHash, node);
        }
    }
  
    /**
     * 定位节点
     *
     * @param key 键值
     * @return
     */
    public String get(String key) {
        if (hashCircle.isEmpty()) {
            return null;
        }
        int hash = hash(key);
        if (hashCircle.containsKey(hash)) {
            return hashCircle.get(hash);
        }
        SortedMap<Integer, String> tailMap = hashCircle.tailMap(hash);
        return hashCircle.get(tailMap.isEmpty() ? hashCircle.firstKey() : tailMap.firstKey());
    }
    /**
     * 使用 CRC32 算法
     *
     * @param key
     * @return
     */
    public int hash(String key) {
        CRC32 crc32 = new CRC32();
        crc32.update(key.getBytes());
        return (int) (crc32.getValue() % MAX_HASH_POSTION);
    }
}

public class ConsistentHashTest {
    /**
     * 服务器节点数
     */
    private static final Integer SERVER_COUNT = 10;
    /**
     * 统计server命中情况
     */
    Map<String, Integer> serverAllocateCount = new HashMap<>();
    /**
     * 虚拟节点个数
     */
    private static final Integer VIRTURAL_NODES_COUNT = 150;
    /**
     * 一致性哈希算法
     */
    private ConsistentHash consistentHash;
    private static final String source = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    /**
     * 初始化一致性哈希算法的hash环
     */
    @Before
    public void init() {
        List<String> nodes = new ArrayList<>();
        for (int i = 0; i < SERVER_COUNT; i++) {
            String server = "testServer-" + i;
            serverAllocateCount.put(server, 0);
            nodes.add(server);
        }
        consistentHash = new ConsistentHash(VIRTURAL_NODES_COUNT, nodes);
    }
    @Test
    public void testBalance() {
        // 模拟1000000次KV的请求，请求的key随机
        for (int i = 0; i < 1000000; i++) {
            String server = consistentHash.get(randomString(8));
            Integer count = serverAllocateCount.get(server);
            serverAllocateCount.put(server, ++count);
        }
        // 打印落到各个服务器的数量
        printServerAllocate(serverAllocateCount);
        // 标准差
        System.out.println("标准差： " + standardDeviation(serverAllocateCount.entrySet().stream().map(entry -> entry.getValue()).collect(Collectors.toList())));
    }
    /**
     * 生成随机字符串
     *
     * @param length 字符串长度
     * @return
     */
    public String randomString(int length) {
        StringBuffer sb = new StringBuffer();
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            int number = random.nextInt(62);
            sb.append(source.charAt(number));
        }
        return sb.toString();
    }
  
    /**
     * 打印分布情况
     *
     * @param serverAllocateCount
     * @return
     */
    private void printServerAllocate(Map<String, Integer> serverAllocateCount) {
        System.out.println("服务器分配情况：");
        for (Map.Entry<String, Integer> entry : serverAllocateCount.entrySet()) {
            System.out.println(String.format("服务器 [%s] 分配到的次数：%d", entry.getKey(), entry.getValue()));
        }
    }
    /**
     * 标准差计算
     * σ=sqrt(s^2/n)
     *
     * @param input
     * @return
     */
    private double standardDeviation(List<Integer> input) {
        int length = input.size();
        if (length == 0) {
            return 0;
        }
        // 和
        double sum = 0;
        for (Integer num : input) {
            sum += num;
        }
        // 平均值
        double average = sum / length;
        // 方差
        double s = 0;
        for (Integer num : input) {
            s += ((num - average) * (num - average));
        }
        return Math.sqrt(s / length);
    }
}

服务器分配情况：
服务器[testServer-9]分配到的次数：77199
服务器[testServer-8]分配到的次数：65765
服务器[testServer-7]分配到的次数：86737
服务器[testServer-6]分配到的次数：97315
服务器[testServer-5]分配到的次数：127551
服务器[testServer-4]分配到的次数：116312
服务器[testServer-3]分配到的次数：97729
服务器[testServer-2]分配到的次数：104425
服务器[testServer-1]分配到的次数：113640
服务器[testServer-0]分配到的次数：113327
标准差： 18134.422406021098

服务器分配情况：
服务器 [testServer-9] 分配到的次数：77205
服务器 [testServer-8] 分配到的次数：65832
服务器 [testServer-7] 分配到的次数：86361
服务器 [testServer-6] 分配到的次数：97514
服务器 [testServer-5] 分配到的次数：127939
服务器 [testServer-4] 分配到的次数：116683
服务器 [testServer-3] 分配到的次数：97518
服务器 [testServer-2] 分配到的次数：103946
服务器 [testServer-1] 分配到的次数：113379
服务器 [testServer-0] 分配到的次数：113623
标准差： 18233.18947962753

服务器分配情况：
服务器 [testServer-9] 分配到的次数：77443
服务器 [testServer-8] 分配到的次数：65788
服务器 [testServer-7] 分配到的次数：87089
服务器 [testServer-6] 分配到的次数：97279
服务器 [testServer-5] 分配到的次数：127356
服务器 [testServer-4] 分配到的次数：115884
服务器 [testServer-3] 分配到的次数：97449
服务器 [testServer-2] 分配到的次数：103711
服务器 [testServer-1] 分配到的次数：113940
服务器 [testServer-0] 分配到的次数：114061
标准差： 18073.028495523376