Mentiras sobre la edición colaborativa, parte 1: algoritmos para la edición offline

• La evaluación de Moment sobre edición colaborativa para su editor de texto principal mostró que las familias de algoritmos CRDT y OT pueden producir resultados de fusión que los usuarios percibirían como corrupción de datos en conflictos directos offline
• Incluso en un caso simple donde Alice elimina toda una oración y Bob cambia Color por Colour, se producen resultados no intencionados por humanos, como que el documento final quede solo con la letra u
• En los casos de uso de Moment, alrededor de 20–30% de los conflictos directos probados fueron inaceptables, y por su frecuencia y la reacción negativa se consideró difícil defenderlos como experiencia de producto
• Yjs, ShareJS y Peritext promocionan edición offline, colaboración con retrasos prolongados o fusión automática de copias independientes, pero los algoritmos no pueden conocer la intención ni el orden del usuario, por lo que dependen de heurísticas
• La edición colaborativa offline no es solo un problema de algoritmos, sino más bien un problema de UI/UX, y requiere una experiencia de fusión que una persona pueda leer y juzgar, como la UI de fusión de git o collaborative history de Ink & Switch

---

Límites revelados en la evaluación de edición colaborativa de Moment

• A comienzos de 2024, Moment empezó a investigar un sistema de edición colaborativa para usar en su editor de texto principal
• Varios algoritmos afirmaban resolver no solo la edición simultánea online, sino también casos offline en los que los usuarios editan sin límite de tiempo estando desconectados y luego, al volver a conectarse, los cambios se fusionan automáticamente
• Tras ver papers y presentaciones, al principio esperaban que la comunidad de edición colaborativa hubiera llegado a la “respuesta correcta” para el problema en general
• Durante la evaluación, los algoritmos de las familias CRDT y OT resolvían los conflictos de edición directa de formas poco intuitivas, y los usuarios percibían esos resultados como corrupción de datos
• Como la edición offline aumenta mucho la posibilidad de conflictos directos, con esos algoritmos por sí solos era difícil construir la experiencia de edición offline que Moment quería

Un caso simple donde chocan una eliminación y una corrección ortográfica

• Alice y Bob editan el mismo documento estando ambos offline
• El documento contiene el texto The Color of Pomegranates
• Bob cambia la ortografía de Color a la forma británica Colour, y Alice elimina todo el texto
• Cuando ambos vuelven a estar online más tarde, las dos ediciones entran en conflicto, y el sistema debe reconciliarlas sin saber cuál ocurrió primero
• En este caso, Alice y Bob terminan con un documento que contiene solo la letra u
  • No es una oración válida ni una palabra válida
  • Los usuarios perciben este resultado como si Moment hubiera corrompido sus datos

Los resultados extraños de los conflictos directos no son raros

• Este conflicto es trivial y directo, pero está dentro del rango que podría considerarse soportado por algoritmos populares de edición colaborativa
• El resultado real fue un documento que una persona no habría escrito por sí misma, y se interpretó como corrupción de datos por parte del producto de Moment
• Depende de cada caso de uso, pero aproximadamente 20–30% de los conflictos directos que Moment probó produjeron resultados difíciles de aceptar para casos de edición offline
• Considerando tanto el feedback negativo como la frecuencia, concluyeron que sería difícil explicar y defender estos resultados ante los usuarios

El soporte de edición offline que prometen las herramientas

• Al principio, al ver estos resultados, pensaron que estaban entendiendo mal lo que esas herramientas ofrecían
• Sin embargo, las descripciones de cada proyecto pueden leerse como si ese escenario estuviera dentro del alcance soportado
  • Yjs declara en su README que soporta offline editing
  • ShareJS explica que permite colaborar con cualquier latencia, desde cero hasta el nivel de unas vacaciones largas
  • Peritext explica que los usuarios pueden editar copias independientes de un documento y fusionarlas automáticamente de una manera que preserve la intención del usuario tanto como sea posible
• Moment sigue buscando una solución a este problema, pero considera difícil reconciliar la frecuencia y los tipos de errores que observó en la práctica con esas afirmaciones

Límites fundamentales de los algoritmos sin mediación

