Consistent Hashing in Dynamo
You'll learn how Dynamo distributes data across nodes and handles cluster changes without massive data movement.
The Core Idea
Dynamo uses consistent hashing to map both data keys and storage nodes onto a circular hash ring (imagine a clock face with 0-360 degrees). Each data item gets hashed to a position on this ring, and the node responsible for that data is the first node encountered when moving clockwise around the ring.
The genius addition: virtual nodes. Instead of placing each physical server once on the ring, Dynamo assigns each server many positions (tokens). A single physical machine might occupy 100-500 positions scattered randomly around the ring.
Why Virtual Nodes Matter
Without virtual nodes, adding or removing a server creates uneven data distribution. If you have 3 servers and add a 4th, one server loses exactly 25% of its data—but which server? It's unpredictable.
With virtual nodes, data redistribution becomes smooth and balanced. When you add a new server with 100 virtual nodes, each of those 100 positions takes a small slice of data from its neighbors. The load spreads evenly across the entire cluster.
Similarly, when a node fails, its virtual nodes' responsibilities distribute across many remaining nodes—no single server gets overwhelmed.
Practical Benefits
- Smooth scaling: Adding capacity doesn't create hot spots
- Heterogeneous hardware: Powerful servers get more virtual nodes, weaker ones get fewer
- Fast recovery: Failed nodes' data scatters, reducing rebuild time
- Minimal data movement: Only affected key ranges move, not entire partitions
Key Takeaway: Dynamo's consistent hashing with virtual nodes enables seamless cluster membership changes while maintaining balanced load distribution—essential for the "always-on" availability Dynamo promises.