Pointer Walk

Cache Stampede

One popular key expires and every request rebuilds it at once. Why it happens and three ways to stop it.

System DesignIntermediate8 min read

One key expires

A popular page is slow to build: it needs a heavy database query. So the result is kept in a cache, and every request reads the cached copy. The database is barely touched.

A cached value does not stay forever. It has an expiry time, after which it is thrown away so that it cannot get too far out of date. The next request finds nothing, runs the query, and fills the cache again.

That works when one request arrives at a time. Now picture a busy site.

  1. The cached value expires

    Nothing is wrong yet. This is what an expiry time is for.

  2. Many requests arrive before it is rebuilt

    Rebuilding takes a moment. During that moment every request finds the cache empty.

  3. Each one runs the same slow query

    None of them knows the others are doing the same thing. The database goes from no work to dozens of copies of its heaviest query.

  4. The database slows down, so the rebuild takes longer

    The longer it takes, the more requests arrive and pile on. The problem feeds itself.

This is a cache stampede. It is also called a thundering herd or dog-piling.

Watch it happen

Three requests arrive every tick. The database can run 4 queries at full speed. The cached value expires every 14 ticks.

No protectionInteractive

Requests

3 per tick

Cache: homepage

fresh for 6

Database

0 running · handles 4

Database queries running, tick by tick

database handles 4

The rule: Every request that misses runs its own database query. The cached value expires every 14 ticks.

Requests
0
Database queries
0
Most at once
0
Made to wait
0

Look at the numbers when it finishes. Only one query was needed each time the value expired. Everything above that was the same answer, computed again and again.

Fix 1: one rebuilds, the rest wait

The cheapest fix is to make sure only one request does the work.

  1. The first request to miss takes a lock

    A lock is a marker that says "someone is already rebuilding this".

  2. It runs the query and fills the cache

    One query, at full speed.

  3. Everyone else waits, then reads the cache

    A request that finds the lock taken does not go to the database. It waits a moment and reads the fresh value.

One rebuilds, the rest waitInteractive

Requests

3 per tick

Cache: homepage

fresh for 6

Database

0 running · handles 4

Database queries running, tick by tick

database handles 4

The rule: The first request to miss rebuilds the value. The others wait for it. The cached value expires every 14 ticks.

Requests
0
Database queries
0
Most at once
0
Made to wait
0
python
def get_homepage():
    page = cache.get("homepage")
    if page is not None:
        return page

    if cache.add("lock:homepage", "1", ttl=10):   # only one caller succeeds
        page = build_homepage()                    # the slow query
        cache.set("homepage", page, ttl=300)
        cache.delete("lock:homepage")
        return page

    time.sleep(0.05)                               # someone else is building it
    return get_homepage()

The lock has its own short expiry time. If the request holding it crashes, the lock disappears by itself and someone else can try.

Good at

  • The database runs one query instead of dozens
  • Simple to add around an existing cache

Where it bites

  • Requests that arrive during the rebuild still have to wait for it

Fix 2: serve the old value while rebuilding

Why make anyone wait? The old value is a few seconds out of date. For most pages that is fine.

Keep the expired value, hand it out, and rebuild in the background. The first request to notice the expiry starts one rebuild. Every request, including that one, gets the old value at once. When the rebuild finishes, the new value replaces it. This is often called stale-while-revalidate.

Serve stale, rebuild behindInteractive

Requests

3 per tick

Cache: homepage

fresh for 6

Database

0 running · handles 4

Database queries running, tick by tick

database handles 4

The rule: Requests keep getting the old value while one rebuild runs in the background. The cached value expires every 14 ticks.

Requests
0
Database queries
0
Most at once
0
Made to wait
0

A close relative is early refresh: rebuild a little before the expiry time, so the value never actually runs out.

Good at

  • Nobody waits, and the database runs one query
  • The site stays up even if the rebuild is slow or fails

Where it bites

  • Readers get a slightly old value during the rebuild
  • Needs a cache that can keep a value past its expiry time

Fix 3: do not let keys expire together

A stampede does not need one hot key. It also happens when many keys expire at the same moment. A common cause: the site restarts, fills its cache within a few seconds, and gives everything the same expiry time. Five minutes later all of it expires at once.

Add a little randomness to every expiry time. This is called jitter.

Example

Spreading out the expiry

Instead of 300 seconds for every key, use 300 plus a random number from 0 to 60. A thousand keys that were cached in the same second now expire across a whole minute, about 17 per second instead of 1,000 at once.

python
import random

cache.set(key, value, ttl=300 + random.randint(0, 60))

Compare them yourself

No protectionInteractive
On a miss

Requests

3 per tick

Cache: homepage

fresh for 6

Database

0 running · handles 4

Database queries running, tick by tick

database handles 4

The rule: Every request that misses runs its own database query. The cached value expires every 14 ticks.

Requests
0
Database queries
0
Most at once
0
Made to wait
0
FixDatabase queries per expiryDo requests wait?Use it when
NothingOne per request that missesYes, and longer as load growsNever, for a busy key
One rebuilds, the rest wait1Yes, for one rebuildThe value must never be stale
Serve stale, rebuild behind1NoA slightly old value is acceptable
Jitter on expiry timesSpread out over timeNoAlways, for every key

The fixes combine. A common setup is jitter on every key, plus serve-stale for the handful of keys that are both popular and slow to build.

Key takeaways

  • A stampede happens when a popular cached value expires and many requests rebuild it at the same time.
  • It feeds itself: more queries make each query slower, which leaves the cache empty for longer.
  • A lock lets one request rebuild while the others wait.
  • Serving the old value during the rebuild means nobody waits at all.
  • Random jitter on expiry times stops many keys from expiring together.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress