Caching Challenges

A cache earns its keep only while two invariants hold: its hit rate stays high (so the origin sees a trickle, not the flood) and the values it returns are still correct. Every named caching problem is a specific way one of those invariants breaks — the miss path suddenly re-exposes the origin, one key distorts the node it lives on, or the cached copy stops matching the truth. Naming them matters because each has a different fix, and the fixes trade against one another.

The diagram below places each failure at the exact point in the client → cache → origin pipeline where it strikes; the rest of the page then traces one of them (penetration) end to end with real numbers.

The catalogue

Numbers 1 and 5 in the older lists — "thundering herd" and "cache stampede (dogpile)" — are the same phenomenon under three names: a hot key expires and a burst of concurrent misses hits the origin with identical queries at the same instant. This page counts it once; its mechanism and the four real fixes (single-flight, lock + serve-stale, probabilistic early expiry, stale-while-revalidate) are traced in Cache Stampede & Invalidation (page 011).

Three of these carry a subtlety worth spelling out before we trace one in full.

Hot key — why the textbook fix is wrong

Naive claim (incorrect): "use consistent hashing to spread a hot key's load across nodes." Consistent hashing maps one key to exactly one node; a single hot key therefore lands entirely on one node no matter how many nodes you add. Consistent hashing spreads keys, not the traffic of one key. What actually works: replicate the value under N suffixed keys (trending#0 … trending#3) and have each client read a random replica, spreading a 4× share across four nodes; and/or put a tiny in-process L1 cache in front of the shared cache so most hot-key reads never leave the app server. To find the offending key before it topples a node, sample the traffic: redis-cli --hotkeys (uses the LFU counters) or your cache proxy's per-key request stats will surface the one key eating a disproportionate share.

Big key — the blocking cost, not just the memory

A 50 MB value is not merely 50 MB of capacity. On Redis a single-threaded command against it — DEL, or serializing it onto the wire — blocks the whole node for the duration, stalling every other key on that shard. Use UNLINK (async free) instead of DEL, and split the value into bounded chunks or move large blobs to object storage with only a pointer in the cache.

Pollution — a scan poisons the working set

The classic trigger is a batch job or crawler that reads millions of keys once. Under plain LRU, each cold key is "most recently used" the moment it lands, so it evicts a genuinely hot key. A frequency-aware policy (LFU, or an admission filter like TinyLFU that refuses to admit a brand-new key over a proven-hot one) resists this; see page 010 for how each policy decides.

Worked example — cache penetration, with real numbers

A product API serves 50,000 rps at a 98% hit rate, so the database sees 50,000 × 2% = 1,000 rps — exactly its comfortable budget. An attacker (or a broken client) now sends 20,000 rps for product IDs that do not exist (id=-1, random 18-digit IDs). The standard handler reads: on miss, query DB; if the row is null, return 404 and cache nothing. Trace what the DB sees:

Legitimate traffic still needs its 1,000 rps, so the DB is asked for ~21,000 rps against a 1,000 rps budget — 20× over, and it falls over, taking real users down with it. The cache did nothing, because you cannot cache the absence of a row you never store.

Fix A — negative caching: cache the null result itself, e.g. SET product:-1 "__MISS__" EX 30. Repeated bad IDs now hit the cache; if the attacker reuses a small set of IDs, DB load collapses to (distinct bad IDs ÷ 30 s). Fix B — bloom filter: keep a bloom filter of all valid product IDs in memory; a lookup that the filter reports as "definitely absent" is rejected before any cache or DB call, so even high-cardinality random IDs cost zero DB queries.

Pitfalls

• Negative caching becomes its own DoS. A long null TTL turns a mistake into a stale 404: if a product is created a second after its ID was probed, users get "not found" until the negative entry expires. Keep null TTLs short (seconds), and delete the negative entry on the create/write path.
• Bloom filters have false positives, never false negatives. A saturated filter (too many inserts for its sizing) will occasionally say "maybe present" for a bad key, letting it through — acceptable, since it only leaks the occasional DB call. But you must resize/rebuild it as the valid-ID set grows, and you cannot delete from a plain bloom filter (use a counting bloom or periodic rebuild).
• Replicating a hot key spreads reads but multiplies the write problem. Now an update must fan out to all N replicas, and until it does, clients reading different replicas see different values — you've traded a load problem for a consistency window.
• The naive stampede lock deadlocks or stalls. If the request holding the rebuild lock crashes without releasing it, every other request blocks until the lock TTL expires. Always give the lock a timeout and let waiters serve stale on lock-acquire failure (page 011).
• "Just raise the TTL" fixes drift into a bigger bug. Longer TTLs cut misses but widen the drift window, so reads stay wrong longer after a write. Correctness and hit rate pull in opposite directions here — decide which the data can tolerate.

Choosing the mitigation — and its cost

The problems are a catalogue; the engineering is picking the right guard for your traffic shape, because each guard buys protection with a specific cost.

Penetration: negative cache vs bloom filter

Signal: misses for keys that resolve to nothing. Low-cardinality abuse (a handful of bad IDs, retried) → negative caching: trivial to add, but it consumes cache space for junk and risks stale 404s. High-cardinality abuse (random IDs, near-infinite distinct values) → bloom filter: O(1) memory in bits per key and rejects before any lookup, but it costs a maintained side-structure, tolerates rare false positives, and is awkward to update. Choose the bloom filter when the bad key space is unbounded; prefer negative caching when the bad keys repeat and simplicity matters.

Hot key: key replication vs client-local L1

Replication spreads a key's reads across N nodes but adds write fan-out and a cross-replica consistency window. A client-local L1 (a small in-process cache) removes the hot-key reads from the network entirely — cheapest for reads — but each app instance can serve a slightly stale copy for its short local TTL. Choose L1 when a few seconds of staleness is fine and you have many app servers; prefer replication when reads must be near-fresh but one node can't carry the volume.

Pollution: LFU/TinyLFU vs plain LRU

LRU is cheap and great for recency-dominated traffic, but a one-pass scan poisons it. LFU / TinyLFU protects a stable working set against scans at the cost of more per-entry bookkeeping and slower adaptation when the working set genuinely shifts. Choose frequency-aware policies when a known hot set coexists with bursty cold scans; stay on LRU when access is dominated by recency and simplicity wins.

Takeaways

• Every caching problem is one invariant breaking — hit rate (stampede, penetration, hot/big key, pollution) or correctness (drift) — and each has a distinct fix.
• Thundering herd, cache stampede, and dogpile are one problem, three names; the deep mechanism and its four fixes live in page 011.
• Consistent hashing does not fix a hot key — one key still pins to one node. Replicate the key or front it with a local L1.
• Guards trade against each other: negative caching risks stale 404s, replication adds write fan-out, longer TTLs widen the drift window. Pick for your traffic shape, not by reflex.

Re-authored and deepened for this guide. Draws on Alex Xu, System Design Interview (Vol. 1–2, cache design and stampede protection); Nishtala et al., Scaling Memcache at Facebook (NSDI 2013) for leases, hot-key replication, and thundering-herd control; the Redis documentation on maxmemory-policy (LRU/LFU), big-key handling, and UNLINK; and Einziger et al., TinyLFU: A Highly Efficient Cache Admission Policy. The stampede/thundering-herd mechanism is treated fully in the companion page "Cache Stampede & Invalidation."