Why and where to cache
Open in the interactive app: practice, quiz, mock interview →In one minute
- A cache is a small, fast copy of data kept closer to whoever reads it, so most reads avoid a slower, more expensive trip to the source of truth.
- Caching only works because access is skewed and repetitive: a few keys get most of the reads (temporal locality), and nearby data tends to be read together (spatial locality).
- The number that matters is the miss ratio, not the hit ratio. Average latency is
hit_time + miss_ratio x miss_penalty, so going from 98% to 99% hits halves the load on the source. - Every cache trades freshness and memory for speed. Before adding one, decide how stale an answer may be, what the key must include, and what happens when the cache is empty.
- The same idea appears at every layer of a computer, from CPU cache lines to the OS page cache, database buffer pools, Redis, CDNs, DNS resolvers and the prompt cache in front of an LLM.
How it works
A copy, kept close
Every read has a source of truth: a row on disk, an object in a bucket, a response computed by a service. Reading it costs time (seeks, round trips, query planning, inference) and capacity (connections, CPU, IOPS). A cache keeps copies of recent answers in a faster medium, usually RAM closer to the reader, and answers repeat questions from them.
Being a copy explains everything else. It is smaller than the source, so something must decide what to keep (eviction). It can be out of date, so something must bound staleness (expiry and invalidation). And it can vanish at any moment, so the system must stay correct, just slower, when the cache is empty.
Why it works at all: locality and skew
If every key were equally likely, a cache holding 10% of the data would answer 10% of reads. Real workloads are heavily skewed. Product views, profiles, video segments and DNS names often follow a Zipf-like curve, where the k-th most popular item is read in proportion to 1/k^s with s near 1. Under that curve a cache holding 1% of 20 million keys serves roughly 70% of reads.
Temporal locality means something read now is likely to be read again soon. Spatial locality means data next to it is likely to be read next, which is why CPUs fetch 64-byte lines, the kernel reads ahead file pages and a CDN prefetches the next chunk of a stream. The set of items touched in a time window is the working set. If it fits, the hit ratio is high and stable; if it is slightly larger, the hit ratio can collapse, because a loop over N+1 items through an LRU cache of size N misses every time.
The arithmetic of hits and misses
Average access time is hit_time + miss_ratio x miss_penalty. With a 0.5 ms Redis hit and a 20 ms query, 90% hits average 2.5 ms and 99% average 0.7 ms. For capacity, the load reaching the source is reads x miss_ratio: at 50,000 reads per second, 5,000 queries at 90% hits and 500 at 99%. Frame caching in misses, because each point near the top of the curve is worth far more than one near the bottom.
Caches stack: browser, CDN, in-process map, Redis, database buffer pool. Each layer sees only the misses of the layer above, a colder and flatter slice of traffic, so a lower hit ratio deeper down is expected rather than a tuning failure.
Deciding what to cache
Good candidates are read far more than written, expensive to produce, tolerant of some staleness, and have a hot set that fits in memory: sessions, rendered pages, permission checks, feature flags, geocoding results. Poor candidates are values used to make irreversible decisions, such as a balance that authorises spending or stock counts that decide whether to sell.
The cache key must include every input that changes the answer. Forget the locale and a French user sees German prices; forget the tenant or auth scope and one customer sees another's data. HTTP encodes this as the Vary header, which lists the request headers a stored response depends on (RFC 9111), and many real cache incidents are key bugs rather than staleness bugs.
The same problem shape elsewhere
Caching is the "finding things fast" and "hot spots" shapes together. An AI platform meets it when it reuses the computed prefix of a long system prompt: provider prompt caches key on the exact prefix bytes, expire after a time to live and charge less for a hit, so the same questions apply. Anthropic's API, for example, needs a 100% identical prefix, keeps entries for 5 minutes by default (1 hour at extra cost) and bills a cache read at a fraction of the normal input price, typically a tenth (Anthropic docs). What must the key include, how long is a hit valid, and what does a miss cost?
Down the stack
Layer 1The contract
A cache promises less than people assume. A hit returns a value that was correct at some point within a staleness bound (a TTL, or the lag of an invalidation pipeline), and a lookup is much faster than the source. It does not promise that a key written a moment ago is still there: entries are evicted, expired, lost on restart or moved by resharding. It does not promise read-your-writes unless the write path touches the same cache the reader uses. A testable statement reads like: "p99 hit under 1 ms, staleness under 60 seconds, and the database survives 100% misses at 30% of peak."
Layer 2The mechanism
Every cache is a lookup structure plus per-entry metadata. A CPU cache is set-associative: an address splits into tag, set index and offset, and the hardware compares the tag against all 8 to 12 ways of one set in parallel. Linux keeps file pages in a per-file xarray at address_space.i_pages, so a read() of a cached page is a tree lookup and a copy. PostgreSQL's shared_buffers is an array of 8 KB buffers found through a hash table keyed on relation, fork and block number, each with a pin count and usage count. Redis stores a 24-bit access clock, or for LFU a 16-bit decay time plus an 8-bit logarithmic counter, in each object header (Redis source). It evicts without a separate list by sampling maxmemory-samples keys (5 by default) and evicting the best candidate (Redis docs). Caches differ far more in this metadata (recency, frequency, reference bits, expiry, dirty flags) than in their lookup structures. Which metadata pays off is an empirical question: a study of 153 production cache clusters at Twitter found many workloads more write-heavy than textbooks assume, TTLs that defined the working set, and FIFO doing as well as LRU on many of them (Yang et al.).
Mattson's stack algorithm (1970) is the standard tool for reasoning about size. For each access it records the stack distance: one plus the number of distinct keys touched since the previous access to the same key. An LRU cache of capacity C hits exactly when that distance is at most C, so one pass over a trace yields the hit ratio for every size, the miss-ratio curve. Exact tracking is too heavy to run in production, but sampling a hashed subset of keys works: SHARDS builds curves in 1 MB of memory with average miss-ratio error under 0.01 (Waldspurger et al.).
Layer 3The machine
The latency gaps span six orders of magnitude. An L1 hit is about 1 ns, L2 about 4 ns, L3 10 to 20 ns, DRAM 80 to 100 ns, an NVMe random read 50 to 100 us, a same-datacenter round trip 0.2 to 0.5 ms, and a cross-continent one 70 to 150 ms. A Redis GET spends a few microseconds in the server; nearly all of its 0.3 ms is the network.
Granularity matters as much as speed. CPUs move 64-byte lines, so two threads writing different variables in one line bounce it between cores (false sharing), and a scattered linked list misses where an array streams. The kernel caches 4 KiB pages, so one cold byte costs a page read; a database caches 8 KB or 16 KB pages, so a row's neighbours come free. The transfer unit sets how much spatial locality a cache can exploit and how much memory it wastes when there is none.
Why it's built this way
- Fast storage is small and expensive per byte, slow storage large and cheap, so systems put a little fast memory in front of a lot of slow memory.
- Access is skewed, so a small fast tier absorbs most reads.
- The fast tier cannot hold everything, so it evicts, and it holds copies, so it needs a staleness bound.
- Every copy can be rebuilt from the source, so caches may forget, which is what makes them cheap to run.
Diagram
flowchart LR R[Request] --> L1["In-process map (~1 us)"] L1 -->|hit| A[Answer] L1 -->|miss| RD["Redis (~0.3 ms)"] RD -->|hit| F1[Fill in-process map] F1 --> A RD -->|miss| DB["Database (~20 ms)"] DB --> F2[Fill Redis and map] F2 --> A
Worked example
A catalogue service handles 40,000 reads per second at peak; the database sustains 3,000 queries per second. There are 20 million products averaging 3 KB.
The miss budget is 3,000 / 40,000, at most 7.5%, so with headroom we target 2%. Replaying a day of logs through the stack-distance algorithm gives the curve: 1 million products (3 GB) miss 6%, 2 million (6 GB) 2.5%, 4 million (12 GB) 1.8%, 8 million (24 GB) 1.5%. The curve flattens because the long tail is read too rarely for any cache to help, so we pick 4 million, about 15 GB with key and allocator overhead.
At 1.8% misses the database sees 720 queries per second and average latency is 0.3 + 0.018 x 20 = 0.66 ms. Add an in-process map of the top 20,000 products (60 MB per server, 5-second TTL) that catches 40% of reads at 1 us. Every request pays that lookup, and Redis now misses 3% of the colder traffic it sees (still 1.8% of all reads), so latency is 0.001 + 0.6 x (0.3 + 0.03 x 20), about 0.54 ms, and Redis load drops by 40%.
The empty-cache test: after a full flush the database would see 40,000 queries per second, thirteen times its capacity. Amazon calls a service in this state "addicted to its cache" and advises running load tests with caches disabled to prove the safeguards work (AWS Builders' Library). The design therefore also needs warming and a rate limit on the miss path, covered in the cache warming and stampede lessons.
In the wild
- Valve, 2015: a cache key without the user in it. On 25 December, with Steam Store traffic 2,000% above a typical sale because of a DoS attack, Valve deployed a second caching configuration that wrongly cached pages for logged-in users. For about 90 minutes, store pages for some 34,000 users, including billing addresses and partial card numbers, could be served to other people. Valve shut the store, deployed a corrected configuration and purged edge caches before reopening (Valve).
- Facebook, 2013: leases against stale sets and thundering herds. Facebook's memcached tier issues a lease token on a miss and refuses a later set if the key was deleted in between, which stops a slow reader from writing back stale data. The same leases limit each key to one refill every 10 seconds, so other readers wait briefly instead of all hitting the database; on herd-prone keys this cut peak database queries from 17,000 to 1,300 per second (Nishtala et al.).
- Slack, 2022: the cache was load-bearing. A Consul agent rollout pulled memcached nodes out of service and replacements came up empty. Misses on group DM membership fanned out to every database shard, the database could not refill the cache, and retries kept it overloaded, so many users could not load Slack that morning. Slack moved the query to a channel-sharded table and audited other queries that only worked while the cache was warm (Slack).
Trade-offs
| Option | Strengths | Weaknesses | Choose when |
|---|---|---|---|
| In-process cache | Microsecond reads, no network | Copy per server, per-server staleness, app heap | Tiny hot sets, config |
| Shared remote cache (Redis, Memcached) | One copy per key, survives deploys, large | Network hop, another system to run | Shared data across a fleet |
| CDN or HTTP cache | Removes origin traffic, close to users | Public or carefully keyed content, purge delay | Static assets, public pages |
| Database buffer pool only | No extra system, always consistent | Still pays query parsing and connection cost | Working set fits in DB memory, modest QPS |
| No cache | Simplest, always fresh | Source carries full load | Write-heavy data, or staleness is harmful |
Pitfalls in production
- Keys missing an input. A response cached without tenant, locale or permission scope leaks data. Build keys in one function that takes every input, and test that two users never share an entry.
- Watching the wrong ratio. 97% hits looks fine until you notice misses tripled from last week's 99%. Alert on miss rate and source load.
- A working set slightly larger than the cache. Hit ratio collapses instead of degrading gently. Size from the miss-ratio curve with margin and keep scans out of the cache.
- Caching what is cheap. A 0.2 ms primary-key lookup behind a 0.3 ms hop gets slower and gains a staleness bug. Cache expensive answers.
- Treating the cache as storage. Data written only to a cache disappears on eviction or restart. If it must survive, it belongs in a database.
- A cache that refuses writes when full. Redis's default
maxmemory-policyisnoeviction, which returns errors on writes at the memory limit instead of evicting (redis.conf). For a pure cache, setmaxmemoryandallkeys-lruorallkeys-lfuexplicitly.
Leadership lens
- Ask for the miss-ratio curve before approving cache memory; doubling a cache on the flat part of the curve buys nothing.
- Make the staleness budget an explicit product decision per data type.
- Require a tested answer to "what happens if this cache is empty at peak", because a cache the source cannot survive without is a hidden single point of failure. Marc Brooker calls this the cache's second mode: the system is stable at a high hit ratio and collapses at a low one (Brooker).
- Treat caches as dependencies with owners, dashboards and on-call, not free performance.
Check yourself
Your cache's hit ratio rises from 95% to 98%. By what factor does load on the database fall?
Show answer
Misses go from 5% to 2% of reads, so database load falls by a factor of 2.5.
Why can an LRU cache of 1,000 entries get no hits on a loop over 1,001 keys?
Show answer
Every key's stack distance is 1,001, one more than the capacity, so each key is evicted just before it is read again.
A deeper cache layer has a 60% hit ratio while the layer above has 95%. Is the deeper one badly tuned?
Show answer
Not necessarily. It only sees the 5% that missed above, the colder and flatter tail, so a lower hit ratio is expected.
Why do CPUs fetch 64 bytes when a program reads 4?
Show answer
Spatial locality: neighbouring bytes are likely to be read next, and a line costs about the same as a word because the trip to memory dominates.
Sources and further study
Primary
- Nishtala et al., Scaling Memcache at Facebook (NSDI 2013): look-aside caching at billions of requests per second, leases, and invalidation from the commit log.
- Yang, Yue and Rashmi, A large scale analysis of hundreds of in-memory cache clusters at Twitter (OSDI 2020): what real cache workloads look like, with traces released.
- Waldspurger et al., Efficient MRC Construction with SHARDS (FAST 2015): cheap miss-ratio curves by sampling.
Systems docs
- Redis: Key eviction: the eviction policies, approximated LRU, LFU counters and the newer LRM policy.
- Linux kernel: Memory management concepts: the page cache and how file pages are cached and reclaimed.
- Anthropic: Prompt caching: prefix-keyed caching with TTLs and per-hit pricing, the same trade-offs in an LLM API.
Books
- Understanding Distributed Systems, Roberto Vitillo, chapters "HTTP caching" and "Caching": policies, local versus external caches, and the thundering-herd risk.
- Systems Performance (2nd edition), Brendan Gregg, chapters 6 "CPUs", 7 "Memory" and 8 "File Systems": CPU caches, the page cache and file system caching, with the tools to observe them.
Other curricula
- Azure Architecture Center: Cache-Aside pattern: frames caching as load-on-demand with explicit expiry and invalidation, and warns about consistency with the store.
- donnemartin/system-design-primer: walks through cache locations (client, CDN, web server, database, application) and update strategies at survey depth.
Watch
- Cache Systems Every Developer Should Know (ByteByteGo): a tour of caches from CPU to CDN.
- Basic Caching Techniques Explained (Hussein Nasser): spatial and temporal locality and where they show up in backend systems.
Free resources
- What Every Programmer Should Know About Memory (Ulrich Drepper): CPU caches, lines and associativity in depth.
- Latency numbers every programmer should know: the order-of-magnitude gaps that make caching worth doing.
- Caching challenges and strategies (AWS Builders' Library): how Amazon reasons about cache sizing, cold starts and dependence on caches.
- Caches, modes, and unstable systems (Marc Brooker): why a system that relies on a cache's hit ratio has a dangerous second mode.
- RFC 9111: HTTP Caching: the precise rules for freshness, validation and cache keys on the web.