Les CRDT permettent aux répliques de diverger et de converger malgré tout, sans verrous

L'édition multi-utilisateurs fait face à un problème fondamental : lorsque deux personnes modifient le même document hors ligne ou sur des connexions différentes, les deux copies changent, et quelqu'un doit les réconcilier. Les approches traditionnelles soit verrouillent des parties du document — bloquant la collaboration —, soit recourent à la transformation opérationnelle, dont les combinaisons d'états explosent et dont la preuve de correction est notoirement difficile.

En 2011, Marc Shapiro et ses collègues ont proposé les types de données répliqués sans conflit (CRDT) : des structures de données conçues pour que les mises à jour concurrentes commutent. Si chaque mise à jour commute et que les fusions sont associatives, des répliques qui ont divergé peuvent être fusionnées dans n'importe quel ordre et converger malgré tout vers un état identique unique, sans coordinateur central ni boîte de dialogue de conflit. Registres, compteurs, ensembles et éditeurs de texte peuvent tous être construits de cette manière.

La théorie s'est consolidée au cours des années suivantes : l'article OpSets de 2018 de Martin Kleppmann et ses collègues a construit un cadre exécutable qui vérifie mécaniquement les algorithmes de types de données répliqués, a mis au jour une propriété de correction pour le texte collaboratif que plusieurs algorithmes publiés violaient, et a spécifié une opération de déplacement atomique que l'on croyait auparavant impossible sans verrouillage.

Les systèmes en production ont adopté l'idée. Le moteur multijoueur de Figma s'inspire explicitement de la recherche sur les CRDT : sa conception à autorité serveur, par propriété, fonctionne comme un registre « dernier écrivain gagne », choisi après que l'entreprise a rejeté la transformation opérationnelle comme inutilement complexe. Redis, Riak et Cosmos DB fournissent des types de données fondés sur les CRDT, et Notes d'Apple utilise les CRDT pour synchroniser les modifications hors ligne entre appareils.

Rendre le type de données commutatif pour la fusion par conception

Les fusions commutatives rendent le résultat indépendant de l'ordre des mises à jour

Les répliques peuvent être modifiées hors ligne et converger sans aucune autorité centrale

La vérification mécanique a remplacé les preuves de correction approximatives

Les produits à la Figma ont obtenu une collaboration en temps réel sans la complexité de la transformation opérationnelle

Si la coordination est le goulot d'étranglement, reconcevez les données pour que la coordination soit inutile : choisissez des opérations dont les résultats sont indépendants de l'ordre, et les utilisateurs concurrents obtiennent la cohérence gratuitement.

Les CRDT sont désormais la réponse standard pour la collaboration et la réplication hors ligne d'abord : la synchronisation multijoueur de Figma, Notes d'Apple, les types de données de Redis et de Riak, et les outils d'édition pair-à-pair reposent sur cette idée, et la ligne de recherche se poursuit avec les aspects difficiles de l'édition de texte, des déplacements d'arborescence et des contextes byzantins.