One key carrying a fraction f of the traffic leaves the hottest shard at f·λ + (1 − f)λ/N. The first term has no N in it, so resharding cannot reach below f·λ however far it is pushed — a thousand shards barely moved it in the lab. What does work is splitting the key into s pieces, which turns f into f/s, and the price is paid on every read of that key.
Core ideas
One expression with two terms, and everything on this page follows from which of the two terms contains N.
Split the load in two: the hot key's f·λ and everybody else's (1 − f)λ. The second is spread over the fleet and becomes (1 − f)λ/N on each shard. The first goes wherever that one key hashes and stays there, whole. So the hottest shard carries f·λ + (1 − f)λ/N, and taking N to infinity drives the second term to zero and leaves the first exactly where it was.
Write the key as key#0 through key#(s−1), choosing the suffix at random on each write. Those are s distinct keys, so they hash to s places and the hot term becomes (f/s)·λ on each of them. At f = 12% and s = 8 the hottest shard falls from 17 500 /s to 7 000 /s, which is close to the mean of 6 250 /s.
A read of a salted key has to visit all s pieces and combine them, so reads of that key are multiplied by s. Over the whole read stream the multiplier is 1 − f + f·s, because only the f share fans out: at f = 12% and s = 8 that is 1.84 times the reads overall. Salting is a write-side fix bought with read-side work, and it is only worth it when reads of that key are rare or cheap.
The material
Where the two terms come from, what happens to each as N grows, what salting changes, and what it costs on the read path.
A hot key is a single key that receives a disproportionate share f of the traffic to a dataset. Because every partitioning function maps one key to one shard, the whole of f·λ arrives at one node no matter how the function is chosen or how many shards there are. The remaining (1 − f)λ is spread by whatever the function does.
Read the last column down. Sixty-four times the shards took the hottest shard from 17 500 /s to 12 086 /s, a reduction of 31%, and the remaining 12 086 is 12 000 of hot key plus 86 of everything else. Every further shard is buying a share of the 86. The imbalance column is going the other way — 2.80 times the mean at 16 shards and 123.76 times at 1 024 — because the mean is collapsing while the hottest shard is not.
This is the second of the three skews on this course that resharding does not fix, and it is the starkest. A hot range at least moves when you split it; a hot key does not move at all, because there is nothing in it to split. The asymptote is the shape “Graphs and Asymptotes” on the Algebra path describes: a curve falling toward a horizontal line it never meets, and the line is at f·λ.
Salting a key replaces it with s derived keys — key#0, key#1, …, key#(s−1) — choosing a suffix uniformly at random on each write. Writes to the original key are then spread over s distinct keys, which hash independently. A read must fetch all s pieces and combine them, so the operation the salt makes cheap is the write and the operation it makes expensive is the read.
The arithmetic is immediate: the hot term becomes (f/s)·λ and the rest is unchanged, so the hottest shard holds (f/s)·λ + (1 − f)λ/N. At f = 12%, λ = 100 000 /s, N = 16 and s = 8 that is 1 500 + 5 500 = 7 000 /s, against a mean of 6 250 /s. Where sixty-four times the shards bought a 31% reduction, eight salt pieces bought 60%.
Every read of the salted key now issues s = 8 requests instead of one, so reads of that key are 8 times as expensive. Across the whole read stream the multiplier is smaller, because only the hot key fans out: 1 − f + f·s = 0.88 + 0.96 = 1.84, so the fleet does 1.84 times the reads overall. Both numbers are true and they answer different questions — the first sizes the latency of a read of that key, the second sizes the fleet. Quoting only the second makes salting sound cheaper than it is for the request that actually touches the hot key.
Choose s from the target, not from habit. The lab reports that at these numbers a salt of 4 already brings the hottest shard within 1.5 times the mean, at a read multiplier of 1.36 rather than 1.84. Going to s = 16 gets the hottest shard to 6 250 /s — the mean exactly — for a read multiplier of 2.80. The last increments of balance are the expensive ones.
Salting is one of three answers and it is the one with a running cost. If the hot key is read far more than it is written, a cache in front of it removes the load without touching the partitioning at all — “Hit Rate and Backend Load” prices that. If the key is hot because of one client, a rate limit is cheaper than either. Salt when the traffic is genuinely write-heavy on a key that genuinely has to be one key, and then write down the read multiplier you accepted.
One more property worth stating plainly: f is measured, not assumed. It is the hot key's share of the traffic, and getting it from a sampled request log is usually easy. Everything on this page is a function of f, λ, N and s, so a designer who knows those four numbers can answer “will more shards help?” before anyone builds anything — and the answer, when f·λ is already above one node's capacity, is no.
Interactive
f·λ + (1−f)λ/N, and the first term is not a function of N
Method
Measure f first. Every other number on this page is a function of it, and an assumed f makes the whole calculation decorative.
f is the hot key's share of requests, and a sampled log gives it directly. Do this before anything else: the difference between f = 2% and f = 12% is the difference between a problem more shards will handle and one they cannot touch.
f·λ is what the hot shard carries after infinite resharding. If it is already above a node's capacity, resharding is not a candidate solution and there is no point pricing it. At f = 12% and λ = 100 000 /s the floor is 12 000 /s, which is more than the 8 000 /s node of “How Many Shards”.
f·λ + (1 − f)λ/N at both. The gap between them is the entire benefit resharding can deliver — 17 500 to 12 086 here, and the second figure needed sixty-four times the fleet.
Pick the imbalance you will accept, solve for s, and record 1 − f + f·s beside it. At these numbers s = 4 lands within 1.5 times the mean for a 1.36 read multiplier and s = 8 within 1.12 for 1.84. The number you must not omit from the write-up is the second one.
The hottest shard at the current fleet, then after a large reshard, then after a salt — with the read cost of the last one stated both ways.
Put the two middle blocks side by side. Sixty-four times the machines bought a 31% reduction; eight salt pieces bought 60% and left the fleet alone. That comparison is the lesson, and it is available before anything is built, from four numbers.
For a faded rehearsal, take f to 30% with λ = 100 000 /s and N = 16. The supplied first move is the floor, f·λ = 30 000 /s. Produce the hottest shard now, the hottest shard at N = 1 024, and the salt s that would bring the hottest shard within 1.5 times the mean; then state the read multiplier that s costs overall and the multiplier it costs a read of that key. Say which of your answers would change if λ doubled.
You should be able to compute the hottest shard's load at any N, state the floor and compare it with one node's capacity, choose a salt from a target imbalance, and report both read multipliers the salt costs.
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.