Hashing consistente: ubicación estable de claves cuando los nodos aparecen y desaparecen

Qué es

La documentación de Cassandra (citada) contrasta el hashing ingenuo, el hash de la clave módulo el número de cubos, con el hashing consistente: cada nodo posee uno o más tokens en un anillo de hash continuo, se aplica hash a una clave para ubicarla en el anillo, y la propiedad recae en el siguiente nodo recorriendo el anillo en una dirección. Cuando cambia el número de nodos, solo se mueve una pequeña fracción de las claves. Con un token por nodo y pocos nodos no existe una posición de token para un nodo nuevo que deje el anillo equilibrado, y los rangos desiguales significan carga desigual; por eso Cassandra sigue el artículo de Dynamo y asigna varios tokens por nodo físico, los nodos virtuales, de modo que incluso un único nodo añadido toma muchos fragmentos pequeños de muchos vecinos.

El módulo upstream de nginx (citado) ofrece la misma disyuntiva: el simple hash $key puede reasignar la mayoría de las claves cuando se elimina un servidor, mientras que hash $key consistent usa el método ketama para que solo se muevan unas pocas claves. Envoy (citado) ofrece un balanceador de ring hash y Maglev, una variante basada en tablas con búsquedas más rápidas; su documentación señala que Maglev mueve más claves que el anillo cuando se eliminan hosts.

Por qué importa

Las cachés pierden su tasa de aciertos en cada cambio de membresía si las claves se dispersan; los almacenes particionados tendrían que mover la mayor parte de los datos; los servicios con afinidad de sesión perderían esa afinidad en cada despliegue. El hashing consistente acota la disrupción a lo que realmente cambió.

Cómo aplicarlo

• Elegir una clave de hash con suficiente cardinalidad (id de usuario, id de tenant, clave de caché), no algo como la IP del cliente detrás de un NAT.
• Usar una biblioteca o una implementación de proxy; configurar los nodos virtuales o el tamaño de la tabla para que la carga por nodo sea uniforme, y monitorear la proporción por host (Envoy expone medidores del número mínimo y máximo de entradas por host).
• Para la replicación, tomar los siguientes k nodos físicos distintos en el anillo, saltando los nodos virtuales de la misma máquina y, si es posible, del mismo rack o zona.
• Planificar cómo se mueven los datos cuando se une un nodo: el nuevo propietario debe recibir su rango antes de servir, o el propietario anterior debe servir los fallos durante una transición.
• Fijar la función de hash durante toda la vida del despliegue; cambiarla reasigna todo.

Trampas

El hashing consistente no soluciona las claves calientes: una clave popular sigue cayendo en un solo nodo. Los nodos ponderados necesitan proporcionalmente más nodos virtuales. El hashing consistente no tiene nada que ver con la consistencia de los datos; solo decide la ubicación.