• A medida que avanzó la evaluación, llegaron a la conclusión de que esos algoritmos no hacían lo que Moment quería
• La pregunta restante era si se trataba de un problema que podía corregirse contribuyendo al proyecto, o si era un límite fundamental del algoritmo
• Hay tres razones para considerarlo un problema fundamental
  • El algoritmo no puede conocer las intenciones de Alice y Bob, ni preguntarles por email qué querían hacer, ni revisarlo como en la UI de un Pull Request de GitHub
  • Debe tomar la propuesta de Alice de eliminar todo y la propuesta de Bob de corregir la ortografía, y decidir el resultado mediante heurísticas
  • Opera a nivel de caracteres y ofrece garantías muy débiles sobre la salida
  • Si Alice y Bob hubieran sabido qué estaba haciendo la otra persona, tal vez habrían decidido editar de otra manera
• Esto también está relacionado con el problema de que estos algoritmos no pueden seguir el orden causal

La edición offline se parece más a un problema de UI/UX

• Moment esperaba que, implementando algoritmos sofisticados, pudiera soportar verdadera edición offline como efecto secundario, pero después de la evaluación se volvió difícil verlo así
• Era razonable que los usuarios interpretaran los resultados del algoritmo como corrupción de datos; los resultados extraños están incorporados en el propio algoritmo y pueden ocurrir con suficiente frecuencia como para ser un problema real
• Otra interpretación es que la edición colaborativa requiere invertir recursos significativos de UI/UX
• El algoritmo no puede resolver el problema por completo, pero sí puede formar parte de la solución

UI de fusión de git y líneas de investigación

• Ya existe una UI de fusión de documentos ampliamente adoptada: git
• La pregunta de investigación se parece más a cómo hacer que esa experiencia sea más accesible, comprensible y automatizable
• Alrededor de 2009 había mucha discusión sobre los algoritmos que git usa para fusionar cambios automáticamente
  • git adoptó el Myers O(ND) diff algorithm, un algoritmo usado principalmente por biólogos para análisis de secuencias tipo BLAST
  • Bram Cohen consideró que los resultados de diff no eran intuitivos y creó el patience diff algorithm, que fue adoptado por bzr, un competidor de git hoy discontinuado
• En ese momento, la discusión se enfocaba en producir diffs legibles para humanos, pero la discusión actual se acerca más a si un algoritmo puede lograr ese resultado sin intervención humana
• Hay investigaciones en curso que tratan la edición colaborativa como un problema de UI/UX, como collaborative history de Ink & Switch

[GN⁺]

Opiniones de Hacker News

