System Design, Step by Step

Part 3 · The Building Blocks

Caching Part 2: Strategies, Eviction and Invalidation

Adding a cache is easy; keeping it correct is hard. The six read/write strategies, why you delete rather than update on write, eviction policies you can try by hand, invalidation per data type, and the five ways caches cause outages.

Lesson 1612 min readintermediate#caching#redis

On this page

  1. The Problem
  2. The Core Idea
  3. How It Works
  4. Trade-offs
  5. In the Real World
  6. Interview Questions
  7. Key Takeaways
  8. Further Reading

The Problem

You added Redis in front of your database (Part 1). Pages are fast and everyone is happy. Then the bug reports start:

  • "I changed my profile picture, but it still shows the old one."
  • "The price on the product page is different from the price at checkout."

Then one night, a popular cache key expires, 50,000 requests hit the database in the same second, and the site goes down.

Quick reminder: a cache is a fast store that keeps copies of data. A cache key is the name of one cached item. TTL (time to live) is how many seconds an item may stay in the cache before it expires. Stale data is old data that is no longer correct.

Adding a cache is easy. Keeping it correct and safe is the hard part. This post covers the three big questions:

  1. How do reads and writes flow between the cache and the database?
  2. What gets removed when the cache is full?
  3. How do you keep cached data fresh, without melting the database?

The Core Idea

Go back to the kitchen counter from Part 1.

  • Strategy: when you use the last of the salt, do you refill the counter jar right away, or only the next time you need it?
  • Eviction: the counter has limited space. When it's full, which jar goes back to the cupboard? The one you haven't used in weeks.
  • Invalidation: if the milk on the counter has gone off, you need to know, and replace it before someone makes tea with it.
  • Stampede: if everyone in the house wants tea the moment the milk runs out, and they all rush to the shop at once, that's chaos. Better that one person goes while the others wait a minute.

How It Works

Part A: Caching strategies

1. Cache-aside (lazy loading), the most common

Cache-aside means the application manages the cache directly. It reads the cache first. On a miss, it reads the database and then saves the result in the cache. This is also called "lazy loading", because data is only loaded when someone asks for it:

step 1 / 8
App
Cache
Database
  1. GET user:42
  2. miss
  3. SELECT user 42
  4. row
  5. SET user:42 (TTL)
  6. Later, the user edits their profile
  7. UPDATE user 42
  8. DEL user:42
    the next read reloads fresh data
Cache-aside with delete-on-write — the safe default. · sequence · step through
  • ✅ Simple. Only data that's actually requested gets cached.
  • ✅ If the cache dies, the app still works, just more slowly, by reading the DB.
  • ❌ The first read after a miss or delete is slow.
  • ❌ Data can be stale until the key expires or is deleted.

2. Read-through

Like cache-aside, but the cache library or service loads from the database on a miss, not your app code. The app only ever talks to the cache. This is common with caching libraries and some managed caches. It gives cleaner app code, but you're more tied to the cache tool.

3. Write-through

Write-through means every write goes to the cache and the database together, before the write is confirmed to the user:

  1. App
  2. Cache
    updated first
  3. Database
    then confirmed
Write-through: confirmed only after both copies are written. · flow
  • ✅ The cache is always up to date for data you wrote, so reads right after a write are fresh.
  • ❌ Writes are slower, because they touch two systems.
  • ❌ You may fill the cache with data nobody reads.

4. Write-behind (write-back)

Write-behind means writes go to the cache first and are confirmed immediately. The cache writes them to the database later, often in batches (many writes at once).

  1. App
  2. Cache
    ✅ confirmed at once
  3. Database
    lost if the cache dies first
Write-behind: confirmed by the cache now, written to the database later — possibly in batches. · flow
  • ✅ Very fast writes, and batching reduces database load.
  • ❌ Risk of data loss. If the cache crashes before flushing, those writes are gone.
  • ❌ More complex, and the database is temporarily behind.
  • Good for: view counters, likes, analytics, anything where losing a few updates is acceptable. Never for payments or orders.

5. Write-around

Write-around means writes go straight to the database, skipping the cache. The cache is only filled when the data is read. This is useful for data that's written often but rarely read soon after, like logs or bulk imports.

6. Refresh-ahead

