Dubbo负载均衡策略之 一致性哈希

本文主要讲解了一致性哈希算法的原理以及其存在的数据倾斜的问题，然后引出解决数据倾斜问题的方法，最后分析一致性哈希算法在 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除以4的余数为0。这时，请求就被 0 号服务器接收了。

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

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

这种哈希算法的优点在于其简单易用性，因此大多数分库分表规则都采用了它。一般是提前根据数据量，预先估算好分区数。

该技术的不足在于，一旦网络中节点数量发生扩增或收缩，就需要重新计算节点的映射关系，导致数据需要被迁移。所以扩容时通常采用翻倍扩容，避免数据映射全部被打乱，导致全量迁移的情况，这样只会发生 50% 的数据迁移。

三、一致性哈希算法

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

图 4 一致性哈希算法

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

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

图 5 数据倾斜

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

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

加入虚拟节点。

首先一个服务器根据需要可以有多个虚拟节点。假设一台服务器有 n 个虚拟节点。在哈希计算中，可以采用 IP 地址、端口号和编号的组合来计算哈希值。其中的编号就是 0 到 n 的数字。这 n 个节点都指向同一台机器，因为它们共享相同的 IP 地址和端口号。

图 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<?>>();@Overrideprotected <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 原始的 hashcodeint identityHashCode = System.identityHashCode(invokers);ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);// 如果 invokers 是一个新的 List 对象，意味着服务提供者数量发生了变化，可能新增也可能减少了。// 此时 selector.identityHashCode != identityHashCode 条件成立if (selector == null || selector.identityHashCode != identityHashCode) {// 创建新的 ConsistentHashSelectorselectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));selector = (ConsistentHashSelector<T>) selectors.get(key);}// 调用 ConsistentHashSelector 的 select 方法选择 Invokerreturn 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();// 获取虚拟节点数，默认为160this.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) {// 将参数转为 keyString key = toKey(invocation.getArguments());// 对参数 key 进行 md5 运算byte[] digest = md5(key);// 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 方法，// 寻找合适的 Invokerreturn selectForKey(hash(digest, 0));}private Invoker<T> selectForKey(long hash) {// 到 TreeMap 中查找第一个节点值大于或等于当前 hash 的 InvokerMap.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();// 如果 hash 大于 Invoker 在圆环上最大的位置，此时 entry = null，// 需要将 TreeMap 的头节点赋值给 entryif (entry == null) {entry = virtualInvokers.firstEntry();}// 返回 Invokerreturn entry.getValue();}

如上，选择的过程相对比较简单了。首先，需要对参数进行 md5 和 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 上的连接请求以反向代理的方式动态地转发给内部网络上的多台服务器进行处理，从而达到负载均衡的目的。
• 混合型负载均衡在有些大型网络，由于多个服务器群内硬件设备、各自的规模、提供的服务等的差异，可以考虑给每个服务器群采用最合适的负载均衡方式，然后又在这多个服务器群间再一次负载均衡或群集起来以一个整体向外界提供服务（即把这多个服务器群当做一个新的服务器群），从而达到最佳的性能。将这种方式称之为混合型负载均衡。此种方式有时也用于单台均衡设备的性能不能满足大量连接请求的情况下。

作者：京东物流 乔杰

来源：京东云开发者社区

以上是Dubbo负载均衡策略之 一致性哈希的详细内容。更多信息请关注PHP中文网其他相关文章！