Transformación operacional: reescribir la operación antes de aplicarla · Fundamentos de Estado

La lección anterior dejó el problema reducido a un enunciado casi geométrico: una operación lleva coordenadas que solo significan algo en la versión donde nacieron, y aplicarlas sobre una réplica que ha avanzado por su cuenta produce corrupción. Había dos salidas, traducir las coordenadas o abolirlas. La transformación operacional escoge la primera, y lo hace con una decisión de diseño que resulta contraintuitiva la primera vez que se ve: cuando llega una operación remota, el receptor no la ejecuta. La modifica. Toma el insertar en la posición 5 que le mandaron y lo convierte en el insertar en la posición 6 que produce, sobre su documento actual, el mismo efecto que el autor pretendía sobre el suyo. La operación que se escribe en la red y la operación que se aplica en el documento no son la misma cosa, y esa distinción es todo el algoritmo. OT nació en 1989 con el sistema GROVE, se depuró durante dos décadas de correcciones a demostraciones que resultaron estar mal, y acabó siendo la maquinaria de Google Wave y después de Google Docs, es decir, el sistema colaborativo que más personas han usado en la historia. Merece estudiarse no solo por su ubicuidad, sino porque su historia de errores enseña dónde está la dificultad real de la colaboración: no en la idea, que es simple, sino en demostrar que la idea se sostiene cuando las operaciones se propagan por caminos distintos.

🎯 Al terminar esta lección sabrás

Entender la operación central de OT: transformar una operación remota contra las locales concurrentes antes de aplicarla.
Construir la función de transformación para insertar y borrar, con su desempate determinista.
Distinguir TP1 y TP2 y por qué la segunda es la que hunde a la mayoría de implementaciones.
Ver cómo un servidor autoritativo con orden total elimina TP2 y hace OT viable en producción.

Transformar en lugar de aplicar

Volvamos al ejemplo que rompió la ingenuidad. El documento compartido es HOLA. Ana inserta X en la posición 0 y Bruno, a la vez, borra el carácter de la posición 3. Cuando la operación de Bruno llega a Ana, la réplica de Ana ya no es HOLA sino XHOLA: todo lo que estaba a la derecha de la posición 0 se ha corrido un lugar. El índice 3 de Bruno señalaba la A; en el documento de Ana, la A está ahora en el 4. La corrección es evidente en cuanto se ve: sumar uno al índice de Bruno porque una inserción anterior lo empujó. Eso es exactamente lo que hace la función de transformación, que se suele escribir como transformar y recibe dos operaciones concurrentes, devolviendo la primera reexpresada como si la segunda ya hubiera ocurrido.

type Op =
  | { tipo: 'insertar'; pos: number; ch: string; sitio: number }
  | { tipo: 'borrar'; pos: number; sitio: number }

// transformar(a, b) devuelve a reescrita para aplicarse
// sobre un documento que ya incluye b
function transformar(a: Op, b: Op): Op {
  if (a.tipo === 'insertar' && b.tipo === 'insertar') {
    if (a.pos < b.pos) return a
    if (a.pos > b.pos) return { ...a, pos: a.pos + 1 }
    // misma posicion: desempate estable por identificador de sitio
    return a.sitio < b.sitio ? a : { ...a, pos: a.pos + 1 }
  }
  if (a.tipo === 'insertar' && b.tipo === 'borrar')
    return a.pos <= b.pos ? a : { ...a, pos: a.pos - 1 }
  if (a.tipo === 'borrar' && b.tipo === 'insertar')
    return a.pos < b.pos ? a : { ...a, pos: a.pos + 1 }
  // borrar contra borrar
  if (a.pos < b.pos) return a
  if (a.pos > b.pos) return { ...a, pos: a.pos - 1 }
  return { ...a, tipo: 'noop' } as Op  // ya lo borro el otro
}

