System Design Interview
Distributed in-memory cache inspired by Memcached at Facebook (Scaling Memcache at Facebook, NSDI 2013) and Redis Cluster: look-aside caching, consistent hashing, replicas with failover, gutter pools, leases against stampedes and invalidation from the database's commit log. A teaching design.
Put a cache in front of the database and see where one node runs out.
What was missing: Every read went to the database.
Why that's risky: One node holds everything: 100K operations per second exceed it, and losing it sends every read to the database.
What gets added: Look-aside caching: app servers read from one cache node, fill it from the database on a miss, and delete the key after writing to the database.
Trade-offs: Deleting on write (rather than updating the cache) avoids racing writers leaving a stale value, at the cost of one extra miss.
Spread keys across nodes so capacity grows with the cluster.
What was missing: All keys lived on one node.
Why that's risky: A shard failure loses its keys and sends all of their reads to the database; nothing detects or replaces failed nodes.
What gets added: A cache router that hashes each key onto a ring and sends it to the shard that owns it (consistent hashing), and three shards.
Trade-offs: Consistent hashing moves only about 1/N of keys when a node is added, instead of remapping almost everything as 'hash mod N' would.
Survive a node failure without losing its keys or flooding the database.
What was missing: No copies of shards, and nothing detected or handled failures.
Why that's risky: One very popular key still lands on one shard, and when a hot key expires many servers miss at once and stampede the database.
What gets added: A replica per shard, a cluster config service and store that track health and promote a replica when its primary fails, and a gutter pool that absorbs a failed shard's traffic with short TTLs in the meantime.
Trade-offs: Replication is asynchronous, so the last writes before a failure can be lost; for a cache that only costs extra misses.
Stop one viral key or one expiry from overloading a shard or the database.
What was missing: Hot keys overloaded their shard, and an expiring hot key caused a stampede of identical database reads.
Why that's risky: Writes rely on each app server deleting the right keys; a crash between the database write and the delete leaves a stale value, and other regions never hear about it.
What gets added: A near cache inside each app server holding the hottest keys for a few seconds, and leases on every shard: on a miss only one client gets permission to fill the key while others briefly wait or use the stale value.
Trade-offs: Near-cached values can be a few seconds stale; that's accepted for the hottest keys only.
Guarantee caches drop stale values after every write, everywhere, and watch the cluster.
What was missing: Invalidation depended on each app server remembering to delete keys, and other regions were never told.
Why that's risky: Remaining risk is capacity planning: memory per shard and the hit rate must be watched as data grows.
What gets added: An invalidation stream fed from the database's commit log and workers that delete affected keys from every cache, in every region. (The stream is drawn from the app servers so data flows one way; it is read from the commit log.) Monitoring tracks hit rate, evictions, per-shard latency and the hottest keys.
Trade-offs: Invalidation is asynchronous, so a read can see the old value for a few milliseconds after a write.
In cache-aside, the application is responsible for reading from the cache and populating it on misses. In read-through, the cache layer loads missing data from the DB automatically. Cache-aside is common because it keeps the cache simple, but it pushes correctness and stampede protection concerns into the app.
Consistent hashing minimizes the number of keys that move when nodes join or leave the cluster. That reduces cache churn and avoids large miss storms. Production systems still need staged migrations and warmups because even small key movement can spike DB load for hot keys.
Hot keys overload a single shard. Common mitigations: replicate hot keys to multiple nodes, add local in-process caching, use request coalescing, apply per-key rate limits, or redesign the key (shard by suffix/time bucket). You also need detection: per-key QPS metrics and top-k key tracking.
You're in the middle of an interview session. Leaving now will end your current attempt.
Explore concept overviews, real-system examples, key tradeoffs, and interview talking points for each roadmap section.
You've conquered this phase. These are the skills you now own:
