How Does Consistent Hashing Work?

Consistent hashing is a technique for assigning keys to nodes in a distributed system while limiting how many assignments change when nodes are added or removed. It is useful when data, requests, or cache entries must be spread across several machines and the set of available machines can change over time.

The central idea is simple: place both keys and nodes on a circular hash space called a hash ring. A key is assigned to the first node encountered while moving clockwise around the ring. When a node joins or leaves, only the keys in the affected part of the ring need to move. The rest of the assignments remain unchanged.

This behavior is the main reason consistent hashing is useful. A straightforward rule such as hash(key) % numberOfNodes can distribute keys across machines, but changing the number of machines usually changes the destination for most keys. Consistent hashing is designed to avoid that broad reshuffling.

The problem: distributing keys across changing nodes​

Imagine a service with several cache servers. A request contains a key such as a user identifier, product identifier, or URL. The service needs to decide which cache server should store or retrieve the value for that key.

A common first approach is:

nodeIndex = hash(key) % numberOfNodes

If there are four nodes, the result of the modulo operation selects one of four positions. This is easy to understand and can distribute keys reasonably well when the hash function is suitable.

However, the node count is part of the calculation. Suppose a key produces the hash value 17. With four nodes, its destination is:

17 % 4 = 1

If a fifth node is added, the same key is assigned using:

17 % 5 = 2

The key moves even though the original four nodes are still available. Many other keys move for the same reason. Changing the node count can therefore cause a large portion of the key space to select different destinations.

For a cache, this may produce a large cache-miss event because entries are now looked up on different machines from the ones that stored them. For a storage or routing system, it may require substantial data movement or cause requests to reach the wrong owner until data is migrated.

Consistent hashing addresses this specific problem: how to change the membership of a distributed group without remapping nearly everything.

The hash ring​

A hash function maps an input to a value in a fixed range. For example, a simplified hash function might return values from 0 through 99. Instead of treating those values as a straight numerical interval, consistent hashing connects the end of the range back to the beginning:

0, 1, 2, ..., 98, 99, then back to 0

This creates a circle, commonly called a hash ring.

Both nodes and keys are placed on the ring by hashing them. A node is placed at the position produced by hashing its identifier, such as Node-A. A key is placed at the position produced by hashing the key itself, such as user-42.

The ring does not necessarily contain one visible point for every possible hash value. It is a conceptual circular ordering of hash positions. The important properties are that positions have an order and that the final position wraps around to the first position.

A simplified arrangement might look like this:

                         25
                    Node-B
                         |
              10 --------+-------- 40
           Node-A                 key-X
                         |
                         70
                    Node-C

The exact geometry of the drawing is not important. What matters is that nodes and keys use the same coordinate system. A key can therefore be assigned by comparing its position with the positions of nodes.

Clockwise key assignment​

The usual assignment rule is:

1. Hash the key to obtain a position on the ring.
2. Start at that position.
3. Move clockwise.
4. Select the first node encountered.
5. If no node appears before the end of the numerical range, wrap around to the beginning of the ring.

Suppose the ring has three nodes:

Node-A at position 10
Node-B at position 40
Node-C at position 70

Now consider several keys:

key-1 at position 5
key-2 at position 25
key-3 at position 60
key-4 at position 90

Their assignments are:

• key-1 moves clockwise from 5 and reaches Node-A at 10.
• key-2 moves clockwise from 25 and reaches Node-B at 40.
• key-3 moves clockwise from 60 and reaches Node-C at 70.
• key-4 passes the end of the range, wraps to the beginning, and reaches Node-A at 10.

The ring divides the circular key space into ownership intervals. Each node owns the keys after the previous node and up to its own position, using clockwise order.

For example, Node-B owns positions greater than 10 and up to 40. Node-C owns positions greater than 40 and up to 70. Node-A owns positions greater than 70 through the end of the range, plus the interval from the beginning through 10.

The wraparound interval is a normal part of the algorithm rather than an exceptional case to ignore. Every implementation must handle it correctly.