Refresh-ahead means the cache refreshes popular keys before they expire. If a key is read often and its TTL is nearly up, reload it in the background. Popular items never have a slow miss. The downside is extra work if you guess wrong about what's popular.

Summary (a "strategy" is a rule for how reads and writes move between the cache and the database):

StrategyRead speedWrite speedFreshnessData-loss riskTypical use
Cache-asideFast after first missNormalGood (with delete on write)NoneDefault choice
Read-throughSameNormalGoodNoneLibrary-managed caching
Write-throughFastSlowerVery goodNoneRead-after-write is common
Write-behindFastVery fastCache fresh, DB delayedYesCounters, analytics
Write-aroundMiss after writeNormalGoodNoneWrite-heavy, read-rarely data
Refresh-aheadVery fast for hot keysNormalGoodNonePredictable hot keys

Delete or update the cache on write?

With cache-aside, after updating the database, should you update the cached value or delete it? Deleting is usually safer. Here's why updating can go wrong:

step 1 / 5
Request A
Database
Cache
Request B
  1. UPDATE price = 100
  2. UPDATE price = 120
  3. SET price = 120
  4. SET price = 100
    A was slower
  5. Database says 120, cache says 100 — until the TTL expires. Deleting the key instead avoids this.
Why “update the cache on write” can go wrong. A slower request overwrites the newer value. · sequence · step through

If both requests delete the key instead, the next read reloads the correct value (120) from the database.

There's still a smaller race. A race (or race condition) is a bug where the result depends on which request finishes first. Here, a slow read can put old data back just after a delete. That's why teams add:

  • TTLs on everything, so any mistake eventually fixes itself,
  • sometimes a "delete again after a short delay" trick,
  • or version numbers on cached values.

Part B: Eviction, when the cache is full

empty
empty
empty
empty
most recently usednext to be evicted →
hits
0
misses
0
hit ratio
–

Tip: request home, cart, home, p:1, p:2, p:3 and see which key each policy throws away.

A 4-slot cache. Request keys by hand and compare which one each policy throws away. · interactive

Memory is limited. When the cache is full and a new item arrives, something must be removed. This removal is called eviction. The rule for choosing what to remove is the eviction policy:

  • LRU (Least Recently Used). Remove the item that hasn't been accessed for the longest time. It's the most common default, and matches "recently used things will be used again".
  • LFU (Least Frequently Used). Remove the item accessed the fewest times. It's better when some items are always popular, and resists one-off scans pushing popular items out.
  • FIFO (First In, First Out). Remove the oldest-added item. Simple, but ignores popularity.
  • Random. Remove a random item. Surprisingly decent and very cheap.
  • TTL-based. Items expire when their time is up, whether or not memory is full.

In Redis, you choose the policy with the maxmemory-policy setting:

  • allkeys-lru / allkeys-lfu evict any key.
  • volatile-lru / volatile-ttl only evict keys that have a TTL.
  • noeviction makes write commands fail with an error when memory is full. That's right for Redis used as a primary store (where losing data is bad), and wrong for a cache.

Redis uses approximate LRU/LFU: it samples a few keys and evicts the best candidate among them, which is much cheaper than tracking exact order.

Watch the eviction rate (how many items are evicted each second). If popular items are constantly being evicted, the cache is too small, and your hit ratio suffers.

Part C: Invalidation, keeping data fresh

There's no perfect answer. You choose based on how stale each piece of data is allowed to be.

Invalidation means removing or replacing cached data that is no longer correct. 1. TTL only. Let entries expire. Simple, and good when "a bit stale" is fine, like a view count or a trending list.

2. Delete on write. The app deletes the cache key whenever it updates the data. Accurate, but every code path that writes must remember to do it. Forgetting one path is a common bug.

3. Event-driven invalidation. When data changes in the database, an event (a small message that says "this changed") is published. This can use a queue (a list of messages waiting to be processed) or Change Data Capture (CDC), a tool that reads the database's change log (the record of every change). A separate process listens and deletes the matching cache keys. This is reliable even when many services write to the same data (Part 6).

4. Versioned keys. Include a version in the key: product:991:v7. When the product changes, bump the version to v8. Old entries are never read again and simply expire. This avoids delete races completely.

Ask for each type of data: how stale can it be?

