Pour survivre à une panne, copie les données. Mais dès qu'il y a plusieurs copies, il faut décider laquelle croire.
⏱️ Durée : environ 110 minutes · 🎓 Niveau : avancé · 🏅 Badge : Gardien des copies
🎬 L'histoire
HashBox réplique sa base de données sur deux machines supplémentaires. Un soir, la machine principale tombe en panne ; la réplique de secours prend le relais. Le lendemain, des formateurs se plaignent : les trois dernières inscriptions de la soirée ont disparu. Elles avaient été confirmées à l'utilisateur, mais la réplique n'en avait pas encore reçu copie quand la principale est tombée.
« Répliquer, c'est un compromis entre vitesse, sécurité et cohérence, dit Maya. Si tu attends que toutes les copies confirment, c'est lent et fragile. Si tu n'attends pas, tu peux perdre des données. Il existe des réglages — et une règle élégante, les quorums, qui garantit qu'on lit toujours la dernière écriture. »
Tu apprends la réplication leader-suiveurs synchrone et asynchrone, le retard de réplication, le basculement, les quorums (R + W > N), et les types de données répliqués sans conflit (CRDT).
🎯 Ta mission
À la fin, je serai capable de :
- expliquer pourquoi on réplique (disponibilité, latence, débit de lecture) et ce que cela coûte
- comparer réplication synchrone et asynchrone (perte de données, latence)
- simuler un basculement et mesurer les écritures perdues
- démontrer la règle des quorums R + W > N par énumération
- implémenter des CRDT simples (compteur, registre, ensemble) qui convergent sans coordination
🧩 Défi d'échauffement (5 XP)
Tu tiens un registre précieux. Tu en gardes une copie chez un ami. Soit tu lui téléphones à chaque ligne que tu écris et tu attends sa confirmation (sûr, mais lent), soit tu lui envoies les feuilles par la poste à la fin de la journée (rapide, mais il lui manque la journée en cours si ta maison brûle). Quel est ton compromis ? Que se passe-t-il si ton ami et toi corrigez la même ligne en même temps ?
💡 Le concept
Pourquoi répliquer
| Objectif | Explication |
|---|---|
| Disponibilité | le service continue si une machine tombe |
| Durabilité | les données survivent à la perte d'un disque ou d'un site |
| Latence | des copies proches des utilisateurs |
| Débit de lecture | répartir les lectures sur plusieurs copies |
Le coût : maintenir des copies cohérentes est le cœur du problème distribué.
Leader-suiveurs (primaire-réplicas)
flowchart LR
C["Client"] -->|écritures| L["Leader"]
L -->|journal de réplication| F1["Suiveur 1"]
L -->|journal de réplication| F2["Suiveur 2"]
C -.->|lectures| F1
C -.->|lectures| F2
Description du schéma : les clients écrivent sur le leader ; le leader envoie son journal de modifications à deux suiveurs ; les lectures peuvent aller aux suiveurs.
- Une seule machine accepte les écritures (pas de conflit d'écriture) ;
- les suiveurs appliquent le journal dans l'ordre.
Synchrone ou asynchrone ?
| Synchrone | Asynchrone | Semi-synchrone | |
|---|---|---|---|
| Le leader confirme au client… | après que les suiveurs ont reçu | immédiatement | après au moins un suiveur |
| Latence d'écriture | élevée | faible | moyenne |
| Perte à la panne du leader | aucune | possible (écritures non répliquées) | aucune si au moins 1 suiveur survit |
| Disponibilité en écriture | un suiveur lent bloque | non affectée | tolère un suiveur lent |
L'asynchrone est la valeur par défaut de nombreuses bases : rapide, mais l'objectif de point de reprise (RPO) (HEF-120) n'est pas nul.
Le retard de réplication (replication lag)
Avec l'asynchrone, les suiveurs sont en retard de quelques millisecondes à plusieurs secondes. Anomalies visibles pour l'utilisateur :
| Anomalie | Exemple |
|---|---|
| Lecture périmée | je modifie mon profil, je recharge, l'ancienne version s'affiche |
| Violation de « lire ses écritures » (read-your-writes) | mon inscription n'apparaît pas |
| Retour en arrière (lectures non monotones) | je vois la nouvelle valeur puis l'ancienne, selon le suiveur interrogé |
Remèdes : lire sur le leader après une écriture récente ; sessions collantes ; attendre que le suiveur ait atteint une position donnée du journal.
Le basculement (failover)
Quand le leader tombe : détecter la panne (délai : fausses alertes possibles), élire un nouveau leader (le suiveur le plus à jour), reconfigurer les clients, empêcher l'ancien leader de continuer à écrire s'il revient (split brain, mission 9). En asynchrone : les écritures non répliquées sont perdues (ou en conflit au retour de l'ancien leader).
Sans leader : les quorums
Dans un système à N réplicas, une écriture est considérée réussie quand W réplicas l'ont acceptée ; une lecture interroge R réplicas et prend la version la plus récente.
R + W > N ⟹ toute lecture voit au moins un réplica contenant la dernière écriture
Les deux ensembles (écrits, lus) se recoupent nécessairement. Exemples avec N = 3 : W = 2, R = 2 (tolère 1 panne) ; W = 3, R = 1 (écritures lentes, lectures rapides) ; W = 1, R = 1 (rapide, pas de garantie).
Mécanismes complémentaires : réparation à la lecture (read repair) renvoie la bonne version aux réplicas en retard ; anti-entropie compare les données en arrière-plan.
⚠️ Un quorum ne garantit pas, à lui seul, la linéarisabilité (cas limites : écritures concurrentes, horloges, quorums « lâches »). Il garantit de voir une version récente.
Conflits d'écriture
Sans leader unique, deux écritures concurrentes sur la même clé peuvent se produire :
| Stratégie | Principe | Risque |
|---|---|---|
| Le dernier gagne (LWW, horloge physique) | on garde l'écriture avec l'horodatage le plus grand | perd silencieusement des écritures ; dépend d'horloges |
| Versions vectorielles (mission 1) | détecter la concurrence, garder les « frères » | le client doit fusionner |
| Fusion automatique (CRDT) | types de données dont la fusion est mathématiquement sûre | restreint aux types adaptés |
CRDT : types de données répliqués sans conflit
Un CRDT (Conflict-free Replicated Data Type) a une opération de fusion qui est :
- commutative :
a ⊔ b = b ⊔ a; - associative ;
- idempotente :
a ⊔ a = a.
Alors, quel que soit l'ordre ou le nombre de fois où les états sont échangés, tous les réplicas convergent vers le même état.
| CRDT | Principe |
|---|---|
| Compteur G (croissant) | un compteur par réplica ; valeur = somme ; fusion = maximum par réplica |
| Compteur PN | deux compteurs G (ajouts, retraits) |
| Registre LWW | (valeur, horodatage) ; fusion = le plus grand horodatage |
| Ensemble G | union |
| Ensemble OR | ajouts et retraits identifiés par étiquettes uniques |
Utilisés pour : compteurs de « j'aime », panier, édition collaborative.
🧠 Astuce : pour chaque donnée répliquée, décide explicitement : que faire si deux copies diffèrent ? « On verra bien » est la pire réponse.
🔍 Exemple pas à pas
Problème : (1) simuler la réplication leader-suiveurs asynchrone, le retard, et la perte à un basculement, (2) démontrer par énumération que R + W > N garantit de voir la dernière écriture, (3) implémenter et vérifier par propriétés des CRDT.
import itertools, random
# ---------------- 1. réplication asynchrone et basculement ----------------
class Replica:
def __init__(self, nom): self.nom, self.journal, self.applique = nom, [], 0
def valeur(self, cle):
for k, v in reversed(self.journal):
if k == cle: return v
class Cluster:
def __init__(self, mode):
self.leader, self.suiveurs, self.mode = Replica("L"), [Replica("F1"), Replica("F2")], mode
self.en_vol = [] # entrées envoyées mais pas encore reçues par les suiveurs
def ecrire(self, cle, valeur):
self.leader.journal.append((cle, valeur))
entree = (cle, valeur)
if self.mode == "synchrone":
for f in self.suiveurs: f.journal.append(entree)
:
.en_vol.append(entree)
():
e .en_vol[:n]:
f .suiveurs: f.journal.append(e)
.en_vol = .en_vol[n:] n []
():
nouveau = .suiveurs[]
perdues = [e e .leader.journal e nouveau.journal]
nouveau, perdues
asyn = Cluster()
i (): asyn.ecrire(, )
asyn.repliquer()
(, asyn.suiveurs[].valeur(), )
nouveau, perdues = asyn.basculer()
()
asyn.suiveurs[].valeur() (perdues) ==
sync = Cluster()
i (): sync.ecrire(, )
_, perdues = sync.basculer()
perdues == []
():
reps = (N)
ecrits itertools.combinations(reps, W):
lus itertools.combinations(reps, R):
(ecrits) & (lus):
()
N, W, R [(, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , )]:
garantie = quorum_garantit_lecture_fraiche(N, W, R)
()
garantie == (R + W > N)
:
(): .replica, .c = replica, {}
(): .c[.replica] = .c.get(.replica, ) + n
(): (.c.values())
():
r, v autre.c.items(): .c[r] = (.c.get(r, ), v)
:
(): .valeur, .t, .replica = , (, ),
(): .fusionner_valeur(valeur, (t, replica))
():
tag > .t: .valeur, .t = valeur, tag
(): .fusionner_valeur(autre.valeur, autre.t)
rng = random.Random()
essai ():
reps = [CompteurG() i ()]
r reps:
_ (rng.randint(, )): r.incrementer(rng.randint(, ))
attendu = (v r reps v r.c.values())
_ ():
a, b = rng.sample(reps, ); a.fusionner(b)
a reps:
b reps: a.fusionner(b)
(r.valeur() == attendu r reps)
()
a, b = RegistreLWW(), RegistreLWW()
a.ecrire(, , ); b.ecrire(, , )
a1, b1 = RegistreLWW(), RegistreLWW()
a1.fusionner(a); a1.fusionner(b); b1.fusionner(b); b1.fusionner(a)
a1.valeur == b1.valeur ==
(, a1.valeur)
Lecture :
- Asynchrone : le client a reçu 10 confirmations, mais le suiveur n'avait que 7 écritures quand le leader est tombé : 3 écritures confirmées sont perdues après basculement. En synchrone, aucune perte — au prix d'une latence d'écriture plus élevée et d'une disponibilité plus fragile.
- Quorums : l'énumération de tous les choix de réplicas écrits et lus montre que la garantie « la lecture voit un réplica à jour » existe si et seulement si
R + W > N. Les configurations(3,1,1),(3,2,1),(5,2,3)n'ont pas la garantie. - CRDT : après des fusions dans un ordre quelconque (avec répétitions), les compteurs convergent vers la somme exacte. Le registre LWW converge aussi, mais perd l'une des deux écritures concurrentes : convergent n'est pas synonyme de « sans perte ».
✍️ À toi, avec aide (10 XP)
Un système réplique chaque donnée sur N = 5 réplicas, chacun disponible 99 % du temps (indépendamment).
- Pour
W = 3, R = 3(quorum majoritaire) : quelle est la probabilité qu'une écriture puisse être effectuée (au moins W réplicas disponibles) ? Même question pourW = 5(tous). - Quel est le nombre maximal de réplicas en panne que
W = 3, R = 3tolère ? - Pour
W = 1etR = 5, quel est le risque (pour la cohérence) ? Que gagne-t-on ?
💡 Indice 1
P(au moins k disponibles) = somme de la loi binomiale pour i ≥ k.
💡 Indice 2
math.comb(5, i) * 0.99**i * 0.01**(5-i).
💡 Indice 3
Avec R + W = 6 > 5, la garantie existe ; elle n'existe plus si W = 1 et R = 3.
✅ Réponse
from math import comb
def p_au_moins(k, n=5, p=0.99):
return sum(comb(n, i) * p**i * (1 - p)**(n - i) for i in range(k, n + 1))
print(f"W = 3 : disponibilité en écriture {p_au_moins(3):.8f}")
print(f"W = 5 : disponibilité en écriture {p_au_moins(5):.6f}")
assert p_au_moins(3) > 0.99999 and abs(p_au_moins(5) - 0.99 ** 5) < 1e-12
- W = 3 : probabilité ≈ 0,99999 (cinq neuf après la virgule : environ 5 minutes d'indisponibilité par an) ; W = 5 : ≈ 0,951 (seulement 95 %, soit plus de 18 jours d'indisponibilité par an !). Exiger tous les réplicas rend le système moins disponible qu'une seule machine.
W = 3, R = 3tolère 2 réplicas en panne (il en reste 3 pour constituer un quorum).- : , donc lire les 5 réplicas voit toujours la dernière écriture — mais (une panne la bloque). On gagne des (1 réplica suffit), on paie des . Si l'on baisse à , on perd la garantie ().
🚀 À toi, en solo (20 XP)
Magasin à quorum avec réparation à la lecture. Implémente un magasin clé-valeur à 5 réplicas :
- chaque valeur porte une version (compteur) ;
ecrire(cle, valeur, W)l'envoie à W réplicas disponibles choisis au hasard (graine fixée) ; si moins de W sont disponibles, l'écriture échoue sans rien appliquer partiellement de façon visible (ou documente le comportement) ; lire(cle, R)interroge R réplicas disponibles, renvoie la valeur de version maximale, et répare les réplicas lus qui sont en retard (read repair) ;- simule 1 000 opérations aléatoires avec pannes aléatoires de réplicas ; avec
R + W > N, vérifie qu'aucune lecture réussie ne renvoie une version plus ancienne que la dernière écriture réussie ; avecW = R = 1, mesure le taux de lectures périmées ; - mesure le taux d'échecs (indisponibilité) pour
W = R = 3contreW = R = 5avec 5 % de pannes par réplica.
✅ Pistes de correction
import random
class Magasin:
def __init__(self, n=5, graine=1):
self.n, self.rng = n, random.Random(graine)
self.reps = [{} for _ in range(n)] # cle -> (version, valeur)
self.en_panne = set(); self.derniere = {} # dernière écriture RÉUSSIE par clé (pour la vérification)
def disponibles(self): return [i for i in range(self.n) if i not in self.en_panne]
def ecrire(self, cle, valeur, W):
dispo = self.disponibles()
if len(dispo) < W: return False
version = self.derniere.get(cle, 0) + 1
for i in .rng.sample(dispo, W):
.reps[i][cle] = (version, valeur)
.derniere[cle] = version;
():
dispo = .disponibles()
(dispo) < R: (, ),
choisis = .rng.sample(dispo, R)
meilleur = ((.reps[i].get(cle, (, )) i choisis), key= x: x[])
i choisis:
.reps[i].get(cle, (, ))[] < meilleur[]: .reps[i][cle] = meilleur
meilleur,
():
rng, m = random.Random(graine), Magasin(graine=graine)
perimees = lectures = echecs =
op (n_ops):
m.en_panne = {i i () rng.random() < p_panne}
cle =
rng.random() < :
m.ecrire(cle, op, W): echecs +=
:
(version, _), ok = m.lire(cle, R)
ok: echecs += ;
lectures +=
version < m.derniere.get(cle, ): perimees +=
perimees / (lectures, ), echecs / n_ops
W, R [(, ), (, ), (, ), (, ), (, )]:
perimees, echecs = simuler(W, R)
()
R + W > : perimees ==
simuler(, )[] >
simuler(, )[] > * simuler(, )[]
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Confirmer au client avant la réplication, sans le dire | Écritures confirmées puis perdues après basculement | Choisir et documenter synchrone / semi-synchrone / asynchrone |
| Lire sur un suiveur juste après une écriture | L'utilisateur ne voit pas sa propre modification | Lire sur le leader ou attendre la position du journal |
| « Le dernier gagne » par horloge physique | Perte silencieuse d'écritures | Versions vectorielles, CRDT ou arbitrage explicite |
| Quorum mal calibré (R + W ≤ N) | Lectures périmées sans le savoir | Vérifier R + W > N ; tester par énumération |
🐉 Mini-boss (40 XP)
Base répliquée de HashBox. Construis une simulation d'une base clé-valeur répliquée avec trois modes (leader asynchrone, leader semi-synchrone, quorum 3/5) et un injecteur de pannes (arrêt du leader, partition, retard de réplication).
- implémente les trois modes avec le journal de réplication, le retard, le basculement ;
- mesure pour chaque mode, sur 200 scénarios aléatoires : écritures confirmées perdues, lectures périmées, lectures non monotones, disponibilité en écriture et en lecture, latence d'écriture simulée ;
- ajoute la garantie « lire ses écritures » (session collante) et mesure son effet sur le débit de lecture du leader ;
- ajoute un compteur CRDT pour le nombre d'inscriptions et un registre LWW pour le prix d'un cours, et montre sur un scénario de partition ce que chacun perd ou conserve ;
- rédige un tableau de décision : pour chaque type de donnée de HashBox (inscriptions, prix, compteur de vues, profil), le mode de réplication recommandé et pourquoi.
✅ Pistes de correction
Un bon travail : les trois modes mesurés sur les mêmes scénarios aléatoires; le semi-synchrone n'a aucune perte pour une panne simple du leader; l'asynchrone perd des écritures proportionnellement au retard; le quorum 3/5 n'a pas de lecture périmée avec R+W>N; tableau de décision cohérent (inscriptions et paiements : synchrone ou quorum ; compteurs de vues : CRDT; prix : leader unique ; profil : asynchrone avec lecture du leader après écriture).
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. En réplication asynchrone, quand le leader tombe :
- A. aucune écriture n'est jamais perdue
- B. les suiveurs sont toujours à jour
- C. des écritures déjà confirmées au client peuvent être perdues
2. La règle de quorum qui garantit de lire au moins un réplica à jour est :
- A. R + W > N
- B. R + W < N
- C. R = W = 1
3. Un CRDT converge parce que sa fusion est :
- A. aléatoire
- B. commutative, associative et idempotente
- C. irréversible
4. 🔁 Révision mission 04 : Une clé d'idempotence doit être :
- A. nouvelle à chaque tentative
- B. secrète et chiffrée
- C. la même pour toutes les relances d'une même intention
5. 🔁 Révision mission 04 : Pour qu'un consommateur de messages soit idempotent, on enregistre l'identifiant du message :
- A. dans la même transaction que l'effet
- B. dans un journal séparé, plus tard
- C. jamais
✅ Réponses
- C.
- A.
- B.
- C.
- A.
🪞 Je réfléchis (10 XP)
- Si la machine principale de ta base tombait maintenant, combien d'écritures confirmées pourrais-tu perdre ?
- Pour quelle donnée de ton système accepterais-tu une valeur légèrement périmée, et pour laquelle jamais ?
🎒 À retenir
- Réplication leader-suiveurs : synchrone (sûr, lent), asynchrone (rapide, perte possible), semi-synchrone.
- Retard de réplication : lectures périmées, lecture de ses écritures, retours en arrière.
- Basculement : détection, élection, empêcher l'ancien leader d'écrire.
- Quorum : R + W > N garantit de voir au moins un réplica à jour.
- CRDT : fusion commutative, associative, idempotente ; LWW perd des écritures.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Gardien des copies
← Mission 04 — Idempotence · Mission 06 — Partitionnement →
HEF-140 — Systèmes distribués

