cola: tecnología CRDT de texto para edición colaborativa en tiempo real

• cola es un CRDT de texto para edición colaborativa en tiempo real escrito en Rust, enfocado en hacer que documentos modificados simultáneamente por varios pares converjan al mismo estado sin un coordinador central
• Fija las posiciones del documento con un Anchor en formato ReplicaId.n, en lugar de simples offsets, para evitar que el significado de una posición cambie por ediciones simultáneas
• Los conflictos de inserción se manejan de forma consistente ordenando por Lamport timestamp y ReplicaId, mientras que las eliminaciones gestionan las condiciones de integración con tombstones y version vectors en lugar de borrar físicamente
• En la implementación, usa RLE basado en EditRun y un G-tree representado con índices de Vec, buscando búsquedas e inserciones en tiempo logarítmico dentro del modelo seguro de ownership de Rust
• En benchmarks, cola se comparó con diamond-types, automerge y yrs; en upstream es entre 1.4 y 2 veces más rápido que diamond-types, y también muestra un rendimiento muy alto en downstream

---

El problema de edición colaborativa que aborda cola

• cola es un CRDT de texto escrito en Rust, diseñado para que varias réplicas converjan al mismo estado sin una autoridad central en edición colaborativa en tiempo real
• Sobre la capa de red solo hace el supuesto mínimo de que todas las ediciones eventualmente llegarán a todos los pares
  • Las ediciones pueden transmitirse varias veces
  • Las ediciones pueden llegar en cualquier orden
  • Todos los pares deben recibir eventualmente todas las ediciones
• El objetivo no es solo que el estado del documento sea el mismo después de recibir todas las ediciones, sino también que, desde la perspectiva del usuario, el documento resultante tenga una forma razonable

Fijar posiciones con Anchor en lugar de offsets

• Las ediciones basadas en offsets, como insert "abc" at offset 8, pueden cambiar de significado si otro par modifica simultáneamente una zona anterior, lo que puede hacer que las réplicas diverjan
• cola referencia las posiciones del documento mediante identificadores estables, no por contenido de caracteres ni por offsets
  • Cada par asigna un número incremental a los caracteres que inserta
  • Cada par tiene un identificador único, ReplicaId
  • El par ReplicaId.n se convierte en el identificador único de posición de un carácter, Anchor
• El valor n puede garantizar unicidad mediante el incremento de un contador local, pero sin un servidor central es difícil garantizar la unicidad global de ReplicaId
  • cola asume el uso de enteros aleatorios tan grandes que la probabilidad de colisión sea despreciable, como con UUID
• Una inserción especifica su posición con un solo Anchor, y una eliminación especifica un rango con dos Anchor, uno de inicio y otro de fin

Ordenar los conflictos de inserción en el mismo orden

• Cuando llegan varias inserciones al mismo Anchor, cola determina el orden con un Lamport timestamp
• El Lamport clock se actualiza con las siguientes reglas
  • Al insertar texto localmente, el clock aumenta en 1
  • Al recibir una inserción remota, se establece en max(current, remote_timestamp) + 1
• Si una inserción A se creó en un entorno que ya había integrado una inserción B, el Lamport timestamp de A será mayor que el de B
• Las inserciones en conflicto se ordenan por Lamport timestamp descendente
• Para inserciones simultáneas que tienen el mismo Anchor y el mismo Lamport timestamp, no hay un orden más correcto desde la perspectiva del usuario, por lo que se ordenan por ReplicaId ascendente para mantener la consistencia entre pares

Las eliminaciones se procesan con tombstones y version vectors

• Una eliminación convierte los offsets de inicio y fin en Anchor y luego los propaga a otros pares
• Si dos pares eliminan simultáneamente la misma zona, salvo que se considere undo, el resultado es el mismo que eliminarla una vez
  • cola actualmente no soporta undo de eliminaciones
• El procesamiento de eliminaciones tiene tres dificultades
  • Si el texto eliminado se remueve por completo, el Anchor de una edición que aún no llegó podría estar dentro de esa zona
  • Si una eliminación remota se integra demasiado pronto, el contenido que veía el par que creó la eliminación y el contenido del par receptor pueden diferir, haciendo que las réplicas diverjan
  • Incluso dentro del rango eliminado, no deben eliminarse caracteres que el par que creó la eliminación aún no había visto
• El primer problema se resuelve con tombstones
  • Los caracteres eliminados permanecen en el documento, pero se marcan como eliminados
  • Este enfoque aumenta el uso de memoria