DataAcceptable stalenessApproach
View counts, likesMinutesTTL, write-behind
Product descriptionMinutesTTL + delete on write
Price shown on pageSeconds to minutesShort TTL + delete on write
Price at checkoutNoneRead from the source
Account balance for paymentNoneRead from the source

Part D: When caches cause outages

1. Cache stampede (thundering herd)

A stampede (also called a thundering herd) happens when a very popular key expires. Thousands of requests miss at the same moment, and all of them query the database for the same data:

  1. 10:00:00.000
    the popular key “homepage:deals” expires
  2. 10:00:00.001
    5,000 requests miss at once → 5,000 identical database queries
  3. 10:00:00.200
    database CPU at 100%; queries slow to seconds; more requests pile up
  4. The fix
    one request takes a lock (SET key NX) and rebuilds; the rest get the stale value or wait
A cache stampede, second by second. · timeline

Fixes:

  • Locking / request coalescing. The first request to miss takes a short lock (for example, a Redis SET key NX, which sets a key only if it does not exist yet) and rebuilds the value. Others wait briefly, or get the old value. "Coalescing" means joining many identical requests into one.
  • Serve stale while refreshing. Keep the old value a bit longer, return it, and refresh in the background (like stale-while-revalidate in post 14).
  • Probabilistic early refresh. Each request has a small, growing chance of refreshing the key before it expires, so it's refreshed by one request instead of stampeded by all.
  • Refresh-ahead for known hot keys.

2. Cache avalanche

An avalanche happens when many keys expire at the same time, for example because they were all loaded with a 1-hour TTL right after a deploy (a release of new code). The database suddenly gets a flood of misses.

The fix is to add jitter to TTLs. Jitter means a small random amount. Instead of exactly 3600 seconds, use 3600 plus a random 0–300 seconds, so expirations are spread out.

3. Cache penetration

Penetration means requests for data that doesn't exist (like product:99999999) always miss the cache and always hit the database. Attackers can abuse this. Fixes:

  • Cache "not found" results too, with a short TTL.
  • Use a Bloom filter in front of the database. A Bloom filter is a compact structure that can quickly answer "this ID definitely doesn't exist" or "this ID might exist". It never wrongly says "doesn't exist" for an ID that does exist.
  • Validate input (reject IDs that are obviously invalid).

4. Hot keys

A hot key is one key that gets a huge share of traffic, such as a celebrity's profile or a viral post. Even Redis can struggle, because one key lives on one node (one cache server).

