Des CRDT 5�0 fois plus rapides : l'aventure de l'optimisation
Introduction
- Il y a quelques ann�e9es, des chercheurs fran�e7ais ont publi�e9 un article comparant des algorithmes d'�e9dition collaborative en temps r�e9el
- Ils ont impl�e9ment�e9 plusieurs algorithmes et mesur�e9 leurs performances
- Certains algorithmes mettaient plus de 3 secondes pour une simple op�e9ration de collage
- L'algorithme en cause �e9tait celui utilis�e9 par ShareJS
Cause du probl�e8me
- Dans l'article, lorsqu'un grand texte �e9tait coll�e9, il �e9tait trait�e9 en le d�e9coupant en 1�000 op�e9rations distinctes
- Il ne s'agissait pas d'un probl�e8me de l'algorithme lui-m�eame, mais de son impl�e9mentation
L'attrait des CRDT
- Les CRDT (Conflict-Free Replicated Data Types) permettent �e0 plusieurs utilisateurs d'�e9diter des donn�e9es simultan�e9ment
- On peut travailler localement sans latence, tout en maintenant automatiquement la coh�e9rence lors de la synchronisation
- Ils peuvent fonctionner sans serveur central
Les probl�e8mes d'Automerge
- Automerge est une biblioth�e8que d'�e9dition collaborative bas�e9e sur l'algorithme RGA
- Chaque caract�e8re d'un document est g�e9r�e9 avec un identifiant unique, et l'insertion indique un �e9l�e9ment parent
- En raison de probl�e8mes de performances, il fallait 5 minutes pour traiter 260�000 op�e9rations d'�e9dition
- L'utilisation m�e9moire �e9tait �e9galement tr�e8s �e9lev�e9e
Optimisation des performances
- Les probl�e8mes de performance d'Automerge venaient d'une structure de donn�e9es complexe bas�e9e sur un arbre et de l'utilisation d'Immutablejs
- Yjs am�e9liore fortement les performances en utilisant une simple liste plate
- Yjs utilise un cache pour trouver la position d'insertion et une liste doublement cha�een�e9e pour g�e9rer efficacement les insertions
- Yjs est 30 fois plus rapide et consomme moins de m�e9moire
Passage �e0 Rust
- Rust permet d'avoir un contr�f4le fin sur le layout m�e9moire, ce qui peut encore am�e9liorer les performances
- Une nouvelle impl�e9mentation de CRDT, appel�e9e Diamond types, atteint des performances 5 fois sup�e9rieures �e0 Yjs
- Diamond, impl�e9ment�e9 en Rust, traite 260�000 op�e9rations d'�e9dition en seulement 56 millisecondes
Conclusion
- Des structures de donn�e9es optimis�e9es et une gestion efficace de la m�e9moire permettent d'am�e9liorer fortement les performances des CRDT
- L'utilisation d'un langage de bas niveau comme Rust permet d'aller encore plus loin en performance
Le r�e9sum�e9 de GN
- Les CRDT repr�e9sentent l'avenir de l'�e9dition collaborative, avec un outil puissant capable de maintenir la coh�e9rence sans serveur central
- Les probl�e8mes de performance d'Automerge venaient d'une structure de donn�e9es complexe et d'une utilisation inefficace de la m�e9moire
- Yjs et Diamond types am�e9liorent fortement les performances en s'appuyant sur des structures de donn�e9es simples et efficaces
- L'utilisation d'un langage de bas niveau comme Rust permet d'obtenir des performances encore plus rapides
- Si vous d�e9veloppez un outil d'�e9dition collaborative, Yjs et Diamond types valent la peine d'�eatre envisag�e9s
1 commentaires
Avis Hacker News
La raison pour laquelle 32 entrées sont les plus efficaces est que les lignes de cache font 64 octets
Il est difficile de trouver des exemples d’applications réelles utilisant des CRDTs qui offrent une bonne expérience
Les CRDTs sont puissants, mais ont l’inconvénient de conserver l’historique des opérations (ou des éléments)
Citation actuelle du README GitHub :
Cet article était difficile sur le fond, mais si bien écrit qu’il était impossible d’arrêter de le lire
En voyant l’utilisation d’une hiérarchie, quelqu’un s’est demandé pourquoi ne pas avoir utilisé à la place des ensembles imbriqués
Quelqu’un est tombé par hasard sur ce billet il y a quelques années
Une personne s’est demandé pourquoi WASM est 4 fois plus lent que l’exécution native
Comme l’implémentation Rust d’Automerge est terminée, voir des benchmarks mis à jour serait intéressant