Cohérence & consensus

Dans un système distribué, tout peut mal tourner : des paquets perdus, réordonnés, dupliqués ou arbitrairement retardés ; des horloges approximatives ; des nœuds qui se figent (par exemple à cause du ramasse-miettes) ou plantent à tout instant. La façon la plus simple de gérer ces fautes serait de faire échouer le service entier et d'afficher une erreur. Quand cette solution est inacceptable, il faut tolérer les fautes, c'est-à-dire continuer à fonctionner correctement même si un composant interne est défaillant.

La meilleure méthode, comme avec les transactions du chapitre précédent, consiste à trouver des abstractions générales aux garanties fortes, à les implémenter une fois, puis à laisser les applications s'appuyer dessus. L'une des plus importantes est le consensus (consensus) : amener tous les nœuds à se mettre d'accord sur quelque chose. Atteindre de manière fiable un consensus malgré les fautes réseau et les pannes de processus est un problème étonnamment subtil — et ce chapitre montre que la linéarisabilité, l'ordre causal, le broadcast à ordre total, le commit atomique et le consensus sont en réalité profondément liés les uns aux autres.

La linéarisabilité : faire comme s'il n'y avait qu'une copie

La plupart des bases répliquées offrent au moins la cohérence à terme (eventual consistency) : si vous cessez d'écrire et attendez assez longtemps, toutes les répliques finissent par converger. C'est une garantie très faible — elle ne dit rien sur quand la convergence aura lieu, et entre-temps une lecture peut renvoyer n'importe quoi. Si vous écrivez une valeur puis la relisez immédiatement, rien ne garantit que vous la reverrez, car la lecture peut être routée vers une réplique en retard.

La linéarisabilité (linearizability) — aussi appelée cohérence atomique, forte, immédiate ou externe — donne l'illusion qu'il n'existe qu'une seule copie des données, sur laquelle toutes les opérations sont atomiques. Dès qu'un client termine une écriture avec succès, tous les clients qui lisent doivent voir la valeur écrite : c'est une garantie de fraîcheur (recency guarantee). La valeur lue est la plus récente, jamais une version périmée venue d'un cache ou d'une réplique à la traîne.

Concrètement, on imagine qu'à un instant précis (entre le début et la fin d'une écriture) la valeur bascule atomiquement de l'ancienne à la nouvelle. Si une lecture renvoie la nouvelle valeur, toutes les lectures suivantes — sur le même client ou un autre — doivent aussi la renvoyer, même si l'écriture n'est pas encore terminée pour son auteur. C'est l'histoire d'Alice et Bob suivant la finale de la Coupe du monde : Bob recharge sa page après avoir entendu Alice annoncer le score ; voir un résultat périmé viole la linéarisabilité, car sa requête est causalement postérieure à celle d'Alice.

Ne confondez pas linéarisabilité et sérialisabilité (serializability). La sérialisabilité est une propriété d'isolation des transactions : elles se comportent comme si elles s'étaient exécutées dans un ordre séquentiel. La linéarisabilité est une garantie de fraîcheur sur les lectures et écritures d'un objet unique (un registre) ; elle ne regroupe pas les opérations en transactions. Une base qui offre les deux fournit la strict serializability. À l'inverse, l'isolation par instantané sérialisable (SSI) n'est pas linéarisable : elle lit depuis un instantané cohérent, qui par construction ignore les écritures plus récentes.

À quoi sert la linéarisabilité

Quelques situations l'exigent réellement pour fonctionner correctement.

• Verrouillage et élection de leader. Un système à réplication mono-leader doit garantir qu'il n'y a qu'un seul leader (sinon, split brain et perte de données). On élit souvent le leader via un verrou : le premier nœud qui l'acquiert devient leader. Ce verrou doit être linéarisable — tous les nœuds doivent s'accorder sur son propriétaire. Les services de coordination comme ZooKeeper et etcd implémentent ces verrous.
• Contraintes d'unicité. Un nom d'utilisateur ou un e-mail doit identifier un seul compte ; deux personnes ne doivent pas réserver le même siège. Imposer la contrainte à l'écriture revient à acquérir un « verrou » sur la valeur choisie, et réclame la linéarisabilité.
• Dépendances temporelles entre canaux. Si un serveur web dépose une image dans un stockage de fichiers puis poste un ordre de redimensionnement dans une file de messages, et que le redimensionneur lit ensuite l'image, un stockage non linéarisable ouvre une condition de course : la file peut « doubler » la réplication interne, et le redimensionneur traiter une vieille version — laissant les deux images incohérentes pour toujours.

