Caching: The Copy That Can Go Stale

Marlow Books is a four person online bookshop that exists only in this course, and on the Tuesday before Christmas its gift category page spent eleven minutes falling over for twenty or thirty seconds at a time, two or three times a minute.

Up. Down. Up. Down. The founder watched it from the packing room, refreshing, and got a page in 200 milliseconds, then nothing for half a minute, then a page in 200 milliseconds again. Book pages were fine the whole time. Search was fine. Checkout was fine. Only /gifts, the page that week's newsletter pointed at, kept dying and coming back on no rhythm anybody could hear.

They looked at the database first, because everyone looks at the database first. Postgres on box A was sitting at 40% CPU. Load average was unremarkable. No errors in the log, no slow query warnings, nothing killed. By every graph the shop had, its database was having a quiet morning.

Here's what was happening. The gift page is ordered by what's actually selling, which is an aggregation over the last seven days of order lines, and it takes about 900 milliseconds to compute. The founder had wrapped it in a cache with a sixty second lifetime years earlier, when the shop took five requests a second and nobody would ever have noticed. During Christmas week that page takes about twenty a second, ten to each of the two boxes.

So every sixty seconds a box's cached copy expired, and in the 900 milliseconds before anything finished rebuilding it, nine more requests landed on that box, found nothing, and each started its own copy of the same aggregation. Nine copies of one query fighting over the same memory and the same disk are much slower than one, so the rebuild stretched to seconds, so thirty more arrived and started theirs. Every one of them held a worker and a database connection while it waited. The two boxes did this on their own unrelated clocks, which is why the outage had no clean period and why the founder spent eight minutes convinced it was the newsletter.

Nothing was broken. The database was healthy, and it was healthy because it was mostly sitting still, waiting on disk reads for the same seven days of order lines forty times over. The 40% CPU was true and useless.

At 11:13 the founder replaced the ordering with a hand written list of twelve titles. The flapping stopped in the time it took to deploy. That evening they added a cron job that writes the ranking into a small table every ten minutes, and the page reads one row.

The cache had been doing its job for years. The outage was caused by it working.

What a cache is, and the one thing it needs to be true

A cache is a copy of an answer, kept somewhere cheaper to reach than the place that computed it, together with a rule for when to stop believing it.

That second half is the entire subject. Anybody can keep a copy. The engineering is in the rule.

Caching only pays when the same answer gets asked for more than once before it goes stale. That sounds obvious and it quietly disqualifies most of what people try to cache. Lesson 006 put Marlow's Christmas mix at about 96% book pages and 4% full text searches, and noted that no cache helps the searches, because every search string is different. A copy read once is worse than no copy: you paid to compute it, paid to store it, got nothing back.

Two events end an entry's life, and they are not the same event.

Expiry is the rule you wrote. You attached a time to live, a TTL, when you stored the entry, and when it runs out the entry is no longer allowed to be believed. Lesson 004 defined a TTL for DNS records, and it's the same idea with the same sting: for the length of the TTL, you have promised yourself you will not check. Marlow learned what that costs when an address record with an 86,400 second TTL kept orders landing on the old box all through the following day.

Eviction is the cache running out of room and throwing something away to make space for something newer. It happens whether or not your entry was still fresh, and you did not ask for it.

You control expiry. You do not really control eviction. Most of the surprising behaviour in a cache lives in that gap.

Marlow's hit rate, at last

Lesson 001 ended with the founder putting a cache in front of book pages the week after the podcast Friday. Seven lessons later, nobody has said how well it works.

Here it is. The key is the ISBN, the value is the rendered body of the book page, about 12 kilobytes of HTML, and the TTL is ten minutes because ten minutes felt right at the time. During Christmas week the measured hit rate, the share of lookups that find what they're looking for, is 94%.

