Design a distributed cache

Scope the requirements

The trap here is scope. A cache is defined as much by what it doesn't do as what it does — the interviewer is watching whether you volunteer the non-goals (durability, transactions, strong consistency) or sleepwalk into building a database.

Functional — what it must do

SET(key, value, ttl?) — store a value with an optional per-key TTL.
GET(key) — return the value or null; must be O(1).
DELETE(key) — explicit invalidation for cache-aside callers.
Evict least-recently-used entries when a node hits its memory limit.
Scale horizontally: add or remove nodes without a full reshuffle.
Explicitly cut: durability across restarts, transactions, secondary indexes, complex queries — it's a cache, the source of truth lives elsewhere.

Non-functional — the numbers that shape the design

Sub-millisecond get/set on the node; < 10 ms end-to-end including the network hop.
100k+ requests/s peak across the cluster.
Total capacity around 1 TB of cached data.
High availability — losing a node degrades hit rate, never correctness.
Eventual consistency is fine: a stale read within a TTL window is the contract callers signed up for.

Say this out loud

Everything here is in memory and latency-critical, so my design decisions are data structures first, distribution second. And I want to be explicit that durability is a non-goal — the moment I promise to never lose a write, I'm designing a database, not a cache.

Back-of-envelope estimates

The arithmetic here is about node counts and per-entry overhead — it tells you the cluster is small, the per-node load is comfortable, and the real risks are hot keys and memory bookkeeping, not raw throughput.

Quantity	Estimate	How you got there
Total capacity	~1 TB	Stated requirement; the cache holds the hot subset, not the world.
Nodes	16 × 64 GB	1 TB ÷ 16 ≈ 64 GB per node — commodity RAM, no exotic hardware.
Load per node	~6k req/s	100k RPS ÷ 16 nodes. A single Redis-style node does ~100k ops/s, so there's >10× headroom for skew.
Per-entry overhead	~50–100 B	Hashmap slot + two linked-list pointers + expiry timestamp, on top of the value itself. Millions of tiny keys make this dominate.
Latency budget	~0.5 ms network + ~0.1 ms node	Same-DC round trip is the floor — the network hop costs more than the lookup, which shapes the whole client design.

Say this out loud

Per-node load is boring — one node could nearly serve the whole cluster's QPS. The headroom is deliberate: it's what absorbs a hot key before I need cleverer machinery.

Sketch the API

Three commands, deliberately tiny. The interesting decision isn't the API surface — it's that routing intelligence lives in the client library, so server nodes stay simple and never talk to each other on the request path.

CMDSET key value [EX ttl]→ OK. Overwrites unconditionally; TTL in seconds, absolute expiry stored with the entry.

CMDGET key→ value | null. Checks expiry lazily on read; a dead entry is deleted and reported as a miss.

CMDDELETE key→ true/false. The invalidation hook for cache-aside callers doing delete-on-write.

CMDSTATS→ { hits, misses, evictions, memory }. Hit rate is the health metric; a falling hit rate is the earliest failure signal.

Smart client over proxy tier: the client library hashes the key onto the ring and connects straight to the owning node — zero extra hops on a path where the network already dominates. A proxy tier (Twemproxy-style) centralises routing logic and simplifies polyglot clients, but adds ~0.5 ms to every request. I'd name both and pick the smart client, flagging the proxy as the answer if we had ten languages to support.
No multi-key transactions, deliberately — cross-node atomicity would need coordination that destroys the latency contract. Callers who need atomic read-modify-write get it per-key (single node, single-threaded), which covers counters and locks.

Data model

The 'data model' is in-memory data structures, and interviewers score the details: this is where the adjacent coding question (LRU cache) lives inside the design question.

hash table

key → entry pointer

O(1) lookup. Sized with headroom to keep load factor low — resizing a giant hashmap under traffic causes a latency spike, so grow incrementally.

doubly-linked list

entries in recency order

Move-to-front on every access; evict from the tail. Combined with the hashmap this gives O(1) get, set and evict — the expected answer.

entry

key · value · expires_at · list pointers

Expiry travels with the entry; there is no global sorted-by-TTL index — that would make writes O(log n).

The database call

Each node is a single-threaded event loop over these structures — the Redis model — because at sub-millisecond operations, lock contention costs more than it saves and single-threaded means zero races by construction. If a profile showed one core saturating before the NIC does, I'd shard the keyspace across threads within the node (Memcached-style) rather than add locks around shared structures.

High-level design

A smart client hashes keys onto a consistent-hash ring of independent cache nodes. Nodes never coordinate on the request path; replication is asynchronous and exists for availability, not durability.

notice there is no load balancer and no proxy — the client library is the router, and nodes never talk to each other on the request path.

The application calls GET(key) through the client library, which hashes the key onto the consistent-hash ring and picks the owning node directly — one network hop.
The node looks the key up in its hashmap (O(1)), lazily checks expires_at, moves the entry to the front of the LRU list, and returns the value — ~0.1 ms of work.
On SET, if the node is at its memory limit it evicts from the tail of the LRU list first, then inserts — still O(1). The write is asynchronously streamed to the shard's replica.
Cluster topology (which node owns which ring range) comes from a config service or gossip; the client watches it and re-routes when nodes join or leave.
If a node dies, its replica is promoted and the client re-routes. Writes in flight are lost — acceptable by contract, because the source of truth is the database behind us.

Deep dives — where the interview is won

Phase 01

O(1) everything: hashmap + doubly-linked list, and why Redis cheats

The canonical LRU construction: a hashmap gives O(1) lookup, and a doubly-linked list keeps entries in recency order — every access unlinks the entry and moves it to the head; eviction pops the tail. Both structures point at the same entry objects, so get, set and evict are all O(1). Interviewers want this named precisely because it's also a top coding question; hand-waving 'we track recency' reads as not knowing it.

Then say what production systems actually do: Redis implements approximated LRU — it samples a handful of random keys and evicts the least-recent among the sample, because maintaining a perfect global recency list has memory and cache-locality costs. The approximation loses almost nothing on skewed workloads. Naming this signals you've seen the difference between the textbook and the shipped system.

get + set are hashmap ops. eviction uses a doubly-linked LRU list, O(1) both directions.

Trade-offPerfect LRU spends ~16 bytes of pointers per entry and touches the list on every read; sampled LRU is cheaper and nearly as good, but its evictions are probabilistic — you can't reason exactly about what's resident.

Phase 02

Consistent hashing with virtual nodes is what makes 'add a node' cheap

Naive hash(key) mod N remaps almost every key when N changes — adding one node invalidates the whole cluster and stampedes the database behind it. Consistent hashing places nodes on a ring and each node owns the arc to its predecessor; adding a node moves only 1/N of the keys. That single property is why the technique exists, and I'd say it in exactly those terms.

Raw rings are lumpy — random placement gives some nodes double share. Virtual nodes fix it: each physical node appears at 100–200 points on the ring, smoothing ownership to within a few percent and letting heterogeneous nodes take proportional shares. When a node dies, its load also scatters across everyone instead of doubling up its neighbour.

each physical node owns many virtual points on the ring. adding a node moves 1/N of keys.

Trade-offVirtual nodes multiply the routing table the client must hold and re-fetch on topology change — trivial at 16 nodes, a real memory and churn cost at thousands. Tune the vnode count down as the cluster grows.

Phase 03

Hot keys break the partitioning model — read and write cases need different fixes

Consistent hashing balances the keyspace, not the traffic. One celebrity key can drive more QPS than an entire node handles, and no amount of re-sharding helps — the key lives somewhere. For read-hot keys: replicate the key to several nodes and let clients pick randomly, or cache it client-side for a second or two — a 1 s local TTL turns a million reads into a handful without meaningfully changing staleness on a cache that already tolerates it.

Write-hot keys (a global counter, say) can't be replicated away because every replica would need every write. The fix is to split the key — counter:0 through counter:15, sharded across nodes, incremented randomly and summed on read. Detection matters as much as the fix: per-key hit counters feeding the stats endpoint, so the hot key is found by monitoring rather than by an outage.

hot keys: replicate across N shards for reads. writes still go to one owner then propagate.

Trade-offKey replication and client-side caching both widen the staleness window; key splitting makes reads N-way fan-outs. Every hot-key fix trades consistency or read cost for load spreading — say which one the workload can afford.

Phase 04

TTL expiry and replication: correctness from reads, availability without durability

Expiring keys eagerly would need a timer or a scan — both expensive. The production pattern is lazy expiry plus a sampling sweep: a read that finds an expired entry deletes it and returns a miss (correctness comes from the read path), and a background task periodically samples random keys, evicting the dead ones, so untouched expired keys don't leak memory forever. Redis does exactly both, which is worth citing.

Replication is per-shard, asynchronous, and exists only so a node failure doesn't cold-start a sixteenth of the cache. On failure, promote the replica and accept that the last few milliseconds of writes are gone — the caller's contract already covers a miss. What I would not do is make replication synchronous: that doubles write latency to protect data whose source of truth is the database behind us.

expiry checked on read (lazy). replicas serve reads; primary loss = miss storm, not data loss.

Trade-offAsync replication means a promoted replica can serve slightly stale entries or miss recent sets — both are ordinary cache behaviour. Synchronous replication would buy consistency the workload never asked for at the cost of the latency contract it did.

Follow-ups you should expect

A hot key's TTL expires and ten thousand callers miss simultaneously — what happens?

That's a stampede onto the database, and the cache can help: per-key request coalescing so one caller rebuilds while the rest wait on the in-flight fetch, or serve-stale-while-revalidate for keys marked hot. Jittering TTLs prevents the correlated version of the problem. I'd offer coalescing in the client library since it needs no server change.

How do you keep the cache consistent with the database behind it?

I don't promise to — the contract is bounded staleness via TTL plus delete-on-write from cache-aside callers. If the product needs tighter freshness, subscribe to the database's change stream (CDC) and invalidate keys as rows change, which shrinks the window to replication lag. Full synchronous invalidation would couple every database write to cache availability, which inverts the dependency.

Why not strong consistency between a node and its replica?

Because the payoff is nearly zero. A cache read that's stale by ten milliseconds is indistinguishable from a read that happened ten milliseconds earlier, and the caller already handles misses. Synchronous replication would double write latency on every set to eliminate a failure mode the API contract explicitly permits.

When would you pick LFU over LRU?

When popularity is stable and scans are common — LFU keeps genuinely popular keys resident even when a batch job sweeps through millions of one-off reads that would flush an LRU. Its weakness is inertia: yesterday's hot keys hang on after the hot set shifts, which is why Redis's LFU decays counters over time. Default LRU, switch on evidence of scan pollution.

A cache node dies with no replica — walk me through the blast radius.

One sixteenth of the keyspace starts missing, so the database sees roughly 1/16th of cache traffic as extra reads until the ring heals and the segment re-warms — a brown-out measured in minutes. The two guards: make sure the database survives that miss rate (capacity planning includes cold-cache math), and rate-limit backfill so re-warming doesn't itself stampede.

Where candidates lose the room

Designing a single node and asserting it 'scales horizontally' without ever explaining key partitioning — the distribution story is half the question.
Saying 'LRU eviction' without the hashmap + doubly-linked-list construction — interviewers treat the O(1) detail as the price of admission.
Ignoring hot keys because 'consistent hashing balances the load' — it balances keys, not traffic, and the follow-up is waiting.
Adding write-ahead logs, transactions, or synchronous replication to a component whose requirements explicitly waive durability — over-engineering that reads as not understanding what a cache is for.
Optimising node-internal microseconds while ignoring that the ~0.5 ms network hop dominates end-to-end latency — connection pooling and client placement matter more than a faster hashmap.