Por qué OT es difícil de hacer bien

La lección anterior dejó la transformación operacional en su mejor momento: una idea elegante, dos funciones de diez líneas y una convergencia que se comprueba a mano en el ejemplo del documento abc. Esta lección explica por qué esa impresión es engañosa y por qué la historia de OT está poblada de implementaciones publicadas, revisadas y desplegadas que resultaron ser incorrectas. Hay tres fuentes de dificultad y son independientes entre sí, de modo que se multiplican en vez de sumarse. La primera es combinatoria: el número de funciones que hay que escribir crece con el cuadrado del número de tipos de operación, y los editores reales tienen muchos tipos. La segunda es lógica: existe una segunda propiedad de convergencia que no habla de estados sino de igualdad entre operaciones, es mucho más fuerte de lo que parece y hay resultados que muestran que las funciones clásicas de texto no la cumplen. La tercera es epistemológica: los fallos que produce violarla son raros, dependen de tres réplicas en cierta configuración y no aparecen en las pruebas que uno escribiría de forma natural.

La matriz que crece con el cuadrado

La primera dificultad es puramente contable y por eso resulta sorprendentemente fácil de subestimar al empezar un proyecto. La transformación no se define entre operaciones sino entre pares ordenados de tipos de operación: hace falta saber qué le hace una inserción a un borrado, un borrado a una inserción, un borrado a otro borrado, y así con cada combinación. Con dos tipos son cuatro casos y el problema parece de tarde. Los editores que la gente usa de verdad no tienen dos tipos.

// Un editor de texto enriquecido modesto
const tipos = [
  "insertarTexto", "borrarRango", "aplicarFormato", "quitarFormato",
  "partirBloque", "unirBloques", "cambiarTipoBloque", "moverNodo",
  "insertarTabla", "redimensionarColumna", "insertarComentario", "anclarEnlace",
];

const casos = tipos.length ** 2; // 144 funciones de transformacion distintas

Ciento cuarenta y cuatro funciones no son ciento cuarenta y cuatro tareas de programación equivalentes. Cada una es una pequeña teoría sobre qué significa preservar la intención de un tipo de cambio cuando otro tipo de cambio ha ocurrido antes sin saberlo, y varias de esas teorías son genuinamente discutibles. Qué debe pasarle a un formato aplicado sobre un rango que otra réplica acaba de partir en dos bloques no es un problema de índices: es una pregunta sobre el modelo del documento cuya respuesta correcta depende del producto. Y todas ellas deben ser mutuamente consistentes, porque la convergencia es una propiedad del conjunto y no de cada función por separado.

A esa cuenta hay que sumarle un factor que la duplica en la práctica y que casi ningún cálculo inicial contempla. La transformación no es simétrica, de modo que la celda formato frente a partición de bloque y la celda partición de bloque frente a formato son funciones distintas que deben encajar entre sí; y varias operaciones admiten parámetros que cambian cualitativamente el caso —un borrado que abarca el punto de partición no se comporta como uno que queda entero a un lado—, con lo que cada celda esconde a su vez una tabla de subcasos. La cifra honesta no es el cuadrado del número de tipos sino ese cuadrado multiplicado por el número medio de configuraciones geométricas distinguibles, y en un editor de documentos estructurados esa media no es pequeña.

De ahí se sigue un rasgo práctico de OT que no aparece en los artículos y que domina el trabajo real: la matriz de transformación es acoplamiento global. Añadir un tipo de operación para una funcionalidad nueva —notas al margen, seguimiento de cambios, campos de formulario— no añade una función sino una fila y una columna enteras, y obliga a revisar cómo interactúa con todo lo que ya existía. Un sistema con esa forma se endurece con el tiempo: cada mes que pasa, la barrera de entrada para una operación nueva sube, y las funcionalidades que no encajan en los tipos existentes tienden a implementarse fuera del mecanismo colaborativo con excusas de calendario. Ese patrón, más que ningún teorema, es lo que hace difícil vivir con OT a largo plazo.

Dos propiedades, y la segunda no habla de estados

La segunda dificultad es la que separa a los sistemas que convergen de los que parecen converger. La literatura las llama propiedades de transformación uno y dos —abreviadas TP1 y TP2, y también condiciones de convergencia C1 y C2 según la escuela—, y fueron formuladas con esa nitidez en el trabajo de Ressel, Nitsche-Ruhland y Gunzenhäuser presentado en la conferencia CSCW de 1996, que introdujo además el algoritmo adOPTed y un modelo de espacio de estados multidimensional para razonar sobre los caminos de transformación.

// TP1: los dos caminos de aplicacion llegan al MISMO ESTADO
function cumpleTP1(estado, o1, o2) {
  const camino1 = aplicar(aplicar(estado, o1), transformar(o2, o1));
  const camino2 = aplicar(aplicar(estado, o2), transformar(o1, o2));
  return camino1 === camino2;
}

