La réplication

Répliquer (replication), c'est garder une copie des mêmes données sur plusieurs machines reliées par un réseau. Pourquoi se donner cette peine ? Kleppmann avance trois motivations. Rapprocher les données de vos utilisateurs (proximité géographique) pour réduire la latence. Permettre au système de continuer à fonctionner même si certaines de ses parties tombent en panne, donc augmenter la disponibilité (availability). Et répartir les requêtes de lecture sur davantage de machines pour accroître le débit en lecture (read throughput).

Si les données ne changeaient jamais, la réplication serait triviale : on copierait tout une fois et ce serait fini. Toute la difficulté tient à la gestion des changements. Ce chapitre parcourt les trois familles d'algorithmes utilisées par la quasi-totalité des bases de données distribuées — réplication à leader unique (single-leader), multi-leader et sans leader (leaderless) — et leurs compromis : synchrone ou asynchrone, comment traiter les réplicas en panne, et quelles incohérences l'utilisateur risque de percevoir. On suppose ici un jeu de données assez petit pour tenir entièrement sur chaque machine ; le partitionnement des données trop grosses fait l'objet du chapitre suivant.

Réplication à leader unique : leaders et suiveurs

Chaque nœud qui détient une copie de la base est un réplica (replica). La question inévitable : comment garantir que toute écriture finit sur tous les réplicas ? La solution la plus répandue est la réplication à leader (leader-based replication), aussi appelée actif/passif ou maître-esclave (master-slave). Elle fonctionne ainsi.

1. Un réplica est désigné leader (master, primaire). Les clients qui veulent écrire envoient leur requête au leader, qui inscrit d'abord la donnée dans son stockage local.
2. Les autres réplicas sont les suiveurs (followers, read replicas, esclaves). À chaque écriture locale, le leader envoie aussi le changement à tous ses suiveurs via un log de réplication (replication log) ou flux de changements. Chaque suiveur applique les écritures dans le même ordre que le leader.
3. Pour lire, un client interroge le leader ou n'importe quel suiveur. Mais les écritures ne sont acceptées que sur le leader ; les suiveurs sont en lecture seule du point de vue du client.

Ce modèle est intégré à de nombreuses bases relationnelles (PostgreSQL depuis la 9.0, MySQL, Oracle Data Guard, AlwaysOn de SQL Server) et non relationnelles (MongoDB, RethinkDB, Espresso). Il dépasse même les bases de données : les courtiers de messages distribués comme Kafka et les files hautement disponibles de RabbitMQ s'en servent aussi.

Synchrone ou asynchrone : le compromis durabilité/latence

Détail capital : la propagation vers un suiveur est-elle synchrone (synchronous) ou asynchrone (asynchronous) ? En réplication synchrone, le leader attend la confirmation du suiveur avant d'annoncer le succès au client. En asynchrone, il envoie le changement sans attendre de réponse.

Critère	Suiveur synchrone	Suiveur asynchrone
Garantie de fraîcheur	Copie à jour, cohérente avec le leader	Peut être en retard de quelques secondes à plusieurs minutes
Si le suiveur ne répond pas	Le leader bloque toutes les écritures	Le leader continue d'écrire normalement
Durabilité après panne du leader	Donnée préservée sur le suiveur	Écritures non encore répliquées perdues
Latence d'écriture perçue	Plus élevée	Faible

Rendre tous les suiveurs synchrones est impraticable : la panne d'un seul nœud paralyserait l'ensemble. En pratique, activer la réplication synchrone signifie souvent qu'un seul suiveur est synchrone, les autres asynchrones ; si le suiveur synchrone devient lent ou indisponible, un asynchrone prend le relais. On garantit ainsi une copie à jour sur au moins deux nœuds. Cette configuration s'appelle semi-synchrone (semi-synchronous).

Ajouter un suiveur sans interrompre le service

Copier bêtement les fichiers d'un nœud à l'autre ne suffit pas : les clients écrivent en continu, et une copie de fichiers verrait différentes parties de la base à des instants différents. Verrouiller la base contredirait l'objectif de haute disponibilité. Le processus correct se déroule sans interruption :

