cola : technologie de CRDT textuel pour l’édition collaborative en temps réel

 (nomad.foo)
1 points par GN⁺ 2023-09-04 | 1 commentaires | Partager sur WhatsApp
  • cola est un CRDT textuel pour l’édition collaborative en temps réel, écrit en Rust, qui vise à faire converger un document vers le même état quand plusieurs pairs le modifient simultanément sans coordinateur central
  • La position dans le document est figée non pas par un simple offset mais par un Anchor de la forme ReplicaId.n, ce qui évite que le sens de la position dérive lors d’éditions concurrentes
  • Les conflits d’insertion sont résolus de façon cohérente avec un Lamport timestamp et l’ordre de ReplicaId, tandis que les suppressions sont gérées via des tombstones et un version vector au lieu d’une suppression physique
  • Côté implémentation, cola utilise un RLE basé sur EditRun et un G-tree représenté par des index de Vec, afin d’obtenir recherche et insertion en temps logarithmique dans le modèle de propriété sûr de Rust
  • Dans les benchmarks, cola a été comparé à diamond-types, automerge et yrs ; en upstream, il est 1,4 à 2 fois plus rapide que diamond-types et affiche aussi d’excellentes performances en downstream

Le problème d’édition collaborative traité par cola

  • cola est un CRDT textuel écrit en Rust, conçu pour que plusieurs répliques convergent vers le même état dans l’édition collaborative en temps réel, sans autorité centrale
  • Au niveau réseau, l’hypothèse minimale est simplement que toutes les modifications finissent par atteindre tous les pairs
    • une modification peut être transmise plusieurs fois
    • une modification peut arriver dans un ordre arbitraire
    • tous les pairs doivent finir par recevoir toutes les modifications
  • L’objectif n’est pas seulement d’obtenir le même état de document après réception de toutes les modifications, mais aussi que le document final reste cohérent du point de vue de l’utilisateur

Fixer les positions avec des Anchor plutôt qu’avec des offsets

  • Une édition basée sur les offsets comme insert "abc" at offset 8 peut changer de sens si un autre pair modifie en même temps une zone antérieure, ce qui peut faire diverger les répliques
  • cola référence les positions du document non pas par le contenu textuel ou par un offset, mais par des identifiants stables
    • chaque pair attribue un numéro croissant aux caractères qu’il insère
    • chaque pair possède un identifiant unique, ReplicaId
    • la paire ReplicaId.n devient l’identifiant de position unique du caractère, appelé Anchor
  • La valeur n peut garantir son unicité via l’incrément d’un compteur local, mais garantir l’unicité globale de ReplicaId sans serveur central est plus difficile
    • cola part du principe qu’on utilise un entier aléatoire très grand, à la manière d’un UUID, avec une probabilité de collision négligeable
  • Une insertion est positionnée à l’aide d’un seul Anchor, tandis qu’une suppression désigne une plage avec deux Anchor, début et fin

Ordonner les conflits d’insertion dans le même ordre

  • Quand plusieurs insertions arrivent sur le même Anchor, cola détermine leur ordre via un Lamport timestamp
  • L’horloge de Lamport est mise à jour selon les règles suivantes
    • lors d’une insertion locale de texte, l’horloge est incrémentée de 1
    • à la réception d’une insertion distante, elle est définie à max(current, remote_timestamp) + 1
  • Si une insertion A a été créée dans un contexte où l’insertion B avait déjà été intégrée, alors le Lamport timestamp de A sera supérieur à celui de B
  • Les insertions en conflit sont triées par Lamport timestamp décroissant
  • Pour les insertions concurrentes ayant à la fois le même Anchor et le même Lamport timestamp, il n’existe pas d’ordre plus juste du point de vue de l’utilisateur ; cola utilise donc l’ordre croissant de ReplicaId pour garantir la cohérence entre pairs

