Hashing consistente
- Lección 14 de 40
- 10 min
- Intermedio
- 10 pasos
Con hash(clave) % N, cambiar N revuelve casi todo. Con un anillo, cada cambio toca un solo tramo y el resto de los datos se queda donde estaba.
- Servidores activos
- 4
- Claves que cambian
- —
- Porción mayor
- 30%
- petición
- lote
- fallo de caché
Paso 1 de 10
Problema
hash % N se rompe cuando cambia N
En la lección anterior repartimos las claves con servidor = hash(clave) % N. Mientras N no cambie, cada clave tiene un sitio fijo y la carga queda pareja: un 25 % por servidor con 4.
Al pasar a 5 servidores, la cuenta da otro resultado para 4 de cada 5 claves. Una clave solo se queda donde estaba si h % 4 y h % 5 coinciden, y eso pasa en 4 de cada 20 valores. El 80 % de los datos tendría que viajar.
Paso 2 de 10
Técnica
Cerrar el espacio de hash en un círculo
Un hash de 32 bits devuelve números entre 0 y 2^32 − 1. Si pegas el final con el principio, ese rango se vuelve un anillo: después del valor más alto viene otra vez el 0.
Ahora pasa por el mismo hash el nombre de cada servidor y colócalo en el punto que le corresponde. No quedan a la misma distancia unos de otros: cada uno cae donde diga su hash.
Qué cambió
- Anillo de hash
- Cada servidor en la posición hash(nombre)
Paso 3 de 10
Técnica
Cada clave avanza en sentido horario
Las claves también pasan por el hash y caen en el anillo. Su dueño es el primer servidor que aparece avanzando en sentido horario. k1 cae entre D y A, así que es de A; k2 cae entre B y C, así que es de C.
Cada servidor se queda con el tramo que termina en él. En este ejemplo los tramos miden distinto y el de C es el más largo: el 30 % del anillo.
Qué cambió
- Claves k1 y k2 en el anillo
- Cada clave es del siguiente servidor en sentido horario
Paso 4 de 10
Solución
Un servidor nuevo solo se lleva un tramo
E entra al anillo entre B y C. Desde ese momento, las claves del tramo que va de B a E ya no siguen hasta C: se detienen en E. Es lo que le pasa a k2.
Solo esas claves cambian de dueño, un 18 % en este ejemplo, y todas salen de C. A, B y D no se enteran.
Qué cambió
- Servidor E
- El 18 % de las claves pasa de C a E
- El resto no se mueve
Paso 5 de 10
Técnica
Si un servidor cae, también se mueve un solo tramo
Volvemos a los cuatro servidores del principio y ahora C se cae. Las claves que eran suyas siguen avanzando en sentido horario hasta D. Ningún otro servidor cambia.
Con % N, pasar de 4 a 3 servidores movería 3 de cada 4 claves. Aquí solo se mueve el 30 % que tenía C.
Qué cambió
- Servidor C
- Las claves de C, el 30 %, pasan a D
Paso 6 de 10
Problema
Posiciones al azar, tramos desiguales
Como cada servidor cae donde le toca, los tramos no miden lo mismo. Sin C, D hereda su tramo y suma el 54 % de las claves: más del doble que A o B.
Con pocos servidores, el azar alcanza para que uno cargue con mucho más trabajo que los demás.
Qué cambió
- D tiene el 54 % de las claves
Paso 7 de 10
Solución
Varias posiciones por servidor
En lugar de una posición, cada servidor recibe varias: se calcula el hash de «A#1», «A#2» y así. Cada una es un nodo virtual. Aquí cada servidor tiene dos y ocupa varios tramos cortos en vez de uno largo.
Las porciones se emparejan: la mayor baja del 54 % al 35 % en este ejemplo. Y si un servidor sale, sus tramos se reparten entre varios vecinos en lugar de caer sobre uno solo.
Qué cambió
- Dos posiciones por servidor
- Porción mayor: 54 % → 35 %
Paso 8 de 10
Técnica
Copias en los siguientes servidores
Una sola copia por clave no alcanza: si su servidor se cae, el dato se pierde. Por eso cada clave se guarda en los tres primeros servidores distintos que encuentra en sentido horario: su dueño y los dos siguientes.
Para que el dibujo se lea, volvemos a una posición por servidor. k1 se guarda en A (copia 1), en B (copia 2) y en C (copia 3). Si A cae, B y C todavía la tienen.
Qué cambió
- Cada clave en 3 servidores
- Aguanta hasta dos caídas sin perder la clave
Paso 9 de 10
Concepto
Caso: crecer un grupo de cachés
Un grupo de servidores de caché atiende las lecturas antes de la base de datos. Si los clientes eligen servidor con hash(clave) % N, pasar de 4 a 5 cambia el destino de ~80 % de las claves: fallan casi todas a la vez y esas lecturas caen sobre la base de datos.
Con hashing consistente, la quinta caché solo recibe su tramo: un 18 % de las claves en este ejemplo. Esas fallan hasta que E se llena; las demás siguen acertando.
Qué cambió
- Quinta caché, E
- Fallos tras el cambio: ~80 % → 18 %
Paso 10 de 10
Resumen
Lo esencial del hashing consistente
Servidores y claves comparten un anillo de hash; cada clave es del primer servidor en sentido horario.
Sumar o quitar un servidor mueve un solo tramo: cerca de 1/N de las claves.
Los nodos virtuales emparejan las porciones y reparten la carga cuando un servidor sale.
Guarda cada clave en los siguientes servidores distintos del anillo para tener réplicas.
← → paso · R repetir · Espacio pausa
Aprenderás
- Entender por qué hash % N mueve casi todas las claves (visto)
- Ubicar servidores y claves en un anillo de hash (visto)
- Saber qué claves se mueven al sumar o quitar un servidor (visto)
- Emparejar la carga con nodos virtuales (visto)
- Guardar réplicas en los siguientes servidores del anillo (visto)