1. Prendre un instantané cohérent (consistent snapshot) de la base du leader, si possible sans verrou global — la plupart des bases savent le faire, car c'est aussi nécessaire pour les sauvegardes.
2. Copier l'instantané sur le nouveau nœud suiveur.
3. Le suiveur se connecte au leader et demande tous les changements survenus depuis l'instantané. Cela exige que l'instantané soit associé à une position exacte dans le log de réplication (PostgreSQL parle de log sequence number, MySQL de binlog coordinates).
4. Quand le suiveur a traité l'arriéré, il a rattrapé (caught up) le leader et continue à appliquer les changements au fil de l'eau.

Pannes de nœuds : rattrapage et bascule

L'objectif est de garder le système entier opérationnel malgré la panne — ou la maintenance planifiée — d'un nœud individuel. Deux cas se présentent.

Panne d'un suiveur : rattrapage (catch-up recovery). Chaque suiveur conserve sur disque le log des changements reçus. Après un crash ou une coupure réseau, il connaît la dernière transaction traitée, se reconnecte au leader, réclame les changements manqués, les applique, et reprend son cours. Simple.

Panne du leader : bascule (failover). Bien plus délicat. Il faut promouvoir un suiveur en nouveau leader, reconfigurer les clients pour qu'ils lui écrivent, et faire consommer les autres suiveurs depuis ce nouveau leader. Une bascule automatique enchaîne typiquement :

1. Détecter que le leader est en panne. Aucune méthode infaillible : on emploie un délai d'expiration (timeout). Si un nœud ne répond pas pendant, disons, 30 secondes, on le suppose mort.
2. Choisir un nouveau leader, par élection ou via un nœud contrôleur. Le meilleur candidat est le réplica le plus à jour. Mettre tous les nœuds d'accord est un problème de consensus (traité plus loin dans le livre).
3. Reconfigurer le système. Les clients écrivent désormais au nouveau leader. Si l'ancien leader revient, il faut qu'il accepte de devenir suiveur.

Le choix du timeout est lui-même un compromis. Trop long, la récupération traîne ; trop court, une simple pointe de charge ou un paquet retardé déclenche des bascules inutiles qui, sous une charge déjà tendue, aggravent la situation. Faute de solution simple, certaines équipes préfèrent la bascule manuelle même quand l'automatique est disponible.

Comment fonctionne le log de réplication

Plusieurs méthodes coexistent pour matérialiser ce log.

Méthode	Principe	Limite principale
Par instruction (statement-based)	Le leader transmet chaque ordre SQL (insert, update, delete) ; chaque suiveur le rejoue	Casse avec le non-déterminisme : NOW(), RAND(), auto-incréments, effets de bord de triggers
Expédition du WAL (WAL shipping)	Le leader envoie son journal d'écriture anticipée octet par octet ; le suiveur reconstruit les mêmes structures	Très bas niveau, couplé au moteur de stockage ; empêche souvent une mise à jour sans interruption
Log logique (logical/row-based)	Une suite d'enregistrements décrivant les changements au niveau de la ligne	Nécessite un format de log dédié, distinct de celui du moteur, mais en reste découplé
Par triggers (trigger-based)	Du code applicatif déclenché à chaque écriture journalise le changement dans une table	Surcoût et risque de bugs accrus ; en échange, grande flexibilité

Le log logique mérite une attention particulière : découplé des internes du moteur, il reste rétro-compatible (leader et suiveurs peuvent tourner sous des versions différentes), et il est facile à analyser pour un système externe — un entrepôt de données, un index ou un cache sur mesure. C'est le principe de la capture de changements de données (change data capture), repris au chapitre 11. La méthode par instruction, faute de gérer proprement le non-déterminisme, est aujourd'hui largement abandonnée ; VoltDB la conserve en imposant des transactions déterministes.

Les problèmes de latence de réplication

Pour une charge surtout faite de lectures (cas fréquent sur le web), l'architecture de mise à l'échelle en lecture (read-scaling) est séduisante : beaucoup de suiveurs, lectures réparties. Mais elle n'est réaliste qu'en asynchrone — sinon une seule panne bloquerait toutes les écritures. Or lire depuis un suiveur asynchrone en retard renvoie des données périmées. Si vous exécutez la même requête sur le leader et sur un suiveur, vous pouvez obtenir des résultats différents.

