权重随机（Weight random）算法详解

发表于 | 分类于

应用场景

  • 客户端负载均衡，例如 Nacos 提供的客户端负载均衡就是使用了该算法
  • 游戏抽奖（普通道具的权重很高，稀有道具的权重很低）

本文目标

Java 实现权重随机算法

算法详解

比如我们现在有三台 Server，权重分别为1，3，2。现在想对三台 Server 做负载均衡

1
2
3
4
Server1     Server2     Server3

 weight      weight      weight
   1           3          2

权重比例

  1. 我们算出每台 Server 的权重比例，权重比例 = 自己的权重 / 总权重

    1
    2
    3
    4
    5
    6
    7
    server1     server2     server3

     weight      weight      weight
       1           3          2

     radio       radio       radio
      1/6         3/6         2/6

  2. 根据权重比例计算覆盖区域

    1
    2
    3
    4
    5
    6
      server1               server2                  server3
         ^                     ^                        ^
    |---------||---------|---------|---------||---------|---------||
    0         1/6                            4/6                  6/6
               ^                              ^                    ^
          0.16666667                      0.66666667              1.0

  3. 根据权重负载均衡

    如步骤2所示，每个 server 都有自己的范围，把每一个格子作为单位来看的话

    • server1 (0,1]
    • server2 (1,4]
    • server3 (4,6]

    使用随机数函数，取 (0,6] 之间的随机数，根据随机数落在哪个范围决定如何选择。例如随机数为 2，处于 (1,4] 范围，那么就选择 server2。

    思路大概就是这样，落实到代码上，用一个数组 [0.16666667, 0.66666667, 1] 来表示这三个 server 的覆盖范围，使用 ThreadLocalRandom 或者 Random 获取 [0,1) 内的随机数。然后使用二分查找法快速定位随机数处于哪个区间

Java 实现

代码基本上与 com.alibaba.nacos.client.naming.utils.Chooser 一致，在可读性方面做了下优化。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;

public class WeightRandom<T> {

    private final List<T> items = new ArrayList<>();
    private double[] weights;

    public WeightRandom(List<ItemWithWeight<T>> itemsWithWeight) {
        this.calWeights(itemsWithWeight);
    }

    /**
     * 计算权重，初始化或者重新定义权重时使用
     * 
     */
    public void calWeights(List<ItemWithWeight<T>> itemsWithWeight) {
        items.clear();

        // 计算权重总和
        double originWeightSum = 0;
        for (ItemWithWeight<T> itemWithWeight : itemsWithWeight) {
            double weight = itemWithWeight.getWeight();
            if (weight <= 0) {
                continue;
            }

            items.add(itemWithWeight.getItem());
            if (Double.isInfinite(weight)) {
                weight = 10000.0D;
            }
            if (Double.isNaN(weight)) {
                weight = 1.0D;
            }
            originWeightSum += weight;
        }

        // 计算每个item的实际权重比例
        double[] actualWeightRatios = new double[items.size()];
        int index = 0;
        for (ItemWithWeight<T> itemWithWeight : itemsWithWeight) {
            double weight = itemWithWeight.getWeight();
            if (weight <= 0) {
                continue;
            }
            actualWeightRatios[index++] = weight / originWeightSum;
        }

        // 计算每个item的权重范围
        // 权重范围起始位置
        weights = new double[items.size()];
        double weightRangeStartPos = 0;
        for (int i = 0; i < index; i++) {
            weights[i] = weightRangeStartPos + actualWeightRatios[i];
            weightRangeStartPos += actualWeightRatios[i];
        }
    }

    /**
     * 基于权重随机算法选择
     * 
     */
    public T choose() {
        double random = ThreadLocalRandom.current().nextDouble();
        int index = Arrays.binarySearch(weights, random);
        if (index < 0) {
            index = -index - 1;
        } else {
            return items.get(index);
        }

        if (index < weights.length && random < weights[index]) {
            return items.get(index);
        }

        // 通常不会走到这里，为了保证能得到正确的返回，这里随便返回一个
        return items.get(0);
    }

    public static class ItemWithWeight<T> {
        T item;
        double weight;

        public ItemWithWeight() {
        }

        public ItemWithWeight(T item, double weight) {
            this.item = item;
            this.weight = weight;
        }

        public T getItem() {
            return item;
        }

        public void setItem(T item) {
            this.item = item;
        }

        public double getWeight() {
            return weight;
        }

        public void setWeight(double weight) {
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        // for test
        int sampleCount = 1_000_000;

        ItemWithWeight<String> server1 = new ItemWithWeight<>("server1", 1.0);
        ItemWithWeight<String> server2 = new ItemWithWeight<>("server2", 3.0);
        ItemWithWeight<String> server3 = new ItemWithWeight<>("server3", 2.0);

        WeightRandom<String> weightRandom = new WeightRandom<>(Arrays.asList(server1, server2, server3));

        // 统计 (这里用 AtomicInteger 仅仅是因为写起来比较方便，这是一个单线程测试)
        Map<String, AtomicInteger> statistics = new HashMap<>();

        for (int i = 0; i < sampleCount; i++) {
            statistics
                    .computeIfAbsent(weightRandom.choose(), (k) -> new AtomicInteger())
                    .incrementAndGet();
        }

        statistics.forEach((k, v) -> {
            double hit = (double) v.get() / sampleCount;
            System.out.println(k + ", hit:" + hit);
        });
    }
}

这里重点说一下 Arrays.binarySearch(weights, random)，这个 API 我之前没有用过导致我在读 Nacos 源码时，对这块的操作十分费解

来看一下 java API 文档对该方法返回值的解释

Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

解释下，首先该方法的作用是通过指定的 key 搜索数组。（前提条件是要保证数组的顺序是从小到大排序过的）

  • 如果数组中包含该 key，则返回对应的索引
  • 如果不包含该 key，则返回该 key 的 (-(insertion point)-1)

insertion point（插入点）：该 key 应该在数组的哪个位置。举个例子，数组 [1,3,5]，我的搜索 key 为 2，按照顺序排的话 2 应该在数组的 index = 1 的位置，所以此时 insertion point = 1。

（这里 jdk 将能查到 key 和 查不到 key 两种情况做了区分。为了将未找到的情况全部返回负数，所以做了 (-(insertion point)-1) 这样的操作）

看到这，我们就懂了，insertion point 就是我们需要的，现在我们用小学数学来推导一下如何计算 insertion point

1
2
3
4
5
6
7
8
// 小学数学推导一下 insertion point 如何计算
returnValue = (- (insertionPoint) - 1)
insertionPoint = (- (returnValue + 1) )

// 所以就有了上边代码中的
if (index < 0) {
	index = -index - 1;
}

参考

https://github.com/alibaba/nacos/blob/develop/client/src/main/java/com/alibaba/nacos/client/naming/utils/Chooser.java