Consistent Hashing
Consistent hashing maps keys to nodes so membership changes move only a fraction of keys, unlike modulo hashing that remaps nearly everything. The basic ring is only a starting point. Senior candidates discuss virtual nodes, weights, replicas, bounded load, hot keys, membership convergence, rebalancing, failure domains, and alternatives such as rendezvous hashing, Jump Consistent Hash, and Maglev.
How to use this chapter
- Read the mental model and mechanics without taking notes.
- Close the page and explain the topic aloud in five minutes.
- Work the quantitative example on paper.
- Answer the question ladder without revealing the answer signals.
- Complete one design drill and score yourself with the senior checklist.
Learning objectives
- Explain why modulo hashing remaps keys and how a consistent-hash ring limits movement.
- Use virtual nodes/tokens and weights to improve balance and support heterogeneous capacity.
- Place replicas across failure domains and route reads/writes under node failure.
- Handle hot keys, membership changes, data transfer, and stale ring views.
- Compare ring hashing with rendezvous, jump, and Maglev-style approaches.
- Quantify movement and validate balance at senior level.
Mental model
Hash both nodes and keys into a large identifier space. In a ring scheme, a key belongs to the first node clockwise (or a defined token range). Adding a node takes ownership of only nearby ranges; removing one transfers its ranges to successors. This minimizes churn, but does not guarantee even load or solve replication, hot keys, or membership agreement.
Core mechanics
Modulo hashing problem
Simple hash(key) mod N distributes keys reasonably when N is fixed. Changing N alters the modulus, so most keys map to different nodes, causing a cache flush or massive data movement. This is acceptable for tiny static clusters but problematic for elastic distributed systems.
Consistent hashing aims for monotonicity: when membership changes, keys assigned to unaffected nodes mostly remain there. Expected movement when adding one equally weighted node to N is on the order of 1/(N+1) of keys, assuming good balance.
Ring and token ranges
Nodes receive positions/tokens in a circular hash space. A key hashes to a point and is assigned by the ring rule. A single token per node has high variance: some nodes own much larger arcs than others. Hash quality and token assignment matter.
Ring metadata must be versioned and replicated. Clients may route directly using the ring or ask a proxy/coordinator. Direct routing reduces a hop but spreads membership logic; coordinators simplify clients and can redirect when their view differs.
Virtual nodes and weights
Assign many virtual nodes/tokens per physical node. Their ranges interleave around the ring, averaging ownership and allowing gradual movement. A node with twice the capacity can receive roughly twice the token ownership. More tokens improve balance and rebalancing granularity but enlarge metadata and number of transfer streams.
Random token assignment is simple; deliberate token allocation can optimize balance and replica/failure-domain placement. Validate both key-count and weighted workload balance because uniform keys can have nonuniform traffic/value sizes.
Replication
A key is often stored on the primary owner plus the next R−1 distinct nodes or according to a placement strategy that skips same rack/zone. Naively taking adjacent ring nodes can place replicas in the same failure domain if tokens are not topology-aware.
Read/write coordinators choose replicas based on consistency policy. During failure, hinted handoff or temporary replicas may accept writes, followed by repair. Consistent hashing chooses candidates; quorum/version/conflict mechanisms define correctness.
Membership and stale views
Membership can come from a strongly consistent control plane, gossip, or configuration. With gossip, nodes may temporarily disagree about ownership. Requests need forwarding, version checks, and idempotency. During planned changes, use explicit states such as joining, streaming, active, leaving, and removed.
Avoid assigning traffic before the joining node has required data, and avoid deleting old replicas before new copies are durable. Epoch/fencing numbers prevent stale owners from accepting writes after removal.
Rebalancing and repair
Adding/removing nodes triggers range streaming. This consumes disk, network, cache, and CPU and can hurt foreground traffic. Throttle by resource and priority, copy a snapshot then catch up deltas, verify checksums, and keep old replicas until cutover is safe.
Background anti-entropy compares replicas and repairs divergence. Merkle trees or range checksums can locate differences without scanning/transferring everything. Repair cadence affects inconsistency window and resource cost.
Hot keys and bounded load
Consistent hashing balances many independent keys in expectation; it cannot split one extremely hot key. Replicate hot reads, add local caches, shard the logical value, or route through a special hot-key layer. Detect hot keys before the node saturates.
Bounded-load consistent hashing allows a key to choose alternate nodes when its nominal owner exceeds a capacity bound, trading strict placement/locality for better balance. For caches, this can prevent overload; for authoritative stores, relocation requires metadata/replication correctness.
Alternatives
Rendezvous (highest-random-weight) hashing scores each key against nodes and picks the highest; it is simple, supports top-R replicas, and minimizes movement but naïvely costs O(N) per lookup. Jump Consistent Hash maps to numbered buckets with low memory and movement but assumes contiguous buckets and has limited weighting/topology flexibility. Maglev builds lookup tables for fast, stable load-balancer backend selection.
Choose based on lookup cost, membership size/change rate, weighting, replica selection, and need for a compact client-side table. “Consistent hashing” is a family, not one ring implementation.
Decision table
| Decision | Prefer the first option when… | Prefer the second option when… | Senior caveat |
|---|---|---|---|
| Ring vs rendezvous | Range ownership/streaming and established ring tooling matter. | Simple top-K placement and easier membership changes matter. | Rendezvous lookup may need optimization for large N; ring needs token management. |
| Few vs many virtual nodes | Metadata simplicity and deliberate range control dominate. | Balance, weights, and fine rebalancing dominate. | Too many tokens increase control/repair overhead; use empirical balance targets. |
| Client-side vs proxy routing | Clients are controlled and one less hop/parallel replica access matters. | Simple clients and centralized membership/security matter. | Stale client views need redirects/retries; proxy becomes capacity/failure layer. |
| Adjacent replicas vs topology-aware placement | Cluster is one failure domain or simplicity is acceptable. | Rack/zone failures must be tolerated. | Token adjacency alone is not a fault-domain policy. |
| Automatic rebalancing vs operator-controlled | Small changes and robust throttling make automation safe. | Large state movement or strict change windows require staged control. | Automation needs budgets, pause/rollback, and foreground SLO guardrails. |
| Strict owner vs bounded-load alternate | Authoritative storage and predictable locality dominate. | Cache/load-balancer balance under skew dominates. | Alternate placement requires discoverability and can reduce cache locality. |
Quantitative reasoning
Failure modes and production signals
| Failure mode | What users see | Likely cause | Mitigation / design response | Useful signals |
|---|---|---|---|---|
| Token imbalance | Some nodes fill/saturate early | Too few/random tokens or poor weights | Reassign tokens, add vnodes, capacity-aware placement | Owned bytes/QPS per token/node, max/mean |
| Hot key | One node overloaded despite balanced keyspace | Single popular key/value | Replicate/cache/split key, rate limit, special routing | Top-key QPS/bytes, per-node skew |
| Stale membership | Redirect loops, misses, conflicting writes | Clients/nodes use different ring epochs | Versioned membership, forwarding cap, fencing, consistent control plane | Epoch mismatch, redirects, stale-owner writes |
| Repair cascade | Foreground latency spikes during node loss | Unthrottled range streaming/anti-entropy | Resource-aware throttle, priority, spare capacity, gradual repair | Repair bandwidth/IOPS, foreground p99, queue depth |
| Correlated replica placement | Zone/rack loss removes all copies | Topology ignored by token order | Failure-domain-aware replica policy and audits | Replica-domain diversity, risk simulations |
| Join-before-ready | Reads miss or stale after adding node | Traffic routed before data catch-up | Joining state, snapshot+delta, readiness barrier, keep old owner | Range readiness, catch-up lag, fallback reads |
Senior-level lenses
Hash key selection determines skew
Hashing a tenant ID keeps all tenant data together but makes large tenants hot. Hashing object ID spreads load but makes tenant scans scatter. Composite keys can bucket a tenant by time or suffix. Start from access patterns and cross-key operations, not the hash function alone.
Placement and consistency are separate
Consistent hashing tells where replicas should be. It does not define leader election, quorum, conflict resolution, durability, or read freshness. Explicitly pair placement with replication semantics.
Membership changes are transactions
A safe move has prepare/copy/catch-up/activate/retire phases and a rollback boundary. Use epochs and fencing so two owners do not both accept authoritative writes indefinitely. Track data completeness, not only process health.
Simulate with real distributions
Uniform random keys hide tenants, value-size skew, temporal hotspots, and correlated access. Run placement simulations using sampled production keys and weights, test node/zone removal, and report p50/p99/max load plus bytes moved.
Capacity includes failure and repair
Losing a node adds replica traffic and foreground load to survivors. If the cluster runs at 80% disk or network, repair can violate SLO or never catch up. Reserve spare capacity and cap concurrent membership changes.
Stable placement can conflict with perfect balance
Minimal movement preserves caches and reduces transfer, while aggressive load balancing moves more keys. Decide which cost dominates and use bounded-load or selective hot-key migration rather than constant global churn.
Interview question ladder
Why is modulo hashing bad when node count changes?
Show strong-answer signals
Changing N changes most hash mod N results, causing broad remap; consistent hashing limits movement to neighboring ranges/top scores.
What is a virtual node?
Show strong-answer signals
Multiple logical token positions owned by one physical node, improving balance, weights, and movement granularity.
Does consistent hashing solve hot keys?
Show strong-answer signals
No; it balances many keys probabilistically. One hot key needs replication, caching, splitting, or special handling.
How do you place three replicas on a ring?
Show strong-answer signals
Primary owner plus additional distinct nodes/tokens, but enforce rack/zone diversity and avoid duplicate physical nodes due to vnodes.
What happens when a node joins?
Show strong-answer signals
Assign token ranges, stream snapshot from current replicas, catch up deltas, verify, mark ready/activate, then retire old ownership; throttle and version membership.
Compare ring and rendezvous hashing.
Show strong-answer signals
Both minimize movement; ring maps ranges/tokens, rendezvous scores nodes per key and naturally selects top-K. Compare lookup, metadata, weights, and streaming.
Design partition placement for a distributed cache with heterogeneous nodes.
Show strong-answer signals
Weighted vnodes/rendezvous, replication, bounded load, health/membership, client/proxy routing, hot-key L1, gradual rebalance, simulation and metrics.
How do you prevent stale clients from writing to a removed owner?
Show strong-answer signals
Membership epochs, server-side validation/redirect, fencing tokens/leases, idempotent retry, coordinator or consensus-backed ownership, cap redirect loops.
A zone loss leaves replicas available but repair overloads the cluster. What changes?
Show strong-answer signals
Topology-aware capacity, repair throttle/priorities, staged concurrency, spare disk/network, temporary replicas, foreground admission, restore zone before full rebalance when appropriate.
Choose a shard key for a multi-tenant time-series system.
Show strong-answer signals
Tenant+time bucket+hash suffix trade-offs, large tenants, range queries, retention, write hotspots, scan fan-out, rebalancing, and directory for tenant placement.
Design a placement service that supports online node weights and zone evacuations.
Show strong-answer signals
Consensus/versioned membership, simulation/planner, constrained optimization for weights/domains/movement, staged plans, data readiness, fencing, throttles, pause/rollback, audit.
When would you reject consistent hashing entirely?
Show strong-answer signals
Small/static clusters; range queries needing ordered partitioning; directory-based placement for tenant isolation/moves; consensus leader groups; workloads where explicit mapping and operational control outweigh hash simplicity.
Design drills
Design a 500-node cache across five zones with 3× replication, mixed node sizes, and hot keys. Specify placement, membership, rebalancing, client routing, and failure behavior.
What the interviewer is testing
Moving beyond the textbook ring into topology, weights, and operations.
A SaaS database has 100k tenants, with the largest 20 consuming half the load. Compare consistent hashing, range/directory placement, and dedicated shards. Plan an online tenant move.
What the interviewer is testing
Skew and isolation often favor hybrid placement rather than pure hashing.
After adding 20% capacity, cache hit ratio collapses and databases overload. Diagnose possible token/client/version mistakes and define a safe rollout.
What the interviewer is testing
Expected movement, double population, stale views, warmup, and source protection.
Common weak answers and how to improve them
“Consistent hashing evenly distributes load.”
Show the stronger answer
It limits movement and balances uniform keys in expectation; use vnodes/weights and handle hot keys/size skew.
“Put replicas on the next two nodes.”
Show the stronger answer
Ensure distinct physical nodes and failure domains; topology-aware placement is required.
“Adding a node moves 1/N of data.”
Show the stronger answer
Roughly 1/(N+1) in a balanced equal-weight case; actual bytes depend on token and value skew.
“Gossip handles membership.”
Show the stronger answer
Describe epochs, stale views, forwarding, fencing, join readiness, and conflict behavior.
“Rebalancing happens automatically.”
Show the stronger answer
Specify transfer phases, resource throttles, verification, rollback, and foreground SLO guardrails.