Consistent Hashing

// The problem with naive modular hashing
function naiveHash(key: string, numServers: number): number {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 31 + key.charCodeAt(i)) & 0x7fffffff;
  }
  return hash % numServers;
}

// With 4 servers
const server4 = naiveHash('user:123', 4);  // e.g., server 2

// Add a 5th server - almost ALL keys remap!
const server5 = naiveHash('user:123', 5);  // e.g., server 3 (DIFFERENT!)

// With N keys and going from K to K+1 servers,
// approximately (K/(K+1)) * N keys need to move.
// For 4 -> 5 servers: 80% of all keys are remapped!

import crypto from 'crypto';

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

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

  // Generate a numeric hash from a string
  private hash(key: string): number {
    const md5 = crypto.createHash('md5').update(key).digest('hex');
    // Use first 8 hex characters for a 32-bit hash
    return parseInt(md5.substring(0, 8), 16);
  }

  // Add a node (server) to the ring
  addNode(node: T): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualKey = `${String(node)}:vnode${i}`;
      const hashValue = this.hash(virtualKey);
      this.ring.set(hashValue, node);
      this.sortedKeys.push(hashValue);
    }
    // Keep sorted for binary search
    this.sortedKeys.sort((a, b) => a - b);
  }

  // Remove a node from the ring
  removeNode(node: T): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualKey = `${String(node)}:vnode${i}`;
      const hashValue = this.hash(virtualKey);
      this.ring.delete(hashValue);
      this.sortedKeys = this.sortedKeys.filter(k => k !== hashValue);
    }
  }

  // Find the node responsible for a given key
  getNode(key: string): T | undefined {
    if (this.sortedKeys.length === 0) return undefined;

    const hashValue = this.hash(key);

    // Binary search for the first node clockwise from the hash
    let low = 0;
    let high = this.sortedKeys.length - 1;

    // If hash is beyond the last node, wrap around to the first
    if (hashValue > this.sortedKeys[high]) {
      return this.ring.get(this.sortedKeys[0]);
    }

    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (this.sortedKeys[mid] < hashValue) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    return this.ring.get(this.sortedKeys[low]);
  }

  // Get N nodes for replication (for when you want to store copies on multiple servers)
  getNodes(key: string, count: number): T[] {
    if (this.sortedKeys.length === 0) return [];

    const nodes: T[] = [];
    const seen = new Set<string>();
    const hashValue = this.hash(key);

    let startIndex = this.sortedKeys.findIndex(k => k >= hashValue);
    if (startIndex === -1) startIndex = 0;

    let index = startIndex;
    while (nodes.length < count && seen.size < this.ring.size) {
      const node = this.ring.get(this.sortedKeys[index])!;
      const nodeKey = String(node);
      if (!seen.has(nodeKey)) {
        nodes.push(node);
        seen.add(nodeKey);
      }
      index = (index + 1) % this.sortedKeys.length;
    }

    return nodes;
  }
}

// Usage example
const ring = new ConsistentHash<string>(150);

// Add cache servers
ring.addNode('cache-server-1');
ring.addNode('cache-server-2');
ring.addNode('cache-server-3');

// Route keys to servers
console.log(ring.getNode('user:1001'));  // -> "cache-server-2"
console.log(ring.getNode('user:1002'));  // -> "cache-server-1"
console.log(ring.getNode('user:1003'));  // -> "cache-server-3"

// Add a new server - only ~1/4 of keys will be remapped
ring.addNode('cache-server-4');

// Get 3 replicas for redundancy
const replicas = ring.getNodes('user:1001', 3);
console.log(replicas); // -> ["cache-server-2", "cache-server-3", "cache-server-1"]