Edición colaborativa de texto: implementarla sin CRDT ni OT

 (mattweidner.com)
4 puntos por GN⁺ 2025-05-23 | 1 comentarios | Compartir por WhatsApp
  • En una app colaborativa basada en un servidor central, si se edita texto con índices de arreglo, las posiciones se desplazan durante la edición simultánea; por eso, se asigna un ID único global a cada carácter y se actualiza el estado del servidor con el esquema “insertar después de un ID específico”.
  • Los CRDT y OT usados en servicios reales son potentes, pero los algoritmos de orden total o las reglas de transformación de operaciones son complejos, lo que dificulta modificar su funcionamiento interno según las necesidades de la app.
  • El enfoque propuesto hace que cliente y servidor mantengan una lista de IDs con la forma Array<{ id: ID; char?: string; isDeleted: boolean }> y conserva también los caracteres eliminados como tombstones, para que no se rompan las referencias a posiciones de inserción posteriores.
  • Las actualizaciones locales optimistas se manejan mediante reconciliación del servidor (server reconciliation): al recibir una operación remota, se deshacen las operaciones locales pendientes y luego se vuelven a aplicar, en orden, la operación remota y las operaciones locales no confirmadas.
  • También cubre el orden de inserciones simultáneas, formatos de texto enriquecido, variantes distribuidas y la biblioteca Articulated, y permite que el servidor defina operaciones flexibles que vayan más allá de insertar y borrar, según la semántica de cada app.

Por qué la edición basada en índices se rompe con la edición simultánea

  • En la edición colaborativa de texto, el cliente envía al servidor las operaciones ingresadas por el usuario, y el servidor debe actualizar su estado autoritativo.
  • Si se ve el texto como un arreglo de caracteres y se envía una operación como insertar " the" en index 17, antes de que llegue al servidor otro usuario puede haber insertado texto, haciendo que el mismo índice apunte a otra posición.
    • Por ejemplo, si Alice inserta " gray" al inicio, el index 17 de Bob ya no corresponde a la ubicación original.
    • El servidor debe rebasar (rebase) la operación de Bob a index 22.
  • La cuestión central es qué operación envía el cliente al servidor y cómo debe interpretarla el servidor para actualizar el texto de una manera “claramente correcta”.
  • Este problema de rebase de índices puede aparecer no solo en apps de colaboración en tiempo real como Google Docs, sino también en formularios web que insertan elementos de lista o en apps locales de un solo hilo que manejan comentarios en línea e historial de edición.

Puntos en los que CRDT y OT son pesados en la práctica

  • Las soluciones existentes se dividen, a grandes rasgos, en CRDT y OT.
    • CRDT asigna a cada carácter un ID inmutable o una “posición”, y ordena los IDs mediante un orden total matemático, como un recorrido especial de árbol.
    • OT transforma las operaciones mismas considerando la edición simultánea; en el ejemplo, cambia insertar en index 17 por insertar en index 22.
  • Ambos enfoques ya se usan en servicios reales.
    • Google Docs usa OT.
    • La biblioteca CRDT Yjs se usa en varias apps.
  • La carga surge de la complejidad conceptual.
    • El orden total de los CRDT para edición de texto suele ser un algoritmo sutil definido en artículos académicos.
    • Los algoritmos OT deben satisfacer “propiedades de transformación” algebraicas; la cantidad de casos crece cuadráticamente y, sin verificación formal, los defectos son frecuentes.
  • Los algoritmos complejos también complican la implementación y, por lo general, terminan usándose bibliotecas hechas por expertos como una caja negra de red.
  • Cuando se necesita una funcionalidad que la biblioteca no esperaba, su estructura monolítica se vuelve un obstáculo.
    • Cargar en memoria solo las partes necesarias de documentos grandes y dejar el resto en disco.
    • Hacer cumplir desde el servidor permisos de subdocumento, como permisos de edición por párrafo o permisos para usar formatos específicos.
    • Mostrar cambios sugeridos al estilo Google Docs dentro del cuerpo del texto o junto a él.
    • Guardar texto en una representación fácil de sincronizar con un almacén clave-valor como Replicache.
    • Soportar operaciones más allá de insertar y borrar, como mover texto, manipular el árbol del documento o dividir y fusionar párrafos.

