Consistent Hashing on a Ring
Consistent hashing is a way to assign keys to nodes by placing both on a circular, ordered range of hash values. A key belongs to the first node found when moving clockwise from the key’s position. Because nodes occupy positions on the same ring, adding or removing a node changes ownership for only part of the keyspace rather than for nearly every key.
The problem with ordinary hashing
Suppose a service stores objects on three cache servers. A simple distribution rule might be:
server = hash(key) % number_of_servers
This is easy to implement, but the server count is part of the assignment formula. If there are three servers, a key whose hash is 8 goes to server 8 % 3, or server 2. Add a fourth server and it goes to 8 % 4, or server 0. The same calculation changes for most keys, so most cached objects must be fetched again or most stored records must be moved.
That creates a reshuffling storm: a membership change causes widespread cache misses, network traffic, disk work, or database repair. In a distributed system, nodes can join and leave because of scaling, maintenance, failures, or deployment. Reassigning almost everything for each change is usually too expensive.
Consistent hashing changes the assignment model so that node membership changes have local effects.
Putting keys and nodes on a ring
A hash function deterministically turns input data into a number from a large fixed range. Consistent hashing treats that range as circular: after the largest value comes the smallest value again. This circular number line is the logical hash ring.
Both keys and nodes are hashed into this range. A node’s hash result is its position on the ring. To find the owner of a key:
- Hash the key to get its ring position.
- Move clockwise from that position.
- Choose the first node position encountered.
- Wrap from the maximum value to the minimum if necessary.
The interval after one node and up to the next node belongs to the next node. The ring’s wraparound means there is no special “last” partition; the node after the largest position is the one at the smallest position.
For example, imagine three node positions:
Node A: 10
Node B: 40
Node C: 80
A key at position 25 belongs to B. A key at 75 belongs to C. A key at 95 wraps around and belongs to A. The exact hash values do not matter; their order does.
In practice, implementations keep the node positions in a sorted structure and perform a search for the first position greater than or equal to the key’s position. If no such position exists, they select the first position in the structure.
Why one position per node is uneven
A random-looking hash function spreads positions over the ring, but it cannot guarantee equal spacing. With only a few nodes, one node might have a short interval and another might have a very large interval. Since a node owns the interval before it, the larger interval receives more keys.
This is the first job of virtual nodes, often called vnodes. Instead of placing each physical server at one position, the system places that server at many positions. Each position is a separate token on the ring, and all of that server’s tokens collectively represent its ownership.
For example, rather than placing server A once, the system might place A-1, A-2, and hundreds of other tokens at independently hashed positions. A key still selects the first token clockwise, but the token’s label identifies the physical server that handles it.
Many small intervals average out random gaps. A server that happens to receive one unusually large interval may receive several small ones elsewhere, producing a much more even total share. Vnodes also make weights possible: a machine with twice the capacity can be assigned roughly twice as many tokens.
Virtual nodes do not make individual intervals equal. They make the sum of many intervals per physical node more predictable.
What changes when a node joins
Suppose a new node adds a token at position 55. Before the join, keys between B at 40 and C at 80 belonged to C. After the join, keys from 40 through 55 still belong to C, while keys from 55 through 80 now belong to the new node.
Only the interval immediately preceding the new token changes owner. Every other interval keeps its existing owner. With virtual nodes, the new physical node adds many tokens, so it takes a collection of small intervals distributed around the ring. Existing nodes each give up some local ranges, rather than one existing node losing a single potentially huge range.
If the ring is well balanced and a new node joins a group of N nodes, the new node will typically receive about 1 / (N + 1) of the keyspace. That is also roughly the fraction of keys that must move. The exact amount depends on token placement and the distribution of keys.
What changes when a node leaves
When a node fails or is removed, its tokens disappear. Each interval that those tokens owned is assigned to the next token clockwise. Only keys owned by the removed node need to move; keys on other intervals remain where they are.
With vnodes, those intervals are scattered across the ring. The remaining nodes absorb many small ranges, which generally spreads the recovery work instead of concentrating it on one successor.
The hash ring determines which keys should move, but the system still needs to perform the movement: update ownership metadata, copy durable data or repopulate caches, and coordinate requests while the transfer is in progress. Consistent hashing limits the scope of that work; it does not perform replication or data transfer by itself.
When a log says a partition is “rebalancing,” a node is “joining the ring,” or a cache is using “vnodes” or “tokens,” this is the model behind those terms: ordered positions on a circular hash space, with each key owned by the next position clockwise.