System Design Interview: Designing a Distributed Cache
"Design Memcached/Redis cluster" checks whether you understand partitioning, eviction and the consistency trade-offs of caching.
Requirements
get(key)andset(key, value, ttl)with sub-millisecond latency.- Data set larger than one machine's memory (say 2 TB across the cluster).
- Losing cached data is acceptable; the database is the source of truth.
Single node
A hash map plus a doubly linked list gives LRU eviction in O(1). Each entry carries an expiry time; expired keys are removed lazily on read plus by a periodic sampler.
Partitioning
Use consistent hashing with virtual nodes so adding or removing a node moves only about 1/N of the keys. The client library (or a proxy) hashes the key to pick the node.
Replication
For read-heavy hot keys or availability, each shard can have a replica. Replication is usually asynchronous, so a failover can lose recent writes, which is acceptable for a cache.
Cache patterns
- Cache-aside: the app reads cache, on miss reads the database and fills the cache. Most common.
- Write-through: writes go to cache and database together; fresher, but slower writes.
- Write-behind: writes hit the cache and flush later; fast but risky.
On update, prefer deleting the cache entry after writing the database rather than updating it, which avoids racing writers leaving stale values.
Problems to call out
- Thundering herd / cache stampede: many requests miss the same key at once. Fix with request coalescing (one loader per key) or a short lock.
- Hot keys: replicate the key across nodes or add a small in-process cache.
- Avalanche: many keys expiring at the same moment. Add random jitter to TTLs.
- Penetration: repeated lookups for keys that don't exist. Cache the negative result briefly or use a Bloom filter.
Disclosure: I work on Linkjob AI, an AI assistant for technical interviews.