分布式缓存一致性 hash 算法实现

关注

发布于: 2020 年 07 月 07 日

1、首先自己需要提供一个hash算法，保证数据足够的分散，Hash算法如下：
   // 需要保证Hash算法的分散
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        // 为负值则取绝对值
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }
﻿
2、需要构造hash环，然后由真实节点生成虚拟节点，如下代码：
    public ConsistentHash(List<String> serverIps, Integer vnCount) {
﻿
        this.vnCount = vnCount;
        for (String ip : serverIps) {
            realNodes.add(ip);
            for (int i = 0; i < vnCount; i++) {
                // 生成虚拟节点ip用于生成虚拟节点hash
                String vnIp = ip + "&&VN" + i;
                // 根据虚拟节点ip生成hash值
                int vnHash = getHash(vnIp);
                // 对应的Hash作为键，将虚拟节点信息作为value，插入到Hash缓存
                hashAndServerIpMap.put(vnHash, vnIp);
            }
        }
    }
﻿
3、对于提供的健值进行hash计算和路由，确定去哪一台服务器上获取数据，提供方法根据健值返回对应真实服务器的ip，代码如下：
    // 根据数据的健值，计算hash值，然后通过空间环查询服务器ip，然后通过服务器ip查找对应的缓存
    public String getServer(String key) {
        // 结算健值对应的Hash值
        Integer hash = getHash(key);
        // 获取hash后面的节点数据
        SortedMap<Integer, String> tailMap = hashAndServerIpMap.tailMap(hash);
        Integer nodeHash;
        // 如果该tailMap为空，则表示hash值大于列表中的最大值，则需要去第一个节点；
        if (CollectionUtils.isEmpty(tailMap)) {
            nodeHash = hashAndServerIpMap.firstKey();
        } else {
            // 否则就去tailMap中的第一个key值，就是对应的虚拟节点的ip
            nodeHash = tailMap.firstKey();
        }
        String vnIp = hashAndServerIpMap.get(nodeHash);
        return vnIp.substring(0, vnIp.indexOf("&&"));
    }
﻿
4、测试代码如下：
  public static void main(String[] args) {
        Map<String, Integer> serverCountMap = new HashMap<>();
        List<String> serverIps = new ArrayList<>();
        Integer dataCount = 1000000;
        Integer vnCount = 1000;
        Integer server = 10;
        for (int i = 0; i < server; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append("127.0.0.1:");
            sb.append(i);
            sb.append(i);
            sb.append(i);
            sb.append(i);
            String serverIp = sb.toString();
            serverIps.add(serverIp);
            serverCountMap.put(serverIp, Integer.valueOf(0));
        }
        ConsistentHash ch = new ConsistentHash(serverIps, vnCount);
        for (int i = 0; i < dataCount; i++) {
            String serverIp = ch.getServer(String.valueOf(i));
            Integer serverCount = serverCountMap.get(serverIp);
            serverCountMap.put(serverIp, serverCount + 1);
        }
        double sd =  getSD(serverCountMap.values(), dataCount/server);
        System.out.println("sd: " + String.valueOf(sd));
    }
    // 计算方差
    public static double getSD(Collection<Integer> serverCount, Integer average) {
        Integer vnCount = serverCount.size();
        double varianceSum = 0d;
        for (Integer value : serverCount) {
            varianceSum = varianceSum + Math.pow((value - average), 2);
        }
        double variance = varianceSum / vnCount;
        return Math.sqrt(variance);
    }
﻿