// TP2: transformar o3 por los dos caminos produce la MISMA OPERACION
function cumpleTP2(o1, o2, o3) {
  const via1 = transformar(transformar(o3, o1), transformar(o2, o1));
  const via2 = transformar(transformar(o3, o2), transformar(o1, o2));
  return iguales(via1, via2); // igualdad sintactica, no igualdad de efecto
}

La diferencia entre las dos comparaciones finales es todo el asunto. TP1 solo pide que los estados coincidan, y es la propiedad que uno verifica de forma natural al escribir pruebas, porque el estado es lo que se ve. TP2 pide que la operación resultante sea la misma operación, no una que produzca el mismo efecto sobre el documento actual, y esa exigencia parece excesiva hasta que se comprende de dónde viene: con tres o más réplicas, una operación transformada por un camino puede tener que transformarse todavía más veces contra operaciones futuras, y si los dos caminos produjeron operaciones distintas aunque de efecto momentáneamente idéntico, esas transformaciones posteriores divergirán. TP2 no es una condición sobre el presente, es la condición que garantiza que el presente sirva de base para el futuro.

flowchart LR
S[estado comun con o1 o2 y o3 concurrentes] --> P1[transformar o3 frente a o1 y luego frente a o2 transformada]
S --> P2[transformar o3 frente a o2 y luego frente a o1 transformada]
P1 --> R1[una version de o3]
P2 --> R2[otra version de o3]
R1 --> C[TP2 exige que sean identicas y no solo equivalentes ahora]
R2 --> C
C --> F[si difieren la divergencia aparece varias operaciones despues]
style C fill:#f9e2af,color:#11111b
style F fill:#f38ba8,color:#11111b

Hay una tercera exigencia que no lleva número y que ha producido tantos fallos como las dos anteriores: deshacer. Una operación de deshacer no es un cambio nuevo cualquiera, porque su efecto se define respecto de una operación pasada que puede haber sido transformada varias veces desde entonces; deshacer ingenuamente aplicando la operación inversa sobre el estado actual produce resultados incorrectos en cuanto haya habido concurrencia entremedias. El tratamiento del deshacer forma parte del planteamiento de adOPTed desde 1996 precisamente porque el problema es inseparable del de la transformación, y en la práctica es la funcionalidad que más veces revela que una matriz que parecía correcta no lo era.

// Deshacer no es aplicar la inversa sobre el estado actual
const original    = { tipo: "insertar", pos: 3, texto: "hola", id: "op42" };
const inversaCruda = { tipo: "borrar", pos: 3, largo: 4 };
// Si entre medias llegaron operaciones concurrentes, la posicion 3 ya no es la suya:
// hay que excluir esas operaciones del contexto, invertir, y volver a incluirlas.

Aquí está el rasgo que convierte esto en un problema de ingeniería y no solo de teoría: TP2 requiere tres operaciones concurrentes para violarse. Con dos réplicas es imposible fabricar el escenario, y con dos réplicas es como prueba casi todo el mundo, porque es la configuración que se monta abriendo dos pestañas. Un sistema que cumple TP1 y viola TP2 pasa cualquier prueba de dos clientes, funciona durante meses en producción con equipos pequeños, y falla el día en que tres personas editan a la vez la misma región y una de ellas tenía la red mal. El informe del incidente dirá divergencia esporádica no reproducible, que es la firma característica de esta clase de fallo.

Los contraejemplos están publicados

La tercera dificultad es que la intuición humana es mala verificando estas propiedades, y la historia de OT lo documenta con una franqueza poco común en la ingeniería. El algoritmo dOPT del artículo fundacional de 1989 resultó no ser correcto en general, y el problema quedó recogido en la literatura posterior; el trabajo de Sun y Ellis Operational transformation in real-time group editors: issues, algorithms, and achievements, presentado en la conferencia CSCW de 1998, discute abiertamente las dificultades de corrección de los algoritmos previos y propone una alternativa. Ese mismo año, el artículo de Sun, Jia, Zhang, Yang y Chen en la revista TOCHI —Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems— separa con claridad las tres garantías que un editor colaborativo debe ofrecer y muestra que la convergencia sola no basta.

Ese artículo de la revista TOCHI merece una lectura atenta por una razón que va más allá de OT: la garantía que denomina preservación de la intención no es reducible a la convergencia ni se deduce de ella. Un sistema puede hacer converger a todas las réplicas a un estado que ninguno de los autores pretendía, y esa posibilidad no es un fallo del algoritmo sino una propiedad distinta que hay que perseguir aparte. Distinguir esas dos garantías es probablemente la aportación conceptual más duradera de la escuela OT, y reaparecerá literalmente igual cuando la lección cuatro examine qué promete y qué no promete la otra familia.

