Storage fundamentals
Consistent hashing
Consistent hashing is a method for deciding which node in a distributed system stores each piece of data. It maps both data keys and nodes onto the same circular range of hash values, so that any participant can compute where an item belongs, and so that adding or removing a node relocates only a small fraction of the data.
How does a hash ring work?
A hash function turns any input into a number in a fixed range. Picture that range bent into a circle. Each storage node is assigned one or more positions on the circle. To place an object, the system hashes its key to get a position and walks clockwise to the first node it meets, which becomes the owner. Further copies or fragments go to the next nodes along. Because the calculation depends only on the key and the list of nodes, no central lookup table is needed.
Why not simply hash and take the remainder?
The simplest scheme divides the hash by the number of nodes and uses the remainder. It works until the number of nodes changes, at which point almost every key maps somewhere new.
| Property | Hash modulo node count | Consistent hashing |
|---|---|---|
| Lookup | Computed, no table | Computed, no table |
| Adding one node to ten | About 90 percent of data moves | About 10 percent of data moves |
| Removing a failed node | Most data remaps | Only that node's share remaps |
| Balance across nodes | Even | Even, with virtual nodes |
What are virtual nodes?
With one position per node, the arcs between nodes vary in length and some nodes own much more data than others. Virtual nodes fix this by giving each physical node many positions scattered around the ring. The load evens out statistically, a new node takes small slices from many existing nodes instead of a large slice from one, and a larger server can be given more positions than a smaller one so that it receives a proportionate share. That last property is what lets hardware of different capacities coexist.
Where is consistent hashing used in storage?
It is the placement mechanism in many distributed storage systems, object stores and key-value databases, sometimes combined with rules that keep copies in separate racks or sites, as under rack awareness. Its practical benefit shows during growth and failure. Expanding a scale-out storage cluster triggers a bounded rebalance, and losing a storage node affects only the keys that node held. Object storage expansion covers what the rebalance looks like in operation.
Frequently asked questions
Does consistent hashing guarantee even distribution?
Not perfectly. Virtual nodes make the distribution close to even, and systems monitor and correct remaining imbalance.
Is a central metadata server still needed?
Not for placement. Any node or client that knows the ring can compute an object's location.
What happens to data when a node is added?
The keys in the slices the new node takes over are copied to it in the background. Everything else stays where it is.
Related terms
- Distributed storage: systems that spread data across many nodes.
- Scale-out storage: growth by adding nodes.
- Storage node: the unit placed on the ring.
- Rack awareness: placement rules layered on top.
- Data placement policy: what decides where copies may go.