Consistent Hashing
Partition keys across changing nodes while minimizing how much data moves when the cluster scales.
Add a node → move one slice, not every key.
Hash nodes and keys onto a ring → walk clockwise to the first owner
refresher
Consistent hashing maps both nodes and keys into the same hash space. A key belongs to the next node clockwise. Adding or removing a node changes ownership for only a neighboring slice instead of remapping nearly every key.
What problem does it solve?
With hash(key) % N, changing the node count changes the result for most keys. That creates a massive reshuffle precisely when a cluster is already scaling or recovering. Consistent hashing stabilizes ownership across membership changes.
How it works
- Hash each physical node onto multiple positions called virtual nodes.
- Hash each key into the same numeric space.
- Walk clockwise from the key to its first node position.
- Replicate to the next distinct physical nodes for resilience.
- When membership changes, transfer only affected ranges.
Move nodes and keys
Consistent hashing playground
Add and remove nodes to see which keys change owners. The ring uses deterministic positions so every change is explainable.
Key trade-offs
| Choice | What you gain | What it costs |
|---|---|---|
| More virtual nodes | Smoother distribution and capacity weighting | More metadata and range movement |
| Fewer virtual nodes | Simpler ownership maps | Higher risk of uneven load |
| Replication around ring | Node-failure tolerance | Correlated placement unless failure domains are considered |
What happens if?
A node leaves unexpectedly
Its successor temporarily owns the failed ranges and may receive a sudden traffic surge. Replicas preserve availability, but recovery must be rate-limited to avoid turning one failure into overload.
One key receives 40% of requests
Even perfect partition balance cannot split a single hot key. The system needs key replication, request coalescing, caching, or a domain-specific way to shard that item.
Real systems
Amazon Dynamo popularized the model for distributed key-value stores. Variants appear in Cassandra, DynamoDB, caches, proxies, and request routers. Modern systems often use centrally managed range maps when they need tighter placement control.
Senior interview modeWhy do virtual nodes improve consistent hashing?Show answer
Physical nodes receive multiple small, scattered ranges rather than one contiguous slice. This reduces statistical skew, makes rebalancing more granular, and allows stronger machines to receive proportionally more positions.