A small numerical example​

Consider a hash space from 0 through 99. Place three nodes on the ring:

Node-A at 12
Node-B at 45
Node-C at 78

The ownership intervals are:

Node-A: 79 through 99, and 0 through 12
Node-B: 13 through 45
Node-C: 46 through 78

Now hash six keys:

alpha   -> 3
beta    -> 19
charlie -> 44
delta   -> 51
echo    -> 75
foxtrot -> 91

The assignments are:

alpha   -> Node-A
beta    -> Node-B
charlie -> Node-B
delta   -> Node-C
echo    -> Node-C
foxtrot -> Node-A

The key alpha hashes to 3. Moving clockwise reaches Node-A at position 12, so Node-A owns it. The key foxtrot hashes to 91. No node appears between 91 and the end of the numerical range, so the search wraps around and reaches Node-A at position 12.

This example shows that ownership is determined by successor search: the owner is the first node whose position is at least the key position, with the first node selected when the search wraps around.

Why adding one node causes limited remapping​

Suppose the ring initially contains three nodes:

Node-A at 10
Node-B at 40
Node-C at 70

Now add Node-D at position 55. Before the addition, Node-C owns the interval from just after 40 through 70. After the addition, Node-D becomes the first node clockwise for positions after 40 through 55. Those keys move from Node-C to Node-D.

The other intervals remain associated with the same nodes:

• Keys owned by Node-A stay with Node-A.
• Keys owned by Node-B stay with Node-B.
• Keys in the part of Node-C's interval after 55 stay with Node-C.
• Only the portion between the previous node and the new node changes ownership.

This is the key remapping property. A new node takes ownership of one region of the ring rather than forcing every key to recalculate its destination under a completely different modulo base.

In the numerical example above, add Node-D at position 60. The interval from 46 through 60, previously owned by Node-C, now belongs to Node-D:

delta at 51 -> Node-D

The other listed keys do not move:

alpha   -> Node-A
beta    -> Node-B
charlie -> Node-B
echo    -> Node-C
foxtrot -> Node-A

The exact fraction of keys moved depends on where the new node lands and how evenly the existing node positions divide the ring. With ideal uniform positions, a newly added node receives approximately its share of the ring. Real positions can be uneven, which is why virtual nodes are important.

Why removing one node also causes limited remapping​

The same structure handles node removal. Suppose Node-B is removed from this ring:

Node-A at 10
Node-B at 40
Node-C at 70

Before removal, Node-B owns positions after 10 through 40. After Node-B leaves, that interval is absorbed by the next node encountered clockwise, which is Node-C.

Keys that belonged to Node-A and the rest of Node-C's interval remain assigned as before. Only the keys formerly owned by the departing node change destination.

If a node fails unexpectedly, the same principle can route affected keys to another node. If a node is removed deliberately, the system can move or replicate the affected data before or during the membership change. Consistent hashing does not by itself copy data, coordinate migration, or guarantee availability. It provides the ownership layout that those surrounding mechanisms can use.

Looking up a key efficiently​

A ring can be implemented using an ordered collection of node positions. The implementation typically stores pairs such as:

(position, node)

To look up a key:

1. Compute the key's hash position.
2. Find the first node position greater than or equal to that key position.
3. If there is no such position, select the first node in the ordered collection because the ring wraps around.

If the ring contains M positions and those positions are stored in a balanced ordered structure, lookup can generally be performed in logarithmic time, written as O(log M). If the positions are stored in a sorted array, binary search also provides O(log M) lookup after the array has been built.

A conceptual implementation looks like this:

function owner(key):
    position = hash(key)
    nodePosition = firstRingPositionAtLeast(position)

    if nodePosition does not exist:
        nodePosition = smallestRingPosition()

    return nodeAt(nodePosition)

Adding a node requires inserting its position into the ordered structure. Removing a node requires deleting its position. With an ordered structure, these operations are commonly O(log M) per position, although the exact cost depends on the chosen data structure and implementation.

