Consistent hashing ring

Q: How would this look in Go, and in production?

In Go the ring is a []uint32 of sorted positions plus a map[uint32]string or parallel slice, and sort.Search for the lookup. Hash with crc32.ChecksumIEEE or FNV rather than MD5 if you do not need to match another language. Build a new ring on membership change and swap it in with atomic.Pointer, so lookups never take a lock. Memcached clients (ketama), Cassandra's token ring and many load balancers' hash-based balancing use this scheme. Rendezvous (highest random weight) hashing is a simpler alternative with the same minimal-movement property.

mediumRouting and distribution

You shard keys (cache entries, user sessions, tenants) across a set of servers. With hash(key) % N, adding or removing one server changes N, and almost every key moves: a cache cluster that loses one node suddenly misses on most of its keys. Consistent hashing fixes that. Build a hash ring where adding or removing a node only moves the keys that must move.

API (Java: addNode, removeNode, getNode, nodes; constructor takes vnodes)

◈ DIAGRAM

HashRing(vnodes=100)
add_node(node: str) -> None
remove_node(node: str) -> bool     # False if the node was not in the ring
get_node(key: str) -> str or None  # None when the ring is empty
nodes() -> list[str]               # sorted

Rules

Positions on the ring are 32-bit unsigned integers. Use hash(s) = the first 4 bytes of the MD5 digest of s (UTF-8), read big-endian. MD5 is used here only because it is stable across processes and languages, not for security. Python's built-in hash() is randomised per process, so it cannot be used.
Each node is placed at vnodes positions: hash("<node>#0"), hash("<node>#1"), and so on (virtual nodes).
A key belongs to the first node position clockwise from hash(key): the smallest position >= the key's hash. If there is none, wrap around to the smallest position on the ring. If two positions are equal, the node whose name sorts first owns it.
add_node on an existing node raises ValueError.
get_node must be O(log n) in the number of positions.

In the examples the ring has vnodes=50, and 1,000 keys key-0 to key-999 are used to measure movement. Example 2 continues from example 1.

Examples

Example 1

Input: ring = HashRing(vnodes=50) add cache-a, cache-b, cache-c ring.get_node("user:1001") ring.get_node("user:1002") ring.get_node("session:42") ring.get_node("img/logo.png") keys per node for key-0 .. key-999 ring.remove_node("cache-b") keys whose owner changed ...of which were not on cache-b

Output: cache-b cache-b cache-c cache-a {cache-a=320, cache-b=311, cache-c=369} true 311 0

Explanation: Removing cache-b moves exactly its 311 keys, spread over the surviving nodes. Keys on cache-a and cache-c do not move.

Example 2

Input: ring.add_node("cache-b") ring.add_node("cache-d") ring.nodes() keys whose owner changed vs. the 3-node ring all of them moved to cache-d? HashRing().get_node("anything") HashRing().remove_node("cache-x")

Output: [cache-a, cache-b, cache-c, cache-d] 261 true null false

Explanation: Re-adding cache-b restores its old positions, so its keys come back. Adding a fourth node takes about a quarter of the keys, and every moved key goes to the new node.

Hints

Approach

Keep two parallel arrays sorted by position: hashes and owners.

Membership change: add or remove the node from the member set and rebuild the arrays from all node#i labels, sorted by (hash, node name). Rebuilding is O(P log P) for P = nodes × vnodes positions. That is fine, because membership changes are rare compared with lookups. A tree map would allow incremental updates if they were frequent.
Lookup: binary search for the first position >= hash(key) (bisect_left, or a hand-written lower bound in Java). If the index equals the array length, wrap to 0. Return that position's owner.

Why only the necessary keys move: a node's positions are fixed by its name, so removing a node deletes only its own positions. Keys that were on those arcs now continue clockwise to the next position, and every other key's next position is unchanged. Virtual nodes cut each server's share into many small arcs, so the load is spread more evenly and a removed node's keys are shared among all the survivors rather than dumped on one neighbour.

ComplexityTime O(log P) get_node; O(P log P) add/removeSpace O(P) where P = nodes × vnodes

Python

import bisect
import hashlib
 
 
def _hash(s):
    """First 4 bytes of MD5 as an unsigned 32-bit int: stable across processes and languages."""
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:4], "big")
 
 
class HashRing:
    def __init__(self, vnodes=100):
        if vnodes < 1:
            raise ValueError("vnodes must be at least 1")
        self.vnodes = vnodes
        self.members = set()
        self.hashes = []       # sorted ring positions
        self.owners = []       # owners[i] owns position hashes[i]
 
    def _rebuild(self):
        points = sorted((_hash(f"{node}#{i}"), node)
                        for node in self.members for i in range(self.vnodes))
        self.hashes = [h for h, _ in points]
        self.owners = [n for _, n in points]
 
    def add_node(self, node):
        if node in self.members:
            raise ValueError(f"{node} is already in the ring")
        self.members.add(node)
        self._rebuild()
 
    def remove_node(self, node):
        if node not in self.members:
            return False
        self.members.remove(node)
        self._rebuild()
        return True
 
    def get_node(self, key):
        if not self.hashes:
            return None
        i = bisect.bisect_left(self.hashes, _hash(key))   # first position clockwise
        return self.owners[i % len(self.owners)]          # past the end wraps to the start
 
    def nodes(self):
        return sorted(self.members)

Follow-up questions

Return the next 2 distinct nodes clockwise for replication. How do you skip vnodes of a node you already chose?
Give nodes weights so a bigger server takes more keys.
Rebuild the ring while lookups are running on other threads.

Frequently asked questions

More vnodes means a more even split, at the cost of memory and rebuild time. Here, 50 vnodes on 3 nodes still gives shares from 311 to 369 per 1,000 keys. A few hundred per node is a common setting. Vnodes also give you weighting for free: a server with twice the memory gets twice the vnodes.

In Go the ring is a []uint32 of sorted positions plus a map[uint32]string or parallel slice, and sort.Search for the lookup. Hash with crc32.ChecksumIEEE or FNV rather than MD5 if you do not need to match another language. Build a new ring on membership change and swap it in with atomic.Pointer, so lookups never take a lock. Memcached clients (ketama), Cassandra's token ring and many load balancers' hash-based balancing use this scheme. Rendezvous (highest random weight) hashing is a simpler alternative with the same minimal-movement property.