The Power of Two Choices
Epilogue: Beyond servers

Previously, we treated requests as balls and servers as bins: each ball looks at two bins at random and joins the emptier one. Nothing about that picture needs servers. A hash table, the data structure behind almost every lookup a computer does, stores keys in buckets the same way: a hash function sends each key to a bucket, and a bucket that collects too many keys gets slow.

That connection is a big part of why ACM gave Azar, Broder, Karlin, Mitzenmacher and Upfal its Paris Kanellakis Theory and Practice Award in 2021:

"Since bins and balls are the basic model for analyzing data structures, such as hashing or processes like load balancing of jobs in servers, it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications." (ACM, 2021)

This epilogue follows the idea out of the server room, and picks up three more surprises along the way.

1Balls that never leave

Requests finish and leave. Stored data doesn't: a file or a key stays wherever it's put. So keep adding balls and never take any away. Here are 100 bins, one random choice on the left and two choices on the right. Each bar shows how far a bin is above or below the average, and the fullest bin is red.

With one random choice, luck piles up. A bin that gets ahead early has no reason to fall back, and the gap keeps growing: by a thousand balls per bin, the fullest bin is about 75 balls above average. With two choices it's about 2, and it stays 2 however long you let it run. A bin that gets ahead is simply passed over until the others catch up, so bad luck never accumulates. Petra Berenbrink, Artur Czumaj, Angelika Steger and Berthold Vöcking proved that this holds forever: with two choices, the gap from a perfectly even split "does not increase with the number of balls" (Berenbrink et al., 2000).

2A hash table is a load balancer

A hash table gives each bucket a few slots, here 4. A hash function picks a bucket for each new key, as good as a random choice, and a key that lands in a full bucket is trouble: it spills into a slower overflow area, or the whole table has to be rebuilt. Here is one key arriving at a table with one hash function, and at the same table with two:

Now fill a whole table and see how far it gets before the first key has nowhere to go.

With one hash function, a large table (65,536 buckets) typically overflows its first bucket when it is only about 7% full. Give each key two hash functions and put it in the emptier of its two buckets, and the same table fills to about 47% first. The price is that every lookup checks two buckets instead of one, and in hardware both can be read at once. Azar, Broder, Karlin and Upfal described this "two-way chaining" in their 1994 paper, and it spread through hash tables of every kind:

"The impact of [their work] on the design of randomized algorithms and data structures, particularly hash tables and their relatives, has been enormous." (Kirsch, Mitzenmacher & Varghese, 2010)

3Unfair is better

Here is a strange improvement. Split the buckets into a left half and a right half, and give each key one random bucket in each half. The key goes into whichever of its two buckets holds fewer keys, as before. The only change is what happens when both hold the same number, a tie: instead of flipping a coin, always go left. Step through a few keys:

Berthold Vöcking showed in 1999 that this beats breaking ties fairly:

"Surprisingly, this algorithm uses an unfair tie-breaking mechanism, called Always-Go-Left, resulting in an asymmetric assignment of the balls to the bins." (Vöcking, 2003)

Below, both tables get exactly the same random choices, 10,000 keys into 10,000 buckets. The only difference is what happens on a tie.

Breaking ties fairly leaves about 88 buckets with 3 or more keys. Always going left leaves about 45, and almost all of them are on the left.

Andrei Broder and Michael Mitzenmacher explained why. For a bucket to reach 3 keys, a new key has to find both of its buckets already holding 2, one on each side; otherwise it takes the emptier one. Ties are common, especially early on, when most buckets hold the same number of keys. Sending every tie left fills the left side a little faster, so the right side has fewer 2s, and finding a 2 on both sides at once takes much longer (Broder & Mitzenmacher, 2001). Both parts matter: splitting the buckets without the tie rule, or the tie rule without the split, does nothing. Vöcking also proved that no rule using two choices can do much better. Their paper brought the idea into network routers, where it has stuck:

"It appears that d-left hashing is the 'state of the art' way to implement a hash table in hardware; many current products use this scheme." (Kirsch, Mitzenmacher & Varghese, 2010)

4Let them move

Two choices still gives up at about half full. When a new key finds both of its buckets full, there is usually plenty of room elsewhere; the key just can't get to it. In 2001, Rasmus Pagh and Flemming Friche Rodler proposed making room by moving keys that are already in the table.

Every key's two buckets are fixed when it's created, and it always sits in one of them. When a new key finds both of its buckets full, it takes a slot anyway and kicks out the key that was there. That key moves to its own other bucket, possibly kicking out another, until some key lands in a bucket with room. Step through one insert:

"The 'cuckoo approach', kicking other keys away until every key has its own 'nest', works very well." (Pagh & Rodler, 2004)

It's named after the cuckoo, whose chicks push the other birds' eggs out of the nest. Try it, and compare it with the two rules from before.

Lookups don't get any slower, since every key is still in one of its two buckets, and the table now fills almost to the brim. The cost shows up when inserting new keys instead: kicks are almost never needed until the table is half full, then about 3 per new key at 90% full and dozens near the top. And it can still get stuck: if no chain of kicks leads to a free slot, the new key has nowhere to go, even with empty slots elsewhere. Real systems cap the number of kicks per insert (MemC3 stops at 500), and when an insert hits the cap, they rebuild the table with new hash functions or more buckets (Fan, Andersen & Kaminsky, 2013).

The table above is small, and small tables are forgiving. The real difference shows up as tables grow:

The bigger the table, the earlier one and two choices break, because a big table has more buckets that can get unlucky. With kicking, it barely matters: the table fills to between 95% and 98% at every size. Cuckoo hashing runs in real systems. MemC3, a redesign of the widely used memcached cache, used it to cut memory for small items by 30% and serve up to three times as many requests (Fan, Andersen & Kaminsky, 2013), and cuckoo filters use it to replace the Bloom filters common in networks and databases (Fan et al., 2014).

5Where it lives

From balls and bins in 1994 to the hash tables inside routers and caches, the same small idea keeps paying off: don't settle for one random place, look at two. The ACM award named some of the systems built on it:

"Google's web index, Akamai's overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm." (ACM, 2021)

And it ended with a prediction that has held up so far:

"Their content had, and will surely continue to have, a demonstrable effect on the practice of computing." (ACM, 2021)