Dubbo五种负载均衡

发表于 更新于 阅读次数：

最短响应时间策略：

  1. 遍历服务提供者，计算每个服务的预计等待时间：(成功总耗时/成功请求数) * 活跃数。
  2. 选择时间最短的服务，若多个则按权重选择，权重相同则随机。

加权轮询算法

Dubbo的加权轮询算法经历了三个主要阶段，其演进目标是在保证按权重分配请求的前提下，兼顾性能和请求分布的平滑性。

  1. Dubbo 2.6.4 版本及之前：存在严重性能问题的朴素实现。
  2. 第一次优化：修复了性能问题，时间复杂度降至O(1)，但请求分布不平滑。
  3. 最终方案（平滑加权轮询）：在保证O(1)时间复杂度的基础上，实现了平滑的请求分布，避免了某个节点短时间内压力激增。

该算法的灵感来源于Nginx的平滑加权轮询算法。其核心思想是，通过动态调整一个“当前权重”值，让请求能够更均匀地分散到各个节点上，而不是连续地分配给高权重节点。

对于每一次请求，选择过程如下：

  1. 遍历并更新：遍历所有Invoker，将每个Invoker的 <font style="color:rgb(0, 0, 0);">current</font>值加上其固定的 <font style="color:rgb(0, 0, 0);">weight</font>。
  2. 选择最大者：从步骤1更新后的 <font style="color:rgb(0, 0, 0);">current</font>值中，选出最大的一个。该值对应的Invoker即为本次选中的节点。
  3. 调整选中者权重：将选中节点的 <font style="color:rgb(0, 0, 0);">current</font>值减去总权重 <font style="color:rgb(0, 0, 0);">total</font>。
  4. 返回结果：返回选中的Invoker。

关键点：第3步“减去总权重”是保证算法能够循环往复、实现平滑的核心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 非完整代码，仅为说明算法逻辑
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    // 1. 获取第一个Invoker和它的固定权重
    Invoker<T> initInvoker = invokers.get(0);
    int weight = getWeight(initInvoker, invocation);

    // 2. 初始化所有Invoker的当前权重和总权重
    // `weightArray` 是一个数组，保存了每个Invoker的【固定权重】和【当前权重】
    // 这里是为了找到最大的固定权重和总权重
    int totalWeight = weight;
    int maxWeight = weight;
    for (int i = 1; i < length; i++) {
        weight = getWeight(invokers.get(i), invocation);
        maxWeight = Math.max(maxWeight, weight);
        totalWeight += weight;
    }

    // 3. 核心算法循环
    // 如果最大权重大于0，且所有Invoker的当前权重不全都相等，进入状态机逻辑
    if (maxWeight > 0 && !sameWeight) {
        // 状态机模式，循环直到选出一个Invoker
        for (int i = 0; i < length; i++) {
            // 当前索引的Invoker，将其【当前权重】增加【固定权重】
            int current = weightArray[i].current += weightArray[i].weight;
            // 如果当前值大于已知最大值，更新最大值和选中的Invoker
            if (current > maxCurrent) {
                maxCurrent = current;
                selectedInvoker = invokers.get(i);
            }
        }
        // 选中后，将【选中Invoker】的【当前权重】减去【总权重】
        // 这是实现平滑的关键步骤！
        weightArray[selectedIndex].current -= totalWeight;
        return selectedInvoker;
    }
    // 4. 如果所有权重相同，则退化为普通轮询
    return invokers.get(sequence++ % length);
}

Dubbo的加权轮询负载均衡算法通过三次演进，最终采用了平滑加权轮询算法。该算法通过引入动态的“当前权重”（<font style="color:rgb(0, 0, 0);">current</font>），并在每次选中后减去“总权重”（<font style="color:rgb(0, 0, 0);">total</font>），巧妙地实现了：

  1. 严格按权重分配：在多次请求后，各节点被选中的次数比严格等于其权重比。
  2. 请求分布平滑：高权重节点的请求被分散开，避免了瞬时压力过大。
  3. 高性能：时间复杂度为O(n)，其中n是服务节点数，通常很小，可视为常量级。

总结

  • 原理：
    • 最短响应时间策略：选择平均响应时间最短的服务，结合权重和活跃数计算预计等待时间。
    • 最小活跃数策略：选择活跃请求数最少的服务，需配合<font style="color:rgb(0, 0, 0);">ActiveLimitFilter</font>使用，否则退化为加权随机。
    • 一致性哈希策略：通过哈希环和虚拟节点分布请求，减少节点变动时的数据迁移。
    • 加权轮询策略：请求按权重比例轮流分配，平滑加权算法避免请求集中。
    • 加权随机策略：根据权重设置随机概率，权重越大的服务被选中的概率越高。
  • 作用：优化资源利用、提升响应速度、保证高可用性。
  • 应用场景：
    • 最短响应时间：适用于对延迟敏感的场景，如实时计算。
    • 最小活跃数：适合处理时间差异大的服务，如慢查询优化。
    • 一致性哈希：需要会话保持或顺序处理的场景，如缓存分片。
    • 加权轮询/随机：服务器性能不均时，按权重分配负载。