Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 ยท Strategies and Invalidation

Stampede Protection

Understand cache stampedes (the dogpile effect) and defend against them with add-based locks, stale-while-revalidate soft TTLs and probabilistic early refresh, all simulated in Python.

Picture a very popular page whose cached copy takes two seconds to rebuild. At the instant the key expires, 500 requests per second are asking for it. All of them miss, and all of them start the same expensive rebuild at once. The database receives hundreds of identical heavy queries, slows down, the rebuilds take even longer, and more requests pile up. This is a cache stampede, also called the dogpile effect or thundering herd, and it is one of the most common ways a well-cached site falls over.

This lesson reproduces the problem in a small simulation and then shows three standard defences.

Reproducing a stampede

The simulation below has a page that has just expired. Five requests arrive each tick for ten ticks, and a rebuild takes four ticks to finish. Without protection, every request that misses starts its own rebuild.

Python Naive: everyone 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.

Twenty identical rebuilds for one page. In real life the count grows with traffic and with the rebuild time.

Defence 1: a lock with add

Only one request is allowed to rebuild; the others wait briefly, retry, or serve something else. The lock is a key created with add, as you saw in Storage Commands. It needs a short TTL so a crashed worker does not block everyone forever.

Python With a lock: one rebuild

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.

What the losers do next is a design choice:

  • Wait and retry a few times with a short sleep (tens of milliseconds), then re-read the cache. Simple, but waiting ties up web workers.
  • Serve slightly stale data if you kept it (next defence).
  • Fail fast with a fallback value or an error page for non-critical content.

The lock's TTL must be a little longer than a normal rebuild, and always shorter than you can tolerate a dead worker blocking others.

Defence 2: stale-while-revalidate with a soft TTL

Store two expiry times: a soft TTL (when the data should be refreshed) and a hard TTL (when Memcached discards it), the hard one much longer. After the soft TTL, requests still get the old value instantly, but one request wins a lock and refreshes in the background. Nobody waits and nobody stampedes.

You keep the soft expiry inside the stored value, because Memcached only knows the hard TTL.

Python Soft TTL with one refresher

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.

The trade-off is that users may see data up to (soft TTL + refresh time) old, and the cache needs more memory because items live for the hard TTL. In return, the slow rebuild is always off the critical path for all but the very first request.

Memcached 1.6's meta protocol has this built in: the mg command can return flags telling one client that it "won" the right to recache (W), and others that the value is stale (X) or that someone else is already refreshing (Z). Check whether your client library supports meta commands before writing the logic by hand.

Defence 3: probabilistic early refresh

Instead of coordinating with a lock, make each request randomly decide to refresh slightly before the key expires, with a probability that rises as expiry approaches. With many requests, someone almost always refreshes early, and rarely more than one does. A well-known formula (the "XFetch" algorithm) refreshes when:

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

where delta is how long the rebuild takes and beta (default 1) tunes eagerness. The chance of refreshing when time_left seconds remain is exp(-time_left / (delta * beta)).

Python Refresh probability as expiry nears

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.

With 500 requests per second, the chance that nobody refreshed during the last few seconds before expiry is vanishingly small. For a rarely requested key the probability stays low, which is correct: nobody is waiting on it.

Python Early refresh in practice

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.

The key is rebuilt shortly before each expiry, once every 50 to 60 seconds here, instead of all requests missing together afterwards. (The hard TTL here is longer than the soft expiry so the data does not vanish before the refresh.)

Combining the defences

Technique Strength Cost
TTL jitter (TTL lesson) Spreads many keys' expiries apart Does nothing for one hot key
Lock with add Exactly one rebuild Losers must wait or fall back
Soft TTL + stale serving Nobody waits Extra memory, some staleness
Probabilistic early refresh No coordination at all A few early rebuilds, needs the rebuild time estimate

A strong default for a hot key is soft TTL plus a lock; for large fleets of keys add jitter; and keep the database healthy with connection limits so a stampede that slips through does not take it down.

Two situations need extra care: a cold start (restart, new server, flush) when every key is missing at once, and a very hot key that exists on a single server. Chapter 5 and 6 of this course return to both, with warming strategies and hot-key replication.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is a cache stampede?

    At expiry a popular key causes many simultaneous identical rebuilds that overload the backend.
  2. 2. Which Memcached command is typically used to take the rebuild lock?

    add succeeds only if the key is absent, so exactly one request wins.
  3. 3. Why give the lock key a short TTL?

    If the owner dies before releasing, the lock expires by itself and another worker takes over.
  4. 4. What does stale-while-revalidate do?

    A soft TTL triggers a single refresh while everyone else keeps getting the previous value instantly.
  5. 5. What does TTL jitter protect against?

    Jitter spreads the expiry times of many keys. It does not help a single hot key; use a lock or soft TTL for that.

Summary

  • A stampede happens when a hot key expires and many requests rebuild it at once.
  • Use an add lock with a short TTL so only one request rebuilds; losers wait briefly, serve stale data or use a fallback.
  • Soft TTL plus a long hard TTL serves stale data instantly while one request refreshes.
  • Probabilistic early refresh avoids coordination by refreshing slightly before expiry.
  • Combine with TTL jitter for many keys, and protect the database as the last line of defence.

Next: Consistent Hashing and the Hash Ring