Comment compter les visites sur la page google.com? Et comment stocker le compteur de likes d'utilisateurs très populaires? Cet article propose d'envisager de résoudre ces problèmes à l'aide de CRDT (Conflict-free Replicated Data Types, qui en russe se traduit approximativement par Conflict-Free Replicated Data Types), et dans le cas plus général, des tâches de synchronisation de répliques dans un système distribué avec plusieurs nœuds principaux.

1. Introduction

Nous sommes habitués depuis longtemps à utiliser des applications telles qu'un calendrier ou un service de notes tel qu'Evernote. Ils sont unis par le fait qu'ils vous permettent de travailler hors ligne, depuis plusieurs appareils et vers plusieurs personnes en même temps (sur les mêmes données). Le défi auquel sont confrontés les développeurs de chacune de ces applications est de savoir comment assurer la synchronisation la plus «fluide» des données modifiées simultanément sur plusieurs appareils. Idéalement, la participation des utilisateurs ne devrait pas du tout être requise pour résoudre les conflits de fusion.

Dans un article précédent, nous avons déjà envisagé une approche pour résoudre ces problèmes - Transformation opérationnelle, il décrira également une méthode très similaire qui présente à la fois des avantages et des inconvénients (par exemple, CRDT pour JSON n'a pas encore été inventé. Mise à jour : Merci à msvn pour le lien, ici voici un projet des auteurs d'un article de recherche sur l'implémentation de JSON en CRDT)

2. Forte cohérence éventuelle

Récemment, beaucoup de travaux ont été écrits et beaucoup de recherches ont été faites dans le domaine de la cohérence éventuelle. À mon avis, il y a maintenant une forte tendance à passer d'une forte cohérence à diverses options de cohérence, à rechercher quelle cohérence dans quelles situations / systèmes il est plus rentable d'appliquer, à repenser les définitions existantes. Cela conduit à une certaine confusion, par exemple, lorsque les auteurs de certains travaux, parlant de cohérence, signifient une cohérence éventuelle avec une propriété supplémentaire, et que d'autres auteurs utilisent une certaine terminologie pour cela.

La question posée par les auteurs de l'un des articles critique la définition actuelle de la cohérence éventuelle: selon elle, si votre système répond toujours «42» à toutes les demandes, alors tout est OK, il est finalement cohérent.

Sans violer l'exactitude de cet article, j'utiliserai, suivant les auteurs des articles originaux, la terminologie suivante (veuillez noter que ce ne sont pas des définitions strictes, ce sont des différences):

• Forte cohérence (SC): toutes les opérations d'écriture sont strictement ordonnées, une demande de lecture sur n'importe quelle réplique renvoie le même résultat enregistré en dernier. Un consensus en temps réel est nécessaire pour résoudre les conflits (avec les conséquences qui en découlent), peut résister à une chute à n / 2 - 1 nœuds.
• Cohérence éventuelle (EC): mettez à jour les données localement, envoyez la mise à jour plus loin. La lecture sur différentes répliques peut renvoyer des données périmées. En cas de conflit, soit nous reculons, soit nous décidons quoi faire. T.O. un consensus est encore nécessaire, mais plus en temps réel .
• Forte cohérence éventuelle (SEC): EC + pour la résolution des conflits, les répliques ont un algorithme prédéfini. T.O. le consensus n'est pas nécessaire , il peut résister à une chute à n - 1 nœuds.

Notez que SEC (pour ainsi dire) résout le problème du théorème CAP: les trois propriétés sont satisfaites.

Donc, nous sommes prêts à faire don de SC et voulons avoir un certain ensemble de types de données de base pour notre système distribué potentiellement instable qui résoudra automatiquement les conflits d'écriture pour nous (aucune interaction utilisateur ou demande à un arbitre n'est requise)

3. Tâches concernant les likes et les hits

Sans aucun doute, il existe plusieurs algorithmes pour résoudre ces problèmes. CRDT offre un moyen assez élégant et facile.

Nombre de visites sur Google.com:

google.com traite environ 150 000 demandes par seconde du monde entier. De toute évidence, le compteur doit être mis à jour de manière asynchrone. Les files d'attente résolvent partiellement le problème - par exemple, si nous fournissons une API externe pour obtenir cette valeur, nous devrons effectuer une réplication afin de ne pas mettre le référentiel avec des demandes de lecture. Et s'il existe déjà une réplication, peut-être sans files d'attente globales?

Compter les goûts des utilisateurs:

La tâche est très similaire à la précédente, seulement maintenant vous devez compter les hits uniques.

4. Terminologie

Pour une compréhension plus complète de l'article, vous devez connaître les termes suivants:

1. Idempotence
   Dit que l'application de l'opération plusieurs fois ne change pas le résultat.
   Exemples - opération GET ou addition avec zéro: $$$f (x) = x + 0$
   
2. Commutativité
   $$$f (x, y) = f (y, x)$
   
3. Ordre partiel
   Réflexivité + Transitivité + Antisymétrie
   
4. Demi-réseau
   Ensemble partiellement ordonné avec face supérieure (inférieure) exacte
   
5. Version vecteur
   Un vecteur de dimension est égal au nombre de nœuds et chaque nœud, lorsqu'un certain événement se produit, incrémente sa valeur dans le vecteur. Pendant la synchronisation, les données sont transmises avec ce vecteur et cela introduit une relation d'ordre, qui vous permet de déterminer quelle réplique contient des données anciennes / nouvelles.

5. Modèles de synchronisation

Basé sur l'état:

Également appelé synchronisation passive, il forme le type de données répliqué convergent - CvRDT.
Il est utilisé dans des systèmes de fichiers tels que NFS, AFS, Coda et dans les stockages KV Riak, Dynamo
Dans ce cas, les répliques échangent des états directement, la réplique réceptrice fusionne l'état reçu avec son état actuel.


Pour effectuer la convergence des répliques à l'aide de cette synchronisation, il est nécessaire que:

• Les données ont formé un demi-réseau
• La fonction de fusion a produit une limite supérieure exacte
• Les répliques ont formé un graphique connecté.

Un exemple:

• Jeu de données: nombres naturels $$$\ mathbb {N}$
• Article minimum: $$$- \ infty$
• $$$fusion (x, y) = max (x, y)$

De telles exigences nous donnent une fonction de fusion commutative et idempotente qui croît de façon monotone sur un ensemble de données donné:


Cela garantit que les répliques convergent tôt ou tard et vous permet de ne pas vous soucier du protocole de transfert de données - nous pouvons perdre des messages avec un nouvel état, les envoyer plusieurs fois et même les envoyer dans n'importe quel ordre .

Basé sur l'opération:

Également appelé synchronisation active, il forme le type de données répliqué commutatif - CmRDT.
Utilisé dans les systèmes coopératifs tels que Bayou, Rover, IceCube, Telex.

Dans ce cas, les répliques échangent des opérations de mise à jour d'état. Lors de la mise à jour des données, la réplique d'origine:

• Appelle la méthode generate (), qui renvoie la méthode effector () à exécuter sur les répliques restantes. En d'autres termes, effecteur () est la fermeture pour changer l'état des répliques restantes.
• Application d'un effecteur à un état local
• Envoie effecteur à toutes les autres répliques

Pour effectuer la convergence des répliques, les conditions suivantes doivent être remplies:

• Protocole de livraison fiable
• Si l'effecteur est livré à toutes les répliques conformément à l'ordre entré (pour un type donné), alors les effecteurs simultanés sont commutatifs, ou
• Si l'effecteur est livré à toutes les répliques sans tenir compte de la commande, alors tous les effecteurs sont commutatifs.
• Dans le cas où l'effecteur peut être livré plusieurs fois, il doit être idempotent
• Certaines implémentations utilisent des files d'attente (Kafka) dans le cadre du protocole de livraison.

Basé sur Delta:

En considérant l'état / op, il est facile de remarquer que si une mise à jour ne modifie qu'une partie de l'état, alors cela n'a aucun sens d'envoyer tout l'état, et si un grand nombre de modifications affectent un état (par exemple, un compteur), alors vous pouvez envoyer un, changement agrégé et pas toutes les opérations changements.

