Consistent Hashing — Interview Notes

[!success] Status: COMPLETED Full depth covered. Below is marked so you know what to drill vs what's bonus.

[!info] How to read the markers

• ⭐ MUST KNOW — core answer, will be asked directly. Drill until automatic.
• 🎯 FOCUS — high-value follow-up, comes up in most senior loops.
• 💡 GOOD TO KNOW — depth/impressor. Recognize + one-liner enough; don't over-invest.

---

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.

[!important] One-liner to memorize Modulo remaps ~(N-1)/N of keys on scale; 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 (e.g. 32-bit or 64-bit int). 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.

• Question shifts from "which bucket out of N" → "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 is untouched.
• Remove a server → only its keys move, to the next server clockwise. Everyone else unchanged.
• 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: when a server is removed, all its load dumps onto exactly ONE neighbor.
• Fix: hash each physical server to many points (~100–200, or 8–256 in modern Cassandra) using hash(server_id + ":0"), hash(server_id + ":1"), etc. Each physical server owns many small scattered arcs.

Benefits:

• Load averages out evenly across servers.
• On failure, a server's load spreads across many others instead of dumping onto one neighbor.

Tradeoff: 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.
• Easy because each server appears exactly once.

With virtual nodes — the subtlety

• A physical server appears many times on the ring (C1, C2, C3, C4...).
• Replica walk is NOT "take 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 you've already counted."

Consequences:

• Skip-distance is variable (random vnode scatter), so the ring "span" of a replica set varies.
• Topology awareness (Cassandra's NetworkTopologyStrategy) layers extra constraints: distinct rack / distinct AZ, not just distinct physical server.
• Failure/hinted handoff: if a target replica is down at write time, walk continues to the next distinct server as a temporary stand-in; reconciled later.

[!important] Mental model The ring gives an ordering; replication = "first N distinct things you care about in that ordering," where "things" = physical machines / racks / AZs depending on topology sophistication.

5. Real-world implementations 💡 GOOD TO KNOW

[!tip] Focus tip Know Cassandra/Dynamo (ring + vnodes) and Ketama (the "implement it" reference) cold. The rest — one-line recognition is enough.

• Cassandra / DynamoDB — Murmur3Partitioner hashes keys and tokens into 64-bit space. num_tokens = vnodes. Replica placement = clockwise walk + skip repeated owners + rack/AZ diversity.
• Ketama (libketama) — original memcached client sharding. Sorted array of (hash, server) points + binary search. The reference answer for "implement consistent hashing."
• McRouter (Facebook) — memcached proxy-layer sharding.
• Maglev (Google, NSDI 2016) — table-based alternative (~65537 slots), O(1) lookup, tighter balance than rings, at the cost of table rebuild on membership change. Google's production LB.
• Rendezvous / Highest Random Weight (HRW) — for each key, compute hash(key, server_id) per server, pick highest score. No ring, no vnodes needed. O(N) lookup vs O(log N) for a ring. Good for small/stable server counts.
• Bounded-load consistent hashing (Google, 2016) — caps how far above average any server's load can go; keys skip forward past an overloaded owner.

6. Interview questions around 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, and how to make remove faster than O(n)?" → see section 7.
4. "How do you handle concurrency?" → see section 8.
5. "A specific key is hot?" → see section 9.
6. "Compare to rendezvous hashing." → O(log N) vs O(N), no vnode tuning needed.

7. Complexity and making remove faster than O(n) 🎯 FOCUS

• Naive list + bisect: search is O(log n) but insert/delete is O(n) (array shift).
• Fix: use a structure where BOTH search and mutation are O(log n).

• Balanced BST / TreeMap — what Cassandra actually uses (TokenMetadata → TreeMap<Token, InetAddressAndPort>, a red-black tree). floorKey()/ceilingKey() = O(log n) clockwise-walk lookup; put()/remove() = O(log n) via rotations, not array shifts.
• Skip lists — easier to make concurrent than a balanced BST (no rotations). Redis uses them for sorted sets. O(log n) expected via random levels.
• Sorted array + batch rebuild — legitimate real-world choice: ring membership changes are rare (administrative), so 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).

