Java实现权重随机算法详解

Java实现权重随机算法详解

目录应用场景本文目标算法详解权重比例java 实现参考

应用场景

客户端负载均衡，例如 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, 1http://] 来表示这三个 server 的覆盖范围，使http://用 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 {

private final List items = new ArrayList<>();

private double[] weights;

public WeightRandom(List> itemsWithWeight) {

this.calWeights(itemsWithWeight);

}

/**

* 计算权重，初始化或者重新定义权重时使用

*

*/

public void calWeights(List> itemsWithWeight) {

items.clear();

// 计算权重总和

double originWeightSum = 0;

for (ItemWithWeight 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 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] BxEwbQeUK= 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 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 server1 = new ItemWithWeight<>("server1", 1.0);

ItemWithWeight server2 = new ItemWithWeight<>("server2", 3.0);

ItemWithWeight server3 = new ItemWithWeight<>("server3", 2.0);

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

// 统计 (这里用 AtomicInteger 仅仅是因为写起来比较方便，这是一个单线程测试)

Map 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) -http:// 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。