实现一致性 hash 算法

模拟1000000PV，10台服务器，每台设置1个虚拟节点，一致性哈希标准差：75637.51284176979

模拟1000000PV，10台服务器，每台设置10个虚拟节点，一致性哈希标准差：65129.27425598347

模拟1000000PV，10台服务器，每台设置100个虚拟节点，一致性哈希标准差：41379.10907692431

模拟1000000PV，10台服务器，每台设置1000个虚拟节点，一致性哈希标准差：38959.18034444656


package architect.hash;

import org.apache.commons.lang3.StringUtils;
import org.junit.Before;
import org.junit.Test;

import java.util.*;

/**
 * @auther: songdewei
 * @date: 2020/7/8
 */
public class Client {
    //待添加入Hash环的服务器列表
    private static String[] servers = {"192.168.0.0:100",
            "192.168.0.1:100",
            "192.168.0.2:100",
            "192.168.0.3:100",
            "192.168.0.4:100",
            "192.168.0.5:100",
            "192.168.0.6:100",
            "192.168.0.7:100",
            "192.168.0.8:100",
            "192.168.0.9:100"};
    //真实节点列表
    private static List<String> realNodes = new LinkedList<>();
    //虚拟节点列表
    private static SortedMap<Integer, String> sortedMap;

    //虚拟节点列表
    private static LinkedHashMap<String, Integer> countMap;


    @Before
    public void before() {
        //添加真实节点
        for (int i = 0; i < servers.length; i++) {
            realNodes.add(servers[i]);
        }
    }

    public void init(int serverVMNum) {
        //添加真实节点
        countMap = new LinkedHashMap<>();
        for (int i = 0; i < servers.length; i++) {
            countMap.put(servers[i], 1);
        }

        sortedMap = new TreeMap<>();
        //添加虚拟节点
        for (String str : realNodes) {
            for (int i = 1; i <= serverVMNum; i++) {
                String nodeName = str + "VM" + String.valueOf(i);
                int hash = nodeName.hashCode();
                sortedMap.put(hash, nodeName);
//                System.out.println("虚拟节点hash:" + hash + "【" + nodeName + "】放入");
            }
        }
    }

    private String getHost(String vmhost){
        if (StringUtils.isNotBlank(vmhost)) {
            String realHost = vmhost.substring(0, vmhost.indexOf("VM"));
            return realHost;
        }
        return null;
    }

    public void simulateConsistentHash(int vmNum, int pv) {
        init(vmNum);
        for (int i = 0; i < pv; i++) {
            String key = Util.getRandomString(40);
            String vmhost = ConsistentHash.getServer(key, sortedMap);
            String serverHost = getHost(vmhost);
            Integer num = countMap.get(serverHost);
            countMap.put(serverHost, num + 1);
        }
        double[] array = new double[countMap.size()];
        for (int i = 0; i < servers.length; i++) {
            array[i] = countMap.get(servers[i]);
        }

        double result = Util.Sample_STD_dev(array);
//        System.out.println("模拟"+pv + "PV，10台服务器，每台设置"+vmNum+"个虚拟节点，一致性哈希计数：" + countMap);
        System.out.println("模拟" + pv + "PV，10台服务器，每台设置" + vmNum + "个虚拟节点，一致性哈希标准差：" + result);
        System.out.println();

    }

    @Test
    public void test() {
        simulateConsistentHash(1, 1000000);
        simulateConsistentHash(10, 1000000);
        simulateConsistentHash(100, 1000000);
        simulateConsistentHash(1000, 1000000);
    }
}


package architect.hash;

import java.util.SortedMap;

/**
 * 一致性哈希算法
 * @auther: songdewei
 * @date: 2020/7/8
 */
public class ConsistentHash {
    //得到应当路由到的结点
    public static String getServer(String key, SortedMap<Integer, String> sortedMap) {
        //得到该key的hash值
        int hash = key.hashCode();
        //得到大于该Hash值的所有Map
        String host;
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            host = sortedMap.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            host = subMap.get(i);
        }
        return host;
    }
}


package architect.hash;

import java.util.Random;

/**
 * 工具类
 * @auther: songdewei
 * @date: 2020/7/8
 */
public class Util {
    // sample standard deviation 样本标准差
    public static double Sample_STD_dev(double[] data) {
        double std_dev;
        std_dev = Math.sqrt(Sample_Variance(data));
        return std_dev;
    }

    //sample variance 样本方差
    public static double Sample_Variance(double[] data) {
        double variance = 0;
        for (int i = 0; i < data.length; i++) {
            variance = variance + (Math.pow((data[i] - Mean(data)), 2));
        }
        variance = variance / (data.length - 1);
        return variance;
    }

    public static double Mean(double[] data) {
        double mean = 0;
        mean = Sum(data) / data.length;
        return mean;
    }

    public static double Sum(double[] data) {
        double sum = 0;
        for (int i = 0; i < data.length; i++) {
            sum = sum + data[i];
        }
        return sum;
    }

    //length用户要求产生字符串的长度
    public static String getRandomString(int length) {
        String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        Random random = new Random();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            int number = random.nextInt(32);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }


}