All blogs
8 min readEN

Hash Rings — Distributing Hell Evenly with Virtual Nodes

  • System Design
  • Consistent Hashing
  • Distributed Systems
  • Load Balancing
On this page

Consistent hashing, explained with a ring

You have a lot of requests. A second feels like an hour. One server freezes to death while the one next to it burns to death.

How do you survive a flood of traffic hitting your system? How do you spread the load evenly across horizontally scaled servers — and keep it spread when servers come and go?

Hash rings come to the rescue, like a ring that grants three wishes: even distribution, cheap rebalancing, and no single server carrying everyone else's sins.

What Is Wrong With Classic Hashing?

The obvious approach is simple: hash every key and take the modulus by the number of servers.

serverIndex = hash(key) % N

With 4 servers, each key lands on hash(key) % 4. All good, right? The workload is divided based on the modulus of the hash, and every key has exactly one home.

Figure 1: Keys distributed across 4 servers with hash(key) % 4
Figure 1: Keys distributed across 4 servers with hash(key) % 4

Now ask the question that breaks everything: what if the number of servers changes?

Say server 1 goes offline. Now there are 3 servers, so the modulus becomes hash(key) % 3. The hash values did not change — but the divisor did — so almost every key gets a new server index. Not just the keys that lived on the dead server: almost all of them.

Figure 2: After removing server 1, most keys are remapped to a different server
Figure 2: After removing server 1, most keys are remapped to a different server

Every key highlighted in red moved. In a cache, that is a storm of cache misses hitting your database at once. In a sharded datastore, that is a mass migration. Either way, the moment you needed stability the most, classic hashing reshuffles the whole deck.

We need something that gives us consistent hashing. Quoting Wikipedia:

Consistent hashing is a special kind of hashing such that when a
hash table is re-sized and consistent hashing is used, only k/n keys
need to be remapped on average, where k is the number of keys, and
n is the number of slots. In contrast, in most traditional hash tables,
a change in the number of array slots causes nearly all keys to be
remapped.

Building the Ring

Assume SHA-1 is our hash function f. Its output range is x0, x1, x2, ..., xn. In cryptography, SHA-1's hash space goes from 0 to 2^160 - 1. That means x0 corresponds to 0, xn corresponds to 2^160 - 1, and every other hash value falls somewhere in between.

Figure 3: The hash space of SHA-1, from x0 to xn
Figure 3: The hash space of SHA-1, from x0 to xn

By connecting both ends, we get a hash ring:

Figure 4: Connecting x0 and xn turns the hash space into a ring
Figure 4: Connecting x0 and xn turns the hash space into a ring

Placing servers on the ring

Using the same hash function f, we map servers onto the ring based on their IP address or name. Each server gets a position just like a key would.

Figure 5: Servers s0–s3 and keys k0–k3 placed on the ring using the same hash function
Figure 5: Servers s0–s3 and keys k0–k3 placed on the ring using the same hash function

Finding a key's server

To determine which server a key lives on, we go clockwise from the key's position on the ring until we find a server. In Figure 5 above, going clockwise: key0 is stored on server 0, key1 on server 1, key2 on server 2, and key3 on server 3.

Adding and Removing Servers

Here is where the ring earns its keep.

Figure 6: After adding server 4, only key0 needs to move
Figure 6: After adding server 4, only key0 needs to move

After a new server 4 is added, only key0 needs to be redistributed. key1, key2, and key3 stay exactly where they were. Look at the logic: before server 4 was added, key0 was stored on server 0. Now key0 is stored on server 4, because server 4 is the first server it encounters going clockwise. The other keys never hit server 4 on their clockwise walk, so nothing changes for them.

Removing a server works the same way in reverse. If server 1 is removed, only key1 must be remapped — it walks clockwise past the gap and lands on server 2. The rest of the keys are untouched.

Compare that with Figure 2, where removing a single server moved almost every key. That is the difference between a bad night and a routine deploy.

The Two Problems With the Basic Ring

So far the algorithm is:

  • Map servers and keys onto the ring using a uniformly distributed hash function.
  • To find the server for a key, go clockwise from the key's position until the first server is found.

It works, but the basic approach has two real problems:

  • Partition sizes are uneven. A partition is the hash space between two adjacent servers. Servers hash to arbitrary positions, so some partitions end up tiny and some end up huge — and it gets worse every time a server is added or removed. One server may own a sliver of the ring while its neighbour owns half of it.
  • Keys are unevenly distributed. Even if the partitions were equal, keys might cluster in one region of the ring. One server is drowning while the others are idle — exactly the "one freezes, one burns" situation we started with.

How do we solve it? With virtual nodes.

Virtual Nodes: One Server, Many Faces

A virtual node refers to a real node, and each server is represented by multiple virtual nodes on the ring.

Figure 7: Server 0 and server 1 each represented by 3 virtual nodes
Figure 7: Server 0 and server 1 each represented by 3 virtual nodes

In the figure above, both server 0 and server 1 have 3 virtual nodes. The number 3 is arbitrary; in real-world systems the number of virtual nodes is much larger. Instead of a single s0, we have s0_0, s0_1, and s0_2 representing server 0 on the ring. Similarly, s1_0, s1_1, and s1_2 represent server 1.

With virtual nodes, each server is responsible for multiple partitions. Partitions (edges) labelled s0 are managed by server 0; partitions labelled s1 are managed by server 1. Their slices of the ring are now interleaved instead of being two big contiguous chunks.

Lookup does not change: go clockwise from the key's location and find the first virtual node. To find where k0 is stored, we go clockwise from k0 and hit virtual node s1_1, which refers to server 1.

Why this fixes both problems

As the number of virtual nodes increases, the distribution of keys becomes more balanced. Each server now owns many small partitions scattered around the ring, so an unlucky big partition or an unlucky cluster of keys gets averaged out. The standard deviation of the load per server shrinks as virtual nodes grow — more virtual nodes, more balanced data.

There is a trade-off: more virtual nodes means more memory to store the ring. Tuning that number is the real engineering knob.

Finding the Affected Range

When a server is added or removed, a fraction of the data needs to be redistributed. How do we find the affected range?

Figure 8: The affected range when server 4 is added is the arc between s3 and s4
Figure 8: The affected range when server 4 is added is the arc between s3 and s4

When server 4 is added onto the ring, the affected range starts from s4 (the newly added node) and moves anticlockwise around the ring until a server is found (s3). Keys located between s3 and s4 need to be redistributed to s4. Nothing else moves.

The same rule applies to removal: when a server is removed, the affected range starts from the removed node and moves anticlockwise until the previous server is found. Keys in that range are handed to the next server clockwise.

Wrapping Up

  • Classic hash(key) % N is fine until N changes — then it remaps almost everything.
  • A hash ring places both keys and servers in the same hash space; a key belongs to the first server clockwise.
  • Adding or removing a server only moves the keys in one arc of the ring, not the whole dataset.
  • Virtual nodes give each server many small slices of the ring, evening out both partition sizes and key clustering.

This is why consistent hashing sits under Amazon DynamoDB, Apache Cassandra, Discord's chat backend, Akamai's CDN, and plenty of load balancers. Whenever you need to add or remove machines without setting the rest of the fleet on fire, reach for the ring.

Figures in this post are from Alex Xu's System Design Interview — An Insider's Guide, Chapter 5.

References