hard Distributed Cache Clusters: sharding, replication & rebalancing

One cache node has a hard ceiling; scaling past it means splitting the keyspace, and the splitting rule decides how much data moves when a node comes or goes

A single cache node is bounded by its RAM and one process's throughput. To scale beyond that, you shard the keyspace across many nodes: every key is deterministically mapped to exactly one node by a hashing rule. The rule you pick determines what happens on the operation that hits every cluster eventually — adding or removing a node. Pick badly (hash(key) % N) and a single node change reshuffles almost the whole keyspace; pick well (consistent hashing) and only the minimal necessary slice moves.

Sharding: naive mod-N vs. consistent hashing

Naive: node = hash(key) % N. Simple, but N is baked into every lookup: change N (add or remove one node) and hash(key) % N changes for nearly every key, because the modulus itself changed. The traced table above shows it exactly: keys i=0..19 hashed by i % 4 vs. i % 5 — only the four keys smaller than both moduli (0,1,2,3) land in the same bucket both times; the other 16 (80%) move. In a live cache that means an 80% cold cache the instant you resize.

Consistent hashing: place both nodes and keys on a hash ring (e.g. positions 0..2³²−1); a key belongs to the first node clockwise from its hash position. Removing or adding one node only touches the arc between it and its counter-clockwise neighbor — every other node's arc is untouched. In the ring diagram, inserting node E between D and A only takes the small piece of A's arc; B, C, and D keep exactly the keys they had.

In practice each physical node is given many points on the ring (virtual nodes, e.g. 100–200 per node), not just one. This spreads the incoming/outgoing node's share evenly across all existing nodes instead of dumping it all on a single neighbor, and keeps load balanced even with few physical nodes.

Traced: 4 nodes, add a 5th

Scheme	What moves when N: 4->5	Why
Naive mod-N	~80% of keys (16 of 20 sample keys)	The modulus changed, so almost every key's hash % N result changed too
Consistent hashing	~1/5 (20%) of keys — exactly the arc between the new node and its counter-clockwise neighbor	Only the ownership boundary immediately next to the new node moves; every other node's arc is untouched

Replication: primary + replicas per shard

Each shard (key range) is stored on more than one node: one primary accepts writes, and R−1 replicas hold a copy for availability and read scaling. When the primary dies, a replica is promoted — and because it already had the shard's data, the promotion is instant and warm, unlike losing an unreplicated shard. The cost is memory ×R and a replication-lag window where a replica read can return a slightly stale value.

Client-side vs. proxy vs. cluster-gossip routing

• Client-side hashing (e.g. Ketama-style consistent hashing in a Memcached client): the client library computes the ring and talks directly to the owning node. Fewest hops, lowest latency — but every client process must agree on the same ring/topology, or two clients can route the same key to different nodes.
• Proxy-based (Twemproxy, mcrouter): a proxy tier sits between clients and cache nodes and does the routing itself; clients just talk to the proxy. Centralizes the routing logic (fix it once, works for every client language) at the cost of an extra network hop and a tier you must run and scale.
• Cluster gossip (Redis Cluster): nodes exchange topology among themselves (16,384 hash slots mapped to nodes); a client can contact any node and gets redirected (MOVED/ASK) to the slot's owner, or caches the slot map itself. No separate proxy tier, but clients need a cluster-aware driver and you're committed to that cluster's slot model.

Node loss and rebalancing

When a node dies, consistent hashing remaps its arc onto its neighbor(s) — but that neighbor's cache does not have those keys yet. Every request for a key that was on the dead node now misses at once: a cold-cache stampede onto the origin DB, the same mechanism as a synchronized TTL expiry (see Cache Stampede & Invalidation) — the fix family is the same: single-flight/lock the reload path, or pre-warm the inheriting node before cutting traffic to it. Scale-out rebalancing is the gentler mirror image: adding a node only pulls ~1/N of the keyspace onto it (cold for those keys specifically), while the rest of the cluster is undisturbed.

Pitfalls

• Sharding does not fix a hot key. Sharding balances the keyspace, not per-key load — a single viral key still hashes to exactly one shard, no matter how many nodes the cluster has, and that one node can be overwhelmed while the rest sit idle. See Shard Keys: many-key skew vs a single hot key — the fix is key-level (fan the one hot key out across several sub-keys, or replicate it locally), not adding more shards.
• Cold-cache stampede on node loss or rebalance. The moment any node's key range moves — failover or scale-out — the inheriting node is empty for those keys and every read for them misses simultaneously. Treat it exactly like a TTL-expiry stampede: single-flight the reload, or pre-warm before cutover.
• Replication lag surprises read-after-write. A read routed to a replica immediately after a write to the primary can return the old value — the same read-your-writes problem as database replicas. Route freshness-sensitive reads to the primary.

Judgment — the decisions that actually matter

Decision	Trade-off
Consistent hashing vs. mod-N	Mod-N is trivial to implement but unusable for a cluster you ever resize — nearly every key remaps. Consistent hashing costs a bit of ring bookkeeping (and ideally virtual nodes) for ~1/N remap. Pick consistent hashing (or a slot scheme like Redis Cluster) for any cluster you expect to grow or shrink.
Replication factor R	R=1 is cheapest but a node loss is a full cold-cache stampede for that shard and zero read scaling. Higher R buys availability and read fan-out at R× the memory cost and added replication overhead. Size R by how badly the origin DB tolerates a cold-shard stampede.
Client-side vs. proxy vs. gossip routing	Client-side is fastest but needs every client to agree on topology. A proxy centralizes routing logic (easy for many languages) but adds a hop and a tier to operate. Gossip (Redis Cluster) needs no separate tier but locks you into that cluster's slot model and cluster-aware clients.
Dedicated cache tier vs. local in-process cache	A local cache (e.g. an in-memory map per app instance) has zero network latency and no cluster to run — but N instances each cache independently, so an invalidation on instance 1 does not reach instances 2..N: the coherence problem. A shared cluster gives one source of truth for all instances at the cost of a network hop per access. Common answer: a small local L1 (short TTL) in front of a shared L2 cluster.

Takeaways

• Sharding solves capacity by splitting the keyspace; consistent hashing (not mod-N) is what makes resizing cheap — only ~1/N of keys move instead of ~80%+ under naive modulo hashing.
• Replication (primary + replicas per shard) buys availability and read scaling at the cost of memory×R and a replication-lag staleness window.
• Routing logic can live in the client, a proxy tier, or the cluster itself (gossip) — the trade-off is latency/hops vs. where topology complexity is operated.
• Sharding never fixes a hot key, and every rebalance (loss or scale-out) creates a cold-start stampede on the affected slice — both need a key-level or stampede-style fix, not more shards.

---

Sources: Karger et al., "Consistent Hashing and Random Trees" (STOC 1997); Kleppmann, "Designing Data-Intensive Applications" (ch. 6); Redis Cluster specification (hash slots & gossip); Twitter's Twemproxy documentation; DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007). See also: Cache Stampede & Invalidation, Shard Keys: many-key skew vs a single hot key, Consistent Hashing, Sharding Strategies: range vs hash vs directory vs geo, Online Resharding & Cross-Shard Operations. Re-authored/Deepened for this guide.

I just read a lesson on **Distributed Cache Clusters: sharding, replication & rebalancing** (System Design) and want to truly understand it. Explain Distributed Cache Clusters: sharding, replication & rebalancing from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Distributed Cache Clusters: sharding, replication & rebalancing** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Distributed Cache Clusters: sharding, replication & rebalancing** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Distributed Cache Clusters: sharding, replication & rebalancing** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.