Distributed Cache System Design

Introduction

A flash sale starts. One product id is in every cart. Your cache cluster shows healthy CPU—but the database catches fire and checkout fails for everyone.

A distributed cache is fast mutable state spread across machines. The interview is not “Redis vs Memcached trivia.” It is how clients find the right shard, what moves when a node joins, what replicas promise (and do not), and what happens when a hot key or TTL expiry turns the cache into a load generator for the database.

Weak answers say “we add Redis.” Strong answers separate routing (hash ring, virtual nodes) from data plane (GET/SET on primaries) and name cache-aside, invalidation, and thundering herd.

If you remember one thing: A cache protects the DB only if you design routing, eviction, and miss storms—not just hit ratio.

How to approach

Start with one machine: TTL, eviction (LRU/LFU), memory limit.

Add sharding: consistent hashing + virtual nodes so load stays even.

Add replication: async copy, failover, stale read rules.

End with cache-aside: who loads on miss, who deletes on DB update, how you stop herd on expiry.

In the room: “Single-node semantics, then hash ring, then replica lag, then cache-aside invalidation and stampede control.”

If you remember one thing: Order beats feature lists—routing before persistence flags.

Interview tips

Five questions that expose shallow cache answers.

Modulo hashing

You: “We hash the key mod number of servers.”

They ask: “You add one server—what happens to every key?”

Land here: Almost all keys move—cache storm + DB spike. Consistent hashing moves only keys in the wedge near the new token; virtual nodes balance load across physical machines.

Invalidate on update

You: “When the DB updates, we invalidate the cache.”

They ask: “One product row maps to fifty cache keys—how?”

Land here: Delete affected keys (or version stamp in value); pattern invalidation is hard at scale—TTL as safety net; document eventual staleness window.

Read-after-write

You: “We read from any replica for speed.”

They ask: “User saves profile, refreshes, sees old name—why?”

Land here: Replication lag. Critical keys: read primary, sticky routing, or version check in value; say what is OK to be stale (display name) vs not (balance).

Thundering herd

You: “TTL keeps data fresh.”

They ask: “Viral key expires—what hits the database?”

Land here: Thousands of simultaneous misses. Singleflight per key, TTL jitter, probabilistic early refresh, stale-while-revalidate where product allows.

Cache vs database

You: “The cache is our source of truth.”

They ask: “Primary crashes—what did we lose?”

Land here: Cache is ephemeral for most workloads; DB is truth. Persistence (RDB/AOF) trades durability for fork latency on big heaps—name p99 impact if you mention it.

If you remember one thing: Tie every tip to one failure mode—rebalance storm, stale replica, herd, split brain.

Capacity estimation

Implications: You shard to spread RAM and CPU; you do not solve hot keys only by “adding nodes” if one logical key dominates.

If you remember one thing: Hot keys are a logical problem—sharding spreads averages, not one viral id.

High-level architecture

Clients either embed a smart client (knows hash ring) or talk to a proxy (stateless routing). The cluster exposes logical keyspace partitioned into slots or token ranges, each owned by a primary with 1+ replicas. Gossip or a configuration service (etcd-style) publishes membership. Persistence (if any) is async snapshots or append logs—off the critical read path for most designs.

Who owns what:

• Routing layer — Hash(key) → node; handles MOVED/ASK-style redirects when topology changes (Redis Cluster pattern).
• Shard primary — Serializes writes per key (common pattern: single-threaded primary); serves reads or forwards to replica depending on consistency mode.
• Replicas — Async copy from primary; promoted on failover after health checks + epoch bump.
• Control plane — Add/remove nodes, rebalance throttles, placement of primaries across racks/AZs.

[ App servers ]
       |
       |  GET/SET (sync, sub-ms target)
       v
[ Smart client or Proxy ]  ----membership----► [ Config / gossip ]
       |
       |  consistent hash: key → shard
       v
+------------------+     replication      +------------------+
| Primary A        | ------------------► | Replica A'         |
| (token range T1) |                     | (async, read opt)  |
+------------------+                     +------------------+
+------------------+                     +------------------+
| Primary B        | ----------------►  | Replica B'       |
| (token range T2) |                     |                  |
+------------------+                     +------------------+

  Rebalance (async): new node C → migrate token ranges → throttle → HANDOFF

In the room: Walk one GET: hash → node → memory lookup → optional replica. Then one failover: primary dead → replica promoted → clients refresh topology.

If you remember one thing: GET is hash → primary (or replica with stale rules); rebalance is async and throttled.

Core design approaches

Cache-aside (lazy loading)

App checks cache → on miss, loads DB, sets cache. Simple; invalidation is app’s job when DB updates.

Read-through / write-through

Cache module loads DB on miss (read-through); writes go to cache and DB together (write-through). Stronger consistency; higher write latency.

Write-behind

Writes ack after cache update; async flush to DB—fast but loss risk if cache dies before persist—rare for generic interview unless scoped.

Pick: Most candidates describe cache-aside for read-heavy workloads; mention write-through when stale reads are unacceptable after writes.

If you remember one thing: Cache-aside = app owns invalidation; write-through = stronger consistency, slower writes.

Detailed design

Read path

1. Client computes shard (or asks proxy).
2. Primary or replica serves GET if stale read OK.
3. On miss (cache-aside), app loads DB and SET with TTL.

Write path (cache-aside invalidation)

1. App commits DB update.
2. App DELETE cache key(s) or bump version embedded in value.
3. Next read repopulates—avoid stale by delete vs update carefully (race: read old DB, overwrite new cache—ordering matters).

Atomic ops

INCR, CAS—used for counters and locks. Single primary per key makes this tractable; cross-shard transactions are out of scope for “cache.”

If you remember one thing: On DB update, delete cache keys (or bump version)—order matters to avoid writing stale data back.

Key challenges

• Rebalancing: Moving keys without dual ownership bugs (serving wrong value during migration)—handoff protocols and throttled migrations matter.
• Hot keys: One key → one primary thread or one NIC—YCSB-style skew burns you in benchmarks and production.
• Replication lag: “I wrote then read” flakiness—apps must know which replica they hit.
• Eviction thrash: Memory at max + churning working set → constant eviction + miss storm.
• Split brain: Two primaries after partition—mitigate with quorum, fencing, epoch—at cost of complexity.

If you remember one thing: Rebalance and hot keys hurt more in production than picking LRU vs LFU on day one.

Scaling the system

• Horizontal: Add nodes; only adjacent key ranges migrate (consistent hashing).
• Vertical: Bigger RAM for hot shards—sometimes cheaper than perfect algorithmic fairness.
• Read scaling: Replica reads for read-heavy, eventually consistent keys; primary for linearizable per-key sequence if required.
• Multi-region: Active-active cache is hard (conflicting writes)—often read replicas per region with async replication and stale SLAs.

If you remember one thing: Replica reads scale throughput; primary wins when stale is unacceptable.

Failure handling

Degraded UX: Slightly stale data; outage is unavailable cache—often degrade to DB with timeouts (slower, not wrong).

If you remember one thing: Under partition, pick availability + stale for most cache workloads—unless they scope money paths.

API design

Caches expose binary protocols (RESP) or thin REST. Interview clarity matters more than opcode trivia.

Core operations:

Cluster routing:

Error semantics: Miss is not an HTTP 404—it is a cache miss; apps distinguish miss vs error (connection reset).

Request flow diagram (GET):

App --GET key--> Client lib --hash--> Primary shard
                              |
                              hit --> value
                              miss (cache-aside) --> DB --> SET --> value

If you remember one thing: A miss is not HTTP 404—it triggers cache-aside load unless you design read-through.

Production angles

[ Apps spike GETs ] → [ Cache primaries at CPU max ]
       → latency ↑, timeouts
       → some clients fall back to DB → DB overload → worse cache refill

Bottlenecks and tradeoffs

Memory vs hit ratio

The tension — Bigger cluster means fewer DB hits; RAM is not free.

What breaks — Diminishing returns; eviction thrash when working set exceeds RAM.

What teams do — Track evicted_keys and tail latency; tier hot data; right-size per shard.

Say in the interview — Cache size is a cost decision with an SLO, not “as big as possible.”

Strong consistency vs cache speed

The tension — Apps want read-your-writes; caches favor speed and partition tolerance.

What breaks — Cross-shard transactions on a cache are the wrong tool.

What teams do — DB as truth; delete on write; short TTL; primary read for critical keys.

Say in the interview — Most caches are eventually stale—say what your app tolerates.

Rebalance vs availability

The tension — Adding nodes should help capacity; migrating keys risks wrong values and latency.

What breaks — Dual ownership during move; redirect storms.

What teams do — Handoff protocol; throttled migration; hinted handoff for reads during move.

Say in the interview — Adding a node is an ops event, not a free horizontal scale button.

If you remember one thing: Caches fail open to the DB in the worst way unless you engineer miss behavior.

What should stick

You do not need every Redis opcode. You should leave knowing:

1. Consistent hashing + virtual nodes — Adding a server moves a wedge of keys, not the whole keyspace.
2. Cache-aside — App loads on miss; delete (or version) on DB update; TTL as safety net.
3. Replication lag — Replicas scale reads; primary when stale is unacceptable.
4. Thundering herd — One expiry → many DB hits; jitter + singleflight are mandatory patterns.
5. Hot keys — One logical key can saturate one shard; replication or app-level sharding of the key.

Tell it in the room: “Client hashes key to primary via consistent hashing with vnodes. GET hits memory or miss → DB → SET with TTL. On DB write, DELETE cache key. Replica for read-heavy stale-OK data; primary for read-after-write. Viral key: singleflight on miss, TTL jitter. Node add: throttled rebalance with handoff, not big-bang migration.”