caching
Caching
How to make apps fast by remembering results instead of recomputing them — and the hard part: knowing when that remembered copy is stale.
Start track →Start from zero
Before the senior material: what a cache even is, and the handful of words the rest of the track assumes you already know.Caching layers: from CPU to CDN
How caches stack from L1/L2/L3 through RAM, application caches, and CDNs — and why each layer exists.Cache invalidation: the hardest problem in CS
Strategies for evicting stale entries — TTL, event-driven purge, write-through, write-behind — and why getting it wrong corrupts user state.Cache stampede: when one TTL expires and thousands of requests hit the DB
Why a single TTL expiry turns a hot cache key into a flash-DDoS against the origin, and the four mechanisms — locks, single-flight, XFetch, and stale-while-revalidate — that keep the database alive.ETags: conditional requests and zero-byte responses
How entity tags enable conditional GET — the server returns 304 Not Modified when content unchanged, saving bandwidth and reducing latency.Cache-Control: directing browsers and CDNs
The directives — max-age, s-maxage, no-store, stale-while-revalidate — that tell every cache in the chain exactly how long to keep a response.Stale-while-revalidate: serve stale, refresh in background
How SWR decouples freshness from latency — serve the cached version immediately, then update it silently, eliminating the tail-latency spike of synchronous revalidation.Dogpile effect: concurrent cache misses that crush the origin
When a popular key expires, all concurrent requests miss simultaneously and pile onto the database — the pattern, why it differs from stampede, and how mutex locks and probabilistic early expiry prevent it.Caching system design: combining all layers
How to compose CDN, reverse-proxy, application, and database caches into a coherent strategy — choosing TTLs, invalidation triggers, and fallback paths that hold under real traffic.Build with this track
Guided projects that exercise what you learn here.
Bloom filter
Build a space-efficient probabilistic set that answers membership queries in O(1) with a tunable false-positive rate — and understand exactly why it can never produce false negatives.
Cache stampede lab
Reproduce a thundering-herd cache miss under load, then kill it with single-flight and early-expiry recomputation.
Circuit breaker
Build a circuit breaker that stops hammering a failing dependency, probes it safely with a half-open state, and resets automatically — the exact pattern that keeps microservice cascades from turning one bad node into a full outage.
Consistent hashing ring
Build a virtual-node hash ring that remaps only the minimum set of keys when a node joins or leaves — the foundational primitive behind Dynamo, Cassandra, and every sharded cache that must survive node churn without a full reshuffle.
Huffman coding
Build a lossless compressor from scratch: construct the optimal prefix-free code tree bottom-up, derive the bit strings, and prove the round-trip is exact and the output is shorter than fixed-width encoding.
LRU cache
Build a Least-Recently-Used cache that evicts in O(1) by combining a hashmap and a doubly-linked list — the canonical interview problem that teaches you exactly why cache eviction is harder than it looks.
Distributed rate limiter
Build a token-bucket limiter that holds across many app instances by keeping the counter in Redis, not in process memory.
Skip list
Build a probabilistic ordered data structure that delivers O(log n) search, insert, and delete without the rotation bookkeeping of balanced trees — just layered express lanes through a sorted linked list.
Text diff — Myers algorithm
Implement the Myers diff algorithm from scratch: compute the longest common subsequence, backtrack an edit script, prove minimality, and apply patches so any round-trip is byte-perfect.
Topological build scheduler
Build a DAG-based task scheduler — like Make or a CI pipeline — that orders jobs by dependency, detects cycles before they deadlock, and identifies which tasks can run in parallel.
Trie autocomplete engine
Build a prefix tree that powers ranked autocomplete — insert words with weights, walk every prefix in O(prefix length + results), and handle tie-breaking deterministically without a database.
Union-Find (Disjoint Set Union)
Build a disjoint-set structure from a naive parent array up to near-constant amortized time — then use it to drive Kruskal's MST algorithm on a weighted graph.
URL shortener at scale
Build a URL shortener that survives real traffic — then run it: deploy it, watch it, and work the incident when one hot link melts your cache.
Queues, Streams, Eventing
Letting parts of a system hand off work through message queues instead of waiting on each other — so things stay fast and survive a crash without losing a message.