How do you implement a consistent hash ring with virtual nodes?

Question and scope

Implement a ring for routing string keys to physical nodes. The API is addNode(nodeId, weight), removeNode(nodeId), and getNode(key). A node receives weight × V virtual tokens, where V is a configured base count. Use a deterministic 64-bit hash abstraction, keep collisions safe, and return the first live token clockwise from the key. If the ring is empty, getNode returns no node.

This is a coding problem, not a full membership or replication service. Membership updates are assumed to be serialized by the caller. The solution must explain why a node join or removal changes only nearby key intervals, and where that property stops helping, such as a hot key or a badly chosen hash.

What the interviewer is testing

PracHub records this as a DoorDash Software Engineer technical-screen question with addNode, removeNode, and getNode, virtual-node balancing, collision handling, and complexity analysis. A recent public DoorDash interview record also describes fixing a round-robin load balancer and implementing consistent hashing.

The signal is an executable data-structure design: sorted lookup, stable token identity, duplicate-safe updates, a clear invariant, and tests for wrap-around and membership changes. MIT's original paper defines the useful properties as balance and monotonicity: assignments should stay reasonably even, and adding a bucket should not remap keys that can remain on their old bucket.

Clarifying questions before answering

1. Are node IDs unique and stable across restarts? Stable IDs are required to remove exactly the tokens that belong to one physical node.
2. Is weight an integer? This answer assumes a positive integer; fractional capacity needs a normalized token budget.
3. Are membership updates concurrent with lookups? If yes, publish an immutable snapshot or add a read/write lock; the code below assumes serialized updates.
4. Is replication required? The basic API returns one owner. Returning R distinct successors is a follow-up with failure and duplicate-token rules.
5. What hash function is available? Treat it as deterministic and uniform for the exercise; production choices need collision and adversarial-input review.

30-second answer framework

“I store (token, virtualNodeId, physicalNodeId) records in sorted order. Adding a node inserts weight × V deterministic tokens; removing it deletes exactly those tokens. Lookup hashes the key, binary-searches the first token at or after it, and wraps to index zero. The invariant is that every token maps to one live physical node and each key owns the first clockwise token. Lookup is O(log M), updates are O(V·weight·log M), and I test collisions, wrap-around, duplicate updates, removal, empty rings, and key remapping.”

Step-by-step deep answer

1. Choose the representation and invariant

Let M be the number of virtual tokens. Keep a sorted array of records and a map from physical node ID to its generated token records. The sorted array makes lookup a lower-bound search; the reverse map makes removal precise instead of scanning for a matching prefix.

The invariant is:

1. Tokens are sorted by (hash, tokenId).
2. Every token references one registered physical node.
3. A key maps to the first token clockwise, wrapping at the ring boundary.
4. A physical node's token set is generated only from its stable ID, index, and configured count.

The secondary tokenId tie-breaker makes equal hash values deterministic. It does not pretend collisions are impossible.

2. Generate virtual tokens deterministically

For node n and virtual index i, hash the bytes of n + "#" + i. Generate weight × V indices. A higher weight therefore owns more intervals in expectation. Use a fixed hash implementation and persist V and weight policy with the ring snapshot; changing them silently remaps keys.

An implementation can use a balanced tree for O(log M) insertion and deletion. An interview-friendly sorted array keeps the invariant visible; batch membership updates can rebuild the array once rather than shifting it repeatedly.

3. Implement lookup and updates

from bisect import bisect_left

class ConsistentHashRing:
    def __init__(self, virtuals_per_weight, hash64):
        self.v = virtuals_per_weight
        self.hash64 = hash64
        self.tokens = []  # (hash, token_id, node_id)
        self.by_node = {}

    def add_node(self, node_id, weight=1):
        if weight <= 0 or node_id in self.by_node:
            raise ValueError("invalid or duplicate node")
        owned = []
        for i in range(weight * self.v):
            token_id = f"{node_id}#{i}"
            owned.append((self.hash64(token_id), token_id, node_id))
        self.by_node[node_id] = owned
        self.tokens.extend(owned)
        self.tokens.sort()

    def remove_node(self, node_id):
        owned = self.by_node.pop(node_id, None)
        if owned is None:
            return False
        owned_ids = {token_id for _, token_id, _ in owned}
        self.tokens = [t for t in self.tokens if t[1] not in owned_ids]
        return True

    def get_node(self, key):
        if not self.tokens:
            return None
        h = self.hash64(key)
        i = bisect_left(self.tokens, (h, "", ""))
        return self.tokens[i if i < len(self.tokens) else 0][2]

The code treats a duplicate node as a caller error and an absent removal as a no-op. In production, updates would usually build a new snapshot and publish it atomically so readers never observe a half-updated ring.

4. Derive complexity and remapping behavior

With M = V × sum(weight), lookup is O(log M) and O(1) extra space per call. The array implementation's insertion and removal are O(M + K log M) due to sorting and filtering, where K is the changed node's token count; a balanced tree reduces updates to O(K log M). Memory is O(M).

When a node is added, only keys in the intervals immediately preceding its virtual tokens move to it. When a node is removed, those intervals move to their next clockwise owners. This is the monotonicity advantage over modulo hashing, where changing N remaps most keys. Virtual nodes reduce variance but cannot cure a single hot key or a skewed workload.

High-quality sample answer

“I represent the ring as sorted (hash, tokenId, nodeId) records plus a map from node ID to its records. addNode creates deterministic weight × V virtual tokens; removeNode deletes exactly those records. getNode uses lower-bound search and wraps around. The invariant is that every key owns the first live token clockwise, with (hash, tokenId) resolving collisions deterministically. Lookup is O(log M); a sorted array makes updates O(M + K log M), while a tree can make them O(K log M). I would test empty and one-node rings, wrap-around, duplicate IDs, collisions, removal, weighted distribution, and the fraction of keys remapped after membership changes.”

Common mistakes

• Use hash(key) % N → changing node count remaps most keys → search the next clockwise token.
• Assume collisions cannot happen → equal hashes produce unstable ownership → tie-break by deterministic token ID.
• Generate random tokens on every restart → all keys move unexpectedly → derive tokens from stable node ID and index.
• Remove by node-name prefix only → similar IDs can delete the wrong records → keep an explicit reverse map and token IDs.
• Claim virtual nodes eliminate hotspots → a single popular key still targets one owner → add replication, load-aware routing, or hot-key treatment as a separate requirement.
• Ignore empty and duplicate cases → lookup or update invariants fail at boundaries → define return and error behavior before coding.

Follow-ups and responses

How would you return three replicas?

Walk clockwise from the owner and collect distinct physical node IDs until three are found. Skip additional virtual tokens belonging to an already selected node; if fewer than three live nodes exist, return the available set and an explicit shortfall.

How do you test distribution rather than one example?

Generate a fixed corpus of keys, measure each node's share and the maximum-to-minimum ratio, then repeat after adding and removing a node. Keep the hash seed fixed so regressions are reproducible.

What if a node's capacity changes?

Remove its old token set, add a new set using the new weight, and publish one snapshot. Expect only intervals adjacent to changed tokens to move, but monitor load during the transition.

When is modulo hashing simpler?

If membership is fixed or a full rebalance is acceptable, modulo hashing is shorter and often faster. Consistent hashing earns its complexity when membership changes and remapping cost matters.