backend · intermediate · 5d
Cache stampede lab
Reproduce a thundering-herd cache miss under load, then kill it with single-flight and early-expiry recomputation.
Deliverable
A demo where a hot key expiring under 200 concurrent clients sends 1 origin request instead of 200, proven by a k6 load test with origin-QPS and staleness-vs-load graphs.
Milestones
0/5 · 0%- 01Trigger the stampede and measure fan-out
Build a read-through cache (miss → recompute → repopulate) and make the failure visible, not theoretical. A hot key with a fixed TTL is a synchronized timer: every concurrent reader that observes expiry at the same instant decides to recompute, so N readers produce N origin calls from one expiry event. Your job is to instrument this: a hot key, a configurable origin recomputation cost (e.g. 50–200 ms), and a load generator (k6 -c 50–200 or autocannon) that hammers the key across the TTL boundary. Record the fan-out ratio (concurrent misses / origin calls) and the origin-QPS spike on a time-series graph — the spike is the stampede, and without the graph you can't prove the next two milestones fixed anything. Keep the cache read-through, not write-through: the origin is authoritative, the cache only fills on miss.
Definition of done- A k6/autocannon run with 50–200 concurrent clients hammering one hot key across TTL expiry shows a fan-out spike (e.g. 50–200 origin calls from one expiry) on a graph with origin QPS and miss count annotated.
- The cache is read-through: a miss recomputes from the origin (with simulated latency), repopulates the key with a TTL, and a hit never touches the origin.
Feeds fromSelf-review
Show the origin-QPS graph across the TTL boundary and state the measured fan-out ratio. A senior reviewer checks the spike is N≈concurrency (not a flat line) and that the recomputation cost is parameterized, not hardcoded.
- 02Collapse concurrent misses to one origin call
Add single-flight (request coalescing): when N readers miss the same key simultaneously, only one flight goes to the origin and the other N-1 wait for its result and share it. The invariant is exactly-one origin call per coalesced miss window regardless of concurrency. Two subtleties matter at senior depth: (1) error propagation — if the single flight fails, broadcasting the error to all N waiters turns one origin failure into N request failures, so don't cache errors and let waiters retry independently; (2) wait-queue latency — waiters block for the recomputation time (50–200 ms), so measure p50/p99 of the wait and ensure the coalescing map is per-key, heavily contended keys don't stall unrelated keys. Re-run the same hammer from milestone 1 and watch fan-out collapse from N to 1.
Definition of done- Re-running the same 50–200 concurrency hammer shows fan-out = 1 (one origin call per expiry window) — the origin-QPS spike from milestone 1 is gone, verified on the same graph.
- An origin failure during a coalesced window does not poison the cache and does not turn one error into N cached errors — waiters retry or miss independently and the wait-queue p99 is recorded.
Feeds fromSelf-review
Show the before/after origin-QPS graphs (fan-out N→1) and explain what happens to N waiters if the single flight throws. A senior reviewer checks you don't cache the error and that the wait-queue latency is measured, not guessed.
- 03Spread recomputation with XFetch early expiry
Single-flight fixes the herd after it forms; XFetch prevents the herd from forming. Probabilistic early expiration recomputes a hot key before its hard TTL with probability that grows as expiry approaches: recompute if `now - delta * beta * log(rand()) > expiry`, where `delta` is the measured origin recomputation time and `beta ≈ 1` is the tuning knob. The effect is that recomputations spread across the TTL window instead of concentrating at the boundary — the cliff on the origin-QPS graph becomes a slope. Tune beta against your measured delta: too small and you rarely recompute early (cliff remains); too large and you recompute on nearly every request (origin load approaches cache-miss rate). Keep single-flight underneath — XFetch without coalescing still herds when two early recomputations overlap.
Definition of done- XFetch is implemented with the formula `now - delta*beta*log(rand()) > expiry` and beta is tuned against measured delta; the origin-QPS graph shows the expiry cliff replaced by a spread slope and early recomputations are counted separately from hard misses.
- Single-flight remains active underneath so overlapping early recomputations still coalesce to one origin call; disabling XFetch restores the cliff, proving it is XFetch — not just single-flight — that removed it.
Feeds fromSelf-review
State your measured delta, chosen beta, and show the cliff-vs-slope graphs with XFetch on/off. A senior reviewer checks beta is justified from delta (not default 1) and that early recomputations are wall-clock spread, not burst at expiry.
- 04Jitter, staleness, and the tradeoff curve
Jitter and XFetch solve different problems and the senior mistake is conflating them. TTL jitter (e.g. `TTL * (0.9 + 0.2*rand())`) spreads expiry of many keys so they don't all expire in the same instant — it reduces inter-key collisions but does nothing for a single very hot key, which still stampedes on its own expiry regardless of jitter. XFetch spreads recomputation of one hot key. This milestone makes the tradeoff quantitative: sweep TTL and beta, measure two curves — origin QPS (load) vs staleness (how long a reader can see stale data) — and plot the tradeoff. Pick defaults you can defend: e.g. 'TTL 60s + beta 1.0 + 10% jitter keeps p95 staleness < 70s while origin QPS stays < 2% of request rate under 200-concurrency hammer'. Document why jitter alone would not have fixed the hot-key case from milestone 1.
Definition of done- A staleness-vs-origin-load curve is plotted from a sweep (at least 4 TTL/beta combinations) and a defended default (TTL, beta, jitter %) is chosen with numbers — e.g. p95 staleness and origin QPS % recorded.
- A control run with jitter-only (no XFetch, no single-flight) still stampedes on one hot key, proving jitter alone doesn't fix the hot-key case — the result is documented next to the curve.
Self-review
Present the staleness-vs-load curve and defend the chosen defaults with numbers. A senior reviewer checks you can state why jitter alone fails for one hot key (not just 'many keys') and that the curve — not intuition — drove the TTL/beta choice.
- 05Load-test, observe, and work an incident
Prove it end-to-end under production-like load and make it observable when it misbehaves. Run the full stack (cache + origin + single-flight + XFetch + jitter) under a sustained k6 load (e.g. 200 concurrent, 30s, mixed hot/cold keys) and find the QPS where the origin recomputation — not the cache lookup — is the bottleneck. Emit RED metrics (request rate, cache hit/miss rate, origin QPS, recomputation duration p50/p99) and a trace span for the origin call so the cache's own latency is visible in the waterfall. Then work an incident: disable XFetch or inject a 500 ms origin stall and watch the cache amplify it — origin QPS spikes, hit rate drops, p99 balloons. Detect it from your dashboard (not logs), mitigate (re-enable XFetch / add single-flight timeout / shed load), and write a 5-line post-mortem whose prevention is not 'add more cache'.
Definition of done- A sustained load test (≥200 concurrent, ≥30s) reports throughput, hit rate, origin QPS, and recomputation p50/p99; a dashboard shows all four and the origin trace span is visible in the waterfall.
- You reproduced an incident (XFetch disabled or origin stall), detected it from the dashboard, mitigated it, and wrote a post-mortem naming root cause and a prevention that isn't 'add more cache' or 'increase TTL'.
Feeds fromSelf-review
Paste the dashboard screenshot and post-mortem. A senior reviewer checks the bottleneck is attributed to origin recomputation (not cache lookup), the trace span localized it, and the prevention addresses TTL/XFetch/single-flight distribution — not just 'scale up'.
Starter
fallowlone/skein-projects
projects/cache-stampede-lab
- README.md
- src/cache.ts
- test/cache.test.ts
npx degit fallowlone/skein-projects/projects/cache-stampede-lab cache-stampede-lab Implement the stubs, then run the tests until they pass: bun test
Fork the repo and push your work — the grade workflow runs the suite plus static checks on your own runners.
Rubric
| Junior | Mid | Senior | |
|---|---|---|---|
| Stampede reproduction | The cache misses on expiry but the load test is not instrumented; origin QPS during a stampede is not measured. | A load test expires one hot key under sustained concurrent load and shows the origin-QPS spike (e.g. 1 request → N concurrent misses) on a graph with the miss-count recorded. | You reproduce the stampede, measure the exact fan-out (ratio of concurrent misses to origin calls), and explain why TTL jitter alone doesn't fix a hot key — it only reduces the probability of collision when multiple keys expire in the same window. |
| Single-flight coalescing | All concurrent misses independently call the origin; no deduplication of in-flight requests exists. | A single-flight (or mutex per key) ensures that concurrent misses for the same key collapse to one origin call; the rest wait for and reuse the result. | You know the pathological case: if the origin call fails, single-flight broadcasts the error to all waiters — one origin error becomes N request errors. You handle this by retrying independently on failure rather than caching the error, and measure the latency cost of the wait queue under high concurrency. |
| Early expiry & TTL design | TTL is a fixed constant chosen by intuition; the cache always misses on hard expiry, never recomputes proactively. | Stale-while-revalidate or XFetch probabilistic early expiry recomputes a hot key before the hard TTL fires, so the cliff at expiry boundaries disappears under load. | You tune the XFetch beta parameter against your measured origin recomputation time: too small and you don't recompute early enough; too large and you recompute on nearly every request. You present the staleness-vs-origin-load curve and defend the chosen default with numbers from your load test. |
Reference walkthrough (spoiler)
Why thundering herd happens: a popular key expires and every in-flight request observes a miss simultaneously. The cache's own atomicity is what causes the problem — without coordination, N readers each decide to recompute, N origin calls fire, and the cache just multiplied a single expiry into a fan-out proportional to the request concurrency.
Single-flight as the primary fix: collapse all concurrent misses for one key into one origin call and broadcast the result. The tradeoff is latency: waiters block for the recomputation time. The failure-propagation gotcha (a single origin error propagates to all waiters) means don't cache errors — let failures retry independently.
XFetch probabilistic early expiry: recompute a key with probability proportional to the remaining TTL and recomputation cost, so the recomputation spreads across the TTL window instead of concentrating at the boundary. The formula is: recompute if `now - delta * beta * log(rand()) > expiry_time`. Beta ≈ 1 is a good starting point; tune up if origin calls are expensive.
TTL jitter is not enough alone: jitter spreads expiry across time so multiple keys don't expire in the same instant, reducing inter-key collisions, but a single very hot key still stampedes on its own expiry regardless of jitter. Use jitter for key diversity, single-flight or early recomputation for hot-key protection.
Make it senior
- Replace the single TTL with a two-tier stale-while-revalidate: serve stale while a background refresh runs, and measure how it trades staleness for zero blocking on the hot path.
- Add per-key circuit breaking: if the origin fails N times for one key, stop hammering it and serve stale or a fallback for a cooldown window.
- Run a chaos test that kills the origin mid-recomputation under load and prove the cache never serves a partial write and waiters don't hang forever (single-flight timeout).