本文主要讲解了一致性哈希算法的原理以及其存在的数据倾斜的问题，然后引出解决数据倾斜问题的方法，最后分析一致性哈希算法在 Dubbo 中的使用。通过这篇文章，可以了解到一致性哈希算法的原理以及这种算法存在的问题和解决方案。

一、负载均衡

在这里引用 dubbo 官网的一段话——

LoadBalance 中文意思为负载均衡，它的职责是将网络请求，或者其他形式的负载 “均摊” 到不同的机器上。避免集群中部分服务器压力过大，而另一些服务器比较空闲的情况。通过负载均衡，可以让每台服务器获取到适合自己处理能力的负载。在为高负载服务器分流的同时，还可以避免资源浪费，一举两得。负载均衡可分为软件负载均衡和硬件负载均衡。在我们日常开发中，一般很难接触到硬件负载均衡。但软件负载均衡还是可以接触到的，比如 Nginx。在 Dubbo 中，也有负载均衡的概念和相应的实现。Dubbo 需要对服务消费者的调用请求进行分配，避免少数服务提供者负载过大。服务提供者负载过大，会导致部分请求超时。因此将负载均衡到每个服务提供者上，是非常必要的。Dubbo 提供了 4 种负载均衡实现，分别是基于权重随机算法的 RandomLoadBalance、基于最少活跃调用数算法的 LeastActiveLoadBalance、基于 hash 一致性的 ConsistentHashLoadBalance，以及基于加权轮询算法的 RoundRobinLoadBalance。这几个负载均衡算法代码不是很长，但是想看懂也不是很容易，需要对这几个算法的原理有一定了解才行。

二、哈希算法

图 1 无哈希算法请求

如上所示，假设 0,1,2 号服务器都存储的有用户信息，那么当我们需要获取某用户信息时，因为我们不知道该用户信息存放在哪一台服务器中，所以需要分别查询 0,1,2 号服务器。这样获取数据的效率是极低的。

对于这样的场景，我们可以引入哈希算法。

图 2 引入哈希算法后的请求

还是上面的场景，但前提是每一台服务器存放用户信息时是根据某一种哈希算法存放的。所以取用户信息的时候，也按照同样的哈希算法取即可。

假设我们要查询用户号为 100 的用户信息，经过某个哈希算法，比如这里的 userId mod n，即 100 mod 3 结果为 1。所以用户号 100 的这个请求最终会被 1 号服务器接收并处理。

这样就解决了无效查询的问题。

但是这样的方案会带来什么问题呢？

扩容或者缩容时，会导致大量的数据迁移。最少也会影响 50% 的数据。

图 3 增加一台服务器

为了说明问题，加入一台服务器 3。服务器的数量 n 就从 3 变成了 4。还是查询用户号为 100 的用户信息时，100 mod 4 结果为 0。这时，请求就被 0 号服务器接收了。

• 当服务器数量为 3 时，用户号为 100 的请求会被 1 号服务器处理。
• 当服务器数量为 4 时，用户号为 100 的请求会被 0 号服务器处理。

所以，当服务器数量增加或者减少时，一定会涉及到大量数据迁移的问题。

对于上述哈希算法其优点是简单易用，大多数分库分表规则就采取的这种方式。一般是提前根据数据量，预先估算好分区数。

其缺点是由于扩容或收缩节点导致节点数量变化时，节点的映射关系需要重新计算，会导致数据进行迁移。所以扩容时通常采用翻倍扩容，避免数据映射全部被打乱，导致全量迁移的情况，这样只会发生 50% 的数据迁移。

三、一致性哈希算法

一致性 hash 算法由麻省理工学院的 Karger 及其合作者于 1997 年提出的，算法提出之初是用于大规模缓存系统的负载均衡。它的工作过程是这样的，首先根据 ip 或者其他的信息为缓存节点生成一个 hash，并将这个 hash 投射到 [0, 232 - 1] 的圆环上。当有查询或写入请求时，则为缓存项的 key 生成一个 hash 值。然后查找第一个大于或等于该 hash 值的缓存节点，并到这个节点中查询或写入缓存项。如果当前节点挂了，则在下一次查询或写入缓存时，为缓存项查找另一个大于其 hash 值的缓存节点即可。大致效果如下图所示，每个缓存节点在圆环上占据一个位置。如果缓存项的 key 的 hash 值小于缓存节点 hash 值，则到该缓存节点中存储或读取缓存项。比如下面绿色点对应的缓存项将会被存储到 cache-2 节点中。由于 cache-3 挂了，原本应该存到该节点中的缓存项最终会存储到 cache-4 节点中。

图 4 一致性哈希算法

在一致性哈希算法中，不管是增加节点，还是宕机节点，受影响的区间仅仅是增加或者宕机服务器在哈希环空间中，逆时针方向遇到的第一台服务器之间的区间，其它区间不会受到影响。

