# Balls Into Bins In Distributed Systems

DevFeed: [Balls Into Bins In Distributed Systems](<https://devfeed.tech/articles/balls-into-bins-in-distributed-systems-12481.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2018/01/01/balls-into-bins.html>)

Author: Marc Brooker

Published: 2018-01-01T00:00:00Z

Content type: article

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [distributed-systems](<https://devfeed.tech/topics/distributed-systems.md>), [Scalability](<https://devfeed.tech/topics/scalability.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [backends](<https://devfeed.tech/topics/backends.md>), [systems](<https://devfeed.tech/topics/systems.md>)

Tags: [backends](<https://devfeed.tech/tags/backends.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [distributed-systems](<https://devfeed.tech/tags/distributed-systems.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [load-balancer](<https://devfeed.tech/tags/load-balancer.md>), [random](<https://devfeed.tech/tags/random.md>), [scalability](<https://devfeed.tech/tags/scalability.md>), [scale](<https://devfeed.tech/tags/scale.md>), [statistics](<https://devfeed.tech/tags/statistics.md>), [systems](<https://devfeed.tech/tags/systems.md>), [work](<https://devfeed.tech/tags/work.md>)

## AI overview

This article explains the Balls Into Bins problem and its relevance to hash tables, distributed load balancing, and push-based work allocation. It discusses how request or work-item distributions affect lookup performance, load-balancing strategies, scalability, and statistics such as the maximum, mean, median, variance, and distribution tail.

## Source excerpt

Balls Into Bins In Distributed Systems Throwing things can be fun. If you've come across the Balls Into Bins problem, you probably heard about in context of hash tables. When you hash things into a hash table (especially with separate chaining) it's really useful to be able to ask "If I throw 𝑀 balls into 𝑁 bins, what is the distribution of balls in bins?" You can see how this is fundamental to hash tables: the amortized complexity argument for hash tables depends on their being some load factor (i.e. 𝑀/𝑁) for which most bins contain a small number of items. Once this stops being true, lookup and insertion time on hash tables starts to get ugly. So from that perspective it's already clearly an important problem. Load Balancing and Work Allocation Hash tables aren't the only place that the Balls Into Bins problem is interesting. It comes up often in distributed systems, too. For one example, think about a load balancer (in this case a distributor of independent requests) sending load to some number of backends. Requests (𝑀) are balls, and the backends are bins (𝑁) and typically there are multiple requests going to each backend (𝑀 > 𝑁). If we know how to solve for the number of balls in each bin, we can understand the limits of random load balancing, or whether we need a stateful load balancing algorithm like least connections. This is an important question to ask, because sharing consistent state limits scalability, and sharing eventually-consistent state can even make load balancing decisions worse. Load balancing is much easier if it can be done statelessly. A related problem is push-based work allocation. Here, there is some co-ordinator handing out work items to a fleet of workers, and trying to have those workers do approximately equal amounts of work. One way that systems end up with this pattern is if they are using shuffle sharding or consistent hashing to distribute work items (or records). These hashing-based methods can be great for scaling, and so are wid