34. Consistent Hashing for Gradual Feature Rollout

Problem

A naive way to assign users to rollout targets is hash(user_id) % num_nodes. It's simple, but it falls apart the moment num_nodes changes: scale a rollout from 3 buckets to 4, and the modulo of nearly every key changes, so nearly every user gets remapped to a different bucket even though only one bucket was added. For a gradual feature rollout that's supposed to keep users "sticky" to their variant, that's unacceptable churn.

Consistent hashing fixes this by hashing both nodes and keys onto the same fixed circular space (a "ring") instead of hashing into a range that depends on num_nodes. A key is routed to the first node clockwise from its hash position. Adding or removing a node only affects the narrow arc of the ring around that node — every other key keeps its existing assignment. Because a single node landing at just one point on the ring can still leave load unevenly distributed, each real node is hashed multiple times into several "virtual node" replicas scattered around the ring, which smooths out the distribution of keys across nodes.

Source: src/34_consistent_hashing_rollout.py

class ConsistentHashRing:
    def __init__(self): ...
    def add_node(self, node_id: str, num_replicas: int = 3) -> None: ...
    def remove_node(self, node_id: str) -> None: ...
    def get_node(self, key: str) -> str | None: ...

>>> ring = ConsistentHashRing()
>>> ring.get_node("user1")
>>> ring.add_node("A")
>>> ring.get_node("user1")
'A'
>>> ring.add_node("B")
>>> ring.add_node("C")
>>> ring.get_node("user1")
'B'
>>> ring.remove_node("B")
>>> ring.get_node("user1")
'C'
>>> ring.get_node("user3")
'C'

Step-by-Step Approach

1. Represent the ring as a sorted list of (hash_value, node_id) entries. Use a deterministic, non-randomized hash — hashlib.md5, not Python's built-in hash() — so results are reproducible across runs and machines.
2. When adding a node, don't hash it just once: hash num_replicas distinct virtual-node names (e.g. f"{node_id}#{r}" for r in range(num_replicas)) and insert each into the sorted ring. More replicas per node means a more even key distribution.
3. Insert each new ring entry in sorted position with bisect.insort rather than appending and re-sorting the whole list.
4. To route a key, hash the key and binary-search the ring with bisect.bisect_left for the first entry whose hash is >= the key's hash.
5. If the search runs off the end of the list (the key's hash is greater than every node's hash), wrap around to index 0 — the ring is circular, so the "first node clockwise" from the highest hash value is the node at the lowest hash value.
6. Removing a node only requires filtering out that node's own virtual-node entries from the ring; every other node's entries, and therefore every key that wasn't routed to the removed node, are untouched.

The key insight is that only the keys whose nearest-clockwise node was the removed (or added) node ever change assignment — with N nodes, that's roughly a 1/N fraction of keys, versus modulo hashing where changing num_nodes typically remaps almost every key.

Reference solution

import bisect
import hashlib


def _hash(key: str) -> int:
    return int(hashlib.md5(key.encode()).hexdigest(), 16)


class ConsistentHashRing:
    def __init__(self):
        # O(1): ring stays sorted by construction (only insort/filter mutate it)
        self.ring: list[tuple[int, str]] = []
        self.nodes: set[str] = set()

    def add_node(self, node_id: str, num_replicas: int = 3) -> None:
        # O(replicas log n): each insort is O(n) shift + O(log n) search, done `replicas` times
        for r in range(num_replicas):
            h = _hash(f"{node_id}#{r}")
            bisect.insort(self.ring, (h, node_id))
        self.nodes.add(node_id)

    def remove_node(self, node_id: str) -> None:
        # O(n): one filtering pass rebuilds the ring without this node's entries
        self.ring = [(h, n) for h, n in self.ring if n != node_id]
        self.nodes.discard(node_id)

    def get_node(self, key: str) -> str | None:
        # O(log n): binary search for the first ring point >= hash(key), wrapping to 0
        if not self.ring:
            return None
        h = _hash(key)
        idx = bisect.bisect_left(self.ring, (h,))
        if idx == len(self.ring):
            idx = 0
        return self.ring[idx][1]

Key Functions & Tricks

• hashlib.md5(key.encode()).hexdigest() — deterministic hash, unlike Python's randomized-per-process hash().
• bisect.insort(self.ring, (h, node_id)) — inserts a new ring entry while keeping the list sorted.
• bisect.bisect_left(self.ring, (h,)) — binary search for the first entry with hash >= h; a 1-tuple compares correctly against 2-tuples.
• if idx == len(self.ring): idx = 0 — wrap-around trick that makes the sorted list behave like a circular ring.
• num_replicas virtual nodes per real node — spreads one node across several ring points, smoothing an otherwise lumpy key distribution.
• [(h, n) for h, n in self.ring if n != node_id] — list-comprehension filter drops only the removed node's entries, O(n).
• self.nodes: set[str] — tracks real node membership separately from the (replica-expanded) ring.

How to Recognize This Pattern