• Los demás problemas se resuelven incluyendo un version vector en el mensaje de eliminación
  • La clave es ReplicaId, y el valor es el último timestamp de carácter que el par que creó la eliminación había visto en ese momento
  • La integración de la eliminación se espera hasta que el version vector del par receptor sea mayor o igual que el version vector del mensaje de eliminación
  • Los caracteres con timestamp mayor que el timestamp del version vector de eliminación se omiten del objetivo de eliminación
• En cola, al version vector se le llama version map

Separación entre Replica y el búfer de texto

• El estado local del documento de cada par se representa en cola como Replica
• El algoritmo CRDT de cola no necesita conocer el contenido real de las cadenas
  • Las funciones de la API no reciben cadenas como argumentos
  • cola solo maneja bloques numéricos, no el contenido del documento
• Este diseño separa el mecanismo CRDT de la implementación real del búfer de texto

Reducir metadatos con RLE y EditRun

• Como agregar metadatos a cada carácter dificulta construir una implementación de alto rendimiento, cola agrupa bloques con timestamps consecutivos mediante run-length encoding
• Por ejemplo, si se pega completa la página de Wikipedia sobre el Manhattan Project, puede representarse como un solo bloque en lugar de 107,000 bloques
• Incluso cuando se escribe una oración carácter por carácter sin mover el cursor ni eliminar texto, puede representarse como un solo run en lugar de crear un bloque por cada pulsación
• En cola, estos bloques consecutivos se llaman EditRun
  • Una vez que un EditRun se rompe, queda fijo durante la vida del documento y ya no se expande
  • Un run que aún no se ha roto está en estado active
• Si se inserta texto en medio de un EditRun existente, el run se divide en dos y el nuevo texto se coloca entre ambos
• Cuando se elimina texto, esa parte se separa del run y se marca como tombstone
  • Los runs eliminados también pueden usar RLE de la misma manera, reduciendo la carga de memoria de los tombstones

De listas enlazadas a B-tree

• La ruta upstream de una edición local es el proceso de convertir una edición basada en offsets en una edición que pueda enviarse a otros pares
  • Tanto inserciones como eliminaciones deben encontrar el run que contiene el offset y crear un Anchor
  • Si es necesario, el run se divide en hasta 2 partes para inserciones y hasta 3 para eliminaciones
• En una lista enlazada, dividir un run es O(1), pero encontrar el run que contiene el offset requiere escanear desde el inicio, por lo que toma tiempo lineal
• Si se cachean el run active actual y su offset, las ediciones repetidas en la misma posición son rápidas, pero el peor caso sigue siendo lineal
• cola considera una estructura B-tree para lograr rendimiento logarítmico en el peor caso
  • Los runs se representan como hojas del B-tree
  • Un inode almacena sus hijos y la suma de las longitudes de esos hijos
  • Los runs tombstone contribuyen con longitud 0
  • La longitud de la raíz es igual a la longitud total del documento
• Un B-tree puede hacer búsquedas e inserciones en O(log n), lo que permite procesar ediciones locales en tiempo logarítmico
• Sin embargo, para convertir eficientemente Anchor -> run en ediciones remotas, hay que encontrar la hoja que contiene el Anchor

G-tree: B-tree representado con índices de Vec

• Solo con punteros a las hojas de un B-tree común es difícil saber cómo bajar hasta una hoja durante el proceso de inserción top-down
• Las operaciones bottom-up necesitan punteros al padre de cada nodo, y en el modelo seguro de ownership de Rust eso requeriría estructuras como Rc<RefCell<_>>, que pueden volverse lentas y complejas
• cola almacena todos los nodos en un arreglo dinámico como Vec, y representa las referencias entre nodos no como punteros sino como índices
  • El vector posee todos los nodos
  • Cada nodo puede almacenar el índice de su padre
  • Es posible navegar en ambos sentidos sin código unsafe
• Esta estructura depende del supuesto de que los índices de los nodos no cambian
  • Los nodos nuevos se agregan al final del vector con append
  • Como cola no elimina runs y los marca como tombstone, no surge el problema de invalidación de índices
• A esta estructura de árbol grow-only dentro de un vector, cola la llama G-tree
• El código Rust de G-tree mantiene la estructura padre-hijo de un B-tree, pero cambia solo la representación en memoria

Características de rendimiento que produce G-tree

• G-tree realiza búsquedas e inserciones top-down en tiempo logarítmico, como un B-tree
• LeafIdx, el índice de vector de una hoja, puede usarse como identificador estable de hoja
• El run active actual puede cachearse como LeafIdx en lugar de como puntero
  • Si se editan repetidamente las mismas posiciones del cursor, se expande el run active y solo se actualizan las longitudes de los ancestros hasta la raíz
  • Puede procesarse con unas pocas comparaciones de enteros y de 2 a 4 sumas de enteros, sin recorrer el árbol ni hacer nuevas asignaciones
