負載均衡算法中的加權隨機算法

import org.apache.commons.lang3.tuple.Pair;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;

/**
* 加權隨機,nacos
*/
public class RouterWeightRandom {
/**
*
* @param list [{"a":1,"b":3,"c":6}]
*/
public String route(List<Pair<String,Double>> list) {
List<String> addresses = convert2Addresses(list);
// [0.1,0.4,1]
double[] cumulativeWeights = calcCumulativeWeight(list);
// 0.4/0.3/0.99999
double random = ThreadLocalRandom.current().nextDouble(0, 1);
// 下標(0.4時)或 -(插入點:第一個大于num的元素所在下標[0.3時返回1]/若都
// 小于num,則為arr.length[0.99999時返回3])-1
int index = Arrays.binarySearch(cumulativeWeights, random);
if (index < 0) {
// -2 -4
index = -index - 1;
} else {
// b
return addresses.get(index);
}
// 增強校驗
if (index < cumulativeWeights.length && random < cumulativeWeights[index]) {
return addresses.get(index);
}
return null;
}

? ? /**
* 計算累計權重比例
* @param list [{"a":1,"b":3,"c":6}]
* @return index處元素的值= <=index所有元素的比例之和,如 [0.1,0.4,1]
*/
private double[] calcCumulativeWeight(List<Pair<String, Double>> list) {
// 所有權重值累加 10
double originWeightSum = ?0D;
for (Pair<String,Double> item : list) {
double weight = item.getRight();
originWeightSum += weight;
}
// 每一項權重所占比例 [0.1,0.3,0.6]
double[] weightRatios = new double[list.size()];
int index = 0;
for (Pair<String,Double> item : list) {
double singleWeight = item.getRight();
weightRatios[index++] = singleWeight / originWeightSum;
}
// index處元素的值= <=index所有元素的比例之和 [0.1,0.4,1]
double[] cumulativeWeights = new double[list.size()];
double randomRange = 0D;
for (int i = 0; i < index; i++) {
cumulativeWeights[i] = randomRange + weightRatios[i];
randomRange += weightRatios[i];
}
// 允許的誤差
double doublePrecisionDelta = 0.0001;
if (index == 0 || (Math.abs(cumulativeWeights[index - 1] - 1) < doublePrecisionDelta)) {
return cumulativeWeights;
}
throw new RuntimeException("累加權重計算出錯,因為幾率和不等于1");
}

? ? /**
* 獲取地址列表
*/
private List<String> convert2Addresses(List<Pair<String, Double>> list) {
return list.stream().map(Pair::getLeft).collect(Collectors.toList());
}
}

好的，下面我將逐行詳細解釋你提供的 Java 代碼，包括 RouterWeightRandom 類和 testRouterWeightRandom 測試方法的每一行邏輯、作用、運行效果，幫助你徹底理解加權隨機（Weighted Random）負載均衡算法的實現原理。

🌟 一、整體說明
這段代碼實現的是加權隨機負載均衡算法（Weighted Random Load Balancing），它根據每個服務器地址的“權重”來決定其被選中的概率。權重越高，被選中的概率越大。
? RouterWeightRandom：核心算法類，實現加權隨機選擇。
? RouterTest.testRouterWeightRandom()：測試類，模擬地址列表并運行算法。

? 二、測試類 RouterTest 解析
Java
深色版本

