| @@ -0,0 +1,39 @@ | |||
| 1 | + | # System Design Interview: Designing a Distributed Cache | |
| 2 | + | ||
| 3 | + | "Design Memcached/Redis cluster" checks whether you understand partitioning, eviction and the consistency trade-offs of caching. | |
| 4 | + | ||
| 5 | + | ## Requirements | |
| 6 | + | ||
| 7 | + | - `get(key)` and `set(key, value, ttl)` with sub-millisecond latency. | |
| 8 | + | - Data set larger than one machine's memory (say 2 TB across the cluster). | |
| 9 | + | - Losing cached data is acceptable; the database is the source of truth. | |
| 10 | + | ||
| 11 | + | ## Single node | |
| 12 | + | ||
| 13 | + | 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. | |
| 14 | + | ||
| 15 | + | ## Partitioning | |
| 16 | + | ||
| 17 | + | 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. | |
| 18 | + | ||
| 19 | + | ## Replication | |
| 20 | + | ||
| 21 | + | 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. | |
| 22 | + | ||
| 23 | + | ## Cache patterns | |
| 24 | + | ||
| 25 | + | - **Cache-aside**: the app reads cache, on miss reads the database and fills the cache. Most common. | |
| 26 | + | - **Write-through**: writes go to cache and database together; fresher, but slower writes. | |
| 27 | + | - **Write-behind**: writes hit the cache and flush later; fast but risky. | |
| 28 | + | ||
| 29 | + | On update, prefer **deleting** the cache entry after writing the database rather than updating it, which avoids racing writers leaving stale values. | |
| 30 | + | ||
| 31 | + | ## Problems to call out | |
| 32 | + | ||
| 33 | + | - **Thundering herd / cache stampede**: many requests miss the same key at once. Fix with request coalescing (one loader per key) or a short lock. | |
| 34 | + | - **Hot keys**: replicate the key across nodes or add a small in-process cache. | |
| 35 | + | - **Avalanche**: many keys expiring at the same moment. Add random jitter to TTLs. | |
| 36 | + | - **Penetration**: repeated lookups for keys that don't exist. Cache the negative result briefly or use a Bloom filter. | |
| 37 | + | ||
| 38 | + | --- | |
| 39 | + | *Disclosure: I work on [Linkjob AI](https://www.linkjob.ai/), an AI assistant for technical interviews.* | |
linkjobai / System Design Interview: Designing a Distributed Cache
Last active 5 days ago
Interview prep notes
linkjobai revised this gist 5 days ago · 8f5dc3b
1 file changed, 39 insertions