Courses › System Design › Question Breakdowns

Design a Distributed Cache

Consistent hashing, O(1) LRU per node, replication and failover, hot keys and the thundering herd.

Design an in-memory key-value cache that spreads terabytes of data across many machines, like Memcached or Redis Cluster. The API is tiny (get, set, delete), so the interview is about partitioning, eviction, replication and what happens when nodes come and go.

Requirements

Functional

  • set(key, value, ttl), get(key) and delete(key)
  • Entries expire after their TTL
  • When memory is full, the cache evicts entries (LRU)

Out of scope: persistence to disk, transactions, rich data types (lists, sorted sets), cross-key operations.

Non-functional

  • Low latency: < 1ms per operation inside a data center (p99 a few ms)
  • Scale: 1 TB of data, ~100k requests/second, with room to grow
  • Highly available: losing a node shouldn't take the cache down
  • Eventual consistency between replicas is acceptable — this is a cache, the database is the source of truth

[!TIP] A cache can lose data Unlike a database, a cache can drop an entry and the application just reads from the source again. Say this out loud: it's what lets you choose availability and speed over strong consistency, and skip durability.

Capacity estimates

Core Entities

  • Entry — key, value, expiry time, LRU links
  • Node — address, the slots or hash ranges it owns, its replicas
  • Cluster map — which node owns which part of the key space (versioned)

API

GET    /v1/cache/{key}                 → 200 value | 404
PUT    /v1/cache/{key}?ttl=300  value  → 204
DELETE /v1/cache/{key}                 → 204

In practice clients speak a compact binary or text protocol over long-lived TCP connections — HTTP overhead matters when an operation takes 100µs.

High-Level Design

app = client "App Servers\n(cache client)" @0,1
cfg = service "Config Service\n(cluster map)" @1,0
n1 = cache "Cache Node A\n(primary)" @2,0
n2 = cache "Cache Node B\n(primary)" @2,1
n3 = cache "Cache Node C\n(primary)" @2,2
r1 = cache "Replica A'" @3,0
r2 = cache "Replica B'" @3,1
r3 = cache "Replica C'" @3,2
app --> cfg : fetch map
app -> n1, n2, n3 : hash(key)
n1 -> r1 : async
n2 -> r2 : async
n3 -> r3 : async
  • The cache client in each app server holds the cluster map (from a config service such as ZooKeeper/etcd) and hashes each key to the node that owns it.
  • Each node is a single-purpose server: a hash table plus an LRU list, held entirely in memory.
  • Each primary replicates asynchronously to a replica that takes over if the primary dies.

Deep Dives

1. Which node holds a key?

hash(key) % N is the obvious answer, and it's wrong: adding a 17th node changes N, so almost every key moves and the cache hit rate drops to near zero — every request falls through to the database at once.

Consistent hashing fixes this: nodes and keys are placed on a ring and a key belongs to the next node clockwise. Adding a node moves only ~1/N of the keys. Give each node ~100–200 virtual nodes on the ring so load is even and a dead node's keys spread across many survivors instead of landing on one neighbor. (See Consistent Hashing.)

Redis Cluster takes a simpler route: 16,384 fixed hash slots, slot = CRC16(key) % 16384, and the cluster map assigns slot ranges to nodes. Rebalancing moves whole slots.

2. Inside one node: get, set and LRU in O(1)

A hash map from key to a node in a doubly linked list ordered by recency. get moves the entry to the head; set inserts at the head and, if memory is over the limit, evicts from the tail. Both are O(1). (This is the LRU Cache problem.)

Expiry is handled two ways together:

  • Lazy: on get, if the entry has expired, delete it and return a miss.
  • Active: a background task samples a few keys with TTLs every 100ms and deletes the expired ones, so memory isn't held by keys nobody reads again.

Concurrency: either a single thread per node (Redis — no locks, extremely fast for small ops) or a striped lock per hash-map segment (Memcached) to use many cores.

3. Surviving node failures

  • Each primary streams writes to a replica asynchronously. A few writes may be lost on failover — acceptable for a cache.
  • Failure detection: nodes gossip heartbeats (or the config service health-checks them); after a few missed beats the replica is promoted and the cluster map version bumps.
  • Clients see a connection error, refetch the map, and retry against the new primary.

[!WARNING] The thundering herd after a failure When a node dies without a replica, all its keys miss at once and the database takes the full load for those keys. Protect the database with request coalescing (only one request per key goes to the DB; others wait for its result) and short-lived locks on cache fill.

4. Hot keys

A single viral key can get 500k reads/second, more than one node can serve.

  • Replicate hot keys to several nodes (key#1…key#N) and have clients read a random copy.
  • Client-side near cache: keep the hottest keys in each app server's memory for a second or two.
  • Detect hot keys from per-node request sampling and promote them automatically.

5. Adding capacity without a hit-rate crash

When a node joins, it takes over a slice of the ring or a set of slots. Migrate those entries from the current owners in the background; during migration, a read for a key that hasn't moved yet is redirected (ASK) to the old owner. Add nodes one at a time, during low traffic.

6. Consistency with the database

The cache doesn't know when the database changes. Common patterns (see Caching):

  • Cache-aside with a TTL: the app reads the cache, falls back to the DB, then fills the cache.
  • On write, delete the key (don't update it) to avoid racing writes leaving a stale value.
  • For stricter freshness, stream DB changes (CDC) into cache invalidations.

What's expected at each level

  • Mid-level: a hash map + LRU on each node, a way to spread keys across nodes, and TTL handling.
  • Senior: consistent hashing with virtual nodes and why modulo hashing breaks, replication and failover, the thundering-herd problem.
  • Staff: client vs. proxy routing trade-offs, slot migration without downtime, hot-key strategies, and how cache consistency interacts with the database's write path.