Datos que no caben en una máquina
El particionado (en inglés, sharding) reparte un conjunto de datos entre varias máquinas, de modo que cada una guarda solo un trozo. Se hace por la clave de cada dato.
Una tienda con millones de pedidos no los guarda en un solo disco. Esta lección enseña a decidir qué máquina guarda cada clave y cómo evitar mover casi todo al añadir una máquina.
Al final de esta lección
Nota
Puedo repartir unos datos entre varias máquinas según su clave.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Partición | el trozo de los datos que guarda un nodo (shard en inglés) | |
| Clave de reparto | el valor que decide a qué nodo va un dato | |
| Función hash | una función que convierte una clave en un número | |
| Resto | lo que sobra al dividir un número entre otro | 7 % 3 = 1 |
| Hashing consistente | un reparto en anillo donde añadir un nodo mueve pocas claves |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El resto de un hash decide el nodo
Una función hash convierte una clave, como un nombre, en un número que parece al azar pero es siempre el mismo para esa clave.
Para tres nodos numerados 0, 1 y 2, se divide el número entre 3 y se usa el resto. Cada clave tiene un nodo fijo, y las claves se reparten casi a partes iguales.
Ejemplo: tres claves y tres nodos
| Clave | Hash (primeros 4 caracteres) | Resto de dividir entre 3 | Nodo |
|---|---|---|---|
| ana | 24d4 | 2 | nodo 2 |
| bea | b6e1 | 2 | nodo 2 |
| carlos | 7b85 | 1 | nodo 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Calcular el nodo de ana con tres nodos
echo $(( 0x$(printf ana | sha256sum | cut -c1-4) % 3 ))Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Calcular el nodo de bea con tres nodos
echo $(( 0x$(printf bea | sha256sum | cut -c1-4) % 3 ))Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Calcular el nodo de carlos con tres nodos
echo $(( 0x$(printf carlos | sha256sum | cut -c1-4) % 3 ))Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El resto mueve casi todo al añadir nodos
Si la tienda añade un cuarto nodo, el divisor pasa de 3 a 4 y casi todos los restos cambian. Las claves tienen que viajar a su nodo nuevo.
En la simulación, 73 de cada 100 claves cambian de sitio. Mover tantos datos satura la red justo cuando el sistema ya va justo de capacidad.
Calcular el nodo de ana con cuatro nodos
echo $(( 0x$(printf ana | sha256sum | cut -c1-4) % 4 ))Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Calcular el nodo de bea con cuatro nodos
echo $(( 0x$(printf bea | sha256sum | cut -c1-4) % 4 ))Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Contar las claves que se mueven
# Repartir 100 claves (los números 0 a 99) entre nodos con el resto.
cambian = 0
for clave in range(100):
if clave % 3 != clave % 4:
cambian = cambian + 1
print("Al pasar de 3 a 4 nodos cambian de sitio", cambian, "claves de 100")
# Prueba a pasar de 4 a 5 nodos cambiando el 3 por un 4 y el 4 por un 5.
Un error muy común
Advertencia
Mucha gente cree que añadir un nodo solo mueve la parte que va al nodo nuevo. Con el resto, cambia el divisor de todas las claves y se mueven muchas más. Por eso los sistemas grandes no usan el resto simple.
El hashing consistente usa un anillo
En el hashing consistente, las posiciones forman un anillo de 0 a 99, y después de 99 se vuelve a 0. Cada nodo ocupa una posición. Una clave va al primer nodo que encuentra al avanzar desde su posición.
Al añadir un nodo, solo le pasan claves los vecinos de su tramo. El resto de claves no se mueve.
Ejemplo: añadir el nodo D al anillo
| Clave | Posición | Dueño con A 30, B 60, C 90 | Dueño al añadir D en 50 |
|---|---|---|---|
| diego | 20 | A | A |
| carlos | 44 | B | D |
| ana | 4 | A | A |
| bea | 96 | A (da la vuelta) | A (da la vuelta) |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Buscar el nodo dueño en el anillo
# Un anillo de posiciones 0 a 99. Cada nodo ocupa una posición.
nodos = [["A", 30], ["B", 60], ["C", 90]]
posicion_clave = 44
dueno = None
for nodo in nodos:
if nodo[1] >= posicion_clave and dueno is None:
dueno = nodo[0]
if dueno is None:
dueno = nodos[0][0] # se da la vuelta al anillo
print("La clave en la posición", posicion_clave, "va al nodo", dueno)
# Cambia la posición a 95 y vuelve a ejecutar.
Para ir más lejos: nodos virtuales
Con pocos nodos en el anillo, uno puede quedarse con un tramo mucho mayor que los demás. Se arregla dando a cada máquina varias posiciones, los nodos virtuales.
Dibuja un anillo de 100 posiciones con A en 10, 40 y 70, y B en 25, 55 y 85. Anota qué parte del anillo guarda cada máquina.