CRDT d’arbre déplaçable et implémentation de Loro

 (loro.dev)
2 points par GN⁺ 2024-07-30 | 1 commentaires | Partager sur WhatsApp
  • Dans les logiciels collaboratifs, l’édition simultanée d’une structure hiérarchique peut provoquer des conflits d’arbre tels que des nœuds dupliqués, des cycles ou le déplacement d’un sous-nœud alors que son ancêtre a été supprimé ; Loro les implémente avec un CRDT d’arbre déplaçable
  • L’approche de Martin Kleppmann et al. unifie création, suppression et déplacement sous la forme Move t p m c, et traite la suppression comme un déplacement vers le nœud TRASH, ce qui préserve les déplacements simultanés de sous-nœuds
  • L’ordre global est établi avec un Lamport Timestamp et un Peer ID, et lorsqu’une opération distante s’insère au milieu de l’ordre existant, on évite les cycles via undo-do-redo
  • Loro combine un Fractional Index pour ordonner les nœuds frères, et lorsque des index se chevauchent à cause d’insertions simultanées au même emplacement, cela est géré avec le PeerID, du jitter et une réinitialisation de l’index
  • Dans les benchmarks, Loro Movable Tree a exécuté 10 000 déplacements aléatoires en 28 ms après la création de 1 000 nœuds, montrant des performances suffisantes pour la collaboration en temps réel et le checkout de versions passées

Conflits qui surviennent dans les arbres collaboratifs

  • Dans les systèmes distribués et les logiciels collaboratifs, lorsqu’on gère des relations hiérarchiques en modélisant un déplacement comme une combinaison de suppression et d’insertion, les attentes des utilisateurs et le mode de résolution des conflits risquent facilement de diverger
  • Si le même nœud est déplacé simultanément vers des parents différents sur plusieurs replicas, le nœud peut être supprimé deux fois puis recréé sous deux parents, ce qui peut produire des nœuds dupliqués avec le même contenu
  • Les opérations de base d’un arbre déplaçable sont au nombre de trois : création, suppression et déplacement
  • Les situations qui posent le plus souvent problème lors de la synchronisation sont les suivantes
    • le même nœud est supprimé et déplacé en même temps
    • le même nœud est déplacé sous des parents différents
    • des déplacements de nœuds différents se combinent pour créer un cycle
    • un sous-nœud est déplacé pendant qu’un nœud ancêtre est supprimé

Méthodes de traitement selon le type de conflit

  • Si la suppression et le déplacement du même nœud entrent en conflit, on peut appliquer l’une des opérations et ignorer l’autre selon le timestamp du système distribué ou les exigences de l’application
  • Lorsque le même nœud est déplacé sous des parents différents, les options varient selon l’application
    • supprimer le nœud puis créer des copies sous des parents différents, qui sont ensuite traitées indépendamment
    • permettre à un nœud de pointer vers deux parents, mais cela casse la structure en arbre et reste généralement difficile à accepter
    • trier toutes les opérations puis les appliquer dans l’ordre pour produire le même résultat sur tous les peers
  • Lorsque des déplacements de nœuds différents créent un cycle, la résolution de conflit dans un arbre déplaçable devient particulièrement complexe
    • Matthew Weidner récapitule plusieurs approches : gestion d’erreur, rendu d’une zone « time-out », rejet côté serveur, tri topologique puis saut des opérations qui créent un cycle, masquage de certains edges au rendu, ou retour au parent précédent
  • La situation où un sous-nœud est déplacé pendant la suppression d’un nœud ancêtre est elle aussi facile à négliger
    • si tous les sous-nœuds de l’ancêtre sont supprimés immédiatement, l’utilisateur peut croire que ses données ont été perdues

L’approche de Dropbox et de Figma

  • Dropbox traitait au départ le déplacement d’un fichier en deux étapes : suppression à l’emplacement d’origine puis création au nouvel emplacement
    • si une panne de courant ou un crash système survenait entre la suppression et la création, il y avait un risque de perte de données
    • aujourd’hui, lorsque plusieurs personnes tentent simultanément de déplacer et d’enregistrer le même fichier, Dropbox détecte le conflit et, en général, conserve une version du fichier original puis crée une « conflicted copy » pour les modifications d’un utilisateur
  • Figma considère la structure en arbre comme la partie la plus complexe de son système collaboratif et attribue une propriété parent à chaque élément
    • le serveur central surveille les mises à jour de plusieurs utilisateurs et rejette toute opération susceptible de créer un cycle
    • à cause de la latence réseau, un cycle peut apparaître temporairement avant le rejet par le serveur
    • dans ce cas, Figma masque temporairement les éléments inclus dans le cycle et préserve l’état jusqu’au rejet officiel de l’opération par le serveur
    • des explications associées sont disponibles dans l’article multiplayer technology de Figma

