18. Consistent Hashing for Weighted Region Routing

Problem

A real-time voice API serving SF, London, and Bangalore needs to route each new session to a region deterministically — the same session should keep hitting the same region for its whole lifetime (so streaming/session state doesn't have to migrate), but adding or removing a region should only reshuffle the sessions that were mapped to it, not the whole world.

Regions also don't have equal capacity: a bigger region should receive proportionally more sessions. Implement a consistent hash ring with per-region virtual-node weights that solves both requirements.

Source: src/18_weighted_region_router.py

class RegionRouter:
    def __init__(self): ...
    def add_region(self, region: str, weight: int = 1) -> None: ...
    def remove_region(self, region: str) -> None: ...
    def route(self, session_id: str) -> str | None: ...

>>> r = RegionRouter()
>>> r.add_region("sf", weight=3)
>>> r.route("sess-1")
'sf'
>>> r.add_region("london", weight=3)
>>> r.add_region("bangalore", weight=3)
>>> r.route("sess-3")
'sf'

Step-by-Step Approach

1. Hash every region into multiple virtual nodes on a single ring, using a stable hash like MD5 over a string such as f"{region}#{i}" for i in range(weight) — more virtual nodes for a region means it occupies more of the ring's positions.
2. Keep the ring as a dict from hash value to region, plus a separately maintained sorted list of the hash values so a lookup can binary-search it.
3. To route a key, hash the key itself, then binary-search (bisect_left) for the first virtual-node hash at or after it on the ring, wrapping around to index 0 if the key's hash is past every virtual node.
4. To add a region, generate its virtual nodes, insert them into the ring dict, and re-sort the hash list. To avoid stale entries, if the region already exists, remove its old virtual nodes first.
5. To remove a region, delete all of its virtual-node hashes from the ring and re-sort. Because removal only touches that region's own virtual nodes, only the keys that were mapped to those specific positions can possibly move — every other key's nearest-clockwise virtual node is unaffected.
6. Handle the empty-ring case (no region ever added) by returning None from route before attempting any hash math.

The key insight is that a key's owner is determined purely by "nearest virtual node clockwise on the ring," so adding or removing a region can only perturb the keys whose nearest node was one of that region's own virtual nodes — everyone else's nearest node is untouched, which is exactly the minimal-remapping property plain modulo hashing (hash(key) % num_regions) doesn't have, since changing the region count there reshuffles almost every key.

Reference solution

import bisect
import hashlib


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


class RegionRouter:
    def __init__(self):
        # map: ring position (hash) -> region name; kept sorted for binary search
        self.ring: dict[int, str] = {}
        self.sorted_hashes: list[int] = []
        self.weights: dict[str, int] = {}

    def add_region(self, region: str, weight: int = 1) -> None:
        # if the region already exists, drop its old virtual nodes first so
        # re-adding with a new weight doesn't leave stale entries behind
        if region in self.weights:
            self.remove_region(region)
        self.weights[region] = weight
        # `weight` virtual nodes per region -- more virtual nodes means the
        # region "owns" more of the ring, so it draws proportionally more keys
        for i in range(weight):
            h = _hash(f"{region}#{i}")
            self.ring[h] = region
        self.sorted_hashes = sorted(self.ring.keys())

    def remove_region(self, region: str) -> None:
        if region not in self.weights:
            return
        weight = self.weights.pop(region)
        for i in range(weight):
            h = _hash(f"{region}#{i}")
            self.ring.pop(h, None)
        self.sorted_hashes = sorted(self.ring.keys())

    def route(self, session_id: str) -> str | None:
        if not self.sorted_hashes:
            return None
        h = _hash(session_id)
        # walk clockwise from the key's position to the first virtual node
        # at or past it; wrap around to index 0 if we ran off the end
        idx = bisect.bisect_left(self.sorted_hashes, h)
        if idx == len(self.sorted_hashes):
            idx = 0
        return self.ring[self.sorted_hashes[idx]]

Key Functions & Tricks

• hashlib.md5(...).hexdigest() — a stable, uniformly-distributed hash so ring positions don't shift between runs (Python's built-in hash() is randomized per process and unsuitable here).
• bisect.bisect_left — O(log n) lookup of the first virtual-node hash at or after the key's hash.
• Virtual nodes (f"{region}#{i}") — the mechanism that both smooths load distribution across a small number of physical regions and lets weight scale a region's share of the ring.
• Wrap-around via idx == len(sorted_hashes) — the ring is circular, so a key past the last virtual node belongs to the first one.
• Remove-then-readd on duplicate add_region — keeps the ring consistent if a region's weight changes.

How to Recognize This Pattern