La verificación mecanizada llegó después y fue todavía más contundente. En Proving correctness of transformation functions in real-time groupware, presentado en la conferencia europea ECSCW de 2003, Imine, Molli, Oster y Rusinowitch aplicaron un demostrador automático de teoremas a funciones de transformación publicadas y reportaron contraejemplos a las propiedades de convergencia en varias de ellas. La línea de trabajo continuó en la revista Theoretical Computer Science en 2006 con el diseño y la verificación formal de funciones de transformación, y en un informe de investigación de 2005 firmado por Oster, Urso, Molli e Imine que estableció un resultado especialmente incómodo: las funciones de transformación al uso sobre secuencias de caracteres no pueden cumplir TP2, de modo que no se trataba de encontrar la versión correcta sino de que en ese marco no existía.

Conviene añadir que la discusión no quedó cerrada ni es unánime. Existe una tradición, sostenida principalmente por Chengzheng Sun y sus colaboradores a lo largo de tres décadas de publicaciones y de un documento de preguntas frecuentes mantenido durante años, que argumenta que varios de esos resultados negativos dependen de qué se exija exactamente al algoritmo y de qué variante se examine, y que hay formulaciones de OT cuya corrección sí se sostiene. Quien vaya a construir sobre OT debería leer esa línea de trabajo directamente en lugar de fiarse del resumen ambiental, que en los últimos años ha tendido a ser injustamente sumario. Lo que ninguna de las dos partes discute es el hecho histórico: hubo algoritmos publicados, citados y desplegados que no cumplían lo que se creía que cumplían.

Conviene leer esa historia sin condescendencia, porque el detalle relevante no es que hubiera errores sino quién los cometió y dónde estaban publicados. Las funciones que resultaron incorrectas no eran código apresurado de un fin de semana: eran algoritmos revisados por pares, publicados en foros de primer nivel y citados durante años. Si un problema resiste ese nivel de escrutinio, la conclusión razonable no es que hiciera falta más cuidado, sino que la corrección de una matriz de transformación está fuera del alcance de la revisión humana informal y necesita, o bien verificación mecanizada, o bien un diseño que elimine la obligación de demostrarla.

Cómo se convive con esto en la práctica

Los sistemas OT que funcionan hoy en producción no resolvieron estos problemas: los rodearon, y merece la pena inventariar las tres maniobras porque cada una tiene un precio identificable. La primera y más importante es eliminar la obligación de TP2 introduciendo un servidor que ordena las operaciones, de modo que ninguna réplica tenga que transformar contra dos concurrentes; es la arquitectura de Jupiter y es el tema entero de la lección siguiente. La segunda es restringir el repertorio de operaciones hasta que la matriz vuelva a ser manejable, expresando todo cambio como composición de unos pocos primitivos —típicamente retener, insertar y borrar sobre una secuencia con atributos—, que es la forma en que los editores web modernos consiguen soportar texto enriquecido sin ciento cuarenta y cuatro funciones.

// Restringir el repertorio: todo cambio es una secuencia de tres primitivos
const cambio = [
  { retener: 12 },
  { insertar: "hola", atributos: { negrita: true } },
  { borrar: 3 },
  { retener: 40, atributos: { cursiva: true } },
];
// Con tres primitivos la matriz vuelve a tener nueve casos en lugar de ciento cuarenta y cuatro

Esa segunda maniobra tiene un efecto secundario que rara vez se enuncia y que conviene tener presente al evaluarla: al reducir el repertorio a primitivos genéricos, la matriz se vuelve pequeña a costa de perder información sobre la intención. Mover un párrafo deja de ser una operación de movimiento y pasa a ser un borrado seguido de una inserción, con lo que el sistema ya no puede saber que se trataba del mismo contenido y no puede, por ejemplo, conservar los comentarios anclados en él ni fusionar sensatamente una edición concurrente sobre ese texto. Es exactamente el mismo trueque que la primera lección describió entre replicar estado y replicar intención, reaparecido dentro de la propia familia: se compra manejabilidad de la matriz vendiendo expresividad del modelo, y el usuario percibe la venta como comportamientos extraños en los casos que más le importan.

La tercera maniobra es la verificación agresiva por fuerza bruta: generar exhaustivamente todas las combinaciones de tres operaciones cortas sobre documentos diminutos y comprobar TP1 y TP2 en cada una. Es sorprendentemente eficaz, porque los contraejemplos conocidos son pequeños, y es sorprendentemente raro encontrarlo implementado. Un espacio de documentos de cuatro caracteres con tres operaciones concurrentes se recorre en segundos y cubre una fracción de casos que ninguna prueba escrita a mano alcanza.