The Hot Key Hashing Can't Fix

Hashing the key solved the hot spot that key ranges created. It is worth being exact about how far that goes: hashing reduces hot spots, and it cannot eliminate them.

The Limit Case

Start just short of the extreme — one key taking the large majority of the traffic, and a cluster that looks like this.

Even load, and the same cluster with one hot partition

Two four-partition clusters drawn as bar charts of share of load. On the left every partition carries about a quarter. On the right one partition carries eighty-five percent while the other three sit near idle — the bottleneck is that single busy partition, and adding nodes does not move it.

Now push it all the way, so that every read and every write is for that one key. Hash it, range it, do whatever you like — all those requests still route to the same partition, because that is what “the partition for this key” means. No partitioning scheme can spread a single key across nodes, since the scheme’s whole job is to decide on one home for each key. Adding nodes does not help. It has never been a capacity problem; it is a problem of everything having the same address.

The Celebrity

This is an unusual workload, but not an unheard-of one.

Take a social media site. A user with millions of followers does something, and their followers all react at once. That single event produces a storm of writes to the same key — perhaps the celebrity’s user ID, perhaps the ID of the action everyone is commenting on.

Hashing does nothing here, and the reason is worth saying plainly rather than gesturing at: the hash of two identical IDs is the same hash. There is no clever hash function that rescues you, because there is no variation in the input to work with. A hash spreads different keys apart; it has nothing to say about the same key arriving a million times.

Note also what makes this hard operationally: it is bursty and unpredictable. The key that melts your cluster tonight was an ordinary key this morning, and will be ordinary again tomorrow. Whatever you do about it has to survive that.

Splitting the Key

If the input has no variation, you add some.

Splitting a hot key, and the read that pays for it

On the left, every write for one celebrity key lands on a single partition no matter how the key is hashed. On the right, a two-digit random suffix has split that key into a hundred, spread across all four partitions, so the writes distribute. Underneath, one read now has to query all hundred keys and merge the results.

Take the key known to be hot and append — or prepend — a random number. Just two decimal digits turns one key into a hundred, and those hundred keys hash to a hundred different places, so the write load spreads across the partitions rather than piling onto one.

The technique is not subtle, and it works. A key taking 100% of one node’s write capacity now takes roughly 1% on each of a hundred key-slots, distributed across however many partitions you have.

What Splitting Costs

It also has three costs, and they are not incidental.

Reads get more expensive. Having split the writes across a hundred keys, every read must now query all one hundred and combine the results. A single-key lookup has become a hundred-way fan-out and a merge — on every request, forever, not just during the storm. Whatever your read latency was, it is now the latency of the slowest of a hundred parallel requests, which is a meaningfully worse number.

It only pays for genuinely hot keys. Applied to a key with low write throughput, this is pure overhead: you have multiplied the read cost by a hundred to solve a problem that key never had. The arithmetic only works where write volume is high enough that relieving it is worth a hundredfold read amplification — which describes a tiny fraction of keys, and for most applications the split factor should be far smaller than a hundred anyway.

So you need bookkeeping. Because it applies to some keys and not others, something has to track which keys are split, and how many ways. The reader has to know whether to fetch one key or a hundred, and it has to get that answer right on every read. That registry is now part of your system: state to keep, keep correct, keep in sync across every client, and update as keys heat up and cool down.

Which Keys, and How Would You Know?

That last cost hides a question the technique quietly assumes away: the whole approach starts with “a key known to be very hot”, and knowing is the hard part.

Nothing in the storage layer volunteers it. A partition’s aggregate load tells you a partition is saturated, not which of the millions of keys on it is responsible. Finding the offender means per-key request accounting — which is itself a high-cardinality measurement problem, on the hottest path in your system, at exactly the moment it is under the most load.

And a decision has to follow the measurement. How hot is hot enough to split? How wide? When does a key cool off enough to un-split it — and how do you migrate the data back without losing writes in flight? Each of those is a policy your application has to hold an opinion about.

Nobody Does This For You

The obvious question is why the database does not handle all of this itself.

It does not. Today most data systems cannot automatically detect a highly skewed workload and compensate for it, so relieving the skew is the application’s responsibility — deciding which keys to split, how wide, when to start, and when to stop. The database will happily route every one of those requests to the same node and let the node fall over.

Perhaps that changes. Kleppmann’s own note is that data systems may one day detect and compensate for skewed workloads automatically; for now, you have to think through the trade-offs for your own application. In the meantime the honest engineering position is that hot-key mitigation is a thing you build, monitor and operate — not a setting you turn on.

Key Takeaways

Hashing reduces hot spots but cannot remove them: in the limit, all requests for one key still hit one partition, and adding nodes does not help.
The celebrity workload is the real-world version — one key, a storm of writes, and identical IDs hashing identically.
Adding a two-digit random suffix splits one key across a hundred, and spreads the writes.
The bill is a hundred-way read fan-out and merge on every request, worthwhile only for the few keys whose write volume justifies it.
Splitting selectively means keeping a registry of which keys are split and how wide, correct across every client.
Knowing which key is hot is its own problem — per-key accounting on the hottest path, plus a policy for when to split and when to stop.
No mainstream data system compensates for this automatically. It is application work.

This closes the first stretch of partitioning: how a key becomes a partition, and what each answer costs. Three things have been quietly assumed away throughout. Every scheme here routed on the primary key — secondary indexes do not map onto partitions nearly so neatly. Every scheme assumed the partitions were already there — adding and removing nodes means rebalancing them. And every scheme assumed the client knew which node to talk to — which is a request routing problem in its own right.

Those are next.

References

Martin Kleppmann, Designing Data-Intensive Applications, chapter 6 — the treatment of partitioning this sub-series works through.
Giuseppe DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store — the partitioning model underneath Riak and Cassandra, and its own discussion of load imbalance.
Apache Cassandra — Dynamo-style architecture — how a production hash-partitioned store distributes load, and where it stops helping.
Riak KV documentation — a Dynamo-derived store with the same single-key ceiling.