Les CRDT d’arbres déplaçables et l’implémentation de Loro

• Movable tree CRDTs and Loro's implementation

• Contexte

  • Gérer des relations hiérarchiques dans les systèmes distribués et les logiciels collaboratifs est complexe
  • Lorsqu’on modélise un déplacement en combinant suppression et insertion dans une structure de données, il est difficile de résoudre les conflits tout en répondant aux attentes des utilisateurs
  • Par exemple, si le même nœud est déplacé simultanément vers des parents différents, des nœuds dupliqués avec le même contenu peuvent être créés

• Conflits dans les arbres déplaçables

  • Principales opérations d’un arbre déplaçable : création, suppression, déplacement
  • Conflits possibles lors de la synchronisation d’opérations concurrentes :
    • le même nœud est supprimé et déplacé
    • le même nœud est déplacé sous un autre nœud
    • d’autres nœuds sont déplacés, provoquant un cycle
    • un nœud descendant est déplacé pendant qu’un nœud ancêtre est supprimé

• Suppression et déplacement du même nœud

  • Relativement facile à résoudre
  • Selon les timestamps du système distribué ou les exigences spécifiques de l’application, une opération est appliquée et l’autre ignorée

• Déplacement du même nœud sous des parents différents

  • La fusion d’opérations de déplacement concurrentes est plus complexe
  • Selon l’application, différentes approches peuvent être adoptées :
    • supprimer le nœud et créer une copie sous un autre nœud parent
    • autoriser le nœud à être lié à deux parents (ce qui n’est généralement pas permis)
    • ordonner toutes les opérations et les appliquer séquentiellement

• Cycles provoqués par le déplacement d’autres nœuds

  • Résoudre les cycles causés par des opérations de déplacement concurrentes est complexe
  • Plusieurs solutions existent :
    • générer une erreur
    • afficher les nœuds cycliques dans une zone spéciale de "timeout"
    • traiter les opérations de déplacement sur le serveur
    • utiliser un tri topologique
    • masquer l’arête qui provoque le cycle

• Suppression d’un nœud ancêtre et déplacement d’un nœud descendant

  • Le déplacement d’un nœud descendant lors de la suppression d’un nœud ancêtre peut facilement être négligé
  • Supprimer directement tous les nœuds descendants peut être perçu comme une perte de données

• Gestion des conflits dans des applications populaires

  • Dropbox : traitait le déplacement de fichiers comme une suppression suivie d’une création, mais avec un risque de perte de données
  • Figma : un serveur central détecte les cycles et rejette les opérations afin de préserver la cohérence

• CRDT d’arbres déplaçables

  • Utilisation de CRDT plutôt que de solutions centralisées
  • Les premiers algorithmes basés sur les CRDT étaient difficiles à implémenter et impliquaient un surcoût de stockage important
  • Des optimisations continues ont rendu certains algorithmes de synchronisation d’arbres basés sur les CRDT adaptés à la production

• Opérations de déplacement à haute disponibilité pour les arbres répliqués

  • Les trois opérations de l’arbre (création, suppression, déplacement) sont unifiées en une opération de déplacement
  • L’opération de déplacement est définie comme Move t p m c
  • La suppression d’un nœud est gérée en le déplaçant vers un nœud TRASH

• Timestamps logiques globalement ordonnés

  • Utilisation des timestamps de Lamport pour déterminer l’ordre causal des événements dans un système distribué
  • Un plus petit nombre indique un événement plus ancien

• Application des opérations distantes

  • La sûreté d’une opération dépend de l’état de l’arbre au moment de son application
  • Lors du traitement de mises à jour distantes, on annule les opérations récentes, on insère la nouvelle, puis on réapplique celles qui ont été annulées

• CRDT : hiérarchie d’arbre mutable

  • Chaque nœud suit tous ses parents historiques et leur attribue un compteur
  • Si un cycle apparaît lors de la synchronisation, le nœud est reconnecté à son parent historique le plus proche

• Implémentation des CRDT d’arbres déplaçables dans Loro

  • L’algorithme de Martin Kleppmann est implémenté pour offrir de hautes performances
  • L’algorithme Fractional Index est intégré pour permettre le tri des nœuds enfants

• Conflits potentiels dans l’ordonnancement des nœuds enfants

  • Lors de l’insertion de plusieurs nœuds à la même position, le même Fractional Index peut leur être attribué
  • PeerID est utilisé pour déterminer l’ordre relatif entre des Fractional Index identiques

• Implémentation et taille d’encodage

  • Fractional Index fournit l’ordre des nœuds
  • En pire cas, la taille d’encodage peut nécessiter des octets supplémentaires, mais cela reste rare

• Travaux liés

  • En plus de Fractional Index, il existe aussi des CRDT de listes déplaçables
  • Fractional Index est simple à implémenter et utile lorsqu’on n’a besoin que d’un ordre relatif

• Benchmarks

  • Des benchmarks ont été réalisés sur les performances de l’implémentation d’arbre déplaçable de Loro
  • Elle peut prendre en charge la collaboration en temps réel et un passage fluide entre versions historiques

• Résumé

  • Présentation des difficultés d’implémentation des CRDT d’arbres déplaçables et de deux algorithmes innovants
  • Loro combine l’algorithme de Martin Kleppmann et Fractional Index pour répondre à divers scénarios applicatifs

• Résumé de GN⁺

  • Les CRDT d’arbres déplaçables jouent un rôle important dans la gestion de structures de données hiérarchiques dans les systèmes distribués
  • Loro offre de hautes performances et une résolution efficace des conflits, ce qui le rend adapté aux applications de collaboration en temps réel
  • L’utilisation de Fractional Index permet de résoudre les problèmes d’ordonnancement des nœuds enfants
  • Parmi les autres projets dotés de fonctionnalités similaires figurent Figma et Dropbox

[GN⁺]

Commentaire Hacker News

• Je développe un nouvel éditeur multijoueur

  • Il prend en charge le texte et les opérations d'outliner
  • Les documents sont transformés en une grande structure arborescente
  • La synchronisation se fait à l'aide d'opérations insmov (déplacement ou insertion)
  • Quand le serveur envoie des modifications, le client les réapplique
  • Dans la plupart des cas, il n'est pas nécessaire d'annuler les opérations
  • Il y a rarement des problèmes lors des mises à jour en temps réel

• Je propose React Table Library en open source

  • Il gère des structures arborescentes de dossiers/fichiers
  • Il prend en charge le déplacement, la copie et le chargement différé des dossiers/fichiers
  • Cela m'a permis de comprendre pourquoi Google Drive n'affiche et ne modifie les éléments qu'au même niveau hiérarchique

• Je demande des conseils

  • J'utilise un grand arbre dénormalisé dans le frontend
  • Je gère des profils utilisateurs avec une disposition en tuiles
  • J'envoie le minimum de données pour garantir des mises à jour sûres
  • J'ai l'impression qu'utiliser des CRDT rendrait la gestion d'état bien plus simple
  • Cela permettrait aussi la synchronisation entre onglets du navigateur

• Pour du contenu textuel formaté comme dans Google Docs/Zoho Writer, des manipulations d'arbre sont nécessaires

  • Il est difficile de résoudre les problèmes de conflits concurrents
  • Il semble possible de combiner des CRDT de liste et des CRDT d'arbre
  • Il faudrait ajouter une adresse bidimensionnelle à chaque opération

• Je me demande s'il existe des CRDT pratiques pour des applications gourmandes en données, comme les images (pixels) et les modèles 3D

• Je pense que le premier paragraphe ressemble à la voix de ChatGPT