Q6: Consistent Hashing and Virtual Nodes: Mitigating Hot-Spots and Rebalancing. - System Design (50 Qs)

In Simple Words: In standard modulo hashing (hash(key) % N), adding or removing a single server forces almost 100% of keys to be relocated to new servers, causing catastrophic cache stampedes and database overloads. Consistent Hashing maps both servers and data keys onto a circular $2^{32}-1$ hash ring. A key is assigned to the first server encountered moving clockwise. When a node is added or removed, only $K/N$ keys need to be remapped on average ($K$ = total keys, $N$ = total nodes).

Virtual Nodes (Vnodes): Physical servers vary in hardware performance and can create unbalanced clusters. By mapping each physical server to 100–300 Virtual Nodes distributed evenly around the ring:

Load is distributed evenly across all physical servers.
When a physical server fails, its load is split across all remaining servers rather than overwhelming its single clockwise neighbor.

typescript

import crypto from 'crypto';

export class ConsistentHashRing {
  private ring = new Map<number, string>();
  private sortedKeys: number[] = [];
  private replicas: number;

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

  private hash(val: string): number {
    return crypto.createHash('md5').update(val).digest().readUInt32BE(0);
  }

  public addServer(server: string): void {
    for (let i = 0; i < this.replicas; i++) {
      const vnodeKey = this.hash(`${server}#vnode-${i}`);
      this.ring.set(vnodeKey, server);
      this.sortedKeys.push(vnodeKey);
    }
    this.sortedKeys.sort((a, b) => a - b);
  }

  public getServer(key: string): string | null {
    if (this.sortedKeys.length === 0) return null;
    const keyHash = this.hash(key);

    // Binary search clockwise on ring
    let low = 0, high = this.sortedKeys.length - 1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.sortedKeys[mid] >= keyHash) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }

    const targetIdx = low >= this.sortedKeys.length ? 0 : low;
    return this.ring.get(this.sortedKeys[targetIdx]) || null;
  }
}