public class RouterTest {
定義一個測試類，用于測試 RouterWeightRandom。

Java
深色版本

? ?
/**
* 加權隨機
*/
@Test
public void testRouterWeightRandom() {
使用 JUnit 的 @Test 注解標記這是一個測試方法，用于驗證加權隨機算法是否工作正常。

Java
深色版本

RouterWeightRandom router = new RouterWeightRandom();
創建一個 RouterWeightRandom 實例，用于調用其 route() 方法進行路由選擇。

Java
深色版本

List<String> list = mockAddressList();
調用 mockAddressList() 方法，獲取一個模擬的服務器地址列表，內容如下：
深色版本

["http://1.1.1.1", "http://1.1.1.2", "http://1.1.1.3", "http://1.1.1.4", "http://1.1.1.5"]

Java
深色版本

List<Pair<String,Double>> finalList = new ArrayList<>();
創建一個 List<Pair<String, Double>> 類型的列表，用于存儲每個地址及其對應的權重值。
? Pair 來自 Apache Commons Lang3，表示一個鍵值對：address 和 weight。

Java
深色版本

? ? ? ?
for
(String address : list) {
double weight = ThreadLocalRandom.current().nextDouble(1000
);
finalList.add(Pair.of(address, weight));
System.out.println("address:" + address +",權重:"
+ weight);
}
遍歷每個地址，為每個地址分配一個 0 到 1000 之間的隨機權重，并打印出來。
運行效果示例輸出：
深色版本

address:http://1.1.1.1,權重:345.67
address:http://1.1.1.2,權重:892.34
...
? 這里權重是隨機生成的，實際項目中權重可能來自配置中心（如 Nacos）或健康檢查結果。

Java
深色版本

? ? ? ?
for (int i = 0; i < 10
; i++) {
String route = router.route(finalList);
System.out.println((i + 1) + ".route = "
+ route);
}
循環 10 次，每次調用 router.route(finalList) 執行一次加權隨機選擇，并打印選中的地址。
運行效果示例輸出：
深色版本

1.route = http://1.1.1.2
2.route = http://1.1.1.5
...
? 權重高的地址被選中的概率更高。

Java
深色版本

? ?
private List<String> mockAddressList()?
{
List<String> list = new
ArrayList<>();
list.add("http://1.1.1.1"
);
list.add("http://1.1.1.2"
);
list.add("http://1.1.1.3"
);
list.add("http://1.1.1.4"
);
list.add("http://1.1.1.5"
);
return
list;
}
模擬生成 5 個服務器地址，用于測試。

? 三、核心類 RouterWeightRandom 詳細解析
Java
深色版本

import
org.apache.commons.lang3.tuple.Pair;
import
java.util.Arrays;
import
java.util.List;
import
java.util.concurrent.ThreadLocalRandom;
import
java.util.stream.Collectors;

/**
* 加權隨機,nacos
*/
public class RouterWeightRandom {
導入所需類，定義主類 RouterWeightRandom，用于實現加權隨機算法。

🔹 方法一：route() —— 主路由方法
Java
深色版本

? ?
public String route(List<Pair<String,Double>> list) {
入口方法，輸入是一個地址與權重的配對列表，返回選中的地址。

Java
深色版本

List<String> addresses = convert2Addresses(list);
調用 convert2Addresses() 方法，提取所有地址，生成一個純地址列表。
例如： ["http://1.1.1.1", "http://1.1.1.2", ...]
? 用于后續通過索引返回最終選中的地址。

Java
深色版本

? ? ? ?
double[] cumulativeWeights = calcCumulativeWeight(list);
調用 calcCumulativeWeight() 方法，計算累計權重比例數組。
例如：如果原始權重是 [1, 3, 6]，則：
? 總權重 = 10
? 比例 = [0.1, 0.3, 0.6]
? 累計比例 = [0.1, 0.4, 1.0]
? 這個數組用于“輪盤賭”式隨機選擇。

Java
深色版本

? ? ? ?
double random = ThreadLocalRandom.current().nextDouble(0, 1);
生成一個 [0, 1) 區間內的隨機數，作為“命中值”。
例如： random = 0.45
? 這個隨機數將在累計權重數組中查找它“落在哪個區間”。

Java
深色版本

? ? ? ?
int index = Arrays.binarySearch(cumulativeWeights, random);
使用二分查找在 cumulativeWeights 數組中查找 random 的插入位置。
? 如果 random 正好等于某個元素，返回該元素的索引（≥0）。
? 如果 random 不在數組中，返回 -(插入點) - 1（負數）。
例如：
? cumulativeWeights = [0.1, 0.4, 1.0]
? random = 0.45 → 二分查找返回 -3（因為應插入在索引 2 前）
? random = 0.4 → 返回 1
? random = 0.05 → 返回 -1

Java
深色版本

? ? ? ?
if (index < 0
) {
index = -index - 1
;
} else
{
return
addresses.get(index);
}
處理二分查找的結果：
? 如果 index < 0：說明 random 不在數組中，需要轉換為應插入的位置。
? index = -index - 1 就是它應該插入的位置，也就是它“落在”的區間。
? 例如：-3 → 2，說明 random=0.45 落在第 2 個區間（即第三個地址）。
? 如果 index >= 0：說明 random 正好等于某個累計值，直接返回該索引對應的地址。
? 這一步完成了“輪盤賭”選擇：根據隨機數找到對應的地址索引。

Java
深色版本

? ? ? ?
if
(index < cumulativeWeights.length && random < cumulativeWeights[index]) {
return
addresses.get(index);
}
增強校驗：確保 index 合法，并且 random 確實小于等于該區間的上限。
? 雖然前面已經通過二分查找確定了位置，但這里再次確認。
? 防止邊界問題或浮點誤差。
? 如果滿足條件，返回 index 對應的地址。

Java
深色版本

? ? ? ?
return null;
如果以上條件都不滿足（理論上不應該發生），返回 null。
?? 這是一個兜底邏輯，表示選擇失敗。

🔹 方法二：calcCumulativeWeight() —— 計算累計權重
Java
深色版本

? ?
private double[] calcCumulativeWeight(List<Pair<String, Double>> list) {
輸入權重列表，返回累計權重比例數組。

Java
深色版本

? ? ? ?
double originWeightSum = 0D
;
for
(Pair<String,Double> item : list) {
double
weight = item.getRight();
originWeightSum += weight;
}
計算所有權重的總和。
例如： [1, 3, 6] → originWeightSum = 10

Java
深色版本

? ? ? ?
double[] weightRatios = new double
[list.size()];
int index = 0
;
for
(Pair<String,Double> item : list) {
double
singleWeight = item.getRight();
weightRatios[index++] = singleWeight / originWeightSum;
}
計算每個權重占總權重的比例。
例如： [1/10, 3/10, 6/10] = [0.1, 0.3, 0.6]

Java
深色版本

? ? ? ?
double[] cumulativeWeights = new double
[list.size()];
double randomRange = 0D
;
for (int i = 0
; i < index; i++) {
cumulativeWeights[i] = randomRange + weightRatios[i];
randomRange += weightRatios[i];
}
構建累計權重數組：
? cumulativeWeights[0] = 0.1
? cumulativeWeights[1] = 0.1 + 0.3 = 0.4
? cumulativeWeights[2] = 0.4 + 0.6 = 1.0
? 最終得到 [0.1, 0.4, 1.0]，表示三個區間的邊界。

Java
深色版本

? ? ? ?
double doublePrecisionDelta = 0.0001
;
if (index == 0 || (Math.abs(cumulativeWeights[index - 1] - 1
) < doublePrecisionDelta)) {
return
cumulativeWeights;
}
throw new RuntimeException("累加權重計算出錯,因為幾率和不等于1");
校驗累計權重是否接近 1.0（允許浮點誤差）。
? 如果最后一個元素不是 1.0（在誤差范圍內），拋出異常。
? 防止權重計算錯誤導致概率偏差。

🔹 方法三：convert2Addresses() —— 提取地址
Java
深色版本

? ?
private List<String> convert2Addresses(List<Pair<String, Double>> list)?
{
return
list.stream().map(Pair::getLeft).collect(Collectors.toList());
}
使用 Java 8 Stream 流，從 Pair<String, Double> 列表中提取所有 String 地址，返回一個純地址列表。
? 用于后續通過索引返回地址。

? 四、算法核心思想：輪盤賭（Roulette Wheel Selection）
? 權重歸一化：將權重轉換為 [0,1] 區間內的比例。
? 構建累計區間：如 [0.1, 0.4, 1.0] 表示三個區間：
? [0, 0.1) → 地址 A
? [0.1, 0.4) → 地址 B
? [0.4, 1.0] → 地址 C
? 生成隨機數：在 [0,1) 內隨機。
? 查找區間：使用二分查找確定隨機數落在哪個區間，返回對應地址。
? 權重越高，區間越寬，被選中的概率越大。

? 五、總結
組件
作用
Pair<String, Double>
存儲地址和權重
calcCumulativeWeight()
計算累計權重比例數組
convert2Addresses()
提取地址列表
Arrays.binarySearch()
快速查找隨機數落在哪個區間
ThreadLocalRandom
生成隨機數

? 六、運行流程圖（簡化）
深色版本

輸入: [(A,1), (B,3), (C,6)]
↓
計算總權重 = 10
↓
計算比例: [0.1, 0.3, 0.6]
↓
累計比例: [0.1, 0.4, 1.0]
↓
生成 random = 0.45
↓
二分查找 → 落在 [0.4, 1.0] 區間 → 選中 C