Mensonges sur l’édition collaborative, 1re partie : algorithmes pour l’édition hors ligne

 (moment.dev)
2 points par GN⁺ 2024-12-08 | 1 commentaires | Partager sur WhatsApp
  • D’après l’évaluation menée par Moment pour son éditeur de texte principal, les algorithmes de la famille CRDT et OT peuvent produire, lors de conflits directs hors ligne, des résultats de fusion que les utilisateurs percevraient comme une corruption de données
  • Même dans un cas simple où Alice supprime toute une phrase et Bob remplace Color par Colour, le document final peut ne contenir que la lettre u, soit un résultat non voulu par un humain
  • Dans les cas d’usage de Moment, environ 20 à 30 % des conflits directs testés ont donné des résultats inacceptables, et leur fréquence comme les réactions négatives les rendent difficiles à défendre comme expérience produit
  • Yjs, ShareJS et Peritext mettent en avant l’édition hors ligne, la collaboration avec de longs délais ou la fusion automatique de copies indépendantes, mais les algorithmes ne peuvent pas connaître l’intention ni l’ordre voulu par les utilisateurs et s’appuient donc sur des heuristiques
  • L’édition collaborative hors ligne relève moins d’un pur problème d’algorithme que d’un problème UI/UX : il faut une expérience de fusion lisible et jugeable par l’humain, à la manière de l’interface de fusion de git ou de la collaborative history d’Ink & Switch

Les limites révélées par l’évaluation de l’édition collaborative chez Moment

  • Début 2024, Moment a commencé à étudier un système d’édition collaborative pour son éditeur de texte principal
  • Plusieurs algorithmes affirment résoudre non seulement l’édition simultanée en ligne, mais aussi les cas hors ligne, où un utilisateur modifie un document hors ligne pendant une durée illimitée avant de revenir en ligne et de fusionner automatiquement ses changements
  • Après avoir lu les articles et présentations, l’équipe s’attendait d’abord à ce que la communauté de l’édition collaborative soit parvenue à la « bonne réponse » pour l’ensemble du problème
  • Lors de l’évaluation, les algorithmes de type CRDT et OT ont résolu des conflits d’édition directs de façon peu intuitive, et les utilisateurs ont perçu ces résultats comme une corruption de données
  • Comme l’édition hors ligne augmente fortement la probabilité de conflits directs, ces seuls algorithmes ne suffisaient pas pour créer l’expérience d’édition hors ligne voulue par Moment

Un cas simple de conflit entre suppression et correction orthographique

  • Alice et Bob modifient tous deux le même document en étant hors ligne
  • Le document contient le texte The Color of Pomegranates
  • Bob change l’orthographe de Color en anglais britannique, Colour, tandis qu’Alice supprime tout le texte
  • Quand les deux reviennent plus tard en ligne, les deux modifications entrent en conflit, et le système doit les concilier sans savoir laquelle est venue en premier
  • Dans ce cas, Alice et Bob se retrouvent finalement avec un document ne contenant que la lettre u
    • Ce n’est ni une phrase valide, ni un mot valide
    • Les utilisateurs interprètent ce type de résultat comme une corruption de leurs données par Moment

Les résultats étranges des conflits directs ne sont pas rares

  • Ce conflit est un conflit d’édition trivial et direct, mais il se situe dans le périmètre que des algorithmes populaires d’édition collaborative sont censés prendre en charge
  • Le résultat réel était un document qu’aucun humain n’aurait écrit de lui-même, et il a été interprété comme une corruption de données par le produit Moment
  • Cela varie selon les cas d’usage, mais parmi les conflits directs testés par Moment, environ 20 à 30 % ont produit des résultats difficiles à accepter dans un scénario d’édition hors ligne
  • En combinant les retours négatifs et leur fréquence, l’équipe a estimé qu’il serait difficile d’expliquer et de défendre ces résultats auprès des utilisateurs

