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

• Se presenta un nuevo enfoque para resolver el problema de la edición colaborativa de texto, posible de implementar sin algoritmos complejos
• Evita la complejidad y las limitaciones de los enfoques CRDT y OT existentes, usando un método simple de inserción basado en IDs
• Con este método, el servidor procesa directamente instrucciones sobre 'qué insertar y dónde', lo que le da mayor flexibilidad
• Para las actualizaciones locales optimistas, se usa una estrategia de reconciliación con el servidor para resolver los problemas de sincronización de estado
• Con escalabilidad y facilidad de comprensión, este enfoque propone una alternativa que puede implementarse directamente en apps colaborativas existentes

---

Collaborative Text Editing without CRDTs or OT

Planteamiento del problema

• La edición colaborativa de texto es una funcionalidad muy difícil, especialmente en edición simultánea, donde aparece el problema de distorsión de índices de texto (index rebasing)
• Los enfoques existentes, CRDT (tipos de datos replicados sin conflicto) y OT (transformación operacional), se basan cada uno en modelos matemáticos complejos
  • CRDT: sigue cada carácter con un ID y lo ordena con una estructura basada en árbol
  • OT: reajusta dinámicamente los índices para reflejar la entrada de otros usuarios
• Ambos enfoques dependen mucho de librerías y son difíciles de personalizar para las necesidades del desarrollador

Nuevo enfoque

Idea central

• Cada carácter se marca con un ID único (UUID), y el cliente envía al servidor una instrucción del tipo “inserta cierto carácter después de cierto ID”
• Ejemplo: "insert ' the' after f1bdb70a" → f1bdb70a es el ID del carácter objetivo de la inserción
• El servidor lo interpreta tal cual y realiza la inserción, evitando conflictos

Manejo de eliminaciones

• Incluso al borrar un carácter, ese ID permanece en la lista interna y se maneja con una bandera isDeleted
• No aparece en el texto visible para el usuario, pero la referencia se conserva para operaciones futuras

Procesamiento del cliente y actualizaciones optimistas

• Como el usuario debe ver el resultado justo después de escribir, se refleja localmente antes de la respuesta del servidor (actualización optimista)
• Se usa una estrategia de reconciliación con el servidor para:
  1. Revertir todas las operaciones locales aún no confirmadas
  2. Aplicar las operaciones del servidor
  3. Volver a aplicar las operaciones locales para asegurar el estado final sincronizado

Diferencias frente a los enfoques existentes

• CRDT incorpora algoritmos de ordenamiento automático de IDs, mientras que este enfoque solo envía al servidor la posición de inserción explícita
• Como resultado, es más simple y ofrece un comportamiento más claro y predecible

Manejo de inserciones simultáneas

• Ejemplo: en “My name is”, dos usuarios insertan simultáneamente “ Charlie” y “ Dave” en la misma posición
  • Según el orden en que el servidor las reciba, el resultado será “My name is Dave Charlie”
• Esto se considera un comportamiento natural y evita el fenómeno de mezcla a nivel de caracteres (interleaving) que aparece en algunos CRDT

Soporte para operaciones flexibles

• Además de insert/delete, se pueden soportar varias operaciones:
  • insert-before
  • inserción bajo cierta condición (agregar “u” solo si existe “color”)
  • reajuste de posición en drag & drop, etc.
• Esta flexibilidad no queda atada a propiedades matemáticas predefinidas

Soporte para texto enriquecido

• Se puede aplicar formato definiendo rangos basados en IDs (“negrita desde el ID X hasta el ID Y”, por ejemplo)
• Al integrarlo con editores como ProseMirror, es posible resolver conflictos de forma sencilla
• Se pueden añadir funciones de texto enriquecido manteniendo intacta la estructura base

Versión distribuida (Decentralized)

• Incluso sin un servidor central, si se ordenan las operaciones con base en marcas de tiempo de Lamport, puede funcionar con el mismo enfoque
• En ese caso, muestra resultados similares a CRDT como RGA, Peritext y Fugue
• Incluso sin árboles ni pruebas matemáticas, puede lograr consistencia a nivel de CRDT

Librería auxiliar: Articulated

