La résolution automatique des conflits dans un environnement avec plusieurs nœuds principaux (dans cet article, un nœud principal se réfère à un nœud qui accepte les demandes de changement de données) est un domaine de recherche très intéressant. Il existe plusieurs approches et algorithmes différents, selon l'application, et cet article traitera de la technologie des transformations opérationnelles (OT) pour résoudre les conflits dans les applications d'édition collaborative telles que Google Docs et Etherpad.

1. Introduction

La collaboration est difficile d'un point de vue technique, car plusieurs personnes peuvent apporter des modifications différentes à la même section de texte à presque les mêmes moments. Étant donné que la livraison de données via Internet n'est pas instantanée (la vitesse de transfert de données dans la fibre a des limites), chaque client travaille avec une version locale (réplique) du document édité pour simuler une réponse instantanée, qui peut différer des versions des autres participants. Et le principal problème est d'assurer la cohérence entre les versions locales, ou en d'autres termes, de garantir que toutes les versions locales convergent tôt ou tard dans la même version correcte d'un document (nous ne pouvons pas obliger tous les clients à certains moments ont eu simultanément la même version, car le processus d'édition peut être sans fin).

Ancienne version de Google Docs

Au départ, Google Docs, comme de nombreuses autres applications collaboratives d'édition de documents, utilisait une simple comparaison du contenu des différentes versions d'un document. Supposons que nous ayons deux clients - Petya et Vasya, et que l'état actuel du document soit synchronisé entre eux. Dans l'ancienne version du serveur Google de Google, lors de la réception d'une mise à jour de Petya, il calcule la différence (diff) entre sa version et la sienne et essaie de fusionner les deux versions en une seule de la meilleure façon possible. Ensuite, le serveur envoie la version reçue à Vasya. Si Vasya a des modifications non envoyées au serveur, le processus se répète - vous devez fusionner la version du serveur avec la Vasina locale et la renvoyer au serveur.

Très souvent, cette approche ne fonctionne pas très bien. Par exemple, supposons que Petya, Vasya et le serveur commencent par un document synchronisé avec le texte « Le renard brun rapide ».


Petya met en évidence les mots renard brun en gras, tandis que Vasya remplace le mot renard par chien . Laissez Petina changer d'abord sur le serveur et il envoie la version mise à jour de Vasya. Il est clair que le résultat final devrait être Le chien brun rapide , mais il n'y a pas suffisamment d'informations pour que les algorithmes de fusion le comprennent, les options Le chien renard brun rapide , Le chien brun rapide , Le renard chien brun rapide sont absolument correctes. (Par exemple, dans git dans de tels cas, vous obtiendrez un conflit de fusion et vous devrez gouverner avec vos mains). C'est le principal problème de cette approche - vous ne pourrez pas être sûr des résultats de la fusion si vous ne vous fiez qu'au contenu du document.

Vous pouvez essayer d'améliorer la situation et bloquer la capacité des autres participants à modifier des sections de texte que quelqu'un a déjà définies. Mais ce n'est pas ce que nous voulons - cette approche essaie simplement d'éviter de résoudre un problème technique en aggravant l'expérience utilisateur, et il peut également y avoir une situation où deux participants ont commencé à éditer la même phrase en même temps - et alors l'un d'eux perdra les modifications ou il devra combiner manuellement les modifications en cas de conflits ci-dessus.

Nouvelle version de Google Docs

Dans la nouvelle version de Google Docs, une approche complètement différente a été utilisée: les documents sont stockés comme une séquence de modifications et au lieu de comparer le contenu, nous roulons les modifications dans l'ordre (ci - après dénommé la relation de commande ). En sachant comment l'utilisateur a modifié le document et en tenant compte de ses intentions, nous pouvons déterminer correctement la version finale après avoir combiné toutes les modifications.

D'accord, nous devons maintenant comprendre quand appliquer les changements - nous avons besoin d' un protocole de collaboration .

Dans Google Docs, toutes les modifications de documents se résument à trois opérations différentes:

• Insertion de texte
• Supprimer le texte
• Application de styles au texte

Ainsi, lorsque vous modifiez un document, toutes vos actions sont stockées exactement dans cet ensemble d'opérations et elles sont ajoutées à la fin du journal des modifications. Lorsque le document est affiché, le journal des modifications sera exécuté à l'aide des opérations enregistrées.

Une petite remarque: le premier produit (public) de Google avec prise en charge OT était, apparemment, Google Wave. Il a soutenu une gamme d'opérations beaucoup plus large.

Exemple

Que Petya et Vasya partent du même état de «HABR 2017».
Petya change de 2017 à 2018, cela crée en fait 2 opérations:


Dans le même temps, Vasya change le texte en «HELLO HABR 2017»:


