深入学习一致性 Hash

关注
发布于: 2020 年 07 月 08 日
什么是一致性Hash算法一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用
优点一致性Hash算法有着更好的容错性和扩展性，无论添加还是删除节点，都只会对一小部分数据有影响。
优秀的一致性Hash算法的特点平衡性(Balance)
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
﻿
单调性(Monotonicity)
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
﻿
分散性(Spread)
分散性就是在分布式环境中尽量避免因终端无法看所所有缓存节点而导致的相同内容经过哈希只会被映射到不用缓存的情况，因为这样降低了系统存储的效率。
﻿
负载(Load)
负载就是只特定的一段缓存被映射为不同的内容的情况，好的哈希算法应能够尽量降低缓冲的负荷。
﻿
平滑性(Smoothness)
平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。
﻿
原理核心概念-Hash环哈希函数H的值空间定义为0-2^32-1，然后将整个哈希值空间组织成一个虚拟的圆环，整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环
﻿
原理详解具体使用的时候我们是将各个服务进行Hash的，可以选择服务IP或者服务器主机名作为关键字，通过关键字Hash来计算服务器在Hash环上的位置。如下图
﻿
四台服务器通过Hash函数计算之后分别映射到了4个节点上，将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。
﻿
当我们新增一台服务的时候，只有新增服务器所在的Hash环节点和它上一个节点之间的key收到的了影响，如下图：
﻿
当新增服务器X时候，原来映射到Node c的的Object 2映射到了Node x上了，Hash环上Node B 到Node X之间的key映射结果对应的服务器改变了，其它key未收到的影响。
当有一台服务宕机了的时候，情况如下图
﻿
当服务器B宕机之后，原本映射到服务Node B的Object 1变为映射到Node C了，整个Hash环上，只有Node A到Node B之间的key映射结果受到了影响。
综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性
﻿
虚拟节点一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。
﻿
实现ConsistentHash.java的具体实现如下
public class ConsistentHash<T> {
﻿
    //Hash函数
    private final HashStrategy hashStrategy;
    //虚拟节点倍数
    private final int virtualNodeMultiple ;
    //有序Map构造Hash环
    private final SortedMap<Long, T> circle = new TreeMap<>();
﻿
    /**
     * 有参构造函数
     * @param hashStrategy
     * @param virtualNodeMultiple
     */
    public ConsistentHash(HashStrategy hashStrategy, int virtualNodeMultiple) {
        this.hashStrategy = hashStrategy;
        this.virtualNodeMultiple = virtualNodeMultiple;
    }
﻿
    /**
     * 添加节点
     * @param node
     */
    public void add(T node) {
        for (int i = 0; i < virtualNodeMultiple; i++) {
            long key = hashStrategy.getHashCode(node.toString() + "#" + i);
            circle.put(key, node);
        }
    }
﻿
    /**
     * 移除节点
     * @param node
     */
    public void remove(T node) {
        for (int i = 0; i < virtualNodeMultiple; i++) {
            long key = hashStrategy.getHashCode(node.toString() + "#" + i);
            circle.remove(key);
        }
    }
﻿
    /**
     * 获取服务器节点
     * @param key
     * @return
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        long hash = hashStrategy.getHashCode((String) key);
        //如果没有对应此hash的服务器节点，获取大于等于此hash后面的服务器节点；
        //如果还没有，则获取服务器节点分布圆的第一个节点
        if (!circle.containsKey(hash)) {
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
﻿
    /**
     * 求标准差
     * @param map
     * @return
     */
    public static double StandardDiviation(ConcurrentHashMap<String, LongAdder> map) {
        int size = map.size();
        //求和
        long sum = map.values().stream().mapToLong(LongAdder::longValue).sum();
        //求平均值
        double dAve= sum/size;
        double dVar=0;
        //求方差
        for(Object key:map.keySet()){
            long value = map.get(key).longValue();
            dVar += (value - dAve) * (value - dAve);
        }
        return Math.sqrt(dVar/size);
    }
﻿
﻿
    /**
     * 打印hash环
     * @return
     */
    public String printCircle() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Long, T> entry : circle.entrySet()) {
            sb.append(entry.getKey()).append("=").append(entry.getValue());
            sb.append("&");
        }
        return sb.toString().substring(0, sb.toString().length() - 1);
    }
}
﻿
通过标准差反应一致性Hash的均衡性采用MD5 hash算法，10台服务器，100个虚拟节点，100w的key来验证一致性Hash算法的均衡性
﻿
        //使用MD5 hash算法
        HashStrategy strategy = new Md5Hash();
        //预置10台服务器
        String[] nodes = new String[]{"10.21.100.1","10.21.100.2","10.21.100.3","10.21.100.4","10.21.100.5","10.21.100.6","10.21.100.7","10.21.100.8","10.21.100.9","10.21.100.10"};
        //预设100个虚拟节点
        int virtualNodeMultiple = 100;
        ConsistentHash<String> consistentHash = new ConsistentHash<>(strategy, virtualNodeMultiple);
        //添加服务到和虚拟节点到Hash环上
        for(String node:nodes){
            consistentHash.add(node);
        }
        ConcurrentHashMap<String, LongAdder> map = new ConcurrentHashMap<>();
        for (int i=0; i<1000000; i++){
            map.computeIfAbsent(consistentHash.get(RandomString.getRandomString()), k -> new LongAdder()).increment();
        }
        //打印每台服务器分配到的key数量
        System.out.println(map.toString());
        //打印标准差结果
        System.out.println(ConsistentHash.StandardDiviation(map));
