Dictionnaire des CRDT : guide pratique des structures de données distribuées

• Les CRDT (Conflict-free Replicated Data Types) sont des structures de données distribuées qui permettent une fusion cohérente des données sans coordination, même en cas de partition réseau ou de modifications simultanées
• Si la fusion des données respecte la commutativité, l’associativité et l’idempotence, toutes les répliques convergent finalement vers le même état
• Parmi les formes représentatives figurent G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot, chacun répondant à des besoins différents en matière d’ajout, suppression, réajout et maintien de l’ordre
• Les Delta CRDT améliorent l’efficacité en transmettant uniquement les changements plutôt que l’état complet, et la garbage collection est un enjeu clé pour résoudre l’accumulation de métadonnées
• Les CRDT ne sont pas une solution parfaite, mais ils sont considérés comme une option puissante dans les systèmes où la disponibilité est plus importante que la cohérence immédiate

---

Concepts de base des CRDT

• Les CRDT sont des structures de données capables d’être fusionnées sans coordination, même lorsque des modifications concurrentes surviennent dans un environnement distribué
  • Si l’opération de fusion est commutative, associative et idempotente, toutes les répliques convergent vers le même état
• Ils reposent sur la notion de lattice (treillis), avec une conception où l’état ne se déplace que « vers le haut »
  • Exemple : un G-Counter fusionne les compteurs de chaque réplique avec max, garantissant une agrégation sans perte
• Il existe deux approches de CRDT : State-based (CvRDT) et Operation-based (CmRDT)
  • CvRDT fusionne l’état complet, CmRDT propage les opérations

Principaux types de CRDT

• G-Counter : compteur qui ne peut qu’augmenter, avec agrégation de la valeur de chaque réplique
• PN-Counter : combine un G-Counter pour les incréments et un autre pour les décréments afin de prendre en charge un comptage bidirectionnel
• G-Set : ensemble dans lequel on ne peut qu’ajouter
• 2P-Set : ajout et suppression possibles, mais sans réajout
• LWW-Element-Set : basé sur des timestamps, où l’opération la plus récente l’emporte
• OR-Set : utilise des tags uniques pour fusionner sans perte de données lors d’ajouts concurrents, avec un comportement add-wins
• LWW-Register / MV-Register : pour stocker une valeur unique ; LWW choisit un seul gagnant, MV conserve toutes les valeurs concurrentes
• OR-Map : structure de type map qui combine un OR-Set pour chaque clé
• RGA / WOOT / Logoot / LSEQ : CRDT pour des données de séquence ordonnées
  • RGA est basé sur un arbre, WOOT sur des références bidirectionnelles, Logoot/LSEQ sur des identifiants de position

Concepts avancés des CRDT

• Causal CRDTs : utilisent des vecteurs de version pour suivre les relations causales, permettant une détection des conflits plus précise
• Delta CRDTs : n’envoient que les changements (delta) au lieu de l’état complet, ce qui améliore l’efficacité réseau
• Tree CRDTs : prennent en charge la réplication de données hiérarchiques (comme les systèmes de fichiers), avec maintien des relations parent-enfant
• Observed-Remove Shopping Cart : exemple de panier e-commerce combinant OR-Set et PN-Counter

Problème de garbage collection

• Les CRDT accumulent continuellement des métadonnées pour assurer la convergence, ce qui entraîne un problème de croissance infinie
  • Exemple : les tags d’un OR-Set, les tombstones d’un RGA
• Il existe diverses stratégies : expiration basée sur le temps, suppression fondée sur le consensus, suivi causal via vecteurs de version, plafonnement des métadonnées, checkpoint/rebase, etc.
• Chaque approche implique un compromis entre sécurité (éviter la résurrection de zombies) et efficacité de l’espace

Performances et guide de choix

• La complexité en espace et en temps varie selon le type de CRDT en fonction du nombre de répliques, d’éléments, de tags, etc.
  • Les G/PN-Counter sont proportionnels au nombre de répliques, les OR-Set au nombre de tags, les RGA accumulent des tombstones
• Les Delta CRDT améliorent fortement les performances de fusion
• Critères de choix :
  • Ajout uniquement → G-Counter, G-Set
  • Suppression nécessaire, sans besoin de réajout → 2P-Set
  • LWW acceptable → LWW-Set/Register
  • Préserver les modifications concurrentes → OR-Set, MV-Register
  • Besoin de conserver l’ordre → RGA, Logoot
  • Structure imbriquée → OR-Map

Conclusion

• Les CRDT garantissent une convergence sans coordination, mais présentent l’inconvénient de la croissance des métadonnées et de la complexité
• Ils sont utiles dans les systèmes où la disponibilité prime, et chaque CRDT est optimisé pour un type de problème spécifique
• En pratique, ils sont utilisés en parallèle des bases de données traditionnelles, et une stratégie de garbage collection est indispensable
• Il n’existe pas de « CRDT parfait » : l’essentiel est de choisir en fonction des besoins de l’application

[GN⁺]

Discussion sur Hacker News

• L’un des aspects intéressants des CRDT est que ce n’est pas simplement une bibliothèque combinant plusieurs CRDT de bas niveau
  Par exemple, Automerge est en lui-même un CRDT complet, et des preuves mathématiques garantissent sa cohérence même en présence de concurrence
  L’équipe d’Automerge vérifie sa conception avec des outils de démonstration de théorèmes comme Isabelle, et vise une implémentation rapide et correcte en appliquant les techniques de performance les plus récentes du monde des bases de données
  Si vous créez un SaaS de collaboration en temps réel (par ex. Notion, Figma), vous pouvez appliquer immédiatement des structures de données collaboratives sans devoir maîtriser la théorie complexe
  Un simple stockage key-value suffit côté back-end, et une seule bibliothèque suffit côté front-end

  • Automerge fournit d’excellentes API non seulement en Rust, mais aussi en Javascript et en C
    J’ai moi-même créé une bibliothèque automerge basée sur Redis, et j’ai pu implémenter un serveur complet de synchronisation persistante en utilisant pub/sub
    J’ai aussi rapidement finalisé une démo de synchronisation de documents entre plusieurs navigateurs grâce à la fonctionnalité websocket de Webdis
  • Automerge est excellent, mais cela donne encore l’impression d’une approche très académique
    Si vous voulez une meilleure DX et une base de données full-stack fondée sur les CRDT, je recommande Triplit.dev. Le rythme de développement a un peu ralenti, mais le produit est déjà suffisamment abouti
  • Le fait qu’Automerge soit un CRDT complet n’a rien de surprenant
    Personnellement, j’aime aussi Loro, mais sa structure reste orientée document, donc il lui manque un moteur de requête. Pour obtenir les données voulues, il faut désigner directement certains éléments imbriqués
  • Le fait qu’Automerge ne prenne pas en charge l’auto-hébergement est une contrainte rédhibitoire pour beaucoup d’applications

• C’était un bon article, bien structuré, depuis les bases des CRDT jusqu’aux concepts avancés
  À noter que Riak est toujours maintenu sous la forme de OpenRiak

  • Je découvre OpenRiak, et ça me fait plaisir de voir que d’anciens collègues y participent. Basho était vraiment un groupe d’ingénieurs exceptionnel

• J’ai développé des CRDT moi-même ces deux dernières années, mais j’ai fini par constater qu’il y avait trop de trade-offs, et je suis finalement passé à un framework OT basé sur des ID
  Je prévois de lancer Docnode.dev ce mardi. Je serais ravi d’avoir des retours
  À l’avenir, je compte aussi ajouter un mode CRDT pour les cas où le P2P est nécessaire

  • Je serais curieux de savoir quels trade-offs ont été les plus problématiques

• Les CRDT et l’OT visent à résoudre les cas où des personnes modifient simultanément le même paragraphe, mais en pratique ce genre de situation arrive très rarement

  • Mais les systèmes dépourvus de cette fonctionnalité finissent souvent avec des curseurs qui se chevauchent dans la même phrase, ce qui entraîne des pertes de contenu ou une perte de temps

• L’OR-Set mentionné dans cet article ressemble à une ancienne stratégie de fusion utilisée par Monotone depuis 2005
  On peut voir des informations à ce sujet dans la documentation de MarkMerge

• Les CRDT restent encore un domaine où il faut souvent tout implémenter soi-même
  Moi aussi, il y a deux mois, j’ai créé un moteur CRDT basé sur des séquences, inspiré de diamond types
  J’ai demandé de l’aide à l’IA, mais elle n’a été d’aucune utilité sur ce type de problèmes centrés sur la logique
  J’ai l’impression qu’il faudrait des tests en boîte noire pour vérifier si un LLM peut comprendre une logique nouvelle

  • Je me demande ce que ça donnerait de simplement utiliser quelque chose comme Loro

• L’article était excellent, mais je pense qu’un glossaire devrait absolument inclure un index

• Je me demande si les CRDT ne reviennent pas au fond à déplacer les conflits de fusion de la base de données vers la logique applicative

  • Les CRDT peuvent aussi être conçus à l’intérieur de la base de données. C’était précisément l’objectif de Riak
    S’ils sont correctement écrits, une résolution automatique des fusions est possible quel que soit le niveau où ils se trouvent
  • Je réfléchis moi aussi à une base de données graphe dans PostgreSQL appliquant des techniques de CRDT
    Le plus gros problème concernait la gestion des conflits sur UNIQUE/PRIMARY KEY
    On peut résoudre cela en attribuant à chaque serveur un espace de noms d’ID, en faisant gagner la première création, puis en renommant ou supprimant en cas de conflit
    Avec un schéma EAV, il est facile d’implémenter l’exploration de graphe en SQL avec des CTE récursives
    En revanche, PostgreSQL n’a pas de type ANY, ce qui complique la représentation d’objets aux attributs variés, et les FOREIGN KEY doivent aussi être implémentées manuellement
    Malgré cela, la structure EAV est avantageuse pour la conception de méta-schémas comme l’héritage
    Ce serait bien de pouvoir définir directement des types CRDT dans PostgreSQL, mais pour l’instant il n’est pas possible d’imposer des restrictions sur les opérations de monoïde
    Au final, les CRDT pour les colonnes non-clés doivent être gérés dans la couche applicative
    En résumé, on peut implémenter des CRDT dans un SGBDR, mais l’approche varie selon l’endroit où l’on place la logique métier