Shared Distributed In-Memory Cache With Rebalancing and Failover

Design a distributed in-memory cache that many backend services share to take read load off their databases. Clients store a value under a key with an optional expiry, fetch it by key, and delete it. The cache spreads its data across many machines, keeps serving when some of them fail, and lets operators add or remove machines without sending a wave of misses to the databases behind it. This is a Staff-level loop: the interviewer expects you to set the scope, quantify the design, and go deep on the hardest trade-offs rather than enumerate components. ### Constraints and Clarifications - Keys and values are opaque byte strings; the cache never interprets values. - The cache is not the system of record. Losing an entry is acceptable; serving a stale value must be bounded and explainable. - Start with a single region; multiple regions are a follow-up. ### Clarifying Questions - What request rates, key counts and value sizes must the cluster support, and how skewed is access across keys? - Do services fill the cache themselves after a miss, or should the cache load missing values from the database on their behalf? - How long may a read return an old value after the underlying record changes, and who triggers invalidation? - Is a cold restart of a node acceptable, or must cached data survive restarts? - Is the cluster shared by many teams, so that quotas and isolation between tenants matter? ### Part 1 — API, node design and eviction Define the client-facing operations and their semantics. Then describe how a single cache node stores entries in memory, enforces expiry, handles concurrent requests, and decides what to evict when memory runs out. ```hint Count the bytes Estimate the bookkeeping overhead per entry relative to a typical value, and check what it does to how many entries fit and to the cost of your eviction policy. ``` #### What This Part Should Cover - Operations and their semantics, including expiry, conditional writes and batched reads - The in-memory layout and the overhead and fragmentation it implies - Expiry enforcement and an eviction policy that stays cheap under concurrency - Capacity estimates that fix memory per node and the number of nodes ### Part 2 — Partitioning, replication and membership Explain how keys are spread across nodes, how a client finds the node for a key, how the cluster grows or shrinks without remapping most keys, and how replication and failure detection keep reads working when a node dies. ```hint Minimize movement For each placement scheme you consider, work out what fraction of keys changes owner when one node joins or leaves, and what each moved key costs the database. ``` #### What This Part Should Cover - A placement scheme with bounded key movement and an authoritative record of which node owns what - Client-side routing versus a proxy tier, with the trade-off stated - Replication factor, failure detection and failover, and what can be lost during failover - Adding capacity without a flood of cold misses ### Part 3 — Freshness and protecting the database Describe how cached values stay acceptably fresh when the underlying data changes, and how the system behaves when one key becomes extremely hot, when thousands of requests miss the same key at once, and when a large part of the cache starts cold. ```hint Follow one miss Trace what happens when many requests miss the same key at the same moment, and look for the point where they could share a single database read. ``` #### What This Part Should Cover - An explicit consistency model and the race between filling and invalidating an entry - A reliable invalidation path, with expiry as a safety net - Hot-key mitigation, miss coalescing and staggered expiry - Warming a cold cache and degrading gracefully when the cache is unavailable ### What a Strong Answer Covers - Requirements and estimates that drive memory, node count and replication choices - Clear ownership of cluster membership and safe handling of reconfiguration - A stated freshness bound and the mechanisms that enforce it, not a bare "eventually consistent" - Protection for the databases behind the cache in every failure mode discussed - Staff-level operability: tenant isolation, observability, rollout, and the reasoning behind each trade-off ### Follow-up Questions - How would you extend the cache to several regions, and what freshness would you promise across them? - One tenant suddenly consumes most of a shard's memory and CPU. How do you contain it? - When would you choose a write-through cache over one that services fill after a miss, and how does failure handling change? - How do you roll a new cache version across the fleet without the hit rate collapsing?