Hashing Consistente

El Problema con el Hashing Básico

En un sistema distribuido, frecuentemente necesitas asignar datos a servidores. El enfoque ingenuo es usar una función hash simple: servidor = hash(clave) % número_de_servidores. Esto funciona bien cuando el número de servidores es fijo, pero falla catastróficamente cuando se agregan o eliminan servidores.

Supón que tienes 4 servidores y 100,000 claves distribuidas usando hash(clave) % 4. Si agregas un quinto servidor, la fórmula se convierte en hash(clave) % 5, y la gran mayoría de las claves se mapearán a un servidor diferente. Para un caché distribuido, esto significa que casi cada elemento cacheado se convierte en un miss, causando una "estampida" masiva hacia la base de datos subyacente.

// 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!

Cómo Funciona el Hashing Consistente

El hashing consistente, introducido por David Karger et al. en 1997, resuelve este problema usando un anillo de hash en lugar de aritmética modular. Así es como funciona:

1. Crear un anillo de hash: Imagina el espacio de salida de tu función hash (ej. 0 a 2^32-1) organizado en un círculo (anillo).
2. Colocar servidores en el anillo: Hashea el identificador de cada servidor (ej. dirección IP o nombre) y colócalo en el anillo en la posición resultante.
3. Colocar claves en el anillo: Hashea cada clave de datos y colócala en el anillo.
4. Asignar claves a servidores: Cada clave se asigna al primer servidor encontrado al caminar en sentido horario desde la posición de la clave en el anillo.

Nodos Virtuales (Vnodes)

Un anillo de hash consistente básico tiene un problema: con un pequeño número de servidores, la distribución de claves puede ser muy desigual. Un servidor podría ser responsable de un arco mucho más grande del anillo que otro, recibiendo desproporcionadamente más datos y tráfico.

Los nodos virtuales resuelven esto mapeando cada servidor físico a múltiples posiciones en el anillo. En lugar de colocar "Servidor A" en un punto, colocas "Servidor A - vnode 1", "Servidor A - vnode 2", "Servidor A - vnode 3", etc. en diferentes posiciones. Esto distribuye la responsabilidad de cada servidor a través de múltiples arcos del anillo, llevando a una distribución mucho más uniforme.

• Con 100-200 nodos virtuales por servidor físico, la distribución se vuelve muy uniforme.
• Los nodos virtuales también facilitan el rebalanceo: cuando se agrega un nuevo servidor físico, sus nodos virtuales toman pequeñas porciones del anillo de múltiples servidores existentes, en lugar de un solo fragmento grande de un servidor.
• Los servidores con más capacidad pueden tener más nodos virtuales asignados, dándoles una proporción mayor del anillo.

Implementación Completa en TypeScript

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');
    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);
    }
    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 (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]);
  }
}

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

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

console.log(ring.getNode('user:1001'));  // -> "cache-server-2"
console.log(ring.getNode('user:1002'));  // -> "cache-server-1"

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

Casos de Uso del Hashing Consistente

1. Cachés Distribuidos

La motivación original del hashing consistente. Sistemas como Memcached usan hashing consistente en sus bibliotecas de cliente para determinar qué servidor de caché almacena cada clave. Cuando se agrega o elimina un servidor de caché, solo una fracción de las claves se remapea, previniendo una estampida de caché.

2. Balanceadores de Carga

Algunos balanceadores de carga usan hashing consistente para asegurar que las solicitudes del mismo cliente siempre vayan al mismo servidor backend (afinidad de sesión) sin sesiones sticky. Nginx soporta hashing consistente con su directiva hash.

3. Sharding de Base de Datos

El hashing consistente se usa para distribuir datos entre shards de base de datos en sistemas como Apache Cassandra y Amazon DynamoDB. Cassandra usa un anillo de hash consistente donde a cada nodo se le asigna un rango de valores de token.

4. Redes de Distribución de Contenido

Los CDNs usan hashing consistente para determinar qué servidor edge cachea qué contenido. Cuando un servidor edge se cae, su contenido se redistribuye a servidores vecinos en el anillo, minimizando los cache misses.