Worked Design — Distributed Cache

“Design a distributed cache” (a Redis/Memcached-class system). Tests consistent hashing, eviction, replication, and the cache-correctness trade-offs. Even if you’d never build one, the concepts (consistent hashing, invalidation, stampede) come up constantly.

1. Requirements

Functional: get(key), set(key, value, ttl), delete(key); data lives in memory; entries expire; the cache spans many nodes.

Non-functional: very low latency (sub-millisecond), high throughput (100k+ ops/sec/node), horizontally scalable (add nodes for more capacity), available (a node failure loses some cache, not the service). Cache data is, by definition, rebuildable from the source of truth — so durability is not a hard requirement.

Clarify: is it a look-aside cache (app manages it) or read-through (cache fetches on miss)? Eviction policy needs? Replication for HA?

2. The single-node core

Each node is essentially an in-memory hash map plus:

• TTL/expiration — a key expires after its TTL. Lazy expiration (check on access) + active expiration (a background sampler) — pure lazy leaks memory for keys never read again.
• Eviction — when memory is full, evict to make room. LRU (least-recently-used) is the common default; LFU (least-frequently-used) better resists one-off scans polluting the cache. The policy matters: the wrong one (“no eviction”) means set starts failing once full.
• Single-threaded event loop (Redis-style) — avoids lock contention; each op is atomic; the trade-off is one slow command (KEYS *, a big Lua script) blocks everything.

3. The distribution problem — consistent hashing

To spread keys across N nodes, the naive answer is node = hash(key) % N. The fatal flaw: add or remove one node and N changes, so almost every key remaps — a near-total cache wipe, and a stampede onto the source of truth.

Consistent hashing fixes this:

• Map both nodes and keys onto a hash ring (a 0…2³² circle).
• A key belongs to the first node clockwise from its position.
• Add a node → only the keys between it and the previous node move (~1/N of keys), not all of them.
• Remove a node → only its keys move, to the next node clockwise.

        node A
      /        \
  key3          node B
   |             |
  node D        key1
      \        /
        node C — key2

Virtual nodes — each physical node is placed at many points on the ring (e.g. 150 virtual positions). Without this, three physical nodes give lumpy, uneven key distribution; virtual nodes smooth it out and make rebalancing on node add/remove even.

This is the concept interviewers most want to hear — it’s used in Redis Cluster, DynamoDB, Cassandra, CDNs, load balancers.

4. Topology — where the routing lives

Client-side is lowest latency; proxy/cluster-aware are easier to operate. State the trade.

5. Replication & availability

A node failure shouldn’t lose a critical slice of the keyspace or stampede the database.

• Primary + replica per shard — each ring position has a primary and one or more replicas (async replication). Primary fails → promote a replica. This is Redis Cluster / ElastiCache replication-group model.
• Replication is asynchronous — a primary can fail having acked a write the replica didn’t get yet. For a cache that’s acceptable (the data is rebuildable); you would not run a database this way.
• Without replication, a node death just loses that node’s ~1/N of the cache — the source of truth absorbs the resulting miss surge. Whether that’s acceptable depends on whether the DB can take a 1/N miss spike.

6. Cache correctness — the hard part of using a cache

This is where most of the real interview discussion goes (see ../../backend/09_caching/redis/):

• Look-aside (cache-aside) — app checks cache, on miss reads DB and populates cache. Simple, most common. Risk: a race between a DB update and a cache populate can leave a stale entry.
• Write-through — writes go to cache and DB together; cache is never stale, writes are slower.
• Write-behind — writes go to cache, flushed to DB async; fast writes, risk of loss.
• Invalidation — on a DB write, delete (don’t update) the cache key; next read repopulates. Deleting is safer than updating (no race on the written value).
• Cache stampede / thundering herd — a hot key expires and thousands of concurrent requests all miss and hit the DB at once. Fixes: a short lock so one request repopulates while others wait; probabilistic early expiration; or never let truly hot keys expire (refresh them in the background).
• TTL is your friend — even with invalidation bugs, a TTL bounds how long staleness can last.

7. Bottlenecks & trade-offs

• Hot key — one key (a viral item) gets disproportionate traffic, overloading its one node. Consistent hashing doesn’t help — it’s one key, one node. Mitigations: replicate that key to multiple nodes and read randomly; or a small client-side local cache for the hottest keys.
• The single-threaded node — great for atomicity, but one O(n) command stalls the node. Don’t run KEYS *; use SCAN.
• Memory pressure → eviction churn — if the working set exceeds total cache memory, you evict things you’re about to need again; hit rate collapses. The fix is more memory or a smaller working set, not a cleverer eviction policy.
• Consistency — a distributed cache is eventually consistent at best (async replication, races on populate). Never treat it as a system of record; it’s an accelerator in front of one.
• Cache vs no cache — a cache adds a failure mode and a correctness problem. It’s worth it when the read pattern is skewed (a hot subset) and the source of truth is the bottleneck. If reads are uniform and the DB is fine, a cache just adds risk.

Interview angle

• “Why consistent hashing instead of hash(key) % N?” — with modulo, changing N (adding/removing a node) remaps almost every key — a full cache wipe and a stampede onto the DB. Consistent hashing only remaps ~1/N of keys when the node set changes. Virtual nodes make the distribution even.
• “What are virtual nodes?” — each physical node occupies many points on the hash ring instead of one. Without them, a few physical nodes give lumpy key distribution and uneven rebalancing; virtual nodes smooth both.
• “How does the cache stay available when a node dies?” — primary + async replica per shard; promote the replica on failure. Or accept that a node death loses its ~1/N of the keyspace and the DB absorbs the miss surge — fine if the DB has the headroom, since cache data is rebuildable.
• “How do you keep the cache consistent with the database?” — pick a strategy: cache-aside (simple, populate-race risk), write-through (never stale, slower writes), write-behind (fast, loss risk). On DB writes, delete the cache key rather than update it. A TTL bounds the blast radius of any invalidation bug.
• “What’s a cache stampede and how do you prevent it?” — a hot key expires and thousands of concurrent requests all miss and hammer the DB. Prevent it with a repopulation lock (one request rebuilds, others wait), probabilistic early expiration, or background-refreshing hot keys so they never expire under load.
• “How do you handle a hot key?” — consistent hashing can’t help (one key, one node). Replicate that key across multiple nodes and read from a random one, or keep a tiny client-side local cache for the few hottest keys.
• “Why is the node single-threaded?” — it makes every operation atomic with no lock contention and keeps latency predictable. The cost: one slow O(n) command (KEYS *, a heavy script) blocks the whole node — so you use SCAN and avoid long commands.