Hot keys, cache stampede and invalidation

A hot key is one cache key with so much traffic that it overloads the single node that owns it. A cache stampede happens when a popular key goes missing and every request that misses in the next few hundred milliseconds queries the database at once. Invalidation is the job of removing every stale copy when the data changes, which gets hard once a value lives in hundreds of places. All three break the same promise: that the cache absorbs the load and still tells the truth.

Picture it first: the samosa tray at a wedding

At a big wedding, one tray of samosas draws half the guests. One waiter can’t keep up, so the caterer puts out four trays and gives every table a small plate of its own.

When the main tray empties, forty guests walk into the kitchen together. The cook fries one batch at a time, so the kitchen jams. A smarter caterer sends one waiter in while the others wait or take the last cold samosas, and refills trays when they are nearly empty, not bare.

Then a batch of chutney turns out to be spoiled. Every plate with it must go: trays, tables, the kids’ corner. Hunting plate by plate misses some; if every dish with that chutney carries a green toothpick, the waiters clear them all in one sweep.

Map it back: the popular tray is a hot key, the extra trays are key copies and the table plates are near caches. The rush into the kitchen is a stampede; sending one waiter is a lock or single-flight; the cold samosas are stale-while-revalidate; refilling early is probabilistic early refresh. The spoiled chutney is invalidation, and the toothpicks are tags.

Hot keys: when one key outgrows its shard

A distributed cache spreads keys across nodes, not requests. Every read of score:match42 lands on the one primary that owns its slot, however many nodes you add (distributed caching). A key is hot when its own traffic exceeds what one node can serve.

Typical hot keys: a live score during an IPL final, a celebrity’s profile right after they post (AWS’s caching guide uses exactly this as its thundering-herd example), a flash-sale SKU at 12:00 sharp, tatkal availability for one popular train, and the config blob or deals list that every request reads.

The arithmetic is short. Twelve million viewers whose apps poll the score every 30 seconds generate 12,000,000 ÷ 30 = 400,000 reads/s on one key. If your load tests show one Redis node sustains about 100,000 ops/s at an acceptable p99, that key needs four nodes’ worth of CPU on one node. If the scorecard is 20 KB, 400,000 × 20 KB = 8 GB/s ≈ 64 Gbit/s out of one network card. Adding 20 shards changes neither number. Facebook saw the same skew: a single key can account for 20% of a memcached server’s requests.

Hot keys hurt writes too: a live poll counting 300,000 votes a second on one counter serialises on one key and, in Redis, one thread.

Finding hot keys

A hot key shows up as a lopsided cluster: one shard at 100% CPU or line-rate network while its siblings idle, and p99 up only for keys on that shard. Then you need the key’s name:

• Ask Redis. redis-cli --hotkeys samples the keyspace with SCAN and lists the most accessed keys, but only when maxmemory-policy is an LFU policy, because only those keep a per-key access counter. OBJECT FREQ key returns that counter; it is logarithmic and decays, so read it as a ranking, not a rate (cache eviction policies). Scanning costs CPU, so prefer a replica.
• Count in the client or proxy. Sample 1 request in 100 and keep a running top-k with a count-min sketch and a small heap: fixed memory, per-key rates in your metrics.
• Know them in advance. The 7:30 pm match, the noon sale, the creator who posts every evening: register them so the mitigations are on before the spike.

Cooling a hot key

Every fix either sends fewer requests to the owning node or gives the key more than one owner.

An in-process L1 cache. Each app server keeps the value in memory for a second or two. With 200 pods and a 1-second TTL, Redis sees about 200 reads/s instead of 400,000, provided each pod refills with one call (single-flight, below). You gain the biggest reduction for the least work; you pay with up to one TTL of staleness, pods that disagree for that long, and memory in every process.

Split the key into copies. Store the value under N keys, score:match42#0 to score:match42#7, on different shards. Reads pick a suffix at random; writes update or delete all N. Choose N from the arithmetic: 400,000 ÷ (100,000 × 0.5 headroom) = 8 copies of about 50,000 reads/s each. In Redis Cluster, check with CLUSTER KEYSLOT that copies land on different primaries, and avoid hash tags, which pin keys to one slot. You pay N times the writes and memory, and copies briefly disagree if one write fails. Facebook replicates a category of keys within a memcache pool when the whole set fits on one or two servers but draws far more requests than one can serve.

Read replicas. Let the hot shard’s replicas serve reads (READONLY): no code, but capped at its replica count, and replicas lag.

