一致哈希

关注
发布于: 2020 年 07 月 07 日
一致Hash的实现方式一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。 当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。
一致哈希在互联网分布式缓存中非常有用的几个特性冗余少，负载均衡，过渡平滑，存储均衡，关键词单调
应用实例（Java）java 代码实现一致性hash算法，测试100万KV 数据，10个服务器节点的情况下，计算这些KV数据在服务器分布数量的标准差，以评估算法的存储负载不均衡性。
/**
 *
 * hash 环
 *
 */
public class HashHoop {
    /**
     * 环上节点数据数量 : (2^31)-1
     */
    final static private Integer hoopSize = Integer.MAX_VALUE;
    /**
     * 真实节点
     */
    List<Node> realNodes;
    /**
     * 虚拟节点数量
     */
    SortedMap<Long, Node> virtualNodes = new TreeMap<>();
    /**
     * 虚拟节点数量
     */
    private int virtualNodeSize;
    /**
     * 初始化Hash环
     * @param realNodes
     * @param virtualNodeSize
     */
    public HashHoop(List<Node> realNodes,int virtualNodeSize){
        this.realNodes = realNodes;
        this.virtualNodeSize = virtualNodeSize;
        constructVirtualNodes();
    }
    /**
     * 使用HashMap的散列码取值方式  借鉴 xxl-job 的代码
     * @param value
     * @return
     */
    public Long getKeyHashCode(String value){
        // md5 byte
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 not supported", e);
        }
        md5.reset();
        byte[] keyBytes;
        try {
            keyBytes = value.getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("Unknown string :" + value, e);
        }
        md5.update(keyBytes);
        byte[] digest = md5.digest();
        // hash code, Truncate to 32-bits
        long hashCode = ((long) (digest[3] & 0xFF) << 24)
                | ((long) (digest[2] & 0xFF) << 16)
                | ((long) (digest[1] & 0xFF) << 8)
                | (digest[0] & 0xFF);
        long truncateHashCode = hashCode & 0xffffffffL;
    
