31. Consistent Hashing for Model-Replica Routing

Problem

A lab serves a large model across many GPU replicas, each holding a warm KV-cache for recently-seen conversation prefixes — routing the same conversation to the same replica repeatedly avoids a cold-cache miss on every turn.

As replicas are added (scaling up) or removed (draining for a deploy), most conversations should keep landing on the same replica; only conversations that were mapped to a removed replica (or now belong on a newly added one) should move. Implement a consistent hash ring that solves exactly this problem.

Source: src/31_consistent_hash_replica_router.py

class ReplicaRouter:
    def __init__(self): ...
    def add_replica(self, replica_id: str, num_virtual_nodes: int = 3) -> None: ...
    def remove_replica(self, replica_id: str) -> None: ...
    def route(self, conversation_id: str) -> str | None: ...

>>> router = ReplicaRouter()
>>> router.add_replica("R1")
>>> router.route("conv1")
'R1'
>>> router.add_replica("R2")
>>> router.add_replica("R3")
>>> before = router.route("conv1")
>>> router.remove_replica("R2")
>>> router.route("conv1") == before or before == "R2"
True

Step-by-Step Approach

1. Recognize why naive hashing (hash(key) % num_replicas) fails here: adding or removing even one replica changes num_replicas, which remaps almost every key — exactly the cache-miss storm you're trying to avoid.
2. Instead, place both replicas and keys onto the same conceptual ring of hash values (e.g. 0 to 2^128). A key is routed to whichever replica's point on the ring comes first going clockwise from the key's own hash position.
3. Give each replica several "virtual node" points on the ring (e.g. hash of f"{replica_id}#{i}" for i in range(num_virtual_nodes)) rather than just one — this smooths out load distribution, since with only one point per replica some replicas could end up owning a much larger arc of the ring than others by chance.
4. Keep the ring as a single sorted list of (hash_value, replica_id) pairs. Use bisect.insort to add points and binary search (bisect.bisect_left) to route — that's what makes routing O(log n) instead of a linear scan.
5. To route a key: binary search for the first ring point whose hash is >= the key's hash. If no such point exists (the key's hash is past every point on the ring), wrap around to index 0 — the ring is circular.
6. To remove a replica, filter out every one of its virtual-node points from the ring; every key that pointed to one of those removed points remaps to whatever's now the next point clockwise — but every key that pointed elsewhere is completely unaffected.

The key insight is that only the keys whose ring position was "owned" by the changed replica ever move — every other key's nearest-clockwise point is untouched, so on average adding or removing one of N replicas only remaps roughly 1/N of all keys, not almost all of them.

Reference solution

import bisect
import hashlib


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


class ReplicaRouter:
    def __init__(self):
        # ring stays sorted by construction -- only bisect.insort and a filter mutate it
        self.ring: list[tuple[int, str]] = []
        self.replicas: set[str] = set()

    def add_replica(self, replica_id: str, num_virtual_nodes: int = 3) -> None:
        # O(virtual_nodes log n): each insort is an O(n) shift + O(log n) search
        for r in range(num_virtual_nodes):
            h = _hash(f"{replica_id}#{r}")
            bisect.insort(self.ring, (h, replica_id))
        self.replicas.add(replica_id)

    def remove_replica(self, replica_id: str) -> None:
        # O(n): one filtering pass rebuilds the ring without this replica's points
        self.ring = [(h, r) for h, r in self.ring if r != replica_id]
        self.replicas.discard(replica_id)

    def route(self, conversation_id: 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(conversation_id)
        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() converted via int(..., 16) — a cheap, well-distributed hash into a huge integer space
• bisect.insort(ring, (h, replica_id)) — keeps the ring sorted on insert, O(log n) search + O(n) shift
• bisect.bisect_left(ring, (h,)) — binary search for the first point >= h; comparing a 1-tuple against 2-tuples works because Python tuple comparison stops at the first element when they differ
• if idx == len(ring): idx = 0 — the wraparound that makes the ring circular
• Virtual nodes — multiple ring points per replica, smoothing load distribution versus one point per replica

How to Recognize This Pattern