Dos casos de esa tabla merecen atención porque contienen toda la sutileza del enfoque. El primero es el de dos inserciones en la misma posición: no hay ninguna razón objetiva para poner antes la de Ana o la de Bruno, pero sí hay una obligación absoluta de que ambas réplicas tomen la misma decisión. Por eso se desempata con un criterio arbitrario pero total y estable, típicamente el identificador de sitio o de sesión. Arbitrario está bien; inconsistente es fatal. El segundo caso es el de dos borrados del mismo carácter: la segunda operación no debe borrar nada, porque el carácter ya no existe, y transformarla en una operación nula es la única forma de no destruir a un vecino inocente. Es la primera aparición de un patrón que reaparecerá en toda la lección: la transformación no solo mueve índices, también anula operaciones que la concurrencia ha dejado sin objeto.

Con esa función, el algoritmo local es directo. Cada réplica mantiene un historial de las operaciones que ha aplicado y sabe cuáles de ellas son concurrentes con la que acaba de recibir —es decir, cuáles el emisor no había visto cuando la generó, algo que se determina con un vector de versiones o, en la variante de servidor, con un simple número de secuencia—. La operación entrante se transforma sucesivamente contra cada una de esas concurrentes, en orden, y solo entonces se aplica.

sequenceDiagram
participant A as replica de Ana
participant B as replica de Bruno
A->>A: insertar X en pos 0
B->>B: borrar pos 3
A-->>B: envia insertar pos 0
B-->>A: envia borrar pos 3
A->>A: transforma borrar pos 3 contra insertar pos 0
A->>A: aplica borrar pos 4
B->>B: transforma insertar pos 0 contra borrar pos 3
B->>B: aplica insertar pos 0
Note over A,B: ambas replicas quedan en XHOL

TP1 y TP2: por qué esto fue difícil durante veinte años

Que la transformación funcione en un ejemplo no demuestra nada. Para que un conjunto de funciones de transformación sea correcto debe cumplir propiedades formales, y son exactamente dos. La primera, TP1, es la condición de convergencia entre dos réplicas: si Ana aplica su operación y después la de Bruno transformada, y Bruno aplica la suya y después la de Ana transformada, ambos documentos deben quedar idénticos. Es la propiedad que se verifica de forma casi mecánica recorriendo la tabla de casos, y la que cualquier implementación razonable acaba satisfaciendo.

La segunda, TP2, es la que arruinó carreras académicas. Aparece solo cuando hay tres o más operaciones concurrentes que pueden propagarse por caminos distintos. Su enunciado exige que transformar una operación contra otras dos dé el mismo resultado independientemente del orden en que se hagan esas dos transformaciones. Dicho de otro modo: la transformación debe ser, en cierto sentido, conmutativa respecto del camino de propagación. La razón de que sea tan difícil es que el resultado de una transformación depende de un contexto que puede haberse construido de dos maneras distintas, y basta un caso —clásicamente, tres inserciones alrededor de una misma posición— para que las dos rutas produzcan documentos distintos. Durante años se publicaron algoritmos con demostraciones de TP2 que después se refutaron con contraejemplos; la lista de correcciones a dOPT, adOPTed, GOT y sus descendientes es un capítulo instructivo sobre la diferencia entre parecer correcto y serlo.

⚠️

Casi todos los OT caseros son incorrectos y no lo saben

Una implementación casera de OT suele satisfacer TP1 sin proponérselo y violar TP2 sin enterarse, porque TP2 solo se manifiesta con tres o más operaciones concurrentes que llegan por rutas distintas, algo que no ocurre nunca en las pruebas con dos pestañas abiertas y sí ocurre en producción con seis personas y una red irregular. El síntoma no es una excepción sino una divergencia silenciosa: dos usuarios ven textos distintos y ninguno de los dos lo sabe hasta que alguien lo menciona. Si vas a escribir OT a mano, la única defensa seria es el testeo por propiedades: genera secuencias aleatorias de operaciones concurrentes, propágalas por todos los órdenes posibles y verifica la igualdad de los documentos finales en cada uno.

El atajo de Google: un servidor que impone el orden

