In distributed systems, consistent hashing is how you decide which server stores which piece of data. The classic version is essentially the “balls into bins” model: each item (ball) is assigned to a random server (bin). That means the maximum load on any server – the busiest machine – grows like

Θ(log n / log log n)

where n is the number of servers. For n=1000000, that’s only about 5 or 6.

It may sound tiny, but for systems that need strict guarantees, it’s not small enough. A server might still get 10–20× more requests than another. Hot spots happen – a single machine melts while others sit idle.

In 2016, Google published “Consistent Hashing with Bounded Loads”. The paper then adds a hard capacity limit, guaranteeing that no server ever exceeds a user‑defined bound.

I’m currently reading this paper. It’s a fantastic opportunity to revise probability and randomized algorithms. Because to really understand why the classic scheme gives

Θ(log n / log log n)

and why two choices blows it out of the water, you have to go back to the beginning.

The birthday problem

We have n people, 365 days. The chance of no shared birthday is:

P(no match) = (365/365) · (364/365) · ⋯ · ((365 − n + 1)/365)

For n=23, that product dips below 0.5, so a collision is more likely than not. The key insight: the number of pairs grows like n². Even though any single pair is unlikely to match, there are so many pairs that the improbable becomes probable.

Takeaway: If you’re looking for any collision among random items, the threshold grows like the square root of the number of possibilities. For birthdays, √365 ≈ 19, and the real answer is 23. That’s very different from the “linear” guess of 183 (half of 365).

Now swap parties for servers

Let’s generalise. Instead of days, think bins. Instead of people, think balls. Throw n balls randomly into n bins. The birthday paradox tells us a collision is almost certain. But a more interesting question, and more relevant in this context: how full does the fullest bin get?

That’s the maximum load problem. In computing, each bin is a server, each ball is a request. If one server ends up with way too many requests, it’s a bottleneck.

Say the balls and the bins are equal in number. What’s the maximum load then? One can highhandedly think of it as 1. But the answer is:

Θ(log n / log log n)

Even for a million bins (n=10⁶), log(n)≈13.8 and log(log(n))≈2.6, so the ratio is about 5.3. The fullest bin holds only 5 or 6 balls on average. In practice, with 10⁶ servers, you’ll still see some servers with load 10, 12, or even 15, while others sit at 0 or 1. For a system that processes billions of requests per second, a 2× imbalance is a disaster.

You don’t want your system to work on the Pareto Principle. This is exactly the problem that Google solved with its paper.

Fast forward to consistent hashing

Classic consistent hashing assigns each item to a single random server, the balls‑into‑bins model. Consequently, the maximum load grows like

Θ(log n / log log n)

While that’s small, it isn’t bounded. In a dynamic system with servers joining and leaving, the constant can become problematic.

The power of two choices (look at two random servers, pick the less loaded one) changes the game completely. The maximum load drops to

Θ(log log n)

which is exponentially better. But we’ll get to that in its time.

More writing: Yes, you can store JSONs in Postgres. No, you shouldn’t. Well, it depends.  ·  This piece is also on Substack.