System Design Interview: Designing a Distributed Cache
6 views
"Design a distributed cache like Memcached or a Redis cluster" is a classic system design question. It tests partitioning, replication, eviction and failure handling in one compact problem. Here is a structure that fits a 45-minute interview.
1. Clarify requirements
Functional: get(key), set(key, value, ttl), delete(key). Non-functional: sub-millisecond reads at p99, hundreds of thousands of operations per second, values up to about 1 MB, and the cache is allowed to lose data (the database is the source of truth). Ask whether strong consistency is required; usually it is not, and that single answer simplifies the whole design.
2. Back-of-the-envelope sizing
Suppose 500 GB of hot data and 300k ops/sec. With 64 GB nodes and roughly 70% usable memory, you need about 12 nodes before replication. One node handling 50k ops/sec means 6 nodes would cover throughput, so memory is the binding constraint.
3. Partitioning
Use consistent hashing with virtual nodes so adding or removing a node moves only about 1/N of the keys. Clients can run the hash ring themselves (smart client) or talk to a thin proxy layer. Smart clients save a network hop; proxies make upgrades and topology changes easier. Mention both and pick one.
4. Single-node internals
A hash table plus a doubly linked list gives O(1) LRU eviction. Memcached-style slab allocation reduces fragmentation. TTLs can be enforced lazily on read plus a background sweeper. Mention that LFU or approximated LRU (sampling, as Redis does) can beat strict LRU for skewed workloads.
5. Replication and failure
Keep one or two replicas per shard with asynchronous replication. A coordination service or gossip protocol detects failures and promotes a replica. Because the cache is not the source of truth, an occasional lost write is acceptable; say so explicitly.
6. Hard problems interviewers love
- Hot keys: replicate a hot key to several nodes or add a small in-process cache in front.
- Thundering herd: when a popular key expires, use request coalescing or a lock so only one caller reloads it.
- Cache invalidation: cache-aside with delete-on-write is the usual answer; discuss the race where a stale read repopulates the cache and how short TTLs bound the damage.
- Cold start: warm new nodes gradually instead of sending full traffic at once.
7. Wrap up
Summarize the trade-offs: availability over consistency, memory as the scaling constraint, consistent hashing for elasticity. Offer monitoring (hit rate, eviction rate, p99 latency) as the final touch.
Practicing out loud is the best preparation. During the real interview, Linkjob AI (https://linkjob.ai) can provide real-time help in live technical and system design interviews, surfacing reminders like "mention the thundering herd" when you need them.