Load Balancing: The Intuition Behind the Power of Two Random Choices

They talked about doing this for AWS lambda at "gigantic scale". I assume at some point scanning all the buckets becomes infeasible.

I think it comes down to complexity. Scanning is O(N) where N is the number of buckets, two random choices is O(1) (if bucket lookup is O(1), e.g. a hash map).

Do you have to pick two random buckets or just one random bucket and one adjacent bucket?

Feels like picking an adjacent bucket would work just as well and increase locality.

Two random choices has a few significant advantages over "find the least filled one":

- It's O(1), rather than O(buckets).

- It's robust to stale data and concurrency. One way systems try to avoid the O(buckets) work is by caching, or by scanning in parallel, either of which cause stale load estimates. "Pick the best" tends to lead to significant over-filling http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20... or https://brooker.co.za/blog/2012/01/17/two-random.html).

- Best-of-k (rather than best-of-two) provides a parameter `k` that allows the system to tradeoff between optimality (higher k is more optimal), and robustness to stale data and concurrent accesses (lower k is more robust). Mitzenmacher's core observation is that the step up from k=1 to k=2 is a massive improvement in optimality with only a small loss in robustness (and much more than most people would expect).

It felt over-complicated to me, too. Your explanation is significantly more concise and is a lot clearer to me

The beauty is it doesn't need to be particularly for the technique to work.

consistent hashing requires a bunch of additional memory to solve load variance. there's a nice equation to calculate this somewhere that I'd have to search for, but roughly you need 100 virtual slots in your coordinate space per every destination server to reduce standard deviation to about 10%, and 1000 virtual slots to reduce it to less than 5%.

There's some alternative hashing solutions (rendezvous hash, jump hash, maglev) that improve load distribution without the memory overhead, but still have similar challenges with node addition/removal overhead. Also, integrating state into any of these solutions is incredibly difficult and really antithetical to their point (being deterministic). This is fine when you're assigning uniform workloads and preferred when these assignments need to be long-lived, but for request load balancing you're dealing with uneven workloads and short-lived assignments.

This is where power of two load balancing shines, as it allows you to perform stateful load balancing (using queued requests, cpu utilizations, host perf) efficiently with low memory overhead and minimal effort to add/remove nodes. And if you lose a node with state its no big deal because the lifetime of a request is so short.

It’s more costly to determine the server with absolute least connections since you have to keep track of the ordering of the servers by how many connections they have.

Not my field but I'm guessing when you have thousands of servers it can be quite the overhead to keeping track of the load of each one for each request.

The proposed algorithm only needs to consider two, and from what I can gather should work in parallel with multiple load balancers without coordination.

O(log n) vs O(1)

> what are the advantages against taking the least occupied server/bin always

The other answers are saying for algo reasons. Sure, but, pick two is even more better for uptime reasons.

In serving at scale, quite often the "least occupied" server of all of them is one with an error causing it to have least load/connections/whatever.

By starting with a random two, you pick among probably healthy servers, and then the least load.

> good improvements with nginx load balancing when changing its configuration to least_conn, that chooses the server with least connections.

nginx doesn't know why your app is failing to keep connections open long enough to serve them, least_conn between two random results in far fewer 100% "outages" when a single box or subset of boxes among 10s or 1000s is bad.

In large enough systems, it becomes prohibitively expensive to keep consensus of the state of all members.

Sure with 10 or so hosts it’s trivial to select the least busy one but at the scale of 1000s of hosts you begin to run into a ton overhead just to decide where to forward a request.

As many others have said, O(N) for each request vs O(1) while avoiding hot spots.

See my reply here: https://news.ycombinator.com/item?id=37175685

Short version: it's robust to staleness and concurrency, which is important in distributed settings ("find the best" is hard to do when "best" is a moving target).

I suspect it’s because random assignment is simpler to implement than incremental round robin when the targets are moving rapidly (eg. pods coming and going in K8s). If you are iterating over N replicas in true round-robin fashion and the nth+1 replica comes online, you need to manage inserting it into your rotation to maintain true incremental round robin. To do it probabilistically you just update your weights. This is how kube-proxy sets up iptables based load balancing.

Round robin is hard when you're doing things concurrently and distributed, because state is hard.

A server is taking requests 30 at a time in separate threads. To add a sequential step for picking which target is next, you need to add a synchronous piece of code that all of the threads depend on- a bottleneck. That's doable, but it adds complexity.

And then you have (let's say) 30 servers making calls. Do they each use round robin load balancing separately, or do they try to coordinate? That's difficult.

"Pick two randomly" requires no state. Every thread and server can run the same algorithm without regard for each other.

If you have multiple load balancers then doing round robin is hard because they need to talk to each other to ensure proper balancing.

The proposed algorithm should work sufficiently well for multiple load balancers without coordination, assuming the number of load balancers is small compared to the number of servers processing the load.

Round robin can work very well when the variance of task sizes is small, but degrades quickly when the variance of task sizes becomes large (i.e. there are some tasks that keep servers busy for minutes, and some for milliseconds).

In distributed systems with large numbers of producers (like one of the systems Mihir has worked, AWS Lambda) round robin essentially degrades into random placement as the number of producers increases.