Réplication des données : enjeux et approches

Single Master, Multi Master, Masterless … derrière ces concepts se cachent des approches différentes pour la réplication des données dans un système distribué, souvent dans le cadre d’une base de données. Les compromis, avantages et limites de ces approches peuvent ne pas être évidents à comprendre et à synthétiser de prime abord. Cependant, les connaître est essentiel pour orienter le choix d’une solution technique selon le besoin auquel on cherche à répondre.

Souhaitant en apprendre davantage, je me suis tourné vers le livre de Martin Kleppmann, Designing Data-Intensive Applications , que je recommande à ceux qui veulent apprendre ou se remettre en tête les concepts du Data Engineering.

Le but de cet article est de synthétiser les principales idées et considérations lorsque l’on choisit une approche par rapport à une autre, afin de mieux orienter nos choix concernant les différentes bases de données disponibles à l’heure actuelle. L’article n’ayant pas une visée exhaustive, je n’aborderai pas les problématiques du partitionnement et du rebalancement.

Réplication des données : enjeux

La réplication des données est un concept plutôt explicite. Dans le cadre d’une base de données, cela se traduit par l’évolution d’une architecture avec une seule instance à une architecture où plusieurs instances (appelées replicas) gardent chacune une copie de ces données et synchronisent les changements entre elles.

On souhaitera notamment procéder à cette évolution dans des problématiques de mise à l’échelle et d’infrastructures fault-tolerant (signifiant qu’une instance puisse devenir indisponible sans que les autres instances soient impactées, permettant de continuer les opérations courantes). Cela permet aussi d’améliorer la durabilité des données.

Cependant, ce changement d’architecture entraîne une complexité supplémentaire, principalement pour la réplication des changements. Il n’est initialement pas compliqué de copier une base de données vers une autre instance, mais lorsque de nouvelles opérations ont lieu sur l’un des noeuds (j’utiliserai désormais le mot noeud à la place du mot instance), il est nécessaire de le répliquer sur les autres pour que l’ensemble ait un état cohérent.

Dès lors, certaines problématiques (non-exhaustives) se posent :

• Faut-il répercuter les modifications de manière synchrone ou asynchrone ?
• Comment gérer les conflits d’écriture si deux opérations différentes ont lieu sur la même donnée sur des noeuds différents, et ce en même temps ?
• Comment gérer les limites inhérentes des systèmes distribués, notamment les latences réseau pour la réplication des données (certains noeuds peuvent recevoir les données avant les autres).
• Comment gérer l’échec d’un noeud : re-routage des requêtes, mise à jour lors de sa réintégration etc.

Les deux modes de synchronisation des données ne sont en réalité pas mutuellement exclusifs car une base de données (ex: DynamoDB) peut choisir d’utiliser les deux (semi-synchronous). En effet, chaque mode vient avec ses avantages et inconvénients :

• Le mode synchrone permet de s’assurer que les données d’un noeud sont bien à jour avec celles d’un autre noeud. Cependant, ce mode de synchronisation est bloquant : si le noeud de réception des données n’est pas disponible, le noeud d’envoi va bloquer toutes les écritures en attendant la disponibilité de l’autre noeud (ce qui peut causer une paralysie en cascade du système).
• A l’inverse, le mode asynchrone n’est pas bloquant. Cependant, nous n’avons pas de garantie que le noeud de réception aura déjà mis ses données à jour lorsqu’on fait une requête de lecture dessus. La synchronisation asynchrone émet aussi la possibilité d’une perte de données si un noeud cherchant à répliquer ses nouvelles données connaît un échec (avec données irrécupérables) avant que la synchronisation ait eu lieu.

Pour couper la poire en deux, DynamoDB choisit de répliquer d’abord une nouvelle donnée de manière synchrone sur un noeud, puis de manière asynchrone sur les autres.

La considération de la cohérence des données à un instant donné se pose alors : si certains noeuds obtiennent les données de manière asynchrone afin de ne pas bloquer le système, il se peut que des requêtes de lecture sur ces noeuds ne renvoient pas les dernières données disponibles (on voit ici la relation directe avec le théorème CAP). Cela peut aussi entraîner une violation de causalité, due à des différences de vitesse de réplication, par exemple l’arrivée d’une mise à jour d’une valeur sur un noeud avant que l'insertion initiale de cette valeur arrive sur le dit noeud (B arrive avant A). Ces problèmes de latence sont dénommés replicas lags et, si ils ne sont pas pris en compte lors de la conception d’une application, peuvent sérieusement entraver l’expérience de l’utilisateur et notre compréhension du système.

