Consistent hashing

When data or traffic is spread over N servers, you need a rule that maps each key (a user id, a cache key, a chat room) to one server. The naive rule is server = hash(key) mod N. It is simple and even, but when N changes, almost every key maps to a different server. For a cache that means a sudden flood of misses; for a database it means moving most of the data.

Consistent hashing fixes this. Imagine a circle of hash values from 0 to 2^64. Each server is hashed to one or more points on the circle. A key is hashed onto the same circle and belongs to the first server found by walking clockwise. When a server joins, it takes over only the keys between its point and the previous point. When it leaves, only its keys move to the next server. On average only K/N keys move (K keys, N servers).

With one point per server the load is uneven, because random points leave some servers with big arcs. The standard fix is virtual nodes: each physical server is placed at 100 to 256 points. Load evens out, and a server with twice the capacity can simply get twice as many virtual nodes.

Consistent hashing is one family of answers. Related schemes you should know by name: rendezvous (highest random weight) hashing, Google's jump consistent hash, Maglev hashing for load balancers, and fixed hash slots as in Redis Cluster (16,384 slots assigned to nodes), which is not a ring but solves the same problem.

1. 1Pick a hash function with good spread (MurmurHash3, xxHash, or MD5 truncated to 64 bits). It does not need to be cryptographic, but every client must use the same one.
2. 2Place each server on the ring at many points by hashing names like 'cache-a#0', 'cache-a#1' ... 'cache-a#149'. Keep the points in a sorted array.
3. 3To find a key's owner, hash the key and binary-search the sorted array for the first point greater than or equal to it, wrapping to the start if you pass the end. Lookup is O(log V) where V is the total number of virtual nodes.
4. 4To replicate, walk clockwise and take the next R distinct physical servers (skipping more virtual nodes of a server already chosen). This is how Dynamo-style stores pick the replica set (the 'preference list') for a key.
5. 5When a server is added, it takes ownership of the arcs just before each of its virtual nodes, pulling those keys from their old owners. About 1/(N+1) of the keys move.
6. 6When a server fails or is removed, its arcs fall to the next servers clockwise. Because its virtual nodes are scattered, the extra load is spread across many servers instead of landing on one neighbour.
7. 7Keep ring membership consistent across clients: a config service (ZooKeeper, etcd), a gossip protocol (Cassandra) or a smart client library that refreshes the server list. Two clients with different rings will read and write different servers.

import bisect
import hashlib


def h(value: str) -> int:
    # Any well-mixed hash works; md5 is used here only for spread, not security
    return int(hashlib.md5(value.encode()).hexdigest()[:16], 16)


class HashRing:
    def __init__(self, nodes, vnodes=150):
        self.vnodes = vnodes
        self.ring = []          # sorted list of (position, node)
        for node in nodes:
            self.add(node)

    def add(self, node):
        for i in range(self.vnodes):
            bisect.insort(self.ring, (h(f"{node}#{i}"), node))

    def remove(self, node):
        self.ring = [(p, n) for p, n in self.ring if n != node]

    def node_for(self, key):
        pos = h(key)
        i = bisect.bisect_right(self.ring, (pos, chr(0x10FFFF)))
        return self.ring[i % len(self.ring)][1]   # wrap around the circle


ring = HashRing(["cache-a", "cache-b", "cache-c", "cache-d"])
print(ring.node_for("user:42"))   # same answer on every app server
ring.add("cache-e")               # only ~1/5 of keys now map to a new node