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%
Servidor AServidor ACaché AServidor AServidor BServidor BCaché BServidor BServidor CServidor CCaché CServidor CServidor DServidor DCaché DServidor DServidor EServidor ECaché EServidor Eclave k1clave k2B#2D#2A#2De 4 a 5 servidoreshash(k) % 4 → % 5~80 % se muevelo ideal~20 % (1/5)anillo · 0 … 2^32 − 1sentido horariok1 → Ak2 → CPorción de cada servidor (ejemplo)A22 %B24 %C30 %D24 %total100 %nuevok2 ahora → E18 % de las clavescaídosus claves siguen a D54 % de las clavesSin C (ejemplo)A22 %B24 %D24 % + 30 % = 54 %B#2D#2A#2Dos posiciones por servidor (ejemplo)A33 %B32 %D35 %total100 %clave k1copia 1copia 2copia 3vacía al entrarFallos al pasar de 4 a 5 cachéshash(k) % N~80 %hashing consistente18 %18 %: tramo de E en el ejemplo; de media, 1/5k1 → Ak2 → C
  • 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.

Aprenderás

  • Entender por qué hash % N mueve casi todas las claves
  • Ubicar servidores y claves en un anillo de hash
  • Saber qué claves se mueven al sumar o quitar un servidor
  • Emparejar la carga con nodos virtuales
  • Guardar réplicas en los siguientes servidores del anillo