Les suppressions sont gérées avec des tombstones et des version vectors

  • Une suppression convertit d’abord les offsets de début et de fin en Anchor, puis la propage aux autres pairs
  • Si deux pairs suppriment simultanément la même zone, le résultat est équivalent à une suppression unique, sauf si l’on prend en compte l’undo
    • cola ne prend pas encore en charge l’annulation des suppressions
  • Le traitement des suppressions pose trois difficultés
    • si le texte supprimé est retiré complètement, des Anchor de modifications pas encore arrivées peuvent se trouver dans cette zone
    • si une suppression distante est intégrée trop tôt, le contenu vu par le pair émetteur peut différer de celui du pair récepteur, ce qui peut faire diverger les répliques
    • dans la plage supprimée, il ne faut pas supprimer des caractères que le pair émetteur n’avait pas encore vus
  • Le premier problème est résolu avec des tombstones
    • les caractères supprimés restent dans le document, mais sont marqués comme supprimés
    • cette approche augmente l’usage mémoire
  • Les autres problèmes sont résolus en incluant un version vector dans le message de suppression
    • la clé est ReplicaId, et la valeur est le timestamp du dernier caractère vu à ce moment par le pair qui a créé la suppression
    • le pair récepteur attend pour intégrer la suppression jusqu’à ce que son propre version vector soit au moins égal à celui du message de suppression
    • les caractères dont le timestamp est supérieur à celui du version vector de suppression sont exclus de la suppression
  • Dans cola, le version vector est appelé version map

Séparation entre Replica et tampon de texte

  • L’état local du document de chaque pair est représenté dans cola par Replica
  • L’algorithme CRDT de cola n’a pas besoin de connaître le contenu réel de la chaîne
    • les fonctions de l’API ne prennent pas de chaîne en paramètre
    • cola manipule uniquement des blocs numériques, pas le contenu du document
  • Cette conception sépare le mécanisme CRDT de l’implémentation réelle du tampon de texte

Réduire les métadonnées avec RLE et EditRun

  • Comme il est difficile d’obtenir une implémentation performante si l’on attache des métadonnées à chaque caractère, cola regroupe en run-length encoding les blocs de timestamps consécutifs
  • Par exemple, coller la page complète de Wikipedia sur le Manhattan Project peut être représenté non pas par 107 000 blocs, mais par un seul bloc
  • Si l’on saisit une phrase caractère par caractère sans déplacer le curseur ni supprimer, il n’est pas nécessaire de créer un bloc par frappe ; l’ensemble peut être représenté par un seul run
  • Dans cola, ces blocs continus sont appelés EditRun
    • une fois cassé, un EditRun reste figé pour toute la durée de vie du document et ne s’étend plus
    • un run qui n’a pas encore été cassé est dans un état actif
  • Si du texte est inséré au milieu d’un EditRun existant, le run est scindé en deux et le nouveau texte est inséré entre les deux
  • Quand du texte est supprimé, la partie concernée est détachée du run et marquée comme tombstone
    • les runs supprimés peuvent eux aussi être compressés en RLE, ce qui réduit le coût mémoire des tombstones

De la liste chaînée au B-tree

  • Le chemin upstream des éditions locales correspond à la conversion d’éditions basées sur les offsets en éditions transmissibles aux autres pairs
    • pour les insertions comme pour les suppressions, il faut trouver le run contenant l’offset et produire un Anchor
    • si nécessaire, le run peut être scindé en au plus 2 parties pour une insertion et 3 pour une suppression
  • Dans une liste chaînée, le découpage d’un run se fait en O(1), mais trouver le run contenant l’offset nécessite de balayer depuis le début, donc en temps linéaire
  • Mettre en cache le run actif courant et son offset permet d’accélérer les éditions répétées au même endroit, mais le pire cas reste linéaire
  • Pour garantir de meilleures performances au pire cas, cola envisage une structure en B-tree
    • les runs sont représentés comme des feuilles du B-tree
    • les inodes stockent leurs enfants ainsi que la somme des longueurs de ceux-ci
    • les tombstone runs contribuent avec une longueur nulle
    • la longueur de la racine est égale à la longueur totale du document
  • Le B-tree permet d’effectuer recherche et insertion en O(log n), ce qui donne un traitement logarithmique des éditions locales
  • En revanche, pour les éditions distantes, convertir efficacement Anchor -> run nécessite de retrouver la feuille contenant l’Anchor

