Detailed Explanation of Weight Random Algorithm in Java
- 2021-10-27 07:26:32
- OfStack
Detailed solution of algorithm
Realization of weight ratio Java
Reference
Application scenario
Client load balancing, such as the client load balancing provided by Nacos, uses this algorithm
Game lottery (the weight of ordinary props is very high, and the weight of rare props is very low)
Objectives of this article
Realization of Weight Random Algorithm in Java
Detailed solution of algorithm
For example, we now have three Server with weights of 1, 3 and 2 respectively. Now I want to load balance three Server
Server1 Server2 Server3
weight weight weight
1 3 2
Weight ratio
We calculate the weight ratio of each Server, weight ratio = own weight/total weight
server1 server2 server3
weight weight weight
1 3 2
radio radio radio
1/6 3/6 2/6
Calculate the coverage area according to the weight ratio
server1 server2 server3
^ ^ ^
|---------||---------|---------|---------||---------|---------||
0 1/6 4/6 6/6
^ ^ ^
0.16666667 0.66666667 1.0
Load balancing according to weight
As shown in step 2, each server has its own range. If you look at every grid as a unit,
server1 (0,1] server2 (1,4] server3 (4,6]
Use the random number function, take the random number between (0, 6), and decide how to choose according to the range of random numbers. For example, if the random number is 2 and is in the range of (1, 4), then server2 is selected.
This is the idea. When implemented in the code, an array [0.16666667, 0.6666667, 1] is used to represent the coverage of these three server, and ThreadLocalRandom or Random is used to obtain random numbers in [0, 1). Then the 2-point search method is used to quickly locate which interval the random number is in
Implementation of Java
The code is basically the same as com. alibaba. nacos. client. naming. utils. Chooser 1, which is optimized in readability.
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);
}
/**
* Use when calculating weights, initializing or redefining weights
*
*/
public void calWeights(List<ItemWithWeight<T>> itemsWithWeight) {
items.clear();
// Calculate the sum of weights
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;
}
// Calculate each item Actual weight ratio of
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;
}
// Calculate each item Weight range of
// Starting position of weight range
weights = new double[items.size()];
double weightRangeStartPos = 0;
for (int i = 0; i < index; i++) {
weights[i] = weightRangeStartPos + actualWeightRatios[i];
weightRangeStartPos += actualWeightRatios[i];
}
}
/**
* Random algorithm selection based on weight
*
*/
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);
}
// Usually you don't go here. In order to ensure that you can get the correct return, you can return here at will 1 A
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));
// Statistics ( Used here AtomicInteger Just because it is convenient to write, this is 1 Single-threaded test )
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);
});
}
}
Here I focus on Arrays. binarySearch (weights, random), I have not used this API before, which leads me to read the source code of Nacos, the operation of this piece of 10 points puzzled
Look at the explanation of the return value of this method in java API document under 1
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.
To explain, first of all, the function of this method is to search the array through the specified key. (The premise is to ensure that the order of arrays is sorted from small to large)
If the array contains the key, the corresponding index is returned If the ES 105EN is not included, the (-(ES 107EN ES 108EN)-1) of the ES 106EN is returned
insertion point (insertion point): Where the key should be in the array. For example, for the array [1, 3, 5], my search for key is 2, and in order, 2 should be at the position of index = 1 in the array, so insertion point = 1.
(Here, jdk makes a distinction between key and key. In order to return all the unfound cases to negative numbers, the operation (-(insertion point)-1) is done.)
So we see that insertion point is what we need. Now we use elementary school mathematics to deduce how to calculate insertion point
// Mathematical derivation in primary school 1 Under insertion point How to calculate
returnValue = (- (insertionPoint) - 1)
insertionPoint = (- (returnValue + 1) )
// So you have the
if (index < 0) {
index = -index - 1;
}
Reference
https://github.com/alibaba/nacos/blob/develop/client/src/main/java/com/alibaba/nacos/client/naming/utils/Chooser.java