¿Por qué no usar simplemente clave mod N para elegir un servidor?

Con hash(clave) mod N, cambiar N de un número de servidores a otro reordena casi todas las claves, porque el módulo cambia para prácticamente todas ellas. El hashing consistente evita esto desacoplando las posiciones de las claves del número de servidores.

¿Qué son los nodos virtuales?

Cada servidor físico se coloca en muchos puntos del anillo, llamados nodos virtuales o réplicas. En lugar de una posición por servidor, V posiciones reparten la propiedad del servidor en muchos arcos pequeños, lo que equilibra la carga.

¿Por qué los nodos virtuales mejoran el equilibrio de carga?

Con un solo punto por servidor, la colocación aleatoria puede dar a algunos servidores arcos enormes y a otros minúsculos. Muchos nodos virtuales promedian estas variaciones, de modo que cada servidor físico termina con una parte más justa de las claves.

¿Cómo encuentra una clave su servidor en el anillo?

La clave se aplica a una función hash para obtener una posición en el anillo, y luego se recorre en sentido horario hasta encontrar el primer servidor (nodo virtual). Ese servidor posee la clave. Si se pasa la parte superior del anillo, se da la vuelta hasta el inicio.

¿Dónde se usa el hashing consistente?

Impulsa cachés distribuidas como el sharding de clientes de memcached, almacenes clave-valor como Amazon Dynamo, Cassandra y Riak, redes de distribución de contenido, y tablas de hash distribuidas (DHT) de igual a igual como Chord.

¿Qué ocurre con las claves cuando se elimina un servidor?

Solo se reasignan las claves que pertenecían a los nodos virtuales del servidor eliminado. Cada clave afectada se mueve en sentido horario al siguiente servidor superviviente, mientras que todas las demás claves permanecen exactamente donde estaban.

¿Cuántos nodos virtuales debería usar?

En la práctica los sistemas usan entre unos 100 y varios cientos de nodos virtuales por servidor. Más réplicas dan un equilibrio más uniforme pero cuestan más memoria y sobrecarga en la estructura de búsqueda.

¿Cómo se asignan exactamente las claves al anillo?

Una función hash asigna cada clave y cada etiqueta de nodo virtual a un número dentro de un rango fijo, por ejemplo de 0 a 2^32 − 1. Ese rango se trata como un círculo, de modo que el valor más grande da la vuelta hasta el más pequeño.

Inicio▸Computación Distribuida y Paralela▸Hashing Consistente — El Anillo de Hash

💍 Hashing Consistente — El Anillo de Hash

Coloca claves y servidores en un anillo de hash para que añadir o quitar un nodo solo reasigne una pequeña fracción de las claves. Los nodos virtuales suavizan la carga — la técnica detrás de las cachés distribuidas y las DHT.

Computación Distribuida y Paralela3DModerado60 FPS

Acerca de Hashing Consistente

El hashing consistente resuelve un problema crítico en los sistemas distribuidos: cómo asignar claves de datos a servidores de forma que añadir o quitar un nodo reordene la menor cantidad posible de claves. La técnica asigna tanto las claves como los servidores a posiciones en un anillo de hash circular de tamaño 2^32. Cada clave pertenece al primer servidor que se encuentra en sentido horario desde su posición. Con el enfoque ingenuo de módulo (hash(clave) mod N), cambiar N de un número de servidores a otro puede reasignar prácticamente todas las claves — catastrófico para una caché en producción. El hashing consistente limita la disrupción a aproximadamente 1/N de las claves en promedio, porque solo cambia de dueño el arco del anillo adyacente al servidor añadido o eliminado.

Los nodos virtuales (también llamados réplicas) son el refinamiento práctico: cada servidor físico se coloca en V posiciones del anillo en lugar de una sola, dividiendo su propiedad en muchos arcos pequeños. Esto suaviza drásticamente la distribución de la carga — sin nodos virtuales, un solo servidor podría reclamar por azar el 40% de las claves; con más de 100 nodos virtuales, la distribución converge hacia el ideal de 1/N por servidor. Ajusta los servidores, el número de nodos virtuales y el conjunto de claves con los controles deslizantes, y luego añade o elimina servidores para observar cuán pocas claves (resaltadas en blanco) necesitan moverse.

Preguntas Frecuentes

¿Por qué el hashing por módulo provoca una redistribución masiva de claves cuando cambian los servidores?

Con hash(clave) mod N, la ranura a la que se asigna cada clave depende de N. Cuando N cambia — digamos de 4 a 5 — el módulo cambia para prácticamente todas las claves, reasignando aproximadamente (N−1)/N ≈ 80% de ellas. El hashing consistente elimina esto desacoplando las posiciones de las claves del número de servidores: cada clave siempre se asigna a la misma posición del anillo, y solo cambia la búsqueda en sentido horario cuando se añade o elimina un servidor.

