Benchmarking a new load balancing algorithm
- Dominant language
- C#
- Stars
- 9.6k
- Forks
- 933
- Avg merge
- 12d 18h
- Merged PRs (30d)
- 2
Description
### What should we add or change to make your life better?
We would like to benchmark a simple variant of the Two-Choice load balancing algorithm on YARP. Is there a recommended benchmark or a typical workload that you use?
The variant is the following: For each request,
1. Allocate to the least loaded of two randomly chosen servers (i.e., like Two-Choice) with probability β.
2. Otherwise, allocate to a random server.
Somewhat surprisingly we recently demonstrated in theory and simulations ([paper](https://arxiv.org/pdf/2302.04399.pdf), [slides](https://www.cl.cam.ac.uk/~dl516/slides/spaa23_slides.pdf), [visualisation](https://dimitrioslos.com/phdthesis/conf/spaa23.html)) that for suitably chosen β, this outperforms Two-Choice when there is outdated information (RTT is large, there are multiple allocators) or there is noise. The main reason for this is that it allocates to lesser loaded servers less aggressively than Two-Choice, so that it spreads the load more evenly (see figure below).

We would like to see whether this result also implies improvements in real-world load balancers, including YARP. For the evaluation purposes, I have drafted a very simple implementation (see [here](https://github.com/Dim131/reverse-proxy)) and was wondering whether you could give me some pointers for setting up and running a benchmark representative of a typical workload.
Kind regards,
Dimitris
P.S. I have reached out to a few other open source load balancers.
Contributor guide
Assessment
This issue has not been assessed yet.