Logical circular space 0 to 2^n-1
Data / Knowledge library
Consistent Hashing
Maps keys and nodes onto a ring so membership changes move relatively few keys
Why learn Consistent Hashing?
It supports elastic distributed caches and partitions
The problem it solves
It reduces reshuffling when storage nodes join or leave
Where it came from
Consistent Hashing is a algorithm that maps keys and nodes onto a ring so membership changes move relatively few keys. Its guarantees and tradeoffs depend on the concrete implementation and operating context.
Build your understanding
Work through these exercises in order. Try the task before opening a reference.
- Define Consistent Hashing and distinguish it from a neighboring concept.
- Choose a realistic task where Consistent Hashing is appropriate.
- Identify a failure mode caused by misusing Consistent Hashing.
- Interpret a small design or result involving Consistent Hashing.
- Explain one tradeoff or limitation of Consistent Hashing.
Documentation and sources
- NIST Dictionary of Algorithms and Data Structures (xlinux.nist.gov)
Connect the ideas
Explore next
Real World Example
Dynamic Cache Scaling for Global Content Delivery
A global media streaming platform that caches video fragments across distributed edge servers.
The business problem
When the number of edge servers changes, traditional modulo-based hashing causes a massive remapping of keys, resulting in cache misses that overwhelm the origin server during scaling events.
How this topic solves it
Consistent hashing maps both keys and nodes onto a logical ring using a hash function. By assigning each node to multiple points on the ring, the system ensures that when a node is added or removed, only the keys in the immediate neighborhood of that node need to be remapped, rather than the entire dataset.
- Map all available edge server nodes to multiple positions on a circular hash ring.
- Hash each incoming content request key to a specific point on the same ring.
- Traverse the ring clockwise from the key's position to find the first encountered node.
- Route the request to that identified node for cache retrieval.
- Update only the affected segments of the ring when a node joins or leaves the cluster.
Shows how keys are mapped to the nearest clockwise node on a ring.
Physical server at position X
Physical server at position Y
Request hash at position Z
- Content Key → maps to nearest clockwise → Node A
- Node A → ring progression → Node B
Expected business outcome
The platform achieves stable cache hit ratios during infrastructure scaling, preventing origin server overload.
Limitations and checks
The primary trade-off is the potential for non-uniform distribution of keys across nodes, which can lead to hotspots; this is checked by monitoring the load variance across nodes and increasing the number of virtual nodes per physical server to improve balance.