The hard parts: invalidation, stampedes and hot keys

Part of the free System Design course on LogicWiz, in the chapter: Caching. The interactive whiteboard exercises and simulations run in the app.

Week 6, Day 4: Sale day, 12:00:00

"At noon the cache was warm and the database was asleep. At 12:10 the database was on fire. Nothing had deployed."

Meera, writing the incident notes

Invalidation: the price changed, the cache did not

There is an old joke that the two hard problems in computing are naming things, cache invalidation and off-by-one errors. Here is why it is not a joke.

Marketing drops the price of a 5 kg atta pack from 290 to 249 rupees at noon. The old price sits in the cache with 10 minutes left on its TTL. For 10 minutes, some shoppers see 290, and worse, the cart (reading the database) says 249. Support gets angry calls.

You have three tools, usually combined:

  • Wait for the TTL. Simple, with bounded staleness. Fine for descriptions, wrong on its own for prices.
  • Delete on write. When the price changes, the same code deletes the cached entry (or overwrites it), so the next read refetches. Fast, but if the delete fails or a different service changes the data, the copy survives.
  • Version the key. Store under "atta:v42" and bump the version on change. Old entries simply never get asked for again.

Rule of thumb: pair delete-on-write with a TTL as a safety net. The delete gives freshness; the TTL guarantees that even a missed delete heals itself in minutes, not never.

The stampede: SwiftKart's 12:10 incident

The festival sale starts at noon. The homepage "Top deals" list is cached with a TTL of 10 minutes, and 15,000 shoppers a second are reading it. The cache absorbs everything; the database sees almost nothing.

At 12:10 the entry expires. In the next fraction of a second, thousands of requests all miss at once. None of them knows that the others are fetching too, so each one runs the expensive "top deals" query (about 400 ms). Within a second, roughly 6,000 identical heavy queries hit the database. It can run only a few dozen of those a second, so this is a hundred times too many. It slows and queries time out. The fetches fail, so nothing gets stored in the cache, and the misses keep coming. This is a cache stampede (or thundering herd). The cache was protecting the database, and its own expiry broke the protection.

flowchart LR
  U["6000 requests"] -->|"all miss at 12:10"| D["Database"]
  D -->|"overloaded"| X["Timeouts"]

Three fixes, all used in practice:

  1. Request coalescing. On a miss, only the first request fetches; the rest wait for its answer. 6,000 queries become one.
  2. Jittered TTLs (for many keys). Thousands of different entries may be cached at the same moment. Give each a TTL of 600 plus or minus 60 seconds so they do not all expire together. This does nothing for a single hot key such as Top deals; use coalescing or refresh-ahead (refreshing the entry shortly before it expires) for that.
  3. Stale-while-revalidate. Keep serving the slightly expired copy while one background worker refreshes it. Shoppers rarely see a miss; a truly cold cache still misses.

⚠️ Warning: Cold starts are stampedes too. If the whole cache restarts empty just before a sale, every request misses at once. Pre-warm the cache with the hot items before traffic arrives.

Meera ran the numbers afterwards. With the stampede, the database took about 6,000 heavy queries in the first second. With coalescing it takes one. With stale-while-revalidate, or a refresh started 30 seconds before expiry, the key never expires under load, so the database also sees one query. Jitter is the answer for a catalogue of many keys, not for one key. Cheap fixes, huge difference.

Hot keys

Spread is the other danger. A cache distributes keys over several nodes, but "Top deals" is a single key, and it lives on one node. If 15,000 requests a second hit that single key, that node can saturate while its neighbours idle. This is the hot key problem, the cache version of Week 5's hotspot.

There are two fixes. Keep a copy of the very hottest entries in each service machine's own memory for a few seconds. Or store the hot key under several names (deals:1 to deals:4) and let each request pick one at random. Remember to invalidate all four copies when the data changes.

A cache is not the source of truth

During the incident review, someone asked: "The cache holds our data, so why worry about the database?" The cache is a disposable copy. It can be evicted when memory fills, lost in a restart, or wiped by a failover. The real, durable record lives in the database. Test every design with one question: if I flush the whole cache right now, is anything lost? If yes, you have used the cache as a database. One restart will lose orders.

This also explains the single cache instance risk. One cache node that dies is not a data loss, but it is a stampede: all traffic suddenly lands on the database, which was sized for 1% of it. So run the cache with replicas (on the board, 2 means two instances). Also protect the database on a cold start, so it never takes the full traffic. Warm the hot keys, coalesce misses, and shed load (rate-limit or reject excess reads).

Deciding the policy

For each cached thing, write down three choices: TTL, how it is invalidated, and what happens on a miss. Fast-changing prices: 60-second TTL plus delete-on-write. Slow-changing prices: 10 minutes plus delete-on-write. Product photos: 1 day, versioned URLs. Top deals (one hot key): 10 minutes, coalesced refresh, stale-while-revalidate. Product pages (many keys): 10 minutes plus or minus 60 s jitter. That short table is what a design interviewer wants to hear.

📌 Summary: Invalidate with delete-on-write plus a TTL safety net. Stop stampedes with coalescing (one hot key) or jittered TTLs (many keys). The cache is a disposable copy, never the source of truth.

What Meera learns next

With data stored, split and cached, SwiftKart needs its pieces to talk without waiting on each other. Next week: queues and asynchronous work.

Check your understanding

  1. The single "Top deals" key is read 15,000 times a second during a sale and has a 10-minute TTL. A teammate suggests jittering its TTL to 600 plus or minus 60 seconds. What should Meera do?
  2. At 11:55 the team pre-warms 50,000 product pages, all with the same 10-minute TTL, before a noon sale. What should they add?
  3. When marketing changes a price, the code deletes the cached entry. Why does Kabir still want a TTL on it?
  4. A design writes new orders to Redis and copies them to the database every 5 minutes. Which single question exposes the flaw?