Consistent Hashing, Visually Explained

Why modulo hashing breaks

With hash(key) % N, the server for each key depends on N (the number of servers). If N changes, the answer changes for most keys. Here is an example, using small numbers as the hashes:

In this small sample, 5 of 9 keys moved. Across all keys, going from 4 to 5 servers keeps only about 1 in 5 keys in place, so about 80% move. Going from 100 to 101 servers moves about 99%. For a cache, this means a flood of misses (the data is not found in the cache). For a database, it means moving nearly all the data.

The hash ring

1. Imagine all possible outputs of a hash function (say 0 to 2³² − 1) arranged in a circle. After the biggest number, you wrap around to 0.
2. Hash each server (for example, its name or IP address) to get a point on the ring.
3. Hash each key to get a point on the ring.
4. A key belongs to the first server clockwise from its position.

To keep it simple, use a small ring from 0 to 99, with servers at A = 10, B = 45, C = 80. Picture this line bent into a circle, so that position 99 joins back to 0:

Adding a server

Add D at position 60:

Only the keys between 45 and 60 (the arc just before D) move, from C to D. Everything that A and B own is untouched. So are C's other keys.

Removing a server

Now suppose B (45) dies. Its keys (the arc from 10 to 45, including k2) move to the next server clockwise, which is C. A's keys are not affected.

On average, adding or removing one server moves only about 1/N of the keys. With 5 servers, that is about 20%. With modulo hashing it is about 80%.

The problem with a simple ring: uneven load

A server's arc is the part of the ring that it owns. If you have only a few servers at random points, the arcs can be very uneven:

Also, when a server fails, all of its load goes to one neighbour. That neighbour might then fail too. This chain of failures is called a cascade.

Virtual nodes (vnodes)

The fix is to place each physical server at many points on the ring, often 100–200. Each point is a virtual node (vnode). You make the points with different hashes, like hash("A#1"), hash("A#2") and so on.

Ring positions:  A1 C1 B1 A2 B2 C2 A3 C3 B3 A4 ...                 (each physical server appears many times, spread out)

• ✅ Even distribution. With many points, each server's total share becomes close to 1/N.
• ✅ Failures spread out. When A dies, its many small arcs go to many different servers, not just to one neighbour.
• ✅ Mixed hardware. A server that is twice as powerful gets twice as many virtual nodes, so it holds twice the data.
• ❌ More metadata (extra information) to track, because the ring map is bigger. This is a small cost.

Replication on the ring

Distributed databases also use the ring for replication (keeping copies). Store each key on the owner and on the next N−1 distinct physical servers clockwise. Here N is the number of copies you want:

Replication factor 3:  key → first server clockwise (primary) + next 2 distinct servers (replicas)

This is how Dynamo-style databases (Cassandra, Riak, ScyllaDB) decide which nodes hold the copies of each piece of data. It connects with the quorums in Lesson 24. Real systems also make sure that the replicas are on servers in different racks or availability zones (separate data centre areas, so one failure does not hit all copies).

Looking up a key efficiently

In code, the ring is usually a sorted list of node positions. To find the owner of a key, you binary search for the first position after the key's hash. Binary search checks the middle of the list and keeps only the half that can hold the answer. If there is no position after the hash, you wrap around to the start of the list. This takes O(log M) steps, where M is the number of virtual nodes. So it is very fast.

import bisect, hashlibdef h(s):  # hash to a big integer    return int(hashlib.md5(s.encode()).hexdigest(), 16)class Ring:    def __init__(self, nodes, vnodes=100):        self.ring = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))        self.keys = [pos for pos, _ in self.ring]    def owner(self, key):        i = bisect.bisect(self.keys, h(key)) % len(self.ring)  # wrap around        return self.ring[i][1]ring = Ring(["cache-a", "cache-b", "cache-c"])print(ring.owner("user:42"))   # cache-a

(MD5 is fine here, because we only need an even spread of numbers, not security.)

Alternatives worth knowing

• Rendezvous hashing (Highest Random Weight, HRW). For each key, compute a score for every server (hash(key + server)) and pick the server with the highest score. It is simple and gives an even spread, with no ring or virtual nodes. But one lookup takes O(N) steps. This is fine for tens or hundreds of servers.
• Jump consistent hash (from Google). A tiny and fast algorithm. It maps keys to numbered buckets 0…N−1, with little movement and an almost perfect balance. The catch: the servers are numbered, so you can only add or remove servers at the end of the list.
• Maglev hashing (from Google). It uses a lookup table to route traffic in a load balancer (Lesson 12) very fast and evenly.
• Consistent hashing with bounded loads. This adds a limit, so that no server gets more than, say, 125% of the average load. The extra load goes to the next server. It protects against hot spots.