探索一致性哈希算法以及在 Dubbo 负载均衡中的应用

图解均衡算法：一致性哈希，并详细介绍 Dubbo 对一致性哈希算法的应用，简介清晰，易于理解

wzz2333

1011人浏览 · 2024-03-26 20:10:18

wzz2333 · 2024-03-26 20:10:18 发布

文章目录

负载均衡简介
基于哈希算法的负载均衡策略
一致性哈希在 Dubbo 中的应用
- ConsistentHashSelector 构造方法
- ConsistentHashSelector select方法

负载均衡简介

负载均衡（Load Balance，简称 LB）是一种技术，用于将请求按照某种策略分配给后端集群中的不同机器进行处理，缓解单点服务器的高负载，提升服务整体的吞吐量和可用性。

负载均衡的作用如下：

提高系统的可靠性和可用性：负载均衡可以防止任何单点故障影响整个系统，如果某个服务器失败，负载均衡器下线出现故障的机器，并将流量重定向到其他健康的服务器上。
优化资源的利用率：一个良好的负载均衡策略能充分利用集群中所有机器的资源，没有机器处于过载或空闲的状态。
提升吞吐量：负载均衡可以分散流量到最少负载的服务器或地理位置最近的服务器，减少用户请求的响应时间，提升服务整体的吞吐量。
提供横向扩展的能力：当集群不能支撑现有的业务流量时，可以通过增加更多服务器来扩展服务的处理能力，灵活应对不断变化的负载需求。

负载均衡的类型：

四层负载均衡(L4)：在网络传输层进行，主要根据 IP 地址和端口号来分发流量。比较著名的 L4 软件有：Linux Virtual Server(LVS)、HAProxy。
七层负载均衡(L7)：处理应用层数据，根据HTTP头部、URL、甚至请求的具体内容来进行智能路由和负载分配。比较著名的 L7 软件有：Nginx、HAProxy、Apache HTTP Server。

基于哈希算法的负载均衡策略

传统哈希算法

适用传统的哈希算法实现数据负载均衡的步骤如下：

添加、查询还是删除数据，都先将数据的 id（例如：Redis 的 key）通过哈希函数（如：CRC16）转换成一个哈希值 hash；
如果集群中有 N 台机器，计算 hash % N 的值，这个值就是数据所属的机器编号，该条数据的增删改查都是在这台机器上进行。

示意图如下：

这种负载策略算法的缺点：增加或删除机器（N 变化），会导致所有的数据不得不根据 id 重新计算一遍哈希值，并将哈希值对新的机器数进行取模运算，然后执行大规模数据迁徙。

假设增加一台 Redis 实例 server_2，键值对的分布需要重新计算哈希值，示意图如下：

一致性哈希算法

一致性哈希算法就是为了解决上述问题而产生的，假设数据的 id 通过哈希函数转换成的哈希值范围是 $2^{32}$ ，即 $0\sim2^{32}-1$ 的区间内。可以将这些数据头尾相连，形成一个闭环，如下图所示：

数据 id 计算出哈希值后，对应到环上的一个位置。

假设集群中存在三台机器，根据机器 id 计算出的哈希值得到机器在环上的位置。

数据如何确定属于哪台机器？

根据数据 id 用哈希函数计算出哈希值，映射到环中相应的位置；
从数据映射的位置开始，顺时针找寻最近的机器，那台机器负责该数据的增删改查。

以上图为例，离 key1 顺时针最近的是机器 ③、key4 属于机器 ① 管理、key2 和 key3 属于机器 ② 管理。

如何增加节点？

如果新加入机器 4（如下图所示），由机器 ① 到机器 ④ 掌管的数据先前由机器 ② 负责管理，现在需要将这部分数据迁徙到机器 ④。即 key2 所代表的数据需要从机器 ② 迁移至机器 ④。

虚拟一致性哈希算法

如果机器数量较少，很有可能机器在整个环上的分布不均匀，从而导致机器之间的负载不均衡。如下图，机器 ① 到机器 ② 的距离远远大于机器 ② 到机器 ①，这导致大多数数据将分配至机器 ②，引起机器负载不均：