Deux approches du CRDT d’arbre déplaçable

  • Au lieu d’une solution centralisée, on peut gérer une structure d’arbre collaborative avec un CRDT
  • Les premiers algorithmes d’arbre fondés sur les CRDT étaient difficiles à implémenter et impliquaient un fort surcoût de stockage, mais avec les optimisations et améliorations, des algorithmes de synchronisation d’arbre adaptés à certains environnements de production ont fini par apparaître
  • Il existe deux approches CRDT représentatives

Approche de Kleppmann : unifier toutes les opérations en Move

  • A highly-available move operation for replicated trees unifie création, suppression et déplacement de l’arbre en une seule opération move
  • L’opération move est définie par quatre valeurs : Move t p m c
    • t : un timestamp unique et ordonnable, comme un Lamport timestamp
    • p : l’ID du nœud parent
    • m : les metadata associées au nœud
    • c : l’ID du nœud enfant
  • Si c n’existe pas dans l’arbre, cela devient une opération de création qui crée l’enfant c sous le parent p
  • Si c existe déjà, cela devient une opération de déplacement qui le transfère de son parent actuel vers le nouveau parent p
  • La suppression est traitée comme un déplacement vers un nœud TRASH désigné
    • tous les sous-nœuds de TRASH sont considérés comme supprimés
    • mais ils restent en mémoire afin que des modifications simultanées puissent déplacer ces nœuds ailleurs
    • ce mécanisme sert à gérer les situations où la suppression d’un ancêtre et le déplacement d’un sous-nœud se produisent en même temps

Ordonnancement et unsafe operation

  • Puisque la suppression est elle aussi définie comme une opération move, le cas « suppression et déplacement du même nœud » devient un conflit entre deux opérations move
  • Il reste alors deux problèmes essentiels
    • déplacer le même nœud sous des parents différents
    • déplacer des nœuds différents pour créer un cycle
  • Si l’on trie linéairement toutes les opérations avec un Lamport timestamp et un Peer ID, même les déplacements simultanés du même nœud sont représentés comme deux opérations ordonnées
  • Lorsqu’on modélise l’arbre uniquement avec des opérations move, les situations exceptionnelles de l’édition simultanée se ramènent à la création de cycles
  • Les opérations qui créent un cycle sont traitées comme des unsafe operations
    • l’algorithme trie toutes les opérations move par ordre de timestamp
    • avant d’appliquer chaque opération, il détecte la présence d’un cycle
    • si elle crée un cycle, l’unsafe operation concernée est ignorée afin de conserver une structure d’arbre valide

Lamport Timestamp et application des opérations distantes

  • Le Lamport Timestamp permet de déterminer l’ordre causal des événements dans un système distribué
    • chaque peer possède un compteur qui commence à 0
    • lorsqu’un événement local se produit, le compteur est incrémenté de 1 et cette valeur sert de timestamp
    • lorsque le peer A envoie un message à B, il y joint le timestamp
    • B compare sa propre horloge logique avec le timestamp reçu et la met à jour avec la plus grande valeur
  • Pour l’ordre global, on compare d’abord le Lamport Timestamp, puis, si les valeurs sont égales, on utilise l’ID unique du peer comme tie-breaker
  • Lorsqu’une mise à jour distante s’insère au milieu de la séquence déjà triée d’opérations, il faut recourir à undo-do-redo
    • annuler les opérations récentes
    • insérer et appliquer la nouvelle opération
    • réappliquer les opérations annulées
  • Pour annuler rapidement une opération move, on met en cache le old parent du nœud cible avant l’application de chaque move
  • Même si l’effet d’une unsafe operation est ignoré, son enregistrement doit être conservé
    • le caractère sûr ou non d’une opération est déterminé dynamiquement
    • si, plus tard, on reçoit une mise à jour qui supprime d’abord un autre nœud à l’origine du cycle, une opération auparavant unsafe peut devenir safe
    • lors du processus d’annulation, un marquage ineffective est nécessaire pour retrouver le parent cible de la dernière opération qui a effectivement eu un effet

Exemple d’undo-do-redo

  • Si une nouvelle opération dépend d’une opération absente en local, la mise à jour d’une version intermédiaire manque encore ; il faut donc la mettre temporairement en cache, puis l’appliquer après réception des mises à jour manquantes.
  • Si le nouvel opId est supérieur à toutes les opérations existantes, il peut être appliqué immédiatement.
    • s’il est safe, on enregistre le parent actuel du nœud cible comme ancien parent, puis on applique le déplacement.
    • s’il est unsafe, on le marque comme ineffective et son effet est ignoré.
  • Si le nouvel opId s’insère au milieu de l’ordre existant, on annule une à une les opérations suivantes, on applique la nouvelle opération, puis on réapplique dans l’ordre les opérations annulées.
  • Dans le flux d’exemple, Peer1 déplace localement C sous B, puis reçoit une opération où Peer0 déplace B sous C.
    • Dans l’ordre des timestamps de Lamport, 0:3 précède 1:3, donc on commence par annuler 1:3 pour remettre C à son ancien parent A.
    • Ensuite, avec 0:3, on déplace B sous C.
    • Puis on refait 1:3 pour tenter de déplacer C sous B, mais un cycle est détecté, donc l’opération n’est pas appliquée.
    • L’état de l’arbre ne change pas et le processus undo-do-redo est terminé.

Méthode d’Evan Wallace : suivi des parents passés

  • CRDT: Mutable Tree Hierarchy d’Evan Wallace fait en sorte que chaque nœud suive tous ses parents passés.
  • Un compteur est associé à chaque parent enregistré.
    • La valeur de count du nouveau parent est supérieure de 1 à tous les count des parents passés de ce nœud.
    • Le parent ayant le count le plus élevé devient le parent actuel.
  • Lors de la synchronisation, l’historique des parents est synchronisé lui aussi.
  • Si un cycle apparaît, un algorithme heuristique rattache le nœud à l’origine du cycle à son parent passé le plus proche qui ne crée pas de cycle et qui est connecté à la racine.
  • Ce processus est répété jusqu’à ce que tous les nœuds cycliques soient de nouveau rattachés à l’arbre, afin de synchroniser la structure d’arbre entre les replicas.
  • Cette approche évite la coûteuse procédure undo-do-redo, mais à chaque réception d’un move distant, il faut vérifier que tous les nœuds sont connectés à la racine et rattacher les nœuds cycliques, ce qui peut dégrader les performances quand le nombre de nœuds est élevé.
  • Un benchmark a été créé séparément pour comparer les performances.

Implémentation du Movable Tree dans Loro

  • Loro implémente l’algorithme de Martin Kleppmann et al., A highly-available move operation for replicated trees.
  • Cet algorithme offre de hautes performances dans la plupart des scénarios réels.
  • Le processus clé d’undo-do-redo est très proche de la manière dont l’Eg-walker (Event Graph Walker) applique les mises à jour distantes dans Loro.
  • Un arbre déplaçable à lui seul ne résout pas le problème de l’ordre entre nœuds frères.
    • Dans des outline notes ou des logiciels de design graphique pour la gestion des calques, il faut ordonner les nœuds enfants.
    • Les utilisateurs doivent pouvoir réorganiser l’ordre des nœuds et synchroniser ce changement avec d’autres collaborateurs ou appareils.
  • Loro intègre l’algorithme Fractional Index pour permettre le tri des nœuds enfants dans un arbre déplaçable.

Fractional Index et conflits d’insertion concurrente

  • Fractional Index attribue à chaque objet une valeur ordonnable.
    • Lorsqu’une nouvelle insertion se produit entre deux objets, le Fractional Index du nouvel objet se situe entre la valeur de gauche et celle de droite.
    • Des explications sont disponibles sur le blog de Figma et le blog d’Evan.
  • Dans un environnement distribué, si plusieurs peers insèrent de nouveaux nœuds au même endroit, des nœuds de contenu différent peuvent recevoir le même Fractional Index.
  • Loro conserve le même Fractional Index, et l’ordre relatif entre indices identiques est déterminé par le PeerID, l’identifiant unique de chaque peer.
  • S’il y a le même Fractional Index des deux côtés, il est impossible de créer un nouveau Fractional Index entre eux.
  • Loro traite ce problème de deux façons.
    • Il ajoute une certaine quantité de jitter aux Fractional Index générés, ce qui réduit fortement la probabilité d’indices identiques.
    • Par exemple, si la valeur entre 0 et 1 est à l’origine 0,5, un jitter aléatoire peut donner des valeurs comme 0.52712, 0.58312 ou 0.52834.
    • S’il faut insérer entre 0.7@A et 0.7@B, on peut réattribuer de nouveaux Fractional Index au nouveau nœud et au nœud 0.7@B dans l’intervalle entre 0.7 et 1.

