af83

Synchroniser des données dans des webapps collaboratives

Wikipédia, Etherpad, Campfire et Koalab sont quelques exemples d'applications web collaboratives. Elles ont en commun qu'elles permettent à des utilisateurs de travailler ensemble sur un même jeu de données pour arriver à construire un résultat meilleur que si chaque utilisateur avait travaillé dans son coin. Cela demande donc aux développeurs de ce type d'applications de penser à la manière dont les modifications de données vont être prises en compte et renvoyées aux utilisateurs.

Il n'existe pas de stratégie universelle pour synchroniser les données et selon les contextes l'une ou l'autre des stratégies présentées ci-dessous sera la plus adaptée.

Le problème

Prenons l'exemple d'un éditeur de texte collaboratif. Si trois utilisateurs, Alice, Bob et Carole, travaillent sur un même document et font des modifications, on peut espérer que le résultat final respecte certaines propriétés. Il existe plusieurs modèles de consistance, dont un des plus connus est le modèle CCI. Celui-ci décrit 3 propriétés :

  • préservation de la Causalité : Si Alice supprime le texte saisi par Bob, alors dans le document de Carole, l'opération d'ajout du texte devra être traitée avant l'opération de suppression et le texte ne devra donc pas apparaître dans le document final.
  • Convergence : à la fin, le document affiché dans les éditeurs d'Alice, Bob et Carole devra être identique.
  • préservation de l'Intention : si Alice supprime le X dans fooXbar, le caractère X devra bien avoir disparu dans le document final.

Ces propriétés peuvent sembler triviales mais il est compliqué de les obtenir quand les différents utilisateurs peuvent faire des opérations en parallèle. Par exemple, pour transmettre une modification d'un utilisateur aux autres utilisateurs, on utilise souvent la position de la modification dans le document. Ainsi, quand Alice supprime le X dans fooXbar, Carole recevra l'ordre de supprimer le 42ème caractère du document. Mais si au même moment Bob ajoute un caractère à la 28ème position et que Carole reçoit cet ajout avant la suppression, le caractère X sera à la position 43 et c'est un o à la position 42 qui sera supprimé.

Les différentes stratégies de synchronisation

L'approche naïve

L'approche la plus simple consiste à dire que la dernière personne qui envoie une modification gagne. C'est, par exemple, cette approche qui est utilisée sur koalab. Si Alice et Bob déplacent tous les deux le même post-it au même moment, c'est celui qui lâchera le post-it en dernier qui imposera sa position.

L'avantage de cette solution est qu'elle est très simple à mettre en place. Par contre, si deux utilisateurs font une modification au même moment, le comportement peut être surprenant pour les utilisateurs et ne respectent pas les principes énoncés plus hauts. Cette solution convient donc bien quand les modifications peuvent être transmises très rapidement. C'est le cas pour koalab où on s'attend à ce que les utilisateurs soient connectés en haut débit et où les modifications sont très petites (chaque caractère saisi sur un post-it par exemple).

L'approche pessimiste

L'approche naïve était très optimiste : on partait du principe qu'il n'y aurait pas de soucis et, si jamais il y en avait un, celui-ci ne serait pas très grave. L'approche pessimiste prend le parti inverse : il faut empêcher tout risque d'édition simultanée pour être sûr de n'avoir aucun conflit.

Cette approche est utilisée dans l'espace de rédaction collaboratif de LinuxFr.org. Quand un utilisateur veut modifier un paragraphe, il va demander au serveur s'il peut passer en mode édition. Le serveur va poser un verrou sur le paragraphe en question. Ce verrou restera en place jusqu'à ce que l'utilisateur ait fini ses modifications et les renvoie au serveur. Ainsi, si un deuxième utilisateur veut modifier le même paragraphe quand le verrou est posé, le serveur lui refusera de passer en mode édition pour éviter un conflit.

Cette méthode fonctionne bien pour LinuxFr.org car il est très rare que deux utilisateurs veuillent éditer simultanément le même paragraphe. De plus, ces derniers préfèrent attendre un petit peu plutôt que d'introduire une coquille dans le texte en cours d'édition.