[!important] The move Answer "TreeMap / balanced BST → ceilingKey() for the clockwise walk, O(log n) everything." That's the expected upgrade from the bisect version.

8. Concurrency — adds/removes vs in-flight lookups 💡 GOOD TO KNOW

[!tip] Focus tip Only need this in senior/staff loops. Answer = Copy-on-Write immutable snapshot. Memorize that phrase + why readers never block.

• Problem: a lookup is walking the ring while an add/remove mutates it. Locking the whole ring per lookup serializes all traffic — unacceptable on the request hot path.

Copy-on-write (CoW) immutable snapshots (the production pattern):

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 (Java), atomic.Value (Go), ArcSwap (Rust), GIL-protected reassignment (Python). This is the RCU (read-copy-update) pattern applied to a hash ring. No lock held during lookups.

Versioned rings with epoch numbers (refinement for multi-node / gossip systems):

• Each snapshot carries a monotonic version/epoch.
• Detects staleness: a node can recognize "this request assumed ring v41, I'm on v43" and redirect.
• Enables gossip convergence: nodes learn ring changes asynchronously; versions let a node reason about currency without a global lock.

Why not just an RWLock? Valid and simpler when mutations are rare (many concurrent readers, block only on rare writer). But CoW goes further: no reader ever blocks on a writer even briefly, and it extends naturally to distributed multi-node settings (no single lock to hold). Follow-up trap: "what if the write rebuild takes 50ms — comfortable blocking reads cluster-wide?" CoW answer: reads never block, period.

9. Hot keys 🎯 FOCUS

[!warning] 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.

• Virtual nodes fix structural imbalance (uneven arcs from placement). Fixed at ring-construction time.
• A hot key is a traffic-pattern problem: one key (viral post, celebrity profile, flash-sale item) hit far more than others regardless of ring balance. Consistent hashing's "one deterministic owner per key" IS the problem here.

Fixes:

• Request-level replication of the hot key — fan the key out to many more servers than the normal N, load-balance reads across them. "Hot key splitting" (Twemproxy, Facebook memcache paper). Proxy/client detects request-rate threshold, then randomly picks among K replicas.
• Client-side / edge caching — push a short-TTL copy to the layer nearest the request (app memory, CDN edge, client). Popularity makes even a seconds-long TTL highly effective.
• Request coalescing / single-flight — on concurrent requests for the same key (esp. right after cache expiry), first request fetches + populates, the rest wait and share its result. Kills the "thundering herd on expiry" variant.
• Bounded-load consistent hashing — hard cap: no server holds more than c × avg load (e.g. c=1.25). When the nominal owner is at cap, key goes to next server clockwise, tracked per-request. Caps extra load absorption; does NOT reduce total volume for a viral key. A load-shedding safety valve, not demand reduction — deployed alongside replication/caching, not instead of.

[!important] One-liner vnodes fix uneven placement; hot keys are uneven demand — fix demand with replication/caching/coalescing, and fix placement's failure to absorb demand with bounded-load hashing as a safety net.

10. CDN routing 💡 GOOD TO KNOW

[!tip] Focus tip Key insight to keep: two problems get conflated. "Client → nearest POP" is DNS/anycast (NOT consistent hashing); "within a POP → which cache box" IS consistent hashing.

• Two different problems get lumped together:
  • Client → nearest edge POP: DNS geo-routing or anycast. NOT consistent hashing.
  • Within/across a POP → which cache machine holds this object: THIS is consistent hashing.
• CDN doesn't want every edge server caching the same popular object (wastes memory; N simultaneous origin fetches on cold cache = thundering herd).
• Hash the request key (URL, or URL + cache-relevant headers) onto a ring of cache-server identities. Every server resolves the same key to the same owner → object fetched from origin once, cached on one (or N) machine, subsequent requests route to the warm machine.
• Same mechanism as memcached sharding (ketama). Varnish shard director works this way.
• Operational win: add/remove a cache node → only ~1/N of URL space reassigned; the rest keeps hitting warm cache instead of the whole POP going cold.

11. Sticky sessions on load balancers 💡 GOOD TO KNOW

[!tip] Focus tip Recognize the config knobs (HAProxy/nginx/Envoy) — naming one real setting scores credibility. Don't memorize all three.