Il est donc courant d’entendre parler des termes eventual consistency (cohérence à terme) et strong consistency (cohérence forte). Les implémentations pour arriver à chacune de ces garanties divergent (je ne rentrerai pas dans les détails), mais on souhaite pouvoir au moins assurer les suivantes :

• Monotonic read : éviter de voir un état antérieur à l’état que je viens de voir sur des requêtes successives (je fais une requête sur un noeud à jour puis une autre requête sur un noeud en retard).
• Read-after-write consistency (aussi appelé read your own write) : une fois qu’une écriture est réalisée, éviter que, en tant que client, j’aille faire une requête à un noeud où la réplication n’a pas encore eu lieu, voyant alors mes données fraîchement insérées disparaître !

Ces problématiques en tête, il nous reste maintenant à aborder le coeur du problème : les approches implémentées par différentes bases de données pour gérer les changements et les potentiels conflits d’écriture ou de cohérence des données.

Réplication des données : approches

Il existe trois approches (ou algorithmes) principales utilisées par les bases de données qui supportent la réplication des données. Les concepteurs de ces systèmes choisiront l’approche qui est la plus efficiente pour les cas d’utilisation destinés à leur base de données.

Single Master

Implémentée notamment par : PostgreSQL, DynamoDB, MongoDB, Kafka (même si Kafka n’est pas une base de donnée pure)

Cette approche fonctionne de la manière suivante : nous avons N noeuds. Un seul noeud est considéré comme le noeud maître, c’est à dire qu’il est le seul noeud à accepter des requêtes de modification des données (insertion, mise à jour, etc.). Les N-1 noeuds sont des noeuds en lecture seule (read replicas).

L’avantage de cette approche est d’éviter les conflits d’écriture. En effet, comme les modifications passent toutes par le même noeud, nous ne pouvons pas avoir de modifications concurrentes sur des noeuds différents, entraînant un problème détectable seulement plus tard lorsque la synchronisation asynchrone s’est effectuée. Ainsi, ce type d’approche est généralement recommandé pour les applications où la cohérence des données est importante. Comme l’approche parfaite n’existe pas, il y a un compromis : le seul noeud en écriture est le point d’échec principal de l’infrastructure (single point of failure). S’il tombe, nous ne pourrons plus accepter de modifications des données tant qu’un autre noeud n’aura pris sa place (le mécanisme d’élection, que je détaillerai juste après) !

Lorsqu’une nouvelle donnée est insérée ou modifiée via le noeud maître, celui-ci transmet les modifications aux noeuds en lecture seule. En effet, dans cette approche, on peut considérer que la synchronisation des données se fait par une différence entre l’état du noeud maître et l’état du noeud en lecture seule. Pour évaluer cet état, les bases de données qui implémentent cette approche utilisent ce qu’on appelle un log de réplication (replication log). Un log de réplication peut prendre plusieurs formes :

• statement-based replication : on copie la requête aux followers, une approche jugée dangereuse si la requête n’est pas déterministe (avec les mêmes entrées, à un instant et état donné, la requête produit toujours le même résultat).
• write-ahead log shipping : un log des modifications effectuées sur la base de données, très bas niveau (modifications de bytes) et couplé au moteur de base de données utilisé.
• logical (row-based) log replication : un log découplé du moteur utilisé, utilisé spécifiquement pour la réplication, ici on spécifie directement les valeurs à insérer ou identifier, le quoi.

Par exemple, PostgreSQL, qui implémente l’approche de Single Master, permet de configurer la réplication : physique (WAL) ou logique.

Ce log de réplication est aussi utilisé dans le cas où un noeud en lecture seule tombe. Lorsqu’il revient en ligne, il aura certainement pris du retard sur le noeud maître. Il faut donc implémenter un mécanisme permettant à ce noeud de mettre à jour ses données pour refléter l’état actuel du noeud maître. Ce mécanisme est communément dénommé catch-up recovery. Le noeud en lecture seule va faire une demande du log de réplication au noeud maître, et par le calcul d’une différence, mettre à jour ses données.

