Design a distributed cache

Design a distributed in-memory cache like Memcached/Redis Cluster that many services use to store hot key-value data across a fleet of cache servers.

1. Clarify the requirements

Before drawing anything, ask questions. These are the answers an interviewer would typically give:

Data size?

About 10 TB of hot data in total.

Throughput?

10 million reads per second, 1 million writes per second.

Consistency?

Eventual consistency is acceptable; it's a cache.

Can data be lost?

Losing some keys on a crash is OK (the source of truth is elsewhere), but a node failure shouldn't cause a stampede on the database.

Server memory?

Each cache server has 128 GB of usable RAM.

2. Estimate the scale

Assumptions: 10 TB of data, 128 GB RAM per server, 2 copies of each key.

• Cache servers needed (with 2 copies): about 160 servers10 TB × 2 ÷ 128 GB ≈ 160 servers (plus headroom).

3. The high-level design

1. App servers behind a load balancerThe cache serves your app servers. They're stateless and sit behind a load balancer as usual.
2. The source of truthData lives in the database. The cache is cache-aside: on a miss, the app reads the database and fills the cache.
3. A cluster of cache nodesKeys are spread over many nodes with consistent hashing (virtual nodes even out the load), so adding a node moves only a small share of keys. Each shard has a replica, and LRU + TTL decide what stays.
4. Watch it in productionMetrics and alerts close the loop: hit ratio, evictions, memory per node and hot keys.

4. The components and what each one does

Load balancer Load balancer

Spreads requests over the stateless servers behind it, health-checks them and routes around a dead one. Rate limits abusive clients.

App servers App servers

Stateless. A cache client library hashes each key onto the ring (consistent hashing), so every server finds the same cache node.

Source database SQL database

Source of truth; primary + read replicas with failover.

Cache cluster Cache · Redis Cluster / Memcached

Nodes own ranges of a consistent-hash ring (virtual nodes). Each shard has a replica; LRU eviction + TTL. Membership tracked by a config service (ZooKeeper).

Metrics & alerts Metrics & alerts

Dashboards and alerts on p99 latency, error rate, queue depth and cache hit ratio, so a bottleneck shows up before it becomes an outage.

5. Deep dive: partitioning, eviction & failure

How are keys spread across servers so adding/removing one moves few keys? How do you evict, replicate, and avoid hot keys and stampedes?

• Consistent hashing with virtual nodes.
• LRU eviction plus TTLs.
• Replicate to the next node(s) on the ring; use request coalescing to stop thundering herds.

6. What interviewers listen for

• API with TTLget(key), set(key, value, ttl), delete(key).
• Consistent hashing (with virtual nodes)Modulo hashing remaps almost every key when the fleet changes; a ring with virtual nodes moves only ~1/n.
• Eviction policy (LRU/LFU) and TTLMemory is finite: evict the least valuable keys and expire stale ones.
• Replication of keysCopies on other nodes keep hit rates up when a node dies.
• Clients/proxy know the ring (routing)Someone must map keys to nodes: a smart client with the ring config, or a proxy layer.
• Hot keys and thundering herdOne viral key can overload a node; a mass expiry can stampede the DB.
• Write strategy (cache-aside, write-through, write-back)Say how the cache stays in sync with the database.
• Database replication and failoverA single database is a single point of failure. Replicas give redundancy and read capacity; failover promotes a replica when the primary dies.
• Partition (shard) data as it growsOne machine eventually can't hold the data or the write load. Say how you'd split it and by which key.

7. Follow-up questions

1. One cache node out of 160 dies. What happens to its keys and to the database behind it?
2. One key (a celebrity's profile) gets 2 million reads a second. Your nodes handle 200K each. What now?

The design in a nutshell

• Smart client (or proxy) hashes keys onto a consistent-hash ring with virtual nodes; ring config distributed via a config service/gossip.
• Each node: in-memory hash map + LRU eviction + TTLs; keys replicated to the next N-1 nodes.
• Cache-aside from services; request coalescing and jittered TTLs prevent stampedes; hot keys replicated or cached locally.
• Monitor hit ratio, evictions, memory, p99 latency.

Related lessons: The hash ring · Two problems, and virtual nodes · Data partition and replication