On the face of it 94% is absurd. There are 1.2 million titles. Christmas week runs 400 requests a second, of which 96% are pages, so about 384 page requests a second. Spread those evenly across the catalogue and each title comes up once every 3,125 seconds, which is fifty two minutes, so a ten minute TTL would catch almost none of them. The hit rate would round to zero.

It's 94% because traffic is never even. A few thousand titles carry most of a bookshop's day, and during Christmas week it's worse, because everybody is buying from the same handful of lists.

Now run the arithmetic the other way, which is the useful direction. If 6% of 384 requests miss, that's about 23 misses a second. Every miss writes an entry. Every entry lives ten minutes. So at any moment the cache is holding roughly:

live entries = misses per second  x  TTL in seconds
             = 23  x  600
             = 13,800 entries

memory       = 13,800  x  12 KB
             = about 166 MB

Keep that formula. It sizes a cache without guessing, and it prices a TTL. Double the TTL to twenty minutes and the memory heads for double, though not quite, because the longer life also raises the hit rate, and fewer misses means fewer new entries. You are buying hit rate with memory and paying for it in staleness, at a rate you can actually compute.

Marlow's is not a big cache. A hundred and sixty six megabytes of HTML is holding up a Christmas.

The number is on the other side of the subtraction

The question that gets asked in code review: how much faster is a request with the cache?

Before the cache existed, lesson 001 measured a book page at about 5 milliseconds of box time. With the cache in the path a hit costs about 2 milliseconds, which is the web framework, the socket, and a hash lookup that barely registers on lesson 002's ladder. A miss costs about 6: the 5 the page always cost, plus the lookup that found nothing and the write back.

Average box time per page at a hit rate of h is 2h + 6(1 - h). Work it out at a few values:

Look at the two right hand columns. Between 90% and 99% the average request improves by 15%, a number that loses arguments in planning meetings. Over the same two rows, the traffic reaching Postgres falls by a factor of ten.

The average is measuring the wrong thing. A cache's real output is the load it takes off the origin, which lives on the other side of the subtraction: not the hit rate, the miss rate. Going from 90% to 95% sounds like five points of nothing and halves your database's work. From 99% to 99.5% halves it again.

Put Marlow's numbers against a ceiling and it stops being abstract. Lesson 005 measured the pair of boxes at about 260 book pages a second, and lesson 006 read that as the rate at which pages can actually reach Postgres, which has never left box A. Christmas week offers 384 pages a second. Without the cache, the shop is being asked for 148% of what it can serve, which is the podcast Friday of lesson 001 all over again. With the cache at 94%, the database sees 23 pages a second, under a tenth of that ceiling. The rest of the ceiling is spoken for: lesson 006's other 4% is 16 full text searches a second at 60 milliseconds each, close to a full second of work every second, most of it inside Postgres, and no cache will ever touch it.

One thing the cache did not buy: the tail.

At a 94% hit rate, six requests in a hundred take the miss path. The 95th percentile book page is a miss. So is the 99th. The cache moved the typical request from 5 milliseconds to 2 and left the slow ones a millisecond worse than it found them. Lesson 002 spent a section on why the typical request is not the one that loses you a customer, and a cache is the purest example of a change that buys the median and leaves the tail alone. Your p99 is your miss path, right up until the hit rate passes 99%.

Where the copy sits, and what the distance costs

Four places to keep a copy, ordered by how far they sit from the thing that made it.

Reading down, each row is faster for the client and less controllable for you. An in-process lookup is a hash table read, effectively free. A shared store like Redis or Memcached costs a network round trip inside the data centre, half a millisecond on lesson 002's ladder, twenty times cheaper than a spinning disk seek and thousands of times dearer than the dictionary above it. An edge cache serves from the customer's own city and lesson 022 owns it. A browser cache answers before a packet leaves the laptop.

In exactly the same order, your ability to change your mind disappears. Clearing an in-process dictionary is a line of code. Deleting a key from Redis is a command. Purging a CDN is a request you make and then hope about. A copy sitting in a stranger's browser cannot be touched at all until its TTL runs out, which is why the header you set on a static asset is a promise with no take-backs. Staleness is the price of distance.

