Design a distributed cache

01The design, in the six-step framework

1. Requirements

Interviewers phrase this many ways: an in-memory cache for web pages, a cache with TTL invalidation, a Memcached-like tier. Clarify that it is a general key-value memory tier shared by many services, and that correctness means "never serve a value older than the TTL and never lose the whole tier when one node dies".

Functional

• get(key), set(key, value, ttl), delete(key), and get_many for batches.
• Values up to 1 MB; keys up to 250 bytes; TTLs from seconds to days.
• Eviction when memory is full, preferring least recently used.
• Clients find the right node without a central lookup on every call.
• Out of scope: persistence, transactions, secondary indexes.

Non-functional

• Scale: 10 million gets a second, 1 million sets a second, 50 TB of cached data, 95 percent hit rate target.
• Latency: get under 1 ms p99 inside a data centre.
• Availability: losing one node loses at most its slice of data and never stalls the cluster; adding a node moves only its share of keys.
• Safety: a key that expires or is deleted is never served afterwards; a stampede on a popular key must not take down the backing database.

2. Core entities

• Entry: key, value bytes, expiry time, size, last-access position in the LRU list.
• Node: node id, address, memory capacity, slot range on the hash ring, health.
• Ring: the mapping from key hash to node, versioned; distributed to clients.
• Namespace: prefix owned by a service, with a default TTL and a memory budget.

3. API

• GET key, SET key value EX ttl, DEL key, MGET k1 k2 …: the wire protocol, called by a client library inside each service.
• SET key value NX EX ttl: set only if absent, used for the stampede lock.
• GET /ring from the configuration service: returns the current node list and ring version; clients watch for changes.
• POST /nodes for adding or draining a node (operators).

4. High-level design

1. The client library hashes the key, looks up the owning node in its local copy of the ring (consistent hashing with virtual nodes), and sends the request directly. No proxy, no central lookup.
2. The node checks its hash table; an expired entry is treated as a miss and freed. A hit updates the LRU position and returns.
3. On a miss the application reads the backing store, sets the value with a TTL, and returns. This is the read-through pattern done in the client.
4. The ring service watches node health and publishes a new ring version when a node joins or leaves; clients switch within seconds.

5. Deep dives

How are keys spread, and what happens when a node is added or dies?

Hash each node to 100 or so points on a ring and each key to one point; the key belongs to the next node clockwise. Adding a node takes about 1/N of the keys from its neighbours and no others; removing one does the reverse. Virtual nodes smooth the load so no node owns twice its share. When a node dies, its keys are simply misses until refilled from the backing store, which is a sudden 1/N rise in database load; with 300 nodes that is 0.3 percent, acceptable. For a small cluster, or for hot keys, replicate each slot to the next node on the ring and read from the replica when the owner is down, trading memory for a flatter miss spike (replication).

How does eviction and TTL work inside a node without a sweep?

Memory is divided into slab classes by size so that a 1 MB value cannot fragment the space meant for 100-byte values. Each slab class keeps an LRU list; on allocation failure, the tail of that class's list is evicted. TTL is checked lazily on read (an expired entry is a miss), and a background task samples a few hundred random keys a second and frees expired ones, which keeps memory from filling with dead entries without a full scan. Say the eviction is per slab class, which is why a cache can evict a fresh small item while old large items remain; that is the Memcached behaviour interviewers like you to know.

What stops a stampede when a popular key expires?

At expiry, 10,000 requests a second for the same key all miss and all hit the database. Three defences, combined: a short lock using SET NX so that only one requester recomputes while others wait briefly or serve the stale value; probabilistic early refresh, where a request recomputes a little before expiry with probability rising as expiry nears, so the refresh happens before the cliff; and request coalescing inside the client library so concurrent misses in one process become one database read. For keys that must never miss, a background refresher keeps them warm and the TTL is only a safety net (cache stampedes).

How do writes keep the cache consistent with the database?

The simplest correct strategy is cache-aside: write the database, then delete the key; the next read repopulates. Delete rather than set, because two concurrent writers could set the cache in the wrong order. There is still a window where a reader fills the cache with the old value between the database write and the delete; shrink it by deleting again after a short delay, or by having the database's change stream delete keys. Write-through and write-back are for cases where the cache is the primary access path and are rarely right for a shared tier. State the window honestly; interviewers reward knowing it exists more than claiming it does not.

6. What a strong answer sounds like

• Do the node arithmetic first; then say the problem is routing, eviction and failure, not throughput.
• Explain consistent hashing with virtual nodes and the 1/N movement property.
• Describe slab allocation and per-class LRU with lazy expiry and random sampling.
• Give the three stampede defences and when each applies.
• Name cache-aside with delete-on-write and the race window it leaves.
• Follow-ups to expect: hot keys that exceed one node's bandwidth (replicate the key to several nodes and spread reads), values larger than 1 MB (chunk or store a pointer to blob storage), and multi-tenant fairness (memory budgets per namespace with separate LRU lists).

02Where this question was reported

• IGotAnOffer · EM list: 'in-memory cache for web pages'; SWE list: 'cache where values get invalidated based on a TTL'; TPM: 'Design a web cache'
• IGotAnOffer · Low-level list: 'in-memory cache for webpages'
• IGotAnOffer · 'How would you design a web cache?'
• Hello Interview · One of 5 'commonly asked' Google L5 SD questions
• Hello Interview · One of 5 'most commonly asked' Google L6 questions
• Hello Interview · Most commonly asked for Google EM
• DesignGurus · FAQ: 'a global cache system' commonly asked
• DesignGurus · 'Design a Cache System'
• System Design Handbook · 'Distributed Cache or Key-Value Store', infrastructure-focused
• System Design Handbook · Listed as an L5 question type
• scaleengineer.com · 'How would you design a distributed cache system?'
• scaleengineer.com · North America: distributed caching for large-scale web app