Design a Distributed Cache: System Design Solution

Solution
medium
caching
sharding
eviction
availability

Want to try it yourself first?

Answer each stage in the practice workspace, sketch the architecture, or run a timed mock, then come back here to compare.

Practice this question

The problem

A distributed cache keeps frequently read data in memory across a cluster of nodes so that most reads never reach the database. Putting one cache in front of one database is easy. The interview is about what happens at scale: how keys are spread across nodes, what happens when you add or lose a node, how you keep the cache from serving stale data, and how a single expiring key or a single celebrity post can overload the system. The theme running through every answer: the database is sized for the cache's misses, not for the full read traffic, so anything that empties the cache can take the database down.

Watch: Design a Distributed Cache

At 1M reads/s with a 95% hit rate only 50,000 reads reach a database that handles 100,000, so a cold cache sends it 10x too many. Use cache-aside: on a miss read the database and fill the cache; on a write update the database, then delete the key, because updating the cache lets two racing writers leave a stale value forever. Hash mod N moves about 91% of keys when going from 10 to 11 nodes; consistent hashing moves about 1/11, and 100 virtual nodes per node bring the busiest node from about 3x to 1.16x its share. Evict with LRU (hash map + doubly linked list, O(1)), give every key a TTL with jitter so a million keys don't expire in the same second, coalesce concurrent misses into one database query, cache hot keys on each app server for a second, and give every shard a replica so losing one node doesn't push 145,000 reads/s at the database.

Functional Requirements

The core features:

  • get(key) → value or miss.
  • set(key, value, ttl): store a value with an expiry time.
  • delete(key): used to invalidate a key when the underlying data changes.
  • Every key expires. A TTL on every value means stale data can't live forever, even if an invalidation is lost.
  • Transparent to callers: app code calls a client library; which node holds a key is the library's problem.

Example. The profile service reads user:42. It's a miss, so it loads the row from the database (40 ms) and calls set("user:42", profile, ttl=300s). The next 10,000 reads of user:42 in the next five minutes are hits (~1 ms each).

Out of scope for a first pass: persistence to disk, transactions across keys, rich data structures (sorted sets, streams). Mention them so the interviewer knows you're scoping on purpose. A cache is allowed to lose data: the database is the source of truth.

Scale Requirements

Rough numbers to anchor the design:

  • 1,000,000 reads/s at peak, 95% hit rate.
  • Warm cache: 1M × 5% = 50,000 reads/s reach the database.
  • The database handles 100,000 reads/s. So it has 2× headroom while the cache is warm.
  • Cold cache (all nodes restarted): all 1,000,000 reads/s go to the database. That's 10× its capacity.
  • Data: 100 million keys × 1 KB = 100 GB.
  • Nodes: 10 nodes × 16 GB = 160 GB of RAM, leaving room for overhead and growth.
  • Per node: 1M / 10 = 100,000 ops/s, which a single in-memory cache node handles comfortably.

The takeaway: the database is sized for the cache's misses, not for the real traffic. Every deep dive below is about something that suddenly turns hits into misses.

Non-Functional Requirements

  • Low latency. ~1 ms p99 for get and set. Everything stays in memory.
  • High hit rate. Losing hit rate is how the database gets overloaded.
  • Protect the database. No single event (a node dying, a hot key expiring, a deploy) should push database load past its capacity.
  • Eventual consistency is fine. Serving a value a few seconds old is usually acceptable; serving it for hours is not, which is why every key has a TTL.
  • Data loss is fine. The cache is not the source of truth. Losing a node costs misses, not data.
  • Scale out. Adding a node should move only a small fraction of keys.

API

get(key)                    -> value | MISS
set(key, value, ttl_s)      -> OK
delete(key)                 -> OK
get_many([key1, key2, ...]) -> { key: value }   // one round trip per node
  • Keys are strings like user:42 or post:7:comments; values are opaque bytes (a serialized object), typically under 1 MB.
  • The client library hashes the key to pick a node, so app servers talk to cache nodes directly with no proxy hop.
  • get_many groups keys by node and sends one request per node in parallel. Pages that need 50 keys don't make 50 round trips.

