Design a distributed cache (like Redis)

Simple 'hash(key) mod N' breaks when N changes: going from 160 to 161 nodes remaps almost every key, causing a mass miss storm that can take down the database. Consistent hashing places nodes on a ring (with 100-200 virtual nodes each to smooth load) and a key goes to the next node clockwise; adding a node moves only about 1/N of keys. Redis Cluster uses a variant: a fixed 16,384 hash slots, with each slot assigned to a primary. Scaling means moving whole slots, key by key, with the source answering ASK redirects for keys already moved. Fixed slots make the routing table small and explicit, make rebalancing an operator decision (not an accident of hashing), and allow hash tags like {user:42} to force related keys onto the same slot for multi-key operations. Memcached-style systems instead put consistent hashing in the client library (ketama), keeping servers completely unaware of each other. In an interview, either is fine; explain why plain modulo fails and how many keys move when you add a node.

When memory reaches the limit the cache must evict. Exact LRU needs a linked list over 60M keys per node and costs memory and pointer updates on every read. Redis uses approximate LRU: each key holds a 24-bit access clock, and on eviction it samples ~5-10 random keys and evicts the oldest, keeping a small pool of good candidates. This is close to true LRU at a fraction of the cost. LFU (frequency with decay) is better when a big scan of one-time keys would otherwise push out the real hot set. Expiry is lazy (check on access) plus active: sample random keys with TTL and delete expired ones, repeating while more than ~25% of the sample was expired. Memory fragmentation from many different value sizes is real; allocators like jemalloc with size classes, and active defragmentation, keep RSS close to used memory. Plan nodes at ~50-60% of RAM because snapshotting with fork() uses copy-on-write, and write-heavy nodes can nearly double memory during a snapshot.

Two problems take down caches in production. Hot keys: a celebrity profile or a flash-sale product gets 500k reads/s, all on one shard, saturating its CPU or NIC. Fixes: a small in-process cache in each app server with a 1-5 s TTL (absorbs most reads), reading from replicas, or key replication: store the value under user:42#0..#9 on different shards and read a random one. Detect hot keys with client-side sampling or the server's hot-key stats. Stampede: a popular key expires and 2,000 requests miss at the same moment and all query the database. Fixes: request coalescing (single-flight per key in each app server), a distributed lock so one caller recomputes while others serve the stale value, TTL jitter so many keys do not expire together, and probabilistic early refresh (refresh a little before expiry with a probability that grows as expiry approaches, the XFetch technique). Mention that after a cold start or a big failover, you should warm the cache or rate-limit DB reads, otherwise the cache outage becomes a database outage.

Smart clients (hold the slot map, connect directly to every shard) give the lowest latency: one hop. But every language needs a good client, and 5,000 app servers × 320 nodes means 1.6M connections. A proxy layer (Twemproxy, Envoy Redis proxy) hides topology and pools connections, costing an extra hop (~0.2 ms) and more machines. Large fleets often use a proxy or a sidecar for this reason.

Synchronous replication would double write latency and make the cache as slow as a database. Since the cache is not the source of truth, asynchronous replication is accepted: a failover can lose the last few milliseconds of writes. If a use case cannot tolerate that (sessions, rate-limit counters for security), use WAIT-style acknowledgement for those keys only, or store them in a durable store.

Cache-aside with delete-on-update (update DB, then DELETE the key) is the common default. Updating the cache instead of deleting can race: two writers can leave the older value cached. Delete-then-reload still has a small window where a slow reader writes an old value back; short TTLs bound it, and versioned values (SET only if version is newer) or invalidation from the DB's change stream (CDC → delete) close it.

A Redis-style node runs commands on one thread, so one slow command (KEYS *, a big DEL, a large Lua script) blocks everything for milliseconds. Ban O(N) commands, use UNLINK for async deletes, and use I/O threads for network handling. Scale by more shards, not bigger nodes.

Tens of thousands of clients each opening connections to hundreds of nodes exhausts file descriptors and memory. Use connection pooling, multiplexed clients and proxies or sidecars.

If a primary is cut off from the majority but still reachable by some clients, it may keep accepting writes that will be lost when the replica is promoted. Redis Cluster limits this with node timeout: a primary in the minority side stops accepting writes after it cannot reach the majority. Writes in that window are lost, which is acceptable for a cache.

All reads miss and go to the database, which usually cannot take 5M reads/s. Protect the DB with rate limiting and load shedding, warm the cache from snapshots or by replaying recent hot keys, and design apps to degrade (serve defaults, hide non-critical widgets).