El recorrido de optimización que hizo que los CRDT fueran 5000 veces más rápidos (2021)

 (josephg.com)
3 puntos por GN⁺ 2024-08-28 | 1 comentarios | Compartir por WhatsApp
  • La evaluación de que los CRDT son lentos en la edición colaborativa suele ser resultado de mezclar el algoritmo en sí con la forma de implementación; solo con la estructura de datos y la disposición en memoria el rendimiento puede cambiar mucho
  • Automerge v1.0.0-preview2 usó 291 segundos y 880 MB de RAM para procesar un historial de 260,000 ediciones, mientras que Diamond types native procesó la misma tarea en 56 ms y con 1.1 MB de RAM
  • Yjs redujo el mismo historial a 0.97 segundos y 3.3 MB de RAM usando una lista plana en vez de un árbol, caché de posiciones, una lista doblemente enlazada y almacenamiento de spans
  • Diamond types usa en Rust una estructura basada en range tree/B-tree para manejar búsquedas de posición, inserciones y borrados en tiempo log(n), y aun en WebAssembly registró 193 ms en Node.js
  • Este benchmark solo analiza la reproducción local de ediciones de un único usuario y el uso de RAM, así que para elegir en la práctica también hay que considerar tiempos de guardado y carga, tamaño en red/disco, binary encoding, protocolo, presence y editor binding

El algoritmo y el rendimiento de la implementación son cosas distintas

  • Una comparación académica implementó edición colaborativa en tiempo real, como Google Docs, con varios CRDT y algoritmos OT, y los puso en benchmark; algunos algoritmos tardaron más de 3 segundos en procesar un simple paste
  • Los métodos lentos eran algoritmos usados en ShareJS y Google Wave, pero esa implementación procesaba un paste de 1000 caracteres dividiéndolo en 1000 operations individuales
  • Este caso muestra que hay que separar el comportamiento ante edición concurrente de la forma de implementación
    • El comportamiento se refiere a con qué orden y reglas se fusionan ediciones concurrentes cuando entran en la misma zona
    • La implementación incluye el lenguaje de programación, las estructuras de datos y el nivel de optimización
  • La misma función de text OT transform se ejecutaba unas 100,000 veces por segundo en JavaScript y 20 M veces por segundo en C, una diferencia de aproximadamente 200 veces
  • Una implementación lenta no prueba que todas las implementaciones de ese sistema sean lentas; es posible hacer una implementación más rápida

Modelo básico de CRDT y Automerge

  • CRDT permite que varios usuarios editen los mismos datos al mismo tiempo, trabajen localmente sin latencia y luego sincronicen para llegar a eventual consistency
  • Automerge es una biblioteca de edición colaborativa creada por Martin Kleppmann y basada en el algoritmo RGA
  • CRDT como Automerge y Yjs ven un documento compartido como una lista de caracteres y asignan un ID único a cada carácter
    • Si se ingresa abc en un documento vacío, recibe IDs como (seph, 0), (seph, 1), (seph, 2)
    • Cada carácter nuevo también registra “después de qué elemento se inserta”
  • Automerge/RGA agrega un sequence number a cada elemento
    • Un elemento nuevo recibe un valor 1 mayor que el mayor sequence number visto hasta ese momento
    • Si hay varios elementos hijos, se ordenan por sequence number descendente y, si empatan, por agent ID
  • El comportamiento de Automerge/RGA puede verse en tres pasos
    • Conectar cada elemento con su parent para construir un árbol
    • Ordenar por sequence number e ID los elementos que tienen varios hijos
    • Aplanar el árbol con depth-first traversal para crear la lista final o el documento de texto

