Quand plusieurs machines doivent s'accorder sur une seule vérité malgré les pannes, il faut un consensus. Et quand on y renonce, il faut savoir précisément ce qu'on perd.
⏱️ Durée : environ 115 minutes · 🎓 Niveau : avancé · 🏅 Badge : Arbitre de la vérité
🎬 L'histoire
Deux clients de HashBox réservent la dernière place d'un cours en même temps, sur deux serveurs différents séparés par une coupure réseau. Chacun répond « confirmé ». Le lendemain, le cours a six inscrits pour cinq places. La direction demande : « Pourquoi n'avez-vous pas simplement refusé l'un des deux ? »
« Parce que pendant la coupure, aucun serveur ne pouvait savoir ce que faisait l'autre, dit Sam. Pour refuser l'un des deux, il aurait fallu choisir entre répondre quand même (et risquer l'incohérence) ou refuser de répondre (et perdre la disponibilité). Ce choix a un nom : CAP. Et il existe des algorithmes — Paxos, Raft — qui permettent à un groupe de machines de décider de façon sûre, tant que la majorité vit. »
Tu apprends le théorème CAP sans le caricaturer, les modèles de cohérence (linéarisable, séquentielle, causale, finale), le problème du consensus, et tu fais tourner une version simplifiée de Raft pour voir un leader se faire élire, des entrées se valider, et une partition ne pas casser la sûreté.
🎯 Ta mission
À la fin, je serai capable de :
- énoncer précisément le théorème CAP et PACELC
- distinguer linéarisabilité, cohérence séquentielle, causale, cohérence finale
- définir le consensus (accord, validité, terminaison) et citer l'impossibilité FLP
- comprendre élection de leader, réplication du journal et validation dans Raft
- vérifier les propriétés de sûreté d'une exécution avec partitions et pannes
🧩 Défi d'échauffement (5 XP)
Cinq amis doivent décider ensemble du restaurant du soir, uniquement par messages qui peuvent se perdre, et certains peuvent s'endormir. Règle : un restaurant n'est « choisi » que si la majorité (3 sur 5) l'a approuvé. Peut-on se retrouver avec deux restaurants « choisis » ? Que se passe-t-il si deux amis sont déconnectés ? Si trois sont déconnectés ?
💡 Le concept
Le théorème CAP, sans caricature
Trois propriétés d'un service de données répliqué :
| Lettre | Propriété | Signification précise |
|---|---|---|
| C | Cohérence (linéarisabilité) | toute lecture voit la dernière écriture, comme s'il n'y avait qu'une seule copie |
| A | Disponibilité | toute requête reçue par un nœud non défaillant obtient une réponse |
| P | Tolérance aux partitions | le système continue malgré des messages perdus entre nœuds |
CAP : en présence d'une partition, on ne peut pas avoir à la fois C et A. Comme les partitions arrivent (on ne choisit pas), le vrai choix est : pendant une partition, sacrifier la cohérence (AP) ou la disponibilité (CP).
- CP : les nœuds minoritaires refusent de répondre (ou répondent par une erreur) ; la vérité reste unique.
- AP : tous répondent, les copies divergent, on réconcilie après.
CAP n'est pas « choisis deux sur trois » à vie : sans partition, on peut avoir C et A ; et le choix se fait par opération, pas pour tout le système.
PACELC : et quand tout va bien ?
Partition → choisir A ou C ; Else (sinon) → choisir Latence ou Cohérence. Même sans panne, la cohérence forte coûte des allers-retours (latence). C'est le compromis de tous les jours.
Modèles de cohérence (du plus fort au plus faible)
| Modèle | Garantie | Exemple |
|---|---|---|
| Linéarisable | les opérations semblent atomiques et ordonnées selon le temps réel ; une lecture après une écriture terminée voit cette écriture | un compteur de stock, un verrou |
| Séquentielle | un ordre total unique, cohérent avec l'ordre de chaque client (pas nécessairement le temps réel) | journal global |
| Causale | si a → b, tous voient a avant b ; les concurrents peuvent être vus dans des ordres différents | commentaires et réponses |
| « Lire ses écritures » | un client voit ses propres écritures | profil utilisateur |
| Finale (eventual) | si plus d'écritures, les copies finissent par converger | DNS, compteurs de vues |
Plus le modèle est fort, plus il est simple à raisonner, et plus il coûte en latence et disponibilité.
Le problème du consensus
Plusieurs processus proposent des valeurs ; ils doivent décider une valeur unique.
| Propriété | Sens |
|---|---|
| Accord (agreement) | deux processus corrects ne décident jamais de valeurs différentes |
| Validité | la valeur décidée a été proposée par quelqu'un |
| Terminaison | tout processus correct décide finalement |
Impossibilité FLP (Fischer, Lynch, Paterson, 1985) : dans un système asynchrone où un seul processus peut tomber, aucun algorithme déterministe ne garantit à la fois accord et terminaison. En pratique, on garantit la sûreté toujours (accord, validité) et la vivacité (terminaison) quand le réseau est suffisamment calme (bornes de temps partielles, temporisations aléatoires).
Raft : un consensus compréhensible
Raft décompose le problème :
- Élection du leader : un seul leader par terme (numéro d'époque). Un suiveur qui n'entend plus de battements de cœur devient candidat, incrémente son terme, demande des votes. Un nœud vote une seule fois par terme. La majorité des voix fait un leader. Les délais d'élection sont aléatoires pour éviter les égalités.
- Réplication du journal : le leader reçoit les commandes, les ajoute à son journal, les envoie aux suiveurs (
AppendEntries). Une entrée est validée (committed) quand elle est stockée sur une majorité ; le leader l'applique et informe les autres. - Sûreté :
- un seul leader par terme ;
- un candidat dont le journal est moins à jour ne gagne pas les voix : toute entrée validée est dans le journal de tout futur leader ;
- un suiveur dont le journal diverge est corrigé (les entrées conflictuelles non validées sont supprimées).
stateDiagram-v2
[*] --> Suiveur
Suiveur --> Candidat: délai écoulé sans battement
Candidat --> Leader: majorité des voix
Candidat --> Suiveur: terme plus grand vu
Candidat --> Candidat: égalité, nouveau délai
Leader --> Suiveur: terme plus grand vu
Description du schéma : un nœud commence suiveur ; sans nouvelles du leader il devient candidat ; avec la majorité des voix il devient leader ; s'il voit un terme plus grand il redevient suiveur.
Tailles de grappe et pannes tolérées
Une grappe de N nœuds nécessite une majorité ⌊N/2⌋ + 1. Elle tolère N − majorité pannes :
| N | Majorité | Pannes tolérées |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 (pas mieux que 3 !) |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
On choisit un nombre impair. Une grappe ne tolère donc jamais la perte de la majorité : la minorité isolée ne peut ni élire de leader ni valider (choix CP).
Où trouve-t-on du consensus ?
Services de coordination (etcd, ZooKeeper, Consul) : configuration, élection de leader, verrous, découverte de services ; bases distribuées fortement cohérentes (journaux répliqués par Raft ou Paxos). On évite de l'employer pour le volume de données : on l'utilise pour les métadonnées et décisions critiques.
Vérifier la cohérence : la linéarisabilité
Un historique d'opérations (avec heures de début et de fin) est linéarisable s'il existe un ordre séquentiel des opérations, conforme au temps réel (si a finit avant que b commence, a précède b), et valide pour la spécification (un registre rend la dernière valeur écrite). Les outils de test (Jepsen, Knossos) vérifient cela sur des exécutions réelles avec pannes injectées.
🧠 Astuce : devant chaque donnée, demande : si deux copies divergent pendant une coupure, préfère-je répondre faux ou ne pas répondre ? Le stock d'un cours : ne pas répondre. Le nombre de vues : répondre.
🔍 Exemple pas à pas
Problème : faire tourner une version simplifiée de Raft (5 nœuds, réseau simulé avec délais et partitions) : élire un leader, valider des entrées, isoler le leader, voir la majorité élire un nouveau leader, constater qu'une entrée proposée à la minorité n'est jamais validée, réparer la partition, puis vérifier les propriétés de sûreté sur 60 scénarios aléatoires (partitions, pannes, redémarrages).
import random
from collections import defaultdict
class Noeud:
def __init__(self, id_, ids, rng):
self.id, self.ids, self.rng = id_, ids, rng
self.terme, self.vote_pour, self.log, self.commit = 0, None, [], 0 # état DURABLE : terme, vote, journal
self.redemarrer()
def redemarrer(self): # état volatil (perdu à la panne)
self.etat, self.votes, self.ecoule = "suiveur", set(), 0
self.delai = self.rng.randint(15, 30) # délai d'élection ALÉATOIRE
self.next_index, self.match_index, self.depuis_hb = {}, {}, 0
@property
def majorite(self): return (.ids) // +
:
():
.rng = random.Random(graine)
.ids = ((n))
.noeuds = {i: Noeud(i, .ids, .rng) i .ids}
.messages, .t = [],
.arretes, .groupes = (),
.leaders_par_terme = defaultdict()
():
a .arretes b .arretes:
.groupes (a g b g g .groupes)
():
.peut_communiquer(de, a):
.messages.append((.t + .rng.randint(, ), (msg, de=de, a=a)))
():
n.terme, n.etat, n.vote_pour, n.votes = terme, , , ()
():
n.etat, n.terme, n.vote_pour, n.votes, n.ecoule = , n.terme + , n., {n.},
n.delai = .rng.randint(, )
li, lt = (n.log), (n.log[-][] n.log )
p .ids:
p != n.: .envoyer(n., p, =, terme=n.terme, idx=li, tl=lt)
():
n.etat = ; .leaders_par_terme[n.terme].add(n.)
n.log.append((n.terme, ))
n.next_index = {p: (n.log) p .ids}; n.match_index = {p: p .ids}
n.depuis_hb =
():
p .ids:
p == n.:
prev = n.next_index[p] -
.envoyer(n., p, =, terme=n.terme, prev=prev, prev_t=(n.log[prev - ][] prev > ),
entrees=(n.log[prev:]), commit=n.commit)
():
m[] > n.terme m[] (, ): .devenir_suiveur(n, m[])
m[] == :
dernier = n.log[-][] n.log
journal_ok = m[] > dernier (m[] == dernier m[] >= (n.log))
accorde = m[] == n.terme n.vote_pour (, m[]) journal_ok
accorde: n.vote_pour, n.ecoule = m[],
.envoyer(n., m[], =, terme=n.terme, ok=accorde)
m[] == :
m[] > n.terme: .devenir_suiveur(n, m[])
n.etat == m[] == n.terme m[]:
n.votes.add(m[])
(n.votes) >= n.majorite: .devenir_leader(n)
m[] == :
m[] < n.terme: .envoyer(n., m[], =, terme=n.terme, ok=, =);
n.etat, n.ecoule = ,
m[] > ((n.log) < m[] n.log[m[] - ][] != m[]):
.envoyer(n., m[], =, terme=n.terme, ok=, =);
idx = m[]
e m[]:
idx +=
(n.log) >= idx n.log[idx - ][] != e[]: n.log[idx - :]
(n.log) < idx: n.log.append(e)
n.commit = (n.commit, (m[], m[] + (m[])))
.envoyer(n., m[], =, terme=n.terme, ok=, =m[] + (m[]))
m[] == :
m[] > n.terme: .devenir_suiveur(n, m[]);
n.etat != m[] != n.terme:
p = m[]
m[]:
n.match_index[p] = (n.match_index[p], m[]); n.next_index[p] = n.match_index[p] +
N ((n.log), n.commit, -):
n.log[N - ][] == n.terme + ( q .ids q != n. n.match_index[q] >= N) >= n.majorite:
n.commit = N;
:
n.next_index[p] = (, n.next_index[p] - )
():
.t +=
dus = [m t, m .messages t <= .t]; .messages = [(t, m) t, m .messages t > .t]
m dus:
m[] .arretes: .traiter(.noeuds[m[]], m)
n .noeuds.values():
n. .arretes:
n.etat == :
n.depuis_hb +=
n.depuis_hb >= : n.depuis_hb = ; .envoyer_entrees(n)
:
n.ecoule +=
n.ecoule >= n.delai: .demarrer_election(n)
():
_ (ticks): .tick()
():
c = [n n .noeuds.values() n.etat == n. .arretes]
(c, key= n: n.terme) c
():
l = .leader_actuel()
l :
l.log.append((l.terme, commande)); l., (l.log)
c = Cluster(, graine=)
c.run()
l = c.leader_actuel()
()
l ((ids) <= ids c.leaders_par_terme.values())
cmd (, , ): c.proposer(cmd)
c.run()
(, [(n., (n.log), n.commit) n c.noeuds.values()])
((n.log) == n.commit == n c.noeuds.values())
ancien = l.
c.groupes = [{ancien}, (c.ids) - {ancien}]
c.run()
nouveau = ((n n c.noeuds.values() n.etat == n. != ancien), key= n: n.terme)
()
nouveau.terme > c.noeuds[ancien].terme c.noeuds[ancien].etat ==
c.noeuds[ancien].log.append((c.noeuds[ancien].terme, ))
nouveau.log.append((nouveau.terme, ))
c.run()
()
c.noeuds[ancien].commit == nouveau.commit ==
c.groupes = ; c.run()
journaux = {(e[] e n.log) n c.noeuds.values()}
(, journaux)
(journaux) == ((journaux))
c.noeuds[ancien].etat ==
():
c = Cluster(, graine); rng = random.Random(graine * + )
valide, nb = {},
t (ticks):
t % == :
r = rng.random()
r < : k = rng.randint(, ); a = (rng.sample(c.ids, k)); c.groupes = [a, (c.ids) - a]
r < : c.groupes =
r < (c.arretes) < : c.arretes.add(rng.choice(c.ids))
r < c.arretes:
x = rng.choice((c.arretes)); c.arretes.discard(x); c.noeuds[x].redemarrer()
t % == c.proposer(): nb +=
c.tick()
n c.noeuds.values():
i (, n.commit + ):
e = n.log[i - ]
valide.setdefault(i, e) == e, (graine, t, )
((ids) <= ids c.leaders_par_terme.values()), (graine, )
(valide)
resultats = [scenario(g) g ()]
()
(resultats) >
Lecture :
- Un leader est élu par la majorité (au plus un par terme), puis les commandes sont répliquées et validées sur les 5 nœuds.
- Pendant la partition, la majorité (4 nœuds) élit un nouveau leader à un terme supérieur. L'ancien leader, isolé, se croit toujours leader mais ne peut rien valider : l'écriture proposée à la minorité reste à 4 entrées validées. C'est le choix CP : la minorité sacrifie la disponibilité pour préserver la vérité.
- À la réparation, l'ancien leader voit un terme supérieur, redevient suiveur, et son entrée non validée est écrasée : tous les journaux deviennent identiques.
- Sur 60 scénarios aléatoires (partitions, arrêts, redémarrages), aucune entrée validée ne change et il n'y a jamais deux leaders dans le même terme : les propriétés de sûreté tiennent, même quand la vivacité est parfois perdue (pas de leader pendant un moment).
✍️ À toi, avec aide (10 XP)
Pour des grappes Raft de 3, 4, 5, 6, 7 et 9 nœuds :
- calcule la majorité et le nombre de pannes tolérées ;
- explique pourquoi 4 nœuds ne valent pas mieux que 3 (et 6 pas mieux que 5) ;
- pour une grappe de 5 nœuds répartis en 3 centres (2 + 2 + 1), quelles pannes de centre sont tolérées ? Et si les centres sont répartis 3 + 1 + 1 ?
💡 Indice 1
Majorité = N // 2 + 1 ; pannes tolérées = N − majorité.
💡 Indice 2
Pour les centres : la grappe tolère la perte d'un centre si les nœuds restants forment une majorité.
💡 Indice 3
3 + 1 + 1 : perdre le gros centre fait perdre 3 nœuds sur 5.
✅ Réponse
for n in (3, 4, 5, 6, 7, 9):
maj = n // 2 + 1
print(f"N = {n} : majorité {maj}, pannes tolérées {n - maj}")
def tolere_centre(repartition):
n = sum(repartition); maj = n // 2 + 1
return [i for i, taille in enumerate(repartition) if n - taille >= maj]
print("2 + 2 + 1 :", tolere_centre([2, 2, 1]), "| 3 + 1 + 1 :", tolere_centre([3, 1, 1]))
assert [n - (n // 2 + 1) for n in (3, 4, 5, 6, 7, 9)] == [1, 1, 2, 2, 3, ]
tolere_centre([, , ]) == [, , ] tolere_centre([, , ]) == [, ]
🚀 À toi, en solo (20 XP)
Vérificateur de linéarisabilité. Écris est_lineaire(historique) pour un registre (lecture/écriture d'une valeur entière, valeur initiale 0). Chaque opération a un client, un type (ecrire(v) ou lire() → v), une heure de début et une heure de fin.
- recherche en profondeur : à chaque étape, choisis une opération dont aucune autre opération restante n'a fini avant son début (elle peut être ordonnée maintenant), applique-la (lecture : la valeur lue doit égaler l'état courant) ;
- teste cinq historiques :
- (a) écriture(1) [0,2] ; lecture→1 [3,4] : linéarisable ;
- (b) écriture(1) [0,2] ; lecture→0 [3,4] : non linéarisable (lecture périmée après une écriture terminée) ;
- (c) écriture(1) [0,5] ; lecture→0 [1,2] ; lecture→1 [3,4] : linéarisable (lecture concurrente de l'écriture) ;
- (d) écriture(1) [0,5] ; lecture→1 [1,2] ; lecture→0 [3,4] : non linéarisable (la valeur « revient en arrière ») ;
- (e) deux écritures concurrentes (1 et 2) et deux lectures successives qui voient 2 puis 1 : à toi de décider, avec le vérificateur ;
- génère 300 historiques aléatoires d'un registre réellement atomique (exécution séquentielle simulée avec durées aléatoires) et vérifie qu'ils sont tous linéarisables ; puis injecte des lectures périmées et mesure la part détectée.
✅ Pistes de correction
import random
from functools import lru_cache
def est_lineaire(operations):
ops = tuple(operations) # (client, type, valeur, debut, fin)
@lru_cache(maxsize=None)
def chercher(restantes, etat):
if not restantes: return True
for i in restantes:
_, type_, valeur, debut, _ = ops[i]
# i peut passer maintenant si aucune autre opération restante n'a FINI avant son début
if any(ops[j][4] < debut for j in restantes if j != i): continue
if type_ == "w": nouvel_etat = valeur
else:
if valeur != etat: continue
nouvel_etat = etat
if chercher(restantes - {i}, nouvel_etat): return True
return False
return chercher(frozenset(range(len(ops))), )
W = c, v, d, f: (c, , v, d, f)
R = c, v, d, f: (c, , v, d, f)
a = [W(, , , ), R(, , , )]
b = [W(, , , ), R(, , , )]
c_ = [W(, , , ), R(, , , ), R(, , , )]
d = [W(, , , ), R(, , , ), R(, , , )]
e = [W(, , , ), W(, , , ), R(, , , ), R(, , , )]
[est_lineaire(x) x (a, b, c_, d, e)] == [, , , , ]
()
():
etat, t, ops = , , []
i (n_ops):
t += rng.uniform(, ); instant = t
client =
debut, fin = instant - rng.uniform(, ), instant + rng.uniform(, )
rng.random() < :
v = rng.randint(, ); etat = v; ops.append((client, , v, debut, fin))
:
ops.append((client, , etat, debut, fin))
ops
rng = random.Random()
(est_lineaire(historique_atomique(rng)) _ ())
()
detectees = total =
_ ():
h = historique_atomique(rng)
lectures = [i i, o (h) o[] == ]
lectures:
i = rng.choice(lectures); o = h[i]
h[i] = (o[], , (o[] + rng.randint(, )) % , o[], o[])
total += ; detectees += ( est_lineaire(h))
()
detectees / total >
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| « CAP : choisis deux sur trois » | Simplification fausse : P n'est pas optionnel | Pendant une partition : C ou A, opération par opération |
| Confondre disponibilité et cohérence | Réponses rapides mais fausses, ou refus injustifiés | Décider par donnée : stock (C), compteur de vues (A) |
| Grappe de consensus en nombre pair, ou répartie sur un seul site | Pas de gain, ou perte de majorité sur panne d'un site | Nombre impair, centres équilibrés |
| Utiliser le consensus pour de gros volumes | Latence et débit insuffisants | Consensus pour les métadonnées et décisions critiques |
🐉 Mini-boss (40 XP)
Banc d'essai de consensus. Étends le mini-Raft de la mission :
- ajoute des clients qui envoient des commandes avec identifiant (idempotence, mission 4) et reçoivent une confirmation uniquement quand l'entrée est validée ;
- implémente une machine à états « compteur de places par cours » appliquée à partir des entrées validées, avec capacité maximale ;
- injecte pannes, partitions, pertes et doublons de messages (réseau configurable) ;
- vérifie les invariants sur 200 graines : un seul leader par terme ; les entrées validées ne changent jamais ; aucun cours n'est surbooké ; aucune commande confirmée n'est perdue ; chaque commande est appliquée au plus une fois malgré les relances ;
- mesure la vivacité : délai d'élection moyen, proportion de commandes confirmées, durée d'indisponibilité pendant une partition ;
- compare avec une variante sans consensus (deux nœuds acceptent chacun les inscriptions pendant la partition) et montre le surbooking ;
- rédige un tableau CAP : pour chaque scénario, ce que le système a choisi (C ou A) et ce que cela a coûté.
✅ Pistes de correction
Un bon travail : une file de commandes avec identifiants, des clients qui relancent tant qu'ils n'ont pas de confirmation, une machine à états appliquée sur commit avec déduplication par identifiant; invariants vérifiés dans un moniteur; mesure de la disponibilité (la minorité ne confirme rien, la majorité oui); variante AP montrant le surbooking en cas de partition; tableau CAP clair. Le message clé : Raft garantit la sûreté même quand la vivacité est suspendue; le prix de la cohérence forte est l'indisponibilité de la minorité.
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Pendant une partition réseau, un système CP :
- A. refuse de répondre côté minoritaire pour préserver la cohérence
- B. répond partout avec des copies divergentes
- C. ignore la partition
2. Dans Raft, une entrée est validée (committed) quand elle est stockée sur :
- A. tous les nœuds
- B. une majorité de nœuds
- C. un seul nœud
3. Une grappe de 5 nœuds de consensus tolère :
- A. 3 pannes
- B. 5 pannes
- C. 2 pannes
4. 🔁 Révision mission 06 : Avec hash(clé) mod N, ajouter un serveur :
- A. déplace la majorité des clés
- B. ne déplace aucune clé
- C. déplace exactement 1/N des clés
5. 🔁 Révision mission 06 : Le hachage cohérent avec nœuds virtuels :
- A. supprime le besoin de répliquer
- B. limite les déplacements à environ 1/(N+1) des clés et équilibre la charge
- C. empêche toute panne
✅ Réponses
- A.
- B.
- C.
- A.
- B.
🪞 Je réfléchis (10 XP)
- Pour quelle donnée de ton système préférerais-tu une erreur à une réponse potentiellement fausse ?
- Combien de tes services dépendent d'une seule instance « qui ne tombe jamais » ?
🎒 À retenir
- CAP : pendant une partition, choisir C ou A ; PACELC ajoute latence contre cohérence.
- Modèles : linéarisable, séquentiel, causal, finale.
- Consensus : accord, validité, terminaison ; FLP en asynchrone pur.
- Raft : élection (un leader par terme), journal répliqué, validation à la majorité.
- Majorité nécessaire : nombre impair de nœuds, centres équilibrés.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Arbitre de la vérité
← Mission 06 — Partitionnement · Mission 08 — Files et événements →
HEF-140 — Systèmes distribués