• Soy el autor de Eg-walker y ShareJS. Aunque el artículo parece tener un tono contrario a mi trabajo, en realidad estoy totalmente de acuerdo, y vengo diciendo lo mismo en HN desde hace años.
  Las herramientas actuales de colaboración en tiempo real funcionan bien cuando todos editan juntos en línea, pero si los usuarios editan sin conexión o en ramas de larga duración, al fusionar se necesitan marcadores de conflicto y la opción de revisión manual. Esto es especialmente cierto en código.
  Por suerte, algoritmos como egwalker guardan las huellas de edición a nivel de caracteres de todos los usuarios y el orden causal, es decir, un orden de cambios como el DAG de Git, así que tienen mucha más información que Git. Por lo tanto, debería ser posible crear un CRDT que, al fusionar ramas, detecte y marque los rangos en conflicto, y permita que el usuario los resuelva manualmente.
  Me parece un problema algorítmicamente interesante, pero bastante resoluble, y curiosamente casi nadie en el área de edición de texto parece haberlo intentado todavía. Si alguien quiere hacer una contribución original y valiosa en este campo, es una pieza importante que falta en el ecosistema CRDT, así que ojalá alguien lo intente.
  [1] Más abajo en este comentario: https://news.ycombinator.com/item?id=19889174

  • Si haces eso, al final terminas metiendo conflictos como parte del modelo de datos. Es una forma curiosa de lograr la C de CRDT, es decir, “conflict-free”, pero es completamente legítima y quizá sea la única manera.
    El siguiente desafío interesante aparece cuando surgen conflictos alrededor de la propia resolución de conflictos.
  • Joseph, no quería decir que tu trabajo fuera malo. La intención era más bien ayudar a que quienes trabajan en esto entiendan qué pueden esperar y motivar problemas como el que mencionaste al final.
    Evaluar este tipo de sistemas ya es, por sí mismo, un problema técnico bastante difícil, así que creo que muchos equipos van a sufrir con eso. Por eso merecen consejos prácticos, y siento que a nosotros también nos habría gustado saberlo antes.
  • Soy escéptico sobre si será posible una solución algorítmica, pero parece algo que se puede manejar en la capa de UX por encima. Por ejemplo, el cliente podría detectar conflictos a partir de las huellas de edición y mostrar un diálogo de resolución de conflictos que convierta el resultado resuelto en una nueva edición.
    La parte difícil es marcar que el conflicto ya fue resuelto. Podría ser tan simple como agregar un campo al CRDT, aunque no sé si entonces habría que considerarlo una solución algorítmica.
    [1] https://josephg.com/blog/crdts-go-brrr/
  • El artículo trata el caso de splices simultáneos que se superponen, un caso límite raro y bastante conocido.
    Si se trata de editar código de programas, uno espera que el resultado de la fusión sea un programa válido, así que se vuelve una madriguera mucho más profunda. Escuché que en JetBrains había un proyecto que intentó resolver esto con fusión basada en AST, pero después de profundizar mucho más decidieron que no valía la pena.
  • Creo que la edición “sin conexión” es un problema humano, así que no se puede resolver con automatización. La gente siempre encuentra formas de romper o rodear la automatización o los sistemas.
    La única “edición sin conexión” que permitiría en documentos escritos por personas es agregar comentarios. No edición, y no fusión automática.
    Para la “edición sin conexión” de código fuente, que sí es objetivo de automatización, usamos Git, y Git no pretende resolver las fusiones: solo muestra revisiones. La fusión es algo que una persona supervisa o que una automatización especializada realiza con su mejor estimación, y aun así se necesitan revisión y pruebas para confirmar si tuvo éxito.

• Los algoritmos mecánicos de fusión pueden hacerlo mejor o peor según el tipo de conflicto, pero al final ningún CRDT puede determinar si el texto fusionado es lo que el usuario quería decir.
  El artículo de Upwelling trata con más detalle la diferencia entre lo que en escritura llaman conflictos semánticos y conflictos gramaticales: https://inkandswitch.com/upwelling/
  Siento que la colaboración seria, en última instancia, también es un problema de revisión de documentos. En periodismo o publicación científica esto es especialmente cierto, y en minutas de reuniones quizá se pueda ignorar en gran medida.

  • Peter, gracias por el buen comentario. Espero que se haya notado que buena parte del artículo termina motivando directamente el trabajo de Ink & Switch que mencioné al final.
    También quería enlazar a Upwelling, pero no recordaba el nombre y por la fecha límite lo reemplacé por otro enlace.

• Otro lado oscuro de las implementaciones de CRDT es la carga de infraestructura. Hace tiempo escribí sobre esto en profundidad[0], y me alegró ver que Supabase llegó a las mismas conclusiones que mis resultados empíricos en su artículo de hace unos años sobre una extensión CRDT para Postgres[1].
  Si vas a usar CRDT, conviene usar algo como Redis, o bien una base sobre MyRocks[2] o RocksDB/LevelDB, aunque solo pensar en el uso de memoria duela. Hagas lo que hagas, no pongas un RDBMS, especialmente Postgres, como backend.
  [0]: https://news.ycombinator.com/item?id=40834759
  [1]: https://supabase.com/blog/postgres-crdt
  [2]: http://myrocks.io

  • Estoy armando algo por mi cuenta con Yjs + Postgres, así que esto parece realmente útil. Tal vez algún día me ayude a evitar una crisis grande.

