J’avais tort. Les CRDT sont l’avenir.

 (josephg.com)
24 points par xguru 2020-10-05 | 10 commentaires | Partager sur WhatsApp

L’histoire des Conflict-free Replicated Data Types racontée par un développeur de Google Wave

→ CRDT : une structure de données qui prend en charge l’édition simultanée dans les outils de collaboration en temps réel

  • Wave reposait sur l’OT (Operational Transform) : stockage d’une liste chronologique de toutes les modifications. C’est comme un git rebase en temps réel

  • L’un des problèmes de l’OT est qu’il nécessite un serveur/une base de données centralisés

→ C’est probablement pour cela que Google Docs (qui repose aussi sur l’OT) affiche parfois « Ce document est surchargé et ne peut pas être modifié » quand trop de personnes se rassemblent sur un document ?

→ On peut l’éviter en partitionnant le document ou via une boucle de retry sur les transactions de base de données (en transférant le problème de sérialisation à la base de données)

→ Mais ce n’est pas parfait. Wave a été utilisé par plusieurs personnes en édition simultanée et cela fonctionnait, mais il y avait beaucoup de bugs. C’était trop complexe

  • L’essor des CRDT

→ L’algorithme utilisé par Wave a été inventé en 1995. Les recherches se sont poursuivies pour faire en sorte que l’OT fonctionne bien, mais les CRDT semblent plus prometteurs

→ Les CRDT adoptent une autre approche, qui permet l’édition en temps réel sans base de données centrale

→ La vitesse, la taille, les fonctionnalités et la complexité, autrefois pointées comme des problèmes, se sont toutes améliorées

  • Vitesse : les CRDT modernes (Automerge / RGA ou y.js / YATA) permettent aujourd’hui des recherches en log(n)

  • Taille : l’encodage en colonnes de Martin permet de stocker à environ 1,5 à 2 fois la taille du document.

  • Fonctionnalités : en théorie, le rewinding et le replaying sont possibles. Bien sûr, personne ne l’a encore implémenté

  • Complexité : la taille des implémentations est sans doute plus grande pour les CRDT que pour l’OT, mais l’écart n’est pas énorme

→ Ces améliorations devraient bientôt être proposées dans Automerge

  • Pour l’édition en temps réel, aussi triste que cela puisse paraître, l’OT et les travaux associés ne seront probablement plus nécessaires

→ Toutes les fonctionnalités de l’OT peuvent être intégrées aux CRDT, mais l’inverse est impossible

→ L’avantage de l’OT est qu’il convient bien aux logiciels centralisés, mais les algorithmes distribués fonctionnent aussi très bien dans une approche centralisée

→ Un CRDT de haute qualité exécuté en WASM sera plus rapide qu’une implémentation OT en JS

  • Le moment est venu de créer des CRDT légers et rapides.

→ La partie académique est presque achevée, et il est maintenant temps d’avoir d’excellentes implémentations

À lire aussi

10 commentaires

 
hackerwins 2020-10-05

Je m’appelle Hong Young-taek et je développe le projet Yorkie.

Yorkie, un dépôt de documents pour les applications d’édition collaborative en temps réel, est également construit sur la base des CRDT.

https://github.com/yorkie-team/yorkie
 
iolothebard 2020-10-05

J’avais tort. Les CRDT, c’est l’avenir.

Avec l’OT, on peut quasiment avoir l’undo/redo gratuitement… alors qu’avec les CRDT, il n’y a guère d’autre solution que les snapshots…
 
xguru 2020-10-05

Dans le cas d’Automerge, la bibliothèque elle-même prend en charge l’undo/redo. C’est sûrement compliqué pour la personne qui l’implémente, mais du point de vue de celui qui utilise la bibliothèque, voilà quoi haha
 
ffdd270 2020-10-05

https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d

J’avais traduit l’article en entier, mais j’ai oublié de le publier ; ;_; Je l’ai relu à partir d’une base Papago et je n’ai corrigé que les passages qui sonnaient bizarrement. Si vous voulez voir l’ambiance générale du texte après lecture, n’hésitez pas à consulter le lien ci-dessus~

Pour le poster dans la fenêtre de commentaires… c’est un peu trop long ; ;_; Je vous le partage donc via un lien Notion.
 
ffdd270 2020-10-05

À bien y réfléchir, il est possible que Notion utilise aussi des CRDT !
 
xguru 2020-10-05

Ce qui utilise l’OT, c’est Google Wave / Google Docs / MS Office365

Ce qui utilise les CRDT, c’est Figma / Apple Notes ainsi que Riak / Redis, etc.
 
xguru 2020-10-05

Je me trompais. Les CRDT sont l’avenir.

Comment fonctionne la technologie multi-utilisateur de Figma : https://fr.news.hada.io/topic?id=814
 
xguru 2020-10-05

La vidéo de Martin Kleppmann, développeur d'Automerge, liée dans l'article, "CRDTs: The Hard Parts", explique vraiment très bien le sujet.

Au début, elle compare et explique très bien OT et CRDT. La seconde partie entre davantage dans le détail de l'implémentation des CRDT.

https://www.youtube.com/watch?v=x7drE24geUw

Une bibliothèque CRDT utilisée pour créer des outils collaboratifs en JS
 
xguru 2020-10-05

Vers les systèmes de collaboration : de l’algorithme OT aux systèmes CRDT

https://deview.kr/2013/detail.nhn?topicSeq=66

Parmi les présentations coréennes, c’est presque la seule qui traite des CRDT.
 
hackerwins 2020-10-06

La personne, Hyeongeol, qui a donné cette présentation a créé le RGA mentionné dans le texte.

Yorkie a également implémenté son type de données de liste sur la base du RGA.

https://github.com/yorkie-team/yorkie/issues/2