El hashing consistente explicado: anillo de hash, nodos virtuales y rebalanceo

Repartes una caché entre diez servidores con hash(key) % 10. El tráfico crece, añades un undécimo servidor y la tasa de aciertos se desploma: casi todas las claves apuntan ahora a otro servidor, así que la caché está fría en todas partes a la vez y la base de datos que hay detrás recibe toda la carga. El hashing consistente existe precisamente para evitar esto.

Este artículo explica el anillo de hash y los nodos virtuales con un diagrama, mide cuánto ayudan, muestra una implementación compacta y compara las alternativas que encontrarás en sistemas reales: rendezvous hashing, jump hash, Maglev y los slots de hash fijos.

Por qué se rompe el hashing por módulo

Con server = hash(key) % N, la asignación depende de N. Si cambias N, una clave solo se queda donde está si su hash da el mismo resto con ambos valores, y eso es raro. En una simulación rápida con un millón de claves:

Lo ideal es 1/11, alrededor del 9,1 %: el servidor nuevo debería quedarse con su parte justa y nada más debería moverse. El anillo se acerca; la diferencia restante se debe a que los tokens del servidor nuevo caen en arcos algo más grandes que la media.

En una caché, la diferencia está entre una breve caída de la tasa de aciertos y un arranque en frío. En una base de datos con sharding o un conjunto de workers con estado, es la diferencia entre mover una décima parte de los datos y moverlos casi todos.

El anillo de hash

El hashing consistente, presentado por Karger y sus colegas en 1997 para la caché web, proyecta tanto los servidores como las claves sobre el mismo espacio de hash circular, por ejemplo los enteros de 0 a 2^64 - 1, donde el valor más alto vuelve a 0.

1. Aplica el hash al nombre de cada servidor para obtener una posición en el anillo.
2. Aplica el hash a cada clave para obtener una posición en el anillo.
3. Avanza en el sentido de las agujas del reloj desde la posición de la clave. El primer servidor que encuentres es el dueño de la clave.

Al añadir un servidor, este ocupa una posición y solo se queda con las claves entre su predecesor y él. Todas las demás claves siguen donde estaban. Al quitar un servidor, sus claves pasan al siguiente servidor en el sentido de las agujas del reloj. Nada más cambia.

Nodos virtuales: corregir el desequilibrio

Con una sola posición por servidor, los arcos entre servidores son aleatorios y desiguales, así que algunos servidores poseen una parte del anillo mucho mayor que otros. La misma simulación con diez servidores muestra cuánto:

La solución es dar a cada servidor muchas posiciones, llamadas nodos virtuales o tokens, aplicando el hash a nombres como cache-a#0, cache-a#1, etc. Los nodos virtuales aportan además otras dos ventajas:

• Pesos. Un servidor con el doble de memoria recibe el doble de tokens.
• Fallos más suaves. Cuando un servidor muere, sus muchos arcos pequeños pasan a muchos sucesores distintos, de modo que su carga se reparte por el clúster en lugar de duplicar la de un único vecino.

El coste es una tabla de búsqueda más grande y más metadatos que mover cuando cambia la pertenencia. Cassandra muestra este compromiso en la práctica: usaba por defecto 256 tokens por nodo hasta que la versión 4.0 bajó el valor por defecto a 16, junto con un algoritmo de asignación de tokens que coloca esos 16 de forma uniforme en vez de aleatoria.

Una implementación pequeña

Un anillo es una lista ordenada de posiciones de tokens más una búsqueda binaria:

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

Las búsquedas cuestan O(log T) para T tokens. Las versiones de producción también gestionan las colisiones de tokens y mantienen idéntica la visión de la pertenencia en cada cliente, porque dos clientes con listas de servidores distintas no coinciden en dónde vive cada clave.

Replicación en el anillo

Los sistemas de almacenamiento usan el anillo tanto para la ubicación como para el enrutamiento. El artículo de Dynamo de Amazon guarda cada clave en los primeros N servidores distintos en el sentido de las agujas del reloj desde su posición, su preference list, y salta los tokens adicionales de un servidor que ya está en la lista. Con N = 3, perder un servidor aún deja dos copias de todo lo que tenía, en servidores que son sus vecinos en el anillo.

La misma idea de «avanzar en el sentido de las agujas del reloj y saltar duplicados» se extiende a racks y zonas: salta tokens hasta que las réplicas abarquen dominios de fallo distintos.

Alternativas que encontrarás

El jump consistent hash encaja con almacenamiento con sharding en el que los shards están numerados y solo crecen. El rendezvous hashing encaja con conjuntos pequeños de servidores, donde O(N) por búsqueda no importa. Los slots de hash cambian la ubicación automática por movimientos explícitos controlados por el operador, algo que muchos equipos prefieren para bases de datos.

Claves calientes y cargas acotadas

