Like 0

Interview prep notes

Revision 8f5dc3bf8418c9ebae3b2eba6f424655a3683d01

distcache.md Raw

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) and set(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.