G-tree : un B-tree représenté avec des index de Vec

  • Avec de simples pointeurs vers les feuilles d’un B-tree classique, il est difficile de savoir comment redescendre jusqu’à une feuille lors d’une insertion top-down
  • Les opérations bottom-up nécessitent des pointeurs vers les parents, ce qui, dans le modèle de propriété sûr de Rust, peut obliger à utiliser des structures comme Rc<RefCell<_>>, plus lentes et plus complexes
  • cola stocke tous les nœuds dans un tableau dynamique de type Vec et représente les références entre nœuds non pas par des pointeurs, mais par des index
    • le vecteur possède tous les nœuds
    • chaque nœud peut stocker l’index de son parent
    • la navigation bidirectionnelle est possible sans code unsafe
  • Cette structure repose sur l’hypothèse que les index des nœuds ne changent pas
    • les nouveaux nœuds sont ajoutés à la fin du vecteur
    • cola ne retire pas les runs, il les marque comme tombstones, ce qui évite les problèmes d’invalidation d’index
  • cola appelle cette structure grow-only tree-in-a-vector un G-tree
  • Le code Rust du G-tree conserve la structure parent-enfant d’un B-tree tout en ne changeant que sa représentation mémoire

Les caractéristiques de performance apportées par le G-tree

  • Comme un B-tree, le G-tree effectue recherche et insertion top-down en temps logarithmique
  • L’index de vecteur d’une feuille, LeafIdx, peut servir d’identifiant stable pour la feuille
  • Le run actif courant peut être mis en cache non pas comme pointeur, mais comme LeafIdx
    • lors d’éditions répétées à la même position du curseur, il suffit d’étendre le run actif et de mettre à jour les longueurs des ancêtres jusqu’à la racine
    • cela peut se faire sans parcours d’arbre ni nouvelle allocation, avec seulement quelques comparaisons d’entiers et 2 à 4 additions d’entiers
  • Le G-tree de cola utilise un facteur de branchement de 32, et le taux moyen de remplissage des inodes est d’environ 20 enfants
    • avec seulement 4 niveaux, il peut généralement stocker environ 160k EditRun distincts
    • après traitement de la trace d’édition automerge-paper, le G-tree de cola contient environ 15k EditRun
    • cette trace comprend 260k éditions, enregistrées sur plusieurs jours
  • Comme les nœuds du G-tree sont déjà stockés en mémoire linéaire, la sérialisation et la désérialisation sont également simples

Convertir un Anchor en LeafIdx

  • Le chemin downstream des éditions distantes consiste à convertir des éditions basées sur des Anchor, comme insert 2.3..7 at 1.2 ou delete between 3.4 and 2.2, en éditions locales basées sur les offsets
  • Comme le G-tree permet de naviguer vers le haut et vers le bas, il est possible de calculer l’offset correspondant si l’on connaît le LeafIdx du run contenant un Anchor donné
  • Le point clé est donc la conversion Anchor -> LeafIdx
  • Une conception simple consiste à ajouter un G-tree ou un B-tree auxiliaire, dont les feuilles stockent ReplicaId, une plage temporelle et le LeafIdx du G-tree principal
    • les feuilles sont totalement triées selon ReplicaId et la plage temporelle
    • on peut descendre dans l’arbre à partir de l’Anchor pour retrouver le LeafIdx voulu
    • la recherche comme l’insertion sont en O(log n)
  • Le code source réel de cola n’utilise toutefois pas exactement cette approche avec G-tree auxiliaire
    • dans l’implémentation réelle, la recherche et l’insertion sont en O(log f)
    • f est le nombre de fragments dans lesquels l’EditRun contenant l’Anchor a été découpé au fil du temps
    • f est toujours inférieur ou égal à n, et en pratique souvent bien plus petit

Niveau de maturité actuel et travail restant

  • La conception de cola pose les bases nécessaires pour viser la convergence, la préservation de l’intention et de bonnes performances
  • Pour être prêt pour la production, il reste à ajouter la prise en charge de l’undo/redo ainsi que quelques travaux complémentaires

Benchmarks de CRDT Rust

  • cola a été comparé à trois CRDT basés sur Rust
  • Les benchmarks mesurent le temps nécessaire pour traiter des traces d’édition réelles caractère par caractère
    • ils utilisent la bibliothèque de benchmarking Rust criterion
    • ils mesurent à la fois l’upstream et le downstream
    • le code des benchmarks est disponible dans crdt-benches
  • Les graphiques prennent comme référence 100x les performances de cola et n’affichent pas les mesures de plus de 100 fois plus lentes que cola
  • L’environnement d’exécution est un MacBook Pro 2018 avec un Intel Core i7 6 cœurs à 2,2 GHz
    • les chiffres peuvent varier sur d’autres machines, mais les performances relatives devraient rester similaires

Résultats des benchmarks

  • En upstream, yrs et automerge dépassent la ligne de base
  • En upstream, cola est 1,4 à 2 fois plus rapide que diamond-types
  • En downstream, diamond-types plante sur toutes les traces et aucune mesure n’a pu être obtenue
    • le billet précise que les résultats seront mis à jour s’il s’avère que la bibliothèque a été mal utilisée
  • En downstream, cola est environ deux fois plus lent qu’en upstream
    • c’est un résultat attendu, car l’intégration d’éditions distantes coûte généralement plus cher que la création d’éditions locales
  • cola affiche dans les deux sens des performances comparables, voire supérieures, à celles de bibliothèques rope rapides, et est présenté comme l’implémentation de CRDT textuel la plus rapide à l’heure actuelle

À lire aussi

1 commentaires

 
GN⁺ 2023-09-04
Avis sur Hacker News

  • Je considère toujours le G-tree comme un B-tree avec des pointeurs vers les parents en plus.
    Le fait qu’il soit stocké dans un tableau n’est qu’une question de représentation, cela ne change pas fondamentalement la structure.
    On stocke toujours des pointeurs, mais ils sont exprimés en unités de taille de nœud plutôt qu’en octets, et sous forme de position relative au premier élément du tableau plutôt qu’au début de l’espace d’adressage.
    Par exemple, même un arbre binaire complet stocké dans un tableau sans références explicites, où les enfants de l’indice x se trouvent en 2x + 1 et 2x + 2, n’est qu’une représentation implicite ; on l’appelle toujours un arbre binaire.

    • Cela dit, parler du mode de représentation reste utile.
      C’est particulièrement vrai dans les langages qui poussent vers des références relatives et autogérées plutôt que vers des références absolues.
      L’une des représentations d’arbres que j’ai trouvées intéressantes consiste à stocker les nœuds dans un tableau plat selon l’ordre d’un parcours en profondeur.
      Si c’est en lecture seule et que le lecteur veut de toute façon parcourir en profondeur, cela peut être assez efficace.
      Cela me fait penser aux S-expressions et au HTML.

  • Sauf si j’ai raté quelque chose dans l’API, il semble que cela ne prenne pas en charge les plages de mise en forme comme le gras ou l’italique.
    À ma connaissance, dans les algorithmes de CRDT pour texte enrichi, Peritext est encore l’état de l’art https://www.inkandswitch.com/peritext/
    Ce serait bien que ce projet reprenne aussi les fonctionnalités de texte enrichi de l’algorithme Peritext.

    • En tant que personne qui suit un peu le domaine des CRDT, je me suis toujours demandé s’il serait possible de créer un CRDT de données structurées plus générique.
      L’idée serait que l’utilisateur définisse un modèle ou un schéma décrivant les états sémantiquement valides.
      Par exemple, fusionner simplement du JSON peut produire un état syntaxiquement valide mais sémantiquement absurde.
      De la même manière que l’algorithme Peritext sait que le gras, l’italique et le soulignement sont des opérations additives alors que la couleur de surlignage ne l’est pas, j’aimerais que l’utilisateur puisse déclarer dans le schéma que state: notStarted et completionDate: 2023-09-04 sont incompatibles.
    • Question : l’article dit que Cola ne traite que l’édition sans conflit pour des types de données inconnus, et qu’en pratique il ne manipule que le flux de caractères et les positions.
      Dans ce cas, ne pourrait-on pas représenter la mise en forme elle-même dans le texte, comme en HTML ?
      Je ne connais pas très bien les autres représentations de texte enrichi, donc je n’en suis pas sûr.
      En plus, en lisant le document Peritext lié plus haut, j’ai vu qu’il traitait précisément de ces difficultés propres au RTF, et je l’ai trouvé assez intéressant.

  • Y a-t-il des différences de performances ou de fonctionnalités par rapport à Automerge ou Y.js/Yrs ?

    • La « troisième partie » de l’article commence par : « nous avons benchmarké cola face à trois autres CRDT implémentés en Rust : diamond-types, automerge et yrs ».
      Cette bibliothèque cola semble avoir un net avantage côté vitesse des opérations.
      Je suis aussi curieux de connaître sa consommation mémoire.

  • À ne pas confondre avec le travail du même nom d’Ian Piumarta.
    https://www.piumarta.com/software/cola/
    https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

    • Il y a aussi les Cache Oblivious Lookahead Arrays, autrefois considérés comme une alternative à MergeTree (LSM), mais qui ne sont plus utilisés aujourd’hui https://github.com/giannitedesco/cola
    • Il existe aussi une appli de style clone de Notion appelée coda.io.

  • Beau travail, mais cela ne ressemble pas à un benchmark équitable.
    Les opérations ne sont ni calculées ni stockées, et le texte réel n’est pas stocké non plus.
    Pour en faire un CRDT de texte prenant en charge les mises à jour delta, l’utilisateur devrait stocker OpID => Text dans une structure séparée, et ce coût n’est pas négligeable.

  • En utilisant la crate slotmap (https://docs.rs/slotmap/latest/slotmap/), on pourrait prendre en charge la suppression sans craindre le déplacement d’indices ni qu’un « indice » pointe vers une autre valeur.
    Dans slotmap, on appelle cela une clé, et la clé contient aussi un numéro de version.

    • Est-ce que cela fonctionnerait aussi dans un contexte de CRDT ?
      Je me pose la question, car l’ordonnancement est difficile et la version pourrait n’avoir de sens que localement.

  • Je vais peut-être essayer ça sur un projet qu’Etherpad et Word n’arrivaient pas à gérer.

  • Si l’on suppose que tous les clients connectés reçoivent toutes les modifications, ne pourrait-on pas mettre le hachage attendu de l’état existant du texte devant l’offset et les commandes d’insertion/suppression/remplacement ?
    Cela permettrait presque de garantir que la modification ne s’applique qu’à l’état approprié, et les changements suivants pourraient être accumulés dans un dictionnaire ayant pour clé le « hachage de l’état des données auquel on s’attend à l’application ».
    Bien sûr, cela coûterait cher puisqu’il faudrait recalculer plusieurs fois le hachage des mêmes données, mais ce serait extrêmement simple à comprendre et à implémenter.

    • Avec cette approche, les modifications asynchrones ne seraient jamais appliquées.
      Si je fais une modification locale dans le document et que vous faites une modification distante, le hachage de votre « état attendu » ne correspondra plus jamais à l’état de mon document.
      C’est parce que j’ai déjà effectué un changement local.
      Pour garantir la convergence, un CRDT suppose bien que tous les clients reçoivent toutes les modifications, mais la propriété selon laquelle il n’est pas nécessaire d’appliquer les mises à jour dans un ordre précis est importante dans les cas d’usage distribués réels.

  • Je me demande s’il existe un moyen d’activer facilement la coédition de formulaires dans le navigateur.
    Ce serait bien que, lorsque deux personnes ouvrent la même page ou le même formulaire, on voie quel champ de saisie l’autre est en train de modifier, et que les champs de saisie texte utilisent un CRDT de texte.
    J’ai essayé d’implémenter quelque chose de similaire avec Yjs, mais c’était assez difficile et ça ne fonctionnait pas très bien.

    • Je serais curieux de savoir pourquoi Yjs ne convenait pas.
      Il me semble pourtant parfaitement adapté à cet usage.