Consistent Hashing

Markers: ⭐ MUST KNOW — core answer, asked directly. 🎯 FOCUS — high-value senior-loop follow-up. 💡 GOOD TO KNOW — depth/impressor, recognize + one-liner is enough.

1. The Problem It Solves ⭐ MUST KNOW

• Naive approach: server = hash(key) % N.
• Breaks the moment N changes. Modulus changes from N to N+1, so almost every key's assignment changes.
• Real-world impact: cache layer → mass cache misses → thundering herd on the DB. Partitioned DB → massive unnecessary rebalancing.
• Desired property: when adding/removing one node out of N, only ~1/N of keys should move. Everything else stays put. Naive modulo hashing gives none of this — it's all-or-nothing.

One-liner: Modulo remaps ~(N-1)/N of keys on scale change; consistent hashing remaps ~1/N. That's the whole point.

2. The Core Idea — a Ring ⭐ MUST KNOW

1. Pick a hash function with a large output range (32-bit/64-bit). Treat that range as a circle that wraps around (the "ring").
2. Hash each server identifier (IP, hostname, node ID) onto the ring — each server owns one point.
3. To find a key's owner: hash the key onto the same ring, then walk clockwise to the first server hit. That server owns the key.

The question shifts from "which bucket out of N" to "which server point is nearest clockwise from this key."

Why this fixes rebalancing: add a server → only keys between the new node and its clockwise neighbor get reassigned, every other server untouched. Remove a server → only its keys move, to the next clockwise server. Locality on the ring = locality of impact.

3. Virtual Nodes (the essential fix) ⭐ MUST KNOW

• Problem: hashing each physical server to ONE point gives wildly uneven arcs by luck of the hash — one server might own 40% of the ring, another 5%. Worse: removing a server dumps all its load onto exactly one neighbor.
• Fix: hash each physical server to many points (~100–200, or 8–256 in modern Cassandra) via hash(server_id + ":0"), hash(server_id + ":1"), etc. Each physical server owns many small scattered arcs — load averages out, and on failure the load spreads across many others instead of dumping onto one neighbor.
• Trade-off: more vnodes → better balance, but more memory for ring metadata and slower lookups.

4. Replication on the Ring 🎯 FOCUS

Simple case (no vnodes): for replication factor N=3, walk clockwise from the key, take the first 3 distinct servers.

With virtual nodes (the subtlety): a physical server appears many times on the ring. The replica walk is not "first N points clockwise" — it's "walk clockwise, take the first N points that map to N distinct physical machines, skipping any vnode whose owner is already counted." Topology-aware systems (Cassandra's NetworkTopologyStrategy) add constraints: distinct rack / distinct AZ, not just distinct server. On write, if a target replica is down, the walk continues to the next distinct server as a temporary stand-in (hinted handoff), reconciled later.

Mental model: the ring gives an ordering; replication = "first N distinct things you care about in that ordering," where "things" = machines/racks/AZs depending on topology sophistication.

5. Real-World Implementations 💡 GOOD TO KNOW

Know Cassandra/Dynamo (ring + vnodes) and Ketama cold; the rest — one-line recognition is enough.

• Cassandra / DynamoDB — Murmur3Partitioner hashes keys/tokens into 64-bit space; num_tokens = vnodes.
• Ketama (libketama) — original memcached client sharding: sorted array of (hash, server) + binary search. The reference answer for "implement consistent hashing."
• Maglev (Google) — table-based alternative (~65537 slots), O(1) lookup, tighter balance, costlier rebuild on membership change.
• Rendezvous / Highest Random Weight (HRW) — hash(key, server_id) per server, pick the highest score. No ring, no vnodes. O(N) lookup vs O(log N) for a ring — good for small/stable server counts.
• Bounded-load consistent hashing — caps how far above average any server's load can go; keys skip forward past an overloaded owner.

6. Implementation ⭐ MUST KNOW

Core coding task: implement a ring with add_server(id), remove_server(id), get_server(key).

import bisect, hashlib

