一致性 Hash 算法实现 - Java

public interface ConsistentHashing {

    // 支持虚拟节点
    public void addNode(String key, HashNode node) throws UnsupportedEncodingException, NoSuchAlgorithmException;

    // 环需要有序
    public void sort();

    // 取最近的节点
    public HashNode getFirstNode(String key) throws UnsupportedEncodingException, NoSuchAlgorithmException;
}

public class HashNode {

    String val;

    public HashNode(String val) {
        this.val = val;
    }

    public String getVal() {
        return val;
    }
}

public class HashTreeMap implements ConsistentHashing{
    TreeMap<Long, HashNode> treeMap = new TreeMap<>();
    ConsistentHashingAlg hashingAlg;

    public HashTreeMap(String alg) {
        this.hashingAlg = ConsistentHashingAlgFactory.getSignelStrategy(alg);
    }

    // 一个主机节点映射出的虚拟节点数量
    private static final int VIRTUAL_NODE_SIZE = 10;

    @Override
    public void addNode(String key, HashNode node) throws UnsupportedEncodingException, NoSuchAlgorithmException {
        // 加节点自己
        treeMap.put(hashingAlg.hash(key), node);
        // 虚拟节点  对应同一个node
        for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) {
            long hashCode = hashingAlg.hash(key + String.valueOf(i));
            treeMap.put(hashCode, node);
        }
    }

		// TreeMap本身有序
    @Override
    public void sort() { }

    @Override
    public HashNode getFirstNode(String key) throws UnsupportedEncodingException, NoSuchAlgorithmException {
        long hashCode = hashingAlg.hash(key);
        // 取大于参数值的子集
        SortedMap<Long, HashNode> res = treeMap.tailMap(hashCode);
        if (res.isEmpty()) {
            return treeMap.firstEntry().getValue();
        }
        return res.get(res.firstKey());
    }


// 抽象策略
public interface ConsistentHashingAlg {
    public long hash(String value) throws NoSuchAlgorithmException, UnsupportedEncodingException;
}

// 具体策略
public class HashingMD5 implements ConsistentHashingAlg{

    @Override
    public long hash(String value) throws NoSuchAlgorithmException, UnsupportedEncodingException {
        MessageDigest md5 = MessageDigest.getInstance("MD5");
        md5.reset();
        byte[] keyBytes = value.getBytes("UTF-8");
        md5.update(keyBytes);
        byte[] digest = md5.digest();
        // hash code
        long md5Code = ((long) (digest[3] & 0xFF) << 24)
                        | ((long) (digest[2] & 0xFF) << 16)
                        | ((long) (digest[1] & 0xFF) << 8)
                        | (digest[0] & 0xFF);
        long hashCode = md5Code & 0xFFFFFFFFL;
        return hashCode;
    }
}

// 策略工厂
public class ConsistentHashingAlgFactory {
    private static final HashMap<String, ConsistentHashingAlg> strategys = new HashMap<>();

    static {
        strategys.put("MD5", new HashingMD5());
    }

    public static ConsistentHashingAlg getSignelStrategy(String alg) {
        return strategys.get(alg);
    }
}

static String[] ips = {"192.168.2.9", "119.45.56.8", "45.113.8.40", "192.168.10.0", "47.123.8.8",
                    "36.98.233.54", "142.9.0.98", "119.9.72.90", "69.34.3.87", "123.48.9.9"};

    public static void main(String[] args) throws UnsupportedEncodingException, NoSuchAlgorithmException {
        getStandardDeviation();
    }
    
    
    // KV 数据在10个服务器上分布数量的标准差
    // Standard Deviation =（每个服务器上有多少个映射 - 平均值100万除以10）* 2
    private static void getStandardDeviation() throws UnsupportedEncodingException, NoSuchAlgorithmException {
        double avgVal = 1000000 / 10;
        
        HashTreeMap hashTreeMapV = new HashTreeMap("MD5");
        // 存储node的映射数量
        HashMap<String, Integer> nodeMap = new HashMap<>();
        // 创建10个服务器
        for (int i = 0; i < ips.length; i++) {
            hashTreeMapV.addNode(ips[i], new HashNode(ips[i]));
            nodeMap.put(ips[i], 0);
        }
        // 测试 100 万 KV 数据 key = i
        for (int i = 0; i < 1000000; i++) {
            String ip = hashTreeMapV.getFirstNode(String.valueOf(i)).getVal();
            nodeMap.put(ip, nodeMap.get(ip) + 1);
        }
        nodeMap.forEach((key, value) -> System.out.println(key + "  路由数量：" + value));
        
        // 计算方差
        double variance = 0;
        for (double x : nodeMap.values()) {
            variance += Math.pow((x - avgVal), 2);
        }
        variance = variance / ips.length;
        System.out.println("方差：" + new BigDecimal(variance));
        // 计算标准差
        double standardDeviation = Math.sqrt(variance);
        System.out.println("标准差" + standardDeviation);
    }

// 10个节点 * 10个虚拟节点

142.9.0.98   路由数量：79771
45.113.8.40  路由数量：83283
36.98.233.54  路由数量：95133
69.34.3.87  路由数量：103912
47.123.8.8  路由数量：128768
119.9.72.90   路由数量：102948
192.168.10.0  路由数量：102002
192.168.2.9  路由数量：150841
123.48.9.9   路由数量：72650
119.45.56.8  路由数量：80692

方差：527358714
标准差22964.292151076635