一、Hash取模做法的缺陷

在一个redis集群中，如果我们把一条数据经过Hash，然后再根据集群节点数取模得出应该放在哪个节点，这种做法的缺陷在于：扩容(增加一个节点)之后，有大量缓存失效。如果从n个节点增加到n+1个节点，那就有n/(n + 1)的缓存数据失效，造成缓存雪崩。

二、一致性Hash算法

一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，将节点的IP地址或主机名作为关键字进行哈希计算，得出的结果作为节点在环上的位置。数据经过hash后按顺时针方向找到最近一个节点存放，如图data的hash位置，应该存放在node2。

一致性Hash.png

相比Hash取模，一致性Hash算法的优点就是扩容后影响的缓存数据较少，如果是n个节点扩容到n+1个的话，影响的缓存数是0~1/n，即最多让一个节点的缓存失效。
而他的缺点是，缓存在每个节点上分布不均，毕竟hash值随机，那节点在环上的位置也随机。

三、一致性Hash算法 + 虚拟节点

为了解决数据分布不均的问题，我们引入虚拟节点的概念。我们对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。定位到虚拟节点的数据就存到该虚拟节点对应的真实节点上，这样数据分布就相对均匀了，虚拟节点数越多，分布越均匀。一般虚拟节点数32个以上，dubbo是160个。

一致性Hash+虚拟节点.png

四、代码实现

下面贴一下工具类库hutool里的实现

/**
 * 一致性Hash算法
 * 算法详解：http://blog.csdn.net/sparkliang/article/details/5279393
 * 算法实现：https://weblogs.java.net/blog/2007/11/27/consistent-hashing
 * @author xiaoleilu
 *
 * @param <T>   节点类型
 */
public class ConsistentHash<T> implements Serializable{
    private static final long serialVersionUID = 1L;
    
    /** Hash计算对象，用于自定义hash算法 */
    Hash32<Object> hashFunc;
    /** 复制的节点个数 */
    private final int numberOfReplicas;
    /** 一致性Hash环 */
    private final SortedMap<Integer, T> circle = new TreeMap<>();
    
    /**
     * 构造，使用Java默认的Hash算法
     * @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡
     * @param nodes 节点对象
     */
    public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        this.hashFunc = key -> {
            //默认使用FNV1hash算法
            return HashUtil.fnvHash(key.toString());
        };
        //初始化节点
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 构造
     * @param hashFunc hash算法对象
     * @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡
     * @param nodes 节点对象
     */
    public ConsistentHash(Hash32<Object> hashFunc, int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        this.hashFunc = hashFunc;
        //初始化节点
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 增加节点<br>
     * 每增加一个节点，就会在闭环上增加给定复制节点数<br>
     * 例如复制节点数是2，则每调用此方法一次，增加两个虚拟节点，这两个节点指向同一Node
     * 由于hash算法会调用node的toString方法，故按照toString去重
     * @param node 节点对象
     */
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunc.hash32(node.toString() + i), node);
        }
    }

    /**
     * 移除节点的同时移除相应的虚拟节点
     * @param node 节点对象
     */
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunc.hash32(node.toString() + i));
        }
    }

    /**
     * 获得一个最近的顺时针节点
     * @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
     * @return 节点对象
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hashFunc.hash32(key);
        if (false == circle.containsKey(hash)) {
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);   //返回此映射的部分视图，其键大于等于 hash
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        //正好命中
        return circle.get(hash);
    }
}

其实就是用一个TreeMap来作为环，key为虚拟节点下标，value为真实节点的hash。个人感觉可以加一个Map<T, Set<Integer>>来维护真实节点-虚拟节点的关系。

参考：

博客园-明志健致远
B站-CSDN