Part 3 · Demand

Indexes, Caches, and Serving Under Demand

Lesson 06 gave us the yardstick: reliability, scalability, and a serving promise written as an SLO — a p99 latency target, not an average. It also showed why the tail is what users feel and why fan-out amplifies it. This lesson is the first move that actually buys that promise on the read path. The data already lives in a storage engine (lessons 03–04); the question now is how to answer reads fast enough and often enough under demand. Two tools dominate: an index trades write cost and space to turn a scan into a lookup, and a cache trades freshness to turn a slow lookup into a fast one. Both are derived copies of the truth, and both make you answer a question you cannot dodge: when the copy is stale, how wrong are you allowed to be, and for how long?

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 1 (the latency / percentile framing) and Chapter 3 (indexes as access-path structures over a storage engine), combined with standard caching practice (cache-aside, write-through, stampede control, Little's Law). Original synthesis; the worked numbers, the ASCII read path, and the ML-serving framings are ours.

Linear position

Prerequisite: Lessons 03–04 (storage engines and indexes — a B-tree or LSM lookup vs a full scan, and that every index must be maintained on write) and lesson 06 (SLOs, percentiles, tail-latency amplification under fan-out). We build on "an index is a secondary structure that costs writes to save reads" and "the promise is a p99, not a mean."
New capability: Design the read path under load — choose an index by selectivity, composite-column order, and whether it can cover the query (and know its write-amplification cost); design a serving / caching layer with an explicit freshness budget — pick a cache pattern and eviction policy, compute the effective latency a hit ratio buys you, defend the cache against a stampede on a hot key, and size concurrency to a latency target with Little's Law.

The plan

Five moves. (1) The index as an access-path optimization — a read-speed-for-write-cost trade you met in storage engines — and the three design levers (selectivity, composite-column order, covering) that decide whether it actually helps. (2) Caching — why it exists, the four placement patterns (cache-aside, read-through, write-through, write-behind), eviction (LRU/LFU/TTL), and the hit-ratio → effective-latency equation with a worked number. (3) Invalidation as a derived-view freshness problem — a cache is a derived copy of the system of record, and staleness is a budget you spend on purpose. (4) The cache stampede (thundering herd) when a hot key expires, and the four fixes that tame it. (5) SLO-driven serving — Little's Law to size concurrency, the latency budget across the read path, and CDN / edge caching, tying back to lesson 06's tail.

1 · The index: an access-path optimization

What this is: a secondary structure that trades write cost and space for read speed.

You already met indexes in the storage-engine lessons, so this is a recap with a sharper name for it. A table on disk is, at bottom, a pile of rows. To find "the user with email = x" without an index you must scan the whole pile — O(n) in the number of rows. An index is a separate, ordered structure (a B-tree in lessons 03, an LSM-tree or a hash index over the same data) that maps a search key to the location of the row, turning that O(n) scan into an O(log n) lookup. The index does not hold new truth; it is a derived access path over data that already exists. That single fact carries the whole trade-off:

It costs writes. Every index must be maintained on write. Insert one row into a table with four indexes and you do five writes, not one — the row plus an update to each index. This is exactly the read/write asymmetry you saw between B-trees and LSM-trees (lessons 03 and 04): the index makes reads cheap by making writes more expensive.
It costs space. The index is a second copy of the keys (and for a covering index, of some columns too).
It can lag, when it is asynchronous. A synchronous index is updated in the same transaction as the row, so it is never stale; an asynchronous secondary index (common in search and analytics systems) is itself a derived view that lags behind the row — which is the same freshness problem the rest of this lesson is about, one layer in.

But "add an index" is not one decision — it is three, and getting any of them wrong gives you the write cost without the read speedup. These three levers are what separates a senior answer from "just add an index on that column."

Selectivity — does it narrow enough?

An index only helps if it eliminates most rows. On a column with two values (is_active) over 100M rows, looking up is_active = true still returns ~50M rows; the planner reads the index and then 50M heap rows — slower than a plain scan, so it ignores the index. Rule of thumb: an index earns its keep when a lookup returns a small fraction (say <1–5%) of the table. High-cardinality columns (user id, email) index well; low-cardinality flags usually do not.

Composite order — the leftmost-prefix rule

An index on (tenant_id, created_at) is sorted by tenant_id first, then created_at within each tenant. So it serves tenant_id = 42, and tenant_id = 42 AND created_at > X, and a range/sort on created_at within a tenant — but it is useless for created_at > X alone, because the rows for a given time are scattered across every tenant's block. Column order encodes which queries are cheap; pick it to match your access pattern (lesson 02), equality columns before the range column.

Covering — can the read skip the table?

Normally an index lookup finds a row's location, then does a second read into the heap/table to fetch the other columns. A covering index includes those columns in the index itself, so the query is answered entirely from the index — an index-only scan, no heap visit. It turns two reads into one for hot queries, at the cost of a fatter index (more space, more write amplification). This is the read-side mirror of "store the data shaped for the query" (lesson 02).

Worked number — every index is another tree to write

The cost side has a number worth holding. Each secondary index is its own B-tree (lesson 03), and a write that touches an indexed column must mutate that whole tree too. A table with a primary key plus 4 secondary indexes turns one logical INSERT into 5 tree writes — the row plus one per index — each potentially dirtying a page, splitting it, and appending to the WAL. (An UPDATE is gentler: it only re-writes the indexes whose columns actually changed — and engines like Postgres can skip all secondary-index maintenance when no indexed column is touched — so the 5× figure is the insert/worst-case ceiling, not a flat tax on every write.) So indexes are not free reads bought with nothing: at 4 secondary indexes an insert does up to 5 structures' worth of writes and 5 structures compete for the buffer cache. The discipline: index the columns your reads actually filter and sort on, make the hottest ones covering, and delete indexes no query uses — an unused index is pure write tax. This is exactly the B-tree write-amplification bill from lesson 03, now charged once per index on the serving path.

Hold that shape in mind, because a cache is the same trade pushed one layer out: an index trades write cost for read speed within the database; a cache trades freshness for read speed in front of it.

2 · Caching: why, the patterns, and the latency math

What this is: keep a fast copy of an answer so most reads never touch the slow source.

A cache is a small, fast store that holds copies of recently or frequently used answers so that most reads are served from it instead of from the slower, more expensive system of record (the database, an object store, or an upstream service). Two reasons to want one: latency (an in-memory cache hit is ~0.1–1 ms; a database read that touches disk or crosses the network is tens of ms) and offload (every request the cache absorbs is one the database never sees, so the same backend serves far more traffic). In ML serving the canonical case is a feature cache in front of a feature store, or an embedding / inference-result cache in front of a model.

The first design decision is where the cache sits relative to the reads and writes. Four patterns:

Cache-aside (lazy)

The application owns the cache. On read: check cache; on a miss, read the DB, then write the value into the cache. On write: update the DB and invalidate (or update) the cache entry. Simplest and most common. Cost: every miss pays DB latency, and the invalidation logic lives in app code.

Read-through

The cache itself knows how to fetch from the DB on a miss; the app only ever talks to the cache. Centralizes the load logic, but you depend on the cache layer's correctness and its miss behavior.

Write-through

Writes go to the cache and the DB synchronously before acking. The cache is never stale relative to the DB, but every write pays both stores' latency. Good when reads dominate and you cannot tolerate staleness.

Write-behind (write-back)

Writes go to the cache and ack immediately; the cache flushes to the DB asynchronously. Fastest writes, best absorption of write bursts — but the cache now holds unflushed truth, so a cache crash before flush loses data. The cache is briefly the system of record.

The second decision is eviction: a cache is bounded, so when it fills you must throw something out. LRU (least-recently-used) evicts the entry untouched for the longest — good for workloads with temporal locality. LFU (least-frequently-used) evicts the entry hit the fewest times — good when a stable hot set should never be displaced by a one-off scan. TTL (time-to-live) expires an entry after a fixed age regardless of use — this is your freshness lever, and it reappears in §3 and §4.

Worked number — what a hit ratio actually buys

Effective latency is just the weighted average of the hit path and the miss path:

latency = (hit_ratio × hit_latency) + (miss_ratio × miss_latency)

Take a hit at 1 ms and a miss (cache lookup + DB read) at 40 ms.
At a 95% hit ratio: 0.95 × 1 + 0.05 × 40 = 0.95 + 2.0 = 2.95 ms — call it ~3 ms.
At a 99% hit ratio: 0.99 × 1 + 0.01 × 40 = 0.99 + 0.40 = 1.39 ms.
At a 90% hit ratio: 0.90 × 1 + 0.10 × 40 = 0.90 + 4.0 = 4.9 ms.

Two things to notice. First, the misses dominate the average: at 95% hits the cache is hit 19 times for every miss, yet the misses contribute 2.0 of the 2.95 ms. Second, the last few percent of hit ratio are worth a lot — going 95% → 99% more than halves the average. And recall lesson 06: this is the mean; the user who misses still waits 40 ms, so your p99 is roughly the miss latency. A cache improves the average dramatically and the tail barely — which is why the stampede in §4 matters so much.

3 · Invalidation is a derived-view freshness problem

What this is: the cache is a derived copy of the truth, so "is it stale?" is a budget, not an accident.

"There are only two hard things in computer science: cache invalidation and naming things." The reason invalidation is hard is that a cache is a derived view of the system of record (the SoR — the database that holds the authoritative value). The moment the SoR changes, every cached copy of the old value is wrong. You have three honest ways to keep them aligned, and each is a point on a freshness/cost curve:

TTL expiry. Let the entry simply age out after, say, 60 s. Dead simple, no coupling to writes — but the cache can serve a value up to its TTL stale. The TTL is your freshness budget, made explicit: "users may see a value up to 60 s old."
Write-time invalidation. On a write to the SoR, delete (or overwrite) the cache entry. Tighter freshness, but now the write path must reliably reach the cache — and if the delete is lost (a dropped message, a crash between the two writes), you have a stale entry with no expiry to save you. This is a dual-write hazard, the same one lesson 20 dissects for all derived data.
Change-driven invalidation. Subscribe to a change feed from the SoR (a CDC stream or event log) and invalidate from it. This is the robust version — the change feed is an ordered durable log, so invalidations are not lost — and it is exactly the derived-data discipline lesson 20 argues for: keep the view correct by deriving it from the log rather than by hoping two writes both land.

Staleness is a correctness budget, not a bug

A cache with a TTL is deliberately wrong for up to one TTL. That is fine for a product description, a follower count, or a recommendation list; it is not fine for a price at checkout or an access-control decision. The design question is never "is the cache ever stale?" (yes, always) but "how stale is allowed, on which data, and what reconciles it?" Write that budget down — it is the freshness line of this lesson's Where is truth? artifact below, and it foreshadows the whole derived-data treatment in lesson 20.

4 · The cache stampede (thundering herd)

What this is: a hot key expires, every concurrent reader misses at once, and they all hit the DB together.

Here is the failure the latency math in §2 hides. Suppose one key is extremely hot — a homepage feed, a popular product, a shared feature vector — served at 10,000 requests/second from cache. Its TTL expires. Now, until someone repopulates it, every request is a miss, and if the recompute takes 50 ms, then 10,000 × 0.05 = 500 requests pile onto the database simultaneously, all computing the same value. The database, sized for the steady miss trickle, falls over; latency spikes; more requests miss; the herd grows. This is a cache stampede (or thundering herd / dog-piling): a correlated miss storm triggered by a single expiry.

the read path, and where the stampede strikes client ──▶ [ CDN / edge ] ──▶ [ app cache ] ──▶ [ database / SoR ] ~5-30 ms RTT ~0.5 ms hit ~40 ms read (§5, geo) (§2) (the slow source) steady state (key cached): hot-key TTL expiry (no guard): 99% served here ─┐ t0 key expires ▼ t0+ req#1 misses ─▶ DB (recompute 50ms) [app cache] hit t0+ req#2..500 ALSO miss ─▶ DB │ 1% miss (all recompute the SAME value) ▼ t0+ DB at 500x its miss load ─▶ ⚠ overload [database] one read latency ↑ ─▶ more misses ─▶ herd grows

Four fixes, often combined:

Request coalescing (single-flight). When a key is missing, let only the first request recompute it; concurrent requests for the same key wait for that one result and share it. The DB sees one recompute, not 500. This is the single biggest win and is cheap to implement (a per-key in-flight lock or promise).
Jittered TTL. Never give many keys the same expiry instant — add randomness, e.g. TTL = 60 s ± rand(0..10 s). This spreads expirations so a whole shelf of keys does not stampede together at the top of the minute.
Stale-while-revalidate. On expiry, keep serving the stale value to readers while a background task refreshes it. Readers never see a miss; they see a slightly old value for a moment. (Only legal within your freshness budget from §3.)
Early / probabilistic refresh. Refresh a hot key before it expires — either on a schedule, or probabilistically as it nears expiry (each read has a small, rising chance of triggering an async refresh), so the recompute happens off the critical path while the old value is still valid.

Worked number — coalescing vs not

Hot key at 10,000 req/s, recompute 50 ms. Without a guard: the miss window is the recompute time, so ~10,000 × 0.05 = 500 concurrent DB recomputes of the identical value per expiry. With single-flight: exactly 1 recompute per expiry; the other ~499 readers block ~50 ms (or, with stale-while-revalidate, get the old value in ~0.5 ms and never block). The DB load from this key's misses drops by 500×. Add jittered TTL across the 1,000 hottest keys and you also stop them all expiring on the same tick.

5 · SLO-driven serving: Little's Law, the budget, and the edge

What this is: connect the read path to the lesson-06 promise — size concurrency and spend a latency budget.

Lesson 06 said the serving promise is an SLO: a p99 latency and a throughput. Two tools turn that promise into a sizing decision.

Little's Law relates the three quantities of any queueing system in steady state:

concurrency = throughput × latency (L = λ × W)

The average number of requests in flight equals the arrival rate times the average time each spends in the system. It is an identity — always true in steady state — and it sizes your serving tier. If you must serve 20,000 req/s at an average 10 ms per request, then 20,000 × 0.010 = 200 requests are in flight at any instant, so you need at least 200 concurrent slots (threads / connections / goroutines) just to keep up — fewer, and a queue forms and latency climbs without bound. Crucially, the law shows why a cache miss is doubly bad: if misses push average latency from 3 ms to 5 ms at the same 20,000 req/s, in-flight work jumps from 60 to 100 — a cache regression silently consumes 40 more concurrency slots, and if you have only 60, the system queues and falls over even though "the cache still mostly works."

The latency budget is the p99 SLO spent across the read path. Suppose the SLO is "p99 < 50 ms" for a request that fans out (lesson 06) to an auth check, a feature lookup, and a model call:

p99 budget: 50 ms total edge / TLS + routing ........ 5 ms auth check (cached) ........ 2 ms feature lookup ........ 20 ms ◀ cache this: target 90%+ hit model inference ........ 18 ms serialization + slack ....... 5 ms ───── 50 ms fan-out tail trap (lesson 06): if the request waits on N parallel sub-calls, its latency is the SLOWEST of the N, so each sub-call's p99 must be well under the budget — the tail is what you must cache against.

Finally, CDN / edge caching pushes the cache geographically closer to the user. A CDN (content delivery network) is a fleet of caches in points of presence around the world; a read served from the nearest edge avoids the cross-region round trip entirely (saving the 100+ ms an ocean crossing costs, per lesson 06's fan-out math). It is the same cache-aside / TTL / invalidation machinery from §2–§4, just placed at the edge and best suited to data that is read far more than written and tolerates a freshness budget (static assets, public profiles, rendered pages). The freshness question does not go away at the edge — it gets harder, because now you have thousands of cache copies to invalidate, which is precisely why edge caches lean on TTLs and explicit purge APIs.

Trade-offs

Choice	Buys	Costs
Add an index	O(log n) lookups instead of O(n) scans (only if selective)	One extra tree write per index (~5× write amp at 4 indexes), more space; async indexes lag; useless on low-cardinality columns
Make it covering	Index-only scan — answers the query without a heap read (two reads → one)	Fatter index: more space and more write amplification
Cache-aside	Simple, app controls it, only caches what's read	Every miss pays DB latency; invalidation logic in app
Write-through	Cache never stale vs DB	Every write pays both stores' latency
Write-behind	Fastest writes, absorbs bursts	Cache holds unflushed truth — crash loses data
Longer TTL	Higher hit ratio, less DB load	More staleness — spends more freshness budget
Single-flight + stale-while-revalidate	Kills the stampede; readers never block on a miss	Brief stale reads; per-key in-flight bookkeeping
CDN / edge cache	Cuts geo round-trip; massive offload	Thousands of copies to invalidate; hardest freshness

Failure modes

Cache stampede. A hot key expires and N concurrent readers all recompute it at once, overloading the DB. Symptom: periodic DB latency spikes correlated with TTL boundaries.
Stale-forever entry. Write-time invalidation is lost (dropped message, crash between writes) and there is no TTL, so a wrong value lives indefinitely. Symptom: one record is wrong long after it was updated.
Hit ratio collapse. A scan or one-off traffic evicts the hot set under LRU; the average latency jumps toward the miss latency. Symptom: p50 climbs after a batch job or crawler runs.
Concurrency exhaustion. Misses raise average latency, Little's Law raises in-flight count past the slot limit, a queue forms, latency runs away. Symptom: a small miss-rate rise causes a disproportionate latency cliff.
Write-behind data loss. The cache crashes before flushing acked writes that never reached the DB.
Edge invalidation lag. A purge doesn't reach every PoP; different regions serve different versions.

Decision checklist

What is this data's freshness budget — how stale may a read be, and on which fields? Write it down.
Which pattern: cache-aside (default), write-through (no staleness allowed), or write-behind (write-burst absorption, accept crash-loss)?
Eviction: LRU (temporal locality), LFU (protect a stable hot set), or pure TTL (freshness-driven)? Set a TTL even if you also invalidate on write — it is your backstop.
Estimate the hit ratio and compute the effective latency and p99 (≈ miss latency). Does it meet the SLO?
Is there a hot key? If so, enable single-flight, jitter the TTLs, and consider stale-while-revalidate or early refresh.
How is the cache invalidated — TTL, write-time, or a CDC/change feed (preferred for correctness, see lesson 20)?
Use Little's Law to size concurrency slots for peak throughput at the expected latency, with headroom for a miss-rate rise.
Does geography justify a CDN/edge tier, and can you purge it reliably?

Checkpoint exercise

Try it

You serve an ML product home feed. The personalized feed for each user is expensive to compute (60 ms), read ~50,000 req/s total, and is acceptable up to 30 s stale. (a) Pick a cache pattern, an eviction policy, and a TTL, and justify each against the freshness budget. (b) Your cache hits at 92% with a 1 ms hit and a 60 ms miss — compute the effective average latency, and state your approximate p99 and why. (c) One celebrity's feed is requested 8,000 req/s; when its entry expires, what happens, and which two fixes do you apply? (d) At 50,000 req/s and your computed average latency, use Little's Law to size the minimum concurrency, and explain what happens to that number if the hit ratio drops to 85%.

Where this points next

A cache and an index both made the read path fast by keeping a derived copy of the truth — and both forced us to name a freshness budget for when that copy is stale. But notice what we quietly assumed: that there is a single authoritative system of record sitting behind the cache, one place the truth lives. The next pressure is what happens when that system of record itself must be copied — for durability and read scale — across more than one machine. Lesson 08 introduces replication: a leader accepts writes and followers trail behind it, which means the SoR now has its own internal copies with their own lag and their own freshness budget (replication lag, read-your-writes). The cache's freshness problem you just met is about to repeat one layer deeper — and that recursion, "copies of copies, each with a budget," is the spine of the next several lessons.

Where is truth?

System of record: the database / feature store / upstream service holding the authoritative value.
Copies / derived views: every cache entry (app cache, CDN edge copies) and every secondary index — all derived from the SoR, none authoritative.
Freshness budget: the TTL (plus any stale-while-revalidate window) — e.g. "a read may be up to 60 s old on this field." Make it explicit per data class; some fields (price at checkout, auth) get a budget of zero.
Owner: the service that owns the SoR also owns its cache's invalidation policy.
Deletion path: a delete in the SoR must purge or tombstone every copy — app cache and every CDN PoP — or the budget is violated indefinitely.
Reconciliation / repair path: TTL expiry (the backstop), write-time invalidation, or — best — a CDC/change-feed-driven invalidation that cannot lose events (lesson 20).
Evidence it is correct: hit-ratio and effective-latency metrics meeting the SLO, a bounded max staleness (age never exceeds TTL), and stampede protection (single-flight) keeping DB miss load flat across TTL boundaries.

Takeaway

An index trades write cost and space for read speed inside the database; a cache trades freshness for read speed in front of it — and both are derived copies of a system of record. Choose a cache pattern by where staleness is tolerable (cache-aside by default, write-through when none is, write-behind to absorb write bursts), and an eviction policy by your locality (LRU/LFU/TTL). The hit ratio sets the effective latency by a simple weighted average — but the misses dominate the average and roughly are the p99, so the tail barely improves. Treat invalidation as a derived-view freshness problem with an explicit budget, prefer a change-feed (CDC) invalidation that cannot lose events, and defend hot keys against stampedes with single-flight, jittered TTLs, stale-while-revalidate, and early refresh. Finally, hold the read path to its SLO with Little's Law (concurrency = throughput × latency) and a per-hop latency budget, pushing cache copies to the edge where geography and a freshness budget allow.

Interview prompts

Why does adding an index speed up reads but slow down writes? (§1 — an index is a derived, ordered access path that turns an O(n) scan into an O(log n) lookup, but every write must also update every index, so one insert becomes several writes; it also costs space.)
You have an index on (tenant_id, created_at). Which queries does it serve, and which does it not? (§1 — it's sorted by tenant_id then created_at, so it serves tenant_id = ?, tenant_id = ? AND created_at > ?, and an ordered range on created_at within a tenant; it does not serve created_at > ? alone — the leftmost-prefix rule — because those rows are scattered across all tenants.)
What is a covering index, and when is it worth the cost? (§1 — an index that includes the columns the query returns, so it's answered entirely from the index (an index-only scan) with no second heap read — turning two reads into one for a hot query; worth it when that query is frequent enough to justify the fatter index's extra space and write amplification.)
Why might the planner ignore an index you added? (§1 — low selectivity: if the lookup still returns a large fraction of the table (e.g. a boolean flag over 100M rows), reading the index plus that many heap rows costs more than a plain scan, so the optimizer skips it. Indexes pay off on high-cardinality columns that narrow to a small fraction.)
Walk through the four cache placement patterns and when you'd pick each. (§2 — cache-aside (lazy, app-managed, default); read-through (cache fetches on miss); write-through (sync to both, never stale, slow writes); write-behind (async flush, fast writes, crash-loss risk).)
Cache hits at 95% with a 1 ms hit and a 40 ms miss — what's the average latency, and what's your p99? (§2 — 0.95×1 + 0.05×40 = 2.95 ms average; p99 ≈ the miss latency ~40 ms, because the misses are the slow tail and the cache barely helps the tail.)
Why is cache invalidation hard, and what's the most robust way to do it? (§3 — a cache is a derived view of the SoR, so any SoR change makes copies wrong; TTL is simple but stale, write-time invalidation can be lost (dual-write hazard), and a CDC/change-feed invalidation is robust because the ordered log can't lose events — lesson 20.)
What is a cache stampede and how do you prevent it? (§4 — a hot key expires and many concurrent readers all miss and recompute the same value at once, overloading the DB; fix with single-flight/request coalescing, jittered TTLs, stale-while-revalidate, and early/probabilistic refresh.)
State Little's Law and use it to size a serving tier. (§5 — concurrency = throughput × latency; 20,000 req/s × 10 ms = 200 in-flight, so you need ≥200 concurrency slots; a miss-driven latency rise raises in-flight work and can exhaust slots, causing a queue and a latency cliff.)
How does a freshness budget connect a cache to the rest of the system? (§3, §5 — it's the explicit "how stale may this be" line; it determines TTL and whether stale-while-revalidate is legal, varies by field (zero for price/auth), and it's the same derived-view discipline that governs replication lag (08) and all derived data (20).)