Benchmark de Automerge y cuellos de botella

  • El benchmark usa el historial de edición de automerge-perf
    • Es un trace que registra, carácter por carácter, cómo Martin Kleppmann tipeó un paper académico
    • El trace tiene 260,000 ediciones y el documento final mide unas 100,000 letras
    • No incluye edición concurrente
    • La prueba solo mide el tiempo de aplicar el trace localmente
    • El entorno es una workstation Ryzen 5800x, Nodejs v16.1 y Rust 1.52
  • Automerge v1.0.0-preview2 tardó 291 segundos en procesar este trace, y al finalizar usaba 880 MB de RAM
    • Equivale a unos 10 KB de RAM por cada pulsación de tecla
    • El pico de RAM fue de 2.6 GB
    • En un spike lento, procesar una sola edición tomó 1.8 segundos
  • La baseline que hace splice directamente sobre strings de JavaScript procesó las mismas ediciones en 0.61 segundos y con 0.1 MB de RAM, pero es una baseline comparativa que descarta toda la información necesaria para la edición colaborativa
  • Hay varias razones de implementación por las que Automerge es lento
    • A medida que el documento crece, la estructura de datos basada en árbol crece y se vuelve más lenta
    • Usa mucho Immutablejs, lo que dificulta que el optimizer de V8 y el GC optimicen
    • Trata cada carácter insertado como un elemento separado, así que incluso un paste se procesa como muchos elementos
  • El equipo de Automerge estaba trabajando en una implementación alternativa que usa automerge-rs, una implementación en Rust, vía WASM
    • En ese momento, tomando como referencia la master branch, el rendimiento promedio de esta prueba no mejoraba, pero el uso de memoria se reducía a la mitad y la variación de rendimiento se volvía más suave

Implementación al estilo Yjs con lista plana

  • Yjs es una implementación open source de CRDT creada por Kevin Jahns, y almacena todos los elementos en una única lista plana en vez de un árbol
  • El enfoque de lista plana busca la posición de inserción escaneando desde justo después del parent del nuevo elemento; es una forma de implementar un list CRDT como lista
  • La implementación experimental reference-crdts implementa YATA de Yjs y RGA de Automerge de la misma manera
    • La función insert, salvo pequeñas diferencias, procesa el comportamiento de Yjs y Automerge casi por el mismo codepath
    • Verifica la equivalencia semántica con un fuzzer
  • Este enfoque tiene tres ventajas
    • Usa un flat array en vez de un árbol desbalanceado, por lo que es más pequeño y rápido
    • El código es simple
    • Puede aplicarse a varios list CRDT, como Yjs, Automerge y Sync9
  • En teoría podría volverse lento si hay muchas inserciones concurrentes en la misma posición, pero en la edición real casi siempre se inserta justo después del parent
  • La implementación reference-crdts fue unas 10 veces más rápida que Automerge y usó unas 30 veces menos RAM
Prueba Tiempo de procesamiento Uso de RAM
automerge v1.0.0-preview2 291 s 880 MB
reference-crdts Automerge/Yjs 31 s 28 MB
Ediciones de string plano en JS 0.61 s 0.1 MB

Reducir el costo de escaneo e inserción

  • En la implementación con un array plano quedaban dos cuellos de botella
    • Había que escanear el documento para encontrar la posición donde insertar
    • Al insertar en medio del array con doc.content.splice(destIdx, 0, newItem), había que mover los elementos posteriores
  • Los elementos eliminados no se pueden quitar del array porque otras inserciones pueden referenciarlos, y hay que dejar una marca como isDeleted
    • Aunque el documento actual tenga 100,000 caracteres, puede haber 150,000 items de array incluyendo elementos históricos
    • Para insertar en la posición 50,000 del documento, se podrían escanear aproximadamente 75,000 items saltando los elementos eliminados
  • Con esta estructura, insertar en un documento que tenía n elementos requiere alrededor de n pasos, y si se insertan n caracteres se vuelve O(n²)
  • Yjs cachea el par (index, position) de la última posición editada, ajustándose a la forma en que las personas editan documentos
    • Es probable que la siguiente edición esté cerca de la anterior, así que escanea poco hacia adelante o hacia atrás
    • Guarda un conjunto de posiciones cacheadas para cuando varios usuarios editan en lugares distintos
  • Yjs usa una lista doblemente enlazada en lugar de un array, por lo que, una vez encontrada la posición, inserta en tiempo constante
  • También aprovecha que las personas escriben caracteres de forma continua y guarda hello como un solo span, no como 5 elementos de carácter
    • Solo se puede colapsar cuando el ID y el parent continúan de forma secuencial
    • En este dataset, la cantidad de entradas del array bajó de 180,000 a 12,000, una reducción de 14 veces
