Jiaming Zhang's Blog
0%

dubbo 负载均衡策略

发表于 更新于 分类于

本文简述 Dubbo 的负载均衡的几种策略

Dubbo 负载均衡的原理

从注册中心（如 zookeeper）拉取 provider 信息，保存在客户端，封装成 invoker 对象，再使用某种负载均衡策略选择一个 invoker 提供服务

org.apache.dubbo.rpc.protocol.AbstractInvoker

1
2
3
4
5
6
public abstract class AbstractInvoker<T> implements Invoker<T> {
		private final URL url;	// 路径
  	private volatile boolean available = true;	// 可用性
    private final String version;	// 版本号
  	// ...
}

Dubbo 提供的负载均衡策略

  • Random：随机
  • RoundRobin：轮询
  • LeastActive：最少活跃调用数
  • ShortestResponse：最短响应时间
  • ConsistentHash：一致性哈希
  • P2C：Power of Two Choice
  • Adaptive：自适应

Random

org.apache.dubbo.rpc.cluster.loadbalance.RandomLoadBalance#doSelect

从 invoker 列表中随机选择一个，或者加权随机

1
2
3
4
// Number of invokers
int length = invokers.size();
// 随机选择一个 invoker
invokers.get(ThreadLocalRandom.current().nextInt(length));

随机选择在短时间内不同 invoker 之间存在一定差异，长期累计会比较均匀

RoundRobin

org.apache.dubbo.rpc.cluster.loadbalance.RoundRobinLoadBalance#doSelect

轮训法（RR）从 invoker 列表中按顺序选择一个

1
2
3
4
5
6
7
private static final AtomicInteger atomicInteger = new AtomicInteger(0);

@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    int currentInvokerIndex = atomicInteger.incrementAndGet() % invokers.size();
    return invokers.get(currentInvokerIndex);
}

加权轮询（Weighted Round Robin，WRR）

在 RR 基础上考虑 invoker 性能，下面有两种实现思路：

思路一：将 invokers 按权重数生成一个集合，按 RR 的方式按顺序选择

这种方式流量短时间聚集在一个服务上，过了这段时间要等到下一轮才被分配，导致每个服务的流量不平稳（波动起伏），比如权重为 10:3:3 的分配结果为：[0-9, 10-12, 13-15]，这样带来的问题是，流量可能有尖刺，对保障的要求提高

思路二：平滑加权轮询，操作步骤如下：

  1. 为每个 invoker 设置两个权重，weight 和 currentWeight，weight 为用户配置的权重（固定），currentWeight 是当前权重（动态变化），初始值为 0
  2. 第一次轮询，currentWeight = weight
  3. 后面的轮询，被选中的 invoker 的 currentWeight = currentWeight - 权重之和
  4. 所有 invoker 的 currentWeight = currentWeight + weight

举个例子描述下这个过程：

我们有三个 invoker a, b, c，权重比为 5: 2: 1，a b c 的 currentWeight 变化如下

  1. Step0：a b c = 0 0 0（初始化）
  2. Step1：a b c = 5 2 1（加 weight，a 的 currentWeight 最大，选择 a）
  3. a b c = -3 2 1（a 减总权重 8）
  4. a b c = 2 4 2（加 weight，b 的 currentWeight 最大，选择 b）
  5. a b c = 2 -4 2（b 减总权重 8）
  6. a b c = 7 -2 3（加 weight，a 的 currentWeight 最大，选择 a）
  7. a b c = -1 -2 3（a 减总权重 8）
  8. a b c = 4 0 4（加 weight，a、c 的 currentWeight 相等，选择 weight 大的，选择 a）
  9. a b c = -4 0 4（a 减总权重 8）
  10. a b c = 1 2 5（加 weight，c 的 currentWeight 最大，选择 c）
  11. a b c = 1 2 -3（c 减总权重 8）
  12. a b c = 6 4 -2（选 a）
  13. a b c = -2 4 -2（a - 8）
  14. a b c = 3 6 -1（选 b）
  15. a b c = 3 -2 -1（b - 8）
  16. a b c = 8 0 0（选 a）
  17. a b c = 0 0 0（a - 8）

最终一轮的分配情况为：a, b, a, a, c, a, b, a