为了解决这种数据倾斜问题，一致性哈希算法引入了 虚拟节点机制，对每一台机器 通过不同的哈希函数计算出多个哈希值，对多个位置都放置一个服务节点，称为虚拟节点。

具体的做法可以在 机器 IP 地址或主机名的后面增加编号 来实现。例如存在两台机器 m1、m2，每台机器有两个虚拟节点，分别计算 m1-1、m1-2、m2-1、m2-2 的哈希值，形成四个虚拟节点，节点数变多后哈希函数的散列效果更好，集群负载的平衡性也就更好。

当某一条数据计算出哈希值并找到最近的一个虚拟节点时，根据虚拟节点到实际机器的映射关系找到实际机器，数据将最终归属于实际的机器。同理，虚拟节点间的数据迁移、更新删除等操作，也都是根据虚拟节点到实际机器的映射，找到实际机器完成相应操作。

让每台机器分配数量较多的虚拟节点抢占哈希环，数量多起来后哈希函数的离散型可以得到很好的体现，每台机器就可以按照所占虚拟节点的比例来分配负载。

一致性哈希在 Dubbo 中的应用

Dubbo 中的负载均衡：服务消费者 Consumer 会从所有服务提供者 Provider 中选出一个实例进行远程过程调用（RPC），在代码中 Provider 封装为 Invoker 实例。通俗的讲，负载均衡策略就是从 Invoker 列表中选出一个 Invoker，供 Consumer 完成调用。

Dubbo 的一致性哈希算法分为两步：

映射 Provider(实际为 Invoker) 至 Hash 值区间中；
映射请求，然后找到大于请求Hash值的第一个Invoker；

Dubbo 中所有负载均衡实现类继承自抽象类 AbstractLoadBalance，调用 LoadBalance#select 方法时，实际调用的是 AbstractLoadBalance#select：

@Override
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    if (CollectionUtils.isEmpty(invokers)) {
        return null;
    }
    if (invokers.size() == 1) {
        return invokers.get(0);
    }
    // 执行负载均衡实现类的doSelect方法
    return doSelect(invokers, url, invocation);
}

Dubbo 一致性哈希的具体实现类为 ConsistentHashLoadBalance：

@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; // 服务名称
    int identityHashCode = System.identityHashCode(invokers); // Invoker列表的哈希值
    ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key); // 获取指定服务的选择器
    // 选择器没有初始化 或 invoker列表发生了变更, 初始化一个ConsistentHashSelector实例
    if (selector == null || selector.identityHashCode != identityHashCode) {
        selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
        selector = (ConsistentHashSelector<T>) selectors.get(key);
    }
    return selector.select(invocation);
}

方法步骤说明：

通过入参 invocation 获取方法调用信息，包括：方法名 methodName、服务唯一标识 key、服务提供者列表 invokes 的哈希码 identityHashCode；
从 ConcurrentHashMap 中获取特定服务的选择器；
当出现如下情况时，则初始化一个选择器：
- 不存在服务选择器(select == null)；
- 服务提供者集群发生了变更 (selector.identityHashCode != identityHashCode)，例如实例增加、删除、ip 地址更改等。
执行选择器的 select 方法，获取一个 Invoker 实例用于远程调用。

ConsistentHashSelector 构造方法

一致性哈希策略的选择器实现类为 ConsistentHashSelector，它包含如下属性：

private static final class ConsistentHashSelector<T> {
	// 虚拟节点哈希值到 Invoker 实例的映射
    private final TreeMap<Long, Invoker<T>> virtualInvokers;
	// 
    private final int replicaNumber;
	// 识别 Invoker 列表是否发生变化的哈希码
    private final int identityHashCode;
	// 请求中用来做哈希映射的参数索引
    private final int[] argumentIndex;
    // ...
}

