Consistent hashing, and the hot key that hashing cannot fix
Why does modulo hashing turn a node change into an outage, and what fixes the one hot key that hashing cannot?
A distributed cache spreads keys over many nodes. The usual reason given for consistent hashing is "so we do not have to rehash everything". That understates the mechanism by about a factor of ten.
Why modulo hashing is dangerous
With node = hash(key) mod N, a change in the number of nodes remaps (N − 1)/N of all keys. With N = 10 that is 90%. For disposable cache data, "remap" means "miss". So losing one node out of ten gives a cache that is about 90% cold. The second copy's leverage then gives the origin about twenty times its planned load.
Consistent hashing moves only the keys whose owner has vanished, K/N of them (K keys, N nodes), which is the minimum possible. Ten nodes, one fails: modulo hashing makes 90% of the cache cold, consistent hashing 10%. Virtual nodes, which even out each node's share, and bounded loads, which cap it, are explained there too.
The thing hashing cannot fix
A single key maps to one node by definition. No hash function can split the traffic of one key. And hot keys are not an edge case. What makes data cacheable's arithmetic guarantees them. At α = 1 over 10⁹ items, the top key alone carries 1/H_N ≈ 4.7% of all traffic (H_N is the N-th harmonic number, 1 + 1/2 + ... + 1/N ≈ ln N + 0.58, which is about 21 here). With a hundred nodes, each expects 1%. So one key creates a hotspot of about 5 times the average, and no amount of ring tuning removes it. This is Ifeoma's viral article.
The escapes and their prices:
| Escape | How it works | Price |
|---|---|---|
| Replicate the hot entry on k nodes, pick one at random | spreads the load | invalidation fan-out multiplied by k; destroys the single owner that made invalidation cheap; you pay in coherence |
Salt the key with k suffixes (key#0 ... key#k-1) | same idea, done by the client | the same trade, with the fan-out moved to the client |
| A tiny client-side cache of the top keys | each client keeps the hottest keys itself | a tier you cannot invalidate directly |
The third is the standard answer, for an elegant reason: the key that causes the hotspot is exactly the key that a hundred-entry local cache will hold. What makes data cacheable showed that a tiny cache captures just the head of the popularity distribution, and the head is exactly what makes one node hot. The problem and its solution are one Zipf fact seen from two ends. The price is a tier you cannot invalidate, so you are back to the TTL-only regime of Keeping it honest, or to an invalidation push channel, which is what the "tracking" modes in modern cache clients provide.
Resharding is the warm-up problem again
A cache is disposable, so resharding it moves zero bytes of important data. The cost is a miss storm of size (fraction of keys moved) × (hot set), paid over the refill period. So the right way to reshard is gradually, bounded by origin spare capacity. This is the same controller as Keeping it honest's warm-up ramp, in its second use. One controller governs cold start and rebalance, because they are the same event seen from different causes.
Compression: Modulo hashing makes membership changes availability events. And the top key's ~5% share is a hotspot that cannot be fixed by hashing, whose only good answer is the tiny local cache that the same Zipf fact predicts will hold it.