Consistent hashing asigna claves a propietarios de forma que añadir o retirar un nodo pueda afectar una parte del conjunto, conservando muchas asignaciones anteriores. Resulta útil cuando la topología cambia y redistribuir todo sería costoso. La estabilidad del mapa no garantiza equilibrio de carga ni completa la migración de los datos.
El problema aparece al repartir una caché entre instancias, ubicar datos en shards o elegir un destino para peticiones relacionadas. Esos casos comparten una decisión de enrutamiento, pero tienen contratos distintos: perder una entrada reconstruible y perder una escritura autoritativa requieren respuestas diferentes.
Hash módulo y cambio de tamaño
Un esquema sencillo calcula hash(clave) % N y utiliza el resultado como posición en una lista de N nodos. La misma clave y la misma configuración producen la misma posición. No hace falta consultar un directorio para cada operación si todos los participantes conocen la lista.
Cuando N representa el número de nodos físicos y cambia, también cambia el divisor. Con hashes ilustrativos, 10 % 3 da 1 y 10 % 4 da 2; 45 % 3 da 0 y 45 % 4 da 1. Muchas claves pueden cambiar de destino aunque los nodos anteriores sigan disponibles. La correspondencia entre posiciones y nodos también debe mantenerse definida.
El módulo no es incorrecto por sí mismo. Un número fijo de particiones lógicas o slots puede conservar el cálculo, mientras un mapa separado cambia qué nodo posee cada partición. Así se mueven grupos seleccionados sin recalcular su identidad. La alternativa se evalúa por la granularidad de movimiento, el coste del directorio y las operaciones necesarias, no por una preferencia universal.
Un anillo y un sucesor
En el modelo de anillo, una función sitúa claves y posiciones de los nodos en un espacio de hash. Los puntos se ordenan y el final vuelve al principio. Para una clave, se busca el primer punto de nodo alcanzado en sentido horario, incluyendo ese punto si coincide exactamente: su sucesor es el propietario primario en este ejemplo.
Cada posición posee el intervalo desde su predecesor, excluido, hasta ella, incluida: (predecesor, posición]. El último intervalo puede cruzar el origen. La función, la codificación de claves y la identidad usada para calcular posiciones deben ser estables y compartidas; cambiar esas reglas también puede remapear el conjunto.
Un espacio ilustrativo de 0 a 99 permite seguir el mecanismo. Con A en 20, B en 50 y C en 80, A posee (80, 20]: comprende los valores mayores que 80 y los menores o iguales que 20, pasando por el origen. B posee (20, 50] y C (50, 80]. Una clave situada en 90 llega a A, no a C.
Los dos grupos del diagrama muestran el mapa antes y después de incorporar D. Las flechas representan únicamente el recorrido horario esquemático; no representan replicación, solicitudes ni movimiento de datos. El espacio reducido es didáctico, no una configuración obligatoria.
--- config: look: handDrawn --- flowchart TD subgraph before["Antes"] a0["A · posición 20"] --> b0["B · posición 50"] b0 --> c0["C · posición 80"] c0 --> a0 end subgraph after["Después"] a1["A · posición 20"] --> d1["Nuevo D · posición 35"] d1 --> b1["B · posición 50"] b1 --> c1["C · posición 80"] c1 --> a1 end before ~~~ after
Incorporación y salida
Se incorpora D en 35, conservando las posiciones anteriores. Su predecesor es A en 20 y su sucesor es B en 50. D adquiere (20, 35], que antes pertenecía a B. B conserva (35, 50]; los intervalos de A y C no cambian. Esa es la reducción de movimiento que se busca bajo estos supuestos.
| Hash ilustrativo de la clave | Antes | Después de incorporar D |
|---|---|---|
| 10 | A | A |
| 30 | B | D |
| 45 | B | B |
| 70 | C | C |
| 90 | A | A |
Si se retira D y permanecen las otras posiciones, B vuelve a recibir (20, 35]. Si se retira A, su intervalo que cruza el origen pasa al siguiente propietario. En todos los casos debe distinguirse el nuevo mapa de la disponibilidad de los bytes que contiene ese intervalo.
Con N nodos anteriores de igual peso y reparto equilibrado, añadir uno puede mover aproximadamente 1/(N+1) de las claves; retirar uno de N, aproximadamente 1/N. Son estimaciones bajo hashes y posiciones adecuados, no porcentajes exactos para cualquier anillo. Tampoco describen necesariamente el porcentaje de bytes, peticiones o tiempo de migración.
Nodos virtuales y pesos
Una sola posición por nodo puede producir intervalos desiguales. Los nodos virtuales, o tokens, asignan varias posiciones a un mismo nodo físico. Cada token posee su intervalo; el propietario físico puede recibir muchos intervalos repartidos por el espacio.
Con suficientes posiciones bien distribuidas se obtiene una asignación más granular y se puede repartir la redistribución entre varios propietarios. Los pesos pueden representarse con más posiciones para nodos de mayor capacidad. La proporción resultante es aproximada; debe medirse con la carga real y los límites de cada recurso.
Añadir tokens nuevos o modificar pesos también cambia asignaciones. Para conservar el beneficio de estabilidad, se debe especificar qué posiciones permanecen y cuáles cambian. No basta con recalcular un anillo completamente diferente y llamarlo consistent hashing.
La arquitectura Dynamo documentada por Cassandra describe el anillo y los tokens en un sistema de almacenamiento. El balanceador ring hash de Envoy aplica la idea al enrutamiento. Son ejemplos de contratos distintos, no una afirmación de que toda base o balanceador use esta estrategia.
Claves, carga y hotspots
Un hash uniforme distribuye posiciones; no uniformiza el trabajo asociado a cada clave. Un usuario puede generar muchas más peticiones que otros, un objeto puede ocupar muchos más bytes y una operación puede costar más CPU. Una sola clave caliente sigue llegando a su propietario aunque existan miles de tokens.
La elección de la clave conserva o divide localidad. Mantener los datos de un tenant juntos facilita ciertas consultas y transacciones, pero puede concentrar carga. Dividir esa entidad en buckets puede repartir trabajo, con costes para consultas, orden y coordinación. La decisión corresponde al modelo de datos y sus accesos, no únicamente a la función de hash.
Para una caché pueden ayudar el agrupamiento de peticiones repetidas, una capa local y lecturas compatibles con su frescura. En almacenamiento autoritativo, las escrituras y las invariantes necesitan el contrato adecuado. Replicar no convierte automáticamente una escritura sobre una única clave en trabajo distribuido entre primarios.
Enrutamiento, movimiento y disponibilidad
Los participantes necesitan una visión coherente de membership: qué nodos y tokens existen y qué versión del mapa deben usar. Configuración divergente puede enviar operaciones sobre la misma clave a propietarios distintos. Un router central, metadatos distribuidos o clientes actualizados son opciones con costes diferentes; el anillo por sí solo no coordina esas decisiones.
Cambiar propietario tampoco mueve los datos. Una migración debe transferir el intervalo y las escrituras concurrentes, verificar el destino, coordinar el cambio de autoridad y conservar recuperación. Durante la transición pueden existir copias con estados distintos. El cutover necesita reglas explícitas; volver a una copia antigua sin reconciliar nuevas escrituras puede perder información.
En cachés, los nuevos destinos pueden provocar misses y carga adicional sobre el origen. Una incorporación abrupta puede producir una caché fría; el fallback y la recuperación requieren límites para no sobrecargar la base. La estabilidad de las claves restantes reduce trabajo, pero no elimina ese riesgo.
Replicación, alta disponibilidad y backups son decisiones adicionales. Si una política replica sobre sucesores del anillo, debe elegir nodos físicos distintos y evitar contar varias posiciones del mismo físico como réplicas independientes. Una caída temporal no obliga siempre a retirar al nodo del mapa: el contrato puede recurrir a una réplica o a otra política de servicio. Lecturas, escrituras y reparación dependen de la consistencia requerida; consistent hashing no aporta por sí solo consenso ni atomicidad.
Elegir según el problema
Consistent hashing encaja cuando interesa preservar muchas asignaciones ante cambios de topología y se acepta su coordinación operativa. Un directorio de particiones lógicas puede dar control más explícito sobre propietarios y migraciones; los rangos pueden favorecer consultas ordenadas. Esas técnicas pueden combinarse según el diseño.
La evaluación debe separar número de claves, bytes por propietario, peticiones, latencia y coste de redistribución. También debe explicar cómo se publican cambios de mapa, qué sucede durante un fallo y cuándo una copia pasa a ser autoritativa.
El anillo responde dónde se asigna una clave. El diseño completo debe responder quién puede escribirla, dónde existen sus datos y cómo se conserva el contrato mientras cambia de propietario.