﻿
输出结果如下:
﻿
-----------key分布情况------------
{10.21.100.8=105590, 10.21.100.7=92469, 10.21.100.6=96057, 10.21.100.5=89047, 10.21.100.9=116228, 10.21.100.4=104149, 10.21.100.3=101953, 10.21.100.2=99218, 10.21.100.10=85484, 10.21.100.1=109805}
-----------标准差------------
9029.5056232332
调整虚拟节点的结果影响如下：
﻿
从结果来看增加虚拟节点可以有效的提高均衡性
不同Hash算法的均衡性验证采用10台服务器，100个虚拟节点，100w的key来分别验证DubboHash、Fnv132Hash、Fnv1A32Hash、JDK默认Hash、MurMurHash、OneAtATimeHash的均衡性
﻿
从结果上看Dubbo采用的hash函数均衡性较好，DubboHash 其实就是MD5方式的Hash 函数，具体实现如下：
﻿
public class DubboHash implements HashStrategy {
﻿
    @Override
    public long getHashCode(String value) {
        return hash(md5(value), 0);
    }
﻿
    private long hash(byte[] digest, int number) {
        return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                | (digest[number * 4] & 0xFF))
                & 0xFFFFFFFFL;
    }
﻿
    private byte[] md5(String value) {
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e.getMessage(), e);
        }
        md5.reset();
        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        md5.update(bytes);
        return md5.digest();
    }
}
﻿
guava中提供的一致性hashGuava中有一个Hashing类简单实现了一个一致性哈希的算法
﻿
//bucket是服务器节点数量，返回服务器集合的index值
int bucket = Hashing.consistentHash(id, buckets)
﻿
源码﻿
public static int consistentHash(long input, int buckets) {
    checkArgument(buckets > 0, "buckets must be positive: %s", buckets);
    //使用LCG算法实现产生随机数
    LinearCongruentialGenerator generator = new LinearCongruentialGenerator(input);
    int candidate = 0;
    int next;
﻿
    while (true) {
        // 每次hash的循环中每一个的next的值总是会固定 :
        next = (int) ((candidate + 1) / generator.nextDouble());
﻿
        if (next >= 0 && next < buckets) {
            //  next范围不对，重新计算
            candidate = next;
        } else {
            // 返回这个 candidate 值
            return candidate;
        }
    }
}
﻿
// LCG算法实现，可以参考 http://en.wikipedia.org/wiki/Linear_congruential_generator
private static final class LinearCongruentialGenerator {
    private long state;
﻿
    public LinearCongruentialGenerator(long seed) {
        this.state = seed;
    }
﻿
    public double nextDouble() {
        state = 2862933555777941757L * state + 1;
        return ((double) ((int) (state >>> 33) + 1)) / (0x1.0p31);
    }
}
﻿
均衡性效果采用Md5Hash算法，10台服务器，100个虚拟节点，100w的key来分别验证guava一致性hash算法的均衡性效果如下
标准差：287.63483794561466
﻿
从结果上来看guava的一致性hash算法均衡性非常好，而且使用简单，我们可以在均衡性要求较高的场景使用
﻿