Prueba Tiempo de procesamiento Uso de RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Ediciones de strings simples en JS 0.61s 0.1MB

Rust y el enfoque de range tree de Diamond types

  • Los objetos de JavaScript tienden a convertirse en una estructura dispersa con punteros para content, deletion flag, ID, seq, parent, etc., lo que aumenta la fragmentación de memoria y el costo de cache misses
  • Rust permite controlar directamente la disposición de memoria y también se puede usar en la web mediante WebAssembly
  • Diamond types es una implementación de CRDT escrita en Rust, casi igual a Yjs, pero internamente usa un range tree en lugar de una lista enlazada
  • El range tree interno es un B-tree ligeramente modificado
    • En lugar de guardar keys como un BTreeMap común, los nodos internos guardan la suma de la cantidad de caracteres incluidos en sus hijos
    • Procesa consultas de posiciones arbitrarias, inserciones y eliminaciones del documento en tiempo log(n)
  • El trace de 260,000 ediciones queda almacenado en este tree con unos 3 niveles de leaf nodes, por lo que cualquier item puede encontrarse con aproximadamente 3 lecturas de memoria
  • Para hacer merge de remote edits también hay un índice pequeño que busca en un B-tree por ID, y ese codepath no está incluido en este benchmark
  • Los leaf nodes almacenan de forma compacta bloques de 32 entries en un array de tamaño fijo
    • El autor indicó que el bucket size de 32 funcionó bien tras hacer benchmarks con varios tamaños, pero que no sabe por qué es el óptimo
  • Al compilar Diamond a WASM como diamond-js y llamarlo desde Node.js, procesa el mismo trace en 193ms
    • Es aproximadamente 5 veces más rápido que Yjs
    • Es aproximadamente 3 veces más rápido que el baseline de strings de JavaScript
  • La ejecución nativa en Rust registró 56ms en el benchmark
    • Es más de 5000 veces más rápido que Automerge
    • Procesa 4.6M operaciones por segundo
    • Durante el procesamiento total de 260,000 ediciones, hubo 1394 llamadas a malloc
Prueba Tiempo de procesamiento Uso de RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Ediciones de strings simples en JS 0.61s 0.1MB
Diamond WASM vía Node.js 0.19s desconocido
Diamond nativo 0.056s 1.1MB

Separación de Ropey y tradeoff

  • La implementación de Diamond no pone directamente el contenido de texto del documento en la lista de items del CRDT, sino que lo almacena en una estructura de datos separada
  • Para el contenido de texto usa la biblioteca de Rust Ropey, que también implementa un B-tree para gestionar texto
  • Este enfoque tiene un tradeoff de ingeniería
    • Ropey hace byte packing especializado para texto, por lo que puede reducir el uso de RAM
    • Al insertar, hay que actualizar dos estructuras de datos, lo que vuelve la ejecución más de 2 veces más lenta, y el bundle WASM también crece de 60KB a 120KB
    • Si se conecta con un editor como VS Code, el editor mantiene una copia del documento, así que puede no ser necesario guardar el contenido del documento dentro de la estructura CRDT
  • Procesar el trace solo con Ropey tarda 29ms
  • Si en Diamond nativo se desactiva la actualización del content del documento, registra 23ms y 0.96MB de RAM
    • Es aproximadamente 14,000 veces más rápido que Automerge
    • Procesa 11M operaciones por segundo
    • Este resultado es más bien un experimento para ver el límite del procesamiento de metadata CRDT que para medir su utilidad