La synchronisation delta combine les deux approches et envoie des mutateurs delta qui mettent à jour l'état en fonction de la dernière date de synchronisation. Lors de la synchronisation initiale, il est nécessaire d'envoyer complètement l'état, et certaines implémentations dans de tels cas prennent déjà en compte l'état des répliques restantes lors de la construction de delta-mutateurs.

La méthode d'optimisation suivante consiste à compresser le journal basé sur les opérations, si des retards sont autorisés.

Basé purement sur les opérations:

Il y a un retard dans la création de l'opector dans la synchronisation basée sur les opérations. Dans certains systèmes, cela peut ne pas être acceptable, alors vous devez envoyer la modification d'origine au prix de compliquer le protocole et la quantité supplémentaire de métadonnées.

Approches d'utilisation standard:

• Si les mises à jour doivent être envoyées immédiatement dans le système, alors basé sur l'état serait un mauvais choix, car l'envoi de l'état entier est plus cher qu'une simple opération de mise à jour. Delta-based fonctionne mieux, mais dans ce cas particulier, la différence avec state-based sera faible.
• Si vous avez besoin de synchroniser la réplique après une panne , alors basé sur l'état et basé sur le delta sont le choix parfait. Si vous devez utiliser une opération, les options sont les suivantes:
  
  1) Lancer toutes les opérations manquées à partir du moment de l'échec
  2) Une copie complète de l'une des répliques et la restauration des opérations manquées
• Comme indiqué ci-dessus, basé sur les opérations nécessite que les mises à jour soient livrées exactement une fois à chaque réplique. L'obligation de livraison ne peut être supprimée qu'une seule fois si l'effecteur est idempotent. En pratique, il est beaucoup plus facile de mettre en œuvre le premier que le second.

La relation entre Op-based et State-based:

Deux approches peuvent être émulées l'une par rapport à l'autre, donc à l'avenir, nous considérerons le CRDT sans référence à un modèle de synchronisation spécifique.

6. CRDT

6.1 Compteur

Un entier qui prend en charge deux opérations: inc et dec. Par exemple, considérez les implémentations possibles pour les synchronisations basées sur les opérations et les états:

Compteur basé sur les opérations:

De toute évidence, il suffit d'envoyer des mises à jour. Exemple pour inc:

function generator() { return function (counter) { counter += 1 } } 

Compteur basé sur l'état:

L'implémentation n'est plus aussi évidente, car on ne sait pas à quoi devrait ressembler la fonction de fusion.

Considérez les options suivantes:

Compteur à augmentation monotone (compteur à incrémentation uniquement, compteur G):

Les données seront stockées comme un vecteur de dimension égale au nombre de nœuds (vecteur de version) et chaque réplique augmentera la valeur en position avec son id.

La fonction de fusion prendra un maximum dans les positions correspondantes, et la valeur finale est la somme de tous les éléments du vecteur

$$

$$\ begin {align} inc () &: V [id ()] = V [id ()] + 1 \\ value () &: \ sum_ {i = 0} ^ {n} V [i] \\ fusionner (C_1, C_2) &: i \ in [1..n] \ Result [i] = max (C_1.V [i], C_2.V [i]) \ end {align}$$

Vous pouvez également utiliser le G-Set (voir ci-dessous)

Application:

• Compter les clics / hits (sic!)

Compteur avec support de décrémentation (compteur PN)

Nous commençons deux G-compteur - un pour les opérations d'incrémentation, le second - pour décrémenter

Application:

• Le nombre d'utilisateurs connectés dans un réseau p2p, tel que Skype

Compteur non négatif

Une implémentation simple n'existe pas encore. Suggérez vos idées dans les commentaires, discutez.

6.2 S'inscrire

Une cellule mémoire avec deux opérations - assigner (écrire) et valeur (lire).
Le problème est que l'attribution n'est pas commutative. Il existe deux approches pour résoudre ce problème:

Registre des derniers gains en écriture (registre LWW):