IDs de caracteres y el enfoque “insert after”

  • La idea básica es asignar a cada carácter un ID único global en lugar de usar índices de arreglo.
    • La estructura de datos central tiene la forma Array<{ id: ID; char: string }>.
    • En vez de insertar en index 17, el cliente envía al servidor una operación como insertar " the" después de f1bdb70a.
    • El servidor busca el ID objetivo e inserta los nuevos caracteres justo después.
  • El cliente también debe especificar los IDs de los nuevos caracteres.
    • Ej.: insertar " the" después de f1bdb70a con ids [...].
    • Si el cliente genera los IDs, puede referenciar esos nuevos IDs en operaciones posteriores de insert after antes de recibir la respuesta del servidor.
  • Si los caracteres eliminados se quitan por completo, se puede perder la posición de inserción.
    • Si Bob intenta insertar después de 26085702 mientras otro usuario borra el carácter 26085702, el servidor no sabrá dónde insertar.
    • El servidor debe mantener también los IDs eliminados en la lista interna.
  • La representación corregida del estado es la siguiente:
Array<{ id: ID; char?: string; isDeleted: boolean }>
  • El texto visible para el usuario puede construirse concatenando solo los elementos que no fueron eliminados:
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')

Manejo de inserciones y eliminaciones

  • Al ingresar un carácter, el comportamiento del cliente y del servidor es simple.
    • El cliente encuentra before, el ID del carácter inmediatamente anterior al punto de inserción.
    • Genera para el nuevo carácter un ID único global id, como un UUID.
    • Envía al servidor una operación para insertar char con id después de before.
    • El servidor busca before, incluyendo los elementos eliminados, e inserta { id, char, isDeleted: false } justo después.
  • La eliminación de caracteres también se maneja con IDs.
    • El cliente encuentra el id del carácter que quiere eliminar.
    • Envía al servidor una operación para borrar el elemento con ese ID.
    • El servidor encuentra ese elemento y, si aún no fue eliminado, establece entry.isDeleted = true.
  • Este enfoque resuelve directamente el problema de posición de las operaciones de edición enviadas al servidor sin seguir artículos de CRDT u OT.
  • Una implementación simple con arreglos puede ser ineficiente porque debe guardar un UUID por carácter; las optimizaciones se tratan en Articulated.

Actualizaciones optimistas y reconciliación del servidor

  • En la edición colaborativa al estilo Google Docs, el usuario debe ver de inmediato el resultado de su entrada sin esperar la respuesta del servidor.
  • El punto difícil aparece cuando el cliente tiene operaciones locales pendientes que el servidor aún no confirmó y, en ese estado, recibe del servidor una operación remota simultánea.
  • En este caso no es imprescindible usar CRDT; puede manejarse con reconciliación del servidor (server reconciliation).
    1. Deshacer todas las operaciones locales pendientes para rebobinar el estado del cliente a la perspectiva del estado anterior del servidor.
    2. Aplicar la operación remota para alinear el cliente con el estado del servidor.
    3. Volver a aplicar las operaciones locales que aún no fueron confirmadas.
  • Una estrategia más simple es Wait for Ack, que prohíbe procesar operaciones remotas cuando hay operaciones locales pendientes.
    • El cliente de Bob puede ignorar el primer mensaje del servidor hasta recibir el estado del servidor donde su propio mensaje ya fue procesado.
    • Si Bob sigue escribiendo o la latencia de red es alta, el retraso puede crecer indefinidamente, por lo que es menos en tiempo real que la reconciliación del servidor.

