Consistent hashing ring: an interactive simulator

Consistent hashing places servers and keys on the same circle of hash values, and gives each key to the first server clockwise from it. When a server joins or leaves, only the keys on its arcs move, about 1 / N of them, instead of almost all of them as with hash(key) mod N. Each server sits at many points on the ring (virtual nodes) so the load comes out even.

The playground puts 300 keys and four servers on a ring. Add a server and compare the two counts: what moved on the ring, and what would have moved with mod N. Then try one point per server against a hundred.

How consistent hashing works

1. Hash every server onto the ring, many times each: server A at hash("A#0"), hash("A#1"), and so on. Each position is a virtual node.
2. Hash every key onto the same ring: hash("user:42").
3. Walk clockwise from the key to the first server point. That server owns the key. In code this is a binary search over the sorted points, O(log n).
4. A new server takes over the arc just before each of its points, from whichever server owned it. Nothing else moves.
5. A server that leaves hands each of its arcs to the next point clockwise. With many virtual nodes, that is a little to every other server rather than everything to one neighbour.

Consistent hashing vs hash mod N

With hash(key) mod N a key's server depends on N, so changing N changes the answer for almost every key: going from N to N + 1 servers moves N / (N + 1) of the keys, 80% when a fifth server joins four. For a cache that is a near-total miss storm the moment you scale; for a database it is moving almost all the data. On the ring the same change moves about 1 / (N + 1) of the keys, 20%, and all of them to the new server, which is the minimum any scheme can move.

Mod N is still fine when N never changes, such as a fixed number of partitions you assign to servers separately. That is exactly what fixed-slot schemes do.

Why virtual nodes

With one point per server, the arcs between points are random lengths, so one server can own half the ring and another a twentieth; in the playground the busiest server holds around twice its fair share. Placing each server at 100 to 200 points splits its share into many small arcs, and the totals come out close to even, typically within 10 to 20%. Virtual nodes also make removal gentle: the leaving server's arcs are spread around the ring, so its keys go to many servers instead of doubling one neighbour's load. Give a bigger machine more points to give it more load.

Replication on the ring

To keep R copies, store each key on the first R distinct servers clockwise from it, skipping further points of a server already chosen. This is the preference list from Amazon’s Dynamo paper, and it means a server that fails has its keys already on its neighbours.

Which to use

Consistent hashing in code

The whole ring is a sorted list of points and a binary search:

import bisect, hashlib

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

class Ring:
    def __init__(self, servers, points_per_server=100):
        # every server at many places on the ring: its virtual nodes
        self.points = sorted((h(f"{s}#{i}"), s) for s in servers for i in range(points_per_server))
        self.hashes = [p for p, _ in self.points]

    def server_for(self, key: str) -> str:
        # the first point clockwise from the key, wrapping past the top
        i = bisect.bisect_left(self.hashes, h(key)) % len(self.points)
        return self.points[i][1]

Any well-spread hash works; it does not need to be cryptographic. Rebuild the list when servers change, or keep it in a sorted map and insert and delete a server’s points.

In a system design interview

Say it with the numbers: “Keys are spread over cache nodes with consistent hashing, about 150 virtual nodes each so load stays close to even and a lost node’s keys spread over all the others; each key is stored on the next two distinct nodes clockwise.” Expect the follow-ups: hot keys (consistent hashing spreads keys, not traffic, so a celebrity key needs its own fix, such as replicas or a local cache), moving the data when a node joins, and bounded loads, which cap any server at a little over the average.

Watch a strong candidate design a distributed cache, or read the consistent hashing guide for jump hash, rendezvous hashing and hot keys in depth.

Questions people ask