Placing each key in a single random shard leaves a maximum load of about ln n / ln ln n. Sampling two shards and taking the lesser-loaded one leaves about ln ln n — a logarithm replaced by the logarithm of a logarithm, for the cost of one extra lookup. Both of those results are stated and not proved anywhere in this library, so what this lesson does is measure them on placements you can reproduce.
Core ideas
The rule is one sentence and the effect is out of all proportion to it, which is why the honest thing to do with the theory is to state it and measure the rest.
Instead of hashing a key to one shard and placing it there, hash it to d shards, look at how full each of them is, and put the key in the least full. At d = 2 that is one extra lookup per placement and no coordination between placements. The lab runs both rules from the same stream of draws, so the comparison is not confounded by the randomness.
The one-choice maximum grows like ln n / ln ln n, which is 3.58 at n = 1 024 and 5.27 at n = 1 048 576. The two-choice maximum grows like ln ln n, which is 1.94 and 2.63 at the same two sizes. Taking a logarithm of a quantity that was already a logarithm is why doubling n barely moves the second column at all.
The obvious next thought is that scanning every bin would be better still. It is, marginally: the gain from one choice to two is the collapse, and the gain from two to a full least-loaded search is small. Over seeds 3 to 10 the lab's one-choice maximum averaged 5.25 and the two-choice maximum was 3 on every single seed. The expensive part of the rule is the first extra look.
The material
The rule, the two growth rates and their standing on this path, what the measurement shows, and why more than two choices is not the next step.
For a placement of m keys into n bins, the maximum load is the occupancy of the fullest bin. The case of interest here is m = n, where the mean occupancy is exactly 1 and the maximum is therefore entirely a statement about the spread. The d-choice rule places each key in the least loaded of d bins chosen at random for that key.
At m = n the mean is one key a bin, so any maximum above 1 is imbalance and nothing else. That is what makes this the clean case to measure: there is no scale in the answer, and a maximum of 5 means the fullest bin holds five times what an even placement would give it.
The second column is the striking one: eight seeds, eight maxima, and every one of them is 3. One choice produced 5 or 6; two choices produced 3 every time. The rule does not merely lower the maximum, it makes it much less variable, which is the property a capacity plan actually wants.
The empty-bin counts are worth a glance too. Two choices left 243 bins empty where one choice left 377, because a key that would have piled onto a busy bin goes to a quieter one instead. The exact expectation for the one-choice case, m(1 − 1/m)ⁿ with m bins and n keys, is computed on the Algorithms path in “Balls in Bins and the Birthday Bound”; this lesson counts rather than derives it.
The one-choice maximum load at m = n is Θ(log n / log log n), and sampling d bins instead of one replaces it with a quantity growing like log log n — this course states and measures the d = 2 case as ln ln n, which is the figure the lab prints. Both of those results are stated, not proved — not in this lesson, not on the Algorithms path, not anywhere in this library. Their proofs need Chernoff bounds, which no subject here teaches, and the Algorithms path's scope explicitly excludes them.
So the numbers printed beside the measurements are quoted results rather than derived ones, and they are quoted as floating-point approximations: ln n / ln ln n = 3.58 and ln ln n = 1.94 at n = 1 024 are rounded, and the lab labels them where it prints them. “Balls in Bins and the Birthday Bound” states the one-choice result with the same caveat and computes the exact collision and empty-bin expectations that this lesson does not; it points back here as the place where the maximum load is what a system actually pays for.
At n = 1 024 the stated one-choice figure is 3.58 and the measured maximum over eight seeds averaged 5.25. Those do not contradict each other: Θ(log n / log log n) is a growth rate with constants suppressed, so it says how the maximum scales and not what it equals at a particular n. Use the rate to answer “what happens when the fleet is ten times bigger”, and use the measurement to answer “what do I provision now”. Substituting one for the other is the error this example exists to prevent.
Because the benefit is nearly all in the first extra look, and the cost of the search is not. A full least-loaded placement needs the load of every bin at the moment of placement, which in a distributed system means either a central allocator or a global view that is stale by the time it is used — and a stale global view herds new keys onto whichever bin looked emptiest, which is worse than either rule here. Two random probes need no global state at all.
The rule also has an obvious application outside key placement, and it is the reason the result is famous: the same arithmetic governs a load balancer choosing between backends. Sampling two backends and sending the request to the one with fewer outstanding requests gets most of the benefit of least-loaded balancing with none of its coordination, which is exactly the trade above with keys replaced by requests.
Interactive
Sampling two bins and taking the lesser, measured against sampling one
Method
Two placements, one stream, several seeds — and a clear label on which numbers were measured and which were quoted.
With as many keys as bins the mean occupancy is one and the maximum is pure imbalance. Any other ratio mixes the spread with a scale and makes two rules harder to compare.
The comparison is between placement rules, so the stream must be shared. Running each rule from its own seed leaves you comparing two samples as well as two rules, and at these sizes the sampling difference is the same size as the effect.
One choice gave 5 or 6 across eight seeds; two choices gave 3 on all eight. The spread is part of the result — a rule with a stable maximum is worth more to a capacity plan than one with the same mean and a wider range.
Write ln n / ln ln n = 3.58 (stated, rounded) next to 5.25 (measured, eight seeds). They are different kinds of claim, and keeping them in adjacent columns with their labels is what stops the asymptotic being quoted as a provisioning figure.
One seeded run of each rule, then the same comparison over eight seeds, then the two quoted rates beside them.
The stated rates are smaller than the measurements and that is expected: they are growth rates with their constants suppressed, and they are being evaluated at a single, fairly small n. What they are for is the comparison between the two columns rather than the value of either.
For a faded rehearsal, take n to 4 096 with d = 2 and reseed four times. The supplied first move is the two stated rates at that size — ln n / ln ln n = 3.93 and ln ln n = 2.12. Record both measured maxima, say how much each moved relative to n = 1 024, and then state which of the two columns moved by roughly the amount its stated rate predicted. Label every figure you write down as measured or stated.
You should be able to run and read both placements, quote the measured maxima with the number of seeds behind them, write the stated rates beside them with the word “stated”, and explain why d = 2 rather than d = n is the engineering answer.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.