Design a Distributed Cache

30-second answer

over many in-memory nodes with rendezvous or , with and expire with a jittered . The design is won or lost on three failure cases: a on one expired key, a on one node, and a stale fill after a write.

Functional

get, set and delete by key, with an optional TTL
Cache-aside use from application code
Spread data over many nodes and add nodes without downtime
Evict old data when memory is full
Stats: hit ratio, evictions, memory

Non-functional

1M reads a second at peak, under 1 ms per read
Hit ratio of at least 98% to protect the database
Losing a node must not take the database down
Values are small (about 1 KB)
Eventually consistent with the database

Out of scope

Being a durable database
Transactions and secondary indexes
Cross-region replication

Clarify and estimate

Ask first:

Quantity	Calculation	Result
Required hit ratio	1 − 20K database reads ÷ 1M reads	98%
Working set	100M objects × 1 KB × 1.3 overhead	130 GB
Nodes by memory	130 GB ÷ 24 GB usable (75% of 32 GB)	6
Nodes by throughput	1M ops/s ÷ 100K per node	10, so use 12
Load per node	1M ÷ 12	≈ 83K ops/s
Bandwidth	1M × 1 KB = 1 GB/s ÷ 12	≈ 0.7 Gbps per node
One node lost	1 ÷ 12	8.3% of keys miss

API and data model

API. A client library over a plain wire protocol (Memcached or style).

Call	Behaviour
`get(key)`	Value or a miss
`set(key, value, ttl)`	Stores with expiry; evicts if full
`delete(key)`	Removes; used after writes
`getOrLoad(key, loader)`	Read-through: cache, then one guarded load, then fill
`mget(keys)`	One round trip per node for a batch

Field	Notes
Key	`type:id`, such as `user:42`; add a version to the name when the format changes
Value	Serialized bytes, about 1 KB; refuse values over 1 MB
Expiry	TTL with up to 10% jitter
Recency	Position in the LRU list, updated on every hit

Architecture

The client does the routing: no proxy hop, so a hit is one network round trip.

Sharding, eviction and expiry

. The client hashes the key to pick a node.

Stampedes, hot keys and stale data

A popular key expires and 1,000 requests miss at once.

Step-by-step answer

Order: clarify, estimate, , and , then the failure modes (, , stale fill, node loss).

Implementation

Tabs: a byte-limited with , with and negative , , and a hot-key guard.

Read more · 48 words

The single-flight test proves 1,000 simultaneous misses make exactly one database read.
The rendezvous test shows a lost node moves about 8% of keys onto all 11 survivors, and hash mod N moves over 85%.
The hot-key test cuts 5,000 reads to under 150 node reads.

// One cache node's memory: a byte-limited LRU with per-key expiry.
//   - A Map remembers insertion order, so "least recently used" is its first key, and "touch" is delete + set.
//   - Entries expire lazily (checked on read) and the oldest are evicted when the memory budget is exceeded.
// The clock is injected so tests need no sleeping.
export class LruCache {
  #map = new Map();                 // key -> { value, size, expiresAt }
  #bytes = 0;

  constructor(maxBytes, { now = () => Date.now() } = {}) {
    this.maxBytes = maxBytes;
    this.now = now;
    this.stats = { hits: 0, misses: 0, evictions: 0, expired: 0 };
  }

  get bytes() { return this.#bytes; }
  get size() { return this.#map.size; }

  get(key) {
    const e = this.#map.get(key);
    if (!e) { this.stats.misses++; return undefined; }
    if (e.expiresAt <= this.now()) {              // expired: remove it and report a miss
      this.#drop(key, e);
      this.stats.expired++;
      this.stats.misses++;
      return undefined;
    }
    this.#map.delete(key);                        // move to the "most recent" end
    this.#map.set(key, e);
    this.stats.hits++;
    return e.value;
  }

  set(key, value, { ttlMs = 60_000, size = 1 } = {}) {
    if (size > this.maxBytes) return false;       // never cache something bigger than the whole cache
    const old = this.#map.get(key);
    if (old) this.#drop(key, old);
    this.#map.set(key, { value, size, expiresAt: this.now() + ttlMs });
    this.#bytes += size;
    while (this.#bytes > this.maxBytes) {         // evict from the least recently used end
      const [oldestKey, oldest] = this.#map.entries().next().value;
      this.#drop(oldestKey, oldest);
      this.stats.evictions++;
    }
    return true;
  }

  delete(key) {
    const e = this.#map.get(key);
    if (e) this.#drop(key, e);
    return !!e;
  }

  #drop(key, e) {
    this.#map.delete(key);
    this.#bytes -= e.size;
  }

  hitRatio() {
    const total = this.stats.hits + this.stats.misses;
    return total ? this.stats.hits / total : 0;
  }
}

Failure modes and trade-offs

What breaks	Effect	Mitigation
A cache node dies	8% of keys miss; database burst	Single flight; rate limit; spread keys over survivors
Whole cache restarts	Cold start; database overload	Warm up gradually; limit load; replicas for critical keys
Stampede on one key	Many identical queries	Single flight; jittered TTL
Hot key	One node saturated	Local cache; replicate the key
Stale fill after a write	Old data until TTL	Short TTL; delayed second delete; versions
Cache poisoning with a bad value	Wrong data served	Validate on fill; version the key name; flush by prefix
Memory pressure	Evicting useful data	Alert on hit ratio and evictions; resize

Choice	Gain	Cost
Client-side routing	One hop, nothing central	Every client needs the node list
Proxy routing	Thin clients; central policy	Extra hop; proxy must scale
Cache-aside	Simple; cache loss is harmless	App code on every read path
Write-through	Always fresh	Slower writes; caches unread data
Replicas per node	Survives a node loss	Double the memory

Follow-up questions

LRU or LFU?

suits recency-driven traffic. LFU keeps frequent items through scans but adapts slowly.

Should the cache be replicated?

Only for keys whose loss would overload the database. Otherwise accept 8% misses and protect the database.

How do you warm a new cache?

Load the hottest keys first, throttled so the database is not overwhelmed.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. The database can serve 20K reads a second. Traffic is 1M reads a second. What hit ratio must the cache reach?At least 90%At least 98%At least 50%

Patterns behind this

The coding patterns this design is built on. Practise them and the design questions get easier.

Hash Maps and SetsA distributed cache is a hash map spread over machines, and rendezvous hashing is the hash that picks the node for a key.

Trade-offs

Bring it up before they ask

Functional

Non-functional

Out of scope

Clarify and estimate

API and data model

Architecture

Sharding, eviction and expiry

Stampedes, hot keys and stale data

Step-by-step answer

Show why a cache is needed

Choose the pattern

Route in the client

Size the fleet

Evict and expire

Protect the database

Handle hot keys

Keep it correct enough

Implementation

Failure modes and trade-offs

Follow-up questions

Check yourself

Patterns behind this

Questions