Design a Distributed Cache

A cache keeps frequently read data in memory so it can be served in microseconds instead of milliseconds. A distributed cache spreads that memory across many nodes, like Memcached at Meta or Redis Cluster. The question is less about storing bytes and more about partitioning, eviction, consistency with the database, and surviving node failures.

Requirements#

• get(key), set(key, value, ttl) and delete(key).
• Hold terabytes of hot data across many nodes.
• Sub-millisecond latency at millions of operations per second.
• Losing a node should degrade performance briefly, never break correctness.

Caching patterns#

Cache-aside (lazy loading)

The application checks the cache, and on a miss reads the database and fills the cache. It is the most common pattern because the cache only holds what is actually read.

async function getUser(id: string) {
  const cached = await cache.get(`user:${id}`);
  if (cached) return JSON.parse(cached);
  const user = await db.users.findById(id);
  await cache.set(`user:${id}`, JSON.stringify(user), { ttl: 300 });
  return user;
}

Write-through and write-behind

• Write-through: every write goes to the cache and the database together. Reads are always warm, but writes are slower.
• Write-behind: writes land in the cache and are flushed to the database later. Fast, but data can be lost if a cache node dies before flushing.

Architecture#

The cache client (or a proxy like mcrouter or Twemproxy) maps each key to a node using consistent hashing, so adding a node only moves a slice of keys.

Eviction#

Memory is finite, so each node evicts keys when full:

• LRU (least recently used): a hash map plus a doubly linked list gives O(1) get and evict. A good default.
• LFU (least frequently used): better when some keys are popular for a long time.
• TTL: every key expires eventually, which bounds staleness even if invalidation fails.

Keeping the cache consistent#

The hardest part is avoiding stale data after a write.

1. Delete, don't update. On a write, update the database, then delete the cache key. The next read repopulates it. Updating the cache directly races with concurrent writers.
2. Short TTLs as a safety net.
3. Change data capture: a consumer tails the database's change log and invalidates keys, so invalidation doesn't depend on every code path remembering to do it.

Hot keys and stampedes#

• Thundering herd: when a popular key expires, thousands of requests miss at once and hammer the database. Fix it with request coalescing (one request refills while others wait) or by refreshing keys slightly before they expire.
• Hot keys: one celebrity's profile can overload a single node. Replicate hot keys to several nodes with a suffix (user:42#1, user:42#2) or keep a tiny in-process cache on each app server.

Failure handling#

• Each primary has a replica; if the primary dies the replica is promoted.
• If a node is gone with no replica, its keys simply miss and are reloaded from the database. That's why a cache must never be the only copy of important data.
• Warm up a new node gradually so a cold cache doesn't send a wave of misses to the database.