11. Distributed Cache Advanced + Distributed Systems

A. Realistic Interview Prompt

This document has already used "put a cache in front of the database" as a supporting move in half its problems (Prerequisites D) — a single Redis instance, treated as a black box. This problem is the opposite framing: you are the team building that black box. Everything that was previously "just reach for Redis" — where a key lives, what happens when a node dies, what gets evicted when memory fills up — is now the actual subject of the design, and the honest, load-bearing answer to all of it is one integrated decision: consistent hashing to spread keys across shards, leader-follower replication per shard for availability, approximate-LRU eviction under memory pressure, and TTL as a property every entry carries, not a bolt-on feature.

B. Difficulty

Advanced, distributed-systems-heavy — the single-node mechanics (a hash map, an LRU list) are almost trivial; what's hard is doing all of it across a fleet of machines that individually crash, that individually have finite memory, and where a handful of keys can receive wildly more traffic than the rest without warning.

C. What This Problem Tests

• Recognizing the difference between using a cache (Prerequisites D, and nearly every earlier problem) and building the caching system itself — the ownership, partitioning, and failure-handling concerns that a client of Redis never has to think about, because Redis's own engineers already solved them
• Consistent hashing (Prerequisites J, Patterns Playbook L) as a genuinely load-bearing partitioning mechanism here, not a one-line buzzword — the ring, virtual nodes, and what actually moves when the fleet's shape changes
• Honest reasoning about eviction: recognizing that textbook exact LRU doesn't survive contact with real concurrency and scale, and that every production system's real answer is an approximation
• Replication as an availability mechanism with a real consistency cost — leader-follower per shard, and being explicit about what "eventually consistent between leader and follower" actually means for a cache's correctness guarantees
• Recognizing that a single overloaded key is a fundamentally different failure mode than an unbalanced hash function, and needs a fundamentally different fix

D. Requirements

Functional

1. SET key value [TTL] — store a value under a key, with an optional expiration
2. GET key — retrieve the value for a key, or a miss if absent or expired
3. DEL key — explicitly remove a key before its TTL would naturally expire it
4. An entry set with a TTL is automatically unavailable via GET once that TTL elapses, with no explicit deletion required

Non-Functional

• Very low latency — sub-millisecond to low-single-digit-millisecond GET/SET, the entire reason anything reaches for a cache instead of the database in the first place
• Horizontal scalability — a total dataset far larger than any single machine's RAM, served by a fleet of nodes rather than one
• High availability — a node crash should not make its share of keys fully unreachable, and should not require a manual failover
• Even load distribution — both key count and, as far as possible, request traffic spread across the fleet rather than concentrated on a few nodes
• Bounded, predictable memory use per node — a node approaching its memory limit degrades by evicting gracefully, not by crashing or by silently accepting unbounded growth

Out of scope: this system is the cache — a downstream database is assumed to exist as the real source of truth (per the cache-aside pattern, Prerequisites D) but is not itself part of this design; multi-key transactions; a full pub/sub messaging layer; rich data structures beyond a string-valued blob (acknowledged as a real extension in AA).

E. Clarifying Questions

F. Assumptions

