Consistent Hashing

Consistent hashing minimizes key redistribution when nodes are added or removed from a distributed system.

The Ring Concept

        0/360°
           │
     ┌─────┴─────┐
    /             \
   │    Node A    │  ← 45°
   │      ●       │
   │              │
───┤              ├─── 90°
   │      ●       │
   │    Node B    │  ← 120°
   │              │
   │      ●       │
    \   Node C   /   ← 200°
     └─────┬─────┘
           │
         180°

Keys are assigned to the first node clockwise from their hash position.

Basic Implementation

import crypto from 'crypto';

class ConsistentHash {
  private ring: Map = new Map();
  private sortedKeys: number[] = [];
  private virtualNodes: number;

  constructor(virtualNodes: number = 150) {
    this.virtualNodes = virtualNodes;
  }

  private hash(key: string): number {
    const hash = crypto.createHash('md5').update(key).digest('hex');
    return parseInt(hash.substring(0, 8), 16);
  }

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

  removeNode(node: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualKey = `${node}#${i}`;
      const hash = this.hash(virtualKey);
      this.ring.delete(hash);
      this.sortedKeys = this.sortedKeys.filter(k => k !== hash);
    }
  }

  getNode(key: string): string {
    if (this.ring.size === 0) {
      throw new Error('No nodes in the ring');
    }

    const hash = this.hash(key);

    // Find the first node clockwise from the key's hash
    for (const nodeHash of this.sortedKeys) {
      if (nodeHash >= hash) {
        return this.ring.get(nodeHash)!;
      }
    }

    // Wrap around to first node
    return this.ring.get(this.sortedKeys[0])!;
  }

  // Get N nodes for replication
  getNodes(key: string, count: number): string[] {
    const nodes: string[] = [];
    const hash = this.hash(key);
    const seen = new Set();

    // Find starting position
    let startIdx = this.sortedKeys.findIndex(k => k >= hash);
    if (startIdx === -1) startIdx = 0;

    // Collect unique nodes
    for (let i = 0; i < this.sortedKeys.length && nodes.length < count; i++) {
      const idx = (startIdx + i) % this.sortedKeys.length;
      const node = this.ring.get(this.sortedKeys[idx])!;

      if (!seen.has(node)) {
        seen.add(node);
        nodes.push(node);
      }
    }

    return nodes;
  }
}

// Usage
const hash = new ConsistentHash(100);
hash.addNode('server-1');
hash.addNode('server-2');
hash.addNode('server-3');

console.log(hash.getNode('user:123'));  // server-2
console.log(hash.getNode('user:456'));  // server-1
console.log(hash.getNodes('user:123', 2)); // ['server-2', 'server-3']

// Adding a new node only redistributes ~1/N of keys
hash.addNode('server-4');
console.log(hash.getNode('user:123'));  // May still be server-2 or moved to server-4

Consistent Hashing Algorithm

Consistent Hashing Algorithm

Consistent Hashing

The Ring Concept

Basic Implementation