• Es una librería para manejar eficientemente estructuras del tipo Array<{ id, isDeleted }>
• En lugar de UUID, usa una estructura { bunchId, counter } para optimizar memoria
• Con una estructura basada en B+Tree, permite búsquedas e inserciones rápidas por ID
• Al ser una estructura de datos persistente, encaja bien con la reconciliación con el servidor

Conclusión

• Este enfoque es más fácil de entender e implementar directamente que CRDT/OT
• Permite aplicar con libertad distintas funciones de edición, permisos, restricciones y formato, por lo que resulta conveniente para implementar editores colaborativos reales
• La librería Articulated se ofrece como una herramienta útil para llevar este enfoque a la práctica

[GN⁺]

Comentarios de Hacker News

• Este algoritmo se ve bastante elegante. Explica un enfoque donde a cada carácter se le asigna un ID único global, por ejemplo un UUID, para poder referenciarlo de forma consistente en cualquier momento; el cliente le dice al servidor que inserte un carácter después de cierto ID, y el servidor procesa la inserción en esa posición; las eliminaciones solo se ocultan en pantalla, pero internamente se conservan para seguir sirviendo como referencias de posición. También se imagina que este enfoque podría usarse no solo para edición de texto, sino en otras áreas como la sincronización de mundos de juego.

  • Esto parece ser esencialmente un CRDT simplificado; la forma de resolver empates y el uso de un servidor central recuerdan a la arquitectura de la época de Google Wave.
  • Se plantea la duda de si lo descrito no es, de hecho, un CRDT.
  • También hubo quien dijo que en realidad no tiene nada de muy novedoso: usar un proceso central para serializar un sistema distribuido es una forma tradicional de hacerlo, y siguen existiendo problemas como las particiones de red (CAP, etc.) o el punto único de falla. Añaden que les gustaría saber si el artículo habla del rendimiento.
  • Bromean con “buena suerte” para operaciones masivas de seleccionar/copiar/pegar como ctrl+a, ctrl+x y ctrl+v.

• Se comparte la idea de que la diferencia frente a un CRDT está en que el servidor central asume el rol de sincronización, incluyendo el ordenamiento, por lo que no hace falta imponer de antemano un orden fijo en la estructura de datos real. Como solo hay comunicación entre clientes y servidor, el servidor puede procesar por completo las operaciones locales del cliente antes de enviar actualizaciones remotas.

• A alguien le sorprende que no se hable de otras estructuras de datos como dict/map o arreglos de tipos arbitrarios. En las aplicaciones reales suele hacer más falta una variedad de estructuras colaborativas que edición colaborativa de texto puro. Mencionan ejemplos interesantes como validación de datos, carga parcial u operaciones de más alto nivel, y opinan que si herramientas como Yjs no ofrecen esas funciones, probablemente no sea por culpa del CRDT en sí, sino porque esas funciones ya son difíciles de implementar de por sí.

  • Otra persona coincide profundamente con el punto sobre múltiples estructuras de datos: al crear un arreglo de objetos “atómicos”, si no se permite modificar las propiedades del objeto, basta con cambiar el tipo en vez de usar cadenas, y los cambios internos del objeto solo son un poco más complejos porque implican problemas de recorrido y almacenamiento en árbol. También esperan que, del lado del usuario de la librería auxiliar, se pueda conectar lógica propia de “modelo semántico” a modo de hooks para prevenir estados inválidos, por ejemplo un todo con isDone: true y a la vez state: inProgress. Lo relacionan con el formateo de texto enriquecido mencionado en el artículo enlazado.

  • Los CRDT fusionan conflictos eligiendo un lado de forma consistente, pero el problema es que eso puede producir pérdida de datos o datos inválidos. Lo comparan con resolver un conflicto de git merge eligiendo siempre un solo lado: en la mayoría de los casos terminarías con resultados incorrectos o errores de compilación. Señalan que una resolución automática por sí sola puede no preservar bien la originalidad ni el significado de los datos, y creen que esa es una de las razones por las que los CRDT todavía no se usan de forma más amplia.

