Découper les données entre les machines
Le partitionnement (sharding en anglais) découpe un grand jeu de données en morceaux et range chaque morceau sur une machine différente. Chaque machine ne garde qu’une partie des données, et la clé d’une donnée dit sur quelle machine elle se trouve.
Une enseigne garde 40 millions de fiches clients. Aucune machine ne les tient toutes, et il faut pourtant retrouver une fiche en une fraction de seconde.
À la fin de cette leçon
Remarque
Je peux répartir des données entre des machines à partir de leur clé.
Mots clés
| Mot | Ce que ça veut dire |
|---|---|
| Partitionnement | découper les données en morceaux sur plusieurs machines |
| Clé de partition | la valeur qui décide de la machine |
| Fonction de hachage | un calcul qui change une clé en nombre |
| Hachage cohérent | un rangement où ajouter une machine déplace peu de clés |
| Anneau | les positions possibles, mises en cercle |
| Point chaud | une machine qui reçoit bien plus de demandes que les autres |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La clé décide de la machine
On pourrait ranger les clients par ordre alphabétique : de A à H sur la machine 0, de I à P sur la machine 1. Mais certaines lettres sont bien plus fréquentes, et une machine se retrouve surchargée.
On préfère passer la clé dans une fonction de hachage, qui donne un nombre. Le reste de la division de ce nombre par le nombre de machines donne la machine.
Placer cinq clients sur trois machines
# Cinq clients, trois machines : la machine est le reste de la division du numéro par 3.
for numero in [1040, 1041, 1042, 1043, 1044]:
print("client", numero, "-> machine", numero % 3)
# Remplacez 3 par 4 puis relancez : la plupart des clients changent de machine.
Fabriquer un petit client nommé v
v() ( printf '%s\r\n' "$*" | nc -w 1 valkey 6379 )Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Calculer la machine de huit clients
for n in 1040 1041 1042 1043 1044 1045 1046 1047; do echo "client $n -> machine $((n % 3))"; doneAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ranger le client 1042 sur sa machine
v SET dist:machine1:client:1042 LeaAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le retrouver grâce à sa clé
v GET dist:machine1:client:1042Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ajouter une machine déplace presque tout
Avec le reste de la division, le nombre de machines fait partie du calcul. Passer de 3 à 4 machines change la machine de presque toutes les clés.
Il faut alors déplacer ces données d’un disque à l’autre, pendant que le service répond encore. C’est lent et cher.
Compter les clients qui changent de machine
m=0; for n in 1040 1041 1042 1043 1044 1045 1046 1047; do [ $((n % 3)) -ne $((n % 4)) ] && m=$((m+1)); done; echo $mAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le hachage cohérent ne déplace que le voisinage
Dans le hachage cohérent, on met les positions possibles sur un anneau, de 0 à 99 ici. Chaque machine a une position. Une clé a aussi une position, et elle va à la première machine rencontrée en avançant, puis en repartant de 0 si besoin.
Si on ajoute une machine, seules les clés placées juste avant elle changent de machine.
Exemple : ajouter la machine D à l’anneau
| Position de la clé | Avec A=20, B=50, C=80 | Avec D=65 en plus |
|---|---|---|
| 10 | A | A |
| 35 | B | B |
| 60 | C | D |
| 90 | A (retour à 0) | A |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Placer des clés sur un anneau
# Un anneau de 0 à 99. Une clé va à la première machine à sa position ou après.
machines = {"A": 20, "B": 50, "C": 80}
def machine_pour(position):
choisie = None
premiere = None
for nom in machines:
place = machines[nom]
if premiere is None or place < machines[premiere]:
premiere = nom
if place >= position and (choisie is None or place < machines[choisie]):
choisie = nom
if choisie is None:
choisie = premiere
return choisie
for position in [10, 35, 60, 90]:
print(position, "->", machine_pour(position))
machines["D"] = 65
print("Avec D en 65 :", machine_pour(60), "au lieu de C")
Une erreur fréquente
Attention
On croit souvent que partitionner répartit toujours la charge. Si une seule clé est très demandée, comme une vedette ou un billet en promotion, sa machine devient un point chaud. Une recherche sur toutes les clés doit aussi interroger toutes les machines.