Édition collaborative de texte : implémenter sans CRDT ni OT

• Présentation d'une nouvelle approche pour résoudre le problème de l'édition collaborative de texte, réalisable sans algorithmes complexes
• Elle évite la complexité et les contraintes des approches CRDT et OT existantes, en utilisant une méthode simple d'insertion fondée sur des ID
• Avec cette approche, le serveur traite directement des instructions précisant "quoi insérer et où", ce qui offre une grande flexibilité
• Pour les mises à jour locales optimistes, elle s'appuie sur une stratégie de réconciliation côté serveur afin de résoudre les problèmes de synchronisation d'état
• À la fois évolutive et facile à comprendre, cette méthode propose une alternative directement implémentable pour développer des applications collaboratives existantes

---

Collaborative Text Editing without CRDTs or OT

Position du problème

• L'édition collaborative de texte est une fonctionnalité très difficile à mettre en œuvre, en particulier à cause du problème de décalage des index de texte (index rebasing) lors des modifications simultanées
• Les approches classiques, CRDT (types de données répliqués sans conflit) et OT (transformation opérationnelle), reposent chacune sur des modèles mathématiques complexes
  • CRDT : chaque caractère est suivi par un ID et ordonné selon une structure en arbre
  • OT : les index sont réajustés dynamiquement pour refléter les entrées des autres utilisateurs
• Dans les deux cas, la dépendance aux bibliothèques est forte et la personnalisation par les développeurs reste difficile

Une nouvelle approche

Idée clé

• Chaque caractère reçoit un ID unique (UUID), et le client envoie au serveur une instruction du type « insérer tel caractère après tel ID »
• Exemple : "insert ' the' after f1bdb70a" → f1bdb70a est l'ID du caractère cible après lequel insérer
• Le serveur interprète alors cette instruction telle quelle pour effectuer l'insertion, ce qui permet d'éviter les conflits

Gestion de la suppression

• Lorsqu'un caractère est supprimé, son ID reste dans la liste interne et est marqué via un drapeau isDeleted
• Il n'apparaît plus dans le texte visible par l'utilisateur, mais la référence est conservée pour permettre des opérations ultérieures

Traitement côté client et mises à jour optimistes

• L'utilisateur doit voir le résultat immédiatement après sa saisie ; la modification est donc appliquée localement avant la réponse du serveur (mise à jour optimiste)
• Une stratégie de réconciliation côté serveur est utilisée pour :
  1. annuler toutes les opérations locales non confirmées
  2. appliquer les opérations du serveur
  3. réappliquer ensuite les opérations locales afin de retrouver un état final synchronisé

Différences avec les approches existantes

• Les CRDT embarquent un algorithme d'ordonnancement automatique des ID, alors qu'ici seul l'emplacement d'insertion explicite est transmis au serveur
• Le résultat est donc plus simple et offre un comportement plus clair et plus prévisible

Gestion des insertions simultanées

• Exemple : dans « My name is », deux utilisateurs insèrent en même temps « Charlie » et « Dave » au même endroit
  • Selon l'ordre de réception par le serveur, on obtient « My name is Dave Charlie »
• Ce comportement est considéré comme naturel et évite le phénomène d'entrelacement caractère par caractère (interleaving) observé dans certaines approches CRDT

Prise en charge d'opérations flexibles

• Au-delà des insertions/suppressions de base, cette approche peut gérer divers types d'opérations :
  • insert-before
  • insertion sous condition (ajouter « u » seulement si « color » existe)
  • réajustement de position lors d'un drag & drop, etc.
• Cette flexibilité permet de ne pas être enfermé dans des propriétés mathématiques prédéfinies

Prise en charge du texte enrichi

• Les plages peuvent être définies à partir d'ID pour appliquer de la mise en forme (« gras de l'ID X à l'ID Y », etc.)
• En l'intégrant à un éditeur comme ProseMirror, il devient possible de résoudre les conflits de manière simple
• La structure de base reste inchangée tout en permettant d'ajouter des fonctionnalités de texte enrichi

Version décentralisée (Decentralized)

• Même sans serveur central, il est possible d'utiliser la même approche en ordonnant les opérations via des horodatages de Lamport
• Dans ce cas, on obtient des résultats similaires à ceux de CRDT comme RGA, Peritext, Fugue
• Il devient ainsi possible d'atteindre un niveau de cohérence comparable à celui des CRDT, sans arbre ni preuve mathématique

