【算法技术专题】如何用 Java 实现一致性 hash 算法（ consistent hashing ）（上）

一致性 hash 的历史

【Consistent Hashing 算法】早在 1997 年就在论文 Consistent hashing and random trees 中被提出，目前在 cache 系统中应用越来越广泛；

一致性 hash 的目的

一致性哈希算法是分布式系统中常用的算法，一致性哈希算法解决了普通余数 Hash 算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

问题背景

业务开发中，我们常把数据持久化到数据库中，如果需要读取这些数据，除了直接从数据库中读取外，为了减轻数据库的访问压力以及提高访问速度，更多地引入缓存来对数据进行存取。

分布式缓存

分布式缓存，不同机器上存储不同对象的数据。为了实现这些缓存机器的负载均衡，一般就会存在两种 Hash 算法进行均匀分配数据节点存储：普通 Hash 算法

普通的 Hash 算法的

Hash 取模做法的缺陷

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

普通 Hash 的案例分析

比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；

hash(object)%N 

一切都运行正常，再考虑如下的两种情况；

• 一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1) ；

• 由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1) ；

• 这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；（造成缓存雪崩机制）

一致性 Hash 算法

一致性 hash 算法正是为了解决此类问题的方法，它可以保证当机器增加或者减少时，对缓存访问命中的概率影响减至很小。下面我们来详细说一下一致性 hash 算法的具体过程。

• 一致性 hash 算法通过一个叫作一致性 hash 环的数据结构实现。这个环的起点是 0，终点是 2^32 - 1，并且起点与终点连接，环的中间的整数按逆时针分布，故这个环的整数分布范围是[0, 2^32-1]

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

• 相比 Hash 取模，一致性 Hash 算法的优点就是扩容后影响的缓存数据较少，如果是 n 个节点扩容到 n+1 个的话，影响的缓存数是 0~1/n，即最多让一个节点的缓存失效。

• 他的缺点是，缓存在每个节点上分布不均，毕竟 hash 值随机，那节点在环上的位置也随机。

改良版一致性 Hash 算法

一致性 Hash 算法 + 虚拟节点

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

引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系

一般虚拟节点数 32 个以上，dubbo 是 160 个。

处理机器增减的情况

对于线上的业务，增加或者减少一台机器的部署是常有的事情。

例如，增加机器 c4 的部署并将机器 c4 加入到 hash 环的机器 c3 与 c2 之间。这时，只有机器 c3 与 c4 之间的对象需要重新分配新的机器。对于我们的例子，只有对象 o4 被重新分配到了 c4，其他对象仍在原有机器上。

一致性 Hash 算法的实现原理

在业务开发中，我们常把数据持久化到数据库中。如果需要读取这些数据，除了直接从数据库中读取外，为了减轻数据库的访问压力以及提高访问速度，我们更多地引入缓存来对数据进行存取。读取数据的过程一般为：

Java 代码实现 Hash 算法的实现

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

/** * 一致性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);    }}

参考资料

• http://weblogs.java.net/blog/2007/11/27/consistent-hashing 上面有一个 java 版本的例子，可以参考。

• http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx 转载了一个 PHP 版的实现代码。

• http://www.codeproject.com/KB/recipes/lib-conhash.aspx C 语言版本

• http://portal.acm.org/citation.cfm?id=258660

• http://en.wikipedia.org/wiki/Consistent_hashing

• http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

• http://weblogs.java.net/blog/2007/11/27/consistent-hashing

• http://tech.idv2.com/2008/07/24/memcached-004/

• http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx