# Random Load Balancing is Unevenly Distributed

DevFeed: [Random Load Balancing is Unevenly Distributed](<https://devfeed.tech/articles/random-load-balancing-is-unevenly-distributed-20757.md>)

Original publisher: [Read original article](<https://www.evanjones.ca/random-load-balancing-is-uneven.html>)

Published: 2023-08-29T13:13:23Z

Content type: article

Language: en

Sources: [Evan Jones](<https://devfeed.tech/sources/evan-jones.md>)

Topics: [Load Balancing](<https://devfeed.tech/topics/load-balancing.md>), [distributed-systems](<https://devfeed.tech/topics/distributed-systems.md>), [Simulation](<https://devfeed.tech/topics/simulation.md>), [Server](<https://devfeed.tech/topics/server.md>)

Tags: [capacity](<https://devfeed.tech/tags/capacity.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [load-balancing](<https://devfeed.tech/tags/load-balancing.md>), [simulation](<https://devfeed.tech/tags/simulation.md>)

## AI overview

Randomly distributing work across servers creates load imbalance because the most-loaded server, rather than the average server, determines required capacity. A simulation illustrates how this can waste capacity and cause worse-than-linear scaling.

## Source excerpt

This is a reminder that random load balancing is unevenly distributed. If we distribute a set of items randomly across a set of servers (e.g. by hashing, or by randomly selecting a server), the average number of items on each server is num_items / num_servers. It is easy to assume each server has close to the same number of items. However, since we are selecting servers at random, they will have different numbers of items, and the imbalance can be important. For load balancing, a reasonable model is that each server has fixed capacity (e.g. it can serve 3000 requests/second, or store 100 items, etc.). We need to divide the total workload over the servers, so that each server stays below its capacity. This means the number of servers is determined by the most loaded server, not the average. This is a classic balls in bins problem that has been well studied, and there are some interesting theoretical results. However, I wanted some specific numbers, so I wrote a small simulation. The summary is that the imbalance varies with the expected number of items per server (that is, num_items / num_servers). A workload is more balanced with more items or with fewer servers. Most interestingly, this means that scaling a system by adding more servers makes the distribution more unfair. This is one reason we can get worse than linear scaling of some distributed systems. Let's make this more concrete with an example. Let's assume we have a workload of 1000 items, and each server can hold a maximum of 100 items. If we place the exact same number of items on each server, we only need 10 servers, and each of them is completely busy. However, if we place the items randomly, then the median (p50) number of items is 100 items. This means half the servers will have more than 100 items, and will be overloaded. If we want less than a 1% chance of an overloaded server, we need to look at the 99th percentile (p99) server load. We need to use at least 13 servers, which has a p99 load of 97 it