• El G-tree de cola usa un branching factor de 32, y la ocupación promedio de un inode es de alrededor de 20 hijos
  • Con solo 4 niveles normalmente puede almacenar unos 160k EditRun distintos
  • Después de procesar el trace de edición automerge-paper, el G-tree de cola tiene unos 15k EditRun
  • Ese trace incluye 260k ediciones y fue registrado durante varios días
• Como los nodos de G-tree ya están almacenados en memoria lineal, la serialización y deserialización también son simples

Convertir Anchor a LeafIdx

• La ruta downstream de una edición remota es el proceso de convertir ediciones basadas en Anchor, como insert 2.3..7 at 1.2 o delete between 3.4 and 2.2, en ediciones por offset para el documento local
• Como G-tree puede navegar hacia arriba y hacia abajo, si se conoce el LeafIdx del run que contiene cierto Anchor, se puede calcular el offset correspondiente
• La clave es la conversión Anchor -> LeafIdx
• Un diseño simple consiste en mantener un G-tree o B-tree auxiliar, cuyas hojas almacenen ReplicaId, temporal range y el LeafIdx del G-tree principal
  • Las hojas se ordenan completamente por ReplicaId y temporal range
  • A partir del Anchor se puede descender por el árbol para encontrar el LeafIdx buscado
  • Tanto la búsqueda como la inserción son O(log n)
• El código fuente real de cola no usa tal cual este enfoque de G-tree auxiliar
  • La implementación real tiene búsqueda e inserción en O(log f)
  • f es el número de fragmentos en que se dividió con el tiempo el EditRun que contiene el Anchor
  • f siempre es menor o igual que n, y por lo general mucho menor

Estado actual y trabajo pendiente

• El diseño de cola cuenta con una base orientada a convergencia, preservación de intención y rendimiento
• Para estar listo para producción, todavía quedan el soporte de undo/redo y algunas tareas adicionales

Benchmark de CRDT en Rust

• cola se comparó con 3 CRDT basados en Rust
  • diamond-types
  • automerge
  • yrs
• El benchmark mide el tiempo para procesar traces reales de edición character-by-character
  • Usa la biblioteca de benchmarking de Rust criterion
  • Mide tanto upstream como downstream
  • El código del benchmark está en crdt-benches
• La gráfica toma como línea base 100 veces el rendimiento de cola, y no muestra mediciones que sean más de 100 veces más lentas que cola
• El entorno de ejecución fue una MacBook Pro 2018, Intel Core i7 de 6 núcleos a 2.2 GHz
  • En otras máquinas las cifras pueden variar, pero se espera que el rendimiento relativo sea similar

Resultados del benchmark

• En dirección upstream, yrs y automerge superan la línea base
• En upstream, cola es entre 1.4 y 2 veces más rápido que diamond-types
• En dirección downstream, diamond-types falló en todos los traces y no se obtuvieron mediciones
  • Se aclara que, si fue un mal uso de la biblioteca, los resultados se actualizarán
• En downstream, cola es aproximadamente 2 veces más lento que antes
  • Es un resultado esperado, porque integrar ediciones remotas suele ser más costoso que generar ediciones locales
• cola funciona en ambas direcciones a un nivel similar o superior al de bibliotecas rope rápidas, y se evalúa actualmente como la implementación de CRDT de texto más rápida

[GN⁺]

Opiniones de Hacker News

• Sigo viendo a G-tree como un B-tree con punteros al padre agregados.
  Que se almacene en un arreglo es solo una cuestión de representación; no cambia la estructura de forma fundamental.
  Sigue almacenando punteros, solo que no en unidades de bytes, sino en unidades del tamaño de nodo, y son posiciones relativas no desde el inicio del espacio de direcciones, sino desde el primer elemento del arreglo.
  Por ejemplo, incluso un árbol binario completo almacenado en un arreglo sin referencias explícitas, donde los hijos del índice x están en 2x + 1 y 2x + 2, no deja de llamarse árbol binario; es solo una representación implícita.

  • Aun así, hablar de la forma de representación es útil.
    Especialmente en lenguajes que te empujan más hacia referencias relativas y autogestionadas que hacia referencias absolutas.
    Una representación de árboles que me pareció interesante es guardar los nodos en un arreglo plano en orden de recorrido en profundidad.
    Si es de solo lectura y el lector de todos modos va a recorrerlo en profundidad, puede ser bastante eficiente.
    Me hace pensar en S-expressions y HTML.

