Consistent Hashing

You have 10 cache servers. You route keys to them with hash(key) mod 10. It works beautifully. Then you add an 11th server. Now ~90% of your keys hash to a different server — your entire cache invalidates. Origin gets hammered, latency spikes, users see "loading" everywhere.

Consistent hashing (Karger et al., 1997) solves this. When you add or remove a node, only ~1/N of keys move. Adding an 11th server to a 10-server cluster moves 9% of keys. Graceful scaling. It's the technique behind DynamoDB, Cassandra, Memcached clients, and every CDN.

Imagine a circle from 0 to 2³² − 1. Each node takes a position on the ring (via hash(node_id)). Each key also takes a position (hash(key)). A key belongs to the first node you hit going clockwise from the key's position.

Add a node: it claims a fresh arc between two existing nodes. Only the keys in that arc move — from the node that used to own that slice. No other node's keys move. Remove a node: its arc transfers to the next clockwise neighbor. Again, only that slice moves.

The genius: the rest of the ring is stable. No mass rehashing. Add/remove a node, and only ~1/N of the total keyspace is affected.

A naive ring has two problems. (1) If 3 nodes happen to hash to nearby positions, one node owns almost nothing and another owns most of the ring — uneven load. (2) When a node dies, its entire load transfers to exactly one neighbor — hot spot on failure.

Fix: each physical node claims many virtual positions on the ring (typically 100–200). So node A isn't at "position 1234" — it's at 200 different positions, scattered across the ring. This makes load spread statistically even, and when a node dies, its 200 slices go to 200 different neighbors.

Every real consistent-hashing implementation uses virtual nodes. The word "consistent hashing" in interviews should automatically imply "with virtual nodes."

from hashlib import md5
from bisect import bisect

class HashRing:
    def __init__(self, nodes, vnodes=150):
        self.ring = {}
        for n in nodes:
            for i in range(vnodes):
                h = int(md5(f"{n}#{i}".encode()).hexdigest(), 16)
                self.ring[h] = n
        self.sorted = sorted(self.ring)

    def get(self, key):
        h = int(md5(key.encode()).hexdigest(), 16)
        idx = bisect(self.sorted, h) % len(self.sorted)
        return self.ring[self.sorted[idx]]

    def add(self, node, vnodes=150):
        for i in range(vnodes):
            h = int(md5(f"{node}#{i}".encode()).hexdigest(), 16)
            self.ring[h] = node
        self.sorted = sorted(self.ring)

# Adding 1 shard to N=10 → only 1/11 of keys remap (vs N/2 in mod-hashing)

Rendezvous hashing (Highest Random Weight, HRW) is a simpler alternative used by some CDNs: compute hash(key, node_id) for each node, pick the node with the highest hash. Achieves the same "only 1/N moves" property without a ring or virtual nodes. Conceptually cleaner; slightly slower per lookup (O(N) vs O(log N) with a sorted ring). CRUSH (Ceph's placement algorithm) is a variant.

Consistent hashing pairs elegantly with replication. To store a key with 3× replication, walk the ring three nodes clockwise starting from the key's position, placing a copy at each. When a node dies, the N-1 remaining replicas are still on the ring — and the next node clockwise automatically takes the dead node's shard.

This is why Cassandra / DynamoDB use it: one algorithm handles partitioning AND replication. When you add a node, it joins the ring, takes ownership of 1/N of the keyspace, and pulls its data from the three nodes that previously held those ranges. No central coordinator; no rehash-the-world; no manual intervention.

The interview answer: "Consistent hashing with virtual nodes. Each physical node claims ~200 virtual positions for even distribution. Keys map to the next clockwise node; replicas live on the next K clockwise nodes. Adding a node moves ~1/N of keys — graceful scaling without cascading invalidation."

URL shortener shards the redirect DB by consistent-hashed short code. News feed shards feed cache across Redis nodes. Rate limiter shards counters. WhatsApp shards chat data. Distributed logging shards log streams.