dotnet / dotnet/yarp

Benchmarking a new load balancing algorithm

Open
#2,168 2 comments 0 reactions 0 assignees View on GitHub
Type: Idea
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).

![spaa23_tc_vs_opb](https://github.com/microsoft/reverse-proxy/assets/9382526/148640ce-9b0c-43dc-aec9-cc4929164406)

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.