• Si no se me escapó algo en la API, esto parece no soportar rangos de formato como negrita o cursiva.
  Hasta donde sé, en algoritmos CRDT para texto enriquecido, Peritext sigue siendo el estado del arte https://www.inkandswitch.com/peritext/
  Sería bueno que este proyecto incorporara también las capacidades de texto enriquecido del algoritmo Peritext.

  • Como alguien que sigue con cierto interés el campo de los CRDT, siempre me he preguntado si se podría crear un CRDT de datos estructurados más general.
    Sería una forma de que el usuario defina un modelo o esquema que describa estados semánticamente válidos.
    Por ejemplo, si simplemente fusionas JSON, puedes terminar con un estado sintácticamente válido pero semánticamente absurdo.
    Así como el algoritmo Peritext sabe que negrita, cursiva y subrayado son operaciones acumulativas, pero el color de resaltado no lo es, me gustaría que el usuario pudiera declarar en el esquema que state: notStarted y completionDate: 2023-09-04 no pueden coexistir.
  • Pregunta: el artículo dice que Cola solo aborda ediciones sin conflicto sobre tipos de datos desconocidos y que, en la práctica, solo trata con un flujo de caracteres y posiciones.
    Entonces, ¿no se podría representar el formato dentro del propio texto, como en HTML?
    No conozco tan bien otras representaciones de texto enriquecido, así que no estoy seguro.
    Además, al ver el documento de Peritext enlazado arriba, vi que justamente trata estas dificultades propias de RTF, y me pareció bastante interesante.

• ¿Hay diferencias de rendimiento o funcionalidad frente a Automerge o Y.js/Yrs?

  • La “tercera parte” del artículo empieza con “comparé cola con otros 3 CRDT implementados en Rust: diamond-types, automerge y yrs”.
    Esta biblioteca cola parece tener bastante ventaja en velocidad de operaciones.
    También me interesa el uso de memoria.

• No hay que confundirlo con el trabajo del mismo nombre de Ian Piumarta.
  https://www.piumarta.com/software/cola/
  https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

  • O también están los Cache Oblivious Lookahead Arrays, que en algún momento se consideraron una alternativa a MergeTree (LSM), pero que ya no se usan https://github.com/giannitedesco/cola
  • También existe coda.io, una app estilo clon de Notion.

• Es un trabajo bien hecho, pero no parece un benchmark justo.
  No calcula ni almacena operaciones, y tampoco almacena el texto real.
  Para construir sobre esto un CRDT de texto que soporte actualizaciones delta, el usuario tendría que almacenar OpID => Text en una estructura aparte, y ese costo no es bajo.

• Si se usa el crate slotmap (https://docs.rs/slotmap/latest/slotmap/), se podría soportar eliminación sin preocuparse por desplazamientos de índices ni por que un “índice” apunte a otro valor.
  En slotmap a eso lo llaman clave, y la clave también incluye un número de versión.

  • ¿Funcionaría también en el contexto de CRDT?
    Me da curiosidad porque ordenar es difícil y la versión podría tener sentido solo localmente.

• Estoy pensando en probar esto en un proyecto que Etherpad y Word no pudieron manejar.

• Si se supone que todos los clientes conectados reciben todas las ediciones, ¿no se podría poner el hash esperado del estado existente del texto antes del offset y de los comandos de inserción/eliminación/reemplazo?
  Así casi se podría garantizar que la edición solo se aplique al estado adecuado, y los cambios posteriores podrían acumularse en un diccionario usando como clave el “hash del estado de los datos al que se espera que se aplique”.
  Claro que habría que calcular hashes repetidamente sobre los mismos datos, así que el costo sería alto, pero sería muy simple de entender e implementar.

  • Con ese enfoque, las ediciones asíncronas nunca se aplicarían.
    Si yo hago una edición local en el documento y tú haces una edición remota, el hash de tu “estado esperado” nunca volverá a coincidir con el estado de mi documento.
    Porque yo ya hice un cambio local.
    Para que un CRDT garantice convergencia, sí, todos los clientes deben recibir todas las ediciones, pero la propiedad de no tener que aplicar las actualizaciones en un orden específico es importante en casos reales de uso distribuido.

• Me pregunto si hay una forma sencilla de activar la edición colaborativa de formularios en el navegador.
  Sería ideal que, si dos personas abren la misma página o formulario, se vea qué campo de entrada está editando la otra persona, y que en los campos de texto se use un CRDT de texto.
  Intenté implementar algo parecido con Yjs, pero fue bastante difícil y no funcionó bien.

  • Me da curiosidad por qué Yjs no encajó.
    Parece ideal para ese caso de uso.