负载均衡算法中的加权随机算法

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