Diferencias frente a CRDT

  • El enfoque propuesto comparte algunas características con CRDT: asigna IDs a cada carácter y usa una marca isDeleted.
  • La diferencia está en la forma de manejar el orden.
    • En este enfoque, el cliente le dice al servidor inserta X después de Y, y el servidor lo hace tal cual o lo procesa de otra manera definida por el desarrollador.
    • En los CRDT para edición de texto, los IDs se ordenan mediante algoritmos complejos.
  • El factor clave que diferencia a los distintos CRDT de edición de texto es justamente este algoritmo de ordenamiento de IDs, y este enfoque evita esa parte.

Resultado de las inserciones simultáneas

  • Si varios usuarios escriben simultáneamente en la misma posición, el resultado se ordena en el orden inverso al orden en que el servidor recibió las operaciones.
  • Por ejemplo, supongamos que el texto es "My name is" y Charlie ingresa " Charlie", mientras Dave ingresa " Dave" al mismo tiempo.
    • Si la operación de Charlie llega primero, el servidor produce "My name is Charlie".
    • La operación de Dave también inserta después del ID de la s de is, así que el resultado queda como "My name is Dave Charlie".
  • Las operaciones insert after sobre el mismo ID objetivo quedan en orden inverso al de recepción del servidor, incluso si no hay simultaneidad.
  • Aun así, las palabras escritas de izquierda a derecha no se mezclan carácter por carácter.
    • Aunque Dave envíe cada carácter como una operación separada, a se inserta después de D, y v después de a.
    • El estado del servidor cambia como "My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie".
  • En los casos de escritura de derecha a izquierda, si las operaciones de Charlie y Dave llegan al servidor en orden intercalado, el texto resultante también puede intercalarse.
    • En la práctica, esto puede ocurrir cuando dos usuarios están en línea al mismo tiempo e ignoran las ediciones en curso del otro.

El servidor puede definir operaciones más flexibles

  • Al usar reconciliación del servidor, el servidor puede procesar las operaciones del cliente prácticamente de la forma que quiera, y el cliente terminará llegando al mismo estado.
  • Esto contrasta con CRDT y OT, que solo permiten operaciones que satisfacen reglas algebraicas estrictas.
  • Ante inserciones simultáneas en la misma posición, el servidor puede responder de varias maneras.
    • Ignorar esa operación y tratarla como no-op.
    • Agregar el ID a la lista interna, pero marcarlo inmediatamente como eliminado, para que las operaciones posteriores de Dave puedan referenciar el ID anterior.
    • Insertar el texto, pero aplicar a las dos palabras un formato especial para revisión.
    • Convertir la edición de Dave en una “sugerencia” mostrada junto al cuerpo del texto.
    • Preguntarle a un LLM cómo corregir el texto.
  • El cliente también puede enviar operaciones que expresen mejor la intención del usuario.
    • insert before puede usarse al crear un título sobre un párrafo para evitar que el título termine en medio de inserciones simultáneas al final del párrafo anterior.
    • Una operación fix typo puede incluir condiciones como insertar u después de la o de color con ID X, pero solo si la palabra alrededor sigue siendo color.
  • El servidor también puede definir operaciones cuya posición de inserción cambie después de llegar al servidor.
    • Puede reordenar alfabéticamente inserciones simultáneas en la misma posición.
    • Si se agrega una operación move para arrastrar y soltar, un insert after dentro del texto movido puede aplicarse dentro del texto movido, y no en la ubicación original.

