Tous les deux modifient ensemble une liste de courses sur leur téléphone. Ils sont tous les deux hors réseau : l'un est dans l'ascenseur, l'autre dans l'avion. Lan ajoute « du lait », Minh ajoute « des œufs ». Une demi-heure plus tard, ils ont tous les deux retrouvé une connexion.
Le résultat correct devrait être une liste contenant à la fois du lait et des œufs. Mais pour que le système puisse y parvenir de lui-même, sans demander confirmation à personne, il faut une conception des données radicalement différente de celle habituelle. C'est ce qu'on appelle les CRDT.
Pourquoi les méthodes habituelles entraînent-elles une perte de données ?
La méthode la plus courante consiste à laisser le serveur trancher : c'est la version envoyée en dernier qui l'emporte. Cela semble logique, mais voyons ce qui se passe avec la liste de courses.
Lan a envoyé son fichier en premier, Minh a envoyé le sien ensuite. Le serveur a enregistré la version de Minh et supprimé celle de Lan. La rubrique « lait » a disparu, sans que personne n'en soit informé.
La deuxième solution consiste à demander à l'utilisateur : « En cas de conflit, quelle version choisissez-vous ? ». C'est plus sûr, mais cela fait peser la décision sur l'utilisateur, et dans le cas de documents partagés qui sont constamment modifiés, cela revient à poser la question sans arrêt.
Le CRDT opte pour une troisième voie : concevoir une structure de données de telle sorte que la fusion donne toujours une seule et unique réponse correcte, calculable par une machine, sans qu'il soit nécessaire de faire appel à un arbitre ni de consulter qui que ce soit.
Les trois qualités qui font la magie
Pour pouvoir fusionner sans avoir à trier, la fusion doit remplir trois conditions. Cela semble très mathématique, mais en réalité, c'est très simple.
« Échanger les places » signifie que l'on peut fusionner le fichier de Lan avec celui de Minh, ou inversement, le résultat sera le même. C'est important car, sur Internet, on ne peut pas contrôler quel paquet arrive en premier.
Le regroupement signifie que, dès lors qu’il y a au moins trois machines, l’ordre dans lequel on les regroupe n’a pas d’importance. Il n’y a pas besoin d’un ordre global — ce qui est très difficile à obtenir dans un système distribué.
La répétition inoffensive signifie qu’il n’y a aucun problème à recevoir deux fois le même paquet. Cela vous évite toute une série d’erreurs, car les réseaux réels envoient toujours les paquets en double lors des tentatives de réémission.
Si ces trois conditions sont réunies, les copies convergeront immanquablement vers un même état — peu importe qui a envoyé en premier, quels colis se sont égarés ou lesquels sont arrivés deux fois.
L'exemple le plus simple : compter le nombre de « J'aime »
Imaginons qu'un article soit « aimé » sur trois serveurs différents, et que la synchronisation entre eux soit lente. Si chaque serveur conserve un compteur et que l'on retient le plus grand nombre lors de la fusion, on perdra des « j'aime ». Si l'on additionne aveuglément les chiffres, on comptera plusieurs fois les mêmes « j'aime ».
La solution est que chaque machine ne peut écrire que dans sa propre case.
La machine A compte 5 fois, la machine B 3 fois et la machine C 2 fois. Pour les additionner, on prend la valeur la plus élevée de chaque case, puis on les additionne : 5 + 3 + 2 = 10.
Pourquoi prendre la valeur la plus élevée sans l'ajouter ? Comme la cellule de la machine A n'est remplie que par la machine A, le chiffre qui y figure augmente toujours. Si l'on reçoit une version plus ancienne, on l'ignore ; si l'on reçoit une version plus récente, on met à jour. Même en cas de doublon, ce n'est pas grave : en prenant deux fois la valeur la plus élevée, on obtient toujours le même résultat.
Pour compter à la fois les augmentations et les diminutions, il faut utiliser deux compteurs comme indiqué ci-dessus, un pour les augmentations et un pour les diminutions ; le résultat correspond à la différence entre les deux totaux.
Collection : c'est facile d'ajouter, mais difficile de supprimer
Retour à la liste des courses. Ajouter un élément, c'est très simple : la union est l'opération qui combine deux ensembles, et elle satisfait aux trois propriétés ci-dessus.
Les problèmes ont commencé lorsqu'il y a eu une suppression.
Lan a supprimé « lait » de la liste. L'ordinateur de Minh n'était pas au courant, donc « lait » y figurait toujours. Lors de la fusion, « lait » est réapparu — car pour un ordinateur, « je n'ai pas de lait » et « j'ai supprimé lait » sont deux expressions identiques.
La solution consiste à enregistrer une trace : lors de la suppression, on ne supprime pas l'élément, mais on le marque comme ayant été supprimé. Ce marqueur est souvent appelé « pierre tombale ». Lors de la fusion, le marqueur de suppression l'emporte sur l'élément actif, ce qui donne un résultat conforme à l'intention de l'utilisateur.
Le prix à payer, c’est une liste de pierres tombales qui ne cesse de s’allonger. Un document modifié pendant de nombreuses années peut comporter davantage de traces que de contenu réel. Le système doit en effet être nettoyé régulièrement, et ce nettoyage ne peut avoir lieu que lorsque l’on est certain que toutes les copies ont bien reçu la notification de cette suppression.
Texte : le problème le plus difficile
La rédaction collaborative est le domaine dans lequel le CRDT est le plus connu, mais aussi le plus difficile. Le problème réside dans le fait que la position dans le texte n'est pas fixe.
Supposons que le texte soit « MEO ». Lan insère un « C » au début, Minh insère un « O » à la fin. Si l’on décrit l’opération par un numéro d’ordre — « insérer à la position 3 » —, alors, une fois l’opération de Lan effectuée, la position 3 pointe désormais vers un autre emplacement. Le caractère inséré par Minh se retrouve donc au mauvais endroit.
La solution consiste à supprimer complètement les numéros d'ordre. Chaque caractère se voit attribuer un identifiant permanent qui ne change jamais, et l'opération d'insertion est décrite par la relation : « situé entre le caractère de code X et le caractère de code Y ».
Ce qui est intéressant ici, c’est qu’entre deux codes quelconques, on peut toujours générer un nouveau code situé entre les deux — tout comme entre deux nombres réels quelconques, il existe toujours un autre nombre réel. Grâce à cela, il y a toujours de la place pour insérer un élément, même si l’on insère un élément au même endroit un nombre illimité de fois.
Lorsque deux personnes s'insèrent dans la même file d'attente, il faut une règle de départage — généralement la comparaison des identifiants des machines. N'importe quelle règle convient, à condition que toutes les machines utilisent la même, car l'objectif est d'aboutir au même résultat.
Résultat : toutes les copies se recoupent
C'est ce que le CRDT promet et garantit : les nœuds reçoivent les modifications dans un ordre quelconque, autant de fois que nécessaire, à condition qu'au final, chacun reçoive l'intégralité des données, de sorte que tous se retrouvent dans le même état. Pas besoin de serveur central, pas besoin de clé, pas besoin de demander confirmation à l'utilisateur.
Deux façons de concrétiser
Envoi de l'état. Chaque machine envoie périodiquement l'intégralité de son état ; le destinataire regroupe ces informations. Ce système est simple et résiste à la perte de paquets, mais il consomme beaucoup de bande passante lorsque les données sont volumineuses. Les versions modernes envoient uniquement les modifications plutôt que l'intégralité des données.
Envoyer l'opération. Chaque machine n'envoie que l'opération qu'elle vient d'effectuer. Ce système est très économe, mais nécessite une couche de transport garantissant que toutes les opérations parviennent à destination, sans perte et sans être appliquées plusieurs fois.
Ce que le CRDT ne promet pas
C'est là que l'on risque le plus de se tromper. Les CRDT garantissent que toutes les copies convergent vers un même résultat. Elles ne garantissent pas que ce résultat corresponde aux attentes de l'utilisateur.
Si deux personnes modifient une phrase dans deux directions différentes, cela peut donner une phrase hybride et dénuée de sens. Le CRDT garantit simplement que tout le monde verra cette phrase hybride, mais ne garantit pas qu’elle soit bonne.
Les opérations nécessitant une invariance globale — telles que « le solde ne doit pas être négatif » ou « une seule personne peut occuper cette place » — ne peuvent pas être gérées par les CRDT. Ces cas nécessitent toujours un véritable consensus.
Quand faut-il l'utiliser ?
- Convient : notes, listes de tâches, croquis, rédaction collaborative, synchronisation des paramètres sur plusieurs appareils — là où les coupures de connexion sont fréquentes et où la fusion automatique est préférable à une sélection manuelle par l’utilisateur
- À éviter : transactions financières, réservations, gestion des stocks — où une erreur de résultat est une véritable erreur, et pas seulement un inconvénient
- À prendre en compte : données très volumineuses ou modifiées en continu depuis plusieurs années, car la quantité de métadonnées associées peut dépasser celle des données réelles
Si vous comptez réaliser ce projet vous-même, utilisez les bibliothèques existantes plutôt que de tout écrire à partir de zéro. La difficulté ne réside pas dans l'idée — l'idée est celle présentée dans cet article — mais dans la compression des métadonnées, le nettoyage des données obsolètes et le maintien des performances à mesure que le volume de documents augmente.
Thảo luận