El hash consistente resolvió un problema real de los sistemas distribuidos: cuando se añaden o se eliminan depósitos, evitar reasignar todas las claves. Pero el anillo habitual al estilo de Karger conllevaba una carga operativa: nodos virtuales, almacenamiento y desequilibrios que había que corregir.
El hash consistente por saltos de Lamping y Veach planteó una pregunta más acotada: si los depósitos se numeran de forma secuencial, ¿puede calcularse el destino de la clave sin almacenar ningún anillo? Su respuesta cabía en unas cinco líneas de código.
El artículo de arXiv señala que el método no requiere almacenamiento, es más rápido que el algoritmo de Karger et al. y reparte de forma más uniforme tanto el espacio de claves como la carga de trabajo cuando cambia el número de depósitos. Su compromiso es explícito: la numeración secuencial de los depósitos lo hace más adecuado para el almacenamiento que para la pertenencia arbitraria a una caché web.
Saltar directamente al último cambio de depósito
La restricción a identificadores de depósito secuenciales eliminó la necesidad de un anillo de pertenencia.
La reasignación mínima se deriva del proceso de salto: una clave solo se mueve cuando el depósito añadido la gana.
La ausencia de tabla de búsqueda significa que no hay huella de memoria que reconstruir ni distribuir.
La limitación es honesta y útil: el truco encaja mejor con fragmentos de almacenamiento que con flotas de caché volátiles.
Si una estructura de datos existe principalmente para preservar una ley de probabilidad, a veces la ley puede muestrearse directamente y la estructura puede desaparecer.
El hash consistente por saltos se convirtió en una opción compacta para el almacenamiento fragmentado, las bases de datos y las bibliotecas que necesitan una ubicación estable con un coste de implementación mínimo. Su elegancia reside en la restricción: renunciar a nombres de depósito arbitrarios y todo el anillo desaparece.
CONSULTA LAS PRUEBAS
Las fuentes
- A Fast, Minimal Memory, Consistent Hash Algorithm arXiv · arxiv.org ·