Les noeuds en lecture seule peuvent aussi changer de type de synchronisation, principalement dans une approche semi-synchrone. Si le noeud en synchronisation synchrone tombe, un noeud auparavant asynchrone prendra sa place (en devenant synchrone), au risque de bloquer le système.

Cependant, la tâche n’est pas aussi aisée dans le cas de l’échec du noeud maître. Premièrement, il faut choisir le nouvel élu, celui qui deviendra le prochain noeud maître. Deuxièmement, c’est un titre convoité … il faut donc que les noeuds en lecture seule se mettent d’accord entre eux ! Mais sur la base de quels critères ? C’est toute une problématique : le mécanisme de failover. Généralement, c’est le noeud en lecture seule qui a les données les plus récentes qui sera choisi. Cela peut être décidé par vote, par une approche dite de consensus (Raft, Paxos, etc.).

Malheureusement, il existe des cas où l’ancien noeud maître, lorsqu’il retourne à la vie, n’accepte pas d’être relégué au rang de simple noeud en lecture seule. Il se considère toujours comme noeud maître ! On a donc un problème : deux noeuds maîtres dans une approche où un seul noeud maître devrait exister. Ce problème s’appelle le split brain. C’est un problème car le mécanisme de failover doit s’assurer que les requêtes de modification des données sont redirigées vers le nouveau maître ! A cause de ce problème, certains praticiens préfèrent ne pas automatiser le processus d’élection d’un nouveau maître, et le faire manuellement à la place. Quelques approches, comme STONITH (via Pacemaker/Heartbeat), permettent de limiter ces effets secondaires.

Multi master

Implémenté notamment par : CouchDB, Redis

Dans cette approche, en contraste de l’approche Single-Leader, nous avons la possibilité d’avoir plusieurs maîtres. On va généralement utiliser cette approche dans une architecture hautement disponible (high availability) : un maître et quelques followers dans plusieurs zones de disponibilités / régions. Les noeuds maîtres acceptent les opérations de modifications, et se les propagent entre eux. L’avantage de cette approche est de ne plus avoir de point d’échec unique pour les écritures : si un noeud maître tombe, les requêtes sont redirigées vers les autres. On peut aussi bénéficier d’une meilleure latence si l’on place différents noeuds maîtres à différents emplacements, plus proches de nos utilisateurs.

Ici, le challenge principal n’est plus dans le mécanisme de failover pour l’élection d’un nouveau maître, mais pour la résolution des conflits d’écriture. Ces derniers sont particulièrement difficiles à corriger (ils ne sont détectés que plus tard à cause de la synchronisation asynchrone), on cherche donc généralement à les prévenir. Cependant, aucun système en Multi Master ne peut réellement garantir qu’il est capable de prévenir ce genre de conflits. Il ne faut donc pas utiliser de base de données implémentant cette approche si la véracité des données est critique. En cas de conflit d’écriture, il existe diverses méthodes permettant d’arriver à un état convergent, afin de résoudre les conflits (un ID unique pour chaque transaction où le plus grand sera choisi en priorité, etc.) mais la plupart entraînent potentiellement une perte de données.

Il faut aussi penser aux différents “chemins” possibles pour la synchronisation des données entre maîtres, la topologie. Si nous n’avons que deux noeuds maître, la topologie est simple, mais cela se complique si il y a plusieurs noeuds maître.

A mes yeux, cette approche a davantage de sens dans des applications souhaitant être collaboratives et fonctionnant même hors-ligne. En effet, poussée à son extrême, cette approche considère que chaque appareil doit héberger un noeud maître en local (un mini-datacenter en périphérie) permettant de continuer à apporter des modifications aux données en local, pour qu’elles soient enfin synchronisées avec les autres noeuds lorsque la connexion revient. CouchDB correspond totalement à ce cas d’utilisation. Globalement, tout type d’architecture où l’on souhaite avoir un état local qui peut être synchronisé avec d’autres (notamment un cache, ce qui explique pourquoi Redis implémente aussi cette approche).

Pour éviter les conflits dans ce type d’application collaborative, il existe plusieurs approches intéressantes, que je nomme brièvement :