Cette incohérence est temporaire : arrêtez d'écrire, attendez, les suiveurs rattrapent. D'où le nom de cohérence à terme (eventual consistency). Le mot « à terme » est délibérément vague : en principe, rien ne limite le retard d'un réplica. Ce délai entre une écriture sur le leader et son reflet sur un suiveur — la latence de réplication (replication lag) — vaut d'ordinaire une fraction de seconde, mais peut grimper à plusieurs secondes ou minutes sous charge ou en cas de problème réseau. Trois anomalies méritent alors des garanties spécifiques.

Lire ses propres écritures

L'utilisateur soumet une donnée, puis la consulte. L'écriture va au leader, mais la lecture peut venir d'un suiveur qui n'a pas encore reçu le changement. À ses yeux, sa contribution semble perdue. On a besoin de la cohérence lecture-après-écriture (read-after-write consistency), dite aussi read-your-writes : la garantie que l'utilisateur reverra toujours ses propres mises à jour (sans rien promettre sur celles des autres). Quelques techniques :

// Lire au leader ce que l'utilisateur a pu modifier,
// sinon lire un suiveur (donc plus rapide à mettre à l'échelle).
function choisirReplica(req: Requete): Replica {
  // 1) Son propre profil : toujours au leader.
  if (req.ressource === "profil" && req.cible === req.utilisateur) {
    return leader;
  }
  // 2) Pendant 1 min après sa derniere ecriture : au leader.
  if (Date.now() - req.dernierEcritMs < 60_000) {
    return leader;
  }
  // 3) Sinon, un suiveur suffisamment a jour.
  return suiveurAJour(req.timestampDerniereEcriture);
}

Une autre approche fait mémoriser au client l'horodatage de sa dernière écriture ; le système ne sert sa lecture que par un réplica reflétant au moins cet horodatage, quitte à attendre ou à router ailleurs. Attention aux complications : sur plusieurs appareils (desktop et mobile), il faut une cohérence cross-device — l'horodatage doit être centralisé, et les requêtes des deux appareils éventuellement routées vers le même datacenter.

Lectures monotones