        return truncateHashCode > hoopSize?truncateHashCode%hoopSize:truncateHashCode;
    }
    /**
     * 构建虚拟节点
     */
    private void constructVirtualNodes(){
        /**
         * 遍历每一个真实节点
         */
        for (int i = 0; i < realNodes.size(); i++) {
            String ip = realNodes.get(i).getIp();
            for (int j = 0; j < virtualNodeSize; j++) {
                String virtualIp = ip+"."+j;
                Long key = getKeyHashCode(virtualIp);
                virtualNodes.put(key,realNodes.get(i));
            }
        }
    }
    /**
     * 跟进key获取一个最近的NODE节点
     * @return
     */
    public Node getKeyNode(String key){
        Long hashCode = getKeyHashCode(key);
        Node node;
        if(!virtualNodes.containsKey(hashCode)){
            SortedMap<Long, Node> tailMap = virtualNodes.tailMap(hashCode);
            if(!tailMap.isEmpty()) {
                node = tailMap.get(tailMap.firstKey());
            }else{
                node = virtualNodes.get(virtualNodes.firstKey());
            }
        }else{
            node = virtualNodes.get(hashCode);
        }
        /**
         * 增加命中个数
         */
        node.incrementAndGet();
        return node;
    }
    /**
     * 清空虚拟节点
     */
    public void cleanVirtualNodes() {
        virtualNodes.clear();
    }
    /**
     * 节点类
     */
    static class Node {
        /**
         * 节点ip地址
         */
        private String ip;
        /**
         * 命中计数器
         */
        private AtomicInteger counter = new AtomicInteger(0);
        public Node(String ip){
            this.ip = ip;
        }
        public String getIp() {
            return ip;
        }
        public void incrementAndGet(){
            counter.incrementAndGet();
        }
        public int getCounter(){
            return counter.get();
        }
        public void cleanCounter() {
            counter.set(0);
        }
    }
}
测试用例
public class HashHoopTest {
    static int keySize = 1000000;
    static int nodeSize = 10;
    static List<String> keyList = new ArrayList<>(keySize);
    static List<HashHoop.Node> nodes = new ArrayList<>(nodeSize);
    static{
        for (int i = 0; i < nodeSize; i++) {
            HashHoop.Node node = new HashHoop.Node("127.0.0."+i);
            nodes.add(node);
        }
        for (int i = 0; i < keySize; i++) {
            String key = DigestUtils.md5Hex(""+i);
            keyList.add(key);
        }
    }
    public static List<HashHoop.Node> getNodes() {
        return nodes;
    }
    /**
     * 平均值
     * @param hashHoop
     * @return
     */
    public static long average(HashHoop hashHoop){
        long sum = 0;
        /**
         * key集合遍历查找Node节点
         */
        keyList.stream().forEach(key->hashHoop.getKeyNode(key));
        for (int i = 0; i < nodeSize; i++) {
            sum += nodes.get(i).getCounter();
            System.out.println(nodes.get(i).getIp()+"分配KEY数量:"+nodes.get(i).getCounter());
        }
        return sum / nodeSize;
    }
    /**
     * 标准差计算
     * @param hashHoop
     */
    public static void standardDeviation(HashHoop hashHoop){
        long average = average(hashHoop);
        long deviation = 0;
        for (int i = 0; i < nodeSize; i++) {
            int  counter = nodes.get(i).getCounter();
            deviation += Math.pow(counter - average,2);
        }
        System.out.println("平均值："+average);
        double sqrt = Math.sqrt(Double.valueOf(deviation / keySize));
        System.out.println("标准差："+sqrt);
        nodes.stream().forEach(node ->node.cleanCounter());
        System.out.println("Hash环上单个NODE节点虚拟节点数量 = " + hashHoop.virtualNodes.size()/nodeSize);
        hashHoop.cleanVirtualNodes();
        System.out.println("--------------------------------------------");
    }
    public static void main(String[] args) {
        HashHoop hashHoop = new HashHoop(HashHoopTest.getNodes(),10);
        HashHoopTest.standardDeviation(hashHoop);
        HashHoop hashHoop2 = new HashHoop(HashHoopTest.getNodes(),50);
        HashHoopTest.standardDeviation(hashHoop2);
        HashHoop hashHoop3 = new HashHoop(HashHoopTest.getNodes(),100);
        HashHoopTest.standardDeviation(hashHoop3);
        HashHoop hashHoop4 = new HashHoop(HashHoopTest.getNodes(),150);
        HashHoopTest.standardDeviation(hashHoop4);
        HashHoop hashHoop5 = new HashHoop(HashHoopTest.getNodes(),200);
        HashHoopTest.standardDeviation(hashHoop5);
        HashHoop hashHoop6 = new HashHoop(HashHoopTest.getNodes(),250);
        HashHoopTest.standardDeviation(hashHoop6);
        HashHoop hashHoop7 = new HashHoop(HashHoopTest.getNodes(),300);
        HashHoopTest.standardDeviation(hashHoop7);
        HashHoop hashHoop8 = new HashHoop(HashHoopTest.getNodes(),400);
        HashHoopTest.standardDeviation(hashHoop8);
        HashHoop hashHoop9 = new HashHoop(HashHoopTest.getNodes(),800);
        HashHoopTest.standardDeviation(hashHoop9);
        HashHoop hashHoop10 = new HashHoop(HashHoopTest.getNodes(),1000);
        HashHoopTest.standardDeviation(hashHoop10);
        HashHoop hashHoop11 = new HashHoop(HashHoopTest.getNodes(),1500);
        HashHoopTest.standardDeviation(hashHoop11);
        HashHoop hashHoop12 = new HashHoop(HashHoopTest.getNodes(),2000);
        HashHoopTest.standardDeviation(hashHoop12);
        HashHoop hashHoop13 = new HashHoop(HashHoopTest.getNodes(),2500);
        HashHoopTest.standardDeviation(hashHoop13);
        HashHoop hashHoop14 = new HashHoop(HashHoopTest.getNodes(),3000);
        HashHoopTest.standardDeviation(hashHoop14);
        HashHoop hashHoop15 = new HashHoop(HashHoopTest.getNodes(),4000);
        HashHoopTest.standardDeviation(hashHoop15);
        HashHoop hashHoop16 = new HashHoop(HashHoopTest.getNodes(),5000);
        HashHoopTest.standardDeviation(hashHoop16);
        HashHoop hashHoop17 = new HashHoop(HashHoopTest.getNodes(),6000);
        HashHoopTest.standardDeviation(hashHoop17);
        HashHoop hashHoop18 = new HashHoop(HashHoopTest.getNodes(),10000);
        HashHoopTest.standardDeviation(hashHoop18);
        HashHoop hashHoop19 = new HashHoop(HashHoopTest.getNodes(),20000);
        HashHoopTest.standardDeviation(hashHoop19);
    }
}
输出结果：
127.0.0.0分配KEY数量:141125
127.0.0.1分配KEY数量:77641
127.0.0.2分配KEY数量:104462
127.0.0.3分配KEY数量:39402
127.0.0.4分配KEY数量:149200
127.0.0.5分配KEY数量:89326
127.0.0.6分配KEY数量:117044
127.0.0.7分配KEY数量:72907
127.0.0.8分配KEY数量:116147
127.0.0.9分配KEY数量:92746
平均值：100000
标准差：98.76740352970711
﻿
###### Hash环上单个NODE节点虚拟节点数量 = 10
﻿
127.0.0.0分配KEY数量:120295
127.0.0.1分配KEY数量:97681
127.0.0.2分配KEY数量:108186
127.0.0.3分配KEY数量:91186
127.0.0.4分配KEY数量:101720
127.0.0.5分配KEY数量:103941
127.0.0.6分配KEY数量:105702
127.0.0.7分配KEY数量:99307
127.0.0.8分配KEY数量:84174
127.0.0.9分配KEY数量:87808
平均值：100000
标准差：31.811947441173732
﻿
Hash环上单个NODE节点虚拟节点数量 = 50
--------------------------------------------
﻿
127.0.0.0分配KEY数量:121694
127.0.0.1分配KEY数量:105614
127.0.0.2分配KEY数量:104313
127.0.0.3分配KEY数量:98937
127.0.0.4分配KEY数量:95370
127.0.0.5分配KEY数量:96687
127.0.0.6分配KEY数量:89168
127.0.0.7分配KEY数量:95432
127.0.0.8分配KEY数量:98569
127.0.0.9分配KEY数量:94216
平均值：100000
标准差：26.962937525425527
﻿
Hash环上单个NODE节点虚拟节点数量 = 100
--------------------------------------------
﻿
127.0.0.0分配KEY数量:120371
127.0.0.1分配KEY数量:93826
127.0.0.2分配KEY数量:107440
127.0.0.3分配KEY数量:97381
127.0.0.4分配KEY数量:97180
127.0.0.5分配KEY数量:103809
127.0.0.6分配KEY数量:94609
127.0.0.7分配KEY数量:94630
127.0.0.8分配KEY数量:97632
127.0.0.9分配KEY数量:93122
平均值：100000
标准差：25.45584412271571
﻿
Hash环上单个NODE节点虚拟节点数量 = 150
--------------------------------------------
﻿
127.0.0.0分配KEY数量:108738
127.0.0.1分配KEY数量:98449
127.0.0.2分配KEY数量:101241
127.0.0.3分配KEY数量:104618
127.0.0.4分配KEY数量:94029
127.0.0.5分配KEY数量:105536
127.0.0.6分配KEY数量:101061
127.0.0.7分配KEY数量:97512
127.0.0.8分配KEY数量:94730
127.0.0.9分配KEY数量:94086
平均值：100000
标准差：15.394804318340652
﻿
Hash环上单个NODE节点虚拟节点数量 = 200
--------------------------------------------
﻿
127.0.0.0分配KEY数量:103858
127.0.0.1分配KEY数量:101208
127.0.0.2分配KEY数量:93974
127.0.0.3分配KEY数量:98829
127.0.0.4分配KEY数量:97283
127.0.0.5分配KEY数量:104005
127.0.0.6分配KEY数量:100487
127.0.0.7分配KEY数量:105778
127.0.0.8分配KEY数量:99679
127.0.0.9分配KEY数量:94899
平均值：100000
标准差：11.704699910719626
﻿
Hash环上单个NODE节点虚拟节点数量 = 250
--------------------------------------------
﻿
127.0.0.0分配KEY数量:99023
127.0.0.1分配KEY数量:100131
127.0.0.2分配KEY数量:104517
127.0.0.3分配KEY数量:101558
127.0.0.4分配KEY数量:97920
127.0.0.5分配KEY数量:104116
127.0.0.6分配KEY数量:99918
127.0.0.7分配KEY数量:99310
127.0.0.8分配KEY数量:97203
127.0.0.9分配KEY数量:96304
平均值：100000
标准差：8.18535277187245
﻿
Hash环上单个NODE节点虚拟节点数量 = 300
--------------------------------------------
﻿
127.0.0.0分配KEY数量:96202
127.0.0.1分配KEY数量:102863
127.0.0.2分配KEY数量:104250
127.0.0.3分配KEY数量:97786
127.0.0.4分配KEY数量:92200
127.0.0.5分配KEY数量:108342
127.0.0.6分配KEY数量:98033
127.0.0.7分配KEY数量:96841
127.0.0.8分配KEY数量:103379
127.0.0.9分配KEY数量:100104
平均值：100000
标准差：14.177446878757825
﻿
Hash环上单个NODE节点虚拟节点数量 = 400
--------------------------------------------
﻿
127.0.0.0分配KEY数量:94633
127.0.0.1分配KEY数量:99120
127.0.0.2分配KEY数量:105431
127.0.0.3分配KEY数量:92272
127.0.0.4分配KEY数量:96467
127.0.0.5分配KEY数量:100561
127.0.0.6分配KEY数量:101344
127.0.0.7分配KEY数量:103069
127.0.0.8分配KEY数量:104589
127.0.0.9分配KEY数量:102514
平均值：100000
标准差：13.038404810405298
﻿
Hash环上单个NODE节点虚拟节点数量 = 800
--------------------------------------------
﻿
127.0.0.0分配KEY数量:92340
127.0.0.1分配KEY数量:96464
127.0.0.2分配KEY数量:102144
127.0.0.3分配KEY数量:96956
127.0.0.4分配KEY数量:98458
127.0.0.5分配KEY数量:99034
127.0.0.6分配KEY数量:106667
127.0.0.7分配KEY数量:103118
127.0.0.8分配KEY数量:103775
127.0.0.9分配KEY数量:101044
平均值：100000
标准差：12.529964086141668
﻿
Hash环上单个NODE节点虚拟节点数量 = 1000
--------------------------------------------
﻿
127.0.0.0分配KEY数量:95805
127.0.0.1分配KEY数量:100205
127.0.0.2分配KEY数量:99596
127.0.0.3分配KEY数量:97006
127.0.0.4分配KEY数量:96140
127.0.0.5分配KEY数量:101440
127.0.0.6分配KEY数量:102942
127.0.0.7分配KEY数量:103330
127.0.0.8分配KEY数量:102518
127.0.0.9分配KEY数量:101018
平均值：100000
标准差：8.366600265340756
﻿
Hash环上单个NODE节点虚拟节点数量 = 1500
--------------------------------------------
﻿
127.0.0.0分配KEY数量:97863
127.0.0.1分配KEY数量:99000
127.0.0.2分配KEY数量:100414
127.0.0.3分配KEY数量:95832
127.0.0.4分配KEY数量:99524
127.0.0.5分配KEY数量:99485
127.0.0.6分配KEY数量:103827
127.0.0.7分配KEY数量:103904
127.0.0.8分配KEY数量:100984
127.0.0.9分配KEY数量:99167
平均值：100000
标准差：7.416198487095663
﻿
Hash环上单个NODE节点虚拟节点数量 = 1999
--------------------------------------------
﻿
127.0.0.0分配KEY数量:98910
127.0.0.1分配KEY数量:97507
127.0.0.2分配KEY数量:101462
127.0.0.3分配KEY数量:96531
127.0.0.4分配KEY数量:99710
127.0.0.5分配KEY数量:98873
127.0.0.6分配KEY数量:102404
127.0.0.7分配KEY数量:103315
127.0.0.8分配KEY数量:103511
127.0.0.9分配KEY数量:97777
平均值：100000
标准差：7.483314773547883
﻿
Hash环上单个NODE节点虚拟节点数量 = 2499
--------------------------------------------
﻿
127.0.0.0分配KEY数量:98656
127.0.0.1分配KEY数量:97473
127.0.0.2分配KEY数量:100894
127.0.0.3分配KEY数量:97844
127.0.0.4分配KEY数量:98564
127.0.0.5分配KEY数量:98353
127.0.0.6分配KEY数量:102978
127.0.0.7分配KEY数量:103991
127.0.0.8分配KEY数量:102844
127.0.0.9分配KEY数量:98403
平均值：100000
标准差：7.280109889280518
﻿
Hash环上单个NODE节点虚拟节点数量 = 2999
--------------------------------------------
﻿
127.0.0.0分配KEY数量:98580
127.0.0.1分配KEY数量:99114
127.0.0.2分配KEY数量:100538
127.0.0.3分配KEY数量:98451
127.0.0.4分配KEY数量:99889
127.0.0.5分配KEY数量:97336
127.0.0.6分配KEY数量:102568
127.0.0.7分配KEY数量:102403
127.0.0.8分配KEY数量:103717
127.0.0.9分配KEY数量:97404
平均值：100000
标准差：6.708203932499369
﻿
Hash环上单个NODE节点虚拟节点数量 = 3999
--------------------------------------------
﻿
127.0.0.0分配KEY数量:97525
127.0.0.1分配KEY数量:100191
127.0.0.2分配KEY数量:100284
127.0.0.3分配KEY数量:97420
127.0.0.4分配KEY数量:100041
127.0.0.5分配KEY数量:98076
127.0.0.6分配KEY数量:103928
127.0.0.7分配KEY数量:103534
127.0.0.8分配KEY数量:101713
127.0.0.9分配KEY数量:97288
平均值：100000
标准差：7.3484692283495345
﻿
Hash环上单个NODE节点虚拟节点数量 = 4999
--------------------------------------------
﻿
127.0.0.0分配KEY数量:96725
127.0.0.1分配KEY数量:100410
127.0.0.2分配KEY数量:101926
127.0.0.3分配KEY数量:96919
127.0.0.4分配KEY数量:100816
127.0.0.5分配KEY数量:98944
127.0.0.6分配KEY数量:102739
127.0.0.7分配KEY数量:101814
127.0.0.8分配KEY数量:102444
127.0.0.9分配KEY数量:97263
平均值：100000
标准差：7.0710678118654755
﻿
Hash环上单个NODE节点虚拟节点数量 = 5999
--------------------------------------------
﻿
127.0.0.0分配KEY数量:99748
127.0.0.1分配KEY数量:100050
127.0.0.2分配KEY数量:99580
127.0.0.3分配KEY数量:99728
127.0.0.4分配KEY数量:99997
127.0.0.5分配KEY数量:97555
127.0.0.6分配KEY数量:103172
127.0.0.7分配KEY数量:100651
127.0.0.8分配KEY数量:100517
127.0.0.9分配KEY数量:99002
平均值：100000
标准差：4.242640687119285
﻿
Hash环上单个NODE节点虚拟节点数量 = 9999
--------------------------------------------
﻿
127.0.0.0分配KEY数量:100361
127.0.0.1分配KEY数量:99724
127.0.0.2分配KEY数量:100058
127.0.0.3分配KEY数量:99854
127.0.0.4分配KEY数量:100400
127.0.0.5分配KEY数量:98707
127.0.0.6分配KEY数量:100139
127.0.0.7分配KEY数量:101495
127.0.0.8分配KEY数量:98692
127.0.0.9分配KEY数量:100570
平均值：100000
标准差：2.449489742783178
﻿
Hash环上单个NODE节点虚拟节点数量 = 19998
--------------------------------------------
总结标准差随着虚拟节点的增加而逐渐下降。算法中的 getKeyHashCode 方法借鉴 xxl-job中的源码实现，在虚拟节点设置到 10000 时出现了 一个hashCode值冲突，20000 时增加为2 。虽然标准差的值逐步降低但是同样业务产生了两个疑问 1.虚拟机节点的个数应如何界定？2.有没有一个比较通用的hashCode算法？
发布于: 2020 年 07 月 07 日阅读数: 65
原文链接:【http://xie.infoq.cn/article/709ba7c646f5f4050d26228d4】。文章转载请联系作者。
王鹏飞

关注
还未添加个人签名 2019.06.11 加入
还未添加个人简介
发布
暂无评论
创作场景

一致哈希

一致Hash的实现方式

一致哈希在互联网分布式缓存中非常有用的几个特性

应用实例（Java）

总结

王鹏飞

评论