Prueba Tiempo de procesamiento Uso de RAM Estructura de datos
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
Ediciones de strings simples en JS 0.61s 0.1MB ninguna
Diamond WASM vía Node.js 0.20s desconocido B-tree
Diamond nativo 0.056s 1.1MB B-tree
Baseline de Ropey en Rust 0.029s 0.2MB ninguna
Diamond nativo, sin doc content 0.023s 0.96MB B-tree

Criterios para elegir una biblioteca real

  • Si hoy se fuera a crear una app colaborativa basada en documentos, convendría usar Yjs
    • Yjs ofrece buen rendimiento, bajo uso de memoria y un buen ecosistema de soporte
    • Kevin Jahns también ofrece soporte pago para integración con Yjs
  • El equipo de Automerge también tenía el rendimiento como prioridad principal en 2021, y había planes para acelerar Automerge con varias técnicas
  • Diamond es muy rápido, pero todavía queda mucho trabajo para alcanzar la paridad de funciones de Yjs y Automerge
    • Además de la velocidad de las operaciones, una biblioteca CRDT necesita binary encoding, network protocol, estructuras de datos non-list, presence, editor binding, etc.
  • Si se necesitan semantics de base de datos, no se conoce una implementación bien lograda sobre CRDT, y se puede usar ShareDB basado en OT
  • Redwood es un proyecto que soporta P2P editing y planea full CRDT support

Limitaciones del método de medición

  • Este benchmark solo mide el tiempo de reproducción de un trace de ediciones locales y el uso de RAM
  • La entrada de un usuario local solo necesita ser lo bastante rápida; si un CRDT procesa una única edición local en alrededor de 1 ms o menos, una mayor velocidad quizá no importe demasiado
    • Automerge también suele cumplir con este nivel, salvo por alguna pausa de GC con mala suerte
  • En la práctica, hay otras métricas más importantes
    • La cantidad de bytes que ocupa un documento en disco o en la red
    • El tiempo que tarda en guardarse y cargarse
    • El tiempo que tarda en actualizarse un documento guardado dentro de una base de datos
  • El trace usado solo incluye ediciones de un único usuario, por lo que podrían quedar casos patológicos con muchas ediciones simultáneas
  • Actualmente, para actualizar un único objeto de una base de datos con Yjs o Automerge, por lo general hay que cargar todo el documento en RAM, modificarlo y volver a guardar todo el documento, lo que puede ser lento
    • Kevin dice que, ajustando adecuadamente un provider de Yjs, se puede implementar de una forma razonable
  • Los CRDT de listas crecen por defecto de manera continua debido a los tombstones de elementos eliminados, y el pruning es un enfoque aparte
    • Se mencionan como ejemplos el algoritmo de GC de Yjs y Antimatter
    • El pruning es un problema ortogonal a la optimización de estructuras de datos tratada en el artículo

La comparación no es un experimento completamente controlado

  • Cada etapa de optimización cambió varias variables al mismo tiempo, por lo que no se aísla la causa exacta de la mejora de velocidad
  • Al pasar de Automerge a reference-crdts, cambiaron varios elementos
    • La estructura de datos central pasó de un árbol a una lista
    • Se eliminó Immutablejs
    • Desaparecieron el protocolo frontend/backend de Automerge y varias estructuras Uint8Array
    • El estilo de JavaScript cambió de funcional a imperativo
  • También al pasar de reference-crdts a Yjs, y de Yjs a Diamond, los cambios no se aíslan como una única causa
  • El hecho de que automerge-rs no fuera más rápido que Automerge en esta prueba es un indicio de que el rendimiento de Diamond no se debe solo a Rust, pero no se puede conocer la contribución exacta
  • Comparar RGA y YATA con el mismo enfoque de implementación también se apoya en la premisa de que “el comportamiento de fusión simultánea es prácticamente similar, y el rendimiento de la implementación se mantiene aunque se cambie el comportamiento”
    • En la implementación de CRDT de referencia, Yjs y Automerge muestran casi el mismo codepath y el mismo rendimiento
    • En traces con muchos conflictos podría haber diferencias de rendimiento, pero se considera que en la práctica son casos muy poco frecuentes
  • Yjs no guarda cuándo se eliminó cada item, solo guarda si fue eliminado o no
    • En Diamond, guardar el momento de eliminación aumenta el uso de memoria de 1.12 MB a 2.34 MB y lo hace alrededor de un 5% más lento
    • Todos los benchmarks de Diamond de este artículo usan la rama yjs-style, alineada con el enfoque de Yjs