Deuxième anomalie : voir le temps reculer. Un utilisateur fait deux lectures, la première sur un suiveur peu en retard, la seconde sur un suiveur très en retard (typique d'un rafraîchissement de page routé au hasard). La première montre un commentaire récent, la seconde ne le montre plus : le commentaire apparaît puis disparaît. Très déroutant.

Les lectures monotones (monotonic reads) garantissent que cela n'arrive pas : vous pouvez voir une vieille valeur, mais jamais une donnée plus ancienne après en avoir vu une plus récente. C'est une garantie plus forte que la cohérence à terme, plus faible que la cohérence forte. Solution simple : faire en sorte qu'un même utilisateur lise toujours depuis le même réplica, par exemple choisi via un hachage de son identifiant.

Préfixe cohérent

Troisième anomalie, une violation de causalité. Mr Poons demande « Jusqu'où voyez-vous dans le futur, Mrs Cake ? » et Mrs Cake répond « Une dizaine de secondes, généralement. » Un observateur dont la question arrive avec plus de retard que la réponse entend d'abord la réponse, puis la question : Mrs Cake semble douée de voyance.

La garantie de lectures à préfixe cohérent (consistent prefix reads) dit que si des écritures surviennent dans un certain ordre, quiconque les lit les voit dans le même ordre. Le problème est aigu dans les bases partitionnées (sharded), où les partitions opèrent indépendamment, sans ordre global. Une parade : écrire dans la même partition les écritures causalement liées. En général, garantir le préfixe cohérent demande une transaction distribuée avec une garantie de type isolation par instantané (snapshot isolation), reprise au chapitre 7.

Réplication multi-leader

La réplication à leader a un défaut majeur : si vous ne pouvez pas joindre l'unique leader (coupure réseau par exemple), vous ne pouvez plus écrire. Son extension naturelle est d'autoriser plusieurs nœuds à accepter des écritures. La réplication reste identique — chaque nœud propage ses changements aux autres — mais chaque leader joue aussi le rôle de suiveur des autres. C'est la configuration multi-leader (master-master, actif/actif).

Au sein d'un seul datacenter, le bénéfice dépasse rarement la complexité ajoutée. Trois situations la justifient pourtant.

• Opération multi-datacenter : un leader par datacenter. Chaque écriture est traitée localement puis répliquée de façon asynchrone vers les autres. La latence du lien inter-datacenter est masquée à l'utilisateur, chaque datacenter survit indépendamment aux pannes des autres, et les problèmes du lien public sont mieux tolérés.
• Clients hors-ligne : une application qui doit fonctionner sans connexion (l'agenda sur votre téléphone et votre portable). Chaque appareil possède une base locale qui agit comme un leader ; la synchronisation est une réplication multi-leader asynchrone, dont la latence peut atteindre des heures ou des jours.
• Édition collaborative : Etherpad ou Google Docs. Les changements s'appliquent instantanément au réplica local de l'utilisateur, puis se répliquent vers le serveur et les autres. Si l'unité de modification est très petite (une frappe) et qu'on évite les verrous, on hérite de tous les défis du multi-leader, dont la résolution de conflits.

Gérer les conflits d'écriture

Le plus gros problème du multi-leader : deux écritures concurrentes sur la même donnée. User 1 change le titre d'une page de A à B sur son leader, User 2 le change de A à C sur le sien. Chaque écriture réussit localement ; le conflit n'est détecté que de façon asynchrone, plus tard — quand il est peut-être trop tard pour demander à l'utilisateur de trancher. Rendre la détection synchrone reviendrait à perdre l'intérêt du multi-leader ; autant utiliser un leader unique.

La stratégie la plus sûre est d'éviter les conflits : router toutes les écritures d'un enregistrement donné vers le même leader (par exemple le datacenter « domicile » d'un utilisateur). Du point de vue de cet utilisateur, la configuration redevient single-leader. Mais l'évitement s'effondre dès qu'il faut changer de leader pour un enregistrement (datacenter en panne, utilisateur déplacé).

Quand on ne peut éviter le conflit, il faut converger : tous les réplicas doivent aboutir à la même valeur finale. Plusieurs voies :

Stratégie de convergence	Principe	Risque
Dernier écrivain gagne (last-write-wins, LWW)	Attribuer un ID/horodatage à chaque écriture, garder le plus grand, jeter le reste	Perte silencieuse de données ; populaire mais dangereux
Priorité par réplica	Les écritures du réplica au numéro le plus élevé l'emportent	Perte de données également
Fusion (merge)	Combiner les valeurs (ex. ordre alphabétique : « B/C »)	Résultat parfois absurde selon le domaine
Conflit explicite	Conserver toutes les versions et résoudre plus tard (code ou utilisateur)	Reporte la complexité côté application

La logique de résolution sur mesure peut s'exécuter à l'écriture (un gestionnaire en arrière-plan, qui ne peut pas interroger l'utilisateur) ou à la lecture (toutes les versions conflictuelles sont renvoyées à l'application qui tranche, comme dans CouchDB). La résolution s'applique d'ordinaire au niveau d'une ligne ou d'un document, pas d'une transaction entière.

Topologies de réplication

La topologie décrit les chemins de propagation des écritures. À deux leaders, une seule topologie possible. Au-delà, plusieurs choix : circulaire (chaque nœud transmet à un seul suivant, défaut de MySQL), en étoile (un nœud racine relaie aux autres, généralisable en arbre), ou tous-à-tous (chaque leader envoie à tous). Dans les topologies circulaire et en étoile, une écriture traverse plusieurs nœuds ; pour éviter les boucles infinies, chaque écriture est étiquetée des identifiants des nœuds déjà traversés.

Le compromis : circulaire et étoile ont un point unique de défaillance (un nœud en panne interrompt le flux), tandis que tous-à-tous tolère mieux les pannes en offrant plusieurs chemins. Mais tous-à-tous souffre d'un autre mal : des liens de vitesse inégale peuvent faire arriver les écritures dans le désordre. Une mise à jour qui dépend d'une insertion peut précéder cette insertion sur un nœud — un problème de causalité. Un simple horodatage ne suffit pas (les horloges ne sont pas assez synchronisées) ; il faut des vecteurs de version (version vectors), abordés plus bas. Or beaucoup d'implémentations multi-leader détectent mal les conflits : lisez la documentation et testez.

Réplication sans leader

Certains systèmes abandonnent le concept de leader : n'importe quel réplica accepte directement les écritures des clients. L'idée, oubliée à l'ère relationnelle, est revenue à la mode quand Amazon l'a employée pour son système maison Dynamo ; Riak, Cassandra et Voldemort s'en inspirent, d'où le qualificatif « style Dynamo ». Soit le client envoie ses écritures à plusieurs réplicas, soit un nœud coordinateur le fait — mais ce coordinateur n'impose aucun ordre aux écritures.

Écrire et lire pendant qu'un nœud est en panne

Avec trois réplicas dont un est en train de redémarrer, il n'y a pas de bascule : le client envoie l'écriture aux trois en parallèle, et si deux confirment, l'écriture est réussie. Le client ignore que le troisième l'a manquée. Mais quand ce nœud revient, ses lectures renvoient des valeurs périmées (stale). La parade : les lectures vont aussi à plusieurs nœuds en parallèle, et un numéro de version détermine la valeur la plus récente. Deux mécanismes assurent qu'à terme tout se propage :

• Réparation à la lecture (read repair) : en lisant plusieurs nœuds, le client détecte une réponse périmée et y réécrit la valeur récente. Efficace pour les valeurs souvent lues.
• Anti-entropie (anti-entropy) : un processus de fond compare en permanence les réplicas et copie les données manquantes, sans ordre particulier. Sans lui, une valeur rarement lue peut rester périmée indéfiniment.

// Lecture avec reparation : interroge n replicas en parallele,
// retient la version la plus haute, repare les retardataires.
async function lectureReparee(cle: string): Promise<Valeur> {
  const reponses = await Promise.all(
    replicas.map((r) => r.lire(cle)), // {valeur, version} | null
  );
  const fraiche = reponses
    .filter((x): x is Reponse => x !== null)
    .reduce((a, b) => (b.version > a.version ? b : a));

  for (const r of replicas) {
    const vue = await r.lire(cle);
    if (!vue || vue.version < fraiche.version) {
      await r.ecrire(cle, fraiche.valeur, fraiche.version); // repair
    }
  }
  return fraiche.valeur;
}

Les quorums de lecture et d'écriture

Combien de nœuds faut-il vraiment ? Avec n réplicas, si chaque écriture est confirmée par w nœuds et chaque lecture interroge r nœuds, alors tant que w + r > n, l'ensemble lu et l'ensemble écrit se chevauchent forcément : au moins un des r nœuds lus possède la valeur la plus récente. On parle de lectures et écritures à quorum (quorum reads/writes). Pensez w et r comme le nombre minimal de voix requises.

n = 3, w = 2, r = 2   ->  w + r = 4 > 3   tolere 1 nœud indisponible
n = 5, w = 3, r = 3   ->  w + r = 6 > 5   tolere 2 nœuds indisponibles

Choix courant : n impair, w = r = (n + 1) / 2 (arrondi au sup.)
Lectures rapides, peu d'ecritures : w = n, r = 1
  -> mais une seule panne bloque alors toutes les ecritures

Normalement, lectures et écritures partent vers les n réplicas en parallèle ; w et r fixent seulement combien de réponses on attend avant de déclarer le succès. Avec des w et r plus petits (w + r ≤ n), on lit plus souvent des valeurs périmées, mais on gagne en latence et en disponibilité. La base ne devient indisponible que lorsque le nombre de réplicas joignables passe sous w (écritures) ou r (lectures).

Quorums relâchés et transfert indiqué

Une coupure réseau peut isoler un client de la plupart des nœuds, sans qu'ils soient morts. Faut-il alors renvoyer une erreur, ou accepter quand même l'écriture sur des nœuds joignables mais étrangers au groupe des n nœuds « domicile » de la valeur ? Ce second choix est le quorum relâché (sloppy quorum). L'analogie de Kleppmann : enfermé dehors, vous frappez chez le voisin pour dormir sur son canapé. Une fois le réseau rétabli, les écritures temporaires sont renvoyées à leurs nœuds d'origine — c'est le transfert indiqué (hinted handoff), le voisin vous priant poliment de rentrer chez vous.

Le quorum relâché augmente la disponibilité en écriture (tant que n'importe quels w nœuds répondent), mais n'est plus un quorum au sens strict : la dernière valeur a pu atterrir hors des n nœuds, donc même avec w + r > n une lecture peut la manquer tant que le transfert n'est pas terminé. C'est une assurance de durabilité, pas de fraîcheur. Activé par défaut dans Riak, désactivé dans Cassandra et Voldemort.

Détecter les écritures concurrentes

Le sans-leader autorise plusieurs clients à écrire la même clé en même temps : des conflits surgissent, même avec quorums stricts, car les événements arrivent dans un ordre différent selon les nœuds. Si chaque nœud écrasait aveuglément, les réplicas divergeraient à jamais. Pour converger, il faut savoir distinguer un écrasement légitime d'une vraie concurrence.

Le dernier écrivain gagne (LWW) atteint la convergence en gardant la valeur au plus grand horodatage, mais au prix de la durabilité : parmi plusieurs écritures concurrentes toutes confirmées, une seule survit, les autres sont jetées en silence. LWW peut même perdre des écritures non concurrentes à cause de la dérive d'horloge. Le seul usage sûr : n'écrire chaque clé qu'une fois et la traiter ensuite comme immuable (d'où l'usage d'un UUID comme clé dans Cassandra).

Pour faire mieux, il faut la relation « précède » (happens-before). Une opération A précède B si B est au courant de A, en dépend, ou s'appuie dessus. Deux opérations sont concurrentes si ni l'une ni l'autre ne précède l'autre — peu importe qu'elles se chevauchent dans le temps physique : ce qui compte, c'est qu'elles s'ignorent mutuellement. Trois cas seulement : A précède B, B précède A, ou A et B concurrentes. Si l'une précède l'autre, la plus tardive écrase ; sinon, c'est un conflit à résoudre.

Panier d'achat, un seul replica, deux clients concurrents :

C1 +lait           -> v1 : [lait]
C2 +oeufs          -> v2 : [oeufs]                 (ignore [lait])
C1 +farine (base v1) -> v3 : [lait, farine]        garde [oeufs] (concurrent)
C2 +jambon (base v2) -> v4 : [oeufs, lait, jambon] garde [lait, farine]
C1 +bacon  (base v3) -> v5 : [lait, farine,        garde [oeufs, lait,
                              oeufs, bacon]                jambon]

Le serveur compare les numeros de version, sans lire la valeur :
  ecrasable = versions <= numero fourni par le client
  a conserver = versions superieures (= concurrentes)

L'algorithme : le serveur maintient un numéro de version par clé, l'incrémente à chaque écriture. À la lecture, il renvoie toutes les valeurs non écrasées plus le dernier numéro ; un client doit lire avant d'écrire. À l'écriture, le client renvoie ce numéro et fusionne les valeurs lues. Le serveur peut alors écraser tout ce qui est inférieur ou égal, et conserver le reste comme siblings (frères, dans le vocabulaire de Riak) concurrents.

La fusion des siblings retombe sur le problème de la résolution de conflits. Pour un panier, l'union semble raisonnable — mais elle fait réapparaître un article retiré dans un seul des paniers. D'où le tombstone (pierre tombale) : un marqueur de suppression versionné, conservé au lieu d'effacer. Les CRDT de Riak savent fusionner automatiquement, suppressions comprises.

À retenir

• On réplique pour trois raisons — latence (proximité), disponibilité (tolérance aux pannes) et débit en lecture — mais toute la difficulté tient à la propagation des changements.
• La réplication synchrone garantit une copie à jour au prix du blocage ; l'asynchrone est rapide mais peut perdre des écritures confirmées si le leader tombe. En pratique on vise un compromis semi-synchrone, et la bascule (failover) reste pleine de pièges (split brain, données écartées, choix du timeout).
• La latence de réplication engendre des anomalies que trois garanties corrigent : lecture-après-écriture (revoir ses propres écritures), lectures monotones (ne pas voir le temps reculer) et préfixe cohérent (respecter la causalité).
• Le multi-leader sert le multi-datacenter, le hors-ligne et l'édition collaborative, mais impose une résolution de conflits ; LWW converge au prix d'une perte silencieuse de données, là où CRDT et fusion préservent l'information.
• Le sans-leader (style Dynamo) écrit et lit sur plusieurs nœuds ; la condition w + r > n garantit un chevauchement, mais quorums relâchés et écritures concurrentes en érodent les garanties.
• Détecter la concurrence repose sur la relation « précède » et les vecteurs de version ; deux écritures qui s'ignorent sont concurrentes, et leur fusion (siblings, tombstones) incombe souvent à l'application.