Marlow's cache has walked the first two rows.

It started as a dictionary inside the application process, on the one box the shop had. That's what a founder builds in an afternoon and it was the right call. Then lesson 005's second server arrived in September, and the shop had two caches that had never heard of each other.

Lesson 005 listed three things that broke that week: sessions in process memory, cover uploads on local disk, and the payout cron running twice. The cache was a fourth and nobody wrote it down, because it didn't break. Both boxes served correct pages. Both had their own cold start after every deploy. A title cached on box A was a miss on box B the first time round robin DNS sent the same customer there. Lesson 007 called this shape derived per box state: it never errors, it only makes your boxes quietly different from each other, and it survives longest because losing it is invisible.

Two caches means the shop stored the same 12 kilobyte fragment twice, and each box only warmed from the half of the traffic it happened to see.

In February the cache moved into a small managed Redis, and the fleet hit rate went from 94% to 96%. Two points. Price it at the Christmas volume this lesson keeps using, 384 pages a second, and 6% becomes 4%: about 15 misses a second instead of 23, a third of the database's page load gone because two caches became one. Nobody would have approved that work if it had been costed as "two percent".

The cache that quietly got smaller

The shared cache got 256 megabytes, comfortably over the 166 the arithmetic asked for, and the founder stopped thinking about it.

In March the hit rate fell to 88% over about a week. Nothing had been deployed. No errors appeared. Book pages got slower in a way that showed up as a shrug rather than a ticket. Against the same 384 a second that 12% is 46 misses instead of February's 15, three times the database work from a shop selling exactly as many books as before.

A search engine crawler had discovered the catalogue and was walking it at about forty distinct ISBNs a second. Over a ten minute window that's 24,000 entries, 288 megabytes of pages no human will ask for again this month, all of them freshly written and therefore all of them looking recently used. The robot's ten minutes did not fit in the 256 megabyte cache on their own, never mind alongside the shop's.

So it started throwing things out. Which things is the job of the eviction policy, and the near universal default is LRU, least recently used: when there's no room, discard whatever has gone longest without being read. LRU is cheap and it approximates what you actually want, which is to keep whatever will be asked for again.

It has one classic hole and the crawler drove straight through it. A sequential walk through a large keyspace looks, to LRU, exactly like a burst of wildly popular new content. Every entry is brand new. Nothing has aged. So the robot's garbage evicted the shop's bestsellers, one at a time, all week.

Give a cache less memory than its working set and it does not fail. It gets quieter, and then something downstream that was sized against the old miss rate falls over. Alarm on misses rather than hits: 96 to 88 looks like a rounding error on a dashboard, and the same week drawn as misses is a line going up threefold. Lesson 026 owns making that visible.

The stampede

Back to the Tuesday morning, with the mechanism named.

A cache stampede, also called a thundering herd, is what happens when one entry expires and every request that wanted it goes to the origin at once, because none of them can see that the others are already on their way. The naive read path makes it inevitable:

def gift_ranking():
    rows = cache.get("gifts:top")
    if rows is None:              # all nine of them land here
        rows = db.top_titles_last_7_days()   # 900 ms
        cache.set("gifts:top", rows, ttl=60)
    return rows

The size of the herd is arrival rate times rebuild time. Ten requests a second to a box, a 900 millisecond rebuild, nine in the herd. Nine concurrent copies of the same aggregation are slower than one, so the rebuild stretches to a few seconds, so thirty more arrive and join, and now thirty nine of that box's forty eight workers are asleep on the same query. The hard ceiling is the connection pool: lesson 006 established four application processes of twelve workers on each box, 48 in flight per box, 96 of Postgres's 100 connections across the pair. Reach it and the shop has no workers left for anything at all, which is how one category page took the site down with it.

Then it ends, all at once. The first aggregation to finish writes the entry, every request after that is a hit, and the box is instantly well. Sixty seconds later its entry expires again.

