Consistent Hashing

El hash consistente remapea solo 1/n de las claves al añadir o eliminar nodos, minimizando la redistribución; se usa en caché distribuida y sharding.

Propósito

Minimizar el movimiento de datos cuando los nodos se unen o abandonan, técnica central para almacenamiento y caché distribuidos.

Mecanismo

Mapea nodos y claves en un anillo hash de 0-2^32; cada clave pertenece al primer nodo en sentido horario. Añadir o quitar un nodo afecta solo a las claves del arco adyacente. Los nodos virtuales (múltiples puntos hash por nodo) mejoran el equilibrio. La carga se reparte aproximadamente de forma uniforme.

Casos de uso

Caché distribuida (Memcached)
Sharding de nodos CDN
Sharding de bases de datos (Cassandra)
Balanceo de carga

Ejemplos

entrada

Node C joins

Output

Only keys in C's adjacent arc migrate

Minimal migration

Errores comunes

Too few virtual nodes causes uneven load: Use 150+ virtual nodes per node

Términos relacionados

Una tabla hash mapea claves a un array de cubos mediante una función hash, ofreciendo búsqueda/inserción/borrado promedio O(1); es una de las estructuras de datos más usadas.

Un filtro de Bloom aproxima la pertenencia a un conjunto con k funciones hash y un array de bits, ofreciendo eficiencia espacial a cambio de una tasa de falsos positivos.

Un árbol de Merkle coloca los hashes de datos en las hojas y los hashes de los hijos en los nodos internos, permitiendo una verificación de integridad eficiente de grandes datos; se usa en Git y en blockchains.

References