Problem 70 · Object & System Design

Consistent Hashing Ring with Virtual Nodes

MediumClassic DSA & systems

01Problem

Implement a consistent hash ring with add_node, remove_node, and get_node(key). Each physical node owns V virtual points to smooth load distribution.

02Key insight

Hash nodes and keys onto the same ring; a key belongs to the first node point clockwise. Adding or removing a node only moves ~K/N keys, and virtual nodes cut load variance and spread a failed node's load across many peers.

03Solution

solution.pypython34 lines

import bisect
import hashlib


class ConsistentHashRing:
    def __init__(self, vnodes: int = 100) -> None:
        self.vnodes = vnodes
        self.points: list[int] = []        # sorted ring positions
        self.owner: dict[int, str] = {}    # position -> physical node

    @staticmethod
    def _hash(s: str) -> int:
        return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

    def add_node(self, node: str) -> None:
        for i in range(self.vnodes):
            p = self._hash(f"{node}#{i}")
            if p in self.owner:
                continue  # astronomically rare collision; keep first owner
            self.owner[p] = node
            bisect.insort(self.points, p)

    def remove_node(self, node: str) -> None:
        for i in range(self.vnodes):
            p = self._hash(f"{node}#{i}")
            if self.owner.get(p) == node:
                del self.owner[p]
                self.points.pop(bisect.bisect_left(self.points, p))

    def get_node(self, key: str) -> str | None:
        if not self.points:
            return None
        idx = bisect.bisect_right(self.points, self._hash(key)) % len(self.points)
        return self.owner[self.points[idx]]

Try it first.

TimeO(log(N*V)) lookup; O(V*N*V) add/remove (V insort/pop calls, each shifting an O(N*V) array)

SpaceO(N*V)

tests.py · 4 passing

tests.pypython10 lines

ring = ConsistentHashRing(vnodes=50)
assert ring.get_node("x") is None
for n in ("A", "B", "C"): ring.add_node(n)
keys = [f"k{i}" for i in range(2000)]
before = {k: ring.get_node(k) for k in keys}
assert set(before.values()) == {"A", "B", "C"}
ring.remove_node("B")
after = {k: ring.get_node(k) for k in keys}
assert all(after[k] == before[k] for k in keys if before[k] != "B")  # only B's keys moved
assert "B" not in after.values()

04Staff-level follow-up

Replication? Walk clockwise collecting the next R distinct physical nodes (preference list, as in Dynamo); for heterogeneous capacity, give each node vnodes proportional to its weight.