
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
YouTube Videos
- “Consistent Hashing in System Design” - Gaurav Sen [https://www.youtube.com/watch?v=Ibf7wKf8MqU]