• Las observaciones de este artículo son acertadas. Los CRDT son un excelente modelo formal para estructuras de datos distribuidas, pero siempre me incomodó la idea de que todos los conflictos deban resolverse automáticamente, el concepto literal de tipos de datos replicados sin conflictos.
  Como muestra el artículo, creo que es un intento sin futuro. Lo que se necesita es una representación estructural adecuada que permita compartir los conflictos y resolverlos de forma colaborativa, devolver el control al usuario y apoyar el proceso de resolución. Uno de mis papers favoritos, “Turning Conflicts into Collaboration” [1], trata esta idea de manera convincente.
  Como parte de mi investigación doctoral en curso, desarrollé “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2], un modelo formal de representación estructural de conflictos basado en teoría de retículos. Casualmente, también es un CRDT, pero no intenta resolver automáticamente los conflictos, sino que los representa dentro del documento colaborativo. Al abordarlo matemáticamente, pude llegar a un modelo conceptual simple que garantiza propiedades fuertes como completitud, minimalidad y unicidad de las fusiones incluso después de conflictos existentes fusionados repetidamente, y además el cálculo de las fusiones es muy sencillo.
  [1] https://doi.org/10.1007/s10606-012-9172-4
  [2] https://doi.org/10.14279/tuj.eceasst.82.1226

  • Cuando aprendí por primera vez sobre CRDT, la sigla significaba commutative replicated data types, es decir, tipos de datos replicados conmutativos. También era así en el paper de Shapiro y otros; es más difícil de pronunciar, pero me gusta más esa versión.
    El conflicto es un concepto complejo y, aunque “conflict-free” es técnicamente correcto como descripción del resultado, como se ve en este artículo y en lo anterior, puede llevar a malentendidos.
    La conmutatividad es la propiedad de que, aunque Bob aplique los cambios en el orden [Bob, Alice] y Alice los aplique en el orden [Alice, Bob], ambos lleguen al mismo documento. No significa que el documento esté “libre de conflictos” de una manera significativa en un nivel de abstracción más alto.

• Creo que la idea de que varias entidades distintas tengan autoridad simultánea sobre un mismo fragmento de datos, sin coordinación en tiempo real, en general no se puede resolver. Es una lección que ya aprendimos en sistemas distribuidos, y también queda muy clara en este artículo al pensar en la edición distribuida de documentos.
  Me parece que el mismo principio se aplica a ejemplos muy distintos que se puedan imaginar, como controles dobles en la cabina de un avión, la crianza de los hijos, etc.

  • Sí se puede resolver, pero requiere información de contexto más compleja que a mucha gente le daría flojera ingresar. Por ejemplo: “esta palabra que acabo de cambiar solo tiene sentido como parte de toda esta oración, y esa oración completa no es indispensable para todo el párrafo”.
    Y también es gracioso llamar a eso “resolverlo”, porque en este momento una gran parte del planeta parece estar pensando que la salida caótica de los LLM puede ser, en la práctica, el resultado final de un cálculo.
  • Es el teorema CAP de Brewer para almacenamiento de datos distribuido. Solo se pueden tener dos de tres: consistencia, disponibilidad y tolerancia a particiones.

• CRDT y OT, los algoritmos que se usan comúnmente para la edición colaborativa de texto, tienen requisitos algebraicos estrictos sobre qué hacen las operaciones de edición y cómo interactúan entre sí.
  Por eso, aunque el servidor sea lo bastante inteligente como para manejar el ejemplo de “Colour” de una forma razonable desde el punto de vista de UX, diseñar el CRDT/OT correspondiente para edición optimista del lado del cliente es muy difícil.
  Se puede evitar esto si no se usa CRDT/OT. Por ejemplo, el servidor puede procesar las operaciones en el orden en que las recibe y aplicar la lógica de UX deseada, mientras que el cliente usa una estrategia de rebase/predicción encima de eso para permitir edición optimista. Referencia: https://doc.replicache.dev/concepts/how-it-works
  Aplicar esto a la edición de texto también tiene dificultades, pero son independientes del problema de CRDT/OT que se discute aquí.

  • Este comentario está muy infravalorado, y estoy totalmente de acuerdo.

• Creo que esto ocurre porque se mezclaron los conceptos matemático, causal y entrópico de conflicto con el conflicto semántico. Yo también cometí antes el mismo error, pero al revés, y me dijeron con firmeza que no sabía de qué estaba hablando.
  Cuando uno empieza a considerar árboles, se vuelve mucho más desordenado. Por ejemplo, yJS funciona sobre documentos JSON. Si la UI solo muestra un nivel superficial y no despliega los niveles profundos, el usuario podría no ver en absoluto una edición eliminada.
  La clase de CRDT que preserva conflictos —si no recuerdo mal, los casos donde un registro puede tener varios valores— parece la más prometedora. Al usuario se le deberían presentar esos conflictos, e incluso podrían mostrarse de forma completamente visual. Permitirle revisar el historial también parece una alternativa práctica para que entienda cómo surgió algo raro o cómo desapareció su propio cambio.

  • Un buen nombre para este tipo de CRDT sería “Git”.
  • En ese sentido, Loro parece prometedor. Está abordando este problema de forma activa.

