目錄應(yīng)用場(chǎng)景本文目標(biāo)算法詳解權(quán)重比例Java 實(shí)現(xiàn)參考應(yīng)用場(chǎng)景

客戶(hù)端負(fù)載均衡，例如 Nacos 提供的客戶(hù)端負(fù)載均衡就是使用了該算法游戲抽獎(jiǎng)（普通道具的權(quán)重很高，稀有道具的權(quán)重很低）

本文目標(biāo)

Java 實(shí)現(xiàn)權(quán)重隨機(jī)算法

算法詳解

比如我們現(xiàn)在有三臺(tái) Server，權(quán)重分別為1，3，2。現(xiàn)在想對(duì)三臺(tái) Server 做負(fù)載均衡

Server1 Server2 Server3 weight weight weight 1 3 2權(quán)重比例

我們算出每臺(tái) Server 的權(quán)重比例，權(quán)重比例 = 自己的權(quán)重 / 總權(quán)重

server1 server2 server3 weight weight weight 1 3 2 radio radio radio 1/6 3/6 2/6

根據(jù)權(quán)重比例計(jì)算覆蓋區(qū)域

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

根據(jù)權(quán)重負(fù)載均衡

如步驟2所示，每個(gè) server 都有自己的范圍，把每一個(gè)格子作為單位來(lái)看的話(huà)

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

使用隨機(jī)數(shù)函數(shù)，取 (0,6] 之間的隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)落在哪個(gè)范圍決定如何選擇。例如隨機(jī)數(shù)為 2，處于 (1,4] 范圍，那么就選擇 server2。

思路大概就是這樣，落實(shí)到代碼上，用一個(gè)數(shù)組 [0.16666667, 0.66666667, 1] 來(lái)表示這三個(gè) server 的覆蓋范圍，使用 ThreadLocalRandom 或者 Random 獲取 [0,1) 內(nèi)的隨機(jī)數(shù)。然后使用二分查找法快速定位隨機(jī)數(shù)處于哪個(gè)區(qū)間

Java 實(shí)現(xiàn)

代碼基本上與 com.alibaba.nacos.client.naming.utils.Chooser 一致，在可讀性方面做了下優(yōu)化。

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); } /** * 計(jì)算權(quán)重，初始化或者重新定義權(quán)重時(shí)使用 * */ public void calWeights(List<ItemWithWeight<T>> itemsWithWeight) {items.clear();// 計(jì)算權(quán)重總和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;}// 計(jì)算每個(gè)item的實(shí)際權(quán)重比例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;}// 計(jì)算每個(gè)item的權(quán)重范圍// 權(quán)重范圍起始位置weights = new double[items.size()];double weightRangeStartPos = 0;for (int i = 0; i < index; i++) { weights[i] = weightRangeStartPos + actualWeightRatios[i]; weightRangeStartPos += actualWeightRatios[i];} } /** * 基于權(quán)重隨機(jī)算法選擇 * */ 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);}// 通常不會(huì)走到這里，為了保證能得到正確的返回，這里隨便返回一個(gè)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 testint 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));// 統(tǒng)計(jì) (這里用 AtomicInteger 僅僅是因?yàn)閷?xiě)起來(lái)比較方便，這是一個(gè)單線(xiàn)程測(cè)試)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);}); }}

這里重點(diǎn)說(shuō)一下 Arrays.binarySearch(weights, random)，這個(gè) API 我之前沒(méi)有用過(guò)導(dǎo)致我在讀 Nacos 源碼時(shí)，對(duì)這塊的操作十分費(fèi)解

來(lái)看一下 java API 文檔對(duì)該方法返回值的解釋

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.

解釋下，首先該方法的作用是通過(guò)指定的 key 搜索數(shù)組。（前提條件是要保證數(shù)組的順序是從小到大排序過(guò)的）

如果數(shù)組中包含該 key，則返回對(duì)應(yīng)的索引 如果不包含該 key，則返回該 key 的 (-(insertion point)-1)

insertion point（插入點(diǎn)）：該 key 應(yīng)該在數(shù)組的哪個(gè)位置。舉個(gè)例子，數(shù)組 [1,3,5]，我的搜索 key 為 2，按照順序排的話(huà) 2 應(yīng)該在數(shù)組的 index = 1 的位置，所以此時(shí) insertion point = 1。

（這里 jdk 將能查到 key 和 查不到 key 兩種情況做了區(qū)分。為了將未找到的情況全部返回負(fù)數(shù)，所以做了 (-(insertion point)-1) 這樣的操作）

看到這，我們就懂了，insertion point 就是我們需要的，現(xiàn)在我們用小學(xué)數(shù)學(xué)來(lái)推導(dǎo)一下如何計(jì)算 insertion point

// 小學(xué)數(shù)學(xué)推導(dǎo)一下 insertion point 如何計(jì)算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

到此這篇關(guān)于Java實(shí)現(xiàn)權(quán)重隨機(jī)算法詳解的文章就介紹到這了,更多相關(guān)Java 權(quán)重隨機(jī)內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！