Skip to content
ADevGuide Logo ADevGuide
Go back

Consistent Hashing: Caches, Sharding and Rebalancing

By Pratik Bhuite | 7 min read

Hub: Java / Interview Fundamentals

Series: Backend Interview Mastery

Last verified: Sep 19, 2026

Part 58 of 88 in the Backend Interview Mastery

Key Takeaways

On this page
Reading Comfort:

Consistent hashing ring distributing keys across cache and database nodes

When a cache adds one server, a naive hash(key) % nodeCount remaps most keys and causes a thundering herd of misses. Consistent hashing places nodes and keys on a logical ring so a membership change moves only a fraction of keys. Continue from distributed caching, database sharding, and quorum reads and writes.

Table of Contents

Open Table of Contents

How the Ring Works

Hash each node ID and key into the same range. A key belongs to the first node encountered clockwise. Adding or removing one node affects the interval immediately before that node rather than every key.

flowchart TD
    A[Key user:42] --> B[Hash to ring position]
    B --> C{Clockwise successor}
    C --> D[Node B owns key]
    E[Node D added] --> F[Only preceding interval moves]
    F --> D

The ring reduces remapping, but it does not make movement free. Moved cache keys miss, and moved database partitions need data transfer, dual reads, or a migration protocol. Keep the hash function and node membership versioned so clients agree on ownership.

Virtual Nodes and Balance

One physical node gets many virtual-node points. Without them, a small ring can place large key ranges on one server. Weight virtual nodes by capacity when machines differ, and choose enough points to keep range size variance within a measured bound.

Use a sorted array of points and binary search for O(log V) routing, where V is the number of virtual points. Cache the ring in each client but update it from a signed or authenticated membership stream. A stale ring should produce a bounded retry, not writes to an arbitrary node.

Rebalancing and Hotspots

A popular key can overload its owner even when the ring is balanced. Add request coalescing, key replication, or a salted key strategy for hot items. For databases, split a hot tenant or time range rather than blindly adding nodes.

During migration, dual-write new data, read the new owner first with a fallback, verify checksums or counts, and remove the old copy only after a stable window. For caches, warming asynchronously is safer than synchronously copying every entry before admitting traffic.

A Safe Routing Client

function owner(key: string, points: Array<{ hash: number; node: string }>) {
  const target = hash32(key);
  let lo = 0,
    hi = points.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (points[mid].hash < target) lo = mid + 1;
    else hi = mid;
  }
  return points[lo % points.length].node;
}

Include a ring version in requests and metrics. If the node rejects an unknown version, refresh membership and retry once. More retries can amplify an outage, so combine this with backpressure and bounded timeouts.

Interview Questions

1. Why is modulo hashing problematic?

Changing the node count changes the modulus for almost every key, so most cache entries move at once. That creates misses, load spikes, and database pressure. Consistent hashing limits the affected ranges to the new or removed node’s neighbors.

2. What are virtual nodes for?

They spread each physical node across many ring positions, reducing range imbalance and making capacity changes smoother. They also let the system assign more points to larger machines. More points improve balance but increase membership metadata.

3. Does consistent hashing solve hot keys?

No. A single popular key still maps to one owner. Replicate hot keys, coalesce concurrent loads, or split the logical key when the business permits. Monitor per-key or per-tenant skew rather than only node averages.

4. How do you migrate a shard safely?

Version the ring, copy or dual-write the affected range, verify the new owner, and switch reads gradually. Keep a fallback during the transition and make writes idempotent. Delete the old copy only after lag and error metrics stay within bounds.

5. What if clients have different rings?

They may route reads and writes to different owners, causing misses or inconsistency. Publish membership atomically with a version, include that version in requests, and reject or redirect stale clients. A control-plane outage should not silently produce divergent maps.

Conclusion

Consistent hashing limits remapping, but production quality comes from virtual-node weighting, hot-key controls, versioned membership, and a staged migration. Treat the ring as a routing contract and observe skew, movement, and repair work during every topology change.

References

  1. Karger et al.: Consistent hashing
  2. Amazon Dynamo paper
  3. Redis Cluster specification

YouTube Videos

  1. “Consistent Hashing in System Design” - Gaurav Sen [https://www.youtube.com/watch?v=Ibf7wKf8MqU]

Share this post on:

Next in Series

Continue through the [object Object] with the next recommended article.

Related Posts

Keep Learning with New Posts

Subscribe through RSS and follow the project to get new series updates.

Was this guide helpful?

Share detailed feedback

Previous Post
CAP Theorem Explained Without the 'Pick Two' Myth
Next Post
Distributed Locks: Leases, Failure Modes and Safe Use