Le support de l’édition hors ligne revendiqué par les outils

  • Au départ, face à ces résultats, l’équipe a pensé avoir mal compris ce que ces outils promettaient
  • Pourtant, la description de chaque projet peut se lire comme incluant ce scénario dans son périmètre de support
    • Yjs indique explicitement dans son README prendre en charge l’offline editing
    • ShareJS explique permettre la collaboration avec n’importe quelle latence, de zéro jusqu’à l’équivalent de longues vacances
    • Peritext explique que les utilisateurs peuvent modifier des copies indépendantes d’un document, puis les fusionner automatiquement d’une manière qui préserve autant que possible leur intention
  • Moment cherche toujours une solution à ce problème, mais estime difficile de concilier la fréquence et la nature des erreurs observées avec ces affirmations

Les limites fondamentales des algorithmes sans arbitrage

  • À mesure que l’évaluation avançait, l’équipe a conclu que ces algorithmes ne produisaient pas le comportement recherché par Moment
  • La question restante était de savoir s’il s’agissait d’un problème corrigeable par des contributions, ou d’une limite fondamentale de l’algorithme
  • Trois raisons poussent à y voir un problème fondamental
    • L’algorithme ne connaît pas les intentions d’Alice et Bob, et ne peut pas leur demander par e-mail ce qu’ils voulaient ni soumettre le cas à une revue comme dans l’interface de Pull Request de GitHub
    • Il doit recevoir la proposition de suppression complète d’Alice et la proposition de correction orthographique de Bob, puis décider du résultat au moyen d’heuristiques
    • Il fonctionne au niveau des caractères et n’offre que des garanties très faibles sur la sortie
    • Alice et Bob auraient pu prendre des décisions d’édition différentes s’ils avaient su ce que l’autre faisait
  • Ces algorithmes sont aussi liés au problème de l’impossibilité de respecter un ordre causal

L’édition hors ligne est plutôt un problème UI/UX

  • Moment espérait qu’en implémentant un algorithme sophistiqué, elle pourrait obtenir en bonus une véritable prise en charge de l’édition hors ligne, mais l’évaluation a rendu cette lecture difficile à soutenir
  • Il était légitime que les utilisateurs voient les résultats de l’algorithme comme une corruption de données ; les résultats étranges font partie de l’algorithme lui-même et se produisent assez souvent pour devenir un vrai problème
  • Une autre interprétation est qu’il faut consacrer des ressources UI/UX importantes à l’édition collaborative
  • L’algorithme ne peut pas résoudre entièrement le problème, mais il peut constituer une partie de la solution

Interface de fusion git et pistes de recherche

  • Il existe déjà une interface de fusion de documents largement adoptée : git
  • La question de recherche consiste plutôt à savoir jusqu’où rendre cette expérience plus accessible, plus compréhensible et plus automatisable
  • Vers 2009, les discussions portaient beaucoup sur les algorithmes utilisés par git pour fusionner automatiquement les changements
    • git a adopté le Myers O(ND) diff algorithm, un algorithme principalement utilisé par les biologistes pour l’analyse de séquences de type BLAST
    • Bram Cohen, jugeant les résultats de diff peu intuitifs, a créé le patience diff algorithm, qui a été adopté par bzr, un concurrent de git aujourd’hui abandonné
  • À l’époque, la discussion se concentrait sur la production de diffs lisibles par les humains ; aujourd’hui, elle porte davantage sur la capacité d’un algorithme à obtenir ce résultat sans intervention humaine
  • Des recherches comme la collaborative history d’Ink & Switch abordent l’édition collaborative comme un problème UI/UX

À lire aussi