That self-healing is why the failure repeated instead of staying down, and why it was so hard to see. Every sample the founder's monitoring took landed somewhere in a sixty second cycle, and averaged across a minute, everything looked survivable.

Lesson 007 found a POPULAR counter in Marlow's code feeding the "moving this week" strip on the home page: an in-process tally that each box kept for itself, disagreeing with its neighbour forever. It was wrong all Christmas and it never cost the shop a second of downtime, because reading it was free. The correct, expensive, properly cached number is the one that took the site off the internet.

The load balancer lesson 006 installed in January would not have saved them either. The boxes expire on their own clocks, so shifting the gift page's queue to the other one only makes that box's next herd bigger. Two boxes running the same bug against the same key are one failure with two clocks, and 006's fleet-correlated failure has no healthy box to move to.

Four things fix a stampede, and they fix different stampedes.

Let only one rebuild run. The first miss takes a lock, computes and writes; everybody else waits for it, or better, gets served the copy that just expired while that one rebuild happens behind them. Serving slightly stale data on purpose during a refresh is the highest value line of code in most caching layers.

Refresh before expiry. Nothing has to expire at a moment if a background job recomputes it at second fifty of every minute, and the front door then never sees a miss.

Jitter the TTL, and understand what it does. Adding a random spread to expiry times does nothing for the gift page, because there is exactly one key and one expiry. Jitter fixes a different stampede: thirteen thousand entries all written in the same minute after a restart, all expiring in the same minute ten minutes later. That one is real and jitter is the whole fix.

Precompute it. A number that takes 900 milliseconds and changes slowly does not belong on the read path at all. The founder's cron job was not a workaround, it was the design that should have been there from the start.

When the read is a decision

Everything so far has treated a cache as a performance tool. Here's the part that decides whether you get to keep your job.

Lesson 003 mentioned a Marlow bug in passing: a stale stock count served for a day, every request a clean 200 in 8 milliseconds, and the shop sold 40 copies of a book it had 12 of. Perfect availability, no correctness, a week of apology emails.

Caching the stock count was never the mistake. The checkout handler reading that cached number and deciding with it was. A cache is safe wherever a read is a suggestion and dangerous wherever a read is a decision. Showing "3 left" on a catalogue page from a copy a minute old is fine, and every shop on the internet does it. Deciding whether this customer may have the last one needs a row, a transaction and a database allowed to say no. Lesson 015 owns that mechanism.

Stagefront, this course's stadium ticketing service, lives on exactly that line. Two hundred thousand people load the same seat map in the same minute at 10:00, and building it is expensive, so it's cached with a ten second TTL: the database builds it six times a minute rather than two hundred thousand. Every one of those maps is out of date before it renders, and that's fine, because clicking a seat does not buy it. The click goes to the database, which holds the seat or refuses. Cached map, authoritative write. Turn that boundary around and you have sold one seat twice, which lesson 007 already established is a lawsuit rather than a bug.

Galewatch, which collects readings from nine hundred wind turbines, has a read you cannot cache at any TTL. Lesson 003 had an engineer looking at a green tile for a turbine that had been feathered since eleven that morning. Freshness is the whole product there, so sixty seconds of cache is sixty seconds of lying about a machine somebody may be standing next to. The year-long report on the same site can be cached until the heat death of the sun, because last March has made up its mind.

Ask what breaks if this answer is five minutes old, and who finds out. What it costs to compute is the easy half of the question.

The morning it becomes load-bearing

The managed cache restarted for the first time on a Tuesday in March at 04:10, during a maintenance window the founder had clicked through without reading. Nothing happened. Traffic at four in the morning is around 40 requests a second, every one of them a miss, and 40 is comfortably under the 260 the pair can serve uncached. The cache refilled inside a few minutes and no customer ever knew.

