"Design a distributed cache" is really two interviews stacked on top of each other. First: build an in-memory cache on one machine — the classic O(1) LRU question. Then the twist that makes it distributed: the hot data is bigger than one machine's RAM, so you spread it across a cluster — and now you have to answer how keys map to nodes without every key moving when a node joins, what happens when a node dies, and how the cache stays consistent with the database behind it.
This is the condensed walkthrough; the full guide (the O(1) LRU structure, all the write policies, the hard parts, and the full production .NET 9 code) is on my site 👇
Full guide: https://prepstack.co.in/blog/design-a-distributed-cache-system-design
The design at a glance
| Concern | Decision |
|---|---|
| Single-node cache | Hashmap + doubly-linked list → O(1) LRU get/put |
| Sharding | Consistent hashing with virtual nodes |
| Eviction | LRU default; LFU for skewed popularity |
| Availability | Replication (primary + replicas), promote on failure |
| Cache ↔ DB | Cache-aside by default; write-through / write-back / write-around as needed |
| Consistency | Eventually consistent — accept a small stale window |
The single-node cache: O(1) LRU
Before distributing anything, build the one-machine cache with two structures: a hashmap key → node for O(1) lookup, and a doubly-linked list ordered by recency (MRU at the head, LRU at the tail).
get(key): look up in map; move its node to the head; return value
put(key,v): insert at head; if over capacity, evict the tail (LRU); update map
Moving to the head and evicting the tail are both O(1). This is the atom every cache node is built from.
The core of the interview: consistent hashing
Why hash(key) % N fails. It works until N changes. Add one node (N → N+1) and the modulus changes for almost every key, so nearly the entire cache remaps — a mass of misses that all fall through to the DB at once. Adding capacity shouldn't nuke your cache.
Consistent hashing. Map both nodes and keys onto a ring (0 … 2^32). A key is owned by the first node clockwise from its hash.
0 ──── A ──── key1 ──── B ──── key2 ──── C ──── key3 ──(wraps)── 0
└▶ B └▶ C └▶ A (wraps around)
Add node D between B and C and only the keys in arc (B … D] move — roughly 1/N of the keys. Everything else stays put. ~1/N churn instead of ~everything.
Virtual nodes. With only N points on the ring, placement is uneven and one node can own a giant arc (a hotspot). Place each physical node at many points (100–200 vnodes) so load averages out, nodes can be weighted, and a departing node's load spreads evenly instead of dumping on one neighbor.
Eviction
- LRU (least recently used) — the default; great for temporal locality.
- LFU (least frequently used) — better when a stable set of keys is persistently hot and you don't want a one-off scan to flush them.
- TTL expiry runs alongside whichever policy you pick.
Write policies (where cache correctness lives)
- Cache-aside (lazy loading) — the default. Read cache; on a miss read the DB and populate. On a write, update the DB and invalidate the key. Simple and resilient; the trade is a stale window + a miss-penalty on cold keys.
- Write-through — write cache and DB synchronously. Always fresh, higher write latency.
- Write-back — write cache, flush to DB async. Fast writes, but a crash before flush loses data.
- Write-around — write straight to the DB, skip the cache; fills on later reads. Good for write-once-read-rarely data.
The genuinely hard parts
- Cache invalidation — TTL is the pragmatic default; delete-on-write is tighter; event-driven is tightest and most complex.
- Thundering herd (cache stampede) — a hot key expires and thousands of misses hammer the DB at once. Fixes: single-flight/locking, jittered TTLs, stale-while-revalidate.
- Hot keys — one wildly popular key overwhelms its owning node; consistent hashing can't split a single key. Replicate the hot key to multiple nodes or cache it in the client.
Replication
Each shard has a primary + replicas. Replicas serve reads and stand ready for failover — when a primary dies, a replica is promoted and only that shard briefly degrades. Without replication, a dead node turns every key it held into a miss and spikes the DB.
I shipped this in production
Our dashboard recomputes campaign KPIs by aggregating over a 1.2B-row CampaignEvents table in Azure SQL. Every dashboard load fanned out into repeated full aggregate scans — the same tenant/campaign/date-range combos recomputed thousands of times a minute, p95 at 2,100ms, pinning the DB. A cache-aside layer (short TTL for freshness, version-token invalidation on ingestion for correctness):
| Metric | Before | After |
|---|---|---|
| Dashboard KPI query p95 | 2,100 ms | 48 ms |
| Database CPU | 78% | 22% |
| Working set | 2.1 GB | 380 MB |
| SQL cost | baseline | ~$280/mo saved |
Correctness comes from a per-campaign version token, not the TTL: a Kafka ingestion event bumps the version, which instantly makes every cached date range for that campaign unreachable — no SCAN/DEL sweep at 3,200 req/sec. The key is kpi:{tenant}:{campaign}:{range}:v{version}. (Full .NET 9 DashboardKpiService is in the post.)
The model to carry forward
A distributed cache is an O(1) LRU cache, sharded by consistent hashing, kept loosely in sync with a database. The single-node part is a data-structures exercise; the distributed part is all about change — making node joins/failures cheap (consistent hashing + vnodes) and the cache-DB gap manageable (write policies + invalidation). It rests on one permission: the cache is allowed to be a little wrong for a little while, and that's what buys the speed. Three habits: reach for consistent hashing the moment you shard, name the thundering herd, and pick a write policy on purpose.
The full guide has the O(1) LRU walkthrough, consistent hashing + vnodes in depth, all four write policies, replication/failover, the thundering-herd/hot-key fixes, the design checklist, and the complete production .NET 9 cache-aside KPI service:
https://prepstack.co.in/blog/design-a-distributed-cache-system-design
Originally published on PrepStack.
Top comments (0)