Bibliothèque d'appui : Articulated

• Une bibliothèque destinée à manipuler efficacement des structures de type Array<{ id, isDeleted }>
• À la place des UUID, elle utilise une structure { bunchId, counter } pour optimiser la mémoire
• Basée sur une structure B+Tree, elle permet une recherche rapide des ID et des insertions efficaces
• Sa structure de données persistante s'accorde bien avec la réconciliation côté serveur

Conclusion

• Par rapport à CRDT/OT, cette approche est plus facile à comprendre et directement implémentable
• Elle permet d'appliquer librement diverses fonctions d'édition, permissions, contraintes et formats, ce qui la rend bien adaptée à la mise en œuvre réaliste d'éditeurs collaboratifs
• La bibliothèque Articulated est proposée comme un outil permettant de rendre cette approche praticable

[GN⁺]

Discussion sur Hacker News

• Cet algorithme a l’air assez élégant. Il explique une approche où chaque caractère reçoit un identifiant globalement unique (par ex. un UUID) afin de pouvoir être référencé de manière cohérente à tout moment ; le client indique au serveur qu’il insère un caractère après un ID donné, puis le serveur effectue l’insertion à cet emplacement ; les suppressions sont seulement masquées à l’écran mais conservées en interne pour servir de référence de position ; on peut imaginer que cette approche serait utile non seulement pour l’édition de texte, mais aussi dans d’autres domaines comme la synchronisation d’un monde de jeu

  • Cela ressemble essentiellement à un CRDT simplifié, avec un mécanisme de départage et l’usage d’un serveur central similaires à l’architecture de l’époque de Google Wave
  • Quelqu’un se demande si ce qui est décrit n’est pas justement un CRDT
  • Réaction disant qu’il n’y a en réalité rien de très nouveau : utiliser un processus central pour sérialiser un système distribué est une approche traditionnelle, et des problèmes comme les partitions réseau (CAP, etc.) ou le point unique de défaillance subsistent ; avec en plus la question de savoir si l’article parle des performances
  • Blague souhaitant bonne chance avec les opérations de sélection/copier/coller massives comme ctrl+a, ctrl+x, ctrl+v

• Un point de vue partagé est que la différence avec les CRDT réside dans le fait que le serveur central assure la synchronisation, notamment l’ordonnancement, sans qu’il soit nécessaire d’imposer à l’avance un ordre dans la structure de données elle-même ; comme il n’y a que de la communication client-serveur, le serveur peut traiter toutes les opérations locales du client avant d’envoyer les mises à jour distantes

• Certains trouvent surprenant qu’il n’y ait rien sur d’autres structures de données comme dict/map ou des tableaux de types arbitraires ; dans les applications réelles, on a souvent davantage besoin de structures de données collaboratives variées que d’édition collaborative de texte pure ; il existe des exemples intéressants autour de la validation des données, du chargement partiel ou d’opérations de plus haut niveau, et si des outils comme Yjs ne proposent pas cela, c’est probablement moins à cause des CRDT eux-mêmes que parce que ces fonctionnalités sont difficiles à implémenter de toute façon

  • Profond accord sur l’importance de plusieurs structures de données : lorsqu’on crée un tableau d’objets « atomiques », si modifier les propriétés d’un objet est impossible, on peut simplement remplacer les chaînes par des types ; les modifications internes d’un objet ne sont qu’un problème un peu plus complexe de parcours/stockage d’arbre. Il est aussi espéré que les utilisateurs de bibliothèques utilitaires puissent brancher leur propre logique de « modèle sémantique » via des hooks afin d’éviter des états invalides, par exemple un todo avec isDone: true et state: inProgress, dans le même esprit que le formatage de texte enrichi mentionné dans l’article lié

  • Les CRDT fusionnent les conflits en choisissant un côté de manière cohérente, mais le problème est que cela peut produire une perte de données ou des données invalides ; c’est comme si, lors d’un conflit de fusion git, on résolvait toujours en choisissant un seul côté, ce qui aboutirait le plus souvent à un résultat incorrect ou à des erreurs de compilation. L’automatisation seule ne suffit pas toujours à préserver correctement l’authenticité et le sens des données, et ce serait selon certains une des raisons pour lesquelles les CRDT ne sont pas encore largement adoptés

