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, 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 权重随机内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13