Collapse at a CDN. Serve the value over HTTP with a 1-second max-age. The CDN merges concurrent misses for one object into one origin fetch (Fastly’s request collapsing is on by default), so origin load grows with edge locations, not viewers (content delivery network).

Precompute and push. Build the scorecard once per ball and push it over a real-time connection, so nobody polls at all.

Hot write keys

Copies don’t help a counter, because every write must reach every copy. Two patterns do:

• Sharded counters. Keep 16 sub-counters, votes:poll7:0 to votes:poll7:15; each vote increments a random one, and readers MGET all 16 and add them (or a job writes the total every second). At 300,000 votes/s that is about 19,000 per sub-counter, for reads that cost 16 times more or lag a second.
• Batch in the app. Each pod sums votes in memory and flushes one INCRBY every 100 ms: with 200 pods, 200 × 10 = 2,000 writes/s however fast people vote. The total lags 100 ms, and a crashed pod loses up to 100 ms of votes. It is write-behind in miniature (caching strategies, scaling writes).

Cache stampede: one expiry, thousands of misses

A stampede (thundering herd, dog-piling) starts when a popular key disappears: every request that arrives before someone puts it back misses and runs the same expensive query.

How many? Request rate × time until the value is back. A key read 20,000 times a second with a 200 ms recompute gets 20,000 × 0.2 = 4,000 identical database queries per expiry. The XFetch paper by Vattani, Chierichetti and Lowenstein adds the vicious circle: concurrent queries slow the database, which lengthens the recompute, which lets more requests miss. Slow that query to 1 s and 20,000 requests pile in.

Expiry is only one trigger. A hot key also vanishes when a write deletes it (cache-aside does so on every update), when it is evicted, and when a restart, new cluster or key-format change empties everything at once.

Stopping the herd

The fixes come in three families: let only one caller recompute, keep serving the old value while it does, and refresh before the key ever expires.

One caller recomputes: a lock

On a miss, try to take a short lock in the cache. SET score:match42:lock <token> NX PX 5000 succeeds for exactly one caller (NX: only if absent; PX: expire after 5,000 ms). The winner recomputes and fills; losers wait briefly and re-read, or return a stale copy. Release with a script that deletes the lock only if it still holds your token, so a slow winner can’t delete someone else’s lock.

You gain one query per expiry across the fleet instead of 4,000. You pay an extra round trip per miss and a lock TTL to tune, and the XFetch paper notes a fault-tolerance gap: if the winner dies, nobody refills until the lock expires. Redis’s docs steer strict mutual exclusion to Redlock, but this lock is only an optimisation, so a rare double recompute is harmless (see distributed locking).

A lock combined with a soft expiry, so losers get the old value instead of waiting:

import json, time, uuid

SOFT_TTL, HARD_TTL = 60, 600     # refresh after 1 min; never serve older than 10 min
RELEASE = """
if redis.call('GET', KEYS[1]) == ARGV[1] then return redis.call('DEL', KEYS[1]) end
return 0
"""

def get_scorecard(match_id, attempts=3):
    key, lock = f"score:{match_id}", f"score:{match_id}:lock"
    raw = r.get(key)
    entry = json.loads(raw) if raw else None
    if entry and time.time() < entry["fresh_until"]:
        return entry["value"]                              # fresh hit
    token = uuid.uuid4().hex
    if r.set(lock, token, nx=True, px=5_000):              # one winner per key
        try:
            value = db.load_scorecard(match_id)
            entry = {"value": value, "fresh_until": time.time() + SOFT_TTL}
            r.set(key, json.dumps(entry), ex=HARD_TTL)
            return value
        finally:
            r.eval(RELEASE, 1, lock, token)                # delete only our own lock
    if entry:
        return entry["value"]                              # stale, but instant
    if attempts > 0:
        time.sleep(0.05)                                   # cold miss: let the winner fill
        return get_scorecard(match_id, attempts - 1)
    return db.load_scorecard(match_id)                     # give up waiting; don't fill

One caller per process: single-flight

Single-flight does this inside one process. Go’s singleflight.Group.Do keeps one execution in flight per key; duplicate callers wait and share its result. Instagram caches a promise of the value on a miss, so concurrent requests find the promise and wait on one backend request; they built it for turning up clusters whose caches start empty.

You gain no network calls and no lock to expire. But it works per process, so 200 pods still send up to 200 queries per expiry, and every waiter shares the leader’s fate: one slow call stalls them all, one error fails them all, so add a timeout. Pair it with a lock or lease. CDNs do the same as request collapsing; Fastly notes that an uncacheable origin response sends the queued requests on one after another, so let such URLs skip the queue.