Data Model

Each cache node is a single-purpose in-memory store:

StructureShapeWhy
Hash mapkey → pointer to entryO(1) get / set / delete
Entrykey, value bytes, expires_at, prev, nextone per cached key
Doubly linked listentries in recency orderO(1) "move to front" on access, O(1) evict from the tail
Cluster configring of (hash position → node)shared by every client; changes when nodes join or leave

Expiry is checked lazily on get (an expired entry is a miss) and by a background sweep that samples keys and removes expired ones, so memory isn't held by keys nobody asks for.

High-Level Design

Cache-aside (lazy loading), the most common pattern:

Read:

  1. The app's cache client hashes the key and asks the owning cache node.
  2. Hit → return the value.
  3. Miss → read the database, set the value in the cache with a TTL, return it.

Write:

  1. Update the database first.
  2. Then delete the cache key. The next read misses and loads the new value.

Why delete instead of update? If two writers race, "update the cache" can leave an old value there forever: A writes v1 to the DB, B writes v2 to the DB, B writes v2 to the cache, then A's delayed cache write lands with v1. The database says v2, the cache says v1 until the TTL runs out. Deleting has no such ordering problem; the worst case is one extra miss.

Other patterns, and when they fit:

  • Read-through: the cache itself loads from the DB on a miss. Same idea, logic lives in the cache layer.
  • Write-through: write to the cache and DB together. Cache is always fresh, but every write pays both, and you cache data that may never be read.
  • Write-behind: write to the cache, flush to the DB later. Fast writes, but data is lost if a node dies before flushing. Rarely acceptable for a cache in front of a source-of-truth DB.

Deep Dive: Sharding with Consistent Hashing

The obvious approach: node = hash(key) % N. It spreads keys evenly, but changing N moves almost everything. Going from 10 to 11 nodes, a key stays put only if hash % 10 == hash % 11; in a simulation with 100,000 keys, about 91% of keys move. Every moved key is a miss, so adding capacity effectively cold-starts the cache and sends ~10× normal load to the database.

Consistent hashing. Hash both nodes and keys onto a ring (0 to 2³²). A key belongs to the first node clockwise from its position. Adding a node only takes over the arc between it and the previous node, so going from 10 to 11 nodes moves about 1/11 of keys (~9–10%). Removing a node hands its arc to the next node clockwise.