Néanmoins, cela conviendrait pour de fortes contraintes de temps réel. Cela nécessite également de prévoir certains mécanismes de gestion plus avancée des verrous (par exemple, si un utilisateur pose un verrou puis qu'il ferme le navigateur dans lequel il travaille sans avoir envoyé de modifications, il ne faut pas que le verrou bloque ad vitam aeternam le contenu en question).

Git et autres outils de gestion de versions décentralisés

L'idée est de faire travailler les utilisateurs sur leurs propres branches distantes. Puis, quand ils ont fini, ils peuvent pousser leurs modifications vers le serveur. S'il y a eu d'autres changements depuis, l'outil va d'abord essayer de régler automatiquement ces différences. Et s'il n'y arrive, on dit alors qu'il y a un conflit. L'utilisateur va alors devoir régler lui-même ce conflit sur sa branche avant que ses modifications ne soient prises en compte.

Cette utilisation est plus complexe pour l'utilisateur mais elle est très puissante. En particulier, elle convient bien pour des utilisateurs faisant de nombreuses modifications en mode offline.

Un exemple d'utilisation : ChocolateJS.

Operational Transformation (OT)

Et voici l'artillerie lourde : Operational Transformation. L'idée de base consiste à réécrire les modifications pour prendre en compte les changements des autres utilisateurs :

Basic OT Source : Wikipédia

Sur l'exemple ci-dessus, l'utilisateur de gauche ajoute la lettre x au début du texte abc puis reçoit la modification de l'utilisateur de droite. Comme cette modification est intervenue sur une version du texte qui ne contenait pas encore l'ajout, il va commencer par modifier la position de la suppression pour tenir compte du caractère supplémentaire avant de l'appliquer.

OT permet ainsi de respecter les contraintes énoncés plus haut pour de la modification en temps réel. Le problème est qu'OT est très compliqué. Nous n'avons qu'un cas particulier parmi une foultitude. Il faut compter plusieurs mois, voir plusieurs années, pour implémenter solidement OT. Aussi, il est fortement recommandé de s'appuyer sur des solutions existantes même si elles sont encore loin d'être parfaites. En Open-Source, les plus intéressantes sont :

  • ShareJS est probablement l'implémentation de référence (attention, la documentation mélange les versions 0.6 et 0.7 dont les installations sont pourtant très différentes, et l'utilisation de nodejs n'aide pas à stabiliser le tout)
  • Substance est une plateforme ouverte pour la création collaborative de documents numériques, dont une des briques est justement de l'OT. Malheureusement, Substance est en pleine réécriture et n'est pas encore utilisable en l'état. À suivre donc…
  • Google a abandonné Google Wave mais a publié son code sous licence libre et la fondation Apache l'a repris sous le nom d'Apache Wave. Si l'échec de Google Wave ne vous fait pas peur, la partie OT d'Apache Wave tient la route (même si pour l'UI c'est une toute autre histoire).

WithOut Operational Transformation (WOOT)

En réaction à la complexité d'OT, des chercheurs ont proposé un algorithme nommé WOOT. Celui-ci est également adapté pour de l'édition en temps-réel mais avec une complexité bien moindre. Par contre, il se limite à de l'édition de texte et demande quelques ajustements pour des documents avec une longue durée de vie.

En effet, il fonctionne en gardant chaque caractère, y compris ceux qui ont été supprimés (ils sont juste rendus invisibles). Cela permet ainsi d'envoyer au serveur plus d'informations sur les ordres partiels à respecter, ce qui permet ainsi de simplifier les algorithmes coté serveur.

Petit mot pour conclure

Comme nous l'avons vu, il n'y a pas de solution miracle dans ce domaine. On peut espérer que les solutions à base d'OT deviennent plus mûres mais, pour le moment, elles restent très complexes à mettre en œuvre. Il convient donc de bien comprendre le domaine dans lequel on veut opérer pour choisir la stratégie de synchronisation qui conviendra le mieux.

blog comments powered by Disqus