class ConsistentHashRing:
    def __init__(self, vnodes=100):
        self.vnodes = vnodes
        self.ring = {}              # hash -> physical server
        self.sorted_hashes = []

    def _hash(self, s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def add_server(self, server_id):
        for v in range(self.vnodes):
            h = self._hash(f"{server_id}:{v}")
            self.ring[h] = server_id
            bisect.insort(self.sorted_hashes, h)

    def remove_server(self, server_id):
        for v in range(self.vnodes):
            h = self._hash(f"{server_id}:{v}")
            del self.ring[h]
            self.sorted_hashes.remove(h)   # O(n) — fine for interview

    def get_server(self, key):
        h = self._hash(key)
        idx = bisect.bisect(self.sorted_hashes, h) % len(self.sorted_hashes)
        return self.ring[self.sorted_hashes[idx]]

Escalating follow-ups (in the order they tend to come): (1) "What if only one vnode per server?" → load skew, introduce vnodes. (2) "How do you pick N replicas?" → skip-duplicate-physical-owner walk. (3) "Complexity of add/remove/lookup, faster remove?" → §7. (4) "Concurrency?" → §8. (5) "A specific key is hot?" → §9. (6) "Compare to rendezvous hashing." → O(log N) vs O(N), no vnode tuning needed.

7. Complexity — Making Remove Faster Than O(n) 🎯 FOCUS

Balanced BST / TreeMap is what Cassandra actually uses (TokenMetadata → TreeMap<Token, InetAddressAndPort>, a red-black tree): floorKey()/ceilingKey() give O(log n) clockwise-walk lookup, put()/remove() are O(log n) via rotations, not array shifts. Skip lists are easier to make concurrent (no rotations) — Redis uses them for sorted sets. Sorted array + batch rebuild is a legitimate real-world choice when ring membership changes are rare (administrative) — eating an O(n) rebuild amortized over millions of O(log n) lookups is fine; reach for BST/skip-list only when membership churns often (elastic autoscaling).

The expected upgrade from the bisect version: "TreeMap / balanced BST → ceilingKey() for the clockwise walk, O(log n) everything."

8. Concurrency — Adds/Removes vs In-Flight Lookups 💡 GOOD TO KNOW

Only comes up in senior/staff loops. Answer = copy-on-write immutable snapshot; memorize the phrase and why readers never block.

1. Ring is immutable — lookups only read whatever snapshot reference they hold, no mutation.
2. On add/remove: build an entirely new ring object (takes as long as needed, nothing blocked).
3. Atomically swap a single pointer from "current ring" to "new ring."
4. In-flight lookups finish safely against the old, still-consistent ring; new lookups see the new ring.

Relies on atomicity of a single reference write (AtomicReference in Java, atomic.Value in Go, GIL-protected reassignment in Python) — this is the RCU (read-copy-update) pattern applied to a hash ring. No lock is ever held during lookups. Versioned rings with epoch numbers extend this to gossip-based multi-node systems, letting a node detect "this request assumed ring v41, I'm on v43" without a global lock.

Why not just an RWLock? Valid and simpler when mutations are rare. CoW goes further: no reader ever blocks on a writer even briefly, and extends naturally to distributed settings with no single lock to hold.

9. Hot Keys 🎯 FOCUS

Common trap: interviewers push "vnodes balance load, so hot keys are solved, right?" — No. vnodes fix placement skew, not demand skew. Know this distinction cold.

A hot key (viral post, celebrity profile, flash-sale item) is hit far more than others regardless of ring balance — consistent hashing's "one deterministic owner per key" property IS the problem here.

Fixes:

• Request-level replication of the hot key — fan out to more servers than the normal N, load-balance reads across them ("hot key splitting," used by Twemproxy/Facebook memcache).
• Client-side / edge caching — push a short-TTL copy to the layer nearest the request; popularity makes even a seconds-long TTL highly effective.
• Request coalescing / single-flight — concurrent requests for the same key share one fetch instead of each hitting the origin (kills the "thundering herd on expiry" variant).
• Bounded-load consistent hashing — hard cap on how far above average any server's load can go; a load-shedding safety valve, not demand reduction — used alongside replication/caching.

10. CDN Routing 💡 GOOD TO KNOW

Two different problems get conflated: client → nearest edge POP is DNS geo-routing/anycast (NOT consistent hashing); within/across a POP → which cache machine holds this object IS consistent hashing. Hashing the request key onto a ring of cache-server identities means every server resolves the same key to the same owner — the object is fetched from origin once and cached on one (or N) machines, avoiding the thundering-herd-on-cold-cache problem. Same mechanism as memcached sharding; adding/removing a cache node reassigns only ~1/N of URL space. See [[CDN]].

11. Sticky Sessions on Load Balancers 💡 GOOD TO KNOW

Naive backend = hash(client_id) % N means scaling the backend pool remaps nearly every client, causing mass session loss right when scaling. Consistent-hash affinity fixes this the same way: hash the session identifier onto a ring of backends, so scaling remaps only ~1/N of sessions. Real config knobs worth naming: HAProxy's balance hash-type consistent, nginx's hash $key consistent;, Envoy's ring_hash/maglev policies. See [[Load Balancing]].

12. How Data Physically Rearranges When a Server Is Added 🎯 FOCUS

Two fundamentally different cases:

Cache (memcached-style): nothing is migrated — the new owner simply doesn't have the keys yet, so the next request is a miss, fetched from origin, and populated on the new owner. The old server's copies go cold via its own LRU. "Migration" is free — just organic cache warming.

Persistent storage (Cassandra/Dynamo-style): data actually moves. (1) New node picks token(s) (~256 vnodes). (2) With vnodes, it claims small slices from many existing nodes, not one contiguous chunk. (3) Existing owners stream data directly over a dedicated streaming protocol (not write replay). (4) The joining node is invisible to reads until streaming completes and is verified — flips to serving only after catching up; old owners drop redundant copies via a deliberate cleanup step. (5) Old owners keep serving throughout — no availability gap.

Anti-entropy safety net: streaming is best-effort; background repair (Merkle-tree comparison across replicas — see [[Merkle Trees]] for the full mechanism) re-syncs any divergence after the fact — the general "fast/best-effort primary path + slower background reconciliation path" pattern recurs across distributed systems interviews.

Focus Summary — Where to Spend Reps

Cross-links

[[Caching & Redis]] · [[Load Balancing]] · [[Database Replication & Sharding]] · [[Design a URL Shortener]] · [[Message Queues & Kafka]] · [[Merkle Trees]]