Consistent Hashing and Virtual Nodes
Consistent hashing assigns keys to members by placing both on a circular hash space, or ring. A key belongs to the first member encountered when moving clockwise from the key’s position. When a member joins or leaves, only the key ranges next to that member need to move.
The problem with ordinary hashing
A simple distributed cache or database router might choose a member with:
member = hash(key) modulo number_of_members
This works while the member count is fixed. If there are four members, a key whose hash ends in 2 goes to member 2. But adding a fifth member changes the divisor. Most keys now produce different results, so most cached entries become misses or most records need to be found on a different machine.
That is the problem consistent hashing addresses: change membership without remapping nearly every key. This matters when scaling a service, replacing a failed machine, or rebalancing a cluster.
Putting keys and members on a ring
A hash function turns data into a repeatable, apparently well-spread integer. Consistent hashing treats that integer as a position on a circular range. For example, a system might use positions from 0 through 2^64 - 1, with the end connected back to zero.
The system hashes each member’s identifier—such as cache-1—and places the member at that position. It also hashes each data key and places the key on the same ring. To find a key’s owner, walk clockwise from the key until reaching a member. That member owns the key.
For example, suppose the ring has members at these positions:
| Member | Ring position |
|---|---|
| A | 100 |
| B | 400 |
| C | 750 |
A key at position 120 belongs to B: B is the next member clockwise. A key at 800 wraps around the end of the ring and belongs to A. The member immediately counterclockwise from a key is sometimes called its predecessor; the key belongs to the next member after that position.
In a real implementation, the member positions are kept in a sorted structure. Routing a key means hashing it, finding the first position at or after that hash, and wrapping to the first position when necessary.
The ring is logical. It does not mean the machines are physically arranged in a circle; it is an ordering used for ownership.
Why one position per member is not enough
With one position per physical member, the ring can be badly uneven. Hashing usually spreads positions reasonably well, but randomness does not guarantee equal spacing. One member might own a large arc and another a tiny one. A member’s load also changes sharply when another member is inserted into its single arc.
A virtual node, or ** vnode**, is an additional ring position assigned to a physical member. Instead of placing member A once, the system places identifiers such as A-0, A-1, and A-2 at independently hashed positions. All those positions still route to the same machine, but they divide that machine’s ownership into many smaller ranges.
With enough virtual nodes per member:
- ownership is spread across the ring rather than concentrated in one arc;
- random gaps tend to average out, producing a more even distribution;
- adding or removing a physical member affects many small ranges instead of one large range;
- capacity can be represented by assigning more virtual nodes to larger machines.
The exact number of virtual nodes is an operational choice. More nodes generally improve balance, but they also increase the membership metadata and the work needed to maintain and search the ring.
Why membership changes move only some keys
Consider a new member joining between two existing positions. Before the join, the clockwise successor owned the entire interval between the previous position and itself. After the join, the new member owns only the portion from the new position up to that successor. Keys in that interval change owners; keys everywhere else still find the same successor.
The same rule applies to virtual nodes, repeated many times. A new physical member receives a set of virtual positions. Each position takes a small interval from the member that previously followed it. Across the whole ring, the new member receives roughly its share of the ranges—about 1/N with equal capacity when there are N members—rather than forcing every key to be reconsidered as ordinary modulo hashing does.
Removing a member is the inverse. Its intervals are handed to the next clockwise member after each interval. Only keys that belonged to the removed member move. If the member had virtual nodes, those many small intervals are redistributed among their respective successors.
This property is often summarized as minimal disruption: membership changes affect only neighboring ranges on the ring. It does not mean zero movement, nor does it mean data migrates automatically. A cache may simply begin sending misses to the new owner. A storage system must usually copy the affected records and coordinate when the new owner is ready.
Practical details
All participants must use the same hash function, member identifiers, ring rules, and membership view. If two clients disagree about the active members, they can send the same key to different machines even though each is correctly applying the algorithm.
Systems commonly add replication by storing a key on the owner and one or more following members on the ring. That extends the lookup rule but does not change the basic ownership idea. Consistent hashing also cannot solve a single extremely popular key: every request for that key still targets its owner unless the system adds caching, replication, or another hotspot strategy.
When a log says a node was added, removed, or assigned new tokens, it is often describing this mechanism. The tokens are virtual ring positions, and the associated data movement is the limited set of key ranges whose clockwise owner changed.