对比普通加权轮询的分配情况：a, a, a, a, a, b, b, c，平滑加权轮询保证权重分配不变，且分配更平滑

一般的生产环境都是通过 k8s 编排出相同配置的服务容器，感觉不太常用WRR，不过这种思想还挺有意思的，即：有权重要选择一个最大值时，可以通过加weight减totalWeight的方式，达到平滑的效果

leastActive

org.apache.dubbo.rpc.cluster.loadbalance.LeastActiveLoadBalance#doSelect

统计每个 invoker 的活跃调用数，选择活跃调用数最小的 invoker

ShortestResponse

统计每个 invoker 在过去一段时间内的平均响应时间，选择平均响应时间最小的 invoker

ConsitentHash

将请求参数或标识进行哈希计算，选择哈希值最接近的 invoker

由客户端请求决定分配情况，适用于用户和服务节点反复通讯的场景

P2C

Power of Two Choice 算法简单但是经典，主要思路如下：

  1. 对于每次调用，从可用的 invoker 列表中做两次随机选择，选出两个节点 invokerA 和 invokerB
  2. 比较 invokerA 和 invokerB 两个节点，选择当前正在处理的连接数较小的那个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private <T> Invoker<T> selectByP2C(List<Invoker<T>> invokers, Invocation invocation){
    int length = invokers.size();
    if(length == 1) {
        return invokers.get(0);
    }

    if(length == 2) {
        return chooseLowLoadInvoker(invokers.get(0),invokers.get(1),invocation);
    }

    int pos1 = ThreadLocalRandom.current().nextInt(length);
    int pos2 = ThreadLocalRandom.current().nextInt(length - 1);
    if (pos2 >= pos1) {
        pos2 = pos2 + 1;
    }

    return chooseLowLoadInvoker(invokers.get(pos1),invokers.get(pos2),invocation);
}

Q：为什么 pos2 要从 [0, len - 1] 取随机数呢？

A：避免 pos1 和 pos2 相等时判断边界

Q：pos2 的取法，不会让最后一个 invoker 被选择的概率小于其他 invoker 吗？

A：通过实验验证不会小于其他 invoker

Adaptive

基于 P2C 思想实现的负载均衡策略

  1. 从备选列表中做两次随机选择，得到 invokerA 和 invokerB
  2. 比较 invokerA 和 invokerB 的负载值，选择较小的那个

自定义策略

继承 AbstractLoadBalance，实现 doSelect 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MyLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "my_random";

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        for (int i = 0; i < invokers.size(); i++) {
            System.out.println("MyLoadBalance invoker: " + invokers.get(i));
            System.out.println("MyLoadBalance invoker ip: " + invokers.get(i).getUrl().getIp());
            String index = url.getParameter("index");
            if (Strings.isNotBlank(index)) {
                if (Integer.valueOf(i).equals(Integer.valueOf(index))) {
                    return invokers.get(i);
                }
            }
        }
        return invokers.get(0);
    }

}

不同策略的比较

策略 特点 缺点 适用场景
Random 随机 静态、公平、稳定 短时间内不同服务间存在一定差异 服务端处理能力相同、稳定性高
weighted Random 加权随机 静态、公平、稳定 需要维护机器性能的权重比例 服务端处理能力不同、稳定性高
roundRobin 轮询 静态、公平、稳定 服务端处理能力相同、稳定性高
weighted roundRobin 加权轮询 静态、公平、稳定 需要维护机器性能的权重比例 服务端处理能力不同、稳定性高
leastActive 最少链接数 动态 最小链接的服务不一定可以代表服务的吞吐能力 服务端处理能力有波动
最快响应 动态，更加关注响应速度 大多数情况下，不同 provider 的响应时间没有明显区别，导致退化为随机选择 服务端处理能力有波动
固定哈希 稳定 由客户端决定分布，可能分布不均 确定的入参，确定的提供者，适用于有状态请求
P2C 随机选择两个节点后，继续选择"连接数"较小的那个节点
自适应 随机选择两个节点后，继续选择"负载"较小的那个节点

Reference

一种自适应的负载均衡

常用负载均衡及策略图解

NGINX: 轮询调度、加权轮询调度、平滑加权轮询调度

dubbo负载均衡之随机负载均衡