Un type de données répliqué sans conflit (Conflict-Free Replicated Data Type, abrégé CRDT) est une structure de données conçue pour permettre à un système distribué de maintenir plusieurs réplicas de données sans nécessiter de synchronisation, tout en garantissant une cohérence éventuelle forte.
Ce type de donnée est employé pour représenter un état mutable partagé entre plusieurs réplicas. Chaque réplica peut mettre à jour son état de manière indépendante, sans synchronisation, par rapport aux autres, tout en étant assuré de converger vers un état correct commun sans conflits. Les caractéristiques fondamentales des CRDT reposent sur la notion de demi-treillis, issu de la théorie des ordres, et ont été formellement établies par Marc Shapiro, Nuno Preguiça, Carlos Baquero et Marek Zawirski en 2011.
Les CRDT sont utilisés dans des applications concrètes comme les éditeurs collaboratifs en temps réel. Ils permettent une collaboration fluide sans impact sur la cohérence des données, malgré une latence élevée du réseau, des pannes ou des déconnexions.
Méthodes de réplication
Il existe deux approches distinctes de réplication pour les types de données répliqué sans conflit, les classifiant en deux catégories : les Convergent Replicated Data Types (CvRDT) et les Commutative Replicated Data Types (CmRDT).
Bien que l'équivalence entre ces deux approches ait été établie (l'une pouvant émuler l'autre), chacune présente des avantages spécifiques en fonction des propriétés de l'objet à répliquer et des conditions du réseau.
Convergent Replicated Data Types
La réplication des CvRDT repose sur l'envoi de la totalité de l'état de l'objet répliqué à toutes les autres répliques lors de chaque mise à jour. C'est pourquoi on les désigne également sous le terme de state-based CRDT.
Les CvRDT sont couramment adaptés lorsque la taille de l'état est relativement modeste par rapport au volume d'opérations qui lui sont appliquées, ou lorsque les communications ne sont pas fiables.
Commutative Replicated Data Types
La réplication des CmRDT, également appelés operation-based CRDT, repose sur la transmission des opérations effectuées localement par chaque réplica aux autres réplicas, lesquelles les intègrent par la suite à leur propre version de l'objet répliqué. Par conséquent, cette méthode de réplication s'avère plus pertinente lorsque la taille de l'état est significativement plus grande que celle des opérations, ou lorsque les communications sont jugées fiables.
Bibliographie
(en) Marc Shapiro, Nuno Preguiça, Carlos Baquero et Marek Zawirski, « A comprehensive study of Convergent and Commutative Replicated Data Types » (Rapport de recherche), INRIA, (ISSN0249-6399, HALhal-00555588, lire en ligne [PDF]).
(en) Marc Shapiro, Nuno Preguiça, Carlos Baquero et Marek Zawirski, « Conflict-free Replicated Data Types », INRIA, (ISSN0249-6399, HALhal-00609399v1, lire en ligne [PDF], consulté le ).
(en) Carlos Baquero, Paulo Sérgio Almeida et Ali Shoker, « Making Operation-Based CRDTs Operation-Based », 4th International Conference on Distributed Applications and Interoperable Systems (DAIS), Berlin, Allemagne, , p. 126-140 (DOI10.1007/978-3-662-43352-2_11, HALhal-01287738, lire en ligne [PDF]).
