Types de données répliquées convergentes et commutatives – Partie 2 : Exemples Pratiques

«La cohérence à terme vise à assurer que les répliques d’un objet partagé modifiable convergent sans synchronisation à priori.»

Ce sujet est composé de deux articles : la première partie est théorique. Elle définit les propriétés mathématiques que doivent respecter les types de données répliqués convergentes et commutatives.

La seconde partie de l’article est un portfolio d’exemples pratiques. Y sont présentés les différents types de base et d’autres types plus élaborés.

Partie 2 : Exemples pratiques


Rappel

  • CvRDT : Type de données répliqués convergentes
  • CmRDT : Type de données répliqués commutatives
  • CRDT : Type de données répliqués convergentes et commutatives
  • LUB : Plus petite limite supérieure
  • Tombstone : Set des éléments supprimés

Compteurs

Basé sur les opérations

Sans overflow, les additions et soustrations commutent. CmRDT

Basé sur l’état / incrément seulement (G-counter)

Supposons un vecteur dont chaque index est réservé à chaque réplique. Le paquet à délivrer est la totalité du vecteur. La valeur du compteur est la somme de tous les éléments du vecteur. La fusion de deux vecteurs est un vecteur dont chaque élément est le maximumm des éléments aux indices correspondant dans les deux autres vecteurs.

Comme le compteur basé sur les opérations, le compteur basé sur l’état fait le postulat que le paquet n’overflow pas et que l’ensemble des répliques est connu.

Exemple : Afficher la durée de fonctionnement cumulée des nœuds du réseau. Chaque nœud possède un indice dans le vecteur et écris dans cet emplacement sa propre durée de fonctionnement.

Compteur PN / incrément et décrément basé sur l’état

Un compteur PN est constitué de deux compteurs à incrément seulement (G-Counter) : l’un servant à compter les incréments et l’autre les décréments. Ainsi la valeur du compteur PN est égale à la différence des deux G-Counter qui le constituent. Notons qu’il est nécessaire d’utiliser une synchronisation supplémentaire pour réaliser un compteur PN non négatif.

Exemple : Afficher le nombre de pairs disponibles pour un fichier torrent partagé en pair-à-pair.

Registres

Dernière-écriture-gagne (LWW)

Dernière-écriture-gagne crée un ordre total en associant à chaque mise à jour un timestamp. L’opération de fusion sélectionne la valeur dont le timestamp est le plus élevé.

Exemple : Ordonnancer des avions dans un point de passage étroit. L’avion qui veut passer lit l’UID contenu dans l’objet partagé. Si il est vide, il y écrit le sien. En cas de conflit, l’UID le plus récent a la priorité. Lorsque le premier avion est passé, il écrit un UID vierge pour indiquer que la voie est libre. (à ne pas tester IRL)

À-valeurs-multiples (MV)

Une alternative est de définir une LUB qui fusionne les assignations concurrentes, par exemple, en prenant leur union : la valeur de l’objet possède autant de valeurs que nécessaire pour représenter ces états concurrents. Les clients peuvent ensuite joindre eux-mêmes plusieurs valeurs de l’union en une seule en procédant à une nouvelle assignation.

La version basée sur l’état est constitué un set d’objets et de leur versions. La requête de la valeur retourne une copie du set. Assigner calcule une version du vecteur qui domine toutes les versions précédentes. L’opération de fusion prend chaque élément des deux sets qui n’est par dominé par un élément de l’autre set.

Exemple : Un gestionnaire de contacts maître-à-maître. Le champ «numéro de téléphone mobile» peut avoir de multiples valeurs. Cela peut être un état stable (le contact possède deux cartes SIM) ou un état de conflit après une édition concurrente divergente. Dans ce cas, le logiciel peut proposer à l’utilisateur de résoudre le conflit manuellement.

Set

Set uniquement croissant (G-Set)

Le set uniquement croissant dispose uniquement des opérations ajouter et valeur, et ne dispose pas de l’opération supprimer. Comme le G-counter, le G-Set n’est pas très utile en soit mais sert de brique de construction pour des structures plus élaborées. L’opération de mise à jour est réalisée en prenant l’union des deux Sets. Les opérations d’ajouts commutent parce que l’union est commutative; G-Set est un CvRDT.

Exemple : Des sondes dans l’espace qui communiquent le set d’UID de planètes où la vie y a été détecté. (à condition que la vie sur une planète soit irrévocable)

Set à deux phases (2P-Set)

Le 2P-Set est une variante du Set où un élément peut être ajouté, supprimé, mais jamais être ajouté à nouveau. Il combine deux G-Set : un pour les éléments ajoutés, l’autre pour les éléments supprimés (aussi appelé tombstone). Pour réduire les anomalies, la suppression d’un élément n’est possible que cet élément est déjà présent localement dans le set des éléments ajoutés.

Exemple : Des sondes qui observent les espèces sur Terre, capable de reconnaitre les nouvelles et déclarer les espèces éteintes.

Set d’éléments uniques (U-Set)