La salida de este pantano no fue una demostración más ingeniosa, sino una decisión de arquitectura, y es la razón por la que hoy OT se usa en productos que atienden a cientos de millones de personas. La observación clave es que TP2 solo hace falta si existen múltiples caminos de propagación. Si todas las operaciones pasan obligatoriamente por un servidor central que las secuencia, el sistema deja de ser una red de réplicas iguales y se convierte en un conjunto de relaciones independientes entre cada cliente y el servidor. Cada una de esas relaciones es un problema de dos partes, y para dos partes basta TP1. Esta es la esencia del modelo Jupiter, formulado en Xerox PARC en 1995, que es la base de Google Wave y de Google Docs.

🏛️

El servidor define la verdad

Existe un orden total de operaciones, el que el servidor decide al recibirlas. Ese orden es la historia oficial del documento y ninguna réplica puede contradecirlo.

🔁

El cliente aplica al instante y reconcilia después

El cliente ejecuta su operación localmente sin esperar, la envía y guarda las que aún no han sido confirmadas. Cuando llega una operación del servidor, la transforma contra su cola de pendientes.

📮

Una operación en vuelo cada vez

El cliente mantiene como mucho una operación sin confirmar y acumula el resto componiéndolas. Esto reduce drásticamente los estados posibles y con ellos la superficie de error.

🧾

La historia queda ordenada

Como el servidor secuencia, el documento tiene un registro lineal de cambios: auditoría, historial de versiones y control de acceso por operación se vuelven naturales.

// Modelo cliente-servidor: el cliente guarda lo que aun no le han confirmado
let pendientes: Op[] = []

function alRecibirDelServidor(remota: Op) {
  let op = remota
  const nuevasPendientes: Op[] = []
  for (const local of pendientes) {
    nuevasPendientes.push(transformar(local, op))  // mis pendientes se ajustan
    op = transformar(op, local)                    // la remota se ajusta a mi
  }
  pendientes = nuevasPendientes
  aplicarEnDocumento(op)
}

El coste de este atajo es explícito y hay que aceptarlo con los ojos abiertos: el sistema deja de poder funcionar entre pares y deja de poder funcionar sin conexión durante mucho tiempo. Un cliente desconectado acumula pendientes que tendrá que transformar contra todo lo que ocurrió en su ausencia, y como el servidor conserva el orden total, la operación es posible pero cara y el resultado se aleja de la intención cuanto más larga fue la ausencia. La colaboración de Google Docs es excelente mientras hay red y notablemente pobre cuando no la hay, y eso no es un defecto de implementación: es la sombra que proyecta la decisión de tener un secuenciador único. La próxima lección estudiará la familia que renunció al secuenciador para poder trabajar desconectada, y pagó por ello en otra moneda.

Más allá del texto plano: estructura, atributos y explosión de casos

Nada de lo anterior ha salido de una cadena de caracteres, y un documento real no lo es. Tiene negritas, enlaces, títulos, tablas, listas anidadas y bloques incrustados, y todo eso también se edita concurrentemente. La respuesta de OT es enriquecer el vocabulario de operaciones: además de insertar y borrar aparecen operaciones de atributo, que aplican formato a un rango, y operaciones sobre árboles, que mueven o reemplazan nodos de una estructura tipo JSON. El formato de deltas popularizado por el editor Quill es la encarnación más difundida de esta idea, con sus tres primitivas de conservar, insertar y borrar, donde conservar puede además llevar atributos.

// Delta al estilo Quill: conservar avanza el cursor y puede dar formato
type Delta = Array<
  | { retain: number; attributes?: Record<string, unknown> }
  | { insert: string; attributes?: Record<string, unknown> }
  | { delete: number }
>

// Poner negrita a los 5 primeros caracteres y escribir despues
const d: Delta = [
  { retain: 5, attributes: { bold: true } },
  { insert: ' nuevo' },
]