• A alguien le pareció muy entretenido el artículo que explica este enfoque, y dice que también usó algo parecido hace tiempo; le parece curioso que casi no se mencione en la academia. Cuenta que en su caso lo implementó como un CRDT en un entorno descentralizado, de modo que pudiera conservar propiedades como asociatividad, inmutabilidad e intercambiabilidad.

  • Le preguntan qué beneficios concretos obtuvo al desarrollarlo como alternativa a un CRDT.

• Alguien intenta resumir el mensaje principal del texto como: ¿solo hace falta un CRDT/OT realmente complejo cuando no hay un servidor central?

  • Responden que incluso sin un servidor central, si en un esquema distribuido existe alguna forma de acordar y aplicar un orden global de las operaciones, se puede evitar la complejidad de CRDT/OT. Comparten un artículo enlazado y aclaran que eso también sigue siendo una forma de CRDT, aunque más general. Subrayan, eso sí, que implementar undo/replay no es nada trivial, pero que puede ser una alternativa a considerar cuando las estructuras tradicionales de CRDT/OT se sienten todavía más complejas.

  • Se menciona que OT (Operational Transformation) sí requiere un servidor central.

• Esencialmente también entra en la categoría de CRDT, solo que aquí el servidor central define el orden de las operaciones aplicadas al documento. Google Docs y Zoho Writer también usan un enfoque de OT + servidor central. Reconocen que la propuesta tiene estilo CRDT, pero que en la práctica es más útil para servicios basados en servidor central.

• Según otra opinión, la principal diferencia frente a CRDT como Automerge está en cómo coordina el servidor. Automerge ordena inserciones concurrentes según una secuencia definida por número de secuencia e ID de agente, mientras que aquí el servidor procesa según el orden en que van llegando. Citan la explicación del artículo referenciado: “no hacen falta algoritmos fancy, así que se simplifica”. Dicen que, como muchos servicios de todos modos usan un servidor central, este enfoque sí parece práctico, aunque no les queda claro cuánto más simple es realmente, porque la coordinación del servidor exige deshacer/reaplicar las ediciones locales.

  • Comentan que incluso rewind/replay ya les parece un enfoque fancy, y que un Persistent B+Tree tampoco es precisamente simple.

  • Explican que Automerge, al final, también puede construir un orden total internamente, pero en la práctica maneja las operaciones de texto con CRDT tradicionales como RGA, precisamente porque undo/replay no es algo sencillo.

• Da la impresión de ser un CRDT no optimizado, como si lo estuvieras usando a lo bruto con max set size=1.

  • En respuesta, alguien dice que justamente reducir así el proceso de complejidad resulta atractivo porque se parece más a lo que de verdad ocurre en la práctica; aunque no esté optimizado, sigue teniendo encanto.

• Si se usa reconciliación en el servidor, existe el riesgo de que el problema de fusión del lado del cliente se vuelva difícil. Preguntan cómo se puede mantener una UX fluida del editor cuando las actualizaciones del servidor llegan de forma secuencial. Por ejemplo, si una solicitud de inserción falla, ¿se reintenta?, y si mientras tanto llegaron otras actualizaciones, ¿qué se hace? Como posibles soluciones mencionan rebobinar y reaplicar el historial de edición, o esperar y vaciar la cola. Desde la perspectiva de frontend, parece haber bastantes casos límite de UI/UX no explicitados, y por eso los CRDT podrían terminar siendo incluso más simples. En particular, les da curiosidad cómo sería la experiencia de usuario con conectividad inestable, por ejemplo en el metro.

  • Explican que ProseMirror y las versiones recientes de CodeMirror gestionan los cambios del documento en unidades de pasos (step) y van actualizando la información de posición (position map) en cada etapa para poder aplicar esos pasos almacenados al documento. Destacan que eso funciona bien en la práctica para edición colaborativa y comparten enlaces de referencia.

• Alguien propone que quizá valdría la pena intentar usar un LLM, por ejemplo un modelo 4b, para resolver conflictos de fusión más allá de los casos simples sin recurrir a CRDT u OT complejos. Dicen que quizá no sería eficiente energéticamente, pero que podría funcionar sorprendentemente bien.

  • Se preguntan cómo fusionaría un LLM un conflicto como el del ejemplo, donde sobre My name is se insertan Charlie y Dave después de is.