理解一致性哈希算法

场景分析

在分布式缓存的伸缩性设计中，最主要的目标就是在新加入缓存服务器后，应该使整个服务器集群中已经缓存的数据尽可能还被访问到。对于服务器集群管理，路由算法至关重要，它决定着客户端究竟该访问集群中的哪台服务器。

余数Hash

简单的路由算法可以使用余数Hash：

用服务器数目除缓存数据key的Hash值，余数为服务器列表下标编号。

该思路的简单代码实现如下：

class RemainderHash {

    private List<String> serverNodes;
    private int serverNodeSize;

    public RemainderHash(List<String> serverNodes) {
        this.serverNodes = serverNodes;
        this.serverNodeSize = serverNodes.size();
    }

    public String getServerNode(String key) {
        return serverNodes.get(hash(key));
    }

    public int hash(String key) {
        return Math.abs(key.hashCode() % serverNodeSize);
    }
}

该算法可以保证缓存数据在整个服务器集群的均衡分布。
但是假如服务器由3台扩容至4台，扩容前后的缓存重复命中率（扩容前后，同一缓存数据仍在同一服务器上）只有24.99%，而假如服务器由100台扩容至101台，扩容前后的缓存重复命中率只有0.71%。均衡性和重复命中率的测试代码在这

所以这种余数Hash算法不能满足实际生产需要。

一致性Hash算法的思想

要解决上述问题，目前比较流行的算法是一致性Hash算法，该算法通过一致性Hash环的数据结构实现key到缓存服务器的映射。

该算法的具体过程为：
①先构造一个长度为2³²的整数环（称作一致性Hash环），
②根据节点名称的Hash值（其分布范围为[0, 2³²-1]）将缓存服务器节点放置在这个Hash环上；（要保证n个服务器节点均衡地放置在环上）
③根据缓存数据的key的Hash值（其分布范围也为[0, 2³²-1]）在Hash环上顺时针查找距离这个key的Hash值最近的缓存服务器节点，即为该数据应该放置的的服务器。

一致性Hash示意图.png

图中，以Node开头的圆形表示服务器，以key开头的方形表示缓存数据，带箭头的虚线表示缓存数据应该放置在哪台服务器。可以看出，在新增一台服务器后，受影响的缓存数据只是分布在Node2和Node4之间的一小段（顺时针）数据。

但是，上面描述的算法存在一个问题：新加入的结点Node4只影响了Node3，原来的Node1和Node2不受影响，即扩容后，每台服务器的负载不同，没有达到缓存数据均衡分布在各台服务器上的效果。

上述负载不均衡问题的解决方案是使用虚拟层：将每台物理服务器虚拟为一组虚拟缓存服务器，将虚拟缓存服务器的Hash值放置在Hash环上，缓存数据通过key的Hash值首先找到虚拟服务器节点，再找到这个虚拟服务器节点对应的物理服务器。
使用虚拟节点后，缓存数据在服务器节点的分布示意图如下：（图片来源：The Simple Magic of Consistent Hashing）

使用虚拟节点的一致性Hash算法示意图.png

这样，在新加入一个物理服务器节点时，是将一组虚拟节点（假设数量为n）加入环中，这些虚拟节点会影响n个虚拟节点，受影响的n个虚拟节点又对应不同的物理服务器，最终，新加入一台服务器将会分摊原集群中所有服务器的一部分负载，从而达到负载均衡的目的。（每个物理节点对应的虚拟节点越多，各物理节点之间的负载越均衡，但太多会影响性能。在实践中，经验值为150）。

一致性Hash算法的实现

public class ConsistentHash<T> {

    /**
     * 哈希函数
     */
    private final HashFunction hashFunction;
    /**
     * 每台物理服务器节点虚拟出虚拟节点个数
     */
    private final int numberOfReplicas;
    /**
     * Hash环
     * <p>
     * 该Map中仅存放虚拟服务器节点，并不存放实际的缓存数据！！！
     * 该Map中key为虚拟服务器节点对应在环中的位置
     * <p>
     * 使用TreeMap的原因：
     * TreeMap的内部使用红黑树（平衡查找树），
     * 因而在确定了一个缓存数据key的hash值在该环中的位置后，
     * 可以很快查找到该缓存数据应该放置的物理服务器
     */
    private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

    /**
     * 构造器
     *
     * @param hashFunction     哈希函数
     * @param numberOfReplicas 每台物理服务器节点虚拟出虚拟节点个数
     * @param nodes            物理服务器节点
     */
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {

        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        //将物理服务器放在环上
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 添加物理服务器节点
     * <p>
     * 实现：将该物理服务器节点放在环中的numberOfReplicas个位置处，
     * （添加一个物理服务器节点，就要添加numberOfReplicas个虚拟节点）
     *
     * @param node 要添加的物理服务器节点
     */
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunction.hash(node.toString() + i),
                    node);
        }
    }

    /**
     * 移除物理服务器节点
     * <p>
     * 实现：因为该物理服务器节点放在了环中的多个位置，所以在删除时都要删除
     * （移除一个物理服务器节点，就要将该服务器节点对应的numberOfReplicas个虚拟节点移除）
     *
     * @param node 要移除的物理服务器节点
     */
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunction.hash(node.toString() + i));
        }
    }

    /**
     * 根据缓存数据的key获取物理服务器节点
     *
     * @param key 缓存数据的key
     * @return 该缓存数据所在的物理服务器节点
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hashFunction.hash(key);
        //如果缓存数据的key的哈希值没有落在虚拟服务器节点上，
        //则
        if (!circle.containsKey(hash)) {
            //获取map中key值大于该缓存数据的key的哈希值的子map
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            //如果该子map不为空，则返回该子map的第一个元素（因为该map是排序好的，第一个即是最小的元素）
            //如果该子map为空，说明该缓存数据的key的哈希值超出了哈希环中最后的那个虚拟服务器节点对应的位置（顺时针），
            //                则将该缓存数据放在哈希环中第一个虚拟服务器节点中（顺时针）
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

}


class HashFunction {

    int hash(Object key) {
        return key.hashCode();
    }
}

上述代码中，Hash算法有待改进，因为Hash算法至关重要，大部分Object的hashCode()方法不能很好地得到分布均衡的哈希值，比如，通常这些哈希值都是一定范围内的比较小的整数。

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2，但由于MD5碰撞案例较多，因此，MD5在数年前就已经不被推荐作为应用中的散列算法方案，取代它的是安全散列算法。

//TODO 哈希算法归类

那么如何使用一致性Hash呢？通常，只会在别人的依赖库里遇到一致性Hash算法，而不是自己编写。比如，大部分的支持分布式的缓存组件的客户端都支持一致性哈希。值得注意的是，仅仅客户端需要实现一致性哈希算法，缓存服务器除了缓存数据，什么都不用做。

参考

①《大型网站技术架构--核心原理与案例分析》：（文字描述部分）
② Consistent Hashing ：（一致性算法的代码）
③ Hash算法总结
④ The Simple Magic of Consistent Hashing