The number M is the number of positions on the ring, not necessarily the number of physical machines. Virtual nodes increase M, which improves distribution but also increases the amount of ring metadata and the work involved in membership changes.

If there are P physical nodes and each has V virtual positions, the ring contains approximately P × V positions. A binary-search lookup therefore has complexity O(log(P × V)).

The load-balance problem with one position per node​

A basic ring with one position per physical node can still distribute load poorly. Hashing is intended to spread identifiers across the hash space, but a small number of random positions can leave uneven gaps.

Consider four nodes whose clockwise ownership intervals happen to have these sizes:

Node-A owns 10% of the ring
Node-B owns 15% of the ring
Node-C owns 20% of the ring
Node-D owns 55% of the ring

If keys are spread broadly across the hash space, Node-D may receive much more work and data than the other nodes. The ring still has the desired remapping behavior, but the ownership portions are not uniform.

A node's load is influenced by the size of the interval it owns and by the distribution of keys. If many keys are concentrated in a particular region of the hash space, even equal geometric intervals may not produce equal actual load. Nevertheless, uneven node positions are an obvious source of imbalance in a simple design.

The usual solution is to give each physical node multiple positions on the ring. These positions are called virtual nodes, or vnodes.

Virtual nodes​

A virtual node is a logical ring position that maps back to a physical node. Instead of hashing a physical node identifier once, the system hashes several distinct identifiers derived from that node:

hash(Node-A:replica-1)
hash(Node-A:replica-2)
hash(Node-A:replica-3)

Each result places one virtual position on the ring. When a key maps to one of those positions, the system routes the key to the physical node associated with that virtual position.

For example, one physical node might own these virtual positions:

Node-A: 8, 34, 67, 92

Another physical node might own these positions:

Node-B: 15, 48, 75, 86

The ring is now divided into many smaller intervals. Because each physical node appears at several locations, its total ownership is the sum of several separated intervals instead of one large interval.

This tends to make total ownership more uniform. A node that receives a larger-than-average interval at one position may receive smaller intervals elsewhere. The irregularities partially balance one another across the node's virtual positions.

Virtual nodes also make membership changes more granular. When a physical node is removed, its many smaller intervals are distributed among the corresponding clockwise successors. When a physical node is added, its virtual positions take smaller portions from several existing successors instead of taking one potentially large region.

How virtual nodes improve uniform load​

Suppose four physical nodes each have one position. A single unlucky position can give one node a very large interval. Now suppose each physical node has many independently hashed virtual positions. The total share for each physical node is determined by many intervals.

The result is similar to averaging many samples: an individual interval can still be unusually large or small, but the sum of many intervals tends to be less extreme. More virtual positions generally provide a smoother distribution of ownership across physical nodes.

The word “generally” matters. Virtual nodes improve the statistical distribution of ring positions; they do not guarantee identical load. Actual load can also depend on:

• The number of keys assigned to each region.
• Whether some keys receive more requests than others.
• Whether physical nodes have equal capacity.
• Whether the hash function distributes identifiers adequately.
• Whether different virtual nodes are accidentally placed in similar locations.

A practical system can assign different numbers of virtual nodes to different physical machines when their capacities differ. A higher-capacity machine can receive more virtual positions, while a lower-capacity machine receives fewer. The exact weighting policy is a design choice.

Virtual nodes are therefore a load-distribution tool, not a guarantee that every machine will receive exactly the same number of requests or bytes.

The relationship between physical and virtual nodes​

It is important to distinguish a physical node from a virtual node:

• A physical node is the actual server or service instance that handles data or requests.
• A virtual node is a logical ring position associated with one physical node.

The lookup procedure selects a virtual position first. The system then follows the position's ownership metadata to obtain the physical destination. Conceptually:

Ring position 21 -> Node-B:virtual-4 -> physical Node-B

The client does not need to treat every virtual node as a separate server. Virtual nodes are an organization technique inside the partitioning layer.

When Node-B is added, all of its virtual positions are inserted into the ring. When it is removed, all of those positions are deleted. The keys affected by each position move to its clockwise successor. The total changed region is the combined ownership of those positions.

Consistent hashing versus ordinary modulo hashing​

The key difference is not that consistent hashing eliminates movement. A new node must receive some keys if the system is to use its capacity. A removed node's keys must also go somewhere. The difference is how much movement occurs.

With modulo hashing:

owner = hash(key) % N

Changing N changes the arithmetic destination for many hash values. The old and new partitions are not organized so that most keys retain their previous owner.

With a hash ring:

owner = first node clockwise from hash(key)

Adding a node inserts new ownership boundaries into the existing circular structure. Removing a node deletes boundaries. Most existing intervals keep the same owner.

Both approaches can be fast for an individual lookup. The important distinction is their behavior during membership changes, not merely the cost of computing a hash.

This makes the ring particularly useful when node membership changes are expected. The system can add capacity or respond to failures while limiting the set of keys that need to be reconsidered.

Minimal remapping does not mean zero migration​

Consistent hashing limits which keys change owners, but it does not automatically move the associated data. If a key was stored on an old owner and is now assigned to a new owner, the surrounding system must decide how to make the data available there.

Possible operational steps include:

1. Detect that the membership set has changed.
2. Construct the new ring.
3. Identify the intervals whose owner changed.
4. Transfer or rebuild data for those intervals.
5. Route new requests according to the new ring.
6. Handle requests during the transition.

The precise transition protocol is outside the hash-ring rule itself. The important takeaway is that the ring narrows the migration scope. Instead of treating the whole key set as potentially changed, the system can focus on the intervals associated with the joining or leaving node.

For a cache, the system might allow affected entries to be recreated after misses. For a data store, it may need an explicit transfer process. For request routing, it may update clients or a routing layer so that they use the new ownership mapping. Consistent hashing supplies the mapping framework, while data movement and availability require additional design.

A membership update also needs a defined point of view. If different clients use different versions of the ring, they may temporarily disagree about the owner of a key. Consistent hashing does not specify how membership metadata is published or synchronized. That is an operational responsibility of the larger system.

Choosing a hash space and hash function​

A consistent-hashing implementation needs a hash function that maps node identifiers and keys into the same hash space. The ring can be described using a bounded integer range, but the conceptual behavior is the same regardless of the selected range size.

The hash function should provide a useful spread of positions for the identifiers used by the system. Node identifiers should be distinct, and virtual-node identifiers should also be distinct so that their positions are not all identical.

The ring does not require key values and node values to have the same type. They only need to be converted into inputs that the chosen hash function can process. For example:

hash(user:42)
hash(cache-node-A)
hash(cache-node-A:virtual:17)

All results are interpreted as positions in the shared ring space.

Collisions are possible in a finite hash space. An implementation must define how to handle two positions that are equal. It may store multiple entries at one position using a deterministic ordering, or use identifiers and a data structure that supports duplicate positions. The exact policy is an implementation detail, but ignoring collisions can make ownership ambiguous.

The identifiers used for virtual nodes should be generated deterministically. Given the same physical node and virtual-node index, all participants should produce the same logical identifier and therefore the same ring position. Otherwise, different clients can construct different rings from what they believe is the same membership set.

Handling wraparound correctly​

Wraparound is one of the most important edge cases. Suppose the ring's largest occupied position is 90 and a key hashes to 97. There may be no node at a position greater than or equal to 97. The correct owner is the first node in the ordered ring, because moving clockwise past the end returns to the beginning.

A lookup can be expressed as a successor search:

successor(keyPosition) =
    first ring position >= keyPosition,
    or the first ring position if no such position exists

The same rule applies when assigning ownership intervals. The node at the smallest position owns the region that crosses the numerical boundary between the maximum and minimum hash values.

Tests should explicitly include keys before the first node, keys after the last node, keys exactly on a node position, and rings containing only one node. These cases expose incorrect wraparound handling quickly.

An empty ring is another necessary case. There is no valid owner when no nodes have been registered, so an implementation must define whether lookup returns an error, a missing result, or some other explicit outcome. The ring algorithm cannot select a node that does not exist.

A practical ring data structure​

A minimal implementation can maintain an ordered list of virtual-node positions. Each list entry contains a position and its physical owner:

[
  (8,  Node-A),
  (15, Node-B),
  (34, Node-A),
  (48, Node-B),
  (67, Node-A),
  (75, Node-B),
  (86, Node-B),
  (92, Node-A)
]

For a key position of 50, binary search finds the first position at least 50, which is 67. The owner is Node-A. For a key position of 95, there is no position at least 95, so lookup wraps to position 8 and returns Node-A.

A membership update modifies this metadata:

• To add a physical node, generate its virtual identifiers, hash them, and insert the resulting entries.
• To remove a physical node, delete every ring entry associated with it.
• To inspect the affected region, compare ownership before and after the update.

For a small or infrequently changing ring, a sorted array can be simple and efficient. Binary search provides logarithmic lookup, while inserting or deleting entries may require shifting elements. A balanced ordered tree can make updates more convenient, with lookup and individual updates commonly taking O(log M) time.

A system with many clients may distribute a serialized ring or a membership description to each client. Those clients must use the same hash function, virtual-node naming scheme, collision policy, and ordering rules. Otherwise, identical input keys may produce different owners on different clients.

Operational trade-offs of virtual nodes​

Virtual nodes improve distribution, but they introduce costs. If each physical node receives many virtual positions, the ring contains many more entries. This increases:

• Memory used for ring metadata.
• The amount of work needed to add or remove a physical node.
• The size of membership information that may need to be shared.
• The amount of bookkeeping required to identify all positions belonging to one node.

Lookup remains an ordered search over the total number of ring positions. If there are P physical nodes and each has V virtual positions, the ring has approximately P × V positions, so a binary-search lookup is O(log(P × V)).

Adding or removing one physical node requires processing its virtual positions. If each node has V positions and each insertion or deletion costs O(log(P × V)), the update work is commonly on the order of O(V log(P × V)), ignoring the cost of publishing the new membership information and migrating data.

Using more virtual nodes is therefore a balance. Too few can leave ownership uneven. More positions can improve uniformity but increase metadata and update work. The appropriate choice depends on the desired distribution quality, the number of physical nodes, and the operational cost the system can accept.

The important practical principle is to use virtual nodes deliberately rather than assuming that one position per machine will always produce balanced ownership.

Testing a consistent-hashing implementation​

A useful test suite should verify the ring rule, membership updates, wraparound behavior, and virtual-node distribution.

Basic assignment tests​

Create a ring with known node positions and verify that keys map to the expected clockwise successor. Include positions inside every interval and positions exactly on node boundaries.

A key exactly at a node's position should follow the documented boundary rule. The common rule is to select the first position greater than or equal to the key position. Whatever rule is chosen, it must be deterministic and used consistently during lookup and ownership calculations.

Wraparound tests​

Test keys that hash after the largest node position. They should map to the node at the smallest position. Also test keys before the smallest node position and keys positioned near the numerical boundary of the hash space.

Addition tests​

Build a ring, record assignments for a collection of keys, add one node, and compare the old and new assignments. Keys outside the new node's acquired intervals should retain their owners. Keys inside those intervals should move to the new node.

With virtual nodes, repeat this test for every new position. The changed keys should belong to the combined regions taken by the new node's virtual positions, not to unrelated regions of the ring.

Removal tests​

Remove one node and verify that keys previously assigned to it move to the correct clockwise successor. Keys assigned to other intervals should remain unchanged.

When a physical node owns multiple virtual positions, verify each removed position independently. The affected intervals may have different successors, so all removed regions should not automatically be assigned to one surviving machine.

Distribution tests​

Place many virtual positions for each physical node and measure the total portion of the ring owned by each node. The results should be reasonably balanced for the selected identifiers and hash function. This test is about statistical behavior, so it should use enough positions to make the comparison meaningful.

It is also useful to test weighted configurations if machines have different capacities. The expected ownership share should reflect the configured number of virtual positions rather than assuming that every physical node has equal capacity.

Determinism tests​

Given the same membership set, virtual-node identifiers, and hash function, different clients should build the same ring and return the same owner for each key. Deterministic ordering is essential when multiple participants perform lookups independently.

Empty and single-node tests​

An empty ring should produce a clearly defined result rather than an accidental indexing failure. A single-node ring should assign every key to that node, including keys that require wraparound. These simple cases help validate the basic lookup contract.

Common implementation mistakes​

Several errors appear frequently in first implementations.

Treating the ring as a line​

If the lookup fails whenever the key hash is larger than the largest node position, the implementation has forgotten wraparound. The correct result is the smallest node position.

Hashing only keys​

The ring requires both keys and nodes to be mapped into the same coordinate system. If nodes are not represented by positions, the clockwise successor rule cannot be applied.

Using one position and assuming perfect balance​

A single position per physical node can create large ownership gaps. Virtual nodes are used to reduce the effect of unlucky placements.

Confusing virtual nodes with physical machines​

A virtual node is not an additional server. It is a logical position whose metadata points to a physical owner. Treating every virtual position as an independent machine can lead to incorrect capacity calculations and membership handling.

Changing virtual-node identifiers unexpectedly​

If a node receives different virtual identifiers after a restart or membership refresh, its ring positions change. That can cause unnecessary remapping even though the physical membership has not changed. Virtual-node naming should be deterministic.

Ignoring collision behavior​

Two identifiers may hash to the same position. The implementation needs a deterministic way to order or represent colliding entries. Otherwise, different participants might choose different owners.

Assuming the algorithm moves data automatically​

The ring changes the ownership calculation. It does not transfer bytes, rebuild cache entries, replicate records, or coordinate a handoff. Those actions require separate mechanisms.

Practical takeaways​

Consistent hashing can be remembered as four connected ideas:

1. Hash both keys and nodes into one circular space. The shared ring gives keys and nodes a common ordering.
2. Assign each key to the first node clockwise from its position. This defines ownership using successor search.
3. Insert or remove node positions instead of changing a global modulo base. Only nearby ownership intervals change, so remapping is limited.
4. Give each physical node many virtual positions. Multiple positions usually produce more uniform total ownership and make changes more granular.

The technique is valuable when a distributed system must spread work across nodes and tolerate membership changes. It is especially useful for understanding why adding a node need not invalidate the placement of every key.

At the same time, consistent hashing is not a complete distributed-storage solution. It does not by itself provide replication, data transfer, failure detection, membership dissemination, conflict resolution, or request coordination. Those concerns must be built around the ownership map. The algorithm's contribution is focused and important: it provides a stable circular partitioning scheme whose changes affect a limited portion of the key space.

Summary​

A hash ring turns the hash space into a circle and places both nodes and keys on it. To find a key's owner, start at the key's hashed position and move clockwise until reaching a node, wrapping around when necessary. This creates ownership intervals between node positions.

When a node is added, it takes the interval immediately before its position from the node that previously owned that region. When a node is removed, its interval is taken over by the next surviving node clockwise. Consequently, only a limited set of keys changes ownership rather than the majority of the key space.

One position per physical node can produce uneven intervals. Virtual nodes address this by assigning each physical machine multiple logical positions distributed around the ring. The combined ownership of those positions is usually more uniform, while membership changes affect smaller, separated portions of the ring.

For implementation, store ring positions in an ordered structure, use successor search for lookups, handle wraparound explicitly, define collision behavior, and keep the mapping from virtual positions to physical nodes. For operation, remember that limited remapping reduces migration scope but does not eliminate the need for data movement or membership coordination.

That combination of clockwise assignment, minimal remapping, and virtual-node load balancing is the foundation of consistent hashing.