1 commentaires

 
GN⁺ 2024-12-08
Commentaires sur Hacker News

  • Je suis l’auteur d’Eg-walker et de ShareJS. Le texte peut sembler prendre un ton opposé à mon travail, mais en réalité je suis entièrement d’accord et je dis la même chose sur HN depuis des années.
    Les outils actuels de collaboration en temps réel fonctionnent bien quand tout le monde édite ensemble en ligne, mais si des utilisateurs modifient hors ligne ou sur des branches de longue durée, il faut des options d’indication de conflit et de relecture manuelle au moment de la fusion. C’est encore plus vrai pour le code.
    Heureusement, des algorithmes comme egwalker conservent la trace de toutes les modifications caractère par caractère de tous les utilisateurs ainsi que de l’ordre causal, c’est-à-dire un ordre des changements comparable à un Git DAG, et disposent donc de bien plus d’informations que Git. On devrait donc pouvoir créer un CRDT capable de détecter et d’indiquer l’étendue des conflits lors de la fusion de branches, puis laisser l’utilisateur les résoudre manuellement.
    Cela semble être un problème intéressant du point de vue algorithmique, mais tout à fait soluble, et étrangement presque personne ne semble encore s’y être attaqué dans l’édition de texte. Si quelqu’un veut apporter une contribution originale et utile dans ce domaine, c’est une pièce importante manquante de l’écosystème CRDT, et j’aimerais que quelqu’un s’en empare.
    [1] Plus bas dans ce commentaire : https://news.ycombinator.com/item?id=19889174

    • Dans ce cas, on finit en fait par intégrer les conflits dans une partie du modèle de données. C’est une manière amusante d’obtenir le C de CRDT, c’est-à-dire « conflict-free », mais c’est tout à fait légitime, et peut-être même la seule façon de faire.
      Le prochain défi amusant, c’est quand des conflits apparaissent autour de la résolution des conflits elle-même.
    • Joseph, je ne voulais pas dire que ton travail était mauvais. L’intention était plutôt d’aider les praticiens à comprendre à quoi ils peuvent s’attendre, et à motiver des problèmes comme celui mentionné à la fin.
      Évaluer ce genre de systèmes est déjà en soi un problème technique suffisamment difficile, donc je pense que beaucoup d’équipes vont souffrir. Elles méritent donc des conseils pratiques, et nous avons le sentiment que nous aurions aimé le savoir plus tôt.
    • Je suis sceptique sur la possibilité d’une solution algorithmique, mais cela semble gérable dans la couche UX au-dessus. Par exemple, le client pourrait détecter les conflits à partir de l’historique des modifications, puis afficher une boîte de dialogue de résolution de conflits dont le résultat devient une nouvelle modification.
      La partie difficile consiste à indiquer qu’un conflit a été résolu. Cela pourrait être aussi simple que d’ajouter un champ au CRDT, mais dans ce cas je ne sais pas s’il faudrait encore considérer cela comme une solution algorithmique.
      [1] https://josephg.com/blog/crdts-go-brrr/
    • L’article traite de cas de splice concurrents qui se chevauchent, un cas limite étrange bien connu.
      Pour l’édition de code, on s’attend en plus à ce que le résultat de la fusion soit un programme valide, ce qui ouvre un terrier de lapin bien plus profond. Il y avait chez JetBrains un projet qui essayait de résoudre cela avec une fusion basée sur l’AST, mais j’ai entendu dire qu’après être allé beaucoup plus loin, ils avaient conclu que cela n’en valait pas la peine.
    • L’édition « hors ligne » est, à mon avis, un problème humain, donc l’automatisation ne peut pas le résoudre. Les humains finissent toujours par trouver un moyen de casser ou de contourner l’automatisation ou le système.
      Dans les documents écrits par des humains, la seule forme d’« édition hors ligne » que j’autorise est l’ajout de commentaires. Pas d’édition, et pas de fusion automatique.
      Pour l’« édition hors ligne » du code source, qui se prête à l’automatisation, on utilise Git, et Git ne prétend pas résoudre les fusions : il montre seulement les révisions. La fusion est un travail supervisé par des humains ou effectué par une automatisation spécialisée qui propose sa meilleure estimation, et sa réussite doit toujours être vérifiée par revue et par tests.

  • Les algorithmes de fusion mécanique peuvent être plus ou moins performants selon le type de conflit, mais au final aucun CRDT ne peut déterminer si le texte fusionné correspond à ce que les utilisateurs voulaient réellement dire.
    L’article Upwelling détaille davantage une distinction qu’il appelle, dans l’écriture, les conflits sémantiques et les conflits grammaticaux : https://inkandswitch.com/upwelling/
    J’ai l’impression qu’une collaboration sérieuse finit aussi par devenir un problème de relecture de documents. C’est particulièrement vrai en journalisme ou dans l’édition scientifique, alors que pour des comptes rendus de réunion on peut souvent l’ignorer.

    • Peter, merci pour ce bon mot. J’aurais aimé qu’on voie que l’article se termine en grande partie en cherchant à motiver directement le travail d’Ink & Switch que tu mentionnes toi-même à la fin.
      Je voulais aussi faire un lien vers Upwelling, mais je ne me souvenais plus du nom et, faute de temps avant la deadline, je l’ai remplacé par un autre lien.

  • Un autre côté sombre des implémentations de CRDT, c’est la charge d’infrastructure. J’ai déjà écrit en profondeur là-dessus autrefois[0], et j’ai été heureux de découvrir que Supabase était arrivé à la même conclusion que mes résultats empiriques dans son billet d’il y a quelques années sur une extension CRDT pour Postgres[1].
    Si vous allez utiliser des CRDT, il vaut mieux prendre quelque chose comme Redis, ou bien, même si l’usage mémoire fait mal rien que d’y penser, une base sur MyRocks[2] ou RocksDB/LevelDB. Quoi que vous fassiez, il ne faut pas mettre un SGBDR, surtout Postgres, comme backend.
    [0]: https://news.ycombinator.com/item?id=40834759
    [1]: https://supabase.com/blog/postgres-crdt
    [2]: http://myrocks.io

    • Je suis justement en train de construire ça moi-même avec Yjs + Postgres, donc ça a l’air vraiment utile. Ça pourrait peut-être m’éviter une grosse catastrophe un jour.

  • Cette observation de l’article est juste. Les CRDT sont un excellent modèle formel pour les structures de données distribuées, mais l’idée qu’ils doivent résoudre automatiquement tous les conflits — l’idée même de types de données répliqués sans conflit — m’a toujours mis mal à l’aise.
    Comme le montre l’article, cela me semble être une tentative sans espoir. Ce qu’il faut, c’est une représentation structurelle correcte qui permette de partager les conflits et de les résoudre de manière collaborative, en redonnant le contrôle aux utilisateurs et en soutenant le processus de résolution. L’un de mes articles préférés, “Turning Conflicts into Collaboration” [1], traite cette idée de façon convaincante.
    Dans le cadre de mes travaux de doctorat en cours, j’ai développé “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2], un modèle formel de représentation structurelle des conflits fondé sur la théorie des treillis. Par coïncidence, c’est aussi un CRDT, mais il n’essaie pas de résoudre automatiquement les conflits et les représente à l’intérieur du document collaboratif. En adoptant une approche mathématique, j’ai pu aboutir à un modèle conceptuel simple qui garantit des propriétés fortes telles que l’exhaustivité, la minimalité et l’unicité de la fusion, même après des conflits antérieurs fusionnés de manière répétée, et le calcul de fusion est lui aussi très simple.
    [1] https://doi.org/10.1007/s10606-012-9172-4
    [2] https://doi.org/10.14279/tuj.eceasst.82.1226

    • Quand j’ai découvert les CRDT, le sigle signifiait commutative replicated data types, c’est-à-dire types de données répliqués commutatifs. C’était aussi le cas dans les articles de Shapiro et al., et même si c’est plus difficile à prononcer, je préfère cette appellation.
      Le conflit est une notion complexe, et “conflict-free”, bien que techniquement correct pour décrire le résultat, peut prêter à confusion, comme on le voit dans cet article et ci-dessus.
      La commutativité est la propriété selon laquelle Bob peut appliquer les modifications dans l’ordre [Bob, Alice] et Alice dans l’ordre [Alice, Bob], tout en aboutissant tous deux au même document. Cela ne signifie pas qu’au niveau d’abstraction supérieur, le document soit “sans conflit” dans un sens sémantiquement pertinent.

  • Je pense qu’en général, l’idée selon laquelle plusieurs acteurs différents peuvent disposer simultanément d’une autorité sur le même fragment de données sans coordination en temps réel est insoluble. C’est une leçon déjà apprise en systèmes distribués, et cela apparaît clairement dans cet article quand on pense à l’édition distribuée de documents.
    Le même principe semble s’appliquer à la double commande dans un cockpit d’avion, à l’éducation des enfants, et à d’autres exemples très différents qui viennent à l’esprit.

    • On peut le résoudre, mais il faut des informations de contexte plus complexes que beaucoup de gens trouveraient fastidieuses à saisir. Par exemple, des informations du type : « le mot que je viens de modifier n’a de sens que s’il fait partie de cette phrase entière, et cette phrase entière n’est pas forcément indispensable au paragraphe dans son ensemble ».
      Et il est même assez drôle d’appeler ça “résoudre”, parce qu’à l’heure actuelle, une grande partie de la planète semble penser que la sortie chaotique d’un LLM peut quasiment déterminer le résultat final du calcul.
    • Il s’agit du théorème CAP de Brewer appliqué au stockage de données distribuées. On ne peut en avoir que deux sur trois : cohérence, disponibilité et tolérance au partitionnement.

  • Les CRDT et OT, algorithmes couramment utilisés pour l’édition de texte collaborative, imposent des contraintes algébriques strictes sur ce que font les opérations d’édition et sur la façon dont elles interagissent.
    Donc même si le serveur est suffisamment intelligent pour traiter l’exemple “Colour” d’une manière raisonnable du point de vue UX, concevoir le CRDT/OT correspondant pour une édition optimiste côté client est très difficile.
    On peut contourner cela en n’utilisant pas de CRDT/OT. Par exemple, le serveur peut traiter les opérations dans l’ordre de réception et appliquer la logique UX souhaitée, tandis que le client utilise une stratégie de rebase/prédiction pour permettre l’édition optimiste par-dessus. Voir : https://doc.replicache.dev/concepts/how-it-works
    L’appliquer à l’édition de texte pose aussi des difficultés, mais elles sont distinctes des problèmes CRDT/OT discutés ici.

    • Ce commentaire est très sous-estimé, et je suis entièrement d’accord.

  • Je pense que cela vient du fait que les notions mathématique, causale et entropique de conflit sont mélangées au conflit sémantique. J’ai moi-même déjà commis l’erreur inverse par le passé, et quelqu’un m’a alors fermement fait remarquer que je ne savais pas de quoi je parlais.
    Dès qu’on commence à considérer des arbres, cela devient bien plus sale. Par exemple, yJS fonctionne sur des documents JSON. Si l’interface n’affiche que les niveaux superficiels et laisse les niveaux profonds repliés, l’utilisateur peut ne jamais voir une modification supprimée.
    La catégorie de CRDT qui préserve les conflits — si je me souviens bien, celle où un registre peut contenir plusieurs valeurs — me semble la plus prometteuse. Il faut présenter de tels conflits à l’utilisateur, et on pourrait même les montrer de manière entièrement visuelle. Permettre de parcourir l’historique me semble aussi une alternative pratique pour aider l’utilisateur à comprendre comment quelque chose d’étrange s’est produit, ou comment sa propre modification a disparu.

    • “Git” serait un joli nom pour ce type de CRDT.
    • À cet égard, Loro semble prometteur. Il traite activement ce problème.

  • Je me souviens que Torvalds lui-même était assez pessimiste sur ce qu’on pouvait accomplir avec la fusion automatique. Et ce jugement était juste
    Il disait que Git rejetait l’idée qu’un système de contrôle de version puisse, ou doive, « résoudre le problème des fusions » grâce à un algorithme suffisamment intelligent qui ferait automatiquement ce qu’il faut
    Je suis d’accord pour dire que l’édition hors ligne est un problème d’UI/UX. La cause plus profonde, c’est l’habitude qu’a l’industrie informatique de répéter de vieilles solutions, ainsi que la croyance selon laquelle « comme, en général, un sac de 5 livres est plus facile à manipuler qu’un sac de 10 livres, il faut mettre 10 livres de marchandises dans un seul sac de 5 livres »
    L’image de base de l’« éditeur de texte », c’est un textarea de Mosaic, MacWrite, ou quelque part entre les deux, donc on essaie généralement d’y greffer la fusion avec le minimum de changements. Sous la forme d’une entrée de menu ou de quelques options dans une petite boîte de dialogue. Même quand il existe une prise en charge GUI de la fusion, enfouie dans les menus, cela reste soit de l’horreur diff/merge pour programmeurs, soit une vue précaire à base de texte barré, comme piloter un bateau dans le brouillard
    Mais dans un éditeur de texte avec collaboration hors ligne, la fusion partiellement manuelle est au cœur du processus, et elle devrait aussi être au cœur de la conception de l’éditeur. Malheureusement, MacWrite est un optimum local dont il est difficile de sortir

    • Cela laisse la question de l’alternative
      Par exemple, quand quelqu’un parle d’« imitation par cargo cult » et de « vieilles solutions », la phrase suivante est souvent « n’éditez pas le code comme du texte, éditez-le comme un arbre syntaxique ». Mais le problème reste le même. Il suffit de remplacer « caractère » par « phrase »
      Si Bob a ajouté une ligne dans la branche else d’une instruction if et qu’Alice a supprimé toute l’instruction, branche else comprise, que doit faire un système intelligent ?
    • Je crois que j’ai formulé de façon confuse ce que je voulais dire sur la fusion automatique. Quand plusieurs commits modifient un même fichier, Git essaie bien de les fusionner ensemble, mais je voulais dire que les conflits directs doivent impérativement être signalés
      Globalement, il semble y avoir un accord sur le fait que cette approche est la bonne

  • Je suis preneur de questions ou de retours. Je vais être en réunion pendant une heure ou deux, mais j’aime bien parler de ce genre de sujet. Vous pouvez écrire ici ou par e-mail, comme vous préférez : alex@moment.dev

    • Si on conserve la prise en charge hors ligne, des cas plus intéressants finiront par apparaître. Par exemple : « J’ai travaillé là-dessus dans l’avion sans wifi, puis la direction prise ne me plaisait pas, alors j’ai refermé mon ordinateur portable pour faire une sieste. Ensuite, j’ai travaillé sur le document pendant quelques jours depuis mon ordinateur de bureau. Le week-end, j’ai rouvert le document sur le portable, et toutes les modifications faites dans l’avion avaient été intégrées au document et tout était en bazar. Aidez-moi, je n’essayais pas de fusionner quoi que ce soit ! »
      Git n’injecte pas automatiquement des modifications locales sans consentement explicite. bzr n’aurait sans doute même pas rêvé de faire ça. Mais des outils comme Google Docs le font volontiers
      Les progrès réalisés jusqu’ici sont chouettes, et j’espère que le programme d’accès anticipé marchera bien
    • Pourquoi ne pas simplement adopter la fusion de type patch/diff ? Si l’on présente l’édition de texte collaborative hors ligne comme un simple problème d’optimisation UX, alors c’est un problème résolu depuis des décennies

  • J’ai implémenté differential sync(https://neil.fraser.name/writing/sync/). Je ne comprenais pas les autres approches, et pour l’application grugnotes.com, celle-ci me paraissait la plus simple
    L’application est assez bricolée et n’est pas totalement en temps réel, mais, dans l’exemple, la fusion est correctement traitée quel que soit celui qui se reconnecte en premier. Si la suppression revient en ligne en premier, la version colour est écartée et n’est même pas enregistrée dans l’historique des modifications
    Il y aura sûrement d’autres problèmes, et je ne sais pas non plus ce que cela donnerait avec plus de deux utilisateurs, mais pour mon usage cela me convient