• Recuerdo que el propio Torvalds era bastante pesimista sobre lo que se podía lograr con la fusión automática. Y ese juicio fue acertado.
  Dijo que Git rechazaba la idea de que un sistema de control de versiones pudiera, o debiera, “resolver el problema de las fusiones” haciendo que un algoritmo lo suficientemente inteligente hiciera automáticamente lo correcto.
  Estoy de acuerdo en que la edición offline es un problema de UI/UX. La causa más profunda es la costumbre de la industria informática de seguir reciclando soluciones viejas, y la creencia de que, “como en general una bolsa de 5 libras es más fácil de manejar que una de 10 libras, hay que meter 10 libras de cosas en una sola bolsa de 5 libras”.
  La imagen básica de un “editor de texto” es un textarea de Mosaic, MacWrite, o algo intermedio, así que normalmente se intenta agregar la fusión encima con cambios mínimos. Algo como una opción de menú o unas pocas opciones en un pequeño cuadro de diálogo. Incluso cuando hay soporte GUI de fusión escondido en algún menú, termina siendo una historia de terror de diff/merge para programadores, o una vista basada en tachados tan precaria como pilotear un barco en la niebla.
  Pero en un editor de texto con colaboración offline, la fusión parcialmente manual está en el centro del proceso, y también debería estar en el centro del diseño del editor. Lamentablemente, MacWrite es un óptimo local del que es difícil escapar.

  • Queda la pregunta de cuál es la alternativa.
    Por ejemplo, después de que alguien habla de “imitación tipo culto de carga” y “soluciones viejas”, lo siguiente que suele decir es “no editen código como texto, edítenlo como árbol sintáctico”, pero el problema sigue igual. Solo hay que cambiar “carácter” por “sentencia”.
    Si Bob agregó una línea a la rama else de una sentencia if y Alice borró toda la sentencia, incluida la rama else, ¿qué debería hacer un sistema inteligente?
  • Creo que escribí de forma confusa lo de la fusión automática. Lo que quería decir es que, si varios commits modifican un archivo, Git intenta fusionarlos, pero los conflictos directos necesariamente debe señalarlos.
    En general, parece que estamos de acuerdo en que este enfoque es el correcto.

• Acepto preguntas o feedback. Estaré en reuniones una o dos horas, pero me gusta hablar de estas cosas. Pueden mandarlo por aquí o por email, como prefieran: [e-mail]

  • Si mantienen el soporte offline, con el tiempo van a aparecer casos más interesantes. Por ejemplo: “Estaba trabajando en esto en el avión sin wifi, no me gustó el rumbo que estaba tomando, cerré la laptop y dormí una siesta. Después trabajé en el documento desde la desktop durante los días siguientes. El fin de semana abrí el documento en la laptop y todos los cambios que hice en el avión se metieron en el documento y arruinaron todo. Ayuda, ¡yo no quería fusionar nada!”.
    Git no mezcla automáticamente cambios locales sin consentimiento explícito. bzr tampoco habría soñado con hacer algo así. Pero cosas como Google Docs lo hacen con gusto.
    El progreso hasta ahora se ve genial, y espero que al programa de acceso temprano le vaya bien.
  • ¿Por qué no adoptar simplemente una fusión al estilo patch/diff? Si se plantea la edición colaborativa offline de texto solo como un problema de optimización de UX, este es un problema resuelto desde hace décadas.

• Implementé differential sync(https://neil.fraser.name/writing/sync/). Lo hice porque no entendí las otras opciones y, para la app grugnotes.com, esta parecía la más simple.
  La app es bastante rudimentaria y ni siquiera es totalmente en tiempo real, pero maneja correctamente la fusión del ejemplo sin importar quién vuelva a estar online primero. Si la eliminación llega online primero, la versión colour se descarta y ni siquiera se guarda en el historial de edición.
  Seguramente habrá más problemas, y tampoco sé qué pasa con más de dos usuarios, pero para mi caso de uso estoy satisfecho.