Caching & Scale

Consistent Hashing

Map keys to nodes so adding or removing a node moves only a small fraction of keys.

Intermediate, about 60 minutes to read, 4 open questions to practise.

1Understand

The idea

Consistent hashing places keys and servers on a hash ring so when membership changes, only keys in the affected arc move, roughly 1/N of all keys when you add one node to N, unlike hash(key) % N which remaps almost everything. Interviews reach for it for elastic cache clusters, distributed KV, and L7 partition routing, not for SQL range analytics dominated by time scans.

Virtual nodes spread load when you have few physical machines. Replication walks clockwise to distinct hosts for fault tolerance. The skill is pairing the ring model with migration tooling and admitting hot keys are not fixed by hashing alone.

Contrast with directory-based sharding (lookup table) and range partitions (time buckets), consistent hash optimizes key→node stability on resize, not BETWEEN reporting queries.

Intuition

Modulo pain. shard = hash(key) % 10. Resize to 11 → most keys change destination → thundering herd of cache misses or terabytes to move. Interview one-liner: “modulo reshuffles O(keys); ring moves O(keys/N).”

Ring mechanics. Hash keys and nodes to 0…2³²−1 on circle. Owner = first node clockwise from hash(key). Add node → only keys between predecessor and new node migrate.

Virtual nodes (vnodes). Each physical host owns many points (e.g. 100-200) so arc widths stay even with 3-5 machines; without vnodes one server can own 60% of arc.

Join/leave. Add node: copy keys in arcs from neighbors. Remove node: reassign arcs clockwise; use handoff (get from new owner, delete old) to avoid stale reads during lazy migration.

Replication on ring. Primary at owner; replica R1 at next distinct physical node clockwise; R2 next after that, survive one host loss if reads allowed from replica.

Hot keys. Superstar product id still lands on one vnode arc, need local cache, read replicas, or key splitting (product:123:part-{0..7}).

LB consistent hash. Hash client IP or session id at load balancer for cache partition affinity, related but different layer from data ring.

Operational migration. Tools limit bytes/sec moved during node add; track progress per vnode; cancel resize if origin error budget burns. Interview bonus: mention bounded load papers conceptually without deriving math.

Manual override. Emergency cache flush still happens, consistent hash reduces how often you need cluster-wide invalidate, not never.

Client library note. Many caches implement ring logic in the driver, ops still plans vnode count and migration runbooks.

What you will be able to do

  • Contrast modulo hashing with consistent hashing on cluster change
  • Explain the ring and virtual nodes
  • Know when it helps caches vs relational sharding

When this comes up

  • Cache cluster resize
  • Distributed hash table
  • Minimal remapping
  • Virtual nodes

2See it

Architecture sketch

Hash ring

Keys and nodes share a ring. Add a node, move only nearby keys (~1/N), not everything.

100%
ClientOtherCache

Walkthrough

Add a node

Why % N remaps the world

1 / 4

100%

Three nodes on the ring. hash(key) maps clockwise to the next node.

Read the walkthrough as text

Worked example, Memcached cluster grows 6 → 8 nodes during holiday traffic.

Workload: product:{id} cache; no multi-key transactions; ~500M keys.

  1. Baseline: 6 physical nodes, 150 vnodes each; monitor per-node hit rate and arc width.
  2. Modulo alternative rejected: % 6 → % 8 would remap ~80%+ keys → origin DB meltdown, state why ring chosen.
  3. Add 2 nodes: only keys in new arcs migrate; background transfer with rate limit; clients dual-read during handoff optional.
  4. Hot key: product:viral → single arc hot; mitigate app-side local cache + singleflight to origin.
  5. Node loss: vnode arcs to successor; brief duplication if lazy delete, “read repair” pattern.
  6. Not for: “Reports by week” SQL, use date-range shards instead.
  7. Handoff window: clients may read stale vnode during migration, dual-read or brief TTL lowering acceptable.
  8. Monitoring: per-node hit rate, bytes migrated/sec, pending key count in migration queue.
  9. Interview close: cite Dynamo/Cassandra use rings; Redis Cluster hash slots, same family of ideas.

What interviewers listen for: ring + clockwise rule; vnode balance; ~1/N migration; hot key caveat; wrong-fit for range analytics.

Napkin math

Ring napkin

place nodes + keys on hash ring

key → first node clockwise

add 1 node → remap ≈ 1/N keys (not all)

virtual nodes (e.g. 100-200/vnode) smooth load

replicas: next R distinct nodes on ring

