Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 37 ยท Consistency and Failure

Cache Stampede Protection

Simulate a cache stampede when a hot key expires and compare lock-based single flight, stale-while-revalidate and probabilistic early refresh using Memcached add().

Imagine a cached page that takes two seconds of database work to build, and 500 requests per second ask for it. While the key is cached, the database sees nothing. The moment the TTL expires, the next 1,000 requests all miss, all start the same expensive query and all write the same result. The database suddenly receives a burst it was never sized for, slows down, and the slowdown makes the rebuild take longer, so even more requests pile in. This is a cache stampede, also called a thundering herd or dog-pile effect.

This lesson reproduces a stampede in a small simulation and then fixes it with three techniques that work with plain Memcached commands. The simulation uses virtual time and dictionaries, because real servers cannot run in the live editors.

Reproducing the stampede

Time is counted in ticks. A rebuild takes 3 ticks, and 10 requests arrive on every tick. Without protection, every request that arrives while the key is missing starts its own rebuild.

Python Counting duplicate rebuilds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each expiry triggers dozens of duplicate rebuilds instead of one. The first request that finds the key missing should rebuild it while others wait or use something else.

Fix 1: a lock with add (single flight)

Memcached's add command stores a key only if it does not already exist, and does so atomically. That makes it a perfect lock:

  1. On a miss, try add("lock:page", "1", ttl=10).
  2. If the add succeeds, you are the leader: rebuild, set the value, delete the lock.
  3. If the add fails, someone else is rebuilding: wait briefly and retry the cache, or serve a stale copy.

The lock must have a TTL, so that a crashed leader does not block the key forever.

Python Single flight with an add-style lock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Now there is one rebuild per expiry. The cost is that followers wait. Keep the wait short (a few tens of milliseconds, with jitter) and give up after a limit by falling back to a rebuild or an error.

Fix 2: serve stale while one refresher works

Store two things with each value: the value itself with a long physical TTL, and a soft expiry timestamp inside the value. Readers check the soft expiry. If it has passed, one reader wins the lock and refreshes, while everyone else keeps using the slightly old value. Nobody ever waits, which suits pages where a few seconds of age do not matter.

Python
# value stored in memcached
{"data": page_html, "soft_expires": 1735689600}   # physical TTL = soft TTL + grace period

This is the same idea as the HTTP stale-while-revalidate directive you may meet in Multi-Layer Caching and CDNs.

Fix 3: probabilistic early refresh

Locks need an extra round trip and shared state. A statistical alternative lets each reader decide on its own to refresh slightly early, with a probability that rises as the expiry approaches and grows with how expensive the rebuild is. A widely used rule (often called XFetch) is:

TEXT
refresh if  now - delta * beta * ln(random()) >= expiry

where delta is the measured rebuild time and beta (default 1) tunes eagerness. Because ln(random()) is negative, the left side is pushed forward in time by a random amount, so it is rare in the early life of the key, and nearly certain just before expiry. Usually exactly one request refreshes before the key actually dies.

Python When does a reader refresh early?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Far from expiry almost nobody refreshes, and in the last couple of seconds a refresh becomes very likely, so the key is usually renewed before it ever goes missing.

Other measures

  • Jitter TTLs: add a random few percent to every TTL so a thousand keys written together do not all expire together.
  • Warm up after restart: a freshly started cache is empty and invites a stampede on every key. Pre-fill the hottest keys, or bring servers back gradually.
  • Cap concurrency to the database: use a connection pool limit or a queue so even a stampede cannot take the database down.
  • Negative caching: cache "not found" results for a short time, so a missing row does not trigger a rebuild every request.

A lock with no TTL is a bug waiting for a crash. If the leader dies before deleting the lock, the key stays locked, and with add semantics nobody can rebuild it. Always expire locks, and keep their TTL slightly longer than a typical rebuild.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a cache stampede?

    When a hot key expires, all waiting requests miss together and start duplicate expensive work.
  2. 2. Why is Memcached add() useful as a lock?

    Only one concurrent add can succeed, so exactly one request becomes the leader.
  3. 3. What does serving stale while revalidating give you?

    A soft expiry lets most readers keep using the old value while one reader rebuilds.
  4. 4. Why should TTLs have a little random jitter?

    Jitter spreads expirations in time so rebuilds do not arrive in one wave.

Summary

  • A stampede is a burst of duplicate rebuilds after a hot key expires.
  • Use add as a lock with its own TTL so only one request rebuilds.
  • Soft expiry plus a long physical TTL lets readers use stale data while one refreshes.
  • Probabilistic early refresh needs no lock and usually renews a key before it dies.
  • Add TTL jitter, warm new caches and limit database concurrency.

Next: Node Failure and Failover