Consistent Hashing for a Cache Tier

Hash each node to many points on a ring, called virtual nodes, and keep the points sorted. A key belongs to the first point at or after its own hash, wrapping around, which a binary search finds in O(log v) for v points. Adding or removing a node moves only the keys in that node's arcs, about 1/n of them.

hardPattern: Binary search·From Devana's Microsoft question set

Problem

A cache tier spreads keys across nodes. With hash(key) % n, adding one node changes n and moves almost every key, so the whole cache goes cold at once. Implement consistent hashing instead, so membership changes move as few keys as possible.

Write a class ConsistentHash(nodes, virtual_nodes=150) with get_node(key), add_node(node) and remove_node(node). Explain what fraction of keys moves when a node joins or leaves, and how you keep the load even.

class ConsistentHash:
    def __init__(self, nodes: list[str], virtual_nodes: int = 150): ...
    def get_node(self, key: str) -> str | None: ...
    def add_node(self, node: str) -> None: ...
    def remove_node(self, node: str) -> None: ...

This is one of Devana's own questions, written in the style of Microsoft's interviews. It is not a question leaked from Microsoft, and Devana is not affiliated with Microsoft.

Constraints

• A position on the ring is the first 32 bits of the MD5 of a label: node#i for virtual node i, the key itself for a key.
• A key maps to the first virtual node at or after its position, wrapping to the start of the ring.
• Lookups are O(log v) for v virtual nodes in total.
• Adding a node may only move keys onto that node; removing one may only move that node's own keys.
• With no nodes, get_node returns None.

Examples

Input:  ring = ConsistentHash(["a", "b", "c"])
        then add_node("d") and look up 1,000 keys again
Output: about a quarter of the keys move, every one of them to d

Input:  ConsistentHash(["a", "b", "c"], virtual_nodes=1)
Output: a lopsided split

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Open with the failure of modulo hashing and put a number on it: going from 3 to 4 nodes moves about three keys in four. Then describe the ring, the binary search for a key's owner, and why only the new node's arcs move. Finish with virtual nodes as the fix for balance, and say how you would measure it.

Solution

Python

import hashlib
from bisect import bisect_left

def ring_position(label):
    return int(hashlib.md5(label.encode()).hexdigest()[:8], 16)

class ConsistentHash:
    def __init__(self, nodes, virtual_nodes=150):
        self.virtual_nodes = virtual_nodes
        self.nodes = set(nodes)
        self._rebuild()

    def _rebuild(self):
        ring = sorted(
            (ring_position(f"{node}#{i}"), node)
            for node in self.nodes
            for i in range(self.virtual_nodes)
        )
        self.positions = [position for position, _ in ring]
        self.owners = [node for _, node in ring]

    def add_node(self, node):
        self.nodes.add(node)
        self._rebuild()

    def remove_node(self, node):
        self.nodes.discard(node)
        self._rebuild()

    def get_node(self, key):
        if not self.positions:
            return None
        # The first virtual node at or after the key, wrapping past the end.
        i = bisect_left(self.positions, ring_position(key))
        return self.owners[i % len(self.owners)]

JavaScript (Node.js)

const crypto = require("node:crypto");

function ringPosition(label) {
  return parseInt(crypto.createHash("md5").update(label).digest("hex").slice(0, 8), 16);
}

class ConsistentHash {
  constructor(nodes, virtualNodes = 150) {
    this.virtualNodes = virtualNodes;
    this.nodes = new Set(nodes);
    this.rebuild();
  }

  rebuild() {
    const ring = [];
    for (const node of this.nodes) {
      for (let i = 0; i < this.virtualNodes; i++) ring.push([ringPosition(node + "#" + i), node]);
    }
    ring.sort((p, q) => p[0] - q[0] || (p[1] < q[1] ? -1 : p[1] > q[1] ? 1 : 0));
    this.positions = ring.map(([position]) => position);
    this.owners = ring.map(([, node]) => node);
  }

  addNode(node) {
    this.nodes.add(node);
    this.rebuild();
  }

  removeNode(node) {
    this.nodes.delete(node);
    this.rebuild();
  }

  getNode(key) {
    if (this.positions.length === 0) return null;
    // The first virtual node at or after the key, wrapping past the end.
    const target = ringPosition(key);
    let lo = 0, hi = this.positions.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.positions[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return this.owners[lo % this.owners.length];
  }
}

Both versions are tested against the same cases, including every example on this page.

• Rebuilding the sorted ring costs O(v log v), which is fine because nodes join and leave rarely while lookups happen constantly. For frequent changes, insert and remove positions in place instead.
• MD5 is used for spread, not security. Any well-mixed hash works, as long as every client uses the same one.
• Equal positions are rare; when they happen, they are ordered by node name, so every client builds the same ring.

Follow-up questions

Common mistakes

• Using hash(key) % n and calling it consistent hashing.
• Forgetting the wrap-around, so keys hashing past the last point have no owner.
• Using Python's built-in hash for strings, which is randomized per process, so two clients disagree about where keys live.
• One point per node, and assuming the load is even.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Realign Drifting Subtitles: Binary search for the anchor segment around each time, then interpolate along it.
• Design a URL Shortener at Scale: Key generation, a cache-first redirect path, and analytics kept off the hot path.
• Binary search: the pattern guide, with more practice questions.