在新建 ConsistentHashSelector 时，会遍历所有 Invoker 对象，计算出

ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
	// 使用红黑树存储 Invoker 实例, 查询、插入、删除性能比较平衡
    this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
    this.identityHashCode = identityHashCode;
    URL url = invokers.get(0).getUrl();
    // 获取每个 Invoker 实例的虚拟节点数目, 默认为160个, 可以通过hash.nodes属性配置
    this.replicaNumber = url.getMethodParameter(methodName, HASH_NODES, 160);
    // 解析方法中哪些参数用于计算哈希值(通过URL对象中的方法参数得到)
    String[] index = 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) {
    	// 遍历所有 Invoker
        String address = invoker.getUrl().getAddress(); // Invoker实例地址
        for (int i = 0; i < replicaNumber / 4; i++) {
        	// url后拼接序号i后执行md5运算, 得到16字节的摘要
            byte[] digest = md5(address + i);
            // 16字节的摘要, 可以得到四个 32位哈希值
            for (int h = 0; h < 4; h++) {
                long m = hash(digest, h);
                // 每个哈希值相当于一个虚拟节点, virtualInvokers维护虚拟节点到Invoker实例的映射
                virtualInvokers.put(m, invoker);
            }
        }
    }
}

上述代码生成虚拟节点哈希值的过程（以 replicaNumber 取默认值 160 为例）：

假设当前遍历到的 Invoker 地址为 192.168.0.1:20880。该方法会依次计算 192.168.0.1:208800、192.168.0.1:208801、… 、192.168.0.1:2088039 的 md5 摘要。
利用 md5 生成的 16 字节摘要，生成四个 32 位哈希值，每个哈希值相当于一个虚拟节点，virtualInvokers 维护虚拟节点到 Invoker 实例的映射。

hash 方法将 digest 字节数组划分为 4 个部分，每个部分 4字节。每次调用返回 number 指定部分的 32 位整数作为哈希值。

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;
}

以图中所示的摘要数组为例，图中代码将根据 number 返回四个不同的哈希值：

注：Dubbo 使用 URL 传递方法级别参数，例如

dubbo://192.168.0.1:20880/cn.wzz.demo?serialization=fastjson& 
method.selectUsers.timeout=5000&
method.selectUsers.retries=2

URL 的参数中，名称包含 method 前缀的为方法参数，method.selectUsers 表示方法名为 selectUsers 的方法参数。

总结：一致性哈希选择器的构造方法会 为特定服务的每个 Invoker 实例创建 replicaNumber 个虚拟节点，不同的 hash 值标识虚拟节点，通过 virtualInvokers 维护虚拟节点到 Invoker 实例的映射关系。

ConsistentHashSelector select方法

介绍完选择器的构造方法后，我们来看选择器的 select 方法如何挑选出处理请求的 Invoker 实例。

public Invoker<T> select(Invocation invocation) {
	// 根据远程调用的参数值确定key, 默认使用第一个参数计算
    String key = toKey(invocation.getArguments());
    // md5 哈希算法计算key的摘要
    byte[] digest = md5(key);
    return selectForKey(hash(digest, 0));
}

// 将参数列表args中, 由argumentIndex指定下标的参数值拼接成字符串
private String toKey(Object[] args) {
    StringBuilder buf = new StringBuilder();
    for (int i : argumentIndex) {
        if (i >= 0 && i < args.length) {
            buf.append(args[i]);
        }
    }
    return buf.toString();
}

// 从红黑树virtualInvokers 中查找哈希值大于等于hash的第一个 Invoker 实例
private Invoker<T> selectForKey(long hash) {
    Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
    if (entry == null) {
    	// 找不到大于等于 hash 的虚拟节点, 回到哈希环起始位置, 找出哈希值最小的节点
        entry = virtualInvokers.firstEntry();
    }
    return entry.getValue();
}

select 方法的步骤如下：

从 Invocation 对象中获取远程调用的参数列表，利用 toKey 方法获取参数值拼接而成的字符串 key。
使用 md5 哈希算法计算 key 的摘要 digest；
取 digest 的低位 4 字节作为哈希值，使用 selectForKey 方法从红黑树中找到 大于等于 hash 的首个 Invoker 对象。如果找不到(entry == null)，此时应该 跳转到哈希环的起始位置，即找到哈希值最小的 Invoker 对象。

从 selectForKey 中获取到 Invoker 对象后，负载均衡策略执行完毕，后序获取远程调用客户端，执行调用流程。