¿Cómo funciona el hashing consistente, y por qué los cachés distribuidos como Memcached/Redis Cluster lo necesitan en lugar de un simple hashing por módulo?

#Por qué el hashing por módulo se rompe cuando cambia el clúster

La forma ingenua de repartir claves entre N servidores de caché es servidor = hash(clave) % N. Es rápida, es uniforme (asumiendo una función de hash decente) y funciona bien mientras N nunca cambie. En el momento en que agregás o quitás un solo servidor — escalando horizontalmente, un nodo que se cae, un rolling deploy que reemplaza una instancia — N cambia, y hash(clave) % N se recalcula a un servidor distinto para casi todas las claves del sistema, no sólo para las que "pertenecían" al nodo que agregaste o quitaste.

Concretamente: con 4 servidores, hash_clave % 4 y hash_clave % 5 casi no coinciden en nada. Una clave que mapeaba al servidor 2 de 4 no tiene ninguna razón particular para seguir mapeando al servidor 2 de 5. El efecto práctico es una estampida de caché — en el instante en que redimensionás el clúster, la abrumadora mayoría de tu working set queda "en el servidor equivocado", cada lectura de caché se convierte en un miss, y todo ese tráfico cae de golpe sobre la base de datos, justo en el peor momento posible: cuando estabas intentando agregar capacidad.

#Hashing consistente: sólo se mueve la porción afectada

El hashing consistente resuelve esto ubicando tanto a los servidores como a las claves en el mismo espacio circular — típicamente el rango de salida de una función de hash de 32 o 64 bits, imaginado como un anillo que va de 0 a 2^32 - 1 y vuelve a 0. Cada servidor ocupa uno o más puntos de ese anillo. Para encontrar al dueño de una clave, se hashea la clave dentro del mismo espacio y se recorre el anillo en sentido horario hasta encontrar la primera posición ocupada por un servidor — ese servidor es el dueño.

Cuando se agrega un servidor, éste reclama un único arco del anillo, y sólo las claves que caen en ese arco se mudan hacia él — todo lo demás conserva a su dueño de siempre. Cuando se quita un servidor, sólo las claves que le pertenecían se mudan, hacia su vecino en sentido horario. En ambos casos, la cantidad de claves que se mueve es proporcional a 1/N del total, no "casi todas". Esa es toda la propuesta de valor: una disrupción acotada y predecible en lugar de una reorganización casi total.

Recorriendo el anillo en sentido horario (hash creciente, dando la vuelta desde 2^32-1 hasta 0): session:99 (hash 5) tiene como primer nodo en sentido horario al Nodo A (15) — así que el Nodo A es su dueño. user:42 (20) pertenece al siguiente nodo en sentido horario, el Nodo B (25). user:17 (40) pertenece al Nodo C (50). order:8 (60) da toda la vuelta al anillo sin encontrar ningún nodo hasta llegar de nuevo al Nodo A (15), así que también le pertenece a él.

#Nodos virtuales: corrigiendo la carga despareja