The founder now believes a cache restart is free. Run the same restart at 11:00 on the Tuesday before Christmas and the shop is offered 384 pages a second against an origin that can serve 260.

That is not "slower". Lesson 001's queueing arithmetic is unforgiving: when the arrival rate is above the service rate there is no steady state at all, only a queue growing until something times out. Worse, the requests that would refill the cache are the ones timing out, because a miss writes an entry only if it completes. A cold cache under load above the origin's ceiling can stay cold.

Somewhere between those two mornings the cache stopped being an optimisation and became a component. The test is one line of arithmetic: add what your cache absorbs to what your origin already carries, and if the total is above what the origin can serve, your cache is a dependency. It belongs in lesson 003's chain of things that multiply together to give you your availability, and it needs an alert and a plan for the restart you have not had yet.

Almost nobody does this, because a cache goes in as a performance fix, and performance fixes do not get pagers. Marlow's had no alert on it at all.

Lesson 007 asked of any shared store what's in there that exists nowhere else. Marlow's cache holds no only copies; every entry can be rebuilt from Postgres. The data is safe to lose. The capacity is not, and those are different questions with different answers, which is why "it's only a cache" is a sentence worth being suspicious of.

Recap

A cache is a copy plus a rule for when to stop believing it. Anyone can keep a copy; the rule is where the engineering and the failures live. It pays only when the same answer is asked for twice before it goes stale.

The number that matters is the miss rate. Hit rate is how it gets reported and it flatters you. Marlow at 94% sends the database 23 pages a second out of 384, and moving to 96% sounds like two points while removing a third of that load. Read the column that says what still reaches the origin.

A cache buys your median and leaves your tail. At a 94% hit rate the 95th and 99th percentile requests are both misses, and a miss now costs a millisecond more than it did before the cache existed.

Live entries are the miss rate times the TTL. Marlow's 23 misses a second at a ten minute TTL, 12 kilobytes an entry, is 166 megabytes. One cache sizing question you can answer with arithmetic instead of opinion.

Staleness is the price of distance. In the process, in a shared store, at the edge, in a browser: each step out is faster to read and harder to correct, and the copy in a stranger's browser cannot be recalled at all.

The herd is arrival rate times rebuild time. One expiry, nine identical nine hundred millisecond queries, then thirty nine, then every worker the box has. It heals itself the moment the first rebuild lands, which is why it returns a minute later and why the averages look fine.

A cached read is a suggestion; a decision needs the row. Marlow sold 40 copies of a book it had 12 of because a checkout believed a cache. Stagefront serves a stale seat map to two hundred thousand people on purpose and lets only the database say yes.

A cache you cannot survive losing has stopped being an optimisation. Once the offered load is above what your origin can serve, the cache is in your availability chain, and a cold start at 11am on the busiest Tuesday of the year is an outage rather than a slow patch.

Check your understanding

1. Marlow's book page cache runs at 94% with a ten minute TTL and 23 misses a second. The founder wants to halve the database's page load without buying hardware. Give two changes that would do it, say what each costs in memory or in staleness, and say which you would ship first.

2. A service caches a response that takes 400 milliseconds to build and gets 50 requests a second for it. Work out the herd at each expiry, then what it becomes if the rebuild slows to 2 seconds under load, and where it stops growing.

3. Your hit rate has been 97% for six months. This morning it's 91% and nothing was deployed. List what could cause that, and say which one you would rule out first and how.

4. Take Stagefront's ten second seat map and argue the other side: what would have to be true for ten seconds to be unacceptable, and what would you cache instead if it were.

5. An engineer proposes caching an authorization check for five minutes to save a database lookup. Using lesson 007's framing of a token as a cached decision, say what you would ask before agreeing and what number would settle it.

Next lesson

009 Cache Invalidation and the Cost of Being Wrong. Today's lesson let entries die on a timer and treated the staleness in between as a price you pay knowingly; next lesson goes after the entries that need to die the moment the underlying data changes, and works out what it costs to be wrong when they don't.