mod N remaps everything. A ring remaps a slice.

3Answer it

How to answer in an interview

When cache cluster resize, DHT, “how do you route keys to servers”:

  1. Modulo failure on N±1.
  2. Ring model, hash, walk clockwise.
  3. Vnodes for balance.
  4. Join/leave fraction moved + handoff.
  5. Replication on ring if durability needed.
  6. Fit, KV/cache vs SQL range scans.
  7. Hot keys, explicit mitigation.

Phrases: “only ~1/N keys move,” “virtual nodes even the arcs,” “consistent hash is not range partitioning.”

  1. Numeric anchor: 10 nodes → ~10% keys move on add-one-node resize vs modulo reshuffling nearly all keys.

Answer checklist

1. Problem: modulo hashing reshuffles almost everything on N±1. 2. Ring + hash(key) clockwise to node. 3. Virtual nodes for balance. 4. What moves on join/leave (~1/N with vnodes). 5. Where used (caches, some partitioners) vs when range shards are better.

Tradeoffs & numbers

  • vs modulo: stability on resize; more operational complexity (vnode tuning, migration jobs).
  • vs directory shard map: ring is decentralized; directory flexible but SPOF/scale on metadata service.
  • Many vnodes: better balance; more metadata per node.
  • Weak hash function: cluster imbalance, use stable hashes (Murmur, xxHash slice).
  • Range queries: poor unless keys share locality by design.
  • When NOT: relational warehouse time partitions; tiny static cache where modulo is acceptable.
  • Interview tip: quote ~1/N migration when adding a node to N, converts ring theory to a number.
  • Ring math anchor: add 1 node to 10-node ring → ~10% keys move; modulo would move ~100%.
  • Elasticity goal: add/remove cache nodes weekly without nightly full cache flush, that is the business justification.
  • Interview anchor: ~10% key churn on ring resize vs ~100% under modulo.

Kinds of questions (4)

Same pattern, different interview surfaces. Recognise which variant you are in before you answer.

  • Cache cluster membership change

    Example. Elasticache cluster autoscaling adds two nodes during Prime Day without flushing entire catalog cache. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.

    How. Ring join moves only affected key arcs; background key migration with rate cap; contrast modulo reshuffle storm. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.

  • Virtual nodes for balance

    Example. Only four beefy cache servers must each hold ~25% of keys despite unequal physical capacity labels. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.

    How. Assign 200 vnodes per host; monitor arc QPS; rebalance vnode count if one host runs hot after hardware change. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.

  • Replication along the ring

    Example. Session cache must survive loss of any single Memcached rack without mass logout. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.

    How. Primary vnode owner + R1 on next physical node clockwise; read-your-session from replica on primary timeout. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.

  • Modulo vs consistent hash

    Example. Interviewer asks why Redis cluster docs mention hash slots not `key % N`. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.

    How. Explain slot migration moves bounded key ranges; modulo resize invalidates nearly all mappings at once. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.

Common mistakes

Failure modes the AI coach watches for when you practise open questions.

Resize cost

Avoid. hash(key) % N. Add one cache host, almost every key misses.

Prefer. Consistent hash ring (often with vnodes). Resize moves ~1/N of keys.

Weak sketch

Bad

100%

Stronger sketch

Good

100%
  • Modulo on resize

    Why it happens. Modulo remaps nearly all keys when N changes, triggering cache stampede and massive data movement operators cannot complete in a maintenance window.

    How it fails. “We’ll scale Redis from 8 to 10 and update clients to `hash % 10` overnight.”.

    Fix. Consistent hashing ring with controlled vnode migration; expect ~1/N keys moved per added node.

  • No virtual nodes

    Why it happens. Few ring points on small clusters create uneven arc ownership and one server absorbing most traffic.

    How it fails. Three cache nodes, three hash points total; monitoring shows node-A at 70% hit QPS.

    Fix. Hundreds of virtual nodes per physical host; monitor and rebalance arc distribution.

  • Wrong tool

    Why it happens. Time-range analytics need locality of consecutive keys, not uniform key scatter around a ring.

    How it fails. Clickhouse-style weekly reports sharded only via consistent hash on `user_id` with full table scans anyway.

    Fix. Range/time partitioning for scans; use consistent hash for cache/KV membership elasticity.

4Practise

Concept check

A short quiz on this lesson before open questions. Optional, and it does not gate practice.

Open questions

Ready to practise?

Write an answer, get AI coaching, then revise. You are not building a real system.

Practise with an open question

All systems lessons