Step 2 of 17 · 1 min

Why caching works so well

A cache is a small, fast store that keeps copies of data that's expensive to get, so you can reuse them. Two facts make it so effective.

The speed gap is huge. From lesson 1.2: reading from memory takes nanoseconds, a database query takes milliseconds. Even a cache on another machine, reached over the network, answers a simple lookup in well under a millisecond, while the query it replaces might take 5 or 50.

Requests are very uneven. In almost any app, a small fraction of the data gets most of the reads. A few thousand active profiles and today's popular posts account for the large majority of Chirp's database reads; the millions of old posts are rarely touched. So a cache doesn't need to hold everything. It needs to hold the popular part, and that's usually small enough to fit in memory.

The hit-ratio math

When a request finds what it needs in the cache, that's a hit. When it doesn't and has to go to the database, that's a miss. The share of requests that are hits is the hit ratio, and it's the most important number for any cache.

Two simple formulas explain almost everything:

average latency = hit ratio × cache time + (1 − hit ratio) × database time
database load   = (1 − hit ratio) × total reads

The second one is the surprising one. Look at what happens to database load as the hit ratio climbs:

Going from 90% to 99% sounds like a 10% improvement. It actually cuts the database's read load by a factor of ten. Near the top, every extra point of hit ratio matters enormously.

Step 3 of 17 · 1 min

Where caches live

Chirp's Redis cache is one kind, but caching happens at almost every layer between a user and the data, and it helps to see them together:

This lesson is mostly about the shared cache, because that's where the hard problems are. But the same ideas, especially about stale data, apply at every layer.

Step 4 of 17 · 1 min

Cache-aside

The pattern Chirp used is the most common one, called cache-aside (or lazy loading). The application talks to both the cache and the database, and manages the cache itself:

def get_profile(user_id):
    key = f"profile:{user_id}"
    cached = redis.get(key)
    if cached is not None:
        return deserialize(cached)               # hit

    profile = db.query("SELECT ... FROM users WHERE id = %s", user_id)   # miss
    redis.set(key, serialize(profile), ex=3600)  # keep for an hour
    return profile

Read the cache. If it's there, done. If not, read the database and put the result in the cache for next time.

Cache-aside has real strengths. Only data someone actually asked for ends up in the cache, so memory isn't wasted. If the cache goes down, the code can still fall back to the database (though, as we'll see, the database may not survive that). And it's easy to add to existing code, one query at a time.

Its weakness is that the database and the cache are two separate copies of the data, kept in sync by your own code. That's where all three of Chirp's incidents came from.

The other patterns

You'll hear about a few others, and it's worth knowing how they differ:

• Read-through. Like cache-aside, but the cache itself loads missing data from the database, so the app only talks to the cache. Common in caching libraries. Same behaviour, tidier code.
• Write-through. Every write goes to the cache and the database together, so the cache is always up to date for anything that was written. The cost is slower writes, and the cache fills up with data that may never be read.
• Write-behind (or write-back). Writes go to the cache, and the cache writes them to the database later, in batches. Writes become very fast, but if the cache loses data before it's written to the database, those writes are gone. It suits things like view counters, where losing a few seconds of increments is acceptable, and it doesn't suit anything you'd be upset to lose.
• Write-around. Writes go only to the database, and the cache is filled only on reads. This is what cache-aside does by default.

Step 5 of 17 · 3 min

Invalidation: the hard part

There's an old joke that there are only two hard things in computer science: cache invalidation and naming things. The joke lasts because the first half is true.

Invalidation means making sure the cache doesn't keep serving data that has changed in the database. There are a few approaches, and real systems usually combine them.

Expire after a while

Every cached value gets a time to live (TTL), like the ex=3600 above. After an hour, it disappears, and the next read fetches fresh data. This is simple and always eventually correct, but for up to an hour after a change, readers can see old data. For a follower count, that's fine. For a display name someone just changed, it feels broken.

Delete when the data changes

When a profile is updated, delete its cache entry:

def update_display_name(user_id, name):
    db.execute("UPDATE users SET display_name = %s WHERE id = %s", name, user_id)
    redis.delete(f"profile:{user_id}")

The next read misses and loads the new name.

Why delete rather than write the new value into the cache? Because when two updates happen close together, their cache writes can arrive in a different order from their database writes. Update A writes the database, then update B writes the database, then B's cache write lands, then A's lands last, and the cache now holds A's older value. A delete has no such problem: whatever order the deletes arrive in, the result is the same: nothing cached, so the next read gets the truth.

Two details that matter in practice:

• Delete after the database transaction commits, not before. Delete first, and another request can read the old value from the database and put it back in the cache before your update finishes.
• A delete can fail. If the network blips, the cache keeps the old value until the TTL expires. This is why you keep a TTL even when you delete on writes: it limits how long a missed delete can last.

