Il s’agit d’un article sur la complexité du maintien de la cohérence des données dans les environnements distribués. Il introduit des types de données répliqués sans conflit (CRDT) comme moyen de résoudre les modifications de données simultanées.
Défis communs de cohérence des données
Considérons une situation dans laquelle plusieurs entités distribuées détiennent chacune une copie des mêmes données. La cohérence des données est maintenue si ces copies continuent à correspondre, même lorsqu’une ou plusieurs d’entre elles sont mises à jour.
Si une seule entité met à jour sa copie des données, il n’y a pas de contestation de la dernière « source de vérité » pour ces données, mais il n’y a peut être des différences temporelles dans l’état de chaque entité distribuée. La latence du réseau affectera le taux auquel chaque pair reçoit des mises à jour ; les défaillances du réseau ou du système signifient que certains pairs peuvent ne jamais recevoir de mises à jour.
Mis à part le fait que certaines mises à jour ne parviennent pas à atteindre certains pairs, ces échecs entraînent un défi de cohérence des données. Par exemple, la distribution de certaines mises à jour peut échouer, mais d’autres réussissent ; cela entraîne des problèmes de cohérence et de commande. Une conception de système doit s’adapter à de tels cas pour assurer la cohérence.
Il existe d’autres défis si plusieurs entités effectuent simultanément des mises à jour indépendantes des données. Maintenant, il n’y a pas nécessairement une seule version canoniquement « correcte » des données. Les mises à jour créées par un pair dans un état peuvent entrer en conflit, ou ne pas avoir de sens, avec d’autres pairs qui ont une visibilité sur d’autres mises à jour.
Qu’est-ce que la cohérence forte ? Qu’est-ce que la cohérence à terme ?
La cohérence forte est la propagation de toute mise à jour à toutes les copies de données. Dans le cas le plus simple, une série de mises à jour des données provient d’une seule source, et toutes les autres entités qui détiennent une réplique des données sont assurées de recevoir ces mises à jour dans le même ordre.
Lorsque plusieurs copies des données peuvent être mises à jour en même temps, il doit y avoir un moyen de se mettre d’accord sur la version correcte des données. Avec une forte cohérence, une fois qu’une entité effectue des mises à jour, toutes les autres répliques sont verrouillées jusqu’à ce qu’elles aient été mises à jour vers la même nouvelle version. La source de vérité envoie des mises à jour à toutes les entités dans le même ordre pour les maintenir « en phase ».
Les contraintes de conception imposées par une forte cohérence sont inacceptables dans un nombre croissant de cas d’utilisation. Envisagez la collaboration en temps réel (comme dans les outils de productivité en ligne qui permettent aux utilisateurs d’effectuer des modifications simultanées). Chaque entité peut potentiellement créer et recevoir des mises à jour, il n’y a donc aucun moyen de s’assurer que chaque réplica reçoit la même séquence de mises à jour. La cohérence à terme est la propriété où l’état des données est finalement réconcilié, quel que soit l’ordre des événements de mise à jour qui atteignent chaque réplica.
Qu’est-ce qu’un conflit de réplication ?
Un conflit de réplication se produit lorsqu’il n’est pas clair comment réconcilier les modifications pour atteindre la cohérence des données. Par exemple, quelle mise à jour est prioritaire ? Il doit y avoir un accord commun sur la façon de résoudre les conflits.
Prenons le cas simple où Alice et Bob utilisent une application de coloriage collaborative. Les deux sélectionnent la même zone de l’image à remplir de couleur : Alice choisit de la remplir de jaune ; Bob le remplit de bleu. La zone doit-elle être colorée en jaune ou en bleu (ou en vert : une combinaison des deux mises à jour) ?
La solution la plus courante consiste à disposer d’une politique d’arbitrage unique qui résout de tels conflits à l’aide d’un ensemble de règles, comme la « dernière écriture gagnante », qui utilise l’horodatage de chaque mise à jour pour appliquer les modifications dans l’ordre dans lequel elles se sont produites. Dans le cas ci-dessus, si Bob a fait ses modifications après Alice, elles l’emporteront sur la sienne, et la couleur de la section reste bleue pour Bob et devient bleue pour Alice, ou vice versa si Alice a fait la dernière modification.
Que se passe-t-il si le conflit de réplication ne peut pas être résolu ?
Lorsque les horodatages sont équivalents et ne peuvent pas être utilisés pour résoudre les conflits, la stratégie de résolution peut être une règle telle que « Quel compte a le numéro d’identification le plus bas ? » ou « Quel nom d’utilisateur vient en premier dans l’alphabet ? », entraînant une mise à jour prioritaire. La politique peut être quelque peu arbitraire tant qu’elle est appliquée de manière cohérente par tous les pairs.
Parfois, une approche par force brute est nécessaire, qui, par exemple, abandonne l’effort de réconcilier les changements conflictuels, et elle ne combine pas les mises à jour ni n’en sélectionne une arbitrairement. Dans le cas de Bob et Alice, une approche par force brute peut consister à remplacer les deux modifications, à les ignorer et à rétablir la couleur d’origine de la section, ce qui rend l’expérience utilisateur médiocre mais garantit la cohérence des données. Alice et Bob doivent faire d’autres mises à jour et réconcilier efficacement le conflit eux-mêmes.
Comment Google Docs résout-il les conflits ?
Prenons le cas où Alice et Bob modifient simultanément le même document Google. Alice tape « Hello World! ». Puis elle supprime « Monde ». Bob tape également « Hello World! ».
Alice a fait un ajout et une suppression. Bob a fait un ajout, qui est le même que celui d’Alice. Lorsque nous réfléchissons à la manière de concilier leurs changements, il y a deux interprétations possibles.
Tout d’abord, combinons l’ajout d’Alice, l’ajout de Bob, puis la suppression d’Alice :
Ajout d’Alice + ajout de Bob + suppression d’Alice :
Hello World! + Hello World! - World. Une résolution de conflit sensée détecte que les deux ajouts sont identiques. Il supprime l’un d’eux pour éviter les doublons. Ensuite, le mot « Monde » est supprimé :
Hello World! + Hello World! - World = Hello! Mais que se passe-t-il si vous modifiez l’ordre des modifications ? Considérez l’ajout d’Alice, la suppression d’Alice, puis enfin l’ajout de Bob :
Hello World! - World + Hello World! Maintenant, la résolution des conflits doit déterminer si l’ajout de Bob doit être fusionné avec les deux contributions d’Alice. Les données devraient-elles indiquer « Bonjour ! » (en supprimant tous les ajouts de Bob » ou devrait-il lire « Hello World ! » (en ajoutant le morceau de texte de Bob qui diffère des données après la paire de modifications d’Alice) ?
Légende : L’ordre de traitement des modifications d’Alice et de Bob affectera le texte final.
Google Docs utilise des transformations opérationnelles pour résoudre ce problème de cohérence des données. Basé sur un modèle client-serveur, chaque utilisateur est un client qui détient une réplique du document, et Google Docs agit comme un serveur central. Les modifications d’un client se propagent vers le serveur, qui les transmet aux autres clients.
Que sont les transformations opérationnelles (OT) ?
Lorsqu’une réplique de données change, le client représente les mises à jour comme une ou plusieurs « opérations » (chacune encapsule la modification apportée, et non le résultat de cette modification) et les partage avec un serveur central. Plusieurs clients effectuent des modifications simultanées, ils seront donc chacun dans des états différents. Ils envoient leurs opérations au serveur, qui s’adapte à ces différents états de départ en décidant de l’ordre dans lequel l’ensemble d’opérations en suspens doit être appliqué (en utilisant des règles telles que la dernière écriture gagne). Il transforme ensuite les opérations avant de les propager à chaque client pour les appliquer à leur copie des données.
Que sont les CRDT ?
Les types de données répliqués sans conflit (ou CRDT, parfois appelés « types de données répliqués convergents ou types de données répliqués commutatifs) peuvent résoudre les conflits de réplication résultant d’opérations simultanées sur des réplicas existant dans un environnement décentralisé.
Avec un CRDT, il est mathématiquement toujours possible de fusionner ou de résoudre les mises à jour simultanées sans conflits ni arbitre central. Une approche clé consiste à réduire toutes les opérations d’édition à de simples opérations commutatives afin que l’ordre des modifications n’ait plus d’importance. En pratique, cela prend en charge les changements qui arrivent « dans le désordre » car soit il n’y a pas d’ordre fixe pour les modifications indépendantes se produisant sur différentes répliques ou, lorsqu’il existe une commande valide, il n’y a aucune garantie que les modifications puissent se propager à chaque destinataire pour y adhérer.
Par exemple, si le type de données est une valeur de compteur qui ne peut qu’être incrémentée, l’ordre dans lequel deux opérations se produisent n’a pas d’importance. Si la valeur commence à 0 et une réplique (Alice) envoie un incrément de 12, tandis qu’une autre réplique (Bob) envoie un incrément de 6, les mises à jour combinées sur d’autres réplicas équivalent à la même valeur ( 18) quel que soit l’ordre des modifications appliquées. Bien que toutes les répliques puissent diverger temporairement, les données finiront par revenir à la cohérence (forte cohérence éventuelle).
Légende:
Dans cet exemple, l’ordre dans lequel deux opérations se produisent n’a pas d’importance.
Avec les CRDT basés sur l’état, le client ne transmet pas la ou les opérations qu’il a appliquées pour modifier les données. Au lieu de cela, il envoie le nouvel état des données (en tant que CRDT) à tous les autres clients. Les clients peuvent fusionner avec leurs propres modifications car les CRDT se conforment à une politique cohérente pour résoudre les conflits et éventuellement converger.
Dans les CRDT basés sur les opérations, l’opération de mise à jour est propagée et appliquée localement. Il existe certaines exigences de livraison pour garantir que chaque opération de mise à jour est transmise une seule fois à une réplique car, dans certaines formulations de CRDT, les opérations ne sont pas toujours idempotentes. Une fois qu’ils arrivent au réplica, comme les CRDT basés sur l’état, ils peuvent être appliqués dans n’importe quel ordre.
Pourquoi utiliser les CRDT ?
La suppression délibérée du besoin d’un coordinateur central crée un environnement distribué qui permet l’échange simultané de données entre un grand nombre d’utilisateurs. Dans ces circonstances, un serveur central peut s’avérer peu pratique pour des raisons d’échelle.
De plus, l’absence d’hypothèses sur les serveurs centraux signifie que les CRDT peuvent être utilisés, que ces serveurs fassent ou non partie de la topologie.
Les CRDT simplifient-ils la conception de logiciels ?
Les CRDT ont une approche clémente de l’ordre des opérations. En théorie, cela réduit la complexité de conception des mécanismes de distribution puisqu’il n’y a pas besoin de protocoles de sérialisation stricts. En tolérant des mises à jour hors service, le mécanisme de distribution doit répondre à des garanties d’intégrité plus simples. Cependant, une certaine complexité survient pour une application utilisant le CRDT, car cette structure de données peut ne pas être aussi expressive que les besoins de l’application, que nous décrirons comme suit.
Quels sont les inconvénients des CRDT ?
Pour être indépendants de l’ordre, les CRDT sont limités à un ensemble plus simple et réduit d’opérations autorisées sur les données partagées, ce qui signifie qu’un certain compromis dans l’ensemble des fonctionnalités et l’expérience utilisateur est presque inévitable.
L’exemple classique d’un article de Martin Kleppmann est le suivant. Alice et Charlie tapent simultanément dans le même document en même temps. Les données indiquent déjà « Bonjour ! ». Alice décide d’insérer son nom dans le texte, pour que les données lisent « Bonjour Alice ! ». Pendant ce temps, Charlie a la même idée et insère son nom, donc le texte se lit comme suit : « Bonjour Charlie ! ».
Chaque caractère individuel qu’ils ajoutent est traité comme une insertion distincte dans le document, et ils sont simplement ajoutés, au même point d’insertion, classés par horodatage.
L’ajout des caractères saisis dans l’ordre d’insertion signifie que tout le monde voit la même copie des données, mais le fouillis de modifications qui en résulte ( H e l l o A l C i h a r c l i e e !) n’est pas ce que l’une ou l’autre personne avait l’intention.
Pour éviter ce scénario et d’autres problèmes similaires lorsque les utilisateurs appellent « annuler » ou marquent leur texte, l’algorithme CRDT doit conserver l’état historique pour comparer les modifications au fur et à mesure qu’elles surviennent. Une stratégie intuitive de résolution des conflits est techniquement complexe et pose un problème d’efficacité des ressources par la quantité de stockage nécessaire pour l’état du document.
Où puis-je en savoir plus sur les CRDT ?
Marc Shapiro, Nuno Preguiça, Carlos Baquero et Marek Zawirski ont décrit les CRDT en 2011, et leur article est fondamental pour comprendre les concepts.
Martin Kleppmann n’a cessé de faire avancer le sujet…