Código del benchmark y materiales de reproducción

  • El código de pruebas para la línea base con strings de JS, Yjs, Automerge y reference-crdts está en este GitHub gist
  • Para la mayoría de las pruebas se necesita automerge-paper.json.gz de josephg/crdt-benchmarks
  • El benchmark de reference-crdts depende de esa versión de josephg/reference-crdts
  • El benchmark de Diamond se ejecuta con esa versión de josephg/diamond-types
    • El comando de ejecución es RUSTFLAGS='-C target-cpu=native' cargo criterion yjs
    • Las memory statistics se consultan con cargo run --release --features memusage --example stats
  • El wrapper WASM de Diamond usa diamond-js, y el wasm bundle se optimiza con wasm-opt
  • Los gráficos se hicieron en ObservableHQ

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-08-28
Opiniones en Hacker News

  • Si usaron enteros de 2 bytes, es muy probable que haya sido por la línea de caché de 64 bytes.
    32 entradas forman exactamente una línea de caché, así que cada línea de caché habría contenido un bucket completo y reducido las costosas transferencias desde la memoria principal.

    • Me gustaba la forma en que Knuth hacía benchmarks de sus programas posteriores.
      Básicamente agregaba un contador para contar cuántas veces había que leer algo desde memoria, y me pregunto si se podría aproximar de forma similar cuántas veces hay que vaciar una línea de caché.
    • Al hacer benchmarks por tamaño de lote, suelen aparecer grandes saltos relacionados con la jerarquía de memoria.
      Saltan en límites como el tamaño de palabra (64 bits), el tamaño de fetch alineado a caché (normalmente los 64 bytes mencionados arriba), el tamaño de página del SO (4 a 16 KB), el tamaño de L1 (unos 80 KB por core) y L2 (del orden de algunos MB).

  • Me pregunto qué apps que usan CRDT en servicios reales ofrecen una experiencia muy buena.
    Recuerdo que Notion era una de ellas, pero en la práctica que dos personas tomen notas juntas en Notion es casi inutilizable comparado con Google Docs.

    • Thymer[1] usa CRDT para todo.
      Es un IDE para tareas y planificación, una app multiusuario, con cifrado de extremo a extremo, offline-first y self-hosting opcional; como todo el espacio de trabajo es un único grafo, CRDT fue una elección natural.
      Todas las acciones en Thymer se reducen a un pequeño número de transformaciones CRDT. Mover/copiar texto, cambiar propiedades de "frontmatter", arrastrar tarjetas, subir archivos y agregar etiquetas se manejan con las mismas pocas operaciones CRDT.
      Implementarlo al principio sin una librería dio mucho trabajo, pero si el estado de la aplicación es un solo grafo, vale totalmente la pena porque se pueden crear funciones como mover texto entre páginas, enlaces a páginas con backlinks y transclusión sin preocuparse por la sincronización.
      CRDT garantiza que todos los clientes converjan al mismo estado y, como por naturaleza es append-only, también se obtiene gratis versionado a un punto en el tiempo.
      Dicho eso, hicimos algunas concesiones por rendimiento. El historial de versiones tiene demasiados datos como para ofrecerlo offline, y en algunos casos usamos resolución de conflictos last-writer-wins.
      En general vale mucho la pena, sobre todo si diseñas la app pensando en CRDT desde el inicio. Si fuera una app AJAX más tradicional a la que luego se le agrega funcionalidad multiusuario, probablemente no usaría CRDT.
      Los cambios de CRDT primero se aplican de forma optimista y, cuando se determina el orden autoritativo de eventos, todos los clientes tienen que volver al último estado compartido y reaplicar todos los eventos en el orden correcto.
      Si estuviste offline mucho tiempo, tal vez haya que deshacer y reaplicar varios días de cambios. El usuario no sabe cuántas transformaciones de árbol ocurren detrás, pero CRDT afecta el diseño de toda la aplicación.
      La mayoría de las apps populares de hoy fueron diseñadas cuando las transformaciones CRDT todavía no se entendían bien.
      [1] https://thymer.com (casi listo para beta)
    • Hoy Notion es un sistema last-writer-wins con apenas algunas operaciones de preservación de intención, como el orden de los bloques en datos de lista.
      El texto es last-writer-wins, y el texto o las propiedades de cada bloque son registros last-writer-wins. Están trabajando en un nuevo formato CRDT para el texto de bloques.
    • Tengo entendido que la mayoría de los servicios de iCloud usan CRDT internamente.
      Incluye Notes y Reminders, y Photos también podría usarlo. También escuché en un bar, de un ex-SRE de Apple borracho, que usan FoundationDB como parte del backend.
    • Linear: https://linear.app/
      También vale la pena ver su charla en Local First Conf: https://youtu.be/VLgmjzERT08
    • Pensándolo un poco más, hay otro ejemplo que la gente no suele tener presente de inmediato.
      Todos los juegos en red que hacen algún tipo de rollback o corrección se acercan a esto. Una modalidad de best effort con rollback como ruta alternativa quizá sea la forma de CRDT ampliamente usada con mejor experiencia de usuario.
      No es un CRDT en el sentido académico estricto. Técnicamente, el estado del juego no está completamente replicado en todos los clientes, porque cada cliente solo recibe un estado parcial del juego.
      Además, los clientes de juego necesitan sincronización de baja latencia, y académicamente eso podría verse como "coordinación". En la práctica, el cliente acepta y renderiza localmente, de forma probabilística, el resultado de las entradas antes de que llegue la resolución de conflictos o la corrección por rollback.
      Habrá quien se ponga quisquilloso, pero al llegar al tercer ejemplo se ve un tema común: los CRDT más populares, usables y bien implementados en realidad rompen las reglas académicas.
      Esta es una trampa típica de los modelos de pensamiento demasiado académicos. Los algoritmos y tipos de datos del mundo real suelen ser mucho más creativos que el "reglamento" académico. Timsort, por ejemplo.
      Si estás construyendo un producto para usuarios reales y no para la revisión de un paper, no caigas en la trampa de la sobreingeniería o el academicismo. Aprende las reglas académicas, rómpelas deliberadamente y, en vez de intentar implementar a la perfección conceptos definidos con una rigurosidad útil solo entre académicos, agrega valor real y haz que sea agradable de usar.

  • Los CRDT son potentes, pero tanto si están basados en operaciones como en estado, lo malo es que dejan rastros de operaciones o elementos pasados.
    Incluso con compresión sigue siendo una desventaja, y es una parte que hace dudar antes de adoptarlos.
    Aun así, gracias a esta discusión me empezó a interesar la posibilidad de implementar algoritmos sin conflictos, o algoritmos de resolución fina de conflictos, sobre almacenamientos basados en archivos como Dropbox o Syncthing.

    • Soy el autor. He tenido muchas veces esta conversación, y también se habla seguido de esto en el ámbito de los CRDT, pero en la práctica, al menos en edición de texto, el overhead es tan pequeño que no creo que llegue a ser un problema real.
      Mi proyecto post-CRDT, Diamond Types, básicamente crece indefinidamente con el tiempo, pero el overhead normalmente es de menos de 1 byte por cada carácter escrito hasta ahora.
      Si activas la compresión LZ4 sobre el texto guardado, los documentos editados con Diamond Types muchas veces son más pequeños que el estado final del documento, aunque guarden todo el historial de edición.
      Técnicamente conozco varias formas de resolver esto, pero no estoy seguro de que en la mayoría de los sistemas sea un problema real.
      Escuché de alguien que tuvo problemas usando yjs en una herramienta de modelado 3D. Fue porque, mientras arrastraba un objeto, creaba una edición persistente por cada movimiento del mouse a nivel de píxel.
      Para ese tipo de trabajo creo que es más sensato usar ediciones temporales, algo que la mayoría de las bibliotecas CRDT no soportan.
      Como referencia, Git tiene el mismo problema. El repositorio crece con el tiempo, y crece mucho más rápido que usando una biblioteca CRDT moderna. Pero parece que a nadie le preocupa demasiado.
      En Git se pueden hacer clones superficiales, pero casi nadie los hace. Si quisieras, podrías hacer lo mismo con CRDT.
    • Si no estás creando un sistema totalmente descentralizado, puedes relajar algunas de las restricciones que exige CRDT.
      Por ejemplo, si puedes garantizar que todos los clientes recibieron los cambios posteriores a la fecha X, entonces puedes descartar de forma segura las operaciones anteriores a esa fecha.
    • Un log de operaciones completo y una fusión determinista encajan bien con un almacenamiento de bloques inmutables, y también pueden tener ventajas de seguridad, rendimiento y costo.
      Estoy creando Fireproof[1] para aprovechar la investigación más reciente en esta área.
      Al direccionar datos inmutables por contenido, hay un beneficio adicional: cada operación puede derivar en una prueba o diferencia garantizada criptográficamente. Se puede imponer consistencia causal y crear referencias estables a snapshots.
      Es decir, puedes ejecutar en el edge o en el navegador una base de datos interactiva, que funciona offline y se fusiona sin pérdidas, y aun así tener la integridad que antes se esperaba de una base de datos central o de una blockchain.
      Por ejemplo, puedes poner un CID de snapshot en un PDF para firmar o en un contrato inteligente, eliminando cualquier ambigüedad sobre el estado referenciado.
      [1] https://github.com/fireproof-storage/fireproof
    • El concepto mismo de CRDT no exige dejar rastros de operaciones o elementos pasados.
      Al final, en lugar de hablar de forma general sobre el conjunto de leyes matemáticas que sigue cierto tipo de dato o base de datos, es más correcto criticar una implementación concreta.
    • Si se puede borrar el historial, me pregunto cuál es la preocupación.

  • Es un artículo de 2021 y parece que también incluye la implementación en Rust de Automerge, así que sería interesante ver benchmarks actualizados.

    • Soy el autor. Yjs también tiene yrs, reescrito en Rust, y es mucho más rápido que la versión en JavaScript.
      También tengo un enfoque nuevo, completamente distinto, para resolver este problema.
      Definitivamente estaría bueno actualizar los benchmarks. Todo se volvió más rápido.

  • Me costó entender buena parte del contenido, pero es de esos artículos raros que están tan bien escritos que uno sigue leyendo sin parar.

  • Estas son discusiones relacionadas anteriores.
    https://news.ycombinator.com/item?id=28017204 (hace 3 años, 151 comentarios)
    https://news.ycombinator.com/item?id=33903563 (hace 2 años, 22 comentarios)
    https://news.ycombinator.com/item?id=41372833 (publicación actual)
    https://news.ycombinator.com/item?id=41373288 (comentario actual)

  • Citando el Readme actual de GitHub[0], dice que desde esa publicación de blog el rendimiento volvió a mejorar entre 10 y 80 veces.
    [0] https://github.com/josephg/diamond-types

  • Me gustaría que alguien explicara por qué los CRDT son lentos.
    Este artículo parece mostrar el futuro: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
    Sería bueno compararlo con Y.js o Automerge: https://github.com/canvasxyz/okra-js

    • Soy el autor. La razón principal es que muchas bibliotecas CRDT fueron escritas por académicos, y ellos no tenían el tiempo, la habilidad ni el interés para optimizarlas.
      Desde que escribí este artículo hace unos años, todas las principales bibliotecas CRDT se volvieron más rápidas por varios órdenes de magnitud.

  • Recuerdo haberme topado con este artículo hace unos años.
    Es un artículo realmente divertido, y uno de mis favoritos de los últimos años.

    • Creo recordar que el título era CRDTs go brrr.

  • Sobre “¿por qué WASM es 4 veces más lento que la ejecución nativa?”, pensé que era porque todas las operaciones con strings tenían que copiarse a la memoria de WASM y, una vez calculado el resultado, copiarse de vuelta a JS.
    ¿Me equivoco? ¿Entendí mal el contexto? Pregunto en serio.

    • Soy el autor. Aunque este artículo es de hace varios años, según recuerdo esa parte estaba controlada. Así que el problema no era FFI.
      Antes de medir el tiempo cargué todo el historial dentro de wasm, y lo procesé en un loop interno escrito en Rust que corría dentro del propio contexto de wasm. Solo había unas dos llamadas a wasm.
      La causa de que fuera 4 veces más lento no era FFI, sino que el código del algoritmo en sí se ejecutaba realmente 4 veces más lento.
      Sería interesante volver a correr el benchmark ahora. La salida wasm de los compiladores mejoró y los runtimes de wasm seguramente también son más rápidos. El código del benchmark probablemente todavía esté en algún lado.
    • Parece una causa plausible.
      Un problema que sigue apareciendo en otro ámbito es que hablar de multithreading no es sencillo, y el soporte de bibliotecas y herramientas tampoco está completo.
      Probé correr en el navegador motores de juegos y binarios de utilidades como ffmpeg o zip, y por eso eran muy lentos.
    • Creo que la mejor pregunta es por qué esperaríamos que ambos fueran iguales.
      Nunca trabajé con intérpretes o JIT de WASM, pero ¿qué tan seguido pasar por varias capas de traducción resulta mejor que pasar por una sola?
      Cuando se traduce código de alto nivel a WASM o a algún lenguaje ensamblador, se pierde mucha de la intención contenida en el código de alto nivel.
      En código de bajo nivel se suele ver una enumeración de modismos específicos del lenguaje para lograr un objetivo, que pueden o no tener una correspondencia directa con la máquina real.
      En x86-64 moderno hay muchísimas instrucciones mucho más potentes que lo que se puede hacer en WASM.
      Claro que existen los descompiladores, y quizá haya una lista de fusiones de macrooperaciones con la que un JIT de WASM pueda generar buen código nativo mediante pattern matching relativamente simple. Probablemente no sea así, y la optimización multiplataforma sería más difícil.
      LLVM tampoco es perfecto, así que sin duda hay partes fáciles que un optimizador posterior podría mejorar. Por lo tanto, en teoría no es imposible hacer que WASM sea más rápido que la salida nativa de LLVM.
      Pero creo que es muy difícil obtener resultados del mismo nivel a menos que haya un plan muy bien diseñado, o que básicamente se cree un conjunto de instrucciones que sea un superconjunto de lo que soporta la arquitectura del conjunto de instrucciones de destino.
      A mi parecer, WASM se parece más a un subconjunto, así que estandarizar operaciones y volver a combinarlas en tiempo real no es fácil. Aunque no sea completamente imposible, requiere un logro de ingeniería considerable.
      Intuitivamente, si traduces un libro escrito en inglés a un idioma muy distinto y limitado a unos pocos miles de palabras, y luego lo vuelves a traducir al inglés, no obtendrás exactamente el mismo texto.
      Habrá casos en los que un concepto que en inglés se expresa con una sola palabra tendrá que explicarse en un párrafo. Para recuperar el inglés original haría falta una traducción 1:1 de todo, o una lista de traducciones de párrafo→una palabra acordada por ambos traductores.