The race that still gets through

Even with delete-after-commit, there's a well-known race in cache-aside, and it's the one that caused Chirp's first incident.

Meera changed her display name from "Meera K" to "Meera Kapoor." At almost the same moment, someone loaded her profile. Here's the order things happened in:

1. The reader checks the cache. It's empty (it had just expired), so that's a miss.
2. The reader queries the database and gets "Meera K."
3. The writer updates the database to "Meera Kapoor" and commits.
4. The writer deletes the cache entry, which wasn't there anyway.
5. The reader, which was a few milliseconds slower, now puts "Meera K" into the cache, with a one-hour TTL.

The cache now holds the old name, the delete has already happened, and nothing will fix it for an hour.

It needs unlucky timing, so it's rare. But with millions of reads a day, rare things happen every day. A few things help:

• A shorter TTL limits how long a stale value can survive. It doesn't prevent the race.
• Leases. This is the fix Facebook described in its well-known paper on scaling Memcache. When a reader misses, the cache gives it a lease: a token that says "you may fill this key." If a delete happens before the reader writes, the lease becomes invalid, and the reader's write is rejected. In the steps above, the reader's write in step 5 fails, and the next reader loads the new name.
• Version checks. Store a version number with each row (incremented on every update), cache it with the value, and only write to the cache if the version is newer than what's there.

Chirp added leases for profiles and kept a 10-minute TTL as a safety net.

Making invalidation reliable

There's a bigger problem underneath all of this: every place in the code that updates a profile has to remember to delete the cache entry. Chirp had seven different code paths that could change a profile, and two of them forgot. No amount of clever leasing helps if the delete never happens.

The more reliable approach is to invalidate from the database's own record of changes, its write-ahead log (lesson 1.4). A small separate process follows that log and deletes the cache key for every row that changes, no matter which code made the change. This is called change data capture, and lesson 3.4 shows how it works.

Step 6 of 17 · 1 min

Keys, sizes and memory

Some practical choices that make a big difference:

Name keys predictably, and include a version. profile:v2:4821, not 4821. When you change what gets stored for a profile, bump the version. New code reads new keys, old entries simply stop being used and expire, and nothing tries to read a value in the old format.

Cache what's expensive and widely shared. A profile that a thousand people view is a great cache entry. A page of search results for one user's unusual query is a poor one.

Remember "not found." If someone requests a user who doesn't exist, every request misses the cache and queries the database. Bots can do this on purpose. Cache the "not found" result too, briefly, which is called negative caching.

Estimate the memory. It's napkin math (lesson 1.3). Chirp's most active 1 million profiles at about 1 KB each, plus the last two days of posts, came to a few gigabytes. Redis needs some extra for its own bookkeeping, so they gave it 16 GB.

When memory runs out

A cache is always smaller than the data behind it, so it needs a rule for what to throw out when it's full. This is the eviction policy:

• LRU (least recently used): throw out whatever hasn't been read for the longest. A good default.
• LFU (least frequently used): throw out whatever is read least often. Better when popularity is stable over time.
• TTL-based: throw out what's going to expire soonest anyway.

In Redis, this is the maxmemory-policy setting, and its default in many setups is noeviction, which means that when memory is full, Redis refuses new writes with an error, instead of throwing anything out. That's the right behaviour if Redis is storing data you can't lose (like the sessions from lesson 2.1). For a pure cache, it's exactly wrong. Chirp's cache used allkeys-lru, and its sessions lived in a separate Redis instance with noeviction.

Step 7 of 17 · 2 min

The stampede

Chirp's second incident happened at 9:04 pm, during a cricket match.

A commentator's profile was cached with a one-hour TTL. It was one of the most viewed profiles on Chirp that night: about 2,000 views a second. At 9:04 the entry expired.

In the next 50 milliseconds, around a hundred requests arrived for it. Each checked the cache, missed, and ran the profile query, a fairly expensive one that included follower counts. Each of those queries was slower than usual because a hundred identical copies were running at once, so the cache stayed empty for longer, so more requests missed. Within a second, there were nearly a thousand copies of the same query on the database. Database CPU hit 100%, and everything else on Chirp slowed to a crawl for about forty seconds until one query finally finished and filled the cache.

This is a cache stampede (also called dog-piling or the thundering herd): a popular entry expires, and many requests try to rebuild it at the same moment, piling onto the database.

There are several fixes, and they combine well:

Only let one request rebuild it. When a request misses, it takes a short lock for that key (in Redis, a SET ... NX like lesson 2.1's). The one that gets the lock queries the database. The others wait briefly and then read the cache, or return slightly stale data. Inside a single server, the same idea is called request coalescing or single-flight: if a request for the same key is already in progress, later ones wait for its result instead of starting their own.

Serve stale while refreshing. Keep the old value a little past its expiry. When it's stale, return it immediately and let one background refresh fetch the new value. Users never wait for the database, and the database sees one query instead of a thousand. This is the same idea as the stale-while-revalidate header from lesson 2.3, applied to your own cache.

Refresh early, at random. Instead of every request waiting until the exact expiry moment, each request that reads a value close to expiry has a small chance of refreshing it early, and that chance grows as expiry approaches. With many requests per second, one of them refreshes it a little before it expires, and the stampede never happens. A 2015 paper by Vattani and colleagues worked out an optimal version of this, sometimes called XFetch.

Spread out expiry times. If Chirp deploys and warms 50,000 entries at once, all with a one-hour TTL, they all expire at the same moment an hour later. Adding a little randomness to each TTL (say, 55 to 65 minutes) spreads the misses out.

Chirp used single-flight inside each server, plus serve-stale-while-refreshing for its most popular keys.

Step 8 of 17 · 2 min

When the cache goes away

The third incident was the serious one.

Six weeks after the cache went in, the team restarted the Redis server to upgrade it. It took about thirty seconds, and when it came back, it was empty.

In those six weeks, Chirp had grown. The database now handled evening traffic comfortably with a 97% hit ratio, at around 25% CPU. Nobody had checked what it would face without the cache. Without the cache, it got every read: about thirty times its normal load. It went to 100% CPU instantly, queries piled up, app servers ran out of database connections (lesson 1.4), and Chirp went down. Even after Redis was back, the database was so overloaded that the cache couldn't fill up quickly, because every miss took seconds to answer. It took seven minutes, and temporarily blocking some traffic, to recover.

This is the trap at the end of every successful cache. Once the cache is good enough, the system quietly comes to depend on it. The database is no longer sized for the real load, only for the misses. The cache has stopped being an optimization and become a load-bearing wall.

What helps:

• Know your cold-start load. Work out, or test, what happens with an empty cache. If the answer is "the database falls over," plan for it.
• Don't let caches all go cold at once. Run the cache with replicas, so a restart or failure of one node doesn't empty it. Restart nodes one at a time. Many teams prefer several cache nodes, each holding part of the keys, so losing one only loses a fraction of the cache.
• Warm before switching. Before sending traffic to a new or restarted cache, fill it with the most popular keys, for example by replaying recent read traffic or loading a known list.
• Protect the database. If the cache is unavailable, limit how many requests can go to the database at once, and turn the rest away quickly, or serve stale data from a small in-process cache. A partly degraded Chirp is better than a completely down one. Lesson 6.1 covers these patterns.
• Set timeouts on cache calls. A cache that is slow, rather than down, can be worse: every request waits for it before falling back. Cache lookups should give up after a few milliseconds.

Step 9 of 17 · 1 min

Hot keys

Even a healthy cache has a limit. A Redis server handles each key on one machine. During that cricket match, one profile was being read 2,000 times a second; at a big event, a single key can get hundreds of thousands, more than one machine's network card can handle.

The usual fixes are a tiny in-process cache on each app server for the very hottest keys (a few seconds of staleness is fine for a profile), or storing several copies of a hot key under different names and picking one at random. Lesson 4.5 goes much further into hot keys.

Step 10 of 17 · 1 min

What not to cache

Not everything should be cached, or at least not with the same rules:

• Data where being out of date is dangerous. Whether someone has blocked you, whether a post is private, account balances. If you cache them at all, invalidate carefully and keep TTLs very short, or check the database for the final decision.
• Data that's read once. Caching it costs memory and effort for no benefit.
• Data that's cheap to get anyway. If the query takes 0.2 ms from the database's own memory, a network trip to a cache saves very little.

Step 11 of 17 · 1 min

From the real world: the fixer that broke Facebook

Chirp's third cache incident was a feedback loop: a failure that creates more of the load that caused it. The largest public example of one in a cache is Facebook's outage on 23 September 2010, its worst in four years at the time.

Facebook had an automated system for checking configuration values that were cached around its fleet. If a client found a cached value that looked invalid, the system would delete the cached copy and read the correct value from the database. For bad values in a cache, that's a reasonable self-repair.

That day, someone changed a value in the persistent store itself, and the new value was interpreted as invalid. Now every client saw an "invalid" value, and every client tried to fix it the same way: delete the cache entry and query the database. One database cluster suddenly received hundreds of thousands of queries a second.

The database cluster started failing some queries. And here's the loop: a client that got an error from the database treated it as another invalid value, deleted the cache entry again and queried again. The more the database struggled, the more load it got. There was no state the system could drift back to on its own.

The only way out was to stop all traffic to that database cluster, which meant turning off the site for everyone. Once the databases recovered, Facebook let people back in gradually, and turned off the automatic fixer. The outage lasted about two and a half hours.

Things to check in your own cache code:

• "I couldn't check" is not "I checked, and it's wrong." A timeout or error from the database must not trigger the same path as a confirmed bad value.
• Self-repair needs a limit: a maximum rate of repairs, or a circuit breaker that stops repairing when repairs aren't working.
• Ask "what if every client does this at once?" The same question as Facebook's 2021 DNS outage in lesson 1.1, eleven years earlier.

Step 12 of 17 · 2 min

Going deeper: why LRU loses to a batch job

This lesson recommended LRU eviction as a good default, and for steady traffic it is. It has one well-known weakness, and Chirp hit it the first time someone ran a data export at lunchtime.

The export read every user's profile once, a million profiles, through the same cache-aside code as the app. Under LRU, every key that's read gets admitted, and goes to the front of the line. So each of those million one-off profiles pushed out something popular. By the end of the scan, the cache was full of profiles nobody would read again, and the profiles people actually look at were gone. The hit ratio dropped from about 94% to near 10%, and took most of an hour to recover, while the database carried the difference.

There are three ways to defend against this:

• Keep batch reads out of the cache. Exports, backfills and crawlers should read the database (or a replica) directly, or use a "read-through without filling" flag. This is the cheapest fix and usually the right one.
• Use a scan-resistant policy. Modern in-process caches use admission control: a new key only gets in if it's likely to be more useful than the key it would replace. W-TinyLFU, used by Caffeine (Java) and Ristretto (Go), keeps a compact count of how often keys have been requested recently (a count-min sketch, a few bytes per key). A one-off key from a scan loses the comparison against a popular key, so it's not admitted. A small "window" of plain LRU still lets genuinely new popular keys in quickly.
• Use segmented LRU. Redis's allkeys-lfu policy, and many CDNs, separate keys seen once from keys seen more than once, so a burst of one-off keys only competes with other one-off keys.

The broader point: an eviction policy is a prediction of the future. LRU predicts "what was read recently will be read again." Scans break that prediction. Frequency-based policies predict "what has been popular will stay popular," which survives scans but adapts more slowly when popularity shifts. W-TinyLFU's window-plus-frequency design is popular because it hedges between the two.

Step 13 of 17 · 1 min

What Chirp changed

• Kept cache-aside, with versioned key names and a TTL on everything as a safety net.
• Added leases for profile entries to close the stale-set race, and started moving invalidation to change data capture.
• Added single-flight in each app server, and serve-stale-while-refreshing for the most popular keys. TTLs got a random 10% spread.
• Set the cache's eviction policy to allkeys-lru, with sessions in a separate Redis instance set to noeviction.
• Moved the cache to a replicated setup, and added a monthly test with the cache deliberately emptied at low traffic, to measure the database's cold-start load.
• Gave cache calls a 5 ms timeout, and capped concurrent database queries per app server, so a cache failure degrades the app instead of taking it down.

Step 14 of 17 · 1 min

In the simulation

Stage 1's decision D3 includes "add a cache." It's the cheapest option, and it works well. Then Stage 1 restarts your cache during peak traffic. Whether that's a blip or an outage depends on whether you also did something about the database's cold-start load. In Stage 3, a celebrity's profile turns into exactly the stampede in this lesson.

Open the simulation →

Step 15 of 17 · 1 min

If you're here for an interview

"Add a cache" is in almost every design answer. The questions that follow it:

• "What's your hit ratio, and what happens to the database at 90% vs 99%?" Show the (1 − hit ratio) math.
• "How do you keep the cache up to date?" Delete on write after commit, a TTL as a safety net, and mention the stale-set race. Leases or change data capture are strong answers.
• "What happens when a popular key expires?" Name the stampede and give a fix: single-flight, serve stale, or early refresh.
• "What if the cache goes down?" This is the question that separates people who've run caches from people who've drawn them. Talk about cold-start load and protecting the database.

Step 16 of 17 · 2 min

Try these yourself

Step 17 of 17 · 1 min

Further reading

• Rajesh Nishtala et al., "Scaling Memcache at Facebook," NSDI 2013. The section on leases, and on regional and cold-cluster warm-up, is directly relevant.
• Andrea Vattani, Flavio Chierichetti, Keegan Lowenstein, "Optimal Probabilistic Cache Stampede Prevention," VLDB 2015.
• Redis documentation on key eviction (maxmemory-policy) and on replication.
• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 11, for change data capture and keeping derived data in sync.
• Robert Johnson, "More Details on Today's Outage," Facebook Engineering, 23 September 2010.
• Gil Einziger, Roy Friedman and Ben Manes, "TinyLFU: A Highly Efficient Cache Admission Policy" (ACM Transactions on Storage, 2017), and the Caffeine wiki's "Efficiency" page with hit-ratio comparisons on real traces.