• Naive: backend = hash(client_ip_or_session_id) % N. Scaling the backend pool changes N → nearly every client routes to a different backend → mass session loss (logged-out users, dropped carts) right when scaling.
• Consistent-hash affinity: hash the session identifier (source IP, cookie value, header) onto a ring of backends. Scaling remaps only ~1/N of sessions; everyone else stays pinned. Direct LB-layer application of the ring — "keys" = session IDs, "servers" = backends.

Real config knobs:

• HAProxy: balance hash-type consistent + hash <expression> (ketama-style internally).

• nginx: hash $key consistent; in an upstream block (ketama-based).

• Envoy: ring_hash and maglev LB policies — framed as minimal-disruption alternatives to plain hashing.

• Cookie-based affinity — LB inserts a cookie naming the backend. Different solution to the same problem; sidesteps rehashing (mapping stored client-side). Failure mode: if the named backend dies, LB must fall back to another selection, and the client's cookie points at a dead target.

12. How data physically rearranges when a server is added 🎯 FOCUS

[!tip] Focus tip The cache vs persistent storage split is the money insight — drill that. The 5-step Cassandra streaming detail is 💡 good-to-know depth.

Two fundamentally different cases:

Cache (memcached-style) — nothing is migrated:

• New owner simply doesn't have the keys yet → next request is a cache miss → fetched from origin → populated on the new owner.
• Old server's copies go cold, evicted by its own LRU.
• "Migration" is free — just organic cache warming. Only cost: temporary origin-load bump, kept small by vnodes + gradual rollout.

Persistent storage (Cassandra/Dynamo-style) — data actually moves (the new node's copy IS the source of truth):

1. Token assignment — new node picks token(s) (~256 vnodes), randomly or via a balancing allocation algorithm.
2. Range calculation — with vnodes, the new node claims small slices from MANY existing nodes, not one contiguous chunk.
3. Streaming — existing owners stream SSTable data directly over a dedicated streaming protocol (bulk data transfer, separate from client request path — NOT write replay).
4. Invisible until caught up — joining node is JOINING, excluded from reads. Cassandra streams a consistent snapshot + forwards new writes landing in that range during transfer. Flips to NORMAL only after streaming completes, then serves reads. Old owners drop redundant copies via nodetool cleanup (deliberate manual step).
5. Old owners keep serving throughout — no availability gap. Brief window where "logical" owner (ring position) and "actual" owner (who has the data + is live) differ; coordinator routes accordingly.

Single-key walkthrough:

• Key K was on B; new node F's token now sits before K → F should own it.
• Before bootstrap: reads for K → B (F not in owner list).
• During streaming: B sends F its range data incl. K; writes for K go to BOTH B and F (prevents lost writes in the handoff gap).
• After F is NORMAL: K's reads → F; B gets cleanup'd.

Consistency during migration:

• K normally lives on N replicas; only ONE copy's range is moving. The other N-1 replicas are untouched.
• This is why "only ~1/N of keys move" holds at the replica level too — adding one node to an N-way replicated ring perturbs ~1/(num_nodes) of replica assignments, spread thinly.

Anti-entropy safety net:

• Streaming is best-effort; network blips/restarts happen.
• nodetool repair uses Merkle trees to compare a range's data across replicas and re-sync divergence after the fact.
• General pattern: fast/best-effort primary path + slower background reconciliation path. Recurs across distributed systems interviews.

Interview-ready summary of data movement:

1. New node computes which token ranges it now owns.
2. Streams those ranges directly from current owner(s) — not via client-traffic replay.
3. Excluded from serving reads until streaming completes and is verified.
4. Old owner keeps serving throughout — no availability gap.
5. Anti-entropy (Merkle-tree repair) runs afterward as a correctness backstop, decoupled from the time-critical bootstrap.

---

Focus summary — where to spend your reps

---

Related

• [[Caching & Redis]] — Redis Cluster uses consistent hashing
• [[Distributed Systems Concepts]] — partitioning, replication
• [[Message Queues & Kafka]] — Kafka partition assignment
• [[System Design/Problem Designs/Design a URL shortener]] — base62 encoding (different sharding)