Design a Distributed In-Memory Cache: Partitioning, Failover and Invalidation

Design a distributed in-memory cache that many internal services can use to keep frequently read data close at hand and shield a slower backing database from most of the read traffic. The cluster spans many machines, so the design has to decide how keys are spread across nodes, how the cluster grows and shrinks, what happens when a node dies, and how cached values stay acceptably close to the source of truth. The round is short (about 40 minutes for the whole design), so move from requirements to a working high-level design quickly and keep time for the deep dives the interviewer chooses. ### Constraints and Clarifications - Treat the cache as a shared key-value service with string keys and opaque binary values, not a library embedded inside one application. - The database stays the source of truth: losing cached entries may cost latency and database load, but never user data. - Traffic volume, data size, value sizes and latency targets are not given. Agree on them with the interviewer before sizing the cluster. ### Clarifying Questions - What peak read and write rates, total hot-data size and typical value size should the cluster be built for? - Do clients fill the cache themselves after a miss, or should the cache read from and write to the database on their behalf? - How stale may a cached value be, and does any caller need to read its own writes immediately? - Must cached data survive a node restart, or is starting cold acceptable? - Is this a single-region deployment, or must it serve several regions? ### Part 1 — Requirements, API and the single node Pin down the functional and non-functional requirements and a rough capacity estimate, define the client API, and describe how one cache node stores entries, enforces its memory limit, chooses what to evict, and removes entries whose time-to-live has passed. ```hint Start with one machine Before distributing anything, decide which data structures let a node look up a key, record that it was used, and find the entry to throw away when memory runs out, all without scanning. ``` #### What This Part Should Cover - Requirements and sizing assumptions agreed before drawing components - A small client API with clear time-to-live and miss semantics - Constant-time lookup and eviction on a node, with a justified eviction policy - How expired entries are cleaned up and how memory headroom is managed ### Part 2 — Partitioning and cluster membership Explain how a key is mapped to the node that owns it, how clients find that node, and what happens to existing keys when nodes are added or removed. ```hint Count the keys that move Compare how many keys change owner when one node joins under plain modulo hashing and under a scheme built for changing membership. ``` #### What This Part Should Cover - A partitioning scheme and its trade-offs against the alternatives - Rebalancing that moves few keys and keeps load even across nodes - Request routing (client-side versus proxy) and where the authoritative cluster map lives ### Part 3 — Failures, replication and consistency Describe what happens when a node fails, how replication and failover work, how cached values are kept consistent with the database after writes, and how the database is protected when many requests miss at once or a single key becomes extremely popular. ```hint Kill a node mid-traffic Trace the reads aimed at a node that just died: where do they go, how many reach the database, and what does the next write to one of those keys have to do? ``` #### What This Part Should Cover - Replication, failure detection and failover without split-brain - A write and invalidation strategy with a bound on staleness, and the races it leaves open - Protection against miss stampedes and hot keys - The metrics and alerts that show whether the cache is healthy ### What a Strong Answer Covers - Numbers and requirements agreed before architecture, and a design that fits them - Explicit trade-offs at each decision point rather than a single unexplained choice - A cache that can lose any node without endangering correctness or overwhelming the database - Concrete handling of stale data, stampedes and hot keys - Good use of limited time: breadth first, then depth where the interviewer steers ### Follow-up Questions - During a flash event one key receives a large share of all reads. How do you keep its owning node from saturating? - How would you extend the cache across two regions, and what consistency would you promise between them? - How do you roll out a new cache server version across the cluster without a collapse in hit rate? - When would you choose write-through over look-aside caching, and what goes wrong if the database write fails?