When caches go wrong

A cache that's working quietly changes your system's shape. After a few months at a 95% hit ratio, Tiffin's database is sized for 5% of the real menu load. Nobody decided that; it just happened, because nobody needed a bigger database.

That's fine, until the cache stops doing its job for a few seconds. Then the database gets 20 times its usual load at once. This lesson is about the ways that happens: stampedes, hot keys, lookups for things that don't exist, and the cache going down entirely. Each one has a name, a typical cause, and a standard fix.

Stampedes: everyone misses at once

At 8:00pm, menu:v1:42 expires. Restaurant 42 is popular: its menu is requested 300 times a second.

In the 25 ms it takes the first request to load the menu from the database, about 8 more requests arrive. They all miss too, and they all run the same 25 ms query. If the database is already busy, that query takes longer, say 200 ms, and now 60 requests are piling on the same query. Their load slows the database further, so the next query takes even longer.

This is a cache stampede (also called a thundering herd, or dog-piling). Lots of requests miss the same key at the same moment and all rush to the database to rebuild it.

%% caption: A stampede feeds itself. The slower the rebuild, the more requests join it.
flowchart TD
  K["Key expires"] --> MS["300 requests per second miss"] --> D[("Database<br/>same query x 60")]:::hot
  D --> SL["Slower"] --> W["More requests waiting"] --> D

One key causing this is a bad few seconds. Many keys expiring together (for example, everything cached at 6pm with the same 2-hour TTL, all expiring at 8pm) can take a database down.

Fix 1: Only one request rebuilds

The idea: the first request to miss takes a short lock and rebuilds the value. Everyone else waits briefly, or gets the old value, instead of hitting the database.

async function getMenu(id, tries = 0) {
  const key = `menu:v1:${id}`
  const cached = await redis.get(key)
  if (cached !== null) return JSON.parse(cached)

  // Only one request across all servers wins this lock (NX = only if not exists).
  // The random token marks the lock as ours.
  const token = crypto.randomUUID()
  const gotLock = await redis.set(`lock:${key}`, token, { NX: true, EX: 5 })
  if (gotLock) {
    try {
      const menu = await loadMenuFromDb(id)
      await redis.set(key, JSON.stringify(menu), { EX: 600 })
      return menu
    } finally {
      await releaseLock(`lock:${key}`, token)
    }
  }

  // Someone else is rebuilding. Wait a moment and try the cache again,
  // but after about a second, stop waiting and read the database.
  if (tries >= 20) return loadMenuFromDb(id)
  await sleep(50)
  return getMenu(id, tries + 1)
}

// Delete the lock only if it still holds our token. It's a tiny Lua script because
// "check, then delete" has to happen in one step inside Redis.
function releaseLock(lockKey, token) {
  return redis.eval(
    "if redis.call('GET', KEYS[1]) == ARGV[1] then return redis.call('DEL', KEYS[1]) end return 0",
    { keys: [lockKey], arguments: [token] },
  )
}

The lock expires after 5 seconds on its own, so a crashed rebuilder can't block everyone forever. Two details keep it safe. The token stops a slow rebuilder from deleting a lock that has already expired and been taken by the next request. And the retry limit means a stuck rebuild can't keep other requests waiting. Inside one server, the same idea is often done with a shared in-memory promise, called request coalescing or single-flight: concurrent requests for the same key all await the one database call.

Fix 2: Serve stale while refreshing

Better still, don't let popular keys disappear at all. Store the value with a "soft" expiry inside it, and a longer real TTL:

{ "menu": { ... }, "refresh_after": "2026-10-18T20:00:00Z" }

When a request sees the soft expiry has passed, it still returns the cached menu immediately, and triggers one background refresh (protected by the lock above). Customers never wait for a rebuild, and the database sees one query. This is the same idea as the HTTP header stale-while-revalidate. The cost is that data can be slightly older than the soft TTL; for a menu that's also invalidated on change, that's fine.

Fix 3: Add jitter to TTLs

To stop many keys expiring at the same moment, don't give them identical TTLs. Add a little randomness:

const ttl = 600 + Math.floor(Math.random() * 120)   // 10 to 12 minutes

Now keys cached together expire spread over two minutes instead of in the same second. This mass-expiry problem is sometimes called a cache avalanche, and jitter is the cheap, standard fix.

Fix 4: Refresh ahead of expiry

Cache-aside refreshes a key only after it's gone: the first request after expiry misses and waits for the database. Fix 2 softens that by serving the old value while one request refreshes. Refresh-ahead goes one step further: it reloads a popular key before it expires, so it never misses and is never served past its TTL.

There are two common ways to do it.

A scheduled refresher. A small background job keeps a list of hot keys, say the 500 most-viewed restaurants at dinner, and reloads each one a minute or so before its TTL runs out. It's simple and predictable, but someone has to maintain the list, and a restaurant that goes viral at 8:05pm isn't on it.

Probabilistic early expiration. No list, no job. Each request that reads a key rolls a dice, and the closer the key is to expiring, the more likely the roll says "refresh it now". Store how long the last rebuild took alongside the value, then:

// delta: how long the last rebuild took, in ms. beta: 1 by default; higher refreshes earlier.
const refreshEarly = Date.now() - delta * beta * Math.log(Math.random()) >= expiresAt
if (refreshEarly) rebuildInBackground(key)   // still behind the Fix 1 lock

Math.log(Math.random()) is negative, so each read adds a random amount of "pretend it's later than it is", scaled by how slow the rebuild is. A hot menu read 300 times a second is almost certain to be refreshed by one request shortly before expiry. A cold key read twice an hour just expires normally, so you never spend database work on keys nobody wants. This scheme comes from a 2015 VLDB paper, "Optimal Probabilistic Cache Stampede Prevention", and is often called XFetch.

Refresh-ahead has a cost: it does database work in advance, and some of that work is wasted if the key isn't read again. That's why it's for hot keys only, and why the probabilistic version is popular: it refreshes in proportion to demand. It also doesn't replace invalidation. A restaurant that edits its menu still needs the key deleted on change (the invalidation lesson); refresh-ahead only stops expiry from ever causing a miss.

Cold starts: the cache is empty

A related problem: the cache is empty, not because keys expired, but because Redis restarted, was replaced, or you just bumped the key version from v1 to v2 in a deploy.

For a moment, the hit ratio is 0%. Every request goes to the database. At 3am that's fine. At 8pm it's a stampede across every key at once.

Defences:

• Don't flush or change key versions at peak. Deploys that change cache formats go out in the morning.
• Warm the cache first. Before switching to v2, a script loads the 500 most popular menus into v2 keys. Popularity follows a steep curve: a few hundred restaurants account for most menu views.
• Use the stampede fixes above, so even a cold cache sends one query per key, not hundreds.

Hot keys: one key, too much traffic

Now a different problem. Tiffin runs a promotion with a famous chef's restaurant and sends a push notification to 2 million customers at 8pm. In the next few minutes, restaurant 42's menu is requested 20,000 times a second.

The cache has it, so the database is fine. But a single key lives on a single Redis server, and now:

20,000 requests/s x 30 KB = 600 MB/s = ~4.8 Gbit/s

That's about half of a typical 10 Gbit/s network link, for one key. Redis handles commands on a single main thread, and copying out 30 KB values that fast keeps it busy too. Every other key on that server slows down with it. This is a hot key.

Fixes:

• Cache it closer: in each app server's memory. Keep hot keys in a small in-process cache with a short TTL, like 5 seconds. Each app server then asks Redis once every 5 seconds instead of thousands of times. The cost is up to 5 seconds of extra staleness, so pair it with checkout validation, as always.
• Make copies of the key. Store the value under several keys (menu:v1:42#1 to menu:v1:42#8), spread across Redis servers, and have readers pick one at random. Invalidation has to delete all copies.
• Make the value smaller. Compressing the 30 KB menu to 8 KB cuts the bandwidth by nearly 4 times. Splitting rarely-needed parts (long descriptions) out of the main payload helps too.
• Know in advance. Promotions are planned. If marketing tells engineering first, the hot key can be pre-warmed into local caches before the notification goes out.

Hot keys also exist in databases and partitioned systems. Module 14 covers them in depth.

Lookups for things that don't exist

Cache-aside only stores things it finds. So what happens when someone asks for something that isn't there?

GET /restaurants/99999999/menu

The cache misses (there's nothing to cache), the database query finds nothing, and the request returns 404. Nothing is stored, so the next request for the same id misses again. A bot that requests random ids, or a buggy app stuck retrying a deleted restaurant, sends every single request straight to the database, and the cache does nothing to stop it. This is called cache penetration.

Fixes:

• Cache the "not found" too. Store a small marker, like menu:v1:99999999 = "none", with a short TTL (say 60 seconds). Repeat requests for the same missing id now hit the cache. Keep the TTL short, because "not found" can become "found" when a restaurant is created.
• Reject impossible ids early. If ids are positive integers under 10 million, refuse anything else before touching the cache or the database.
• Use a Bloom filter for huge key spaces. A compact structure that can answer "this id definitely doesn't exist" without asking the database. We'll see how it works in Module 19.
• Rate limit. One client asking for thousands of different missing ids a minute is abuse, and Module 8 covers stopping it.

When the cache goes down

Finally, the big one: Redis is unreachable. In the cache-aside lesson, we fell back to the database. But we also saw the catch: at a 95% hit ratio, the database is about to receive 20 times its normal menu load.

You need a plan for this before it happens:

• Short timeouts on cache calls (tens of milliseconds), so a slow cache doesn't make every request slow.
• Stop calling a cache that's clearly down. After several failures in a row, skip the cache for a few seconds instead of paying the timeout on every request. This is a circuit breaker, covered in Module 12.
• Limit how much reaches the database. Cap the number of concurrent menu queries. Requests beyond that get a fast error or a simplified response, rather than queuing until the database falls over.
• Keep a small local cache. The in-process hot-key cache from above also absorbs much of the load when Redis is gone.
• Make Redis itself sturdier. Managed Redis services offer a replica that takes over if the primary fails, usually within seconds to a minute.

The honest test: can the database survive the full read load for a few minutes without the cache? If not, the cache isn't an optimisation any more. It's a critical part of the system, and needs to be run like one.

The problems at a glance