Virtual nodes. With one point per node, arcs are uneven: with 10 nodes and 100,000 keys, the busiest node got about 3× its fair share. Giving each node 100 points on the ring (node-3#0 … node-3#99) evens it out to about 1.16×. Virtual nodes also mean a dead node's keys spread across many nodes instead of all landing on its single neighbour, and bigger machines can get more points.

Who knows the ring? A small config service (or ZooKeeper/etcd) stores membership; clients cache the ring and refresh it when it changes. Redis Cluster uses a similar idea with 16,384 fixed hash slots assigned to nodes.

Deep Dive: Eviction and Expiry

LRU (least recently used). Keep a hash map from key to a node in a doubly linked list. On every get or set, move the entry to the front. When memory is full, evict from the tail. Every operation is O(1).

Example with capacity 4: after a, b, c, d the order is d c b a. Reading a moves it to the front (a d c b). Setting e evicts b, the least recently used.

Alternatives: LFU keeps frequently used keys even if they weren't touched recently (better for stable popularity, worse when popularity shifts). Redis uses an approximate LRU that samples a few keys and evicts the oldest, avoiding the list's memory overhead.

TTL. Every key gets one, so a lost invalidation can't leave stale data forever. Typical values: seconds for fast-changing data, minutes to hours for profiles and config.

Add jitter to TTLs. If a batch job sets 1,000,000 keys with the same 300 s TTL, they all expire in the same second, and the next second's reads all miss. Using ttl = 300 ± 30 s (uniform) spreads expiry across 60 seconds: about 17,000 expiries per second instead of a million at once.

Deep Dive: Cache Stampede (Thundering Herd)

A hot key like the home page feed gets 20,000 reads/s. It expires. Loading it from the database takes 50 ms. During those 50 ms, every reader misses: 20,000 × 0.05 = 1,000 misses, and each one sends the same query to the database. The cache was supposed to protect the database, and instead it multiplied the load.

Fixes:

  • Request coalescing (singleflight). The first miss for a key takes a short lock (in-process, or a SET NX lock key in the cache with a ~1 s TTL) and loads the value. Every other request for that key waits for that result instead of querying. 1,000 queries become 1.
  • Serve stale while revalidating. Store a soft expiry inside the value. After it passes, one request refreshes it in the background while everyone else gets the slightly old value. No one waits.
  • Probabilistic early refresh. Each reader refreshes with a small probability that grows as expiry approaches, so the key is usually refreshed before it expires.

Deep Dive: Hot Keys

Consistent hashing spreads keys, not traffic. A celebrity post at 300,000 reads/s all goes to the one node that owns post:celebrity, and that node handles ~100,000 ops/s. Adding nodes doesn't help: it's still one key.

Fixes:

  • Local cache on each app server. Keep hot keys in process memory for ~1 second. With 50 app servers, the cache node sees at most 50 reads/s for that key (one refresh per server per second) instead of 300,000. The cost: up to 1 s of staleness.
  • Replicate the hot key. Store it as post:celebrity#0 … #9 on different nodes and have clients pick one at random. Writes must update or delete all copies.
  • Detect hot keys by sampling requests on the cache nodes (or in clients) and publishing a list of keys to treat this way, instead of guessing in advance.

Deep Dive: Node Failures and Cold Starts

Lose 1 of 10 nodes and a tenth of the keys are suddenly gone. Those keys used to be 95% hits; now they're all misses:

  • Normal misses: 1M × 5% = 50,000 reads/s.
  • New misses: 1M × 10% × 95% = 95,000 reads/s.
  • Total: 145,000 reads/s against a database that tops out at 100,000.

The cache layer losing one node, a routine event, can take down the database. Design for it:

  • A replica per shard. Each node asynchronously replicates to a standby; on failure the standby is promoted and is already warm. (Redis Cluster does this with replicas per primary.)
  • Rolling restarts. Deploy and restart one node at a time, and wait for its hit rate to recover before the next.
  • Warm before serving. A replacement node can be pre-filled from its replica or from a snapshot before it joins the ring.
  • Limit misses to the database. A per-app-server cap or a circuit breaker on database reads makes overload fail fast (some requests get an error or a fallback) instead of letting the database fall over for everyone.
  • Don't remove a node from the ring too eagerly. A brief network blip that triggers rebalancing causes more misses than waiting a few seconds.

Wrap-Up & Trade-offs

The design in one breath:

  • Cache-aside: on a miss, read the DB and fill the cache; on a write, update the DB, then delete the key.
  • Sharding: consistent hashing with ~100 virtual nodes per node; adding a node moves ~1/N of keys instead of ~91%.
  • Memory: LRU eviction (hash map + doubly linked list) and a TTL with jitter on every key.
  • Stampedes: request coalescing so one miss means one DB query.
  • Hot keys: a ~1 s local cache on app servers, or replicate the key.
  • Failures: a replica per shard, rolling restarts, and a cap on DB reads so the database sheds load instead of dying.

Trade-offs. Longer TTLs mean higher hit rates but staler data. Local caches crush hot-key load but add staleness you can't invalidate quickly. Replicas double memory cost to avoid a cold-shard spike. Write-through keeps the cache fresh but slows writes and caches data nobody reads.

Common follow-ups: multi-region caching (each region has its own cache; invalidate via a change-data-capture stream from the database), caching query results vs objects (invalidation gets much harder), and negative caching (cache "not found" briefly so missing keys don't hammer the DB).

Common follow-up

During a deploy, two of your ten cache nodes restart at the same time and come back empty. Reads are 1M/s with a 95% hit rate and the database tops out at 100,000 reads/s. Walk through what happens to database load in the next minute, and what in your design keeps the database up.

FAQ