Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Caching

System Design HLD-05.05

Thundering herd, cache stampede and hot keys

When a popular key expires, thousands of requests hit the database at once. Coalescing, early refresh, TTL jitter and hot-key replication stop it.

Advanced 12 min Last reviewed

The big idea

A cache protects the database only while it has the data. Picture the home page's "trending" list, cached for 60 seconds and read 10,000 times per second. At second 60 the entry expires. The next request misses and starts recomputing it, which takes 200 ms. During those 200 ms, another 2,000 requests arrive, all miss, and all start the same expensive recomputation. The database, sized for a trickle of misses, suddenly gets thousands of identical heavy queries. It slows down, recomputation takes longer, more requests pile in, and the site falls over at exactly the moment it was busiest.

This is a cache stampedeMany requests missing the cache for the same key at once and all hitting the backing store to recompute it, overloading it., also called a dog-pile or thundering herd. The same thing happens after a deploy or cache restart when thousands of keys are all cold at once, or when many keys were cached at the same moment and expire together. A related problem is the hot keyA single key so popular that the one cache node holding it becomes overloaded, even though the cluster as a whole has spare capacity.: one key so popular that the single cache node holding it is overwhelmed.

Think of a shop that runs out of a bestseller. If every customer who finds the shelf empty phones the publisher separately, the publisher's line jams. One assistant should phone once while everyone else waits a moment.

How it works

Step 1: Coalescing (single flight)

A stampede versus coalesced requests Left: when a hot key expires, hundreds of requests all miss and send the same query to the database, which is overloaded and shown in red. Right: with request coalescing, the first request recomputes the value while the others wait for its result, so the database sees a single query. No protection Coalesced (single flight) requests x 2,000 cache: miss Database 2,000 queries requests x 2,000 1 leader, rest wait Database 1 query Figure 1. Left, every request that misses recomputes the value: hundreds of identical queries hit the database (red). Right, with coalescing one request recomputes and the rest wait for its answer: one query.

When a key misses, the first request takes a short-lived lock or registers itself as the one computing that key; every other request for the same key waits for that result instead of querying the database. Inside one server this is an in-memory map of in-flight requests (Go's singleflight package is the classic example). Across many servers it is a lock in the cache itself, or the lease mechanism from Cache invalidation and consistency , where only one requester gets a token and the rest briefly retry. Waiting requests can also be served the expired value while the new one is computed.

Step 2: Refresh before expiry

Rather than letting a hot key expire at all, refresh it early. A background job can recompute known hot keys on a schedule. Or each read can decide, with a probability that rises as expiry approaches, to recompute the value early while still serving the cached one (probabilistic early expiration). Either way, readers almost never see a miss for popular keys.

Step 3: Jitter the TTLs

If a deploy or batch job caches 100,000 keys in the same minute with the same 1-hour TTL, they all expire in the same minute an hour later. Add random jitterA small random variation added to a timer, such as plus or minus 10 percent on a TTL, so that many timers do not fire at the same moment. to each TTL, for example plus or minus 10 to 25 percent, and the expiries spread out. The same trick spreads out retries ( Timeouts, retries, backoff and jitter ).

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. One very hot key, everything off: thousands of queries per second for the length of the recompute, far over capacity.
  2. Turn on request coalescing: a single query. Turn it off and turn on early refresh instead: also a single query, and nobody even sees a miss.
  3. Switch to 400 keys cached at the same moment with coalescing on: still one tall spike, because every key expires in the same instant. Turn on TTL jitter: the spike spreads into a low, safe wave.

Step 4: Hot keys

Coalescing fixes expiry, but a key read 500,000 times per second can overload the single cache node that owns it even when it never expires. Fixes:

  • Local caches: keep the hottest keys in each application server's memory for a few seconds, so most reads never reach the shared cache.
  • Replicate hot keys: store copies under several keys (trending#1 to trending#8) on different nodes and read a random copy.
  • Detect and adapt: track key access frequency and automatically promote very hot keys to local caching.

Going deeper

Protect the database regardless

All of these reduce the chance of a stampede; none guarantees the database is safe. Systems also cap concurrent queries at the database layer, shed load when it is saturated, and serve stale data rather than nothing during an incident. Those patterns, from bulkheads to load shedding, are in Load shedding and graceful degradation .

Trade-offs

OptionWins whenLoses when
Request coalescing Any expensive key with many concurrent readers Simplicity; waiting requests share the leader's latency and failures
Early or background refresh Known hot keys: no misses at all Work spent refreshing keys that may not be read
TTL jitter Many keys written together, after deploys or batch loads Predictable expiry times
Local in-process caching of hot keys Extremely hot keys that overload one cache node Freshness across servers and memory per server

Common mistakes

  • Identical TTLs on keys written in bulk, guaranteeing a synchronized mass expiry.
  • Restarting or flushing the whole cache during peak traffic.
  • Coalescing inside each server only, then running 200 servers, which still send 200 queries per expiry.
  • Assuming the cluster has capacity when one node holds a key that receives a large share of all traffic.

Check yourself

  1. A key read 5,000 times per second expires and takes 400 ms to recompute. Without protection, roughly how many requests hit the database?

    Show answer

    C. About 2,000 All requests during the 400 ms recompute miss: 5,000 x 0.4 = 2,000.

  2. What does request coalescing do?

    Show answer

    B. Lets one request recompute a missing key while others wait for its result Only one database query per key per expiry, however many requests arrive.

  3. Why add jitter to TTLs?

    Show answer

    B. So keys written together do not all expire at the same moment Random variation spreads expiries out instead of synchronizing them.

  4. One key gets 40 percent of all reads and its cache node is at 100 percent CPU while others idle. What helps most?

    Show answer

    B. Caching the key locally in app servers or replicating it across nodes The problem is one node's load; spreading or localizing that key's reads fixes it.

Recap

  • A stampede is many simultaneous misses for the same key recomputing it at once.
  • Coalescing lets one request recompute while the rest wait.
  • Refreshing hot keys before they expire avoids the miss entirely.
  • Jittered TTLs stop keys written together from expiring together.
  • Very hot keys need local caching or replication across cache nodes.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up