Quand les données ne tiennent plus sur une machine, on les découpe. Le choix du découpage décide de tout : équilibre, requêtes possibles, coût des changements.
⏱️ Durée : environ 100 minutes · 🎓 Niveau : avancé · 🏅 Badge : Découpeur de données
🎬 L'histoire
La table des inscriptions de HashBox atteint 2 To. Aucune machine abordable ne la contient confortablement, et les écritures saturent le disque. L'équipe décide de répartir les données sur 5 serveurs : « l'inscription numéro n va sur le serveur n mod 5 ». Trois mois plus tard, il faut passer à 6 serveurs. Verdict : 83 % des données doivent changer de serveur. Le déménagement dure quatre jours, pendant lesquels le service est dégradé.
« Le découpage par modulo est le plus simple et le pire quand on grandit, dit Sam. Il existe une technique, le hachage cohérent, où ajouter un serveur ne déplace que 1/6 des données. Et il y a d'autres pièges : les clés populaires qui surchargent un serveur, les requêtes qui doivent interroger tous les serveurs. »
Tu apprends à choisir une clé de partitionnement, à comparer hachage et plages, à implémenter un anneau de hachage cohérent avec nœuds virtuels, à mesurer le déséquilibre et à traiter les points chauds.
🎯 Ta mission
À la fin, je serai capable de :
- expliquer pourquoi et comment on partitionne (sharding)
- comparer partitionnement par hachage et par plage (requêtes, équilibre)
- implémenter un hachage cohérent avec nœuds virtuels et mesurer la quantité de données déplacées
- mesurer l'équilibre de charge et traiter un point chaud
- identifier les requêtes inter-partitions et leur coût
🧩 Défi d'échauffement (5 XP)
Une bibliothèque de 1 million de livres est trop grande pour un seul bâtiment. Option A : un bâtiment par lettre initiale du titre. Option B : on attribue chaque livre à un bâtiment par un tirage « au hasard mais reproductible » à partir du titre. Pour chaque option, comment cherches-tu « tous les livres de A à C » ? Comment cherches-tu « le livre Les Misérables » ? Que se passe-t-il le jour où un nouveau bâtiment ouvre ? Quelle option évite qu'un bâtiment soit plein de titres commençant par « L' » ?
💡 Le concept
Pourquoi partitionner
| Raison | Explication |
|---|---|
| Volume | les données dépassent la capacité d'une machine |
| Débit | une seule machine ne suit pas les écritures ou les lectures |
| Latence | placer les données près des utilisateurs (par région) |
Partitionner (sharding) = répartir les données en sous-ensembles, les partitions (shards), chacun sur une machine (souvent répliqué : mission 5). Ne pas confondre : réplication = copier les mêmes données ; partitionnement = diviser les données. On combine les deux.
La clé de partitionnement
Chaque enregistrement possède une clé qui détermine sa partition. Le choix de la clé est la décision de conception : elle doit :
- répartir uniformément données et trafic ;
- permettre aux requêtes fréquentes de n'interroger qu'une partition ;
- être stable (ne pas changer pendant la vie de l'enregistrement).
Deux grandes familles
| Par hachage | Par plage | |
|---|---|---|
| Principe | partition = hash(clé) mod N (ou anneau) | chaque partition couvre un intervalle de clés ordonnées |
| Équilibre | bon (le hachage disperse) | dépend de la distribution des clés |
| Requête sur une clé | 1 partition | 1 partition |
| Requête sur une plage | toutes les partitions (scatter-gather) | 1 ou quelques partitions |
| Point chaud typique | clé très populaire | clés monotones (horodatages : toutes les écritures vont à la dernière plage) |
Le piège du hash mod N
Si N change, presque tout change de place :
N = 5 → 6 : une clé garde sa partition avec probabilité ≈ 1/6 ; ≈ 5/6 des clés se déplacent.
Le hachage cohérent
On place les serveurs et les clés sur un anneau (un cercle de valeurs de hachage). Une clé appartient au premier serveur rencontré en tournant dans le sens horaire.
flowchart LR
subgraph Anneau
S1((Serveur A)) --> K1[clé 1] --> S2((Serveur B)) --> K2[clé 2] --> S3((Serveur C)) --> K3[clé 3] --> S1
end
Description du schéma : un anneau où se succèdent les serveurs A, B, C et des clés ; chaque clé est affectée au serveur suivant dans le sens de rotation.
Ajouter un serveur ne déplace que les clés situées juste avant lui : en moyenne 1/(N+1) des clés, au lieu de N/(N+1).
Nœuds virtuels : chaque serveur physique occupe plusieurs points de l'anneau (100 à 500). Ainsi la charge est répartie plus uniformément (loi des grands nombres) et un serveur qui tombe répartit sa charge sur tous les autres plutôt que sur un seul voisin.
Points chauds
Un hachage uniforme équilibre le nombre de clés, pas le trafic : une clé qui reçoit 30 % des requêtes (un cours en promotion) surcharge sa partition. Remèdes :
| Remède | Principe | Coût |
|---|---|---|
| Cache devant la partition | la lecture ne touche plus la partition | invalidation |
| Réplicas de lecture pour la clé | répartir les lectures | cohérence |
Salage de la clé (cle#0 … cle#k-1) | découper une clé chaude en k sous-clés | lectures par scatter-gather sur k sous-clés |
| Partition dédiée | isoler les clés chaudes connues | gestion |
Requêtes inter-partitions
| Requête | Coût |
|---|---|
| Lecture par clé | 1 partition |
| Jointure ou agrégat global | interroger toutes les partitions, puis fusionner : latence = la plus lente |
| Transaction touchant 2 partitions | coordination (2PC, saga : mission 9) |
| Index secondaire global | maintenu sur chaque partition (index local) ou séparé (index global, mise à jour asynchrone) |
D'où la règle : regrouper ensemble ce qui est accédé ensemble (par exemple partitionner les inscriptions par cours si on les interroge par cours).
Rééquilibrage
Quand on ajoute des machines ou qu'une partition grossit : déplacer des partitions entières (toujours plus de partitions que de machines : 10 à 100 par machine) ; le déplacement se fait en arrière-plan, la table de routage est mise à jour atomiquement.
Routage
Comment un client trouve-t-il la bonne partition ? Un routeur (proxy), un client qui connaît la table de routage (récupérée d'un service de coordination), ou n'importe quel nœud qui redirige.
🧠 Astuce : demande-toi toujours : quelle est ma requête la plus fréquente, et touche-t-elle une seule partition ? Une mauvaise clé transforme chaque requête en tempête sur tous les serveurs.
🔍 Exemple pas à pas
Problème : mesurer la fraction de données déplacée en passant de 5 à 6 serveurs avec hash mod N et avec un anneau cohérent, l'effet des nœuds virtuels sur l'équilibre, un point chaud et son salage, et le nombre de partitions touchées par une requête sur une plage.
import bisect, hashlib, random
from collections import Counter
def h(valeur):
return int(hashlib.md5(str(valeur).encode()).hexdigest()[:12], 16)
CLES = [f"inscription:{i}" for i in range(50000)]
# ---------------- 1. hash mod N : presque tout bouge ----------------
def mod_n(cle, n): return h(cle) % n
deplacees = sum(1 for c in CLES if mod_n(c, 5) != mod_n(c, 6)) / len(CLES)
print(f"hash mod N, de 5 à 6 serveurs : {deplacees:.1%} des clés déplacées (théorie : 5/6 = {5 / 6:.1%})")
assert abs(deplacees - 5 / 6) < 0.02
# ---------------- 2. anneau de hachage cohérent avec nœuds virtuels ----------------
class Anneau:
def __init__(self, serveurs, virtuels=):
.virtuels, .points = virtuels, []
s serveurs: .ajouter(s)
():
v (.virtuels): bisect.insort(.points, (h(), serveur))
():
.points = [(p, s) p, s .points s != serveur]
():
i = bisect.bisect(.points, (h(cle), ())) % (.points)
.points[i][]
anneau5 = Anneau([ i ()])
avant = {c: anneau5.trouver(c) c CLES}
anneau5.ajouter()
apres = {c: anneau5.trouver(c) c CLES}
deplacees_c = ( c CLES avant[c] != apres[c]) / (CLES)
()
(deplacees_c - / ) <
(apres[c] == c CLES avant[c] != apres[c])
():
a = Anneau([ i ()], virtuels)
charge = Counter(a.trouver(c) c CLES)
moyenne = (CLES) /
(charge.values()) / moyenne
()
res = {}
v (, , , ):
res[v] = desequilibre(v); ()
res[] > res[] res[] < res[] >
rng = random.Random()
cours = [ i ()]
poids = [ / (i + ) ** i ()]
requetes = rng.choices(cours, weights=poids, k=)
a6 = Anneau([ i ()], )
charge = Counter(a6.trouver(c) c requetes)
(, (charge.values(), reverse=))
ratio = (charge.values()) / ((requetes) / )
ratio >
():
cle {, , } cle
charge_salee = Counter(a6.trouver(salage(c)) c requetes)
ratio_salee = (charge_salee.values()) / ((requetes) / )
()
ratio_salee < ratio
dates = [ m (, ) j (, )]
frontieres = [ m (, , , , )]
(): bisect.bisect(frontieres, cle)
requete = [d d dates <= d <= ]
par_plage = {partition_plage(d) d requete}
par_hash = {(h(d) % ) d requete}
()
(par_plage) == (par_hash) ==
ecritures = Counter(partition_plage(d) d dates[-:])
(, (ecritures), )
(ecritures) ==
Lecture :
hash mod Ndéplace ≈ 83 % des clés en passant de 5 à 6 serveurs. L'anneau cohérent n'en déplace que ≈ 17 % — et toutes vers le nouveau serveur (rien n'est brassé entre les anciens).- Avec 1 nœud virtuel par serveur, le plus chargé a bien plus que sa part ; avec 100 à 500, l'équilibre devient bon.
- Le hachage équilibre les clés, pas le trafic : sous une charge de type Zipf, un serveur reçoit 50 % de plus que la moyenne. Saler les clés chaudes répartit leurs requêtes, au prix d'une lecture éclatée sur k sous-clés.
- Plages contre hachage : une requête sur « avril » touche 1 partition par plage, mais les 6 par hachage. En contrepartie, les clés monotones (dates) concentrent toutes les écritures récentes sur la dernière plage.
✍️ À toi, avec aide (10 XP)
Calcule par simulation la fraction de clés déplacées quand on retire un serveur d'un anneau de 8 serveurs (200 nœuds virtuels chacun) :
- fraction déplacée (théorie : 1/8) ;
- vers quels serveurs vont les clés déplacées ? Sont-elles réparties uniformément entre les 7 serveurs restants (avantage des nœuds virtuels) ou toutes vers un seul voisin ? Compare avec 1 seul nœud virtuel par serveur ;
- quel est le plus gros reçu / la moyenne attendue ?
💡 Indice 1
Utilise la classe Anneau de l'exemple : retirer.
💡 Indice 2
Compte les destinations des clés dont le serveur d'origine était le serveur retiré.
💡 Indice 3
Avec 1 nœud virtuel, un seul voisin hérite de tout.
✅ Réponse
import bisect, hashlib
from collections import Counter
def h(v): return int(hashlib.md5(str(v).encode()).hexdigest()[:12], 16)
class Anneau:
def __init__(self, serveurs, virtuels=200):
self.virtuels, self.points = virtuels, []
for s in serveurs:
for v in range(virtuels): bisect.insort(self.points, (h(f"{s}#{v}"), s))
def retirer(self, s): self.points = [(p, x) for p, x in self.points if x != s]
def trouver(self, c):
i = bisect.bisect(self.points, (h(c), chr(0x10FFFF))) % len(self.points); return self.points[i][]
CLES = [ i ()]
virtuels (, ):
a = Anneau([ i ()], virtuels)
avant = {c: a.trouver(c) c CLES}
a.retirer()
apres = {c: a.trouver(c) c CLES}
deplacees = [c c CLES avant[c] != apres[c]]
destinations = Counter(apres[c] c deplacees)
()
virtuels == :
((deplacees) / (CLES) - / ) < (destinations) == (destinations.values()) < * (deplacees)
:
(destinations) <=
🚀 À toi, en solo (20 XP)
Partitionnement par plages avec scission automatique. Écris TablePlages :
- une liste de plages triées, chacune avec une capacité maximale (par exemple 1 000 enregistrements) ;
ecrire(cle, valeur)route vers la bonne plage ; si une plage dépasse la capacité, elle est scindée en deux au milieu (médiane des clés) ;lire_plage(a, b)renvoie les valeurs et le nombre de plages touchées ;- teste avec des clés aléatoires (équilibre naturel) puis avec des clés monotones (horodatages croissants) : compte les écritures reçues par chaque plage ; montre que les clés monotones concentrent le trafic sur la dernière plage (point chaud) ;
- corrige en préfixant la clé par un compartiment de hachage (
h(cle) mod 8+ clé) : mesure la répartition des écritures et le nombre de plages touchées par une lecture de plage (compromis).
✅ Pistes de correction
import bisect, hashlib, random
from collections import Counter
def h(v): return int(hashlib.md5(str(v).encode()).hexdigest()[:8], 16)
class TablePlages:
def __init__(self, capacite=500):
self.capacite = capacite
self.bornes = [] # bornes inférieures des plages 1..n (la plage 0 démarre à -∞)
self.plages = [{}] # chaque plage : dict cle -> valeur
self.ecritures = Counter() # écritures reçues par numéro de plage (au moment de l'écriture)
def _indice(self, cle): return bisect.bisect(self.bornes, cle)
def ecrire(self, cle, valeur):
i = self._indice(cle); self.plages[i][cle] = valeur; self.ecritures[i] += 1
if len(self.plages[i]) > self.capacite: ._scinder(i)
():
cles = (.plages[i]); milieu = cles[(cles) // ]
gauche = {k: v k, v .plages[i].items() k < milieu}
droite = {k: v k, v .plages[i].items() k >= milieu}
.plages[i:i + ] = [gauche, droite]; .bornes.insert(i, milieu)
nouveau = Counter()
j, c .ecritures.items(): nouveau[j j < i j + ] += c
nouveau[i] += ; .ecritures = nouveau
():
debut, fin = ._indice(a), ._indice(b)
valeurs = [v j (debut, fin + ) k, v (.plages[j].items()) a <= k <= b]
valeurs, fin - debut +
():
t, vers_derniere = TablePlages(),
n, c (cles):
n >= (cles) // t._indice(c) == (t.plages) - : vers_derniere +=
t.ecrire(c, n)
t, vers_derniere / ((cles) - (cles) // )
rng = random.Random()
aleatoires = [ _ ()]
monotones = [ n ()]
t_a, part_a = repartition(aleatoires); t_m, part_m = repartition(monotones)
()
()
part_m > part_a <
compartimentees = [ c monotones]
t_c, part_c = repartition(compartimentees)
()
part_c <
_, t_touchees = t_c.lire_plage(, )
(, t_touchees, )
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
hash(clé) mod N avec N variable | 83 % des données déplacées à chaque agrandissement | Hachage cohérent, ou beaucoup de partitions fixes |
| Clé monotone (horodatage) en partitionnement par plage | Toutes les écritures sur la dernière partition | Préfixe de hachage ou clé composite |
| Supposer qu'un hachage uniforme équilibre le trafic | Une clé populaire surcharge une partition | Cache, réplicas de lecture, salage de la clé chaude |
| Choisir la clé sans connaître les requêtes | Chaque requête interroge toutes les partitions | Regrouper ce qui est accédé ensemble |
🐉 Mini-boss (40 XP)
Magasin partitionné de HashBox. Construis un magasin clé-valeur partitionné avec :
- un anneau cohérent à nœuds virtuels, un routeur avec table de routage versionnée ;
- ajout et retrait de nœuds avec migration des clés concernées, sans perte pendant la migration (les lectures consultent l'ancienne et la nouvelle position tant que la migration n'est pas terminée) ;
- détection automatique d'un point chaud (une partition reçoit plus de 2× la moyenne) et salage automatique de la clé responsable ;
- requête de type scatter-gather (comptage global) avec délai d'attente par partition et résultat partiel signalé ;
- simulation de 10 000 clés, charge Zipf, ajout de 2 nœuds puis panne d'un nœud ;
- tableau : fraction déplacée à chaque événement, équilibre avant/après salage, latence du scatter-gather (la plus lente des partitions) ;
- 10 tests (aucune clé perdue, déplacement ≤ 1/N + marge, équilibre).
✅ Pistes de correction
Un bon travail : classe Anneau + classe Magasin avec table_de_routage[version], migration en deux temps (copie puis bascule), lecture « double » pendant la migration; détecteur de point chaud par comptage glissant; salage automatique avec registre des clés salées (lectures éclatées); scatter-gather avec délais et résultat partiel ({"resultat": n, "partitions_manquantes": [...]}); tests des invariants (aucune clé perdue, déplacement proche de 1/N, ratio d'équilibre < 1,2 avec 200 nœuds virtuels).
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Avec hash(clé) mod N, ajouter un serveur :
- A. ne déplace aucune clé
- B. déplace la majorité des clés
- C. déplace exactement 1/N des clés
2. Le hachage cohérent avec nœuds virtuels :
- A. supprime le besoin de répliquer
- B. empêche toute panne
- C. limite les déplacements à environ 1/(N+1) des clés et équilibre la charge
3. Une requête sur une plage de clés est efficace avec :
- A. un partitionnement par plage, qui touche peu de partitions
- B. un partitionnement par hachage, qui en touche beaucoup
- C. aucun partitionnement possible
4. 🔁 Révision mission 05 : En réplication asynchrone, quand le leader tombe :
- A. aucune écriture n'est jamais perdue
- B. des écritures déjà confirmées au client peuvent être perdues
- C. les suiveurs sont toujours à jour
5. 🔁 Révision mission 05 : La règle de quorum qui garantit de lire au moins un réplica à jour est :
- A. R + W < N
- B. R = W = 1
- C. R + W > N
✅ Réponses
- B.
- C.
- A.
- B.
- C.
🪞 Je réfléchis (10 XP)
- Quelle est ta requête la plus fréquente, et sur combien de partitions s'exécuterait-elle ?
- Quelle clé de ton système est trop populaire pour rester sur une seule machine ?
🎒 À retenir
- Partitionnement = diviser ; réplication = copier ; on combine.
- Hachage (équilibre) contre plage (requêtes d'intervalles) ; clés monotones = point chaud.
hash mod Ndéplace presque tout ; l'anneau cohérent déplace ≈ 1/(N+1).- Nœuds virtuels : équilibre et répartition de la charge d'un nœud perdu.
- Point chaud : cache, réplicas, salage ; scatter-gather coûteux.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Découpeur de données
← Mission 05 — Réplication · Mission 07 — Cohérence et consensus : panorama →
HEF-140 — Systèmes distribués