El problema que esto crea es de crecimiento combinatorio, y es la razón práctica de que las implementaciones de OT sean tan difíciles de extender. La función de transformación necesita un caso por cada par ordenado de tipos de operación: con dos tipos son cuatro casos, con cinco tipos son veinticinco, y cada uno debe demostrarse correcto por separado y volver a verificarse cuando se añade el siguiente. Un CRDT, en cambio, compone: se construye un tipo mapa cuyos valores son otros CRDT, y la corrección del conjunto se hereda de la de las piezas sin escribir un solo caso nuevo. Esa asimetría en el coste de extender el modelo de datos —lineal frente a cuadrático— pesa mucho más en la vida real de un producto que cualquier diferencia de rendimiento, y explica buena parte del desplazamiento del ecosistema hacia la otra familia.

📝

Los atributos concurrentes se resuelven con la política que aquí sí vale

Cuando dos personas ponen negrita y cursiva al mismo rango, no hay conflicto: los atributos son independientes y se aplican ambos. Cuando ponen dos colores distintos al mismo rango, sí lo hay, y la solución habitual es la más simple posible, que gane el último por atributo. Nótese que es la misma política que en la primera lección destruía documentos enteros, y aquí es perfectamente aceptable: el daño de perder un color es trivial y recuperable de un vistazo, mientras que el de perder un párrafo es invisible y definitivo. La política nunca fue buena o mala en abstracto; lo que la califica es la granularidad a la que se aplica y el coste de equivocarse.

⚡

OT no resuelve el conflicto: reescribe la pregunta para que el índice vuelva a significar lo mismo

Conviene entender qué clase de objeto es una transformación, porque su naturaleza explica a la vez la potencia y la fragilidad del enfoque. Una operación de OT es un acto de habla con deícticos: insertar en la posición 5 es como decir aquí, y aquí solo significa algo si el oyente comparte el lugar del hablante. La red rompe esa comunidad de lugar, y OT no responde exigiendo que todos vuelvan al mismo sitio —eso sería el bloqueo, y mata el producto—, sino haciendo de traductor: reescribe el aquí del emisor como el allí del receptor, usando como diccionario la lista de cosas que pasaron entre medias. Esto es genuinamente elegante, y también explica por qué el enfoque es tan difícil de hacer bien: la traducción depende del contexto entero, y el contexto es una historia que puede haberse construido por caminos distintos en cada réplica. TP2 no es un tecnicismo caprichoso, es la exigencia de que la traducción no dependa del itinerario del mensajero, y su dificultad es la prueba matemática de que traducir contextos es intrínsecamente más frágil que no necesitar traducción. De ahí se sigue la lección de arquitectura que trasciende este algoritmo: cuando un problema teórico se resiste durante veinte años, la solución industrial casi nunca es resolverlo, sino cambiar la topología para que deje de existir. Google no demostró TP2; puso un servidor en medio, convirtió n réplicas en n conversaciones de dos, y con eso el problema difícil se evaporó. Ese movimiento —comprar simplicidad algorítmica con centralización— es una de las transacciones más repetidas y menos reconocidas de la ingeniería de sistemas, y solo se puede evaluar bien si sabes exactamente qué compraste y qué entregaste: aquí compraste corrección demostrable, orden total y auditoría; entregaste el trabajo sin conexión, la resistencia a que el servidor caiga y cualquier posibilidad de que el documento sea de verdad tuyo.

⚔️ Implementa y rompe tu propia transformación

Escribe la función transformar completa para insertar y borrar sobre una cadena, con desempate por identificador de sitio.
Verifica TP1 por fuerza bruta: genera pares de operaciones concurrentes al azar y comprueba que aplicarlas en los dos órdenes con transformación produce siempre el mismo texto.
Intenta verificar TP2 con tríos de operaciones concurrentes propagadas por todos los órdenes posibles. Documenta el primer contraejemplo que encuentres.
Implementa el bucle cliente-servidor con cola de pendientes y comprueba que un cliente con doscientos milisegundos de latencia converge con el servidor.
Simula una desconexión de dos minutos con escritura continua en ambos lados y describe cualitativamente cuánto se aleja el resultado de la intención original.
Explica en dos frases por qué un servidor que impone orden total hace innecesaria la propiedad TP2.