El hashing consistente equilibra claves, no tráfico. Un usuario famoso o un producto viral sigue cayendo en un solo servidor. El hashing consistente con cargas acotadas limita cada servidor a un porcentaje fijo por encima de la media y envía el excedente al siguiente servidor en el sentido de las agujas del reloj. HAProxy lo implementa con su ajuste hash-balance-factor. Para las claves realmente calientes sigues necesitando replicar esa clave, agrupar peticiones o poner una pequeña caché local delante.

Trampas operativas

• Cambiar la función de hash o el esquema de tokens lo recoloca todo, exactamente igual que el hashing por módulo. Trátalo como una migración.
• La pertenencia debe ser coherente. Distribuye la lista de servidores desde una única fuente, como un servicio de coordinación o la configuración del balanceador de carga, y cámbiala en un solo paso.
• Los servidores intermitentes generan churn. Un servidor que falla los health checks cada pocos minutos mueve sus claves de un lado a otro. Añade histéresis antes de quitarlo y volver a añadirlo.
• Los servidores nuevos arrancan en frío. Un nodo de caché nuevo recibe su parte de las peticiones de inmediato; caliéntalo o sube su peso poco a poco si el backend no puede absorber los fallos de caché.

El diagrama del anillo de hash

Cómo leerlo:

• El círculo es el espacio de hash. Las posiciones aumentan en el sentido de las agujas del reloj, y arriba es donde el valor más alto vuelve a cero.
• Los tokens de color son nodos virtuales. Cada color es un servidor, y cada servidor tiene varios tokens repartidos por el anillo.
• Las claves están en sus posiciones de hash, y las flechas apuntan en el sentido de las agujas del reloj al token que las posee.
• Los tokens discontinuos pertenecen al servidor D, que se está añadiendo. Solo cambian de dueño las claves situadas justo antes de los tokens de D, en sentido antihorario.
• La leyenda y el bloque Markdown enumeran los servidores y las cifras de movimiento de la simulación anterior.

Dibujar esquemas de hashing con claridad

• Dibuja el anillo, no una tabla. La regla del sentido horario es visual; una tabla de búsqueda oculta por qué solo se mueven algunas claves.
• Colorea los tokens por servidor y añade una leyenda, en lugar de trazar una arista desde cada token hasta su servidor.
• Muestra un cambio de pertenencia. Un anillo estático explica el enrutamiento; un anillo al que se une un servidor explica todo el sentido de la técnica.
• Pon cifras reales al lado: claves movidas y reparto de la carga. Convencen más que el dibujo.

El hashing consistente aparece en muchos artículos de diseño de sistemas de este blog: en el diagrama de sharding de bases de datos para ubicar datos, en el diagrama de balanceador de carga para el enrutamiento persistente y en el diagrama de estrategias de caché para cachés distribuidas.

Constrúyelo en Archboard

1. Inicia sesión con Google o GitHub y crea un diagrama.
2. Añade una forma Elipse grande del pack Básico como anillo.
3. Añade sobre el anillo formas Elipse pequeñas como tokens, coloreadas por servidor: dos para cada uno de los servidores A, B y C, y dos discontinuas para el nuevo servidor D.
4. Añade cuatro nodos Redis del pack Datos en columna junto al anillo como leyenda, con los colores de sus tokens.
5. Añade las claves como etiquetas Texto del pack Básico sobre el anillo, con flechas cortas hacia sus tokens.
6. Añade un bloque Markdown del pack Básico con las cifras de movimiento de claves y de carga.

El ejemplo usa 14 nodos de diagrama, dentro del plan Free.

Preguntas frecuentes

¿Qué problema resuelve el hashing consistente? Mantiene la mayoría de las claves en el mismo servidor cuando se añaden o quitan servidores. Con el hashing por módulo, cambiar el número de servidores reasigna casi todas las claves; con el hashing consistente, solo se mueve alrededor de 1/N de ellas.

¿Qué son los nodos virtuales en el hashing consistente? Cada servidor físico se coloca muchas veces en el anillo con nombres distintos. Más posiciones hacen los arcos más uniformes, permiten ponderar los servidores según su capacidad y reparten la carga de un servidor caído entre muchos otros.

¿Cuántos nodos virtuales debería tener cada servidor? Los suficientes para un reparto uniforme con el tamaño de tu clúster: en nuestra simulación, 100 por servidor mantuvieron al servidor más cargado dentro del 7 % de la media con diez servidores. Los sistemas con una asignación de tokens más inteligente, como Cassandra 4.0 y posteriores, usan muchos menos.

¿Redis Cluster usa hashing consistente? No en el sentido del anillo. Redis Cluster asigna las claves a 16 384 slots de hash fijos y asigna los slots a los nodos; mover datos significa mover slots de forma explícita.

¿Qué diferencia hay entre el hashing consistente y el rendezvous hashing? Ambos mueven alrededor de 1/N de las claves cuando cambia la pertenencia. El rendezvous hashing puntúa cada servidor para cada clave y elige el más alto; no necesita anillo, pero cuesta O(N) por búsqueda.

Empieza gratis — un puesto, sin tarjeta de crédito.