¿Exactamente cuántas claves se mueven cuando se añade un servidor al anillo?

Cuando un nuevo servidor S se coloca en la posición p del anillo, reclama el arco desde el servidor anterior (en sentido horario) hasta p. Solo se mueven las claves que caen en ese arco — pasan de su dueño anterior a S. En promedio eso es 1/N de todas las claves, donde N es el nuevo número de servidores. Todas las demás claves permanecen con sus dueños existentes.

¿Qué problema resuelven los nodos virtuales, y cuántos deberían usarse?

Con una posición por servidor, la colocación aleatoria en el anillo produce longitudes de arco muy desiguales: algunos servidores pueden recibir 3 veces la carga media. Colocar cada servidor físico en V posiciones de nodo virtual divide el anillo en V×N segmentos, promediando el desequilibrio. Los sistemas en producción (Amazon Dynamo, Cassandra) suelen usar entre 100 y 200 nodos virtuales por servidor, con lo que la desviación estándar de la carga cae por debajo del 10% de la media.

¿Cómo funciona la búsqueda de una clave en tiempo constante?

Las posiciones de los nodos virtuales se almacenan en un array ordenado o en un árbol binario de búsqueda equilibrado. Para encontrar el dueño de una clave, se aplica hash a la clave para obtener su posición en el anillo, y luego se realiza una búsqueda binaria de la posición de nodo virtual más pequeña que sea mayor o igual a la posición de la clave (dando la vuelta a la posición 0 si no se encuentra ninguna). Esta búsqueda se ejecuta en tiempo O(log(V×N)) — efectivamente constante para V y N fijos.

¿Qué sistemas reales usan hashing consistente?

Amazon Dynamo (2007) popularizó el hashing consistente con nodos virtuales para su almacén clave-valor; Cassandra heredó la misma arquitectura. Las bibliotecas cliente de memcached (por ejemplo, el algoritmo ketama) lo usan para fragmentar las claves de caché entre un conjunto de servidores. Las redes de distribución de contenido y las tablas de hash distribuidas (DHT) de igual a igual como Chord y Kademlia también dependen del hashing basado en anillo.

¿Qué ocurre con los datos cuando un servidor falla y se elimina?

Si el servidor S falla, sus posiciones de nodo virtual quedan vacantes. Las claves que poseía S ahora pertenecen al siguiente servidor en sentido horario para cada arco. Si hay replicación configurada (normalmente 3 réplicas en Cassandra), los datos ya existen en los siguientes N−1 servidores en sentido horario, de modo que el clúster sigue sirviendo lecturas sin pérdida de datos. Los cuórums de escritura garantizan la consistencia durante la conmutación por error.

¿Cómo se relaciona el hashing consistente con Chord DHT?

Chord (Stoica et al., 2001) es un protocolo de búsqueda de igual a igual construido directamente sobre el hashing consistente. A cada par se le asigna una posición en un anillo SHA-1 de 160 bits. Chord añade una "tabla de dedos" de O(log N) atajos por nodo, de modo que cualquier clave puede localizarse en O(log N) saltos — combinando el hashing consistente con una estructura de enrutamiento distribuido eficiente.

¿Puede el hashing consistente manejar servidores con diferentes capacidades?

Sí. Asignando más nodos virtuales a un servidor de mayor capacidad — digamos 200 nodos virtuales a una máquina con el doble de RAM frente a 100 para un nodo estándar — su parte del anillo aumenta proporcionalmente a su capacidad. Este hashing consistente ponderado se usa en la asignación de tokens de Cassandra y en balanceadores de carga en la nube para dirigir más tráfico a las instancias más grandes.

¿Qué es el hashing consistente con "carga acotada"?

En 2017, Google publicó "Consistent Hashing with Bounded Loads", que añade una restricción de capacidad: ningún servidor puede tener más de (1 + ε) veces el número promedio de claves. Cuando un servidor objetivo está sobrecargado, la clave se asigna al siguiente servidor en sentido horario, distribuyendo la carga de forma más uniforme. Esta variante se usa en los balanceadores de carga en producción de Google.

¿Cómo afecta la elección de la función hash a la distribución en el anillo?

Una buena función hash debe distribuir tanto las claves como las etiquetas de los nodos virtuales de manera uniforme a lo largo del anillo de 2^32 bits. Las funciones hash deficientes producen agrupamientos, provocando que algunos arcos sean mucho más largos que el promedio incluso con muchos nodos virtuales. En la práctica, FNV-1a, MurmurHash3 y xxHash son opciones populares por su velocidad y sus propiedades de distribución uniforme.

⚙ Bajo el capó

consistent hashinghash ringvirtual nodesload balancingCanvas 2D

3D · Renderizador Three.js / WebGL · objetivo 60 FPS · funciona totalmente en el cliente, sin instalación