- Dans une application collaborative reposant sur un serveur central, modifier du texte via des indices de tableau décale les positions lors d’éditions simultanées ; on attribue donc à chaque caractère un ID global unique et on met à jour l’état du serveur en « insérant après un ID donné »
- Les CRDT et OT utilisés dans des services réels sont puissants, mais leurs algorithmes d’ordre total ou leurs règles de transformation d’opérations sont complexes, ce qui rend difficile l’adaptation de leur fonctionnement interne aux besoins de l’application
- L’approche proposée consiste à ce que le client et le serveur conservent une liste d’ID de la forme
Array<{ id: ID; char?: string; isDeleted: boolean }> et laissent aussi les caractères supprimés sous forme de tombstone, afin que les références aux positions d’insertion ultérieures ne se cassent pas
- Les mises à jour locales optimistes sont traitées par réconciliation serveur (server reconciliation) : lorsqu’une opération distante arrive, on annule les opérations locales en attente, puis on réapplique dans l’ordre l’opération distante et les opérations locales non encore confirmées
- Le texte aborde aussi l’ordre des insertions simultanées, le formatage rich text, les variantes distribuées et la bibliothèque
Articulated, et montre qu’un serveur peut définir des opérations flexibles allant au-delà de l’insertion et de la suppression, adaptées à la sémantique de chaque application
Pourquoi l’édition basée sur des indices casse en cas d’édition simultanée
- Dans l’édition collaborative de texte, le client envoie au serveur les opérations saisies par l’utilisateur, et le serveur doit mettre à jour son état faisant autorité
- Si l’on considère le texte comme un tableau de caractères et que l’on envoie une opération comme
insérer " the" à l’index 17, le même index peut désigner un autre emplacement si un autre utilisateur a inséré du texte avant que l’opération n’arrive au serveur
- Par exemple, si Alice insère
" gray" au début, l’index 17 de Bob ne correspond plus à l’emplacement d’origine
- Le serveur doit rebaser l’opération de Bob vers l’
index 22
- Le point clé est de savoir quelles opérations le client envoie au serveur, et comment le serveur doit les interpréter pour mettre à jour le texte d’une manière « manifestement correcte »
- Ce problème de rebasage d’indices peut apparaître non seulement dans des applications collaboratives en temps réel comme Google Docs, mais aussi dans des formulaires web qui insèrent des éléments de liste, ou dans des applications locales monothread qui gèrent des commentaires inline ou un historique de modifications
Là où les CRDT et OT pèsent dans la pratique
- Les solutions existantes se divisent principalement en CRDT et OT
- Les CRDT attribuent à chaque caractère un ID immuable ou une « position », puis trient ces ID selon un ordre total mathématique, par exemple un parcours d’arbre particulier
- Les OT transforment les opérations elles-mêmes en tenant compte des éditions simultanées ; dans l’exemple,
insérer à l’index 17 devient insérer à l’index 22
- Les deux approches sont déjà utilisées dans des services réels
- Google Docs utilise OT
- La bibliothèque CRDT Yjs est utilisée dans plusieurs applications
- La difficulté vient de leur complexité conceptuelle
- L’ordre total d’un CRDT d’édition de texte est souvent un algorithme subtil défini dans des articles académiques
- Les algorithmes OT doivent satisfaire des « propriétés de transformation » algébriques ; le nombre de cas augmente au carré et les défauts sont fréquents sans vérification formelle
- Les algorithmes complexes rendent aussi l’implémentation complexe et conduisent généralement à utiliser une bibliothèque conçue par des spécialistes comme une boîte noire réseau
- Lorsqu’on a besoin d’une fonctionnalité que la bibliothèque n’avait pas prévue, sa structure monolithique devient un frein
- Ne charger en mémoire que les parties nécessaires d’un gros document et laisser le reste sur disque
- Faire appliquer côté serveur des permissions sur des sous-parties du document, comme des droits d’édition par paragraphe ou des droits d’utilisation de certains formats
- Afficher dans le corps du texte ou sur le côté des modifications suggérées à la Google Docs
- Stocker le texte sous une représentation facile à synchroniser avec un stockage clé-valeur comme Replicache
- Prendre en charge des opérations autres que l’insertion et la suppression, comme le déplacement de texte, la manipulation de l’arbre du document, ou la scission et la fusion de paragraphes
ID de caractères et approche « insert after »
- L’idée de base consiste à attribuer à chaque caractère un ID global unique au lieu d’utiliser des indices de tableau
- La structure de données centrale est de la forme
Array<{ id: ID; char: string }>
- Au lieu de
insérer à l’index 17, le client envoie au serveur une opération comme insérer " the" après f1bdb70a
- Le serveur trouve l’ID cible et insère les nouveaux caractères juste après
- Les ID des nouveaux caractères doivent eux aussi être fournis par le client
- Exemple :
insérer " the" après f1bdb70a avec les ids [...]
- Si le client génère les ID, il peut référencer un nouvel ID dans une opération
insert after ultérieure avant même de recevoir la réponse du serveur
- Si l’on supprime complètement les caractères effacés, on risque de perdre l’emplacement d’insertion
- Si Bob veut insérer après
26085702 pendant qu’un autre utilisateur supprime le caractère 26085702, le serveur ne sait plus où insérer
- Le serveur doit donc conserver aussi les ID supprimés dans sa liste interne
- La représentation corrigée de l’état est la suivante
Array<{ id: ID; char?: string; isDeleted: boolean }>
- Le texte visible par l’utilisateur peut être construit en concaténant uniquement les éléments non supprimés
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')
Traitement des insertions et des suppressions
- Lors de la saisie d’un caractère, le comportement du client et du serveur est simple
- Le client trouve
before, l’ID du caractère immédiatement avant le point d’insertion
- Il génère pour le nouveau caractère un ID global unique
id, par exemple un UUID
- Il envoie au serveur une opération demandant d’insérer
char avec l’id après before
- Le serveur cherche
before, y compris parmi les éléments supprimés, puis insère juste après cet élément { id, char, isDeleted: false }
- La suppression de caractères se traite aussi à partir des ID
- Le client trouve l’
id du caractère à supprimer
- Il envoie au serveur une opération demandant de supprimer l’élément correspondant à cet ID
- Le serveur trouve cet élément et, s’il n’est pas déjà supprimé, définit
entry.isDeleted = true
- Cette approche résout directement le problème de position des opérations d’édition envoyées au serveur, sans suivre des articles sur les CRDT ou OT
- Une implémentation naïve par tableau peut être inefficace, puisqu’il faut stocker un UUID pour chaque caractère ; les optimisations sont traitées dans
Articulated
Mises à jour optimistes et réconciliation serveur
- Dans l’édition collaborative à la Google Docs, l’utilisateur doit voir immédiatement le résultat de sa saisie sans attendre la réponse du serveur
- La difficulté apparaît quand le client reçoit du serveur une opération distante simultanée alors qu’il a encore des opérations locales en attente que le serveur n’a pas confirmées
- Dans ce cas, un CRDT n’est pas indispensable : on peut traiter la situation par réconciliation serveur (server reconciliation)
- Annuler toutes les opérations locales en attente pour ramener l’état du client au point de vue du dernier état serveur connu
- Appliquer l’opération distante afin d’aligner le client sur l’état du serveur
- Réappliquer les opérations locales qui n’ont pas encore été confirmées
- Une stratégie plus simple est Wait for Ack, qui interdit de traiter les opérations distantes lorsqu’il existe des opérations locales en attente
- Le client de Bob peut ignorer le premier message du serveur jusqu’à recevoir l’état serveur dans lequel son propre message a été traité
- Si Bob continue de saisir ou si la latence réseau est élevée, le délai peut s’allonger indéfiniment, ce qui est moins temps réel que la réconciliation serveur
Ce qui change par rapport aux CRDT
- L’approche proposée partage certains traits avec les CRDT : elle attribue un ID à chaque caractère et utilise un marqueur
isDeleted
- La différence tient à la manière de gérer l’ordre
- Ici, le client dit au serveur
insère X après Y, et le serveur le fait tel quel ou le traite d’une autre manière définie par le développeur
- Dans un CRDT d’édition de texte, les ID sont triés par un algorithme complexe
- Ce mécanisme de tri des ID est aussi ce qui distingue de nombreux CRDT d’édition de texte entre eux ; cette approche l’évite
Le résultat des insertions simultanées
- Lorsque plusieurs utilisateurs saisissent simultanément au même endroit, le résultat est placé dans l’ordre inverse de l’ordre dans lequel le serveur reçoit les opérations
- Supposons par exemple que le texte soit
"My name is", et que Charlie saisisse " Charlie" tandis que Dave saisit " Dave" en même temps
- Si l’opération de Charlie arrive en premier, le serveur produit
"My name is Charlie"
- L’opération de Dave s’insère elle aussi après l’ID du
s de is, ce qui donne "My name is Dave Charlie"
- Les opérations
insert after visant le même ID cible sont donc placées dans l’ordre inverse de réception par le serveur, même sans simultanéité
- Malgré cela, les mots saisis de gauche à droite ne se mélangent pas caractère par caractère
- Même si Dave envoie chaque caractère comme une opération distincte,
a est inséré après D, et v après a
- L’état du serveur évolue comme
"My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie"
- En revanche, pour une saisie de droite à gauche, si les opérations de Charlie et Dave arrivent au serveur dans un ordre entrelacé, le texte final peut lui aussi être entrelacé
- En pratique, cela peut se produire lorsque deux utilisateurs sont en ligne simultanément et ignorent les modifications en cours de l’autre
Le serveur peut définir des opérations plus flexibles
- Avec la réconciliation serveur, le serveur peut traiter les opérations client pratiquement comme il le souhaite, et le client finit par atteindre le même état
- Cela contraste avec les CRDT et OT, qui n’autorisent que des opérations satisfaisant des règles algébriques strictes
- Pour des insertions simultanées au même endroit, le serveur peut réagir de plusieurs manières
- Ignorer l’opération et la traiter comme un no-op
- Ajouter l’ID à la liste interne mais le marquer immédiatement comme supprimé, afin que les opérations ultérieures de Dave puissent référencer l’ID précédent
- Insérer le texte, mais appliquer un format spécial de révision aux deux mots
- Convertir la modification de Dave en « suggestion » affichée à côté du corps du texte
- Demander à un LLM comment corriger le texte
- Le client peut aussi envoyer des opérations qui expriment mieux l’intention utilisateur
insert before peut servir, lors de la création d’un titre au-dessus d’un paragraphe, à éviter que le titre soit inséré au milieu d’insertions simultanées à la fin du paragraphe précédent- Une opération
fix typo peut exprimer une condition du type insérer u après le o de color portant l’ID X, mais seulement si le mot autour est toujours color
- Le serveur peut aussi définir des opérations dont la position d’insertion elle-même change après leur arrivée au serveur
- Il peut réordonner alphabétiquement les insertions simultanées au même endroit
- Si l’on ajoute une opération
move pour le glisser-déposer, un insert after à l’intérieur du texte déplacé peut s’appliquer dans le texte déplacé plutôt qu’à son emplacement d’origine
Gestion du formatage rich text
- Le rich text gère des formats inline comme le gras, la taille de police ou les hyperliens
- Les formats de plage peuvent eux aussi être exprimés avec des ID de caractères plutôt qu’avec des indices
- Exemple :
appliquer bold de l’ID X à l’ID Y
- En le définissant comme
de l’ID X inclusive à l’ID Y exclusive, les insertions simultanées en fin de plage peuvent elles aussi être mises en gras
- Avec un éditeur rich text comme ProseMirror, le serveur peut trouver les indices actuels dans le tableau pour les ID X et Y, puis demander à l’état ProseMirror local de mettre cette plage en gras
- ProseMirror peut ensuite maintenir le gras pour le texte inséré dans cette plage
- Le serveur peut toutefois appliquer un comportement différent selon une opération d’insertion comme
bold set to false
- Pour comprendre la sémantique du rich text collaboratif, l’essai Peritext constitue une référence utile
Variantes distribuées et lien avec les CRDT
- Jusqu’ici, on a supposé qu’un serveur central définit l’ordre total des opérations selon leur ordre de réception, puis met à jour l’état faisant autorité
- Dans les applications sans serveur central, ou où le serveur est optionnel, on peut attribuer un ordre total final aux opérations de manière distribuée
- Par exemple en triant les opérations avec des Lamport timestamps
- Chaque client considère comme état faisant autorité le résultat du traitement dans l’ordre de toutes les opérations reçues jusque-là
- Dans ce cas, les ID par caractère et les opérations
insert after fonctionnent aussi dans une réconciliation distribuée « sans serveur »
- Techniquement, le résultat devient alors un CRDT d’édition de texte
- Parce qu’il s’agit d’un algorithme d’édition collaborative de texte distribué et à cohérence finale
- Selon la méthode d’ordonnancement utilisée, on retrouve des liens avec des CRDT existants
- Si les opérations sont triées par Lamport timestamp, l’ordre de la liste résultante est équivalent à RGA / Causal Trees
- En combinant Lamport timestamp et opérations de formatage, le comportement ressemble beaucoup à Peritext
- Avec un tri topologique en profondeur d’abord, l’ordre de la liste résultante est équivalent à Fugue
- La preuve détaillée de ces équivalences n’a pas été rédigée
Articulated : bibliothèque d’aide à l’implémentation
- Dans une implémentation réelle, le texte lui-même peut être stocké ailleurs, par exemple dans un état ProseMirror, et cette approche peut n’avoir besoin que d’une liste d’ID de la forme suivante
Array<{ id: ID; isDeleted: boolean }>
- Quatre opérations sont fréquemment nécessaires sur cette liste
- Convertir entre un ID et l’indice actuel du tableau
- Insérer un nouvel ID après un ID donné
- Marquer un ID comme supprimé
- Sérialiser et restaurer l’état pour le stockage
- Un simple tableau n’est pas adapté à ces opérations
- Les opérations 1 à 3 prennent un temps linéaire
- Stocker un objet et un UUID par caractère consomme beaucoup de mémoire et d’espace de stockage
- Articulated est une petite bibliothèque npm qui fournit les mêmes fonctionnalités que ce tableau
- Sa structure de données centrale,
IdList, utilise des optimisations similaires à celles de bibliothèques CRDT populaires pour l’édition de texte
- Les ID ont la forme
{ bunchId, counter }, où bunchId est un UUID que plusieurs ID peuvent partager
- Lorsque des ID d’un même bunch sont adjacents, comme dans le cas courant d’une insertion de gauche à droite, ils sont stockés comme un seul objet en mémoire et dans l’état sérialisé
- La structure de données centrale n’est pas un tableau mais un B+Tree, de sorte que les appels de méthodes prennent un temps
log ou log^2
IdList est aussi une structure de données persistante (persistent data structure)
- Le client peut conserver à faible coût le dernier état reçu du serveur et l’état optimiste
- Lorsqu’une opération distante arrive, il est facile de revenir au dernier état du serveur
- Des ressources supplémentaires sont fournies : la docs, les premiers demos, et IdListSimple, une implémentation simple de moins de 300 SLOC
IdListSimple omet les optimisations et la persistance, mais il est fonctionnellement identique et vérifié par des fuzz tests
1 commentaires
Avis sur Hacker News
Plutôt propre. L’algorithme consiste à attribuer à chaque caractère du texte un identifiant global unique de type UUID, afin de pouvoir le référencer de manière cohérente dans le temps plutôt que via des indices de tableau qui changent sans cesse.
Les clients envoient au serveur une opération « insert after » qui référence un identifiant existant, et le serveur trouve l’ID cible puis insère le nouveau caractère juste après. Les suppressions ne font que masquer le caractère à l’affichage ; celui-ci reste conservé pour le calcul des positions « insert after ». Au-delà de l’édition de texte, on voit un potentiel pour des usages comme la synchronisation de mondes de jeu.
ctrl+a,ctrl+x,ctrl+v, il faudra sans doute croiser les doigts.Ça fait plaisir de voir ce genre d’article. J’avais découvert la même méthode il y a quelques années, et je me demandais pourquoi on la voyait si peu dans la littérature académique.
Cela dit, je l’avais implémentée comme un CRDT dans un contexte décentralisé, afin de préserver des propriétés comme la commutativité, l’idempotence et l’associativité.
J’ai été surpris qu’il ne soit pas question d’autres structures de données comme les dict/map ou les tableaux de types arbitraires. Ce serait bien que ce soit facile à étendre à ces cas-là aussi. D’expérience, les apps ont plus souvent besoin de structures de données collaboratives que d’édition de texte collaborative pure.
Les exemples de synchronisation — validation des mises à jour, chargement partiel, opérations de haut niveau — sont intéressants, mais l’argument selon lequel des outils comme Yjs n’ont pas ces fonctionnalités à cause de l’implémentation CRDT sous-jacente, plutôt que parce qu’elles sont tout simplement difficiles à construire, ne me paraît pas très convaincant.
Pour reprendre les termes de l’auteur, j’ai toujours pensé que les utilisateurs d’une bibliothèque d’aide devraient pouvoir insérer un peu de logique de modèle sémantique afin d’empêcher ou de gérer les états invalides. Par exemple, une tâche ne peut pas être à la fois
isDone: trueetstate: inProgress. C’est similaire à la sémantique de mise en forme de texte enrichi mentionnée dans l’article lié.Imaginez que tous les conflits de merge Git soient résolus en choisissant automatiquement un côté. La plupart du temps, on obtiendrait un résultat incorrect, et parfois même du code qui ne compile pas. S’il n’y a personne pour corriger immédiatement, cela mène à des résultats encore plus confus.
C’est pour cela, à mon avis, que les CRDT ne se sont pas davantage répandus. Ils ne corrigent que le « problème qu’on pensait avoir », mais pas le vrai problème : la résolution de conflits qui préserve les données, la validité et la sémantique. On pourrait même dire qu’ils aggravent ce problème en limitant les méthodes de résolution des conflits à ce qui peut être répliqué de manière déterministe.
La différence essentielle avec les CRDT semble être que, si l’on dispose d’un serveur central, la synchronisation — c’est-à-dire la détermination de l’ordre entre événements concurrents — ne devrait pas être gérée par la structure de données elle-même au moyen d’un ordre lexicographique, mais par le serveur.
Comme toutes les communications se font uniquement entre client et serveur, et non entre clients, lorsque qu’un client se connecte au serveur, celui-ci peut garantir qu’il traitera d’abord toutes les opérations locales de ce client avant de lui envoyer de nouvelles mises à jour distantes.
Le message central de cet article, c’est que toute la complexité des CRDT/OT n’est nécessaire que lorsqu’il n’y a pas de serveur central ?
Comme le disent d’autres commentaires, techniquement c’est aussi un CRDT, et sous une forme assez générale. De plus, l’implémentation même de l’annulation et de la relecture des opérations n’est pas triviale. J’espère néanmoins que cela restera plus simple que d’utiliser des CRDT/OT traditionnels pour chaque type de données.
Je ne suis pas spécialiste du domaine, mais la principale différence avec des CRDT comme Automerge semble être la coordination par serveur. Par exemple, dans cet article [1], Automerge utilise des numéros de séquence pour gérer les insertions simultanées, et lorsque les insertions ont lieu en même temps, il s’appuie sur un ordre convenu des ID d’agents. Cette approche, en revanche, repose sur le serveur qui traite les opérations dans l’ordre d’arrivée.
L’article dit en substance : « dans les CRDT d’édition de texte, un algorithme sophistiqué détermine l’ordre des ID. Cet algorithme d’ordonnancement fait la différence entre plusieurs CRDT d’édition de texte et constitue la partie complexe des articles sur les CRDT. Nous l’évitons complètement ». Comme beaucoup d’apps ont de toute façon un serveur central, l’idée d’éviter cet « algorithme sophistiqué » se comprend. Cela dit, la coordination côté serveur nécessite d’annuler puis de rejouer les modifications locales, donc je ne suis pas entièrement convaincu que ce soit beaucoup plus simple. [1] https://josephg.com/blog/crdts-go-brrr/
Mais Automerge ne procède pas réellement ainsi : il traite les opérations de texte avec un CRDT traditionnel, RGA. C’est probablement, comme tu le soulignes, parce qu’implémenter l’annulation et la relecture des opérations n’est pas facile.
Donc, un CRDT non optimisé, en quelque sorte ? Avec une taille maximale d’ensemble fixée à 1 et on force le passage ?
Le recours à la coordination par serveur risque de rendre la coordination côté client délicate. Comment maintenir une expérience d’édition fluide tout en appliquant chaque mise à jour du serveur à son arrivée ?
Par exemple, si une demande d’insertion de caractère envoyée par le client échoue, faut-il simplement réessayer ? Et si des mises à jour sont arrivées entre-temps ? Édition : la section « Client-Side » reconnaît ce cas, propose de rembobiner puis de rejouer, et suggère aussi une solution plus simple consistant à bloquer jusqu’à ce que la file d’attente soit vide. Du point de vue frontend, il peut y avoir une longue traîne de cas limites UI/UX non explicités, si bien qu’au final les CRDT pourraient être plus simples. Et je me demande aussi ce que donne la sensation d’édition dans le métro new-yorkais, où la connexion saute facilement.
En pratique, cela fonctionne assez bien. Plus de détails ici :
https://marijnhaverbeke.nl/blog/collaborative-editing.html
https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...