CRDTs más rápidos (2021)

CRDT 5000 veces más rápidos: una aventura de optimización

Introducción

• Hace algunos años, investigadores franceses publicaron un artículo comparando algoritmos de edición colaborativa en tiempo real
• Implementaron varios algoritmos y evaluaron su rendimiento con benchmarks
• Algunos algoritmos tardaban más de 3 segundos en una simple operación de pegado
• El algoritmo problemático era el que usaba ShareJS

Causa del problema

• En el artículo, al pegar textos grandes, el procesamiento se dividía en 1000 operaciones individuales
• Ese no era un problema del algoritmo en sí, sino de la implementación

El atractivo de los CRDT

• Los CRDT (Conflict-Free Replicated Data Types) permiten que varios usuarios editen datos al mismo tiempo
• Se puede trabajar localmente sin latencia y, al sincronizar, mantienen la consistencia automáticamente
• También pueden funcionar sin un servidor central

Problemas de Automerge

• Automerge es una librería para edición colaborativa basada en el algoritmo RGA
• Administra cada carácter del documento con un ID único y, al insertar, especifica un elemento padre
• Por problemas de rendimiento, tardaba 5 minutos en procesar 260,000 operaciones de edición
• El uso de memoria también era muy alto

Optimización del rendimiento

• Los problemas de rendimiento de Automerge se debían a una estructura de datos compleja basada en árboles y al uso de Immutablejs
• Yjs mejora mucho el rendimiento usando una sola lista plana
• Yjs usa caché para encontrar la posición de inserción y una lista doblemente enlazada para procesar inserciones de forma eficiente
• Yjs es 30 veces más rápido y además usa menos memoria

El cambio a Rust

• Rust permite controlar el layout de memoria, lo que puede mejorar aún más el rendimiento
• Con una nueva implementación de CRDT llamada Diamond types, se logró un rendimiento 5 veces superior al de Yjs
• Diamond, implementado en Rust, procesa 260,000 operaciones de edición en apenas 56 milisegundos

Conclusión

• Con estructuras de datos optimizadas y una gestión eficiente de memoria, se puede mejorar enormemente el rendimiento de los CRDT
• Usar un lenguaje de bajo nivel como Rust permite alcanzar un rendimiento todavía mayor

Resumen de GN⁺

• Los CRDT son una herramienta poderosa para el futuro de la edición colaborativa, ya que pueden mantener la consistencia incluso sin un servidor central
• Los problemas de rendimiento de Automerge se debían a una estructura de datos compleja y a un uso ineficiente de la memoria
• Yjs y Diamond types mejoran mucho el rendimiento al usar estructuras de datos simples y eficientes
• Usar un lenguaje de bajo nivel como Rust permite alcanzar un rendimiento todavía mayor
• Al desarrollar herramientas de edición colaborativa, vale la pena considerar Yjs y Diamond types

[GN⁺]

Comentarios en Hacker News

• La razón por la que 32 entradas son las más eficientes es que la línea de caché es de 64 bytes

  • Si se usan enteros de 2 bytes, 32 entradas caben exactamente en una sola línea de caché, lo que puede reducir las transferencias desde la memoria principal

• Es difícil encontrar ejemplos de aplicaciones reales que usen CRDTs y ofrezcan una buena experiencia

  • Notion se siente menos usable que Google Docs cuando dos personas escriben una nota al mismo tiempo

• Los CRDTs son potentes, pero tienen la desventaja de conservar operaciones históricas (o elementos)

  • Incluso con compresión, esto sigue siendo una desventaja y genera preocupación sobre su adopción
  • Aun así, resulta interesante la posibilidad de implementar algoritmos sin conflictos en proveedores de almacenamiento basados en archivos (Dropbox, Syncthing, etc.)

• Cita actual del Readme de GitHub:

  • Desde la publicación del blog, el rendimiento mejoró entre 10 y 80 veces

• Aunque el contenido de este artículo es difícil, está tan bien escrito que no podía dejar de leerlo

• Al ver que usaron una jerarquía, surgió la duda de por qué no usaron conjuntos anidados

  • No hay idea de si la ganancia en las operaciones de lectura compensaría la pérdida en las operaciones de inserción

• Me topé con esta publicación por casualidad hace unos años

  • Ha sido una de las publicaciones más divertidas que he leído en los últimos años

• Me intriga por qué WASM es 4 veces más lento que la ejecución nativa

  • Pensé que era porque todas las operaciones con cadenas tienen que copiarse a la memoria de WASM y, después de calcular el resultado, volver a copiarse a JS
  • Me pregunto si estoy entendiendo mal ese contexto

• Como la implementación en Rust de Automerge ya está terminada, sería interesante ver benchmarks actualizados