Nous entrons la commande complète grâce à la génération d'un identifiant unique pour chaque opération (horodatage, par exemple).

Un exemple de synchronisation est l'échange de paires (valeur, id):


Application:

• Colonnes à cassandra
• NFS - fichier en tout ou en partie

Enregistrez-vous avec plusieurs valeurs (Multi-Value Register, MV-Register):

L'approche est similaire à un compteur G - nous stockons l'ensemble (valeur, vecteur de version). Enregistrer la valeur - toutes les valeurs, lors de la fusion - LWW séparément pour chaque valeur dans le vecteur.


Application:

• Panier en Amazonie. Un bug bien connu est associé à cela, lorsque, après avoir retiré un article du panier, il y apparaît à nouveau. La raison en est que malgré le fait que le registre stocke un ensemble de valeurs, ce n'est pas un ensemble (voir l'image ci-dessous). Amazon, d'ailleurs, ne considère même pas cela comme un bug - en fait, il augmente les ventes.
• Riak. Dans un cas plus général, nous déplaçons le problème du choix de la valeur réelle (note - il n'y a pas de conflit!) À l'application.

Explication du bug dans Amazon:

6.3 Beaucoup

L'ensemble est le type de base pour la construction de conteneurs, de cartes et de graphiques et prend en charge les opérations - add et rmv, qui ne sont pas commutatives.

Considérez l'implémentation naïve de l'ensemble basé sur les opérations, dans lequel add et rmv sont exécutés à leur arrivée (add vient à 1 et 2 répliques en même temps, puis rmv passe à 1)


Comme vous pouvez le voir, les répliques se sont finalement dispersées. Considérez les différentes options pour construire des ensembles sans conflit:

Ensemble de croissance (G-Set):

La solution la plus simple consiste à empêcher la suppression d'éléments. Il ne reste que l'opération add, qui est commutative. La fonction de fusion est l'union des ensembles.

Ensemble biphasé (ensemble 2P):

Nous vous autorisons à supprimer, mais vous ne pouvez pas l'ajouter à nouveau après la suppression. Pour l'implémenter, nous avons mis en place un ensemble distinct d'éléments G-set distants (un tel ensemble est appelé un ensemble tombstone)
Exemple pour un état:

$$

$$\ begin {align} lookup (e) &: e \ in A \ land e \ notin R \\ add (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ merge (S_1, S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {align}$$

Ensemble d'éléments LWW:

La prochaine façon d'implémenter un ensemble sans conflit est d'introduire un ordre complet, l'une des options est de générer des horodatages uniques pour chaque élément.

Nous obtenons deux ensembles - add-set et remove-set, lorsque add () est appelé, add (element, unique_id ()), en vérifiant s'il y a un élément dans l'ensemble - regardez où l'horodatage est plus grand - dans remove-set ou dans add-set

PN-Set:

Variation avec ordre de l'ensemble - on démarre un compteur pour chaque élément, quand on l'ajoute, on l'augmente, quand on le supprime on le diminue. Un élément est dans l'ensemble si son compteur est positif.

Notez l'effet intéressant - dans la troisième réplique, l'ajout d'un élément ne conduit pas à son apparition.

Ensemble d'observation-suppression, ensemble OU, ensemble ajout-gain:

Dans ce type, ajouter a priorité sur supprimer. Exemple d'implémentation: chaque élément nouvellement ajouté se voit attribuer une balise unique (relative à l'élément, et non à l'ensemble complet). Rmv supprime un élément de l'ensemble et envoie toutes les paires vues (élément, balise) aux répliques pour suppression.

Ensemble gagnant-gagnant:

Similaire au précédent, mais en même temps, ajoutez / rmv rmv gagne.

6.4 Graphique

Ce type est construit sur la base de nombreux. Le problème est le suivant: s'il y a des opérations simultanées addEdge (u, v) et removeVertex (u) - que dois-je faire? Les options suivantes sont possibles:

• Priorité RemoveVertex, toutes les arêtes incidentes à ce sommet sont supprimées
• Priorité AddEdge, sommets supprimés restaurés
• Nous retardons l'exécution de removeVertex jusqu'à ce que tous les addEdge simultanés soient exécutés.

L'option la plus simple est la première, pour sa mise en œuvre (2P2P-Graph) il suffit d'obtenir deux 2P-Set, un pour les sommets, le second pour les bords

6.5 Carte

Carte des littéraux:

Deux problèmes à résoudre:

• Que faire des opérations de vente simultanées? Par analogie avec les compteurs, vous pouvez choisir la sémantique LWW ou MV
• Que faire avec put / rmv simultané? Par analogie avec les ensembles, vous pouvez soit mettre-victoires, ou rmv-victoires, ou la dernière sémantique gagne-sémantique.

Cartographie CRDT (Carte des CRDT):

Un cas plus intéressant, car vous permet de créer des mappages imbriqués. Nous ne considérons pas les cas de changement de types imbriqués - cela devrait être décidé par le CRDT imbriqué lui-même.

Supprimer la carte en tant que réinitialisation récursive

L'opération de suppression "réinitialise" la valeur du type à un certain état de départ. Par exemple, pour un compteur, il s'agit d'une valeur nulle.

Prenons un exemple - une liste de courses générale. Un des utilisateurs ajoute de la farine et le second effectue un paiement (cela conduit à un appel à l'opération de suppression sur tous les éléments). En conséquence, une unité de farine reste sur la liste, ce qui semble logique.


Supprimer-gagne la carte

L'opération rmv a priorité.

Exemple: dans un jeu en ligne, un joueur Alice a 10 pièces et un marteau. Ensuite, deux événements se produisent simultanément: sur la réplique A, elle a produit un clou, et sur la réplique B, son personnage est supprimé avec la suppression de tous les objets:



Notez que lors de l'utilisation de remove-as-récursif, un clou resterait finalement, ce qui n'est pas l'état correct lorsque le personnage est supprimé.

Mettre à jour-gagne la carte

Les mises à jour ont priorité, ou plutôt annulent les opérations précédentes pour supprimer simultanément rmv.

Exemple: dans un jeu en ligne, le personnage d'Alice sur la réplique B est supprimé en raison de l'inactivité, mais l'activité se produit sur la réplique A en même temps. De toute évidence, l'opération de suppression doit être annulée.


Il y a un effet intéressant lorsque vous travaillez avec une telle implémentation - supposons que nous avons deux répliques, A et B, et qu'elles stockent l'ensemble par une clé k. Ensuite, si A supprime la valeur de la clé k et B supprime tous les éléments de l'ensemble, alors à la fin les répliques laisseront un ensemble vide avec la clé k.

Notez qu'une implémentation naïve ne fonctionnera pas correctement - vous ne pouvez pas simplement annuler toutes les opérations de suppression précédentes. Dans l'exemple suivant, avec cette approche, l'état final serait comme l'état initial, ce qui est incorrect:

Liste

Le problème avec ce type est que les indices d'élément sur différentes répliques seront différents après les opérations locales d'insertion / suppression. Pour résoudre ce problème, l'approche de transformation opérationnelle est appliquée - lors de l'application du changement obtenu, l'indice de l'élément dans la réplique d'origine doit être pris en compte.

7. Riak

À titre d'exemple, considérons CRDT dans Riak:

• Compteur: PN-Counter
• Set: OU-Set
• Carte: mise à jour remporte la carte des CRDT
• (Boolean) Flag: OR-Set où maximum 1 élément
• Registre: paires (valeur, horodatage)

8. Qui utilise CRDT

La section wiki contient de bons exemples.

9. Références

• Magasins Key-CRDT
• Un type de données JSON répliqué sans conflit
• Une étude approfondie des types de données répliquées convergentes et commutatives
• Type de données répliqué convergent et commutatif
• Type de données répliqué sans conflit
• Un guide Bluffers sur les CRDT à Riak
• CRDT: une MISE À JOUR (ou juste un PUT)
• Types de données répliquées sans conflit: vue d'ensemble
• Forte cohérence éventuelle et types de données répliquées sans conflit
• Structures de données finalement cohérentes