Design a Distributed Cache
Problem
Design an in-memory cache that many application services share to avoid repeated database reads. It must hold about 2 TB of cached data spread across many servers, serve 5 million reads per second with sub-millisecond latency, and evict the least recently used entries when memory fills up. Entries can carry a time-to-live, and losing a single cache server must not cause a flood of traffic to the databases behind it.
- Is the cache only a performance layer, or do callers expect data to survive restarts?
- What is the read to write ratio? Is 10 reads per write a fair assumption?
- How large are typical values, and is there a maximum value size?
- How stale may cached data be after the database changes?
- Are there known hot keys, such as a celebrity profile or a global config value?
- Should the cache support data structures (lists, counters, sets) or only opaque values?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
get(key),set(key, value, ttl?), anddelete(key).- Evict least recently used entries when memory is full.
- Expire entries after their TTL.
- Support atomic increment for counters.
- Support multi-get so a caller can fetch many keys in one round trip.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Hold about 2 TB of data: with 64 GB of usable memory per node, that is around 32 primary nodes, plus replicas.
- Serve 5 million reads per second (about 150,000 per primary node) and 500,000 writes per second.
- p99 latency under 1 ms within a data center.
- Survive the loss of a node without overloading the database.
- Scale out by adding nodes with minimal key movement.
- Values average 1 KB, with a hard limit of 1 MB per value.
The cache is a cluster of in-memory nodes sharded by consistent hashing, with each primary shard asynchronously replicated to one replica. A smart client library holds the cluster map, routes each key directly to its shard, and implements cache-aside reads with request coalescing. A small cluster manager tracks node health and promotes replicas when a primary fails.
Loading diagram...
Read (cache aside). The service calls get(key). The client hashes the key, looks up the owning shard in its cluster map, and sends the request over a pooled connection. On a hit, it returns the value. On a miss, the service reads the database and calls set(key, value, ttl). If many requests miss on the same key at once, the client lets only one of them load from the database while the others wait for its result.
Write. When the service updates the database, it deletes the cache key (rather than updating it) so the next read loads fresh data. The primary applies the delete and streams it to its replica.
Node failure. The cluster manager notices missed heartbeats, promotes the replica to primary, and publishes a new cluster map version. Clients that receive a MOVED error or poll the new map start routing to the new primary. Only the writes not yet replicated are lost, and those keys simply reload from the database.
Library linked into every application that routes requests and implements the caching patterns.
- Language libraries (Java, Go, Python) sharing one hashing and routing specification.
- Persistent connection pools with pipelining.
API
get(key),mget(keys[]),set(key, value, ttl?),delete(key),incr(key, delta).getOrLoad(key, loader, ttl)wraps cache aside with request coalescing.
Scalability
Routing in the client avoids a proxy hop, so a read is a single network round trip. mget groups keys by shard and sends one request per shard in parallel.
Tradeoffs
A proxy layer (such as Twemproxy or Envoy) makes clients simpler and language neutral, but adds latency and another fleet to run. A smart client is chosen because sub-millisecond latency is the main goal. The proxy option remains useful for languages without a client library.
A single-process in-memory store that owns some hash slots.
- Redis or Memcached style server with an event loop and non-blocking I/O.
- Slab allocation to limit memory fragmentation.
Diagram
Loading diagram...
Data Model
- Entry:
key,value bytes,expires_at,lru_clock, plus LRU list pointers.
Scalability
A single node serves well over 100,000 operations per second because every operation is an in-memory hash lookup. Expired keys are removed lazily on access, and a background task samples random keys to reclaim memory from entries that are never read again.
Tradeoffs
Exact LRU needs a linked list update on every read, which costs memory and contention. Approximated LRU (sample a few keys and evict the oldest) gives nearly the same hit rate at much lower cost. LFU is better for workloads with stable popularity, so the eviction policy is configurable per cluster.
Splits the key space across nodes and tells clients where each key lives.
- 16,384 hash slots mapped to nodes, with
slot = crc16(key) mod 16384.
Data Model
- Cluster map:
{ version, slots: [{ range, primary, replica }] }.
Scalability
Adding a node moves a subset of slots to it. While a slot migrates, the old owner answers reads for keys it still holds and redirects others with an ASK response, so the cluster keeps serving traffic throughout.
Tradeoffs
Fixed hash slots are a form of consistent hashing that makes rebalancing explicit and easy to reason about. A pure hash ring with virtual nodes works too, but slots make it simple to move a specific hot range and to see exactly which node owns what.
Monitors node health and coordinates failover and rebalancing.
- A small replicated controller backed by etcd, or the gossip-based failover built into Redis Cluster.
Scalability
The manager handles only heartbeats and map changes, not data traffic, so a three-node control plane is enough for hundreds of cache nodes.
Tradeoffs
Asynchronous replication keeps writes fast but can lose the last few writes on failover. For a cache this is acceptable, because the database remains the source of truth. Synchronous replication would double write latency for no real benefit.
Mechanisms that protect both the cache and the database from uneven load.
- A small in-process near cache (a few thousand entries with a 1 to 5 second TTL) in the client library.
- Request coalescing and probabilistic early expiration.
Scalability
A single viral key can receive more traffic than one node can handle. The near cache absorbs most of those reads on the application hosts themselves. For extreme cases, a key is replicated under several suffixed names (key#1 to key#8) and readers pick one at random.
Tradeoffs
The near cache adds a few seconds of possible staleness, which is acceptable for hot, mostly static data but not for everything, so it is opt-in per key prefix. Adding random jitter to TTLs and refreshing a key slightly before it expires prevents thousands of entries from expiring at once and stampeding the database.