Les types de données répliquées sans conflit (CRDT) sont une classe de structures de données qui permettent une collaboration et une synchronisation transparentes des données dans des systèmes distribués, permettant des mises à jour collaboratives sans conflit. Les CRDT sont conçus pour assurer une cohérence éventuelle entre plusieurs répliques de données, garantissant que même lorsque les mises à jour se produisent indépendamment, toutes les répliques convergent vers le même état sans nécessiter de mécanismes complexes de résolution de conflits.

Dans cet article de blog, nous examinerons ce que sont les CRDT, explorerons leurs utilisations et leurs types, comprendrons leur fonctionnement et apprendrons comment les implémenter, en mettant l'accent sur JavaScript et la puissante bibliothèque Yjs.

Cas d'utilisation des CRDT

Les CRDT sont particulièrement utiles dans les scénarios où la collaboration en temps réel et l'assistance hors ligne sont cruciales :

1. Éditeurs de texte collaboratifs : Google Docs, Notion et Etherpad utilisent des structures de type CRDT pour l'édition en temps réel.
2. Outils de conception collaborative : Figma, un outil de conception Web populaire, utilise les CRDT pour permettre une collaboration en temps réel sur des projets de conception. Plusieurs concepteurs peuvent travailler simultanément sur le même fichier, les modifications étant synchronisées de manière transparente entre tous les utilisateurs.
3. Bases de données distribuées : RxDB et Riak utilisent des CRDT pour une réplication sans conflit.
4. Jeux multijoueurs : pour maintenir un état de jeu cohérent entre les joueurs.

Types de CRDT

Il existe deux principaux types de CRDT :

1. CRDT basés sur l'état : ceux-ci reproduisent l'intégralité de l'état de la structure de données. La fusion s'effectue en comparant et en réconciliant les états des différentes répliques.
2. CRDT basés sur les opérations : ceux-ci répliquent les opérations effectuées sur la structure de données. La fusion s'effectue en appliquant les opérations de différentes répliques de manière commutative.

Comment fonctionnent les CRDT

Les CRDT (Conflict-free Replicated Data Types) fonctionnent selon des principes qui garantissent une cohérence éventuelle entre toutes les répliques des données, même lorsque les mises à jour sont effectuées simultanément ou lorsque des partitions réseau se produisent. Approfondissons les mécanismes :

Propriétés clés

1. Commutativité : Cette propriété garantit que l'ordre des opérations n'affecte pas le résultat final. Par exemple, dans un compteur CRDT, incrémenter de 2 puis de 3 donne le même résultat qu'incrémenter de 3 puis de 2.
2. Associativité : Cela signifie que le regroupement des opérations n'a pas d'importance. En reprenant le contre-exemple, (1 2) 3 est identique à 1 (2 3).
3. Idempotence : appliquer plusieurs fois la même opération a le même effet que l'appliquer une seule fois. Ceci est crucial pour gérer les messages en double dans les systèmes distribués.

Résolution des conflits

Les CRDT résolvent automatiquement les conflits dès leur conception :

• Pour les CRDT basés sur l'état (CvRDT), ceci est réalisé grâce à une fonction de fusion qui combine les états de deux répliques. Cette fonction de fusion doit être commutative, associative et idempotente.
• Pour les CRDT basés sur les opérations (CmRDT), les opérations sont conçues pour être commutatives, garantissant que leur application dans n'importe quel ordre conduit au même état final.

Horloges logiques

De nombreuses implémentations de CRDT utilisent des horloges logiques (telles que des vecteurs de version ou des vecteurs de version pointés) pour suivre l'historique causal des opérations. Cela aide à déterminer l'ordre des opérations simultanées et à identifier les mises à jour qu'une réplique a déjà vues.

Utiliser des CRDT en JavaScript avec Yjs

La mise en œuvre de CRDT à partir de zéro peut être complexe. Cependant, il existe des bibliothèques disponibles qui simplifient le processus. Pour JavaScript, l'une des bibliothèques CRDT les plus populaires est Yjs. Il s'agit d'une implémentation CRDT hautes performances qui prend en charge différents types de données. Créons une application simple de liste de tâches à l'aide de Yjs, simulant plusieurs utilisateurs travaillant sur le même document en mémoire.

Voici un exemple de mise en œuvre d'une liste de tâches partagée à l'aide de Yjs :

Utilisons les ydocs créés :

Dans cet exemple, nous créons deux documents Yjs (ydoc1 et ydoc2) pour simuler deux utilisateurs travaillant sur la même liste de tâches. Chaque document possède sa propre carte partagée pour les tâches.

Nous définissons des fonctions pour ajouter, mettre à jour et supprimer des tâches, ainsi qu'une fonction syncDocs pour synchroniser manuellement l'état entre les deux documents. Cela simule ce qui se passerait dans un environnement en réseau où les mises à jour sont échangées entre les clients.

Conclusion

Les CRDT offrent une solution puissante pour créer des applications collaboratives et distribuées qui peuvent fonctionner de manière transparente en ligne et hors ligne. Bien que les concepts sous-jacents puissent être complexes, les bibliothèques comme Yjs permettent aux développeurs d'exploiter plus facilement la puissance des CRDT dans leurs applications. À mesure que les systèmes distribués deviennent plus répandus, la compréhension et l'utilisation des CRDT deviendront une compétence de plus en plus précieuse pour les développeurs.

Liens utiles

1. Yjs
2. CRDT
3. Tiptap - Un éditeur de texte collaboratif