The slate next to the stove (caching)

The second board of the System Design spine. A chai stall, a slate hanging by the stove, and the back room the wala keeps walking to. This lesson is the story of how that slate got invented, what it costs the people who hang one, and what the single number chalked on it is worth.

Before you start. You need the one move from The chai stall that got famous (load balancing): every wala at the counter was made forgetful on purpose, so any wala can serve any customer and you can hire ten more tomorrow. That move worked, and it created the problem this lesson is about, because a forgetful wala has to walk to the back room for every single answer.

The wala who keeps walking to the back room

Watch the counter for five minutes. A customer asks the price of a cutting chai. The wala walks to the back room, reads it off the register, walks back, says twelve rupees. The next customer asks the same thing. The wala walks to the back room again.

At a hundred customers an hour nobody notices. At ten thousand there is a line of walas in the corridor waiting on the same line of the same book. The register did not get slower. It just became the only thing in the stall that knows anything.

The price of chai is asked hundreds of times an hour and changes twice a year. The work is not hard, it is repeated.

So hang a slate by the stove and chalk the common answers on it.

1968: IBM hangs the first slate, and calls it a cache

The chai stall did not invent this. IBM did, in a machine announced in January 1968 called the System/360 Model 85, and their problem was the same shape. The processor, the part that does the arithmetic, could work far faster than main memory, the part that holds the data, could hand it numbers. IBM’s answer was a small fast store between the two, holding whatever had been read recently: 16 or 32 kilobytes, a few pages of text beside a main memory thousands of times larger. If the next number was already in there, main memory was never disturbed. The Model 85 was the first commercially available computer built this way, and IBM’s word for that store is the word we still use.

The slate is a cache. Finding the answer already chalked on it is a hit. Finding it blank is a miss: the slow walk to the back, then chalking the answer so the next person gets a hit.

sequenceDiagram
    participant Customer
    participant Wala as Counter wala
    participant Slate as Slate (cache)
    participant Register as Register (the slow store)
    Customer->>Wala: price of chai?
    Wala->>Slate: check the slate
    alt hit
        Slate-->>Wala: already chalked
        Wala-->>Customer: instant
    else miss
        Slate-->>Wala: blank
        Wala->>Register: walk to the back
        Register-->>Wala: the answer
        Wala->>Slate: chalk it for next time
        Wala-->>Customer: served, but slower
    end

A hit never leaves the counter. A miss pays the full walk and leaves the answer for the next person.

The one number: hit rate, the fraction that never leaves the counter

Only one number matters about a cache: the share of questions that end at the slate. That is the hit rate.

Say a hit takes half a millisecond and a miss takes forty. At a 90% hit rate the average answer takes 4.45 ms, nine times faster than no slate at all. Look at where those 4.45 milliseconds came from: 0.45 from the nine hundred hits, 4 from the hundred misses. The average is essentially the misses.

That is why the last few points of hit rate matter more than the first forty. Going from nothing to a 40% hit rate makes each answer 1.65 times faster; the five points from 90% to 95% make it 1.8 times faster again, off a far smaller number. And speed is the smaller half anyway, because the register only ever feels the misses. At ten thousand questions a second, 90% sends a thousand to the back room, 95% five hundred. Five points halved the register’s entire workload. A slate protects the register first and the customer second.

1966: the perfect rule for what to erase, and nobody can run it

A slate has three lines and the stall has hundreds of answers, so something must be rubbed out to make room. Choosing what goes is eviction.

Two years before IBM shipped the Model 85, a researcher at the same company had already worked out the right answer. László Bélády published a study of replacement algorithms in the IBM Systems Journal in 1966, and its rule is the best any cache can do: erase the line whose next request is furthest in the future. Provably optimal, and unrunnable, because it needs to know what customers will ask. You can only compute it afterwards, as a ceiling.

So everyone reaches for the cheap stand-in: erase the line unasked the longest. Engineers call it LRU, least recently used. The bet is that recently asked means soon asked again, which is true of real traffic most of the time.

Most of the time is doing work there. Take ten questions - chai, chai, chai, vada, tab, vada, lassi, chai, tab, lassi - and a slate of three lines. LRU scores 40%, oldest-first 50%, and rubbing out a line at random scores 60%, which is exactly Bélády’s unbeatable ceiling. The coin flip tied the optimum and the textbook default came last, because at the seventh question LRU rubs out chai, unheard since the third, and chai is asked next.

Bélády found the other embarrassment in 1969, with Robert Nelson and Gerald Shedler. Under the oldest-first rule a bigger cache can take more misses than a smaller one. That is Bélády’s anomaly, and on one twelve-request stream a three-line slate takes nine misses while a four-line slate takes ten. More chalk, more walking. LRU cannot do this to you, and that is its real virtue.

The slate that says yesterday’s price

Now the curse with no clean fix. Milk goes up and someone updates the register in the back room. The slate by the stove still says twelve rupees, and the wala reads it out confidently, because a slate has no way of knowing it has gone wrong. Being out of date is staleness, and there are exactly two cures.

The first is to chalk a lifetime beside each line and wipe it when the time runs out. That is a TTL, a time to live. Nobody coordinates anything, the line goes blank on schedule, and the worst you can be is one lifetime wrong. So the design question is not technical: how wrong am I allowed to be? A like count can be a minute wrong; a bank balance cannot be one second wrong, which is why that one is not cached.

The second cure is to wipe the line the moment the answer changes, which is invalidation. Always fresh, and legendarily hard for a structural reason: there is never just one slate. There is one in your app’s memory, one in a shared cache like Redis, two more in every data centre that keeps a copy of your site near its readers, and one in each reader’s own browser. The wipe must reach all of them, none acknowledges anything, and the browser cannot be reached at all. That is why web filenames carry a content hash like app.9f2c1a.js, a fingerprint of the file’s own bytes: when you cannot talk to a cache, changing the name is the only way to invalidate it.

So practice settles the same way: TTL is the guarantee, invalidation the optimisation. Set the lifetime to the longest staleness you could survive if every wipe were lost, then send wipes to make the common case fresh.

The failure the slate invents: the thundering herd

Hanging a slate creates a way to fail that did not exist before you hung it.

One popular answer is being asked ten thousand times a second, and its lifetime runs out. The next customer finds the line blank and starts the forty-millisecond walk. So does the one a tenth of a millisecond behind. Nothing has been chalked yet, so every request arriving during that walk also finds a blank slate and sets off for the back room.

flowchart LR
  T["line expires"] --> M1["request 1: blank, walks"]
  T --> M2["request 2: still blank, walks"]
  T --> M3["...400 walks in 40 ms"]
  M1 --> R["register: 400 identical questions at once"]
  M2 --> R
  M3 --> R
  R --> S["register slows down, so the walk gets longer, so more pile in"]

Four hundred identical questions hit the register at once to fetch one answer, because a timer went off. That is the thundering herd, and it feeds itself: the register slows under the load, which lengthens the walk, which lets more requests pile in behind. Systems that ran happily for months fall over the first time a popular line expires at peak.

2003: the slate everyone copied

For thirty-five years this stayed hardware and operating-system folklore, until the web got big enough to rediscover it.

In May 2003 Brad Fitzpatrick was watching the database behind LiveJournal fail under its own popularity. He wrote a small program holding answers in memory across a fleet of machines, and changed one rule: ask memory first, go to the database only as a last resort. He called it memcached and gave it away. Within a few years the large web ran on it.

The browser you are reading this in has its own slate, in front of one in a data centre near your city, in front of one in the application, in front of a database keeping one of its own inside. It is slates all the way down, and every one of them has both curses.

You now know

• A cache is a small fast copy of the answers you keep asking for, so the slow store only sees something genuinely new.
• A hit ends at the cache. A miss pays the full walk and chalks the answer on the way back.
• Hit rate is the only number that matters, and the top few points matter most, because the store only ever feels the misses.
• Eviction is choosing what to rub out. The perfect rule needs to see the future, so everyone runs LRU, and LRU can lose to a coin flip.
• Staleness has two cures. A TTL is the guarantee because it cannot be lost. Invalidation is the optimisation because it can.
• A cache invents its own failure: when a popular line expires, every request arriving during the refetch also misses, and the herd lands at once.

Stop here if you want. What follows is the same slate in numbers, for when you want to see where each of those claims comes from.

Second read: the arithmetic

Hit rate, worked. Two numbers describe a cache: a hit costs 0.5 ms to a local Redis, a miss 40 ms to a database that must plan a query and read pages. The average is the mix. Both costs are teaching values, round numbers of the usual size rather than a measurement of one system, so the shape carries over (the misses dominate) and the exact multiples in the table below do not.

avg = hit_rate × 0.5ms  +  (1 − hit_rate) × 40ms

One row by hand: at 90%, 0.9 × 0.5 = 0.45 ms of hits plus 0.1 × 40 = 4 ms of misses is 4.45 ms, and 40 ÷ 4.45 = 9×.

A miss costs 80× a hit, so the remaining misses dominate. As load, at 10,000 req/s:

90% hit  →  1,000 req/s reach the store
95% hit  →    500 req/s        (half the load, for five points)
98% hit  →    200 req/s
99% hit  →    100 req/s

Why three lines of chalk catch most questions. Real traffic is lopsided in a regular way: the most popular item is asked for about twice as often as the second, three times as often as the third, and so on down the list. That pattern is called Zipf, and written out it says the k-th item is asked about 1/k as often as the first. Total asks are then proportional to 1 + 1/2 + … + 1/N, written H(N), the top C catches H(C), and hit rate is H(C)/H(N). Writing ln for the natural logarithm, H(n) ≈ ln(n) + 0.577, so hit rate grows with the logarithm of cache size.

N = 1,000,000 distinct keys, Zipf s = 1

cache      100 keys  =  0.01% of the keyspace  →  36.0% hit rate
cache    1,000 keys  =   0.1%                  →  52.0%
cache   10,000 keys  =     1%                  →  68.0%
cache  100,000 keys  =    10%                  →  84.0%

That table is the formula at s = 1, not a measured trace; real traffic is only roughly Zipf, so a real cache’s curve has to be read off its own logs. One percent of the keys catches two thirds of the questions. That is the justification and also the bad news: every ×10 in size adds ln 10 = 2.3 to the top of that fraction and nothing to the bottom, so each ten-fold buys a fixed ~16 points, not a fixed factor. The tail never goes away. It is also why “cache everything” is wrong: a key asked once evicts something useful and is never read again.

Eviction, measured. The lab on this board (/labs/the-slate/) runs all five rules on the same ten questions:

chai, chai, chai, vada, tab, vada, lassi, chai, tab, lassi

Read one column: capacity 3. Left of it the slate is too small to matter, right of it big enough that the rules agree.

Bélády’s optimum here at capacity 3 is 60%, which random happened to match. On long real traces LRU beats random comfortably, because recency genuinely is predictive; on a short stretch it can be the wrong signal. LFU has the mirror weakness, clinging to yesterday’s crowd-pleasers.

Bélády’s anomaly, reproduced against the same simulation on the stream 1 2 3 4 1 2 5 1 2 3 4 5:

FIFO, slate of 3  →   9 misses
FIFO, slate of 4  →  10 misses     ← a BIGGER slate, MORE walks
LRU,  slate of 3  →  10 misses
LRU,  slate of 4  →   8 misses

LRU is immune because it is a stack algorithm: a size-n cache always holds a subset of what a size-n+1 cache holds. FIFO does not, so it can throw away a line a smaller cache would have kept. Production caches mostly run hybrids anyway, such as TinyLFU, which admits a new key only if an approximate frequency sketch says it beats the line it would displace.

Staleness, priced. For reads arriving at random moments after the write, average staleness is TTL/2.

TTL     worst-case staleness    average staleness
   5s              5s                  2.5s
  60s             60s                   30s
 300s            300s                  150s
3600s           3600s                 1800s

What a tiny TTL buys, for one hot key at 10,000 req/s:

TTL  1s  →  origin sees 1 fetch/s      hit rate 99.99%
TTL 10s  →  origin sees 0.1 fetch/s    hit rate 99.999%
TTL 60s  →  origin sees 0.017 fetch/s  hit rate 99.9998%

A one-second TTL removes 99.99% of the load, the most under-used move in caching.

The herd, counted. Duplicate fetches in flight during one refetch:

10,000 req/s × 0.040 s  =  400 identical queries, for one answer

The synchronised version is worse. Warm 10,000 keys in one burst with the same 60-second TTL and they all expire in the same instant. Jitter does not reduce the work, only the rate, which is all the origin cared about: 10,000 ÷ 12 s = 833/s at ±10%, 10,000 ÷ 60 s = 167/s at ±50%.

no jitter        all 10,000 expire together   →  peak 10,000 requests, instantly
TTL ±10% jitter  expiries spread over 12s     →  peak    833 req/s
TTL ±25% jitter  spread over 30s              →  peak    333 req/s
TTL ±50% jitter  spread over 60s              →  peak    167 req/s

Three fixes, in order:

1. Jitter every TTL. ttl = base × (0.75 + random()×0.5). One line, and it turns a synchronised cliff into a stream. Always do this.
2. One loader per key (singleflight). The first miss takes a lock and does the walk; the other 399 wait for its result, so 400 queries become 1. Go’s singleflight, a per-key async lock in Python, and Redis’ SET key val NX recipe are all this.
3. Refresh ahead of the cliff. Recompute early with a probability that rises as expiry approaches: now − Δ·β·ln(random()) ≥ expiry, where Δ is how long the last fetch took. Some request near expiry refreshes while the old value is still served, so the line is never blank. The only fix that removes the herd instead of shrinking it.

Reading the headers. Every field of a real response is a concept from this lesson:

$ curl -sI https://en.wikipedia.org/static/images/project-logos/enwiki.png

HTTP/2 200
etag: "1f0f-6561f14405800"
cache-control: max-age=31536000
last-modified: Wed, 08 Jul 2026 20:09:04 GMT
content-length: 7951
age: 6913
x-cache: cp5022 hit, cp5022 hit/3
x-cache-status: hit-front

• age: 6913 - this copy has sat on that cache for 6,913 s, 1.9 hours. age is exactly the staleness you are served, the number to look at when someone says the site shows old data.
• cache-control: max-age=31536000 - one year, and that instruction is for your browser, not the edge. Safe only because the URL is immutable.
• x-cache: cp5022 hit, cp5022 hit/3 - two caches on one edge host, front and back. The /3 counts how often the back one served this object since chalking it: three walks to the origin that did not happen.
• etag + last-modified - the revalidation pair. When the line expires the cache does not re-download; it asks “still 1f0f-6561f14405800?” and takes a 20-byte 304 Not Modified instead of the image.

Try it

curl -sI https://en.wikipedia.org/static/images/project-logos/enwiki.png | grep -i x-cache

Run it a few times and watch the counter after hit/ climb. Each increment is a request that ended at the edge instead of walking to Wikipedia’s origin. Now the whole envelope:

curl -sI https://en.wikipedia.org/static/images/project-logos/enwiki.png \
  | grep -iE 'age|cache-control|x-cache|etag|last-modified'

A miss with age: 0 is eviction in the wild: a hit rate is a rate, and your request is not owed one.

Then play the eviction rules against each other in the lab on this board (/labs/the-slate/). Set the slate to 3 lines and step all five through the same ten questions: watch LRU erase chai at step seven and get asked for it at step eight. Move the capacity to 4 and every rule converges. The whole argument lives in the narrow band where the slate is nearly big enough.

Go deeper

• Cloudflare - What is caching?
• AWS - caching overview
• Bélády, A study of replacement algorithms, IBM Systems Journal, 1966
• Bélády, Nelson & Shedler, An anomaly in space-time characteristics, CACM 1969
• memcached - where it came from
• Redis - client-side caching and invalidation
• Einziger, Friedman & Manes, TinyLFU
• Vattani, Chierichetti & Lowenstein - probabilistic early expiration

Related

• The chai stall that got famous (load balancing) is the move that created this problem: forgetful walas, one register, a queue in the corridor.
• The Slate, Properly (caching to real depth) takes the same board through read and write strategies, cache-aside through write-around, and a runnable singleflight.
• The order slip rail (queues & the utilization cliff) is the next bottleneck once the register is protected, and the next stop: what a queue does to waiting time as the stall fills up.

Retrieval practice

9 questions. Answer each one before you open it.