Cachinginvalidationttlstampedethundering herdhot key

Cache Invalidation, Stampedes and Hot Keys

The hard part of caching is knowing when the cached value became wrong; the operational hazards are stampedes when many keys expire together and hot keys when one key gets a disproportionate share of traffic.

▶ InteractiveInterview questionSee how this works internally →
Progress

When the database changes, how does the cache know?

A cache entry is a *derived* value, and the database does not know what was derived from what. So every invalidation strategy is a way of tracking that dependency. TTL only: accept staleness up to the TTL; free, and right for data where "a few minutes old" is fine. Delete on write: the write path deletes the affected keys; correct, but every write site must know every dependent key. Versioned keys: put a version in the key and bump it on write, orphaning old entries instead of hunting them down; the answer to fan-out invalidation. Change data capture: a process tails the database’s WAL and invalidates from the actual committed changes — the only approach that catches *every* write, including manual SQL and other services, at the cost of real infrastructure.

Pick the weakest strategy that meets the actual staleness requirement, and write that requirement down. "This value may be up to 60 seconds stale" is a design decision; discovering it by accident is a bug.

The stampede

A popular key expires. Before the first request can repopulate it, a thousand concurrent requests all miss, and all thousand go to the database for the same row — a stampede (thundering herd). Worse: a deploy that clears the cache, or a TTL set to the same round number everywhere, expires *every* popular key at once, and the database gets the whole read load it had been shielded from, at peak traffic.

Three defences. TTL jitter: add a random offset to each TTL so keys do not expire together — cheap, stateless, turns a spike into a slope. Single-flight lock: the first miss for a key takes a lock and repopulates; concurrent misses wait for it instead of querying — collapses the spike to one query per key. Stale-while-revalidate: serve the expired value for a short grace window while one background request refreshes it — no user waits, the database sees one query, at the price of briefly stale data, which is usually the right price.

Single-flight repopulation
1value = cache.get(key)
2if value is None:
3    if cache.set("lock:" + key, 1, nx=True, ex=5):   # I am the one who refills
4        value = db.query(...)
5        cache.set(key, value, ex=300 + random(0, 60))  # jittered TTL
6        cache.delete("lock:" + key)
7    else:
8        sleep(0.05); value = cache.get(key)          # someone else is refilling; wait

The hot key

Caching spreads load across keys, but one key can be a disproportionate share of all traffic — a celebrity’s profile, the current top post, a global config value. That key lives on one cache node, and its throughput is the whole system’s ceiling; sharding cannot help, because sharding splits *across* keys and this is *one* key. The fixes replicate the key: a small in-process (L1) cache in front of the shared (L2) cache so most reads never leave the app server; or several copies of the value under different names, read at random. The same value, deliberately duplicated, because the problem is concentration.

Key points

  • Invalidation tracks a derived value’s dependency: by time (TTL), by code (delete on write), by key (versioning), or by log (CDC).
  • Pick the weakest strategy that meets the staleness requirement, and state the requirement.
  • Stampede: many misses for one key, or all keys expiring together. Fix with jitter, single-flight, or stale-while-revalidate.
  • Hot key: one key is most of the traffic. Sharding cannot split it; replicate it (L1 cache or multiple copies).

Hit rate, stampede, hot key

Hit rate, stampede, hot key
6,000 requests over 60 ticks against 200 keys with a skewed popularity. Watch the database load per tick — the spike is a cache stampede.
Database queries per tick
peak 71 / tick
Hit rate
93.5%
DB queries
392
Peak per tick
71
Hottest key
12% of traffic
Cache hit rate93%
Stampede. At t=20 every key expired at once and 71 requests missed in the same tick — all of them went to the database for the same handful of rows. This is what a deploy that clears the cache, or a TTL set to the same round number everywhere, does to a database at peak traffic.
Stampede protection

How does the cache know?

When the database changes, how does the cache know?
The question that decides whether a cache is a performance feature or a correctness bug. Four answers, in increasing order of effort and reach.
TTL only

Set an expiry and accept staleness up to that long.

SET product:12 {...} EX 300
Consistency
Bounded staleness = TTL
Cost
Free
Use when: Data where "a few minutes old" is fine: product catalogue, config, anything you would happily serve from a CDN.
The two hard things: cache invalidation is hard because a cache entry is a derived value and the database does not know what derived from what. Every approach above is a way of tracking that dependency — by time, by code, by key naming, or by tailing the log. Pick the weakest one that meets the actual staleness requirement, and write that requirement down.
1/4 · TTL only

When to use — and when not

Use it when
  • Any cache under real traffic — the hazards are not optional to plan for.
Avoid it when
  • Over-engineering invalidation for data a plain TTL handles fine.

Failure modes

  • A deploy clearing the cache and stampeding the database at peak.
  • Uniform TTLs expiring together.
  • A hot key saturating one node while the rest idle.
  • No documented staleness bound, so nobody knows if a stale read is a bug.

See how this works internally →

Descend one layer: the same topic explained from the machinery up.

Eviction inside the engine: buffer replacement
↓ Database Internals → Buffer Replacement: LRU, Clock and Scan Resistance
← Caching Patterns