• Conflict-free replicated datatypes (CRDTs)
• Mergeable persistent data structures
• Operational transformation (utilisé notamment par Google Docs)

Masterless

Implémenté notamment par : Cassandra

L’approche Masterless, c’est la démocratie participative apportée aux bases de données. Ici, plus de hiérarchie : tous les noeuds sont au même niveau, et se concertent entre eux pour la prise de décisions ! Il n’y a plus de concept de réplication de logs (les instructions transmises).

Dans cette approche, chaque requête (qu’elle soit de lecture ou d’écriture) est envoyée à plusieurs noeuds en “même temps” (entre guillemets car les réseaux sont capricieux, certains noeuds recevront les données avant les autres ; je parle donc ici du moment de l’envoi). Comme nous sommes en démocratie, pour qu’une requête soit acceptée, une majorité de noeuds doivent se mettre d’accord. Ce mécanisme de consensus léger s’appelle le quorum. Par exemple, si je veux lire une valeur, je vais envoyer la requête à 3 noeuds. Si le premier noeud a une valeur de “a”, mais les deux autres noeuds ont une valeur de “b”, c’est la valeur “b” qui sera choisie. Elle nous sera renvoyée, et la valeur “a” du premier noeud sera remplacée par “b “(mécanisme de read-repair, si la majorité ne pense pas comme moi, c’est elle qui a raison !). Ce principe peut être implémenté différemment : par exemple dans le cas de Cassandra, c’est le noeud possédant une donnée avec la timestamp la plus récente qui renverra la valeur. On sera ici davantage dans une approche de consultation.

Quelques règles sont à garder en tête pour que le quorum fonctionne bien. Prenons n le nombre de noeuds, w le nombre de noeuds qui doivent confirmer chaque requête d’écriture (write) et r le nombre de noeuds qui doivent confirmer chaque requête de lecture (read).

• On prendra généralement un nombre impair pour n. Pour r et w : w = r = (n + 1) / 2
• w + r > n : Si j’interroge 3 noeuds pour écrire, 3 noeuds pour lire, et que j’ai 5 noeuds en tout, je devrais avoir une valeur à jour car il y a superposition.
• Si w < n, je peux tolérer la perte de n - w noeuds et continuer à supporter les écritures.
• Si r < n, je peux tolérer la perte de n - r noeuds et continuer à supporter les lectures.

L’approche Masterless confère donc nombre d’avantages : résiliente (pas de noeud avec un rôle unique), durabilité des données (envoyées à plusieurs noeuds), performance, mise à l’échelle. On l’utilise ainsi dans les cas où on souhaite supporter des requêtes intensives et une forte résilience du système, au prix de données pas toujours cohérentes (récupération de données anciennes, appelées stale values). En effet, il faut parfois un certain temps avant que des données rarement accédées soient mises à jour par le processus de read-repair. C’est pour cela que certaines bases de données déclenchent un processus en arrière plan (un processus d’anti-entropie) pour régler les différences d’état entre les noeuds.

De plus, cette approche n’évite pas réellement le problème des écritures simultanées. Tous les noeuds n’auront pas le même délai d’écriture, du coup il se peut que des requêtes initiées par un autre client arrivent avant. Il faut donc trouver un mécanisme permettant de prioriser certaines requêtes au détriment d’autres. Cassandra implémente l’approche LWW (Last Write Wins), ce qui signifie que la requête avec la timestamp la plus récente a précédence sur les autres. Cependant, cette approche est limitée : un gros problème des systèmes distribuées est celui de la synchronisation des horloges. Si un noeud a une horloge avec un décalage temporel (drift) plus avancé que les autres, toutes ses requêtes vont supplanter celles des autres noeuds.

J’ai mentionné au début que cette approche n’utilise plus de log de réplication. Cela peut être problématique dans la mesure où le monitoring sera plus compliqué car nous n’avons pas d’historique ordonné des modifications apportées à la base de données.

Enfin, cette approche ne permet pas la gestion des transactions ACID. Une écriture partielle sera ainsi acceptée comme telle (pas d’atomicité).

Gardons donc en tête que la cohérence des données ne peut donc pas être garantie par cette approche, comme pour la précédente.

Synthèse