Java實現權重隨機算法詳解

Posted on by

應用場景

客戶端負載均衡，例如 Nacos 提供的客戶端負載均衡就是使用瞭該算法
遊戲抽獎（普通道具的權重很高，稀有道具的權重很低）

本文目標

Java 實現權重隨機算法

算法詳解

比如我們現在有三臺 Server，權重分別為1，3，2。現在想對三臺 Server 做負載均衡 

Server1     Server2     Server3

 weight      weight      weight
   1           3          2

權重比例

我們算出每臺 Server 的權重比例，權重比例 = 自己的權重 / 總權重

server1     server2     server3

 weight      weight      weight
   1           3          2

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

根據權重比例計算覆蓋區域

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

根據權重負載均衡

如步驟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 一致，在可讀性方面做瞭下優化。 

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 

// 小學數學推導一下 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

到此這篇關於Java實現權重隨機算法詳解的文章就介紹到這瞭,更多相關Java 權重隨機內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：