Le 2P-Set peut être simplifié en U-Set à deux conditions : chaque élément est unique, et la suppression d’un élément ne peut se propager que si l’opération d’ajout de ce même élément a déjà été propagée. Cette condition est une synchronisation supplémentaire.

Exemple : Gestionnaire des collections des musées de France : chaque œuvre d’art est unique, et sa possession pour la France dépend des achats et ventes. (cet objet ne supporte pas la contrefaçon)

Set d’éléments dernière-écriture-gagne (LWW-Set)

Cette alternative attache un timestamp à chaque élément. Comme le 2P-Set, un élément est disponible si il fait parti du set des éléments rajoutés. De plus, si cet élément fait également parti du set des éléments supprimés, les deux timestamps sont évalués : si l’élément a été rajouté plus récemment, il est disponible.

Exemple : Chaque station météo d’un système distribué dépose sa position géographique dans le set des éléments ajoutés lorsqu’il commence à pleuvoir, et dans le set des éléments supprimés lorsqu’il cesse de pleuvoir.

PN-Set

Une autre alternative consiste à associer chaque élément du set à un compteur PN. L’élément est disponible si son compteur est strictement positif. Par construction, ce type de données converge, mais possède un comportement particulier. Par exemple, si deux répliques suppriment un élément dont le compteur était égal à 1, cet élément voit son compteur converger vers -1. Ainsi, la prochaine opération d’ajout n’aura pas d’effet apparent parce que l’élément ne sera toujours pas considéré disponible (compteur = 0). Dans certains scénarios, ça peut être le comportement escompté :

Exemple : Une quantité négative de biens dans un entrepôt signifie que ces biens sont en cours d’acheminement.

Set d’éléments observés-supprimable (OR-Set)

Les Set précédents possèdent des applications pratiques mais possèdent des comportement contre-intuitifs. Pour un 2P-Set, un élément supprimé ne peut pas être ajouté à nouveau. Pour le LWW-Set, tout dépends de l’implémentation opaque de la fonction d’allocation de timestamp uniques.

Dans un OR-Set, chaque élément du Set est adjoint d’un identifiant unique qui n’apparait pas dans l’interface des opérations du Set. L’opération de recherche renvoie vrai si l’élément est présent dans au moins une paire. L’opération d’ajout génère un identifiant unique à l’élément ajouté. L’opération de suppression d’un élément supprime toutes les paires contenants l’élément au moment de la suppression. L’ajout et la suppression du même élément n’a pas d’effet car la suppression a forcément lieu avant : uniquement les éléments observés sont supprimables.

Ainsi, un nœud n’a le droit de supprimer que les éléments qu’il observe au moment de la suppression.

Exemple : Panier d’achat observé-supprimable

Les éléments du OR-Set sont composé de la paire : identifiant du livre (ISBN), et nombre d’exemplaires dans le paniers. Chaque élément est associé à son identifiant unique.

Les deux opérations d’ajout et de suppression sont définies. L’ajout d’un livre ou plusieurs exemplaires d’un livre ajoute un nouvel élément au OR-Set. La suppression d’un certain nombre d’exemplaires observés dans le OR-Set est exécuté en deux étapes. Tout d’abord, tous les éléments observés du OR-Set dont le ISBN correspond sont supprimés. Puis la mise à jour est propagée et on attend que toutes les répliques soient à jour. Ensuite, selon le nombre de livres restants, le cas échéant, la réplique rajoute les exemplaires restants et propage la mise à jour.

Graphes

Graphe simple (2P2P-Graph)

Un graphe est constitué de sommets (V) et d’arêtes (E). Les opérations sur les sommets et arêtes ne sont pas indépendants parce que chaque arête est composée de sommets déjà existants. Une arête ne peut être ajoutée que si les deux sommets existent déjà et un sommet ne peut être supprimé que s’il ne supporte aucune arête. Lors de la concurrence ajouterArête(u,v) et supprimerSommet(u), on ajoute d’abord l’arête puis on la supprime comme effet secondaire de la suppression d’un sommet la constituant.

Exemple : Les liaisons de transport reliant les villes de France.

Graphe orienté acyclique (DAG) monotone à croissance uniquement

Certaines propriétés comme la forme d’un graphe ne peuvent pas être représenté par un CRDT parce qu’un invariant global ne peut pas être déterminé localement; cela nécessite de la synchronisation.

Cependant, il est possible de spécifier des invariants locaux plus restrictifs afin de garantir l’invariant global ! C’est le cas notamment du graphe orienté acyclique monotone pour lequel une arête ne peut être ajoutée que si elle est orientée dans la même direction que les chemins déjà existants. Une nouvelle arête renforce forcément l’ordre partiel défini par le DAG; le graphe reste acyclique.

Si on limite les opérations à l’ajout uniquement, les ajouts concurrents concernant des arêtes différentes commutent. En cas d’ajout concurrent de la même arête, un seul ajout est effectué (idempotence). Ce type est bien un CRDT.

Type de données à ordre partiel avec ajout et suppression

