Like 0

Interview prep notes

linkjobai revised this gist 5 days ago · 8f5dc3b

1 file changed, 39 insertions

distcache.md (file created)
@@ -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.*