Un anillo con apenas 3 a 5 servidores físicos, cada uno hasheado a un único punto, distribuye la carga de forma muy despareja — las longitudes de arco entre nodos consecutivos son esencialmente aleatorias, así que un servidor podría terminar con el 50% del espacio de claves y otro con el 5%. La solución son los nodos virtuales: en lugar de hashear cada servidor físico una sola vez, se lo hashea muchas veces bajo etiquetas distintas (cache-a#0, cache-a#1, … cache-a#149) y se colocan todos esos puntos en el anillo. Cada nodo físico ahora posee muchos arcos pequeños y dispersos en vez de uno grande, y la ley de los grandes números empieza a jugar a favor — con 100 a 200 nodos virtuales por nodo físico, la desviación estándar de la carga entre servidores cae a apenas unos pocos puntos porcentuales en lugar de estar dominada por el azar.

Los nodos virtuales tienen un segundo beneficio: cuando se agrega o quita un nodo físico, sus nodos virtuales están dispersos por todo el anillo, así que las claves que se mueven se toman parejo de todos los nodos sobrevivientes en lugar de descargar todo el peso del rebalanceo sobre un vecino con mala suerte.

#Implementando un anillo con nodos virtuales

Ajustar líneas largas
import { createHash } from "crypto";

function hash32(input: string): number {
  const digest = createHash("md5").update(input).digest();
  return digest.readUInt32BE(0); // los primeros 4 bytes como entero sin signo de 32 bits
}

class AnilloDeHashConsistente {
  private anillo = new Map<number, string>();   // posición en el anillo -> id del nodo físico
  private posicionesOrdenadas: number[] = [];
  private readonly nodosVirtualesPorNodo: number;

  constructor(nodosVirtualesPorNodo = 150) {
    this.nodosVirtualesPorNodo = nodosVirtualesPorNodo;
  }

  agregarNodo(nodeId: string): void {
    for (let i = 0; i < this.nodosVirtualesPorNodo; i++) {
      const posicion = hash32(`${nodeId}#${i}`);
      this.anillo.set(posicion, nodeId);
    }
    this.reconstruirIndice();
  }

  quitarNodo(nodeId: string): void {
    for (let i = 0; i < this.nodosVirtualesPorNodo; i++) {
      const posicion = hash32(`${nodeId}#${i}`);
      this.anillo.delete(posicion);
    }
    this.reconstruirIndice();
  }

  // Devuelve el nodo físico dueño de `key`.
  obtenerNodo(key: string): string | undefined {
    if (this.posicionesOrdenadas.length === 0) return undefined;
    const objetivo = hash32(key);

    // Búsqueda binaria de la primera posición del anillo >= objetivo (el sucesor en sentido horario).
    let lo = 0;
    let hi = this.posicionesOrdenadas.length - 1;
    if (objetivo > this.posicionesOrdenadas[hi]) {
      return this.anillo.get(this.posicionesOrdenadas[0]); // da la vuelta al inicio del anillo
    }
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.posicionesOrdenadas[mid] < objetivo) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    return this.anillo.get(this.posicionesOrdenadas[lo]);
  }

  private reconstruirIndice(): void {
    this.posicionesOrdenadas = Array.from(this.anillo.keys()).sort((a, b) => a - b);
  }
}

// --- uso ---
const anillo = new AnilloDeHashConsistente(150);
anillo.agregarNodo("cache-a");
anillo.agregarNodo("cache-b");
anillo.agregarNodo("cache-c");

console.log(anillo.obtenerNodo("user:42")); // p.ej. "cache-b"
console.log(anillo.obtenerNodo("user:17")); // p.ej. "cache-a"

// Agregar un cuarto nodo sólo remapea aproximadamente 1/4 de las claves —
// el otro 3/4 sigue resolviendo al mismo nodo de siempre.
anillo.agregarNodo("cache-d");

Cada búsqueda cuesta O(log(N * V)), donde N es la cantidad de nodos físicos y V los nodos virtuales por nodo — una búsqueda binaria sobre un arreglo ordenado de posiciones del anillo. En producción, esta estructura suele mantenerse del lado del cliente, como hacen bibliotecas de Memcached del estilo de libketama (ya que los servidores de Memcached no tienen ninguna noción unos de otros), o se usa una biblioteca probada en producción en lugar de programar a mano la matemática de MD5 — pero la mecánica de arriba es exactamente lo que esas bibliotecas hacen por dentro.

#Redis Cluster: un mecanismo relacionado pero distinto

Vale la pena ser precisos acá, porque es un punto de confusión frecuente en entrevistas. Memcached no tiene ningún protocolo de clustering — los servidores no se conocen entre sí, así que el hashing consistente se implementa enteramente en la biblioteca cliente, que es libre de usar un anillo con nodos virtuales exactamente como el de arriba. Redis Cluster, en cambio, no usa un anillo de hash continuo. Divide el espacio de claves en 16.384 slots de hash fijos, calcula CRC16(clave) % 16384 para encontrar el slot de una clave, y asigna rangos contiguos de slots a cada nodo maestro. Resharding en Redis Cluster significa migrar explícitamente un rango de slots de un nodo a otro (CLUSTER SETSLOT), no recorrer un anillo.

Ambos diseños resuelven el mismo problema de fondo — acotar cuántas claves se mueven cuando cambia la membresía del clúster — pero lo resuelven distinto: la cantidad fija de slots de Redis Cluster hace que los slots (y las claves que contienen) se muevan en lotes explícitos y controlados, mientras que un anillo con nodos virtuales redistribuye la propiedad de forma implícita y continua a medida que cambia el conjunto de nodos. Confundir ambos mecanismos en una respuesta de entrevista suele delatar a quien memorizó "hashing consistente" como palabra clave sin entender qué problema resuelve.