Consistent Hashing

The Problem with Naive Hashing

The simplest way to distribute keys across N nodes is `node = hash(key) % N`. This works fine when N is fixed. But when you add or remove a node, N changes, and almost every key maps to a different node. If you have 1 million keys and add one node (N becomes N+1), nearly all keys must be remapped — causing a massive cache miss storm or data reshuffling that can take hours.

The Hash Ring

Consistent hashing solves this by arranging the hash space as a ring (typically 0 to 2^32 - 1 or 0 to 2^64 - 1). Both nodes and keys are hashed onto this ring. Each key is owned by the first node clockwise from the key's position on the ring. When a node is added or removed, only the keys between the new/removed node and its predecessor need to be remapped.

Adding node D at hash=250: only keys between hash=200 (Node B) and hash=250 (Node D) need to move from Node C to Node D. All other keys are unaffected. In a 4-node ring, adding one node remaps only 1/4 of keys on average, instead of nearly all keys with modulo hashing.

Virtual Nodes (Vnodes)

A naive consistent hash ring has two problems: uneven load distribution (nodes land at non-uniform positions on the ring) and hot spots when a node fails (all its keys move to one successor). Virtual nodes solve both: each physical node is placed at multiple positions on the ring (e.g., 256 positions in Cassandra). These virtual positions are spread around the ring, ensuring even distribution.

• Even load: with 256 vnodes per node, load variance is much smaller than with 1 position per node.
• Graceful failure: when a node fails, its 256 virtual positions redistribute their keys across many other nodes — not just one successor.
• Heterogeneous hardware: more powerful nodes can be assigned more virtual positions to carry proportionally more load.

class ConsistentHashRing {
  private ring: Map<number, string> = new Map(); // hash -> nodeId
  private sortedHashes: number[] = [];
  private replicationFactor: number;
  private vnodes: number;

  constructor(replicationFactor = 3, vnodes = 256) {
    this.replicationFactor = replicationFactor;
    this.vnodes = vnodes;
  }

  addNode(nodeId: string): void {
    for (let i = 0; i < this.vnodes; i++) {
      const virtualKey = `${nodeId}#${i}`;
      const hash = this.hash(virtualKey);
      this.ring.set(hash, nodeId);
      this.sortedHashes.push(hash);
    }
    this.sortedHashes.sort((a, b) => a - b);
  }

  getNode(key: string): string {
    const hash = this.hash(key);
    // Find first node clockwise from key's hash
    const idx = this.sortedHashes.findIndex(h => h >= hash);
    const ringIdx = idx === -1 ? 0 : idx; // wrap around
    return this.ring.get(this.sortedHashes[ringIdx])!;
  }

  getReplicaNodes(key: string): string[] {
    // Returns replicationFactor distinct nodes for this key
    const hash = this.hash(key);
    const seen = new Set<string>();
    const nodes: string[] = [];
    let idx = this.sortedHashes.findIndex(h => h >= hash);
    if (idx === -1) idx = 0;

    while (nodes.length < this.replicationFactor) {
      const nodeId = this.ring.get(this.sortedHashes[idx % this.sortedHashes.length])!;
      if (!seen.has(nodeId)) { seen.add(nodeId); nodes.push(nodeId); }
      idx++;
    }
    return nodes;
  }

  private hash(key: string): number {
    // In production: use MurmurHash3 or xxHash
    let h = 0;
    for (const c of key) h = Math.imul(31, h) + c.charCodeAt(0) | 0;
    return Math.abs(h);
  }
}

Real-World Usage