• Quelqu’un dit avoir lu avec intérêt ce billet expliquant cette approche ; il l’utilise lui-même depuis longtemps et trouve étonnant qu’elle soit si peu mentionnée dans le monde académique ; dans son cas, il l’a implémentée comme un CRDT dans un environnement décentralisé, de façon à conserver des propriétés comme l’associativité, l’immuabilité et la commutativité

  • Question sur les bénéfices concrets obtenus si cela a été développé comme alternative aux CRDT

• Tentative de résumer le message principal de l’article : les CRDT/OT complexes ne sont-ils vraiment nécessaires que lorsqu’il n’y a pas de serveur central ?

  • Réponse disant que même sans serveur central, on peut éviter la complexité des CRDT/OT si l’on dispose d’un moyen distribué pour se mettre d’accord sur l’ordre global des opérations et l’appliquer ; un article lié est mentionné. Cela reste bien une forme de CRDT (au sens généralisé), mais implémenter undo/replay n’est pas trivial, et cela peut constituer une alternative quand les architectures CRDT/OT traditionnelles paraissent encore plus complexes

  • Mention que l’OT (Operational Transformation) nécessite un serveur central

• Essentiellement, cela relève aussi des CRDT, à ceci près que l’ordre des opérations appliquées au document est décidé par un serveur central ; Google Docs et Zoho Writer utilisent eux aussi une approche OT + serveur central ; l’idée proposée a un style CRDT, mais il est admis qu’elle est en pratique plus pragmatique pour des services de fait basés sur un serveur central

• Pour certains, la principale différence avec des CRDT comme Automerge tient au mode de coordination par le serveur : Automerge trie les insertions concurrentes selon un ordre défini par les numéros de séquence et les identifiants d’agent, alors que l’approche ici traite les opérations dans l’ordre d’arrivée au serveur ; citation de l’article évoqué : « pas besoin d’algorithmes fancy, donc c’est simplifié ». Comme beaucoup de services utilisent de toute façon un serveur central, cela paraît pratique, mais comme la coordination côté serveur oblige à annuler/réappliquer les modifications locales, certains doutent que ce soit réellement beaucoup plus simple

  • Commentaire disant que « rewind/replay » paraît lui aussi être une approche fancy, et qu’un Persistent B+Tree n’a rien de particulièrement simple non plus

  • Explication qu’Automerge peut lui aussi, au final, établir un ordre global en interne, mais qu’en pratique il traite les opérations texte via des CRDT plus traditionnels (comme RGA), notamment parce que undo/replay n’est pas simple

• Impression d’un CRDT non optimisé, avec la blague que ce serait juste un set utilisé brutalement avec max set size=1

  • À l’inverse, retour disant que réduire ainsi la complexité est séduisant justement parce que cela se rapproche davantage de ce qui se passe réellement ; même sans optimisation, l’idée garde son attrait

• Si l’on utilise une réconciliation côté serveur, il y a un risque que les problèmes de fusion deviennent difficiles côté client ; question sur la manière de garder une UX fluide dans l’éditeur lorsque les mises à jour du serveur arrivent séquentiellement : par exemple, faut-il réessayer si une requête d’insertion échoue, et que faire si d’autres mises à jour arrivent entre-temps ? Parmi les solutions proposées : rembobiner puis réappliquer l’historique d’édition, ou attendre et vider la file. Du point de vue frontend, il semble exister beaucoup de cas limites UI/UX non explicités, et pour cette raison les CRDT pourraient en fait être plus simples, en particulier dans des environnements réseau instables comme dans le métro ; curiosité aussi sur l’expérience utilisateur réelle dans ce genre de contexte

  • Explication que ProseMirror et les versions récentes de CodeMirror gèrent les modifications du document sous forme de step, en mettant à jour à chaque étape les informations de position (position map) afin de pouvoir appliquer les étapes mises en tampon au document ; il est souligné que cela fonctionne bien en pratique pour l’édition collaborative, avec partage d’un lien de référence

• Proposition que quelqu’un essaie d’utiliser un LLM (par ex. un modèle 4b) pour résoudre des conflits de fusion dépassant les cas simples, sans recourir à des CRDT ou OT compliqués ; ce serait peut-être mauvais sur le plan énergétique, mais cela pourrait étonnamment bien fonctionner

  • Dans un conflit comme l’exemple où, à partir de « My name is », on insère respectivement « Charlie » et « Dave » après « is », quelqu’un se demande comment un LLM fusionnerait cela