Keep serving the old value

Store a soft expiry, after which the value should be refreshed, and a hard one, after which it must not be served. In between, return the old value and let the lock holder refresh it, as the code above does: nobody waits, and the database sees one query.

HTTP standardised this in RFC 5861. Cache-Control: max-age=600, stale-while-revalidate=30 means fresh for 600 seconds, then servable stale for 30 more while the cache revalidates in the background; stale-if-error=1200 allows a stale copy for 20 minutes if the origin answers 500, 502, 503 or 504. Facebook’s memcache keeps a deleted value briefly and can return it marked stale, so applications that tolerate slightly old data don’t wait.

You pay in staleness, bounded by the window. Gaps remain: revalidation starts only if a request arrives inside the window, and a key that is missing altogether has no stale copy to serve.

Refresh before expiry: XFetch

Probabilistic early expiration lets each request decide at random to refresh a little early, with odds rising as expiry approaches. The XFetch rule from the VLDB 2015 paper fits on one line. Store with each value how long it took to compute (Δ) and when it expires; on every read, recompute if

now − Δ × β × ln(rand()) ≥ expiry

where rand() is uniform between 0 and 1, so −ln(rand()) is positive, usually below 1 and occasionally much larger. β defaults to 1; raise it to refresh earlier. The paper proves this exponential gap optimal, with no tuning for the request rate.

Rearranged, a request with r seconds left refreshes with probability e^(−r ÷ (Δ × β)). For our key (Δ = 0.2 s, β = 1) that is 0.7% with one second left: tiny. But 20,000 requests a second roll the dice, so the first refresh typically starts when 20,000 × 0.2 × e^(−r ÷ 0.2) reaches 1, at r = 0.2 × ln 4,000 ≈ 1.7 seconds before expiry. During its 0.2 s run, on average e − 1 ≈ 1.7 more requests also win the draw: about 2.7 recomputes instead of 4,000, and nobody sees a miss. With β = 2 the refresh comes about 3.6 seconds early and the average falls to about 1.65.

On a real Goodreads cache item with a 10-second recompute, most stampedes had size 1 or 2 and none exceeded 8; the uniform early expiration in Perl’s CHI library averaged close to 10.

import math, random, time

def xfetch(key, recompute, ttl, beta=1.0):
    entry = cache.get(key)                       # {"value", "delta", "expiry"} or None
    now = time.time()
    gap = -entry["delta"] * beta * math.log(1.0 - random.random()) if entry else 0
    if entry is None or now + gap >= entry["expiry"]:
        start = time.time()
        value = recompute()
        delta = time.time() - start              # how long a refill takes
        cache.set(key, {"value": value, "delta": delta, "expiry": time.time() + ttl}, ex=ttl)
        return value
    return entry["value"]

You pay with slightly earlier refreshes (1.7 seconds of a 60-second TTL is about 3% more recomputes) and two extra fields per value. A key nobody reads near expiry still expires and misses; that is what the lock is for.

Leases, refresh-ahead jobs and jitter

Leases build the lock into the cache server. Facebook’s memcached issues a lease token on a miss at most once every 10 seconds per key and tells other clients to wait briefly and retry; for herd-prone keys, peak database queries fell from 17K/s to 1.3K/s. Leases also stop stale sets, so they live in caching strategies.

A refresh-ahead job rewrites a short list of known hot keys (live matches, a sale’s top 500 SKUs) every second, so reads never miss; the cost is a daemon to run and refreshes nobody asked for.

TTL jitter does nothing for one hot key, but stops thousands of keys expiring together: the avalanche, below.

Avalanche and penetration

Interviewers use three names here; define them precisely. A stampede (also called cache breakdown) is one hot key going missing; an avalanche is many keys, or the cache itself, going missing at once; penetration is traffic for keys that exist nowhere, which the cache can never answer.

Cache avalanche

Keys loaded together expire together. Warm 2 million catalogue keys over 5 minutes at 9:00 with a one-hour TTL and they all expire between 10:00 and 10:05: 2,000,000 ÷ 300 s ≈ 6,667 extra misses/s, echoing every hour as the refill sets the same TTL again.

Jitter breaks the synchrony; AWS’s best-practices guide suggests ttl = 3600 + rand() × 120. With ±10% (54 to 66 minutes), the same 2 million expiries spread over 17 minutes and peak at 2,000,000 ÷ 720 s ≈ 2,778/s: the same misses, a 2.4 times lower peak.

Losing the cache itself is the bigger avalanche: see replicas, gutter pools and warm-up in distributed caching, and cap fallback queries with load shedding or a circuit breaker so pages degrade instead of the database toppling.

Cache penetration

Here the data doesn’t exist, so there is nothing to cache. A scraper walking never-issued product IDs or a bot probing random user IDs misses every time: 5,000 such requests a second are 5,000 pointless queries.

• Validate first. Reject IDs of the wrong format or outside the issued range.
• Cache the absence. Store a “not found” sentinel for 30 to 60 seconds so repeats are absorbed; Amazon’s Builders’ Library reports incidents where not caching negative responses raised failure rates. Delete the sentinel when the item is created, or a new product shows “not found” for a minute.
• Put a Bloom filter of real IDs in front. Random IDs never repeat, so only a filter stops them. At a 1% false-positive rate it needs about 9.6 bits per ID (12 MB for 10 million products) and lets about 50 of the 5,000 requests a second through. Add new IDs before the item becomes readable (Bloom filters).
• Rate-limit clients whose requests mostly miss (rate limiting).

Invalidation at scale, in a hurry

“There are only two hard things in Computer Science: cache invalidation and naming things,” runs the line Martin Fowler attributes to Phil Karlton. For one key in one cache the hard part is ordering, covered in caching strategies: commit then delete, close the stale-set race with leases or versions, make the delete durable with an outbox or CDC, keep a TTL. The other hard part is reaching every copy fast.

Change one price and stale copies sit in 200 pods’ L1 caches, Redis in three regions, CDN edges, derived entries such as the category page, and perhaps a negative entry. Two ideas tame this: one event per change that every layer reacts to, and names for groups so one operation clears a group.

One event, many consumers

A CDC reader or transactional outbox publishes “product 42 changed” to a topic that every layer subscribes to (publish/subscribe). A consumer per region deletes the Redis key and its tag members, reading that region’s own database log (distributed caching); a broadcaster tells pods to drop their L1 copy; a purger calls the CDN; derived views rebuild. Events replay and deletes are idempotent, so a lagging consumer catches up rather than losing invalidations. The lag is typically seconds, so the writer still deletes its own Redis key directly to show users their change.

Near caches: broadcast, or keep the TTL short

L1 copies are the hardest to reach because there are so many. For constantly changing data, skip messages and rely on a 1–5 second TTL. Otherwise broadcast: Redis client-side caching has a broadcasting mode (CLIENT TRACKING on BCAST PREFIX product:) that sends subscribed clients the names of changed keys under a prefix, or each pod consumes the invalidation topic. Watch the volume: 2,000 writes/s × 200 pods = 400,000 messages/s, so batch and use narrow prefixes. A pod that loses its invalidation channel can’t know what changed; Redis’s docs say to flush the local cache then.

Tags: everything that shows the item

A tag names “every cached thing that depends on X”. CDNs support it natively: with Fastly, the origin sends Surrogate-Key: product-42 category-phones, the CDN maps keys to objects many-to-many, and one purge of product-42 removes every page carrying it. A soft purge marks them stale instead, so the edge can serve the old page while it refetches: invalidation without an origin stampede.

In your own cache, keep a Redis set per tag (SADD tag:product:42 page:category:phones) and on a change delete its members. You pay in bookkeeping: tag sets need TTLs, an entry cached just after you read the set escapes until its TTL, and in Redis Cluster members sit on many shards, so one invalidation is many round trips.

Versioned keys and namespace bumps

Sometimes the cheapest invalidation is to stop reading old keys. Version in the key: product:42:v17 changes whenever the row does, and old entries are never read again; LRU evicts them eventually. Basecamp’s key-based cache expiration works this way. Readers must know the current version, and garbage lingers until eviction.

Namespace bump: keep a counter, ns:catalog = 41, and build every key in the group from it, catalog:41:product:42. One INCR ns:catalog invalidates millions of keys in O(1). The memcached wiki’s recipe: one extra lookup per read (cache the counter in L1 for a second), initialise it with add to a value that won’t repeat, such as a Unix timestamp, and let orphaned keys age out. Use it for a bulk re-import, a permission change or a new serialisation format.

TTL or explicit invalidation?

Every key keeps a TTL; the question is whether you also invalidate explicitly. Decide by how often the data changes and how stale a reader may see it.

Going deeper: how the fixes fail

• The lock holder dies, and everyone waits out the lock TTL. Set it to two or three times the p99 recompute, and serve stale meanwhile.
• Stale-while-revalidate hides outages: if refreshes keep failing, users see ever-older data with no error. Alert on the age of what you serve.
• Invalidation storms. Deleting a hot key on every write turns 50 writes a second into 50 stampedes a second. Update such keys in place with a version check, debounce deletes, or use leases.
• Negative caches lie if you cache a database timeout as “not found”. Cache only genuine not-found answers, briefly.
• Hot keys move, so detection must run continuously, not once after an incident.

Cheat sheet

How to say it in the interview

“Sharding spreads keys, not requests, so a score key at 400,000 reads a second sits on one Redis node. I’d give each pod a one-second in-process copy, capping Redis at about one read per pod per second, and split the Redis key into eight copies. Next, stampedes: 20,000 reads a second times a 200 ms recompute is 4,000 identical queries. So clients use single-flight, the refill takes a short Redis lock, everyone else gets the stale value, and hot keys refresh early with XFetch. TTLs are jittered. For changes, CDC publishes one event per write, which deletes the Redis key, broadcasts to pods and purges the CDN by surrogate key.”

How would you find a hot key in production? One shard saturated while the others idle is the symptom. Name the key with redis-cli --hotkeys under an LFU policy, or with sampled top-k counts from clients or a proxy, and register predictable ones (a match, a sale) in advance.

Lock or single-flight? Both. Single-flight is free but per process, so 200 pods still send 200 queries; the lock makes it one fleet-wide, for a round trip and a lock TTL. Serve stale to the losers so nobody waits.

How do you invalidate a product shown on 300 cached pages? Tag each page with the product’s key, as a Redis tag set or a CDN surrogate key, and purge by tag when the CDC event arrives. Soft-purge at the CDN so the edge refetches without an origin stampede.

Why not just set short TTLs everywhere? Short TTLs cut staleness but multiply misses and stampedes, and still lose to delete-on-write for freshness after a change. Use them for constantly changing data; elsewhere invalidate explicitly and keep a long TTL as the backstop.

Where to go next

• Caching strategies: delete-after-commit, stale sets, leases, CDC.
• Distributed caching: shards, replicas, gutter pools, regions.
• Caching 101: hit ratios, choosing TTLs and cold starts.
• Cache eviction policies: the LFU counters behind --hotkeys.
• Content delivery network: edge caching, collapsing and purging.
• Bloom filters: sizing the filter that stops penetration.
• Change data capture: the event stream behind fan-out.
• Design a flash sale: hot keys and stampedes at 12:00 sharp.

References and further reading

1. Optimal Probabilistic Cache Stampede Prevention (Vattani, Chierichetti and Lowenstein, VLDB 2015)vldb.orgThe XFetch rule, why an exponential early-expiration gap is optimal, β defaulting to 1, the costs of locking, and the Goodreads experiment with a 10-second recompute.
2. Scaling Memcache at Facebook (Nishtala et al., NSDI 2013)usenix.orgLeases against thundering herds (one token per key every 10 seconds, 17K/s to 1.3K/s), stale values, replication within pools, and one key taking 20% of a server’s requests.
3. RFC 5861 — HTTP Cache-Control Extensions for Stale Contentrfc-editor.orgstale-while-revalidate and stale-if-error, their worked examples, and when background revalidation actually happens.
4. Redis CLI documentationredis.ioThe --hotkeys sampling mode and its requirement for an LFU maxmemory-policy.
5. Package singleflight (golang.org/x/sync)pkg.go.devDuplicate call suppression: one execution in flight per key, with duplicate callers waiting for and sharing the result.
6. Thundering Herds & Promises (Instagram Engineering)medium.comCaching a promise instead of a value so concurrent misses wait on one backend request, built for turning up clusters with empty caches.
7. Request collapsing (Fastly documentation)fastly.comHow a CDN merges concurrent misses for one object into a single origin fetch, and how uncacheable responses break the queue.
8. Working with surrogate keys (Fastly documentation)fastly.comTagging cached responses with many-to-many keys so one purge removes every object that carries a key.
9. Caching best practices (AWS)aws.amazon.comThe thundering herd on a popular user’s profile, prewarming new nodes, and adding randomness to TTLs.
10. Memcached wiki: Programming tricksgithub.comNamespace version keys to invalidate a whole group at once, plus soft-timeout and lock recipes against stampeding herds.