Caching
A Socratic walk-through of caching — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does a computer keep a second copy of data it already has?
Duplicating data looks like a bad trade. You spend memory you could have used for something else, and you take on the obligation of keeping two things in agreement — for data you already possess. So a second copy is only worth it if the two copies are not really equivalent. What could differ between them, if the contents are identical?
Reasoning it through
REASONING #The answer is distance, expressed as time. Storage is not one thing but a ladder, and the rungs are absurdly far apart. A register is essentially free. A hit in the first-level cache costs on the order of a nanosecond; the second level a few nanoseconds; the third level something like fifteen or twenty. Main memory is around eighty to a hundred nanoseconds. A solid-state drive is tens to hundreds of *micro*seconds. A seek on a spinning disk is several milliseconds, and a network round trip across an ocean is a hundred milliseconds or more.
Sit with those gaps. From cache to memory is roughly a hundredfold; from memory to disk, another hundred thousand-fold. A processor reaching main memory for every operand would spend nearly all its cycles waiting. Fast storage exists — it is simply small, because it is expensive and because proximity to the processor is finite.
So the second copy is not a duplicate of the data; it is a duplicate at a different price. Now the real question: why should a small fast store help at all? If access were spread uniformly over a large address space, a cache holding one percent of it would be hit one percent of the time, and would buy nothing.
It works because programs do not behave that way. They exhibit locality of reference, in two flavours. Temporal locality: something touched recently is disproportionately likely to be touched again — loop counters, the current object, the hot rows of a table. Spatial locality: something near a recent access is likely to be needed next, because arrays are walked in order and code runs forward. This is why caches move data in blocks rather than bytes, betting the neighbours will be wanted too. Locality is an empirical regularity of real workloads, not a law; a program that deliberately hops randomly through a huge array defeats every cache in the machine, and such programs exist.
Given locality, do the arithmetic. Suppose a cache access is 1 nanosecond, memory 100, and 99 of every 100 accesses hit. The average is about two nanoseconds instead of a hundred. Almost all the benefit of the fast store, at almost none of its cost — and it is the hit rate that governs, which is why a small improvement near the top end matters so much.
That raises the next question: the cache is full, and something new arrives. What leaves? The perfect choice is the item whose next use is furthest in the future — Belady's rule, which is optimal and unimplementable, because it requires knowing the future. It survives as a benchmark. Real policies are guesses at it built from the past: least-recently-used, which bets temporal locality holds; least-frequently-used, which bets on long-run popularity; random, which is cheaper than either and surprisingly hard to beat by much. Each is a hypothesis about the workload, and each has workloads that defeat it — LRU is exactly wrong for a sequential scan through data larger than the cache, which evicts everything useful and hits nothing.
And then the part that is genuinely hard. Everything above assumes the copy still matches the original. A cache is a promise, and the promise breaks the moment the underlying value changes — by another core, another server, another user. So you must decide when writes propagate (immediately, or lazily when the entry is evicted), how other holders of the same data learn that theirs is now wrong, and what happens in the window where they have not yet learned. Between cores this is a coherence protocol in hardware. Across services it is expiry times, explicit invalidation messages, and version stamps — and the failure mode is not a crash but silently serving something that is no longer true.
The analogy
THE ANALOGY #Think of a desk, a filing cabinet down the hall, and an archive across town. You keep on the desk what you have used recently and what sits near it in the folder, because the walk to the cabinet costs minutes and the trip to the archive costs a day. The desk is small, so every new document displaces an old one, and you choose what to displace by guessing what you will want next.
The paper on your desk is usually the only copy, so it cannot go stale — whereas the whole difficulty of caching is that the original can be changed by someone else while your copy sits there looking perfectly current.
Clarifying the model
THE MODEL #Three clarifications tie the reasoning together.
First, caching is not the same as buying more fast storage. The hierarchy exists because speed, capacity and cost cannot all be maximised at once; a cache is a way of getting the behaviour of a large fast store out of a small fast one, and it only works to the extent that the access pattern cooperates. Change the pattern and the same cache stops paying.
Second, a cache miss is not merely "no benefit" — it costs the lookup that failed, plus in some designs an eviction and a write-back. A cache with a poor hit rate is slower than no cache at all, which is why hit rate, not size, is the number to watch.
Third, the invalidation problem deserves its reputation — the old joke about the two hard problems in computer science names it first for a reason. Note also that many practical systems choose to be wrong for a bounded time on purpose — a short expiry accepts staleness in exchange for not having to coordinate at all. That is a legitimate design, but it is a decision about correctness, not about performance, and it should be made deliberately.
A picture of it
THE PICTURE #How to readEach bar is one rung of the storage hierarchy, and the height is the base-10 logarithm of its typical latency in nanoseconds — so every whole unit of height is a tenfold slowdown. Read the bars left to right: the first four rise gently, spanning about two orders of magnitude within the chip, and then the jump to SSD adds three more at once. The chart is drawn on a log scale precisely because on a linear one the first four bars would be invisible, which is itself the point.
What became clearer
WHAT CLEARED #A cache is not a spare copy; it is the same data purchased at a different latency, and it pays only because real programs reuse recent data and their neighbours. The hierarchy exists because fast storage is small, eviction policy exists because the future is unknown, and invalidation is hard because a cache silently converts a performance problem into a correctness problem the moment the original changes.
Where to go next
ONWARD #- Cache coherence protocols, and what it costs several cores to agree on one line of memory.
- Working-set size, and why a cache that is slightly too small can be dramatically worse.
- Cache stampedes: what happens when a popular entry expires and every request misses at once.
Key terms
TERMS #| Term | What it means |
|---|---|
| Locality of reference | the empirical tendency of programs to reuse recent data (temporal) and nearby data (spatial). |
| Hit rate | the fraction of accesses served by the cache rather than the slower level below it. |
| Eviction policy | the rule deciding which entry is discarded when the cache is full, e.g. least-recently-used. |
| Belady's optimal policy | evicting the entry whose next use is furthest away; optimal, but requires knowledge of the future. |
| Invalidation | marking or removing a cached entry once the underlying data has changed. |
| Write-back / write-through | deferring writes to the level below until eviction, versus propagating them immediately. |
Every term the collection defines is gathered in the glossary.