Intro
What is efficient way of Load-Balanced selection algorithm in Real-Time.
The best way of this is that it's always calculate separate ratio of previous and pick up a less selected part and then let a new request to be assigned into that.
But it's not easy and likely to be complicated.
Here, There's quite simple and reliable way to do that.
Let's dive in.
Logical consideration
- It would express to specify each ratio separated with semi-colon. e.g. "10:30:40:20"
- It would use Random class provided by Java.
- And return value should be a index among the specified ratios.
Sequential flow
- Create Random object.
- Make sum of all of ratios.
- Generate random integer value ranging 0 ~ sum.
- Compare the random value where it's placed at.
- Return the index in range among ratios
Code review
package org.chaostocosmos.dev.io;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
public class RandomRatioIndexSelection {
List<Integer> ratioList;
public RandomRatioIndexSelection(String ratioExpr) {
this(Arrays.asList(ratioExpr.split(":")).stream().map(e -> Integer.parseInt(e)).collect(Collectors.toList()));
}
public RandomRatioIndexSelection(List<Integer> ratioList) {
this.ratioList = ratioList;
}
public int getSelectIndex() {
Random random = new Random();
int sum = ratioList.stream().reduce((a, b) -> Integer.sum(a, b)).get().intValue();
int start = 0;
int bound = 0;
int ran = random.nextInt(sum);
for (int i = 0; i < ratioList.size(); i++) {
int ratio = ratioList.get(i);
bound += ratio;
if (ran >= start && ran < bound) {
return i;
}
start += ratio;
}
return -1;
}
public static void main(String[] args) {
RandomRatioIndexSelection rris = new RandomRatioIndexSelection("10:30:40:20");
List<Integer> ratioList = new ArrayList<Integer>();
for(int i=0; i<10000; i++) {
int index = rris.getSelectIndex();
ratioList.add(index);
}
long r0 = ratioList.stream().filter(i -> i == 0).count();
long r1 = ratioList.stream().filter(i -> i == 1).count();
long r2 = ratioList.stream().filter(i -> i == 2).count();
long r3 = ratioList.stream().filter(i -> i == 3).count();
System.out.println("Toal count: "+r0+" "+r1+" "+r2+" "+r3);
}
}
Test dive
If you would run above code, the result is like below image.
It's show what the index count be selected as it's each part of ratios. but there's some strange here. the index counts isn't exactly match with ratios.
It's because that is based on random function and it's not static calculation but also it's Real-Time counting to process continuously. Therefore some counts may have some difference from specified ratio.
Conclusion
We have been to talk about how to implement random selected index given ratios. I guess this could contributing that a service is needed Load-Balancing, For that, may have to be customized.
Always elastic thinking is yours!
Thanks.
Top comments (0)