Cruxly › System design › Scaling Building Blocks

Distributed Cache Cluster

sharding a cache so adding one node doesn't invalidate almost everything

Prompt: design a distributed cache cluster (like a Memcached or Redis cluster) — many cache nodes, clients shard keys across them, and the cluster must keep working, with minimal cache-miss disruption, when nodes are added or removed.

40 minutes first. Naive sharding (hash(key) % N) works fine until N changes — then it fails in a specific, expensive way.

Applying the four moves: Scope — many cache nodes, client-side key sharding, keep working with minimal disruption when nodes join or leave; persistence out. Estimate — the fraction of keys that move when one node is added: roughly all of them with hash % N, roughly 1/N with consistent hashing — that single number is the whole case. Sketch — consistent hashing on a ring, with virtual nodes per physical node to keep load even. Deep dive — what a rebalance actually costs: every moved key is a cache miss that lands on the database, so membership changes need to be gradual, and hot keys need replication rather than one owner.

Why hash(key) % N breaks the moment N changes

Scope. In scope: key-to-node sharding, rebalancing on node add/remove, replication for availability, client-side versus proxy-based routing. Out of scope: the cache eviction policy within one node (covered in this track's cache-topology lesson — a different, orthogonal question from sharding across nodes).

The naive approach, node = hash(key) % N, works cleanly as long as N never changes. The instant N changes — a node is added to handle more load, or one dies — nearly every key's hash(key) % N result changes, because the modulus itself changed. This means nearly every key now maps to a different node than the one that (maybe) has it cached, which is functionally equivalent to a full cache flush at the exact moment the cluster is under stress from a topology change — the worst possible time for a thundering herd of cache misses to hit the origin/database all at once.

Consistent hashing: bounding the disruption to roughly 1/N

Consistent hashing turns a topology change from "nearly every key moves" into "only the keys on one arc of the ring move."

Consistent hashing maps both nodes and keys onto the same abstract ring (typically via a hash function mapping to a large numeric space, 0 to 2^32-1, treated as circular). A key belongs to the first node encountered going clockwise from the key's position on the ring. When a new node is added, it only takes over the keys in the arc between itself and the previous node clockwise — every other key's assignment is completely untouched, because their nearest clockwise node hasn't changed. This bounds the disruption from a topology change to roughly 1/N of all keys, instead of nearly all of them — the single idea that makes dynamic cluster resizing practical at all.

Virtual nodes fix the remaining problem: with only a few real nodes on the ring, the arcs between them can be very uneven, giving some nodes far more keys (and load) than others purely by the luck of where their hash landed. Assigning each physical node many virtual positions on the ring (100+ per physical node is typical) averages this out — a node's total key share becomes the sum of many small, independently-placed arcs rather than one large, unpredictably-sized one, converging toward roughly even load distribution across physical nodes regardless of how their hashes happened to land.

Replication and the client-routing question

Each key is typically stored on the N nodes immediately clockwise from its ring position, not just one — replication factor 3 is common, matching this track's other replication discussions. This means losing one node doesn't lose any data outright, only the copies that node held, which the other replicas still serve while the cluster heals.

Who decides which node a request goes to is a real architectural choice, not a detail. Client-side routing (the client library itself computes the consistent-hash ring and talks directly to the right node) avoids an extra network hop but means every client needs to stay in sync with cluster topology changes — a client with a stale view of the ring sends requests to the wrong node, which either fails or (worse) silently reads/writes the wrong replica. Proxy-based routing (a stateless proxy layer in front of the cluster holds the current topology and forwards requests) centralizes that complexity into one place that's easier to keep consistent, at the cost of an extra hop and the proxy layer itself needing to scale and stay available. Redis Cluster uses a hybrid: clients cache a slot-to-node mapping and get redirected (a MOVED response) on a mismatch, self-correcting their cache — worth naming as a real middle ground between the two pure approaches.

Failure modes and the honest edges

A node rejoining after a brief outage may have significantly stale data for the keys it's responsible for — decide explicitly whether it should serve reads immediately (accepting staleness) or first resync from a replica before rejoining reads, the same freshness-versus-availability tradeoff that runs through this track's other consistency discussions.

Hot keys don't get fixed by better hashing at all — consistent hashing distributes distinct keys evenly, but if one specific key gets a disproportionate share of all traffic (a viral post's cache entry), every request for it lands on the same one or few nodes no matter how well the rest of the keyspace is balanced. The fix is key-level, not ring-level: client-side local caching of hot keys, or splitting one hot key into several sub-keys with a resolver that fans out — the same idea covered in this track's caching material.

A full cluster resize (doubling node count) still moves a meaningful absolute number of keys even at a bounded ~1/N fraction — at large scale, "only 10% of keys move" can still be billions of keys, so rebalancing needs to be throttled/rate-limited rather than moved all at once, to avoid saturating inter-node bandwidth during the resize itself.

Consistent hashing says nothing about read-your-own-writes consistency across replicas — if a write goes to the primary replica and a subsequent read from a different replica hasn't caught up yet, the client sees stale data despite hitting "the cache." This is the same replication-lag caveat covered in this track's replication material, worth reconnecting here rather than treating cache replication as magically exempt from it.

How to say it in the interview

"The question that decides this whole design is: when a node joins or leaves, what fraction of keys suddenly hash to a different node than before? With modulo hashing the answer is almost all of them, and that's the entire reason consistent hashing exists."

Checklist

Explained precisely why hash(key) % N remaps nearly every key when N changes
Used consistent hashing to bound topology-change disruption to roughly 1/N of keys
Added virtual nodes to fix uneven load distribution among a small number of physical nodes
Replicated each key to the N nodes clockwise from its position, not just one
Compared client-side and proxy-based routing on where topology-sync complexity lives
Named Redis Cluster's hybrid redirect-and-self-correct approach as a real middle ground
Identified hot keys as a failure mode that better hashing cannot fix
Recognized that a bounded ~1/N fraction can still be billions of keys at scale, requiring throttled rebalancing
Connected cache replica reads back to the same replication-lag caveat covered elsewhere in this track

Practice this interactively