Consistent hashing

Overview

Consistent hashing assigns keys to servers so that adding or removing a server moves only a small fraction of keys. With naive hash(key) % N, changing N remaps almost every key; with consistent hashing, only about 1/N of keys move.

It is used by distributed caches, Dynamo-style databases such as Cassandra and DynamoDB, CDNs, and load balancers that need cache affinity.

When to use it

• Data or cache entries are partitioned across nodes, and nodes are added or removed.
• Remapping many keys would cause a storm of cache misses or data movement.
• You need each key to go to the same node consistently without a central lookup table.

Where it shows up in interviews

Where it is used in real software

Key terms

Hash ring

The hash output space (for example 0 to 2^32 - 1) arranged in a circle.

Node position

hash(nodeId) places each server on the ring.

Key ownership

A key belongs to the first node found clockwise from hash(key).

Virtual nodes

Each physical server appears at many ring positions to spread load evenly.

How it works

1. 1
   Hash the servers

   Place each server on the ring at hash(serverId). With virtual nodes, place it at hash(serverId#0), hash(serverId#1), and so on.

2. 2
   Hash the key

   Compute hash(key) to find its position on the ring.

3. 3
   Walk clockwise

   The first server position greater than or equal to the key's hash owns it; wrap to the start if needed.

4. 4
   Add a server

   It takes over only the keys between its position and the previous node counter-clockwise.

5. 5
   Remove a server

   Its keys move to the next node clockwise; all other keys stay put.

Keys that move when going from 4 to 5 servers

1,000,000 cached keys

Modulo hashing changes the owner of a key whenever N changes. Consistent hashing only moves the keys the new node should now own, which keeps cache hit rates high during scaling.

Implementation

1import { createHash } from "node:crypto";2 3const hash = (value: string) =>4  createHash("md5").update(value).digest().readUInt32BE(0);5 6class ConsistentHashRing {7  private ring: { point: number; node: string }[] = [];8 9  constructor(private virtualNodes = 150) {}10 11  addNode(node: string) {12    for (let i = 0; i < this.virtualNodes; i++) {13      this.ring.push({ point: hash(`${node}#${i}`), node });14    }15    this.ring.sort((a, b) => a.point - b.point);16  }17 18  removeNode(node: string) {19    this.ring = this.ring.filter((entry) => entry.node !== node);20  }21 22  getNode(key: string): string {23    const target = hash(key);24    // Binary search for the first point >= target.25    let low = 0, high = this.ring.length;26    while (low < high) {27      const mid = (low + high) >> 1;28      if (this.ring[mid].point < target) low = mid + 1;29      else high = mid;30    }31    return this.ring[low % this.ring.length].node; // wrap around32  }33}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• No virtual nodes.

  Fix: With few servers, random ring positions create very uneven ranges. Use many virtual nodes.

• Using a non-uniform hash like a string length or language hashCode.

  Fix: Use a well-distributed hash such as MurmurHash, xxHash, or MD5 truncated.

Interview questions

Practice problems