Vasya reçoit l'opération de Petin pour supprimer, s'il l'applique simplement, alors le mauvais texte sera obtenu (le chiffre 7 aurait dû être supprimé):


Pour éviter cela, Vasya doit transformer les opérations de Petin conformément à ses changements locaux actuels (en d'autres termes, les opérations sont contextuelles):

$$

$$\ {Delete \ \ @ 8 \} \ rightarrow \ {Delete \ \ @ 15 \}$$

En parlant un peu plus formellement, considérons cet exemple:


Ensuite:

$$

$$O1 ’(O2 (X)) = O2’ (O1 (X))$$

Voila! L'algorithme décrit est appelé transformation opérationnelle.

2. Transformation opérationnelle

Modèle de cohérence

Pour assurer la cohérence, plusieurs modèles de cohérence ont été développés, pensez à l'un d'eux - CCI.

Le modèle CCI fournit trois propriétés:

1. Convergence: toutes les répliques d'un document commun doivent être identiques une fois toutes les opérations terminées:
   
   
   
   Dans cet exemple, les deux utilisateurs commencent avec des répliques identiques. Ensuite, ils modifient le document et les répliques divergent - de cette façon, le temps de réponse minimum est atteint. Après avoir envoyé des modifications locales à d'autres clients, la propriété de convergence requiert que l'état final du document pour tous les clients devienne identique.
2. Préservation de l'intention: l'intention d'une opération doit être stockée sur toutes les répliques, qu'elle se chevauche ou non pour effectuer plusieurs opérations en même temps. L'intention d'une opération est définie comme l'effet de son exécution sur la copie où elle a été créée.
   
   Prenons un exemple où cette propriété échoue:
   
   
   
   
   Les deux clients démarrent avec les mêmes répliques, puis effectuent les modifications. Pour Petya, l'intention de son opération est d'insérer '12' sur le premier index, et pour Vasya, supprimer les caractères avec les indices 2 et 3. Après la synchronisation avec Petya Vasino, l'intention et avec Vasya Petino l'intention est violée. Notez également que les répliques ont divergé, mais ce n'est pas une exigence pour la propriété en question. La version finale correcte est proposée pour identifier le lecteur comme un petit exercice.
   
3. Préservation de la causalité: les opérations doivent être effectuées dans un ordre causal (basé sur la relation avant-passé ).
   
   Prenons un exemple où cette propriété échoue:
   
   
   
   
   Comme vous pouvez le voir, Petya a envoyé à Vasya et à l'agent Smith sa modification du document, Vasya l'a reçu en premier et a supprimé le dernier caractère. En raison du retard du réseau, Smith reçoit la première opération pour Vasin pour supprimer un caractère qui n'existe pas encore.
   
   OT ne peut pas garantir que la propriété de préservation de la causalité est remplie; par conséquent, des algorithmes tels qu'une horloge vectorielle sont utilisés à ces fins.
   

Conception OT

L'une des stratégies de conception du système OT est la division en trois parties:

• Algorithmes de contrôle de transformation: déterminez quand l'opération (cible) est prête à se transformer, en ce qui concerne les opérations (référence) que les transformations doivent être effectuées et dans quel ordre les exécuter.
• Fonctions de transformation: Transforme l'opération cible en tenant compte de l'impact des opérations de référence.
• Exigences et propriétés des transformations (propriétés et conditions): assurer la connexion entre ces composants et effectuer des vérifications d'exactitude.

Fonctions de conversion

Les fonctions de conversion peuvent être divisées en deux types:

• Inclusion / Transformation vers l'avant: Transformer une opération $$$O_a$ avant la chirurgie $$$O_b$ de sorte que l'effet de $$$O_b$ (par exemple deux inserts)
• Exclusion / Backward Transformation: Transformation d'une opération $$$O_a$ avant la chirurgie $$$O_b$ de sorte que l'effet de $$$O_b$ exclus (par exemple, insérer après la suppression)

Un exemple pour les opérations symboliques d'insertion / suppression (i - insérer, d - supprimer):

Tii(Ins[p1, c1], Ins[p2, c2]) { if (p1 < p2) || ((p1 == p2) && (order() == -1)) // order() –   return Ins[p1, c1]; // Tii(Ins[3, 'a'], Ins[4, 'b']) = Ins[3, 'a'] else return Ins[p1 + 1, c1]; // Tii(Ins[3, 'a'], Ins[1, 'b']) = Ins[4, 'a'] } Tid(Ins[p1, c1], Del[p2]) { if (p1 <= p2) return Ins[p1, c1]; // Tid(Ins[3, 'a'], Del[4]) = Ins[3, 'a'] else return Ins[p1 – 1, c1]; // Tid(Ins[3, 'a'], Del[1]) = Ins[2, 'a'] } Tdi(Del[p1], Ins[p2, c1]) { //   ,    } Tdd(Del[p1], Del[p2]) { if (p1 < p2) return Del[p1]; // Tdd(Del[3], Del[4]) = Del[3] else if (p1 > p2) return Del[p1 – 1]; // Tdd(Del[3], Del[1]) = Del[2] else return Id; // Id –   } 

3. Protocole d'interaction dans Google Docs

Voyons plus en détail le fonctionnement du protocole d'interaction dans Google Docs. Supposons que nous ayons un serveur, Petya et Vasya, et qu'ils aient une version synchronisée d'un document vide.

Chaque client se souvient des informations suivantes:

• Version (id, révision) de la dernière modification reçue du serveur.
• Toutes les modifications apportées localement mais non envoyées au serveur (en attente d'envoi)
• Toutes les modifications effectuées localement, envoyées au serveur, mais sans confirmation du serveur.
• L'état actuel du document que l'utilisateur voit.

Le serveur, à son tour, se souvient:

• Une liste de toutes les modifications reçues mais non traitées (en attente de traitement).
• Historique complet de toutes les modifications traitées (journal de révision).
• L'état du document au moment de la dernière modification traitée.

Donc, Petya commence par le mot «Bonjour» au début du document:


Le client a d'abord ajouté cette modification à la liste d'attente, puis l'a envoyée au serveur et a déplacé les modifications dans la liste envoyée.

Petya continue de taper et a déjà ajouté le mot «Habr». En même temps, Vasya a tapé "!" dans son document vide (il n'a pas encore reçu les modifications de Petina).


Petino $$$\ {Insert \ \ 'Habr', \ @ 5 \}$ a été ajouté à la liste en attente, mais n'a pas encore été envoyé, car nous n'envoyons pas plus d'une modification à la fois, et la précédente n'a pas encore été confirmée . Nous notons également que le serveur a enregistré les modifications de Petit dans son journal de révision. Ensuite, le serveur les envoie à Vasya et envoie une confirmation à Petya (que les premiers changements de Petina ont été traités avec succès)


Le client de Vasya reçoit les modifications de Petina du serveur et applique OT concernant son envoi en attente au serveur $$$\ {Insert \ \ '!', \ @ 0 \}$ . Le résultat est une modification de l'index d'insertion de 0 à 5. Nous notons également que les deux clients ont mis à jour le numéro de la dernière révision synchronisée avec le serveur à 1. Enfin, le client Petin supprime la modification correspondante de la liste des confirmations en attente du serveur.

Ensuite, Petya et Vasya envoient leurs modifications au serveur.


Le serveur reçoit les modifications de Petina avant (concernant l'ordre saisi) Vasinykh, il les traite donc d'abord et envoie une confirmation à Petya. Il les envoie également à Vasya, et son client les convertit concernant des changements qui n'ont pas encore été confirmés $$$\ {Insert \ \ '!', \ @ 5 \}$ .

Vient ensuite le point important. Le serveur commence à traiter les modifications de Vasya, celles qui, selon Vasya, ont la révision numéro 2. Mais le serveur a déjà validé les modifications au numéro 2, il applique donc la conversion à toutes les modifications dont le client de Vasya n'a pas encore connaissance (dans ce cas - $$$\ {Insert \ \ 'Habr', \ @ 5 \}$ ) et enregistre le résultat au numéro 3.


Comme nous pouvons le voir, l'indice du changement de Vasin a été augmenté de 5 pour tenir compte du texte de Petin.

Le processus est terminé pour Petya et Vasya doit recevoir une nouvelle modification du serveur et envoyer une confirmation.

4. Etherpad

Regardons une autre application similaire où OT est utilisé - le projet open source de l'éditeur en ligne avec la co-édition etherpad.org

Dans Etherpad, les fonctions de conversion sont légèrement différentes - les modifications sont envoyées au serveur sous la forme d'un ensemble de modifications (changeset) , défini comme

$$

$$(\ ell_1 \ rightarrow \ ell_2) [c_1, c_2, c_3, ...],$$

où

• $$$\ ell_1$ : longueur du document avant modification.
• $$$\ ell_2$ : longueur du document après édition.
• $$$c_1, c_2, c_3, ...$ - description du document après édition. Si $$$c_i$ Est un nombre (ou une plage de nombres), alors ce sont les index des caractères du document original qui resteront après l'édition (conservés), et si $$$c_i$ - un caractère (ou une chaîne), c'est l'insertion.
  
  Un exemple:
  
  
  1. $$$ inline $ `` "+ \ (0 \ rightarrow 6) [` `Hello"] = `` Hello "$ inline $
  2. $$$ inline $ `` Castor '' + (4 \ rightarrow 4) [`` Ha '', \ 2-3] = `` Habr '$ $ inline $
  
  

Comme vous l'avez déjà compris, le document final est formé comme une séquence de ces modifications appliquées pour un document vide.

Notez que nous ne pouvons pas simplement appliquer les modifications des autres participants (cela, en principe, est possible dans Google Docs), car la longueur totale des documents peut être différente.
Par exemple, si le document source était de longueur n et que nous avons deux modifications:

$$

$$A = (n \ rightarrow n_a) [\ cdots] \\ B = (n \ rightarrow n_b) [\ cdots],$$

alors $$$A (B)$ impossible, car $$$A$ nécessite une longueur de document $$$n$ et après $$$B$ il sera long $$$n_b$ .
Pour résoudre cette situation, Etherpad utilise un mécanisme de fusion : c'est une fonction dénotée par $$$m (A, B)$ , accepte deux modifications à l'entrée sur le même état du document (ci-après dénommé $$$X$ ) et apporte un nouveau changement.

Requis que

$$

$$m (A, B) = m (B, A)$$

Notez que pour un client avec des changements $$$A$ qui a reçu le changement $$$B$ cela n'a aucun sens de calculer $$$m (A, B)$ depuis $$$m (A, B)$ s'applique à $$$X$ et $$$A$ état actuel $$$A (X)$ . En fait, nous devons calculer $$$A ’$ et $$$B ’$ tel que

$$

$$B ’(A (X)) = A’ (B (X)) = m (A, B) (X)$$

Calcul de fonction $$$A ’$ et $$$B ’$ est appelé suivre et est défini comme suit:
$$$f (A, B) (A) = f (B, A) (B) = m (A, B) = m (B, A)$
Algorithme de construction $$$f (A, B)$ suivant:

• L'insert en A devient les indices en $$$f (A, B)$
• L'insert en B devient l'insert en $$$f (A, B)$
• Les indices correspondants dans A et B sont reportés sur $$$f (A, B)$

Un exemple:

$$$$ afficher $$ X = (0 \ rightarrow 8) [`` baseball ']] \\ A = (8 \ rightarrow 5) [0 - 1, `` si' ', 7] \ / \! \! / == `` basilic '\\ B = (8 \ rightarrow 5) [0, `` e ", 6,` `ow"] \ / \! \! / == `` ci-dessous "$$ afficher $$

Nous calculons:

$$

$$A '= f (B, A) = (5 \ rightarrow 6) [0, 1, `` si ", 3, 4] \\ B' = f (A, B) = (5 \ rightarrow 6) [ 0, «e», 2, 3, «ow»] \\ m (A, B) = m (B, A) = A (B ') = B (A') = (8 \ rightarrow 6) [ 0, `` esiow "] \\ $$

Calculer $$$m (A, B) (X)$ offert comme exercice.

Le protocole d'interaction est essentiellement le même que Google Docs, sauf si les calculs sont un peu plus compliqués.

5. Critique de l'ergothérapie

• La mise en œuvre de l'OT est une tâche très difficile en termes de programmation. Citant Wikipédia : Joseph Gentle, le développeur de la bibliothèque Share.JS et ancien ingénieur Google Wave a déclaré: «Malheureusement, la mise en œuvre de l'OT est nul. Il y a un million d'algorithmes avec différents compromis, principalement piégés dans des articles universitaires. Les algorithmes sont vraiment difficiles et longs à implémenter correctement. [...] Wave a mis 2 ans à écrire et si nous le réécrivions aujourd'hui, il faudrait presque autant de temps pour écrire une deuxième fois. »
  
  (Malheureusement, écrire OT est très difficile. Il y a un million d'algorithmes avec leurs avantages et leurs inconvénients, mais la plupart d'entre eux ne sont que des études universitaires. Les algorithmes sont en fait très complexes et nécessitent beaucoup de temps pour leur mise en œuvre correcte. [...] Nous avons passé 2 ans sur écrire Wave, et si nous devions l'écrire à nouveau aujourd'hui, cela nous prendrait le même temps)
  
• Vous devez absolument enregistrer toutes les modifications apportées au document
  

6. Références

• Contrôle d'accès simultané dans les systèmes de collecticiel
• Ce qui est différent dans les nouveaux Google Docs: travailler ensemble, même séparément
• Ce qui est différent dans le nouveau Google Docs: résolution des conflits
• Comprendre et appliquer la transformation opérationnelle
• Wikipédia: Transformation opérationnelle
• Fenêtre à latence élevée et à faible bande passante dans le système de collaboration Jupiter
• Ce qui est différent avec les nouveaux Google Docs: accélérer la collaboration
• Transformation opérationnelle dans les éditeurs de groupe en temps réel: problèmes, algorithmes et réalisations
• Manuel technique Etherpad et EasySync
• Google TechTalks: problèmes et expériences dans la conception de systèmes d'édition collaboratifs en temps réel
• Transformation opérationnelle Foire aux questions et réponses