arthrop0d

Brief articles on varied topics.

Consistent Hashing Rings and Virtual Nodes

distributed systemsalgorithms

A consistent-hashing ring assigns keys to hosts by placing both keys and hosts in the same circular hash space. Virtual nodes give each physical host many positions on that circle, improving balance and making host changes less disruptive.

The problem with ordinary partitioning

A distributed cache must answer a basic routing question: given a key such as user:42, which cache host should receive the request?

A simple approach is to hash the key and use a remainder:

host = hosts[hash(key) % len(hosts)]

With three hosts, this sends each key to one of three indexes. The problem appears when the cluster changes. Adding a fourth host changes the divisor from 3 to 4, so the remainder changes for most keys. Almost every key is now assigned to a different host, even though only one host was added.

Those keys have not necessarily been lost—the backing database can refill them—but the cache behaves as if it were empty. A deployment or scaling event can therefore cause a large wave of cache misses and extra database load. Removing a host has the same broad effect, while also making the removed host's entries unavailable.

Consistent hashing is designed to change assignments locally instead of recalculating the entire partition.

Turning the hash space into a ring

First, choose a hash function that converts a key into an integer in a fixed range. Imagine that range wrapped into a circle: after the largest value comes the smallest value again. This is the hash ring.

Hosts are placed at positions on the ring by hashing an identifier for each host. A key is also hashed to a position. To find the owner, start at the key's position and move clockwise until reaching the first host position. That host stores the key.

For example, suppose the ring runs from 0 through 99:

Moving clockwise from 52 reaches C first, so C owns the key. A key at position 90 wraps around the end of the ring and reaches A at position 10.

Each host therefore owns the interval after the previous host and up to its own position. In the example, C owns positions 41 through 75, while A owns 76 through 99 and 0 through 10.

A router can represent the ring as sorted host positions. For a key lookup, it hashes the key, performs a binary search for the first position greater than or equal to that hash, and wraps to the first position if the search reaches the end.

The important property is not that a key never moves. It is that a membership change affects only the ring interval next to the changed position.

What happens when a host is added

Suppose a new host, D, is placed at position 60. Before D exists, C owns positions 41 through 75. Afterward, D owns positions 41 through 60, and C keeps positions 61 through 75.

Only keys whose hashes fall in D's newly claimed interval move from C to D. Keys assigned to A, B, and the rest of C's interval keep their owners.

With a well-distributed hash function and one position per host, adding one host moves approximately one fraction of the keyspace proportional to the new host's share—roughly 1 / (number of hosts + 1) in a balanced cluster. It does not move every key.

Removing D reverses the operation. D's interval is absorbed by the next host clockwise, so only D's keys need new owners. This is useful both for intentional scaling and for a failed cache host, although the surviving host must now handle the extra traffic and misses.

Why virtual nodes exist

One position per physical host is often too coarse. Random positions can leave large gaps on the ring, causing one host to own far more keys than another. A host added at an unfortunate position might also take an unusually large interval.

A virtual node, or vnode, is a logical ring position that represents a physical host. Instead of placing Host A once, the system places it at many positions derived from distinct identifiers, such as A-0, A-1, and A-2. Host B and every other host receive their own sets of positions.

The routing rule stays the same: find the first vnode clockwise from the key. The vnode's associated physical host is the destination.

For example, a ring might contain these entries:

position 12  -> A
position 27  -> B
position 43  -> A
position 58  -> C
position 71  -> B
position 89  -> C

A key routed to position 43 is physically sent to A. A owns several separate intervals rather than one large interval.

More vnodes make the intervals smaller and spread them around the ring. That usually gives hosts more even ownership, especially when the number of physical hosts is small. It also makes changes smoother: a new host receives many small intervals distributed across existing hosts instead of one potentially large interval from a single insertion point.

When a physical host is removed, the system removes all of its vnodes. Each of those small intervals transfers to the next vnode clockwise, so the departing host's keyspace is redistributed in pieces. The total amount of moved keyspace is still approximately the removed host's share; vnodes improve the distribution of that movement rather than eliminating it.

What the cache must do during a change

Every cache client, proxy, or routing service must use the same membership view and ring-construction rules. Once a new ring is installed, requests for moved keys go to their new owners. Those entries are normally cache misses, and the application repopulates them from its source of truth.

A production implementation must also coordinate membership updates, detect failed hosts, and avoid sending traffic to a host that has been removed but is still serving requests according to an older ring. During convergence, different clients may briefly use different rings, so implementations often provide a transition strategy or replication.

Replication—keeping a key on more than one host—is separate from consistent hashing. The ring chooses a primary owner; a system may then choose additional clockwise vnodes as replicas for availability.

When a log says that a cache is “rebalancing,” or a configuration contains a vnode count, it is often describing this mechanism. The ring determines ownership, virtual nodes make that ownership reasonably even, and membership changes remap only the affected intervals instead of throwing away the cache's entire placement.

← All articles