• Confirmed: GET/SET/DEL with per-key TTL, sub-millisecond latency target, horizontal scale past one machine's RAM.
• Assumption: this is a pure, cache-aside-style cache (E's clarifying question 1) — the source of truth lives elsewhere (a database), so losing a node's data on crash is tolerable in principle, though O and S both discuss reducing how often and how much that actually happens in practice.
• Assumption: followers may serve reads (E's clarifying question 2) — the far more common real-world configuration, and the one that makes replication earn its keep for more than pure failover.
• Assumption: access is skewed, not uniform (E's clarifying question 3) — realistic for almost any real cache workload, and the assumption that makes the hot-key deep dive (P) a first-class part of the design rather than a footnote.
• Assumption: a smart client library maintains shard-ring awareness directly (E's clarifying question 5) — the same model used by real systems (Redis Cluster clients, Memcached's Ketama-based libraries), avoiding a routing-tier hop on every single request.

G. Capacity Estimation

H. Core Entities

I. API Design

-- client-facing (via a shard-aware client library, per F):
SET   key value [EX ttl_seconds]   -> OK
GET   key                          -> value | (nil, cache miss)
DEL   key                          -> OK
-- internal, cluster-facing, not client-facing:
(gossip) node heartbeat + ring-membership propagation                (N)
(replication stream) leader -> follower: append-only change stream   (O)
(rebalance) migrate key range from old owner -> new owner on topology change (N)

Why the client library resolves the shard itself instead of asking a router on every call: a routing-tier hop would add a full extra network round trip to every single GET/SET, directly undermining the sub-millisecond latency requirement (D) — instead, the client library keeps a local, gossip-updated copy of the ring (N) and computes the target node itself, the same "push the routing decision as close to the caller as possible" instinct behind Chat System's connection-routing table (Prerequisites K).

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies the functional requirement in isolation: one machine holds an in-memory hash map, and every client talks directly to it.

V1 — one node, one hash map. Works exactly until the dataset outgrows one machine's RAM, or that machine dies.

Why this breaks immediately, not eventually: a single node has a hard, fixed memory ceiling — once the dataset (G) exceeds it, there is no more "just add more RAM" available, only "buy a bigger machine," which is not horizontal scaling and hits a wall regardless. Worse, that one node is also a hard single point of failure: it crashes, and every key it held is not just unavailable but gone, taking the entire cache offline for every client at once. The naive fix — run several independent standalone nodes and have clients pick one via hash(key) % N — solves the memory ceiling but not the crash problem, and introduces a new one: adding or removing a single node changes the result of that modulo for nearly every key, forcing almost the entire dataset to relocate (effectively a full cache flush) for one node joining or leaving, the exact failure this document already named in Prerequisites J.

K. Data Model & Store Choice

An in-memory hash table per shard, not a general-purpose database: the access pattern is exclusively "fetch/store/delete by exact key," never a range scan or a query — a plain hash map gives O(1) access, which is the entire point of reaching for a cache instead of a database in the first place. There is no relational structure to preserve and no query planner needed, the same "match the store to the access pattern, not the other way around" principle from Prerequisites B, taken to its simplest possible extreme.

Values are opaque byte blobs to the storage layer itself. Whether a value is a serialized object, a plain string, or a counter is a client-side concern (mirroring Redis's own richer data-type layer, Prerequisites D) — the core storage engine only needs to store and return bytes, plus the small amount of per-entry metadata (M) needed for eviction and TTL bookkeeping.

Optional disk-backed persistence (S) is a durability optimization layered on top of the in-memory store, never the primary store itself — every hot-path read and write still hits memory only; disk exists purely to speed up recovery after a restart, discussed fully in S.

L. End-to-End Flow — One GET Request Routed to Its Shard and Served

The client resolves ownership locally before ever making a network call — the ring lookup (N) never leaves the client process on the fast path.

M. Deep Dive 1 — Eviction Policies

Requirement this addresses: bounded, predictable memory per node (D) — once a node's cache is full, adding a new entry means something else has to go, and which entry is the whole question.

Why exact LRU is the wrong default despite being the "obvious" textbook answer: the whole point of a cache is that its most common operation, by an enormous margin, is a read — paying a write-sized cost (a list mutation, a lock) on every read directly fights the sub-millisecond latency requirement (D) this entire system exists to satisfy. Sampled approximate LRU trades a small, statistically negligible amount of precision for removing that cost entirely, which is exactly the trade real production systems make.

N. Deep Dive 2 — Consistent Hashing for Horizontal Scaling

Requirement this addresses: horizontal scalability (D) and directly fixes V1's fatal rehashing flaw (J) — this is the same mechanism already introduced in Prerequisites J and generalized as its own named pattern in the Patterns Playbook (Patterns L), applied here as the central partitioning decision of the whole problem rather than a supporting detail.

Ring plus virtual nodes: both physical nodes and keys are hashed onto points on a fixed circular ring; a key belongs to whichever node's point is the next one clockwise from it. Each physical node is assigned many virtual-node points scattered around the ring (not just one), which is what actually keeps load balanced — with only one point per node, pure hash luck could give one node a disproportionately large arc, and with it, a disproportionate share of keys.

Rebalancing on node add or remove — the property that makes this the right partitioning choice at all: when a node joins, it claims a set of virtual-node points and only the keys that fall in the small arcs immediately adjacent to those points need to move, migrated in the background directly from their old owner to the new one, while the rest of the ring's keys stay exactly where they were. Removing a node is the mirror image: its arcs are absorbed by their clockwise neighbors, and only those keys relocate. Neither case comes close to the "almost everything moves" failure of naive hash(key) % N (J).

Who keeps the ring up to date: nodes propagate ring-membership changes to each other via a lightweight gossip protocol, and the smart client library (I) holds its own periodically-refreshed copy — the same "everyone eventually agrees on current ownership, without a single bottleneck node being asked on every request" model used by Redis Cluster's cluster bus in practice (AD).

A request that lands on the wrong node during a brief rebalance window is handled with a redirect response pointing the client at the correct current owner (mirroring Redis Cluster's real MOVED/ASK responses) rather than being silently dropped or served incorrectly — a brief, self-correcting inconsistency, not a lasting one.

O. Deep Dive 3 — Replication for High Availability

Requirement this addresses: high availability (D) — consistent hashing (N) solves "which node owns this key" but says nothing about what happens when that one owning node crashes; without replication, losing a node still means losing that entire slice of the keyspace outright.

Leader-follower per shard, the standard model (Prerequisites C), applied at shard granularity rather than to the dataset as a whole: each shard has one leader taking all writes and, by default, all reads, plus one or more followers that continuously receive a stream of changes from it.

Failover: followers watch the leader's heartbeat; if it goes silent past a bounded threshold, the cluster's coordination layer promotes one follower to leader via the same lease-based election mechanism already used for Job Scheduler's triggering role (Prerequisites F, P10-M) — exactly one new leader is elected, the ring (N) is updated to point at it, and the shard resumes accepting writes, all without any human intervention.

Why followers serve reads rather than sitting idle (per F's assumption): a shard that only ever reads and writes through its leader wastes the follower's capacity entirely; letting followers serve reads spreads read load across the replica set — the same replica-read-scaling reasoning from Prerequisites C — at the direct cost of the staleness window discussed fully in V.

P. Deep Dive 4 — The Hot-Key Problem

Requirement this addresses: even load distribution (D) — and specifically the gap that N alone cannot close, per E's clarifying question 3.

Why a perfectly balanced hash function doesn't prevent this: consistent hashing (N) guarantees that keys are spread evenly across nodes by count — it says nothing at all about the traffic each individual key receives. A single viral key can receive orders of magnitude more requests than its neighbors on the ring, and because it correctly hashes to exactly one shard, that one shard's leader (and its followers, if read traffic is also skewed) absorbs the entire spike alone, no matter how well-distributed every other key is. This is a fundamentally different problem than an unbalanced ring, and "just add more shards" does nothing to fix it — the hot key still lands on exactly one of them.

• Client-side local (L1) caching of known-hot keys, with a short TTL — a thin, in-process cache directly inside each calling client absorbs a large share of repeat reads for a hot key before they ever reach the cluster at all, trading a small amount of extra staleness for removing the request from the network path entirely.
• Key splitting — store a hot logical key's value under several derived physical keys (key#0, key#1, ... key#N) that consistent hashing naturally scatters across different shards, and have clients pick one at random or round-robin on read; a write now has to fan out to all the split copies, a real added cost, but read traffic for that one logical key is spread across several shards instead of concentrated on one.
• Dedicated extra read replicas for specifically identified or predicted hot keys — rather than adding replicas uniformly across the whole cluster, add them only where monitoring (or predictable patterns, like a known upcoming product launch) shows the need, scaling read capacity for that one shard independently of the rest of the fleet.

Why this deserves its own deep dive rather than being folded into N: conflating "balance the keyspace" with "balance the traffic" is a common and understandable mistake — correctly separating them, and having a distinct answer for each, is a clear signal of real production experience with caching systems rather than textbook familiarity with hashing alone.

Q. Deep Dive 5 — Cache Invalidation Strategies

Requirement this addresses: the TTL functional requirement (D) plus the broader question of keeping cached data from silently drifting from its source of truth — famously one of the two genuinely hard problems in computer science.

TTL as a first-class property of every entry, not an optional extra: every CacheEntry (H) carries an expires_at, even if that value is "very far in the future" for effectively-permanent data — treating expiration as the norm rather than the exception is what makes automatic cleanup (M, R) a uniform mechanism instead of a special case bolted on for the entries that happen to have a TTL set.

Explicit invalidation on write: alongside write-around, a write to the source of truth also issues a DEL for the corresponding cache key, so the next read is a clean miss that repopulates fresh data rather than serving a now-incorrect cached value until its TTL happens to expire on its own.

Thundering herd / cache stampede: when a single hot key's TTL expires, every concurrent request for it misses at the same instant and every one of them independently hammers the database to refetch the same value simultaneously — a self-inflicted traffic spike against the system this cache exists to protect. The fix is request coalescing: the first miss for a given key triggers the actual database fetch and marks that key as "refill in progress"; every other concurrent request for the same key waits on that one in-flight fetch instead of issuing its own, and all of them are satisfied once it completes. Where coalescing isn't practical, a short-lived distributed lock (Prerequisites E) around the refill step achieves the same effect — only the lock holder refetches, and this is exactly the kind of "protect one critical, narrow operation" case Prerequisites E names as the legitimate reason to reach for an external lock at all.

R. Deep Dive 6 — Memory Management & Eviction Under Pressure

Requirement this addresses: bounded, predictable per-node memory (D) — M decided which entry to evict; this decides when eviction actually happens and what happens if it can't keep up.

maxmemory policy, a hard per-node cap: each node is configured with a fixed memory ceiling and a policy for what to do once it's reached — evict something under one of M's policies to make room (the normal, expected behavior), or reject new writes outright with an out-of-memory error rather than evict anything at all, for workloads where "never lose a cached value early" matters more than "always accept new writes" (mirroring Redis's real maxmemory-policy options, including its literal noeviction setting).

Memory fragmentation: as entries of varying sizes are constantly created and freed, the freed gaps left behind don't always line up with the size of the next allocation that needs space, so a node's actually usable memory can be meaningfully less than its physical RAM even while plenty of memory is nominally "free" — a large factor behind G's conservative "usable RAM" estimate, and why allocator choice (e.g. jemalloc over the platform default) is a real, practical lever in production caching systems, not a micro-optimization.

OOM prevention as a design stance, not an afterthought: the system deliberately fails a write explicitly and immediately once truly out of room, rather than letting the underlying process actually exhaust system memory and get killed by the OS — an explicit, recoverable error is a far better failure mode than the whole node (and every key it owns) going down.

Eviction as background work, not purely inline: checking every single key for expiration or over-limit status on every write would add cost to the hottest path in the system; instead, a background reaper thread proactively scans and evicts expired/over-limit entries on its own schedule, while a lightweight lazy check on access (mirroring Redis's active-plus-lazy expiry hybrid) catches anything the background pass hasn't reached yet — most of the cleanup cost is moved off the request path entirely.

S. Deep Dive 7 — Persistence & Recovery

Requirement this addresses: directly revisits E's clarifying question 1 — even granting F's pure-cache-semantics assumption, a cluster that has to rebuild every shard from nothing after every restart pays a real, recurring cost.

Why a cache would want any durability at all, given it's not the source of truth: persistence here is a warm-up optimization, not a correctness requirement — the real, current answer for any key still lives in the backing database (F's cache-aside assumption). Without it, a cluster-wide restart (a deploy, a power event) produces a fully cold cache across every shard simultaneously, and every single key becomes a guaranteed miss at once — precisely the thundering-herd scenario named in Q, except triggered by an operational event instead of a single key's TTL, and hitting the database with the traffic of the entire cache's worth of misses at once instead of one key's.

Warm-up strategy, in priority order: if a live, already-warm follower exists for a shard (O), the fastest recovery path is simply promoting or resyncing from it — no disk load needed at all. Only when no live replica exists does a node fall back to reloading from its own RDB snapshot or replaying its AOF log, trading some recovery time for not needing to hit the backing database cold.

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

What stays stable throughout: the tiny GET/SET/DEL contract from I — every later refinement changes how a key is routed, replicated, evicted, or recovered, never the basic shape of what a client calls.

V. Consistency Model

This is, by explicit design (F, O), a system built on eventual/weak consistency between a shard's leader and its followers — a follower's copy of any given key can lag the leader by some small, bounded window (replication lag, Prerequisites C), and a read served from that follower can return a value that's already stale by that same window. Reading from the leader only recovers read-your-own-writes and full strong consistency for that shard, at the direct cost of losing the read-scaling benefit that letting followers serve traffic provides (O) — clients that need to guarantee seeing their own immediately-preceding write (for example, right after a SET) should route that specific follow-up read to the leader, or accept a short client-side "sticky to leader" window after writing, rather than assuming every read anywhere in the cluster reflects every write everywhere. This is the same narrow, deliberate trade of a small strongly-consistent island (the leader, for a brief post-write window) against a much larger eventually-consistent surface (everywhere else, everywhen else) used throughout this document — here, uniquely, applied to the caching layer itself rather than to something the cache merely sits in front of.

W. Failure Scenarios

• A shard's leader crashes: its heartbeat goes silent, a follower is promoted via lease-based election (O), and the ring (N) is updated to point at the new leader — writes since the last replicated update may be lost (per the async-replication trade-off), but the shard itself becomes available again within one election cycle, not permanently unavailable.
• A follower crashes: no impact on writes at all; read capacity for that shard temporarily drops to whatever remains, and the follower resyncs from its leader once it recovers.
• A node is added or removed from the cluster: only the keys in the ring arcs immediately adjacent to the change actually migrate (N); everything else on the ring is entirely unaffected.
• A single key becomes disproportionately hot: the shard owning it absorbs elevated load regardless of how well-balanced the rest of the ring is, until one of P's mitigations (local caching, key splitting, dedicated replicas) is applied.
• A node approaches its memory limit: eviction (M, R) proactively frees space under the configured policy; if configured for noeviction instead, new writes are rejected outright with an explicit error rather than the process crashing from real OOM.
• The whole cluster restarts (a deploy, a power event): without persistence, every shard comes back fully cold and the backing database absorbs the resulting miss storm; with RDB/AOF (S), each node warms up from disk (or, faster, resyncs from an already-warm follower) instead.

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• A single, unpartitioned cache node with no replication. A hard memory ceiling and a hard single point of failure at once — the most important mistake to avoid on this problem.
• Naive hash(key) % N client-side sharding. "Solves" the memory ceiling while quietly reintroducing a full-keyspace-reshuffle problem on every scaling event.
• Exact, textbook LRU implemented with a real shared linked list under concurrent access. Turns the system's most frequent, most latency-sensitive operation into a lock-contended one, directly undermining the core latency requirement.
• Treating a well-balanced hash ring as sufficient protection against hot keys. Confuses balancing key count with balancing key traffic — two genuinely different problems with two genuinely different fixes (P).
• No TTL story at all, or TTL bolted on as an afterthought rather than a property every entry carries. Leads to unbounded memory growth from data that should have expired long ago, and ad hoc, inconsistent cleanup logic.

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: proposes a single cache node or naive hash % N sharding with no discussion of what happens on a topology change or a node crash; treats "use LRU" as a complete answer with no acknowledgment of what that actually costs at scale.
• Mid-level: correctly reaches for consistent hashing and leader-follower replication, but doesn't reason about what happens to reads/writes during a rebalance or failover, and hasn't considered that a well-balanced ring says nothing about balanced traffic.
• Senior: proactively distinguishes exact LRU from approximate/sampled LRU and explains why the approximation is the right production choice; treats TTL as a first-class property of every entry; is explicit about the eventual-consistency window between leader and followers rather than glossing over it.
• Staff+: raises the hot-key problem unprompted as distinct from load balancing generally; reasons concretely about cache-stampede/thundering-herd mitigation via request coalescing; discusses persistence as a warm-up optimization rather than a correctness requirement, and can explain precisely why it isn't the latter.

AC. Interview Simulation

AD. Online Solution Comparison

AE. Interview Cheat Sheet