但是一致性哈希也是存在问题的：

图 5 数据倾斜

当节点很少的时候可能会出现这样的分布情况，A 服务会承担大部分请求。这种情况就叫做数据倾斜。

那如何解决数据倾斜的问题呢？

加入虚拟节点。

首先一个服务器根据需要可以有多个虚拟节点。假设一台服务器有 n 个虚拟节点。那么哈希计算时，可以使用IP+ 端口 + 编号的形式进行哈希值计算。其中的编号就是 0 到 n 的数字。由于 IP+ 端口是一样的，所以这 n 个节点都是指向的同一台机器。

图 6 引入虚拟节点

在没有加入虚拟节点之前，A 服务器承担了绝大多数的请求。但是假设每个服务器有一个虚拟节点（A-1，B-1，C-1），经过哈希计算后落在了如上图所示的位置。那么 A 服务器的承担的请求就在一定程度上（图中标注了五角星的部分）分摊给了 B-1、C-1 虚拟节点，实际上就是分摊给了 B、C 服务器。

一致性哈希算法中，加入虚拟节点，可以解决数据倾斜问题。

四、一致性哈希在 DUBBO 中的应用

图 7 Dubbo 中一致性哈希环

这里相同颜色的节点均属于同一个服务提供者，比如 Invoker1-1，Invoker1-2，……, Invoker1-160。这样做的目的是通过引入虚拟节点，让 Invoker 在圆环上分散开来，避免数据倾斜问题。所谓数据倾斜是指，由于节点不够分散，导致大量请求落到了同一个节点上，而其他节点只会接收到了少量请求的情况。比如：

图 8 数据倾斜问题

如上，由于 Invoker-1 和 Invoker-2 在圆环上分布不均，导致系统中 75% 的请求都会落到 Invoker-1 上，只有 25% 的请求会落到 Invoker-2 上。解决这个问题办法是引入虚拟节点，通过虚拟节点均衡各个节点的请求量。

到这里背景知识就普及完了，接下来开始分析源码。我们先从 ConsistentHashLoadBalance 的 doSelect 方法开始看起，如下：

public class ConsistentHashLoadBalance extends AbstractLoadBalance {


    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = 
        new ConcurrentHashMap<String, ConsistentHashSelector<?>>();


    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String methodName = RpcUtils.getMethodName(invocation);
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;


        // 获取 invokers 原始的 hashcode
        int identityHashCode = System.identityHashCode(invokers);
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        // 如果 invokers 是一个新的 List 对象，意味着服务提供者数量发生了变化，可能新增也可能减少了。
        // 此时 selector.identityHashCode != identityHashCode 条件成立
        if (selector == null || selector.identityHashCode != identityHashCode) {
            // 创建新的 ConsistentHashSelector
            selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }


        // 调用 ConsistentHashSelector 的 select 方法选择 Invoker
        return selector.select(invocation);
    }

    private static final class ConsistentHashSelector<T> {...}
}

如上，doSelect 方法主要做了一些前置工作，比如检测 invokers 列表是不是变动过，以及创建 ConsistentHashSelector。这些工作做完后，接下来开始调用 ConsistentHashSelector 的 select 方法执行负载均衡逻辑。在分析 select 方法之前，我们先来看一下一致性 hash 选择器 ConsistentHashSelector 的初始化过程，如下：

private static final class ConsistentHashSelector<T> {


    // 使用 TreeMap 存储 Invoker 虚拟节点
    private final TreeMap<Long, Invoker<T>> virtualInvokers;


    private final int replicaNumber;


    private final int identityHashCode;


    private final int[] argumentIndex;


    ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        // 获取虚拟节点数，默认为160
        this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
        // 获取参与 hash 计算的参数下标值，默认对第一个参数进行 hash 运算
        String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
        argumentIndex = new int[index.length];
        for (int i = 0; i < index.length; i++) {
            argumentIndex[i] = Integer.parseInt(index[i]);
        }
        for (Invoker<T> invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            for (int i = 0; i < replicaNumber / 4; i++) {
                // 对 address + i 进行 md5 运算，得到一个长度为16的字节数组
                byte[] digest = md5(address + i);
                // 对 digest 部分字节进行4次 hash 运算，得到四个不同的 long 型正整数
                for (int h = 0; h < 4; h++) {
                    // h = 0 时，取 digest 中下标为 0 ~ 3 的4个字节进行位运算
                    // h = 1 时，取 digest 中下标为 4 ~ 7 的4个字节进行位运算
                    // h = 2, h = 3 时过程同上
                    long m = hash(digest, h);
                    // 将 hash 到 invoker 的映射关系存储到 virtualInvokers 中，
                    // virtualInvokers 需要提供高效的查询操作，因此选用 TreeMap 作为存储结构
                    virtualInvokers.put(m, invoker);
                }
            }
        }
    }
}

ConsistentHashSelector 的构造方法执行了一系列的初始化逻辑，比如从配置中获取虚拟节点数以及参与 hash 计算的参数下标，默认情况下只使用第一个参数进行 hash。需要特别说明的是，ConsistentHashLoadBalance 的负载均衡逻辑只受参数值影响，具有相同参数值的请求将会被分配给同一个服务提供者。ConsistentHashLoadBalance 不 关系权重，因此使用时需要注意一下。

在获取虚拟节点数和参数下标配置后，接下来要做的事情是计算虚拟节点 hash 值，并将虚拟节点存储到 TreeMap 中。到此，ConsistentHashSelector 初始化工作就完成了。接下来，我们来看看 select 方法的逻辑。

public Invoker<T> select(Invocation invocation) {
    // 将参数转为 key
    String key = toKey(invocation.getArguments());
    // 对参数 key 进行 md5 运算
    byte[] digest = md5(key);
    // 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 方法，
    // 寻找合适的 Invoker
    return selectForKey(hash(digest, 0));
}


private Invoker<T> selectForKey(long hash) {
    // 到 TreeMap 中查找第一个节点值大于或等于当前 hash 的 Invoker
    Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
    // 如果 hash 大于 Invoker 在圆环上最大的位置，此时 entry = null，
    // 需要将 TreeMap 的头节点赋值给 entry
    if (entry == null) {
        entry = virtualInvokers.firstEntry();
    }


    // 返回 Invoker
    return entry.getValue();
}

如上，选择的过程相对比较简单了。首先是对参数进行 md5 以及 hash 运算，得到一个 hash 值。然后再拿这个值到 TreeMap 中查找目标 Invoker 即可。

到此关于 ConsistentHashLoadBalance 就分析完了。

在阅读 ConsistentHashLoadBalance 源码之前，建议读者先补充背景知识，不然看懂代码逻辑会有很大难度。

五、应用场景

• DNS 负载均衡最早的负载均衡技术是通过 DNS 来实现的，在 DNS 中为多个地址配置同一个名字，因而查询这个名字的客户机将得到其中一个地址，从而使得不同的客户访问不同的服务器，达到负载均衡的目的。DNS 负载均衡是一种简单而有效的方法，但是它不能区分服务器的差异，也不能反映服务器的当前运行状态。
• 代理服务器负载均衡使用代理服务器，可以将请求转发给内部的服务器，使用这种加速模式显然可以提升静态网页的访问速度。然而，也可以考虑这样一种技术，使用代理服务器将请求均匀转发给多台服务器，从而达到负载均衡的目的。
• 地址转换网关负载均衡支持负载均衡的地址转换网关，可以将一个外部 IP 地址映射为多个内部 IP 地址，对每次 TCP 连接请求动态使用其中一个内部地址，达到负载均衡的目的。
• 协议内部支持负载均衡除了这三种负载均衡方式之外，有的协议内部支持与负载均衡相关的功能，例如 HTTP 协议中的重定向能力等，HTTP 运行于 TCP 连接的最高层。
• NAT 负载均衡NAT（Network Address Translation 网络地址转换）简单地说就是将一个 IP 地址转换为另一个 IP 地址，一般用于未经注册的内部地址与合法的、已获注册的 Internet IP 地址间进行转换。适用于解决 Internet IP 地址紧张、不想让网络外部知道内部网络结构等的场合下。
• 反向代理负载均衡普通代理方式是代理内部网络用户访问 internet 上服务器的连接请求，客户端必须指定代理服务器，并将本来要直接发送到 internet 上服务器的连接请求发送给代理服务器处理。反向代理（Reverse Proxy）方式是指以代理服务器来接受 internet 上的连接请求，然后将请求转发给内部网络上的服务器，并将从服务器上得到的结果返回给 internet 上请求连接的客户端，此时代理服务器对外就表现为一个服务器。反向代理负载均衡技术是把将来自 internet 上的连接请求以反向代理的方式动态地转发给内部网络上的多台服务器进行处理，从而达到负载均衡的目的。
• 混合型负载均衡在有些大型网络，由于多个服务器群内硬件设备、各自的规模、提供的服务等的差异，可以考虑给每个服务器群采用最合适的负载均衡方式，然后又在这多个服务器群间再一次负载均衡或群集起来以一个整体向外界提供服务（即把这多个服务器群当做一个新的服务器群），从而达到最佳的性能。将这种方式称之为混合型负载均衡。此种方式有时也用于单台均衡设备的性能不能满足大量连接请求的情况下。

作者：京东物流 乔杰

来源：京东云开发者社区