Fixes:

  • keep a small local in-process cache of that key on each app server for a few seconds,
  • or replicate the key across several cache nodes (post:123#1, post:123#2…) and read from a random copy.

5. The cache goes down

If the cache fails, all traffic hits the database, which was sized assuming a 95% hit ratio. It may collapse instantly. Plan for this:

  • run the cache with replicas (extra copies of the cache that can take over; Redis offers replication and Redis Cluster),
  • limit database concurrency (how many queries run at once), so it slows down rather than dies,
  • consider warming a new cache (filling it with popular data) before sending traffic to it,
  • use circuit breakers and load shedding (Part 7). A circuit breaker stops calling a failing system for a while. Load shedding means refusing some requests on purpose to protect the system.
Stampede
  • •One hot key expires; thousands miss together
  • +Lock / coalesce, stale-while-revalidate, early refresh
Avalanche
  • •Many keys expire at the same moment
  • +Add random jitter to every TTL
Penetration
  • •Requests for keys that don't exist always miss
  • +Cache “not found”, Bloom filter, validate input
Hot key · cache down
  • •One key or the whole cache overwhelms the DB
  • +Local copies, key replicas, cache replicas, limit DB concurrency
The five cache failure modes and their standard defences. · compare

Part E: Sizing and monitoring

Track:

  • hit ratio (overall and per key type),
  • evictions per second,
  • memory usage (and fragmentation in Redis: memory that is reserved but wasted in small gaps),
  • p99 latency of cache calls (the time that 99 out of 100 calls beat; it shows the slow cases),
  • database load, which should drop when you add caching and spike when the cache has problems.

Trade-offs

  • Freshness vs speed. Longer TTLs give more hits but staler data.
  • Write-through vs cache-aside. Fresher data after writes, but slower writes and wasted cache space.
  • Write-behind gives very fast writes but can lose data. Use it only where that's acceptable.
  • LRU vs LFU. LRU is simple and adapts quickly. LFU protects long-term popular items but reacts more slowly to new trends.
  • Every protection (locks, jitter, Bloom filters) adds code and complexity. Use the ones that fit your traffic.

In the Real World

Facebook's leases. In its memcache paper, Facebook describes leases, a mechanism where the cache gives one client permission to refill a missing key and tells others to wait briefly. It solves both stale sets (when a slow client saves old data into the cache, like the update race above) and thundering herds, at enormous scale.

Facebook's 2010 outage. In September 2010, Facebook went down for around two and a half hours. A configuration value in the main data store was changed to a value that the system treated as invalid. An automated system on every client tried to "fix" its copy by querying the database cluster, and hundreds of thousands of queries per second overloaded it. Errors made clients retry and delete cache keys, making things worse. The team had to cut traffic to let the databases recover. It's a real-world example of a feedback loop between caches and databases.

Stale prices and inventory. Many online stores show cached prices and stock on product pages for speed, but re-check both from the source at checkout. It's a practical example of choosing different freshness rules for different moments.

Hot keys during big events. Social platforms regularly deal with single posts, like a celebrity announcement or a major news event, receiving huge traffic in seconds. Local caches and key replication are common defences.

The famous quote. Phil Karlton's line, "There are only two hard things in Computer Science: cache invalidation and naming things", is repeated so often because nearly every engineering team eventually has a stale-cache bug story.

Interview Questions

Q1Compare cache-aside, write-through and write-behind.

Cache-aside: the app reads the cache, loads from the DB on a miss, and deletes the key on write — simple and safe. Write-through: writes update cache and DB together — fresh reads after writes, slower writes. Write-behind: writes go to the cache and reach the DB later — fastest writes, but data can be lost, so only for counters and analytics.

Q2Why delete the cache entry on write instead of updating it?

Two concurrent writers can update the DB in one order and the cache in the other, leaving the cache permanently wrong until TTL. Deleting makes the next reader reload the true value. Add a TTL to everything as a safety net for the remaining small races.

Q3What is a cache stampede, and how do you prevent it?

A hot key expires and many requests miss at once, all hitting the database for the same value. Prevent it by letting one request rebuild under a lock while others wait or get the stale value, by serving stale-while-revalidate, or by refreshing hot keys early and probabilistically.

Q4LRU vs LFU?

LRU evicts what hasn't been used for the longest time: simple, adapts quickly to new trends, but a one-off scan can flush popular items. LFU evicts what's used least often: protects long-term favourites, but reacts slowly when popularity shifts. Redis supports approximate versions of both.

Q5How do you handle requests for IDs that don't exist?

That's cache penetration: every request misses and hits the database. Cache the negative result with a short TTL, put a Bloom filter in front to reject IDs that definitely don't exist, and validate input early.

Q6What happens if your cache cluster goes down?

All traffic hits a database sized for a 95% hit ratio, and it may collapse instantly. Mitigate with cache replicas, limits on DB concurrency and load shedding so it degrades instead of dying, circuit breakers, and warming a new cache before sending it traffic.

Key Takeaways

  • Cache-aside (read from cache, load on miss, delete on write) is the safe default. Write-through, write-behind and refresh-ahead fit special cases.
  • Prefer deleting keys over updating them on writes, and put a TTL on everything.
  • Eviction policies (LRU, LFU, TTL) decide what leaves a full cache. Watch evictions and hit ratio.
  • Choose invalidation per data type, based on how stale it can be. Critical values (checkout price, balance) should come from the source.
  • Defend against stampedes (locks, stale-while-revalidate), avalanches (TTL jitter), penetration (cache "not found" results, Bloom filters), hot keys and cache failure.

Further Reading

  • The paper "Scaling Memcache at Facebook" (NSDI 2013), especially the sections on leases and regional invalidation
  • The AWS Builders' Library article "Caching challenges and strategies"
  • The System Design Primer on GitHub (section "When to update the cache")
  • Redis documentation on key eviction policies
  • The paper "Optimal Probabilistic Cache Stampede Prevention" (VLDB 2015)
  • Azure Architecture Center pattern "Cache-Aside"

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series