Plutôt que de renforcer les invariants locaux dans l’optique de maintenir un invariant global, on peut également choisir un invariant global plus souple. C’est le cas du type de données à ordre partiel avec ajout et suppression. Puisque l’ordre partiel est transitif, tous les chemins alternatifs existent implicitement. Afin d’assurer la transitivité, les sommets retirés sont conservés dans un Set dédié (tombstone). Les sommets sont stockés dans un 2PSet et les arêtes dans un G-Set.

Exemple : Édition coopérative de texte

L’édition de texte coopératif pair-à-pair est un cas d’usage intéressant de l’ordre d’ajout-suppression. Un document texte est un ensemble d’éléments textuels. Les utilisateurs peuvent ajouter ou retirer un élément. L’utilisation d’un CRDT pour ce cas d’usage permet d’assurer que les éditions concurrentes ne seront jamais en conflits et convergent, même pour des utilisateurs qui sont déconnectés du réseau tant qu’ils se reconnectent à la longue.

Un type de données à ordre partiel n’est pas suffisant car un texte a ses éléments totalement ordonnés. Il faut ajouter un ordre total pour que ce soit utilisable pour l’édition coopérative de texte. Tout type de données à ordre total est un CRDT car dérivant d’un type de données à ordre partiel.

Tableau agrandissable répliqué (RGA)

Le RGA implémente une séquence comme une liste chainée (un graphe linéaire). Chaque élément est adjoint d’un timestamp unique qui permet d’assurer l’histoire causale en cas d’évènements concurrents.

Séquence continue

Plutôt que d’ordonner les éléments dans une liste, il est possible de les placer dans un espace ordonné continu (comme l’espace des Réels). De cette manière, il est toujours possible de trouver un nouvel index entre deux index existants.

Arbre des identifiants comme continuum : Chaque élément est adjoint d’un identifiant unique ordonné. Les éléments sont classés entre eux dans un arbre des identifiants comme continuum.

Identifiants : Le nœud racine a un identifiant vide. L’identifiant d’un nœud est constitué de l’identifiant de son parent, de sa direction par rapport à son parent (gauche ou droite) et de son tag unique. Un nœud parent peut avoir plusieurs nœuds fils gauches ou plusieurs nœuds fils droits. Un nœud est plus petit que son nœud frère si il est situé à gauche et son frère à droite. Si ils sont situés du même côté, ils sont ordonnés par rapport à leur tag unique. Un nœud est plus petit que n’importe quel nœud parent si il est un des fils gauche de son parent, ou fait partie de la descendance de l’un de ses fils gauche. Enfin, un nœud est plus petit qu’un autre nœud en fonction des nœuds frères les plus proche du nœud parent commun.

Ramasse-miette

Les CRDT ne sont pas des structure optimisées : ils ont tendances à grossir avec l’utilisation parce qu’il faut garder en mémoire les nœuds supprimés, ou bien leur arbre d’identifiants devient déséquilibré. Des mécanismes de ramasse-miettes peuvent être mis en place, mais doivent s’assurer de la stabilité et du respect des engagements entre les répliques. Quand ces conditions ne sont pas réunies, le ramasse-miette peut bloquer. Bien que cela impacte les performances, les objets restent intègres et utilisables ce qui est suffisant.

Problème de stabilité

Stabilité : Une mise à jour est stable si, pour la réplique observée, toutes les mises à jour qui pourraient modifier l’ordre causal de cette dernière mise à jour ont été reçues.

Une réplique peut connaitre l’état de stabilité d’une mise à jour si elle connaît les autres répliques et que ces dernières sont en vie. Ainsi, avec chaque une mise à jour est transmit un tableau de timestamps. Chaque réplique maintiens le timestamp de chaque autre réplique à jour en interne. Ce timestamp permet d’identifier toutes les mises à jour émises par la réplique observée et leur réception pour chaque autre réplique. Les répliques doivent périodiquement envoyer leur vecteur de timestamps, éventuellement en envoyant une mise à jour vide. Avec toutes ces informations, si tous les timestamps des autres réplique sont plus récent que le timestamp de la réplique observée, alors cette réplique est stable.

Ce genre d’informations est peut-être déjà en place dans le système de broadcast fiable, et le ramasse-miette peut avoir lieu en arrière-plan.

Problèmes d’engagement

Certains ramasse-miettes ont des contraintes fortes à respecter pour ne pas compromettre l’intégrité des objets : par exemple ré-équilibrer un arbre ou nettoyer les tombstones d’un 2P-Set. Ces opérations nécessitent la connaissance de toutes les répliques et leur coopération. Une manière d’adoucir ces contraintes est de différencier les répliques du noyau des autres répliques : seules les répliques du noyau coopèrent lors des opérations de ramasse-miette. Les autres répliques réconcilient leurs états avec ceux du core.

Credits

Merci d’avoir lu cet article jusque là ! N’hésite pas à écrire des commentaires pour me dire ce que t’en penses ! Je pense qu’une prochaine étape intéressante serait de mettre en pratique quelques exemples pour voir à quoi ça ressemble dans la vraie vie. =)


Photo : Planes – Pravanian

Légende : Les avions de l’exemple de navigation LWW 😉

Laisser un commentaire

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax