- L’idée que les CRDT sont lents en édition collaborative vient souvent d’une confusion entre l’algorithme lui-même et la manière de l’implémenter ; les performances peuvent changer radicalement rien qu’avec la structure de données et l’agencement mémoire
- Automerge v1.0.0-preview2 a utilisé 291 s et 880 Mo de RAM pour traiter une trace de 260 000 modifications, tandis que Diamond types native a traité la même charge en 56 ms avec 1,1 Mo de RAM
- Yjs réduit cette même trace à 0,97 s et 3,3 Mo de RAM en utilisant une liste plate plutôt qu’un arbre, un cache de positions, une liste doublement chaînée et le stockage par spans
- Diamond types utilise en Rust une structure fondée sur range tree/B-tree pour traiter les recherches de position, insertions et suppressions en temps
log(n), et enregistre aussi 193 ms dans Node.js via WebAssembly - Ce benchmark ne mesure que la relecture locale d’éditions effectuées par un seul utilisateur et l’usage de la RAM ; dans un choix réel, il faut aussi considérer le temps de sauvegarde/chargement, la taille sur le réseau et le disque, le binary encoding, le protocole, la presence et l’editor binding
Algorithme et performances d’implémentation sont deux choses distinctes
- Une comparaison académique a benchmarké plusieurs algorithmes CRDT et OT en implémentant un éditeur collaboratif temps réel de type Google Docs, et certains algorithmes mettaient plus de 3 secondes à traiter un simple collage
- Les méthodes lentes étaient celles utilisées dans ShareJS et Google Wave, mais cette implémentation traitait un collage de 1 000 caractères comme 1 000 opérations individuelles
- Cet exemple montre qu’il faut distinguer le comportement en édition concurrente de la manière d’implémenter
- Le comportement désigne la façon dont les modifications concurrentes sur la même zone sont fusionnées, selon quel ordre et quelles règles
- L’implémentation inclut le langage de programmation, les structures de données et le niveau d’optimisation
- Même une même fonction de transformation text OT s’exécute environ 100 000 fois par seconde en JavaScript, contre 20 M fois par seconde en C, soit un écart d’environ 200×
- Une implémentation lente ne prouve pas que toutes les implémentations de ce système sont lentes ; des implémentations plus rapides sont possibles
Le modèle de base des CRDT et d’Automerge
- Les CRDT permettent à plusieurs utilisateurs de modifier simultanément les mêmes données, de travailler localement sans latence, puis de se synchroniser plus tard pour atteindre l’eventual consistency
- Automerge est une bibliothèque d’édition collaborative créée par Martin Kleppmann, basée sur l’algorithme RGA
- Les CRDT comme Automerge et Yjs considèrent le document partagé comme une liste de caractères, et attribuent un ID unique à chaque caractère
- Si l’on saisit
abcdans un document vide, des ID comme(seph, 0),(seph, 1),(seph, 2)sont attribués - Chaque nouveau caractère enregistre aussi « après quel élément il est inséré »
- Si l’on saisit
- Automerge/RGA ajoute un sequence number à chaque élément
- Chaque nouvel élément reçoit une valeur égale au plus grand sequence number vu jusque-là, plus 1
- Si un élément a plusieurs enfants, ils sont triés par sequence number décroissant, puis par agent ID en cas d’égalité
- Le fonctionnement d’Automerge/RGA peut se décomposer en trois étapes
- Chaque élément est relié à son parent pour former un arbre
- Les éléments ayant plusieurs enfants sont triés par sequence number et par ID
- L’arbre est aplati par depth-first traversal pour produire la liste finale ou le document texte
Benchmark d’Automerge et goulots d’étranglement
- Le benchmark utilise la trace d’édition de automerge-perf
- Il s’agit d’une trace, au caractère près, de Martin Kleppmann tapant un article académique
- La trace contient 260 000 modifications et le document final fait environ 100 000 caractères
- Elle n’inclut pas d’édition concurrente
- Le test ne mesure que le temps nécessaire pour appliquer la trace en local
- L’environnement de test était une station de travail Ryzen 5800x, Nodejs v16.1 et Rust 1.52
- Automerge v1.0.0-preview2 a mis 291 s à traiter cette trace, et utilisait 880 Mo de RAM à la fin
- Cela revient à environ 10 Ko de RAM par frappe
- Le pic mémoire atteignait 2,6 Go
- Lors des pics les plus lents, le traitement d’une seule modification prenait 1,8 s
- Une baseline consistant à faire des splice directement dans une chaîne JavaScript traitait les mêmes modifications en 0,61 s avec 0,1 Mo de RAM, mais c’est une baseline de comparaison qui abandonne toutes les informations nécessaires à l’édition collaborative
- La lenteur d’Automerge s’explique par plusieurs raisons d’implémentation
- La structure de données en arbre grossit et ralentit à mesure que le document s’agrandit
- L’usage intensif de Immutablejs complique l’optimisation par V8 et le GC
- Chaque caractère inséré est traité comme un élément distinct, donc même un collage génère de nombreux éléments
- L’équipe Automerge travaillait alors sur une implémentation alternative, automerge-rs, en Rust, utilisée via WASM
- À l’époque, sur la branche master, les performances moyennes de ce test n’étaient pas meilleures, mais l’usage mémoire était réduit de moitié et les variations de performance étaient plus modérées
Implémentation en liste plate à la Yjs
- Yjs est une implémentation CRDT open source créée par Kevin Jahns, qui stocke tous les éléments dans une liste plate unique plutôt que dans un arbre
- L’accès à cette liste plate consiste à parcourir à partir de l’élément juste après le parent pour trouver la position d’insertion ; c’est une manière d’implémenter un list CRDT sous forme de liste
- L’implémentation expérimentale reference-crdts implémente le YATA de Yjs et le RGA d’Automerge de la même manière
- La fonction insert traite Yjs et Automerge avec pratiquement le même codepath, à quelques différences près
- Un fuzzer vérifie leur équivalence sémantique
- Cette approche a trois avantages
- Elle utilise un flat array au lieu d’un arbre déséquilibré, ce qui la rend plus compacte et plus rapide
- Le code est simple
- Elle peut s’appliquer à plusieurs list CRDT, dont Yjs, Automerge et Sync9
- En théorie, elle peut ralentir s’il y a beaucoup d’insertions concurrentes au même endroit, mais dans l’édition réelle, les insertions se font le plus souvent juste après le parent
- L’implémentation reference-crdts était environ 10 fois plus rapide qu’Automerge et utilisait environ 30 fois moins de RAM
| Test | Temps de traitement | Utilisation RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Plain string edits in JS | 0.61s | 0.1MB |
Réduire le coût du scan et des insertions
- Dans l’implémentation avec un array plat, deux goulots d’étranglement subsistent
- il faut scanner le document pour trouver l’emplacement où insérer
- lors d’une insertion au milieu du array avec
doc.content.splice(destIdx, 0, newItem), il faut déplacer les éléments suivants
- Les éléments supprimés ne peuvent pas être retirés du array, car d’autres insertions peuvent encore les référencer ; il faut donc laisser un marqueur comme
isDeleted- même si le document actuel fait 100 000 caractères, il peut y avoir 150 000 éléments dans le array en comptant les anciens éléments
- pour insérer à la position 50 000 du document, il faut parfois scanner environ 75 000 éléments en sautant ceux qui sont supprimés
- Avec une telle structure, une insertion dans un document de
néléments demande environnétapes, et insérerncaractères devient O(n²) - Yjs met en cache la paire
(index, position)du dernier point d’édition, en s’alignant sur la façon dont les humains modifient un document- l’édition suivante a de fortes chances d’être proche de la précédente, donc le scan en avant ou en arrière reste court
- Yjs conserve aussi un ensemble de positions en cache pour les cas où plusieurs utilisateurs éditent à différents endroits
- Yjs utilise une liste doublement chaînée au lieu d’un array, ce qui permet d’insérer en temps constant une fois la position trouvée
- Yjs exploite aussi le fait que les humains tapent les caractères à la suite, en stockant
hellocomme un seul segment plutôt que comme 5 éléments caractère- ce regroupement n’est possible que lorsque les ID et les parent s’enchaînent séquentiellement
- dans ce jeu de données, le nombre d’entrées du array passe de 180 000 à 12 000, soit une réduction par 14
| Test | Temps de traitement | Utilisation RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Yjs v13.5.5 | 0.97s | 3.3MB |
| Plain string edits in JS | 0.61s | 0.1MB |
Rust et l’approche range tree de Diamond types
- Les objets JavaScript ont tendance à disperser dans des pointeurs le contenu, le drapeau de suppression, l’ID,
seq,parent, etc., ce qui augmente la fragmentation mémoire et le coût des cache miss - Rust permet de contrôler directement l’agencement mémoire, et peut aussi être utilisé sur le web via WebAssembly
- Diamond types est une implémentation de CRDT écrite en Rust ; elle est très proche de Yjs, mais utilise en interne un range tree au lieu d’une liste chaînée
- Le range tree interne est un B-tree légèrement modifié
- au lieu de stocker des clés comme un
BTreeMapclassique, les nœuds internes stockent la somme du nombre de caractères contenus dans leurs enfants - cela permet de gérer l’accès à une position arbitraire du document, les insertions et les suppressions en temps
log(n)
- au lieu de stocker des clés comme un
- Une trace de 260 000 éditions est stockée dans cet arbre avec environ 3 niveaux de nœuds leaf, ce qui permet de retrouver n’importe quel élément avec environ 3 lectures mémoire
- Il existe aussi un petit index qui parcourt un B-tree par ID pour la fusion des éditions distantes, mais ce codepath n’est pas inclus dans ce benchmark
- Les nœuds leaf stockent densément des blocs de 32 entrées dans un array de taille fixe
- l’auteur indique que cette taille de bucket de 32 fonctionne bien d’après les benchmarks effectués avec plusieurs tailles, sans savoir exactement pourquoi elle est optimale
- En compilant Diamond en WASM avec diamond-js puis en l’appelant depuis Node.js, la même trace est traitée en 193ms
- soit environ 5 fois plus vite que Yjs
- et environ 3 fois plus vite que la baseline JavaScript sur chaîne de caractères
- L’exécution native Rust atteint 56ms dans ce benchmark
- soit plus de 5 000 fois plus rapide qu’Automerge
- avec 4.6M opérations par seconde
- sur l’ensemble des 260 000 éditions,
mallocn’a été appelé que 1394 fois
| Test | Temps de traitement | Utilisation RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Yjs v13.5.5 | 0.97s | 3.3MB |
| Plain string edits in JS | 0.61s | 0.1MB |
| Diamond WASM via Node.js | 0.19s | inconnue |
| Diamond native | 0.056s | 1.1MB |
Séparation avec Ropey et tradeoff
- L’implémentation de Diamond ne stocke pas directement le contenu texte du document dans la liste des éléments CRDT, mais dans une structure de données séparée
- Pour le contenu texte, elle utilise la bibliothèque Rust Ropey, qui implémente elle aussi un B-tree pour gérer le texte
- Cette approche implique un tradeoff d’ingénierie
- Ropey fait du byte packing spécialisé pour le texte, ce qui peut réduire l’usage mémoire
- il faut mettre à jour deux structures de données lors des insertions, ce qui ralentit l’exécution de plus de 2 fois et fait grossir le bundle WASM de 60KB à 120KB
- lorsqu’on l’intègre à un editor comme VS Code, l’editor conserve déjà une copie du document ; il n’est donc pas forcément nécessaire de stocker aussi le contenu du document dans la structure CRDT
- Le traitement de la trace avec Ropey seul prend 29ms
- Si l’on désactive la mise à jour du contenu du document dans Diamond native, on obtient 23ms et 0.96MB de RAM
- soit environ 14 000 fois plus rapide qu’Automerge
- avec 11M opérations par seconde
- ce résultat relève davantage d’une expérience visant à observer les limites du traitement des métadonnées CRDT que d’un cas d’usage réellement utile
| Test | Temps de traitement | Utilisation RAM | Structure de données |
|---|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB | naive tree |
| reference-crdts Automerge/Yjs | 31s | 28MB | array |
| Yjs v13.5.5 | 0.97s | 3.3MB | linked list |
| Plain string edits in JS | 0.61s | 0.1MB | aucune |
| Diamond WASM via Node.js | 0.20s | inconnue | B-tree |
| Diamond native | 0.056s | 1.1MB | B-tree |
| Ropey Rust baseline | 0.029s | 0.2MB | aucune |
| Diamond native, no doc content | 0.023s | 0.96MB | B-tree |
Critères de choix d’une bibliothèque en pratique
- Si l’on devait créer aujourd’hui une application collaborative basée sur des documents, il serait plus avantageux d’utiliser Yjs
- Yjs offre de bonnes performances, une faible consommation mémoire et un bon écosystème de support
- Kevin Jahns propose aussi un support d’intégration Yjs payant
- L’équipe d’Automerge faisait également de la performance sa priorité numéro un en 2021 et prévoyait plusieurs techniques pour accélérer Automerge
- Diamond est extrêmement rapide, mais il lui reste encore beaucoup de travail pour atteindre une parité fonctionnelle avec Yjs et Automerge
- une bibliothèque CRDT a besoin, au-delà de la vitesse des opérations, d’un encodage binaire, d’un protocole réseau, de structures de données autres que des listes, de presence, de editor bindings, etc.
- Si des semantics de base de données sont nécessaires, l’auteur dit ne pas connaître de bonne implémentation sur CRDT, et suggère d’utiliser ShareDB, basé sur l’OT
- Redwood est un projet qui prend en charge l’édition P2P et prévoit un support CRDT complet
Limites de la méthode de mesure
- Ce benchmark mesure uniquement le temps de relecture d’une trace d’édition locale et l’utilisation de la RAM
- Les entrées de l’utilisateur local n’ont besoin d’être que suffisamment rapides, et si le CRDT traite une seule modification locale en environ 1 ms ou moins, une vitesse supérieure peut ne pas avoir beaucoup d’importance
- Automerge satisfait globalement aussi ce niveau, hors pause GC malchanceuse
- Les indicateurs réellement plus importants sont ailleurs
- le nombre d’octets qu’occupe le document sur disque ou sur le réseau
- le temps nécessaire pour enregistrer et charger
- le temps nécessaire pour mettre à jour un document stocké dans une base de données
- La trace utilisée ne contient que des éditions d’un seul utilisateur, donc il peut rester des cas pathologiques avec beaucoup d’édition concurrente
- À l’heure actuelle, pour mettre à jour un objet unique dans une base de données avec Yjs ou Automerge, il faut généralement charger tout le document en RAM, le modifier, puis réenregistrer tout le document, ce qui peut être lent
- Kevin dit qu’en ajustant correctement le provider Yjs, cela peut être implémenté d’une manière raisonnable
- Les list CRDT grossissent fondamentalement en continu à cause des tombstones des éléments supprimés, et le pruning est une approche distincte
- l’algorithme de GC de Yjs et Antimatter sont cités comme exemples
- le pruning est un problème orthogonal aux optimisations de structures de données abordées dans l’article
La comparaison n’est pas une expérience entièrement contrôlée
- Chaque étape d’optimisation a modifié plusieurs variables à la fois, donc elle n’isole pas la cause exacte des gains de performance
- Lors du passage d’Automerge à reference-crdts, plusieurs éléments ont changé
- la structure de données centrale est passée d’un arbre à une liste
- Immutablejs a été supprimé
- le protocole frontend/backend d’Automerge et plusieurs structures Uint8Array ont disparu
- le style JavaScript est passé d’un style fonctionnel à un style impératif
- Les transitions de reference-crdts à Yjs, puis de Yjs à Diamond, ne sont pas non plus isolées en une cause unique
- Le fait qu’automerge-rs n’ait pas été plus rapide qu’Automerge dans ce test suggère que les performances de Diamond ne s’expliquent pas uniquement par Rust, mais la contribution exacte reste inconnue
- Comparer RGA et YATA avec la même manière de les implémenter repose aussi sur l’hypothèse que « le comportement de fusion concurrente est en pratique similaire, et que les performances de l’implémentation restent les mêmes même si le comportement change »
- dans la reference CRDT implementation, les comportements de Yjs et d’Automerge suivent presque exactement le même codepath et affichent les mêmes performances
- sur des traces très chargées en conflits, il pourrait y avoir une différence de performance, mais cela est considéré comme très rare en pratique
- Yjs n’enregistre pas le moment où chaque élément a été supprimé ; il n’enregistre que le fait qu’il l’a été
- dans Diamond, enregistrer le moment de suppression fait passer l’usage mémoire de 1,12 Mo à 2,34 Mo et ralentit d’environ 5 %
- tous les benchmarks Diamond de cet article utilisent la branche de style Yjs, alignée sur l’approche de Yjs
Code du benchmark et éléments de reproduction
- Le code de test pour le baseline des chaînes JS, Yjs, Automerge et reference-crdts se trouve dans ce GitHub gist
- La plupart des tests nécessitent
automerge-paper.json.gzde josephg/crdt-benchmarks - Le benchmark reference-crdts dépend de cette version de josephg/reference-crdts
- Le benchmark Diamond a été exécuté avec cette version de josephg/diamond-types
- la commande d’exécution est
RUSTFLAGS='-C target-cpu=native' cargo criterion yjs - les statistiques mémoire se consultent avec
cargo run --release --features memusage --example stats
- la commande d’exécution est
- Le wrapper WASM de Diamond utilise diamond-js, et le bundle wasm est optimisé avec
wasm-opt - Les graphiques ont été réalisés sur ObservableHQ
1 commentaires
Avis sur Hacker News
S’ils ont utilisé des entiers sur 2 octets, c’est très probablement à cause des lignes de cache de 64 octets
32 entrées remplissent exactement une ligne de cache, si bien que chaque ligne de cache contenait tout un bucket et réduisait les transferts coûteux depuis la mémoire principale
En gros, il ajoutait un compteur pour compter combien de fois quelque chose devait être lu en mémoire ; je me demande si, de façon similaire, on pourrait approximer combien de fois il faut vider une ligne de cache
Ça saute à des frontières comme la taille d’un mot (64 bits), la taille de chargement alignée du cache (souvent les 64 octets mentionnés plus haut), la taille de page de l’OS (4 à 16 Ko), la taille du L1 (environ 80 Ko par cœur), ou le L2 (quelques Mo)
Je me demande quelles apps ont une très bonne expérience en utilisant réellement des CRDT en production
Je crois que Notion en faisait partie, mais en pratique, prendre des notes à deux dans Notion est presque inutilisable par rapport à Google Docs
C’est un IDE pour les tâches et la planification, une app multi-utilisateur, avec chiffrement de bout en bout, offline-first, auto-hébergement optionnel, et tout l’espace de travail est un graphe, donc les CRDT étaient un choix naturel
Toutes les actions dans Thymer se réduisent à un petit nombre de transformations CRDT. Déplacer/copier du texte, modifier des propriétés de « frontmatter », glisser des cartes, téléverser des fichiers, ajouter des tags : tout passe par les mêmes quelques opérations CRDT
Au début, l’implémenter sans bibliothèque a demandé beaucoup de travail, mais si l’état de l’application est un seul graphe, cela vaut largement le coup : on peut créer des fonctionnalités comme le déplacement de texte entre pages, les liens de pages avec backlinks, ou la transclusion, sans se soucier de la synchronisation
Les CRDT garantissent que tous les clients convergent vers le même état et, comme ils sont essentiellement append-only, on obtient gratuitement la gestion de versions à un instant donné
Cela dit, nous avons fait quelques compromis pour les performances. L’historique des versions représente trop de données pour être proposé hors ligne, et dans certains cas nous utilisons une résolution de conflit last writer wins
Globalement, cela vaut vraiment le coup, surtout si l’app est conçue dès le départ avec les CRDT en tête. Si l’on ajoute après coup des fonctionnalités multi-utilisateur à une app AJAX plus traditionnelle, je ne pense pas que j’utiliserais des CRDT
Les changements CRDT sont d’abord appliqués de manière optimiste ; puis, une fois l’ordre d’événements faisant autorité établi, tous les clients doivent revenir au dernier état partagé et réappliquer tous les événements dans le bon ordre
Si l’on est resté hors ligne longtemps, il peut falloir annuler puis réappliquer plusieurs jours de changements. L’utilisateur ne sait pas combien de transformations d’arbres se produisent en coulisse, mais les CRDT influencent toute la conception de l’application
La plupart des apps populaires d’aujourd’hui ont été conçues à une époque où les transformations CRDT n’étaient pas encore bien comprises
[1] https://thymer.com (presque prêt pour la bêta)
Le texte est en last writer wins, et le texte ou les propriétés de chaque bloc sont des registres last writer wins. Ils travaillent sur un nouveau format CRDT pour le texte des blocs
Cela inclut Notes et Reminders, et peut-être aussi Photos. J’ai entendu dire dans un bar, par un ancien SRE Apple ivre, qu’une partie du backend utilisait aussi FoundationDB
La présentation à Local First Conf vaut aussi le détour : https://youtu.be/VLgmjzERT08
Tous les jeux en réseau qui font une forme de rollback ou de correction s’en rapprochent. Le modèle best-effort avec rollback comme chemin de repli est peut-être la forme de CRDT largement utilisée qui offre la meilleure expérience utilisateur
Ce ne sont pas des CRDT au sens académique strict. Techniquement, l’état du jeu n’est pas entièrement répliqué sur tous les clients, et chaque client ne reçoit qu’un état partiel du jeu
De plus, les clients de jeu ont besoin d’une synchronisation à faible latence, ce que le monde académique pourrait appeler de la « coordination ». En pratique, le client accepte et rend localement le résultat des entrées de façon probabiliste avant que la résolution de conflit ou la correction par rollback ne revienne
Certains pinailleront, mais avec ce troisième exemple, le thème commun devrait apparaître. Les CRDT les plus populaires, les plus utilisables et les mieux implémentés enfreignent en réalité les règles académiques
C’est un piège typique d’un modèle de pensée trop académique. Les algorithmes et types de données du monde réel sont souvent bien plus créatifs qu’un « règlement » académique. Timsort en est un bon exemple
Si l’on construit un produit pour de vrais utilisateurs, et non pour une revue d’articles, il faut éviter les pièges de la sur-ingénierie et de l’académisme. Il faut apprendre les règles académiques, puis les enfreindre délibérément, et ajouter de la valeur réelle en rendant le produit agréable à utiliser, plutôt que d’essayer d’implémenter parfaitement des concepts définis avec une rigueur seulement utile entre universitaires
Les CRDT sont puissants, mais, qu’ils soient fondés sur les opérations ou sur l’état, il est dommage qu’ils laissent des traces des opérations ou des éléments passés.
Même avec de la compression, cela reste un inconvénient, et c’est un point qui fait hésiter à les adopter.
Cela dit, grâce à cette discussion, je trouve intéressant le potentiel d’implémenter des algorithmes sans conflit, ou des algorithmes de résolution fine des conflits, au-dessus de stockages de fichiers comme Dropbox ou Syncthing.
Mon projet post-CRDT, Diamond Types, grossit en principe indéfiniment avec le temps, mais le surcoût est généralement inférieur à 1 octet par caractère saisi jusqu’ici.
Si l’on active la compression LZ4 sur le texte stocké, les documents édités avec Diamond Types sont souvent plus petits que l’état final du document, alors même qu’ils stockent tout l’historique d’édition.
Techniquement, je connais plusieurs façons de résoudre cela, mais je ne suis pas convaincu que ce soit un vrai problème dans la plupart des systèmes.
J’ai entendu parler d’une personne qui utilisait yjs dans un outil de modélisation 3D et qui a rencontré des problèmes. C’était parce qu’elle créait une édition persistante à chaque déplacement de la souris au pixel près pendant qu’elle faisait glisser un objet.
Pour ce genre d’opérations, il me semble plus judicieux d’utiliser des éditions temporaires, ce que la plupart des bibliothèques CRDT ne prennent pas en charge.
À noter que Git a le même problème. Le dépôt grossit avec le temps, et bien plus vite qu’avec une bibliothèque CRDT moderne. Mais personne ne semble vraiment s’en soucier.
Git permet bien les clones superficiels, mais presque personne ne les utilise. Si on le voulait, on pourrait faire la même chose avec les CRDT.
Par exemple, si l’on peut garantir que tous les clients ont reçu les changements postérieurs à une date X, on peut supprimer sans risque les opérations antérieures à cette date.
Je développe Fireproof[1] pour tirer parti des recherches récentes dans ce domaine.
L’adressage par contenu de données immuables a l’avantage supplémentaire de faire aboutir chaque opération à une preuve ou à un diff garanti cryptographiquement. On peut imposer la cohérence causale et créer des références stables vers des snapshots.
Autrement dit, on peut faire tourner à l’edge ou dans le navigateur une base de données interactive, fonctionnant hors ligne et fusionnant sans perte, tout en bénéficiant de l’intégrité que l’on attendait auparavant d’une base de données centrale ou d’une blockchain.
Par exemple, on peut insérer un CID de snapshot dans un PDF à signer ou dans un smart contract, afin de lever toute ambiguïté sur l’état référencé.
[1] https://github.com/fireproof-storage/fireproof
Au final, il est plus juste de critiquer une implémentation concrète que de parler de façon générale d’un ensemble de lois mathématiques suivies par un type de données ou une base de données donné.
L’article date de 2021 et semble inclure aussi l’implémentation Rust d’Automerge ; il serait intéressant de voir des benchmarks à jour.
J’ai aussi une toute nouvelle approche, complètement différente, pour résoudre ce problème.
Ce serait clairement bien de mettre les benchmarks à jour. Tout est devenu plus rapide.
J’ai eu du mal à comprendre une bonne partie du contenu, mais l’article est si bien écrit que c’est l’un de ces rares textes qu’on lit sans s’arrêter.
Voici les discussions précédentes liées :
https://news.ycombinator.com/item?id=28017204 (il y a 3 ans, 151 commentaires)
https://news.ycombinator.com/item?id=33903563 (il y a 2 ans, 22 commentaires)
https://news.ycombinator.com/item?id=41372833 (publication actuelle)
https://news.ycombinator.com/item?id=41373288 (commentaire actuel)
Pour citer le README GitHub actuel[0], les performances se seraient encore améliorées de 10 à 80 fois depuis cet article de blog.
[0] https://github.com/josephg/diamond-types
J’aimerais bien que quelqu’un puisse expliquer pourquoi les CRDT sont lents.
Cet article semble montrer l’avenir : https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
Ce serait intéressant de comparer cela à Y.js ou Automerge : https://github.com/canvasxyz/okra-js
Depuis que j’ai écrit cet article il y a quelques années, toutes les principales bibliothèques CRDT sont devenues plus rapides de plusieurs ordres de grandeur.
Je me souviens être tombé sur cet article par hasard il y a quelques années.
C’est un texte vraiment passionnant, et l’un de mes préférés de ces dernières années.
À la question « pourquoi WASM est-il 4 fois plus lent que l’exécution native ? », je pensais que c’était parce que toutes les opérations sur les chaînes devaient être copiées dans la mémoire WASM, puis, une fois le résultat calculé, recopiées vers JS.
Je me trompe ? J’ai mal compris le contexte ? Je suis sincèrement curieux
Avant de mesurer le temps, je chargeais tout l’historique dans wasm, puis je le traitais dans une boucle interne écrite en Rust, exécutée dans le contexte wasm lui-même. Il n’y avait qu’environ deux appels wasm.
La cause du ralentissement par 4 n’était pas le FFI : le code de l’algorithme lui-même s’exécutait réellement 4 fois plus lentement.
Ce serait intéressant de relancer les benchmarks aujourd’hui. La sortie wasm des compilateurs s’est améliorée et les runtimes wasm ont sans doute aussi gagné en vitesse. Le code de benchmark doit encore traîner quelque part.
Dans un domaine à part, un problème qui revient sans cesse est que la question du multithreading n’est pas simple, et que le support des bibliothèques et des outils n’est pas complet.
J’ai essayé de faire tourner dans le navigateur des moteurs de jeu ou des binaires utilitaires comme ffmpeg et zip, et c’était très lent à cause de ça.
Je n’ai jamais travaillé sur un interpréteur ou un JIT WASM, mais à quelle fréquence passer par plusieurs couches est-il préférable à passer par une seule couche de traduction ?
Quand on traduit du code haut niveau en WASM ou dans un langage d’assemblage quelconque, on perd une grande partie de l’intention contenue dans le code haut niveau.
Dans du code bas niveau, on voit souvent une suite d’idiomes propres au langage pour atteindre un objectif, qui peuvent ou non avoir un équivalent direct sur la machine réelle.
Le x86-64 moderne dispose d’un très grand nombre d’instructions bien plus puissantes que ce que WASM permet de faire.
Bien sûr, il existe des décompilateurs, et un JIT WASM pourrait disposer d’une liste de fusions de macro-opérations permettant de produire du bon code natif par un pattern matching relativement simple. Ce n’est probablement pas le cas, et l’optimisation multiplateforme est plus difficile.
LLVM n’est pas parfait non plus, donc il y a sûrement des points faciles qu’un optimiseur de post-traitement pourrait améliorer. En théorie, il n’est donc pas impossible de rendre WASM plus rapide que la sortie native de LLVM.
Mais à moins d’avoir un plan très bien conçu, ou de créer un jeu d’instructions qui soit en fait un sur-ensemble de ce que l’architecture cible prend en charge, obtenir un résultat du même niveau me paraît très difficile.
À mes yeux, WASM ressemble plutôt à un sous-ensemble ; il n’est donc pas facile de standardiser les opérations puis de les recomposer en temps réel. Ce n’est pas totalement impossible, mais cela demanderait un effort d’ingénierie considérable.
Intuitivement, si l’on prend un livre écrit en anglais, qu’on le traduit dans une langue très différente et limitée à quelques milliers de mots, puis qu’on le retraduit en anglais, on n’obtient pas exactement le même texte.
Il arrive qu’un concept qui tiendrait en un seul mot en anglais doive être expliqué en un paragraphe. Pour retrouver l’anglais d’origine, il faudrait soit une traduction 1:1 pour tout, soit une liste de traductions « paragraphe → un mot » convenue entre les deux traducteurs.