Pour les contraintes d'unicité, on peut parfois s'en passer : envoyer un e-mail d'excuse au perdant d'un doublon, commander du stock supplémentaire, ou facturer des agios. Cette transaction compensatoire (compensating transaction) fait souvent déjà partie des processus métier.

Comment l'implémenter, et à quel prix

Toutes les méthodes de réplication ne sont pas linéarisables.

Méthode de réplication	Linéarisable ?	Pourquoi
Mono-leader	Potentiellement	Lectures sur le leader ou des followers synchrones ; faux si snapshot isolation, ou si un leader « fantôme » continue de servir.
Algorithmes de consensus	Oui	Protections contre split brain et répliques périmées (ZooKeeper, etcd).
Multi-leader	Non	Écritures concurrentes sur plusieurs nœuds, répliquées de façon asynchrone, donc conflictuelles.
Sans leader (Dynamo)	Probablement pas	Le LWW basé sur les horloges et les quorums approximatifs cassent la fraîcheur ; même un quorum strict (w + r > n) peut échouer.

Même un quorum strict ne suffit pas : avec des délais réseau variables, un lecteur A peut voir la nouvelle valeur tandis qu'un lecteur B, dont la requête commence après celle de A, voit encore l'ancienne. On peut rendre les quorums Dynamo linéarisables (lecture-réparation synchrone, relecture d'un quorum avant écriture), mais au prix de la performance — et un compare-and-set linéarisable, lui, exige un algorithme de consensus.

Surtout, la linéarisabilité est lente — tout le temps, pas seulement pendant une panne. La RAM d'un CPU multicœur moderne n'est même pas linéarisable (caches et tampons d'écriture par cœur) : la raison y est la performance, pas la tolérance aux fautes. Attiya et Welch ont prouvé que le temps de réponse des lectures et écritures linéarisables est au moins proportionnel à l'incertitude des délais réseau. Aucun algorithme plus rapide n'existe ; c'est un compromis majeur pour les systèmes sensibles à la latence.

Ordre et causalité

La linéarisabilité impose un ordre total : toutes les opérations sont sur une seule ligne de temps, et pour deux opérations quelconques on peut toujours dire laquelle a eu lieu en premier. C'est puissant, mais coûteux. Un ordre plus faible suffit souvent : l'ordre causal (causal order).

La causalité, c'est la relation « est arrivé avant (happens-before) » : si A est arrivé avant B, alors B a pu connaître A, s'appuyer sur A ou en dépendre. La cause précède l'effet ; la question précède la réponse ; un message est envoyé avant d'être reçu. Quand deux opérations ne sont liées ni dans un sens ni dans l'autre, elles sont concurrentes (concurrent) — et donc incomparables.

C'est la différence entre ordre total et ordre partiel (partial order). Les nombres entiers sont totalement ordonnés ; les ensembles mathématiques ne le sont pas ({a, b} n'est ni plus grand ni plus petit que {b, c}). De même :

• Linéarisabilité → ordre total : pas d'opérations concurrentes, une seule ligne de temps.
• Causalité → ordre partiel : certaines opérations sont ordonnées, d'autres incomparables. L'historique ressemble au graphe de versions de git, avec branches et fusions.

La linéarisabilité implique la causalité : tout système linéarisable préserve correctement la causalité, sans rien faire de spécial. C'est ce qui le rend si simple à comprendre. Mais la bonne nouvelle est qu'un terrain intermédiaire existe : un système peut être causalement cohérent sans payer le prix de la linéarisabilité. La cohérence causale est même le modèle le plus fort qui ne ralentisse pas sous l'effet des délais réseau et reste disponible en cas de panne — CAP ne s'y applique pas. Bien des systèmes qui semblent exiger la linéarisabilité n'ont en fait besoin que de cohérence causale.

Numéros de séquence et horloges de Lamport

Suivre toutes les dépendances causales explicitement est coûteux. On utilise plutôt des numéros de séquence (sequence numbers) ou des horodatages issus d'une horloge logique (logical clock) — un compteur incrémenté à chaque opération, et non une horloge murale. Ces numéros sont compacts et fournissent un ordre total que l'on peut rendre cohérent avec la causalité : si A précède causalement B, A reçoit un numéro plus petit.

Avec un leader unique, c'est trivial : le journal de réplication incrémente un compteur. Sans leader (multi-leader, sans leader, partitionné), les générateurs naïfs (compteurs pairs/impairs, horodatages physiques, blocs préalloués) sont plus rapides mais incohérents avec la causalité. La solution, proposée par Leslie Lamport en 1978, est l'horloge de Lamport (Lamport timestamp) : un couple (compteur, identifiant de nœud). L'idée clé : chaque nœud et chaque client retient le compteur maximal vu, l'inclut dans chaque requête, et avance son propre compteur si le maximum reçu est plus grand.

// Horloge de Lamport : un total order cohérent avec la causalité.
type Timestamp = { counter: number; nodeId: number };

class LamportClock {
  private counter = 0;
  constructor(private readonly nodeId: number) {}

  // Événement local : on incrémente avant d'estampiller.
  tick(): Timestamp {
    this.counter += 1;
    return { counter: this.counter, nodeId: this.nodeId };
  }

  // Réception : on adopte le maximum vu, puis on incrémente.
  receive(remote: Timestamp): Timestamp {
    this.counter = Math.max(this.counter, remote.counter) + 1;
    return { counter: this.counter, nodeId: this.nodeId };
  }
}

// Ordre total : d'abord le compteur, l'identifiant départage.
function before(a: Timestamp, b: Timestamp): boolean {
  return a.counter < b.counter
    || (a.counter === b.counter && a.nodeId < b.nodeId);
}

Attention : les horloges de Lamport ne sont pas des vecteurs de versions (version vectors). Ces derniers savent dire si deux opérations sont concurrentes ou causalement dépendantes ; les horloges de Lamport imposent toujours un ordre total et perdent cette information.

Le broadcast à ordre total

Un ordre total cohérent avec la causalité ne suffit pourtant pas à tout. Pour garantir l'unicité d'un nom d'utilisateur, comparer des horodatages après coup fonctionne, mais au moment où un nœud reçoit une demande, il ne sait pas si un autre nœud est en train d'en créer un identique avec un horodatage plus petit. Il manque de savoir quand l'ordre est définitif. Vérifier auprès de tous les autres nœuds paralyserait le système dès qu'un seul est injoignable.

C'est exactement ce que résout le broadcast à ordre total (total order broadcast), aussi appelé broadcast atomique. C'est un protocole d'échange de messages garantissant deux propriétés, même en cas de fautes :

• Livraison fiable : aucun message perdu ; livré à un nœud, il est livré à tous.
• Livraison totalement ordonnée : les messages sont livrés à chaque nœud dans le même ordre.

Crucialement, l'ordre est figé au moment de la livraison : on ne peut pas insérer rétroactivement un message à une position antérieure si des messages suivants ont déjà été livrés. C'est ce qui le rend plus fort que l'ordonnancement par horodatage.

Une autre façon de le voir : le broadcast à ordre total revient à créer un journal (log) — livrer un message équivaut à ajouter une ligne au journal, que tous les nœuds lisent dans le même ordre. C'est précisément ce qu'il faut pour la réplication par machine à états (state machine replication) : si chaque message est une écriture et que toutes les répliques les appliquent dans le même ordre, elles restent cohérentes. ZooKeeper et etcd implémentent du broadcast à ordre total ; dans ZooKeeper, le numéro de séquence monotone du journal s'appelle le zxid et sert de jeton de barrière (fencing token).

On peut bâtir un stockage linéarisable par-dessus le broadcast à ordre total : pour réserver un nom, on ajoute un message au journal, on attend qu'il revienne, et si le premier message pour ce nom est le sien, on a gagné — sinon on abandonne. Tous les nœuds, voyant les messages dans le même ordre, s'accordent sur le gagnant. Réciproquement, un registre linéarisable doté d'un increment-and-get atomique permet de construire le broadcast à ordre total. Les deux problèmes sont équivalents — et équivalents au consensus. C'est une observation aussi profonde que surprenante.

Commit atomique distribué : la validation à deux phases

Quand une transaction touche plusieurs nœuds (base partitionnée, index secondaire distribué), un nouveau problème surgit : elle peut réussir sur certains et échouer sur d'autres. Pour préserver l'atomicité (au sens ACID), tous les nœuds doivent s'accorder sur l'issue — tous valident, ou tous annulent. Envoyer un simple ordre de commit à chacun ne suffit pas : un commit peut réussir ici et échouer là, et une fois validé sur un nœud, il est irrévocable. C'est l'instance du consensus appelée commit atomique (atomic commit).

La validation à deux phases (two-phase commit, 2PC) est l'algorithme classique. Attention : elle n'a rien à voir avec le verrouillage à deux phases (2PL), qui assure l'isolation. La 2PC introduit un coordinateur (coordinator), souvent une bibliothèque dans le processus applicatif. Les nœuds de la base sont les participants.

Phase 1 — Préparation
  Coordinateur ── prepare ──▶ Participant 1   "peux-tu valider ?"
  Coordinateur ── prepare ──▶ Participant 2
  Participant 1 ── "yes" ───▶ Coordinateur    (écrit tout sur disque,
  Participant 2 ── "yes" ───▶ Coordinateur     vérifie les contraintes,
                                               renonce au droit d'annuler)
Phase 2 — Validation (point de non-retour)
  Coordinateur écrit "COMMIT" dans son journal  ◀── point de commit
  Coordinateur ── commit ──▶ Participant 1
  Coordinateur ── commit ──▶ Participant 2      (retransmis jusqu'au succès)

Le protocole repose sur deux points de non-retour. D'abord, quand un participant répond « yes », il promet de pouvoir valider sans erreur — il a écrit toutes les données sur disque et renonce à son droit d'annuler (le coordinateur peut encore décider d'annuler). Ensuite, dès que le coordinateur écrit sa décision dans son journal (le point de commit), elle est définitive : il retransmettra le commit indéfiniment jusqu'à succès. Ce système de promesses est ce qui rend la 2PC atomique, là où un commit en une seule phase ne l'est pas.

Le standard XA (eXtended Architecture, 1991) étend la 2PC aux technologies hétérogènes (bases de différents éditeurs, courtiers de messages). C'est une API C, pas un protocole réseau, exposée en Java via JTA. Elle permet par exemple le traitement exactement une fois (exactly-once) : valider atomiquement l'accusé de réception d'un message et les écritures de son traitement. Mais XA hérite de tous les défauts de la 2PC, aggravés. Le coordinateur est lui-même une sorte de base : s'il n'est pas répliqué, c'est un point de défaillance unique. XA, étant le plus petit dénominateur commun, ne détecte pas les interblocages entre systèmes et ne fonctionne pas avec SSI. Les implémentations sont lentes (jusqu'à plus de 10× pour MySQL) à cause des fsync et des allers-retours réseau supplémentaires. Surtout, la 2PC exige que tous les participants répondent : elle a tendance à amplifier les pannes, à rebours de notre objectif de tolérance aux fautes.

Le consensus tolérant aux fautes

Le commit atomique nous a menés au cœur du sujet. Formellement, dans le consensus, un ou plusieurs nœuds proposent des valeurs et l'algorithme en décide une. Un algorithme correct satisfait quatre propriétés :

Propriété	Énoncé	Rôle
Accord uniforme (uniform agreement)	Deux nœuds ne décident jamais différemment.	Cœur du consensus : même résultat partout.
Intégrité (integrity)	Aucun nœud ne décide deux fois.	La décision est irrévocable.
Validité (validity)	Si on décide v, alors v a été proposée par un nœud.	Exclut les solutions triviales (décider toujours null).
Terminaison (termination)	Tout nœud qui ne plante pas finit par décider.	Tolérance aux fautes : le système doit progresser.

Les trois premières sont des propriétés de sûreté ; la terminaison est une propriété de vivacité. Sans tolérance aux fautes, satisfaire les trois premières est facile : on désigne un nœud « dictateur ». Mais s'il tombe, plus aucune décision — c'est exactement le drame de la 2PC quand le coordinateur plante. La terminaison formalise l'exigence de progrès malgré les pannes ; elle suppose qu'une majorité stricte de nœuds fonctionne. La plupart des implémentations garantissent toujours la sûreté, même si une majorité tombe : une grande panne peut bloquer le système, mais jamais le corrompre.

Vous avez peut-être entendu parler du résultat d'impossibilité FLP (Fischer, Lynch, Paterson) : aucun algorithme déterministe ne peut garantir le consensus si un nœud risque de planter. Or nous discutons d'algorithmes — pourquoi ? Parce que FLP suppose un modèle asynchrone pur, sans horloges ni délais d'attente. Dès que l'algorithme peut utiliser des délais d'attente (timeouts) pour suspecter un nœud planté (même à tort parfois), ou même de simples nombres aléatoires, le consensus redevient soluble. FLP a une grande portée théorique, mais en pratique on atteint le consensus.

Des algorithmes, et leur lien avec le broadcast à ordre total

Les algorithmes de consensus tolérants aux fautes les plus connus sont Viewstamped Replication (VSR), Paxos, Raft et Zab. Plutôt que de décider une seule valeur, ils décident d'une séquence de valeurs — ce qui en fait des algorithmes de broadcast à ordre total. Une exécution de broadcast à ordre total revient en effet à plusieurs tours de consensus : à chaque tour, les nœuds proposent le prochain message et décident lequel livrer ensuite.

• L'accord garantit que tous livrent les mêmes messages dans le même ordre.
• L'intégrité garantit l'absence de doublons.
• La validité garantit l'absence de corruption ou de fabrication.
• La terminaison garantit l'absence de perte.

VSR, Raft et Zab implémentent directement le broadcast à ordre total (plus efficace) ; pour Paxos, cette optimisation s'appelle Multi-Paxos.

Un paradoxe se présente alors : le broadcast à ordre total ressemble à la réplication mono-leader, qui exige un leader ; mais pour élire un leader sans split brain, il faut le consensus. Pour élire un leader, il faut d'abord un leader ? La sortie est le numéro d'époque (epoch number) — appelé ballot number dans Paxos, view number dans VSR, term number dans Raft. Ces protocoles ne garantissent pas qu'un leader est unique pour toujours, mais qu'il est unique au sein de chaque époque. Chaque fois que le leader courant est soupçonné mort, un vote démarre avec une époque incrémentée ; en cas de conflit, le leader d'époque la plus élevée l'emporte.

Avant de décider quoi que ce soit, un leader vérifie qu'aucun leader d'époque supérieure n'existe, en collectant les votes d'un quorum (une majorité). Un nœud ne vote pour une proposition que s'il n'a connaissance d'aucun leader d'époque plus élevée. Puisqu'il faut une majorité pour devenir leader et une majorité pour décider, les deux quorums se recoupent : au moins un votant aura vu une éventuelle élection plus récente. Cela ressemble superficiellement à la 2PC, mais la différence est capitale : le consensus n'exige qu'une majorité (pas l'unanimité) et définit un processus de reprise garantissant la sûreté après l'élection.

Services de coordination : ZooKeeper et etcd

ZooKeeper et etcd se décrivent comme des « magasins clé-valeur distribués » ou des « services de coordination ». Pourquoi tant d'efforts pour implémenter un algorithme de consensus, s'ils ressemblent à des bases ? Parce qu'on ne les utilise généralement pas directement : HBase, Hadoop YARN, Kafka et bien d'autres s'appuient dessus en arrière-plan. Ils détiennent peu de données, qui tiennent en mémoire, répliquées par broadcast à ordre total. Modelé sur le service de verrous Chubby de Google, ZooKeeper combine un ensemble de fonctionnalités précieuses :

• Opérations atomiques linéarisables : un compare-and-set permet d'implémenter un verrou — un seul gagnant garanti, même en cas de panne. Le verrou est généralement un bail (lease) à expiration, libéré si le client défaille.
• Ordre total des opérations : chaque opération reçoit un identifiant monotone (zxid) servant de jeton de barrière (fencing token), pour empêcher un client en pause de corrompre une ressource après avoir cru tenir le verrou.
• Détection de défaillance : les clients tiennent une session longue avec battements de cœur (heartbeats). Si les battements cessent au-delà du délai de session, ZooKeeper déclare la session morte et supprime ses nœuds éphémères (ephemeral nodes).
• Notifications d'événements : un client peut surveiller (watch) les valeurs d'un autre, et apprendre ainsi qu'un nœud rejoint le cluster ou défaille, sans interrogation répétée.

Seules les opérations atomiques linéarisables exigent vraiment le consensus ; c'est leur combinaison qui rend ZooKeeper si utile. On l'emploie pour allouer le travail aux nœuds : élire un primaire parmi plusieurs instances, décider quelle partition assigner à quel nœud, rééquilibrer la charge quand des nœuds arrivent ou partent — automatiquement, sans intervention humaine. ZooKeeper tourne sur un nombre fixe de nœuds (3 ou 5) et y fait ses votes majoritaires, tout en servant un grand nombre de clients : il externalise la coordination. Ses données changent lentement (« le nœud 10.1.1.23 est leader de la partition 7 »), pas à la cadence de l'état applicatif.

ZooKeeper, etcd et Consul servent aussi à la découverte de services (service discovery) : trouver l'adresse IP d'un service dans un environnement cloud où les machines vont et viennent. Mais la découverte de services n'exige pas le consensus — le DNS, avec son cache multi-couches, fait l'affaire et tolère des résultats un peu périmés. C'est l'élection de leader, elle, qui exige le consensus. Enfin, couplée au consensus, la détection de défaillance fournit un service d'appartenance (membership service) : un accord sur les nœuds vivants du cluster, indispensable par exemple pour « choisir le membre actif de plus petit numéro » comme leader.

Tout système n'a pas besoin de consensus, cependant : les réplications multi-leader et sans leader s'en passent volontairement. Les conflits qu'elles produisent sont la rançon de cette absence de consensus global — mais c'est parfois un compromis acceptable, à condition d'apprendre à vivre sans linéarisabilité.

À retenir

• La linéarisabilité fait « comme s'il n'y avait qu'une seule copie », mise à jour atomiquement : c'est une garantie de fraîcheur, indispensable aux verrous, à l'élection de leader et aux contraintes d'unicité — mais elle est lente en permanence, car son coût croît avec l'incertitude des délais réseau.
• Le théorème CAP, bien compris, dit « cohérent (linéarisable) OU disponible quand le réseau est partitionné » — ni « 2 sur 3 », ni un guide de conception.
• L'ordre causal est un ordre partiel plus faible que l'ordre total, mais souvent suffisant ; les horloges de Lamport fournissent un ordre total cohérent avec la causalité, sans dire si deux opérations sont concurrentes.
• Le broadcast à ordre total livre les mêmes messages dans le même ordre à tous : c'est un journal répliqué, équivalent au consensus, et le socle d'un stockage linéarisable.
• La validation à deux phases (2PC) assure le commit atomique distribué via un coordinateur et un système de promesses, mais elle bloque si le coordinateur tombe (transactions en doute, verrous tenus) et amplifie les pannes — d'où la mauvaise réputation de XA.
• Le consensus (accord, intégrité, validité, terminaison) est résolu en pratique par Raft, Paxos/Multi-Paxos, Zab et VSR via numéros d'époque et quorums majoritaires ; ZooKeeper et etcd l'externalisent pour offrir verrous avec fencing, élection de leader et appartenance.