Manejo de formatos de texto enriquecido

  • En texto enriquecido se manejan formatos en línea como negrita, tamaño de letra e hipervínculos.
  • Los formatos por rango también pueden expresarse con IDs de caracteres en lugar de índices.
    • Ej.: aplicar bold desde ID X hasta ID Y.
    • Si se define como desde ID X inclusive hasta ID Y exclusive, las inserciones simultáneas al final del rango también pueden quedar en negrita.
  • Si se usa junto con un editor de texto enriquecido como ProseMirror, el servidor puede encontrar los índices actuales en el arreglo de los IDs X e Y, e indicar al estado local de ProseMirror que aplique negrita a ese rango.
  • ProseMirror puede mantener la negrita también en el texto que se inserte después dentro de ese rango.
    • Pero el servidor también puede manejarlo de otra forma según una operación de inserción como bold set to false.
  • Para entender la semántica del texto enriquecido colaborativo, el ensayo Peritext sirve como referencia.

Variantes distribuidas y conexión con CRDT

  • Hasta ahora se asumió que un servidor central define el orden total de las operaciones según el orden de recepción en el servidor y actualiza el estado autoritativo.
  • En apps sin servidor central, o donde el servidor es opcional, se puede asignar un orden total final a las operaciones de forma distribuida.
    • Por ejemplo, ordenando las operaciones con Lamport timestamps.
    • Cada cliente toma como estado autoritativo el resultado de procesar, en orden, las operaciones que recibió hasta el momento.
  • En ese caso, los IDs por carácter y la operación insert after también funcionan en una reconciliación distribuida “sin servidor”.
  • Técnicamente, el resultado se convierte en un CRDT de edición de texto.
    • Porque es un algoritmo distribuido y con consistencia eventual para edición colaborativa de texto.
  • Según el método de ordenamiento usado, se conecta con CRDT existentes.
    • Si se ordenan las operaciones con Lamport timestamps, el orden de la lista resultante es equivalente a RGA / Causal Trees.
    • Si se usan Lamport timestamps junto con operaciones de formato, el comportamiento se parece bastante a Peritext.
    • Si se usa un ordenamiento topológico en profundidad, el orden de la lista resultante es equivalente a Fugue.
  • No se incluye una demostración detallada de estas afirmaciones de equivalencia.

Articulated: biblioteca de apoyo para la implementación

  • En una implementación real, el texto en sí puede guardarse en otro lugar, como el estado de ProseMirror, y este enfoque puede necesitar solo una lista de IDs con la siguiente forma:
Array<{ id: ID; isDeleted: boolean }>
  • En esta lista se necesitan con frecuencia cuatro operaciones.
    • Convertir entre ID e índice actual del arreglo.
    • Insertar un nuevo ID después de un ID especificado.
    • Marcar un ID como eliminado.
    • Serializar y restaurar el estado para almacenamiento.
  • Un arreglo simple no es adecuado para estas operaciones.
    • Las operaciones 1 a 3 tardan tiempo lineal.
    • Almacenar un objeto y un UUID por carácter consume mucha memoria y espacio de almacenamiento.
  • Articulated es una pequeña biblioteca npm que ofrece la misma funcionalidad que este arreglo.
  • Su estructura de datos central, IdList, usa optimizaciones similares a las de bibliotecas CRDT populares para edición de texto.
    • Los IDs tienen la forma { bunchId, counter }, donde bunchId es un UUID que pueden compartir varios IDs.
    • Cuando IDs del mismo bunch están contiguos, como ocurre típicamente al insertar de izquierda a derecha, se almacenan como un solo objeto en memoria y en el estado serializado.
    • La estructura de datos central no es un arreglo, sino un B+Tree, por lo que el tiempo de llamada a sus métodos es log o log^2.
  • IdList también es una estructura de datos persistente (persistent data structure).
    • El cliente puede conservar de forma barata tanto el estado recibido más recientemente del servidor como el estado optimista.
    • Al recibir una operación remota, es fácil hacer rollback al último estado del servidor.
  • Como material adicional, se ofrecen la documentación, demos iniciales y IdListSimple, una implementación simple de menos de 300 SLOC.
  • IdListSimple omite optimizaciones y persistencia, pero es funcionalmente equivalente y está verificada con fuzz tests.

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-05-23
Opiniones en Hacker News

  • Bastante limpio. El algoritmo le asigna a cada carácter de texto un ID único global, como un UUID, para poder referenciarlo de forma consistente a lo largo del tiempo en vez de usar índices de arreglo que cambian constantemente.
    El cliente envía al servidor una operación de “insertar después de” que referencia un ID existente, y el servidor busca el ID objetivo e inserta el nuevo carácter justo después. Al borrar, el carácter solo se oculta visualmente, pero se conserva para calcular las posiciones de “insertar después de”. Incluso fuera de la edición de texto, por ejemplo en sincronización de mundos de juegos, parece tener potencial.

    • Esto es literalmente un CRDT degenerado. La idea de que un servidor central determine el orden de los conflictos existe desde Google Wave.
    • Me pregunto si esto de verdad es tan nuevo. Usar un proceso central para serializar un sistema distribuido es casi el punto de partida obvio, hasta que uno empieza a preocuparse por particiones de red y cosas como CAP. Ahora también tienes un punto único de falla. Lo leí por encima y me pregunto si hablaba de rendimiento.
    • ¿Lo que describe no es un CRDT?
    • Con ctrl+a, ctrl+x, ctrl+v, parece que habrá que cruzar los dedos.

  • Me alegra ver un artículo así. Hace unos años descubrí el mismo método y me preguntaba por qué no aparecía mucho en la literatura académica.
    Eso sí, yo lo implementé como CRDT en un contexto descentralizado para que se mantuvieran propiedades como conmutatividad, idempotencia y asociatividad.

    • Si la idea era crear una alternativa a los CRDT, me da curiosidad qué se ganó al convertirlo en un CRDT.

  • Me sorprendió que no hablara de otras estructuras de datos, como dict/map o arreglos de tipos arbitrarios. Sería bueno que también se pudiera extender fácilmente a eso. Por experiencia, las apps suelen necesitar estructuras de datos colaborativas más a menudo que edición de texto colaborativa pura.
    Los ejemplos de sincronización —validación de actualizaciones, carga parcial y operaciones de alto nivel— son interesantes, pero no me parece muy convincente que Yjs y similares no tengan estas funciones por la implementación CRDT subyacente, o porque de entrada sea difícil construirlas.

    • Totalmente de acuerdo. Si es un arreglo de objetos “atómicos” cuyas propiedades no se pueden cambiar, parece que bastaría con cambiar strings por tu propio tipo. Los cambios dentro de los objetos serían más complicados, aunque quizá también sea un problema de almacenar y recorrer árboles de forma eficiente.
      En términos del OP, siempre pensé que los usuarios de una biblioteca auxiliar deberían poder insertar una lógica ligera de modelo semántico para impedir o administrar estados inválidos. Por ejemplo, un ítem de tareas no debería poder tener isDone: true y al mismo tiempo state: inProgress. Es parecido a la semántica de formato de texto enriquecido de la nota enlazada.
    • Los CRDT, en esencia, funcionan eligiendo determinísticamente un lado cuando surge un conflicto. El problema es que, en general, eso no garantiza que no haya pérdida de datos ni que los datos sean válidos.
      Imagínate que todos los conflictos de merge en Git se resolvieran automáticamente eligiendo un lado. Normalmente daría resultados incorrectos, y a veces incluso código que no compila. Si no hay alguien ahí para corregirlo de inmediato, puede terminar en resultados aún más confusos.
      Por eso creo que los CRDT no se han difundido más. Los CRDT solo arreglan “el problema que uno creía tener”, pero no resuelven el problema real: resolver conflictos preservando los datos, la validez y el significado. De hecho, podría decirse que lo empeoran, porque restringen la resolución de conflictos a métodos que puedan replicarse de forma determinista.

  • La diferencia clave con los CRDT parece ser que, si hay un servidor central, la sincronización —es decir, decidir el orden entre eventos simultáneos— debería hacerla el servidor, no la estructura de datos en sí mediante un orden lexicográfico.
    Como toda la comunicación ocurre solo entre cliente y servidor, y no entre clientes, cuando un cliente se conecta al servidor este puede garantizar que procesará primero todas las operaciones locales de ese cliente antes de enviarle nuevas actualizaciones remotas.

  • ¿El mensaje central de este artículo es que toda la complejidad de CRDT/OT solo es necesaria cuando no hay un servidor central?

    • Incluso sin un servidor central, si existe un método descentralizado para ordenar finalmente las operaciones en un orden total y aplicarlas en ese orden, se puede evitar la complejidad de CRDT/OT: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      Como dicen otros comentarios, técnicamente eso también es un CRDT, y de una forma bastante común. Además, implementar el deshacer y reproducir operaciones tampoco es trivial. Aun así, espero que sea más simple que usar CRDT/OT tradicionales para cada tipo de dato.
    • Ese es el núcleo de los CRDT. Varias réplicas de la misma estructura de datos se mantienen en múltiples nodos, cada réplica se actualiza de forma independiente y al final todas convergen.
    • OT requiere un servidor central.

  • No soy experto en este campo, pero la principal diferencia con CRDT como Automerge parece ser la coordinación del servidor. Por ejemplo, si ves este artículo [1], Automerge usa números de secuencia para manejar inserciones concurrentes, y cuando las inserciones ocurren al mismo tiempo depende de un orden acordado de IDs de agentes. En cambio, este enfoque depende de que el servidor procese en orden de llegada.
    El artículo dice: “En los CRDT de edición de texto, un algoritmo sofisticado decide el orden de los IDs. Ese algoritmo de ordenamiento es lo que diferencia a muchos CRDT de edición de texto, y es la parte compleja de los papers sobre CRDT. Nosotros lo evitamos por completo”. Como muchas apps de todos modos tienen un servidor central, tiene sentido que se pueda evitar ese “algoritmo sofisticado”. Aun así, la coordinación del servidor requiere deshacer y reproducir ediciones locales, así que no estoy 100% seguro de que sea mucho más simple. [1] https://josephg.com/blog/crdts-go-brrr/

    • Estoy de acuerdo en que deshacer y reproducir tampoco es precisamente simple. Un B+Tree persistente tampoco es algo muy simple.
    • Tengo entendido que Automerge internamente termina almacenando todas las operaciones en un orden total consistente, y eso podría usarse como sustituto del servidor en la coordinación del servidor: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      Pero Automerge en realidad no lo hace así, sino que maneja las operaciones de texto con RGA, un CRDT tradicional. Probablemente, como señalas, porque implementar el deshacer y reproducir operaciones no es fácil.

  • Entonces, ¿es un CRDT sin optimizar? ¿Algo como fijar el tamaño máximo del conjunto en 1 y tirar para adelante?

    • Me resulta atractivo porque parece una especie de complejidad irreducible. Es más cercano a lo que realmente ocurre y es simple. Como dices, probablemente no esté optimizado.

  • Por el uso de coordinación del servidor, la coordinación del lado del cliente parece que sería difícil. ¿Cómo mantener una UX de editor fluida mientras se aplican las actualizaciones del servidor cada vez que llegan?
    Por ejemplo, si falla una solicitud del cliente para insertar un carácter, ¿simplemente se reintenta? ¿Y si mientras tanto llegaron actualizaciones? Edición: en la sección “Client-Side” reconoce este caso y propone rebobinar y luego reproducir, además de una opción más simple: bloquear hasta que se vacíe la cola de espera. Desde el punto de vista del frontend, podría haber una larga cola de excepciones de UI/UX no especificadas, así que en conjunto quizá los CRDT sean más simples. Y también me pregunto cómo se sentiría editar en el metro de Nueva York, donde la conexión se corta fácilmente.