Taille d’encodage et réglage du jitter

  • Loro utilise l’implémentation Fractional Index basée sur Vec<u8> de drifting-in-space.
  • Cette implémentation est en base 256.
    • Avec la valeur par défaut, il faut continuer à insérer 128 valeurs vers l’avant ou vers l’arrière pour que la taille en octets du Fractional Index augmente de 1.
  • Dans le pire cas, le surcoût de stockage apparaît lorsqu’on insère à chaque fois une nouvelle valeur en alternance.
    • Par exemple, dans ab, on insère c entre a et b, puis d entre c et b, puis e entre c et d.
    • Dans ce cas, une nouvelle opération peut nécessiter un octet supplémentaire, mais cette situation est très rare.
  • Loro ajoute à l’implémentation d’origine une solution simple de jitter.
    • Il ajoute des octets aléatoires à la fin du Fractional Index, selon la longueur de la valeur de jitter.
    • En JavaScript, on peut activer le jitter en passant une valeur positive à doc.setFractionalIndexJitter(number).
    • La taille d’encodage augmente légèrement, avec l’ajout de jitter octets à chaque Fractional Index.
  • La relation entre le jitter et le nombre maximal d’éditions concurrentes n pour éviter les collisions avec une probabilité de 99 % lors de la création d’un Fractional Index au même emplacement est la suivante :
jitter Nombre maximal d’éditions concurrentes
1 3
2 37
3 582
  • De nombreux Fractional Index triés partagent un préfixe commun important.
  • Lors de l’encodage, Loro réduit la taille totale grâce à une optimisation de préfixe qui ne stocke que le nombre de bits de préfixe identiques à la valeur précédente et les octets restants.

Travaux connexes et raisons du choix

  • En plus de Fractional Index, il existe des movable list CRDT capables d’ordonner les nœuds siblings d’un arbre.
  • Moving Elements in List CRDTs de Martin Kleppmann est utilisé dans la Movable List de Loro.
  • La solution Fractional Index est plus simple à implémenter.
  • Lors de la modélisation des nœuds d’arbre, si l’on ne fournit pas une représentation stable de la position pour les nœuds enfants, toute la structure de l’arbre devient excessivement complexe.
  • Fractional Index présente un problème d’interleaving.
    • Dans des cas comme les éléments de calques Figma ou des signets multi-niveaux, où seul l’ordre relatif compte sans nécessiter une sémantique séquentielle stricte, cela reste acceptable.

Résultats des benchmarks

  • Loro a benchmarké son implémentation de Movable Tree sur des déplacements aléatoires de nœuds, des bascules vers des versions passées et des conditions extrêmes avec des structures d’arbre très profondes
  • Les résultats sont suffisants pour prendre en charge la collaboration en temps réel et un checkout fluide des versions passées
  • L’environnement de test utilise un CPU M2 Max, et le code du benchmark est disponible dans tree.rs
Tâche Temps Configuration
10 000 déplacements aléatoires 28 ms Créer d’abord 1 000 nœuds
1 000 bascules vers différentes versions 153 ms Créer d’abord 1 000 nœuds puis effectuer 1 000 déplacements
1 000 bascules vers différentes versions dans un arbre de profondeur 300 701 ms Chaque nouveau nœud est l’enfant du nœud précédent

Exemples d’utilisation et démo

  • LoroTree de loro-crdt fournit la création de nœuds, la création avec positionnement, le déplacement, le déplacement vers la racine, le déplacement avant ou après un autre nœud, la consultation de l’index dans le parent, la consultation du Fractional Index et l’accès à la data map du nœud
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";

let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
  • Une démo d’application Todo simulant la synchronisation des données entre plusieurs pairs avec Loro a été créée
    • Movable Tree représente les relations de sous-tâches
    • Map représente diverses propriétés de la tâche
    • Text représente le titre de la tâche
    • En plus de la création, du déplacement, de la modification et de la suppression, la bascule de versions basée sur Loro a également été implémentée
    • Il est possible de faire glisser la scrollbar pour passer entre toutes les versions passées enregistrées

En résumé

  • L’implémentation d’un tree CRDT déplaçable est difficile en raison des déplacements concurrents, des suppressions, des cycles, ainsi que des combinaisons entre suppression d’ancêtres et déplacement de descendants
  • Loro implémente les déplacements dans la hiérarchie de l’arbre avec l’algorithme de move à haute disponibilité de Kleppmann et al.
  • Les déplacements et le tri entre nœuds enfants sont gérés en intégrant l’implémentation du Fractional Index de drifting-in-space
  • Cette combinaison peut répondre aux besoins de divers scénarios d’applications collaboratives

À lire aussi

1 commentaires

 
GN⁺ 2024-07-30
Commentaires Hacker News

  • Je suis en train de créer un nouveau éditeur multijoueur [1] pour les tâches/notes, qui prend en charge à la fois les opérations sur le texte et sur un outliner.
    En surface, il se comporte comme un document texte plat, mais avec les fonctions d’outliner, c’est en interne un grand arbre. Pour la synchronisation des changements, on utilise une approche proche des opérations de déplacement à haute disponibilité. Il n’y a qu’une seule opération qui modifie l’arbre, insmov, et quand le client est en ligne, il synchronise l’ensemble de changements C avec le serveur. Si le serveur a des changements distants, il renvoie tous les changements R depuis la dernière synchronisation dans un ordre linéaire global, annule les insmov des changements locaux C, puis réapplique R ainsi que les nouveaux changements qui n’ont pas encore été synchronisés.
    On n’utilise pas d’index fractionnaires ; le tuple insmov inclut non seulement le parent P, mais aussi le guid A du frère précédent. Comme toutes les opérations sur l’arbre sont finalement appliquées dans l’ordre linéaire global défini par le serveur, le tri est géré par l’opération insmov elle-même. La plupart du temps, il n’est pas nécessaire d’annuler quoi que ce soit ; il faut rejouer dans le bon ordre uniquement lorsque le serveur contient un changement insmov que je ne connais pas au moment même où j’envoie un nouveau insmov. Cela peut arriver quand on se reconnecte au Wi-Fi après un long vol, mais c’est moins fréquent quand on est en ligne et qu’on reçoit des push en temps réel via WebSocket, et ce n’est pas nécessaire pour les opérations non-insmov comme les mises à jour de texte.
    [1] https://thymer.com

    • Cette approche semble équivalente à un CRDT de liste RGA [1] utilisant l’ordre linéaire global du serveur comme horodatage logique.
      Par exemple, ce serait une variante qui utilise l’ordre du serveur au lieu d’horodatages de Lamport.
      [1] https://inria.hal.science/inria-00555588/
    • Hier, je lisais par hasard un vieux fil [0] et un commentaire sur Thymer a éveillé mon intérêt.
      En cherchant Thymer sur HN, je suis tombé sur un Show HN de 2009 [1], et on dirait que Thymer est en bêta privée depuis 15 ans.
      0. https://news.ycombinator.com/item?id=40786425
      1. https://news.ycombinator.com/item?id=518803
    • Je me demande quel texte riche il utilise.

  • Il faut vraiment que je lise cet article. Dans le cadre d’une mission freelance pour un client, j’ai publié en open source React Table Library [0], en mettant l’accent sur les opérations sur les arbres.
    Ils manipulent des structures d’arbres de dossiers/fichiers de l’ordre de 100 000 nœuds, avec déplacement et duplication de dossiers et de fichiers, chargement paresseux aux niveaux racine et imbriqués, le tout dans la même structure de table. Après avoir terminé le projet, j’ai compris pourquoi Google Drive n’autorise l’affichage et l’édition qu’au même niveau hiérarchique. Implémenter cela dans une vue imbriquée avec beaucoup de nœuds impose tout simplement trop de contraintes à prendre en compte.
    [0] https://react-table-library.com/

    • Ça a l’air bien ; je me demande quand ce sera entièrement headless.

  • J’aimerais demander conseil. Ce n’est pas une application multijoueur, mais côté frontend nous avons de grands arbres dénormalisés interconnectés utilisés comme profils utilisateur.
    On peut imaginer une structure de type mise en page en tuiles, où l’utilisateur ajoute/supprime/redimensionne des tuiles, ajoute plusieurs composants à chaque emplacement de tuile, et ces composants ont chacun leur propre profil. Il peut exister plusieurs layouts avec différents agencements de tuiles, et il y a aussi la complexité de tuiles individuelles qui référencent ou partagent d’autres morceaux de l’état global.
    C’est difficile à mettre à jour de façon sûre avec du REST classique. Il faut garantir que si le même utilisateur ouvre deux onglets, fait une mise à jour dans l’onglet 1 puis une autre dans l’onglet 2, l’ensemble du profil ne se retrouve pas dans un état invalide. Globalement, l’ordre compte aussi. Si le serveur saute une mise à jour correctement appliquée côté client, ça peut casser.
    Comme solution très simple, nous avons envoyé le minimum de données permettant d’écraser complètement un fragment d’état donné, puis nous l’avons mis en file d’attente. En général ça va, mais il arrive qu’on envoie 50 Ko alors que le changement réel ne fait que quelques octets, ce qui crée du gaspillage.
    Nous n’avons pas les raisons habituelles d’avoir besoin de CRDT, mais même pour un seul utilisateur, j’ai l’impression que la gestion d’état deviendrait beaucoup plus simple. D’abord, cela synchroniserait les onglets du navigateur de l’utilisateur ; surtout, je pourrais faire une simple modification de l’état frontend et faire confiance au CRDT pour la coordonner correctement avec le serveur. Je n’aurais plus à le gérer moi-même. Je me demande si cela a du sens, ou si, sans besoin de multijoueur ni de local-first, ajouter quelque chose comme Yjs représente un overhead qui n’en vaut pas la peine.

    • Si l’application utilise activement plusieurs onglets, employer quelque chose comme YJS peut avoir du sens, car c’est très efficace pour résoudre ce type de problème.
      Cela dit, si l’édition de profil est réservée à un seul utilisateur, introduire un CRDT me semble excessif. À première vue, le scénario avec deux onglets ouverts est la principale source de bugs ; on peut donc utiliser BroadcastChannel pour notifier les événements de mise à jour à tous les autres onglets.
    • Pour ce cas d’usage, un CRDT me semble approprié.
      Maintenir un état partagé au moyen d’appels REST qui écrasent une partie de l’état serveur est en réalité fragile, et ne convient guère qu’à l’écrasement de champs dans des enregistrements de données plats. En outre, la coordination de l’état serveur-client doit toujours être envisagée avec soin, et les chemins hors du flux normal se désynchronisent facilement.
      Comme vous le dites, créer un CRDT qui explicite la manière dont les mises à jour se fusionnent réduirait fortement la charge cognitive.

  • Dans les contenus de texte enrichi comme Google Docs ou Zoho Writer, les opérations consistant à déplacer un élément de liste vers le bas, à ajouter une nouvelle colonne, ou les opérations sur des tableaux/listes sont intrinsèquement des opérations de manipulation d’arbre.
    Les conflits concurrents dans ce type de cas sont notoirement difficiles à faire converger sans traitement spécifique au contexte [1]. Je me demande si cette implémentation fournit aussi une solution généralisée pour ces cas d’usage.
    On pourrait probablement utiliser un CRDT de liste ou de chaîne pour les nœuds feuilles, c’est-à-dire les blocs de texte, et combiner ce CRDT d’arbre pour les nœuds structurels que sont les listes et les tableaux. Mais dans ce cas, il faut ajouter à toutes les opérations une adresse bidimensionnelle (parent-id, index_offset_into_that_parent).
    [1] https://github.com/inkandswitch/peritext/issues/27

    • C’est ainsi que je l’ai toujours imaginé. Le texte riche ajoute deux choses au texte brut : des plages d’annotation, comme une portion en gras, et des éléments non textuels, comme des tableaux ou des images intégrées.
      Un CRDT de texte n’est fondamentalement qu’un CRDT de liste contenant des données caractères. Un élément intégré peut donc facilement être modélisé comme un élément spécial de taille 1, comme n’importe quel autre élément de la chaîne, c’est-à-dire comme un nœud enfant intégré. Avec la bonne approche, on peut mélanger différents CRDT dans l’arbre selon les besoins. Par exemple, un tableau dans du texte riche, avec une image dans l’une de ses cellules.
      Ajouter un champ parent-crdt-id à toutes les opérations est regrettable, mais semble difficile à éviter. Heureusement, dans la plupart des cas d’usage réels, il sera probablement très courant que des opérations consécutives partagent le même CRDT parent, si bien que ce champ d’ID devrait bien se compresser par codage par plages.
    • En pratique, l’implémentation permet effectivement de combiner plusieurs types de CRDT. Dans l’implémentation interne de Loro, chaque opération doit stocker l’ID du parent.
      Cela dit, comme Seph l’a indiqué, les opérations consécutives sous le même parent peuvent être compressées efficacement, donc le surcoût amorti de ces ID de parent n’est généralement pas très important.

  • Je me demande s’il a existé des CRDT pratiques pour des applications à forte densité de données, comme les pixels d’une image ou les modèles 3D.

    • Dans les applications collaboratives, il faut d’abord définir un cadre conceptuel pour les modifications que les utilisateurs vont effectuer, ainsi que la meilleure façon de préserver l’intention de l’utilisateur et la cohérence du document résultat lorsque ces modifications se produisent de manière asynchrone.
      Même si la représentation concrète du document est gourmande en données, la manière d’encoder les modifications et opérations individuelles de l’utilisateur peut rester compacte.
      Supposons que l’on crée un éditeur d’images comme Photoshop : une image non compressée de 102 millions de pixels avec une profondeur de couleur de 16 bits par canal, par exemple une photo Fujifilm GFX100, représente environ 610 Mo en TIFF. Représenter chaque pixel comme un registre distinct en last-write-wins entraînerait un gros surcoût, mais cette représentation ne correspond pas vraiment à la préservation de l’intention de l’utilisateur. Les modifications que l’utilisateur effectuera sont plutôt du type « augmenter le contraste de l’image de 15 % » ou « peindre la spline [(0,0), (1500, 1500)] avec la brosse Q et la couleur #000 ». Si chaque pixel est synchronisé avec un timestamp de Lamport, le changement de contraste de l’utilisateur 1 s’appliquera à tous les pixels sauf ceux peints par l’utilisateur 2, ce qui peut donner un aspect étrange aux pixels repeints.
      Il vaut mieux représenter l’intention de l’utilisateur sous forme de liste d’opérations d’édition. C’est beaucoup plus petit que toute la grille de pixels de 102 Mo. Les structures de données CRDT sont l’un des mécanismes techniques possibles pour synchroniser cette intention utilisateur, mais la structure doit être choisie en fonction de la sémantique de l’intention utilisateur, pas de la disposition concrète des données en sortie.
      Il peut tout de même y avoir des opérations d’édition contenant de grandes quantités de données, comme "add new layer named bgbelow layerfgwith pixelsdata:(10mb of pixels) at (1500, 1500)". Mais le surcoût de synchronisation de ce type de commande d’édition est très faible, et sa taille est en O(1), pas en O(pixels) proportionnellement au nombre de pixels contenus dans la commande.
    • Ce n’est pas exactement la même chose, mais Figma prend en charge l’édition concurrente et, à ma connaissance, utilise une approche proche des CRDT (https://www.figma.com/blog/how-figmas-multiplayer-technology...)
    • Pour l’édition d’images, tous les conflits de modification peuvent être facilement résolus en last writer wins, donc je ne sais pas si un CRDT est vraiment nécessaire.
      Les modèles 3D sont un autre problème, et je n’ai pas vu d’outil de modélisation 3D collaborative sur le marché. Je n’ai pas non plus cherché activement.
    • J’avais esquissé dans un long article sur les CRDT ce à quoi pourrait ressembler un CRDT basé sur les pixels performant : http://archagon.net/blog/2018/03/24/data-laced-with-history/...
      Je ne l’ai pas construit moi-même, et je ne suis pas sûr qu’il soit réellement pratique. Mais au moins, il permettrait de préserver tout l’historique du document.
    • Le bel exemple que j’ai vu est Modyfi, un éditeur non destructif pour graphismes raster.
      Il représente les données avec Yjs, mais au lieu de stocker les pixels bruts, il stocke l’historique complet des transformations.
      https://digest.browsertech.com/archive/browsertech-digest-ho...

  • Je me demande si le texte a été vérifié avec GPT. Dans le premier paragraphe, je sens fortement un style ChatGPT.

    • Ça ne semble pas être le cas. Ce type d’erreur grammaticale ne ressemble pas à ChatGPT :
      This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.