Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
Who this mechanism is for: a developer who writes code, calls APIs, knows basic SQL and has probably put a cache (such as Redis or Memcached) in front of a database at least once. You do not need any database-internals knowledge. Every technical term is explained the first time it appears, and again in the glossary at the end. This mechanism shows that a cache is not "a faster place to keep data". It is a second copy with its own mathematics, its own failure modes and its own hidden costs.
The story we will follow
Ifeoma Okafor is a backend engineer at Dawnpost, an online newspaper. Dawnpost publishes about 400 articles a day and serves about 20 million page views a day. Articles live in a Postgres database. In front of it sits a cache (the "article cache"), and in front of that a CDN (a network of servers that keep copies of web pages close to readers). Behind the newsroom is a second system: an analytics warehouse. Reader events are stored as Parquet files (a column-oriented file format) in cloud object storage, and editors run SQL dashboards over them. Her lead, Mateus Silva, reviews every design.
Over one busy season Ifeoma will meet six problems, one at the start of each article below. Each problem looks like a bug: a stale headline, a cache that does nothing when it is doubled, a dashboard that was fast last week, a database that falls over. Each one is actually a consequence of arithmetic about caches. At the end of each article we go back to Ifeoma and solve her problem with the mechanisms of that article.
This is the main idea of this whole mechanism:
How this mechanism is organized
- 1
The second copy
What exactly is a cache, why can it be stale, and what two inequalities control the whole subject?
CaseThe stale headline and the cold restart
- 2
What makes data cacheable
How do you measure whether a workload can be cached at all, and how big the cache must be?
CaseDoubling the cache did nothing
- 3
The derivation ladder
Should you cache raw files, metadata, query results, materialized views or "misses"?
CaseThe result cache that stopped working
- 4
Keeping it honest
How do you bound how wrong the cache can be, and survive the moment an entry disappears?
CaseThe 09:00 stampede and the missing correction
- 5
Making it fit
Which entries do you admit, which do you throw out, and how do you spread a cache over many machines?
CaseThe nightly crawl and the viral article
- 6
What caching forbids
What does caching forbid, what are the escapes, and what does each escape cost?
CaseThe design review
After that: a summary, hands-on labs, interview questions and a glossary.
One request: do not skip the formulas. They are short, and each one replaces an experiment you would otherwise run on production.
What do I do, and what does each option cost?
Size a cache
Before buying cache capacity: measure reuse, find out whether the cache must grow with the data, size to just past a knee, check each tier pays, and check the percentile you promised.
DesignChoose what to cache
Something is slow and a cache could help: cache file blocks, metadata, final results, a materialized view, overlapping fragments, or the absence of a key? Two checks and five questions lead to one of six choices.
ChooseKeep a cache honest
A cache sits in front of data that changes: decide how writes reach it, how stale an entry may get, and how to stop expiry and restarts from flooding the store behind it.
Design
Can I see it myself?
Measure leverage and the cost of a cold restart
See that hit rate is leverage, and that a restart is a load spike on the layer below.
SimulatePython with NumPyDraw a miss-ratio curve with SHARDS-style sampling
Check that one pass over a trace gives the miss ratio for every LRU size, and that key sampling is accurate.
SimulatePython with NumPy, numbaFind the plateau and the knee
See that adding cache memory can do nothing, then a lot.
SimulatePython with NumPyNegative cache and Bloom filter
Measure the effect of absent-key lookups and the false-positive rate of a Bloom filter.
MeasurePythonThe race between a reader and a writer: update versus delete
Use two threads and a dictionary as the "cache" plus a second dictionary as the "store".
Break itPythonStampede with and without protection
Write a small Python program with a fake "database" function that sleeps 2 seconds and counts how many times it is called.
SimulatePythonScan resistance: LRU against an admission filter
Generate a Zipf-distributed request stream (alpha = 1) over 100,000 keys with numpy.random.zipf or a precomputed cumulative table, 2 million requests, cache size C = 5,000.
SimulatePython with NumPy
Can I reason about it under questioning?
Interview questions
Short questions on caching that an interviewer might ask, each with an answer you could give aloud and a link to the full explanation.
Scenarios
Longer caching problems of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.
The tensions this mechanism takes a position on. Each recurs across mechanisms.
Latency vs. throughput
For example: batching, group commit, micro-batch.
Read-optimized vs. write-optimized
For example: B-tree vs. LSM, merge-on-read vs. copy-on-write.
Space vs. time
For example: compression, indexing, materialization, caching.
Consistency vs. availability vs. latency
For example: quorums, replication modes.
Precompute vs. compute-on-read
For example: materialized views, ELT vs. ETL, schema-on-read.
Show all 11 trade-offsShow fewer
Isolation vs. utilization
For example: multi-tenancy, resource pools, spot capacity.
Mutability vs. immutability
In-place update vs. append-only + GC; buys reproducibility and cheap concurrency, pays in space and janitorial work.
Early binding vs. late binding
When structure is committed; determines where the failure surfaces, at write time or read time.
Exactness vs. approximation
For example: sketches, sampling, ANN.
Push vs. pull
Who initiates the work.
Cost as a substitutable resource
Money buys position on every other axis; the only axis denominated in a different unit.
Ideas this mechanism meets that keep coming back, mechanism after mechanism.
Fixed cost per operation
Fixed cost per operation implies a natural batch size.
Power laws and skew
Variance costs more than volume
Variance costs more than volume.
Costs are conserved
Costs are conserved, never removed.
Undeclared dependencies
An optimization that succeeds becomes an undeclared dependency, with leverage 1/(1 − h).
Show all 12 principlesShow fewer
Immutable storage grows indirection
An immutable substrate grows an indirection layer plus a collector.
Designate one write
Atomicity over n items is atomicity over one designated item.
Sound approximations
When exactness is too expensive, use a sound approximation.
Randomization replaces coordination
Randomization can replace coordination.
Fixed capacity meets growth
A fixed-capacity structure meeting growing cardinality breaks the design.
Granularity mismatch
Granularity mismatch creates amplification.
The algebra decides
What can be skipped, pushed down, parallelized, merged or precomputed is determined by the algebra of the function, not the layout of the data.