Transformación operacional: reescribir la operación

El nivel anterior terminó con una tesis: cuando dos operaciones conmutan, el conflicto desaparece por construcción. La transformación operacional nace de una intuición distinta y anterior, y conviene entenderla en sus propios términos antes de juzgarla desde los CRDT. Su punto de partida es que las operaciones que la gente ejecuta de verdad —insertar aquí, borrar esto— no conmutan y no van a conmutar, porque están formuladas contra una posición en el documento y esa posición se mueve bajo los pies. La propuesta no es cambiar la operación por otra que conmute, sino conservarla tal como el usuario la generó y reescribir sus parámetros en el momento de aplicarla, de modo que exprese sobre el estado de llegada la misma intención que expresaba sobre el estado de partida. Esta lección instala esa idea con precisión, la sitúa en el artículo de 1989 que la fundó y explica por qué tardó veinte años en volverse infraestructura cotidiana.

El índice que caducó mientras viajaba

Toma el documento abc replicado en dos sitios sin coordinación. La réplica A inserta X en la posición 1 y obtiene aXbc. La réplica B, sin haber visto nada, borra la posición 1 y obtiene ac. Ambas son operaciones perfectamente definidas sobre el estado que cada autor tenía delante. El problema aparece al intercambiarlas: si A aplica literalmente borrar la posición 1 sobre aXbc, elimina la X que acaba de escribir, y si B aplica literalmente insertar X en 1 sobre ac obtiene aXc. Las réplicas divergen, y no por un fallo de transporte ni por una carrera de relojes, sino porque el número 1 significaba cosas distintas en cada lado.

// La operacion viaja intacta y por eso miente al llegar
const doc = "abc";
const opA = { tipo: "insertar", pos: 1, texto: "X" };
const opB = { tipo: "borrar",   pos: 1, largo: 1 };

aplicar(aplicar(doc, opA), opB); // "abc": el borrado se come la X recien puesta
aplicar(aplicar(doc, opB), opA); // "aXc": aqui el borrado hizo lo que queria su autor

El diagnóstico exacto importa porque descarta las salidas fáciles. El índice no es un dato del documento sino una coordenada relativa a un estado, y cuando ese estado cambia la coordenada apunta a otro sitio sin avisar de nada. Bloquear el documento mientras alguien escribe devuelve la latencia al camino crítico de cada pulsación y anula el motivo de replicar. Reenviar el documento completo en cada cambio es correcto y ruinoso en ancho de banda, y además destruye la intención: el receptor recibe un resultado y ya no puede saber qué se pretendía. Y aplicar sin más una política de último escritor sobre el documento entero es la técnica que la lección tres del nivel anterior descartó con detalle.

La propuesta de la transformación operacional es la única que conserva las tres cosas que interesan a la vez —latencia local nula, tráfico proporcional al cambio e intención recuperable— y consiste en aceptar que la operación llegará descontextualizada y repararla en el destino. Si la réplica A sabe que su documento contiene una inserción de un carácter en la posición 1 que el emisor de borrar 1 no conocía, puede deducir que el carácter que aquel quería eliminar está ahora en la posición 2, y aplicar borrar 2. El resultado es aXc en ambos lados. Nada se ha bloqueado, nada se ha retransmitido entero y nadie ha perdido su edición.

flowchart TD
D0[documento abc en las dos replicas] --> A1[replica A inserta X en la posicion 1]
D0 --> B1[replica B borra la posicion 1]
A1 --> AX[estado aXbc]
B1 --> BX[estado ac]
AX --> T1[A recibe borrar 1 y lo transforma en borrar 2]
BX --> T2[B recibe insertar X en 1 y lo deja igual]
T1 --> F[aXc en las dos replicas]
T2 --> F
style D0 fill:#89b4fa,color:#11111b
style F fill:#a6e3a1,color:#11111b

La función de transformación y su argumento oculto

La pieza central es una función de dos argumentos, transformar(a, b), que recibe una operación a y otra operación b concurrente con ella y definida sobre el mismo estado, y devuelve una versión a' de la primera destinada a aplicarse después de la segunda. La condición que debe cumplir es de igualdad de estados: aplicar b y luego a' tiene que dar lo mismo que aplicar a y luego la simétrica b'. Escrita así parece una identidad algebraica menor; en realidad es la especificación completa del sistema, y el resto de la lección siguiente consiste en descubrir lo caro que sale satisfacerla.

// Insercion frente a insercion concurrente
function transformarInsertInsert(a, b) {
  if (a.pos < b.pos) return a;                                  // b queda a la derecha
  if (a.pos > b.pos) return { ...a, pos: a.pos + b.texto.length };
  // Empate exacto: hace falta un criterio total, estable y compartido
  return a.sitio < b.sitio ? a : { ...a, pos: a.pos + b.texto.length };
}

// Insercion frente a borrado concurrente
function transformarInsertDelete(a, b) {
  return a.pos > b.pos ? { ...a, pos: a.pos - b.largo } : a;
}

Ya en este fragmento minúsculo hay tres detalles que anticipan toda la dificultad del nivel. El primero es que hacen falta cuatro funciones y no una, porque cada par ordenado de tipos —inserción frente a inserción, inserción frente a borrado, borrado frente a inserción, borrado frente a borrado— tiene su propia semántica. El segundo es que la función no es simétrica: transformar a contra b y transformar b contra a son cálculos distintos que deben encajar entre sí. Y el tercero es que la transformación puede aniquilar la operación: si dos réplicas borran concurrentemente el mismo carácter, la segunda no tiene ya nada que borrar, y el sistema necesita representar explícitamente la operación vacía en lugar de tratarla como un caso de error.

// Borrado frente a borrado: los rangos pueden solaparse o desaparecer
function transformarDeleteDelete(a, b) {
  if (a.pos >= b.pos + b.largo) return { ...a, pos: a.pos - b.largo };
  if (a.pos + a.largo <= b.pos) return a;
  const solapado = Math.min(a.pos + a.largo, b.pos + b.largo) - Math.max(a.pos, b.pos);
  const restante = a.largo - solapado;
  if (restante <= 0) return { tipo: "vacia" };          // b ya lo borro todo
  return { ...a, pos: Math.min(a.pos, b.pos), largo: restante };
}

Fíjate en el desempate del caso de igualdad, porque es donde se cuela la primera decisión que la matemática no dicta. Si dos personas insertan en la misma posición, ambos órdenes producen documentos distintos y ambos son defendibles; el algoritmo elige uno mediante un identificador de sitio, y esa elección tiene que ser total, determinista e idéntica en todas las réplicas o el sistema no converge. Es exactamente la misma clase de decisión de política que el nivel anterior identificó al hablar de prioridad al alta o a la baja en un conjunto: no ha desaparecido, se ha mudado dentro de la función de transformación.

El segundo detalle es más profundo y suele explicarse mal. transformar no es una función sobre valores sino sobre contextos. Una operación no significa nada por sí sola: significa algo relativa al estado sobre el que se generó, y transformarla exige saber con precisión qué operaciones ha visto ya el destino y cuáles no. Por eso todo sistema OT arrastra, además de las funciones, una contabilidad no trivial: cada sitio guarda un registro de las operaciones ejecutadas y un vector que resume cuántas ha visto de cada réplica, y al recibir una operación remota la transforma una por una contra el sufijo exacto del registro que el emisor desconocía. La función es la parte visible; la contabilidad del contexto es la que consume el código.

GROVE, 1989: de dónde viene la idea

La formulación original está en Concurrency Control in Groupware Systems, de C. A. Ellis y S. J. Gibbs, presentado en la conferencia SIGMOD de 1989. El contexto no era la web sino GROVE, un editor de esquemas para trabajo en grupo desarrollado en el consorcio MCC, y la pregunta que el artículo se plantea es explícitamente una pregunta de control de concurrencia: qué hacer cuando la respuesta canónica de las bases de datos —serializar y bloquear— resulta inaceptable porque hay una persona esperando delante de la pantalla y la latencia de la coordinación es visible para ella. El artículo describe un algoritmo distribuido de transformación de operaciones, conocido después como dOPT, en el que cada sitio mantiene un registro de peticiones y un vector de estado, y transforma las operaciones remotas contra las locales que el emisor no había visto.

El aparato de contabilidad que el artículo describe merece atención porque sobrevive intacto en las implementaciones actuales. Cada sitio mantiene dos cosas además del documento: un registro con las operaciones que ha ejecutado, en el orden en que las ejecutó, y un vector de estado que cuenta cuántas operaciones ha recibido de cada participante. Cuando llega una operación remota acompañada del vector de su emisor, la comparación entre ambos vectores identifica con exactitud qué entradas del registro local eran desconocidas para quien la generó, y la operación se transforma sucesivamente contra esa sublista. Es la misma comparación de vectores que el nivel 22 construyó para detectar concurrencia, aplicada aquí no para decidir si hay conflicto sino para calcular contra qué hay que reparar.

// El sufijo del registro que el emisor no habia visto
function pendientesPara(registro, vectorEmisor) {
  return registro.filter((entrada) => entrada.contador > (vectorEmisor[entrada.sitio] ?? 0));
}

function integrar(opRemota, registro, vectorEmisor) {
  let op = opRemota;
  for (const local of pendientesPara(registro, vectorEmisor)) {
    op = transformar(op, local.operacion); // una reparacion por cada desconocida
  }
  return op;
}

Merece la pena subrayar dos rasgos del planteamiento de 1989 que explican buena parte de lo que vino después. El primero es que las operaciones consideradas son deliberadamente pobres: insertar un carácter y borrar un carácter sobre una secuencia lineal. Esa pobreza no es un descuido de un trabajo temprano, es la condición que hace manejable la matriz de transformación, y cuando los editores reales necesitaron formato, bloques anidados y movimientos de nodos, el coste creció exactamente por donde el artículo había sido prudente. El segundo es que el algoritmo está pensado para una topología entre iguales, sin servidor: cada sitio transforma contra su propio registro. Es una elección de diseño coherente con los sistemas distribuidos de la época y, como la lección tres explicará, es también la que la industria acabaría abandonando.

Lo que la hizo famosa

Entre el artículo de 1989 y la fama pública hay dos décadas y dos escalones. El primero es High-latency, low-bandwidth windowing in the Jupiter collaboration system, de Nichols, Curtis, Dixon y Lamping, publicado en UIST en 1995, que reformula el problema colocando un servidor en el centro y reduciendo la transformación general a una relación de dos partes entre cada cliente y ese servidor. Ese trabajo, y no el de 1989, es el que describe la arquitectura que casi todo OT desplegado usa hoy, y la lección siguiente a la próxima lo desarrolla en detalle porque su consecuencia para local-first es decisiva.

Entre medias hay una línea de trabajo que refinó el algoritmo entre iguales y que conviene conocer porque fija el vocabulario. El artículo de Ressel, Nitsche-Ruhland y Gunzenhäuser presentado en CSCW en 1996 introdujo adOPTed junto con un modelo geométrico del espacio de transformaciones, y el de Sun y Ellis en CSCW de 1998 propuso la familia GOT y GOTO separando dos operaciones inversas entre sí: la transformación de inclusión, que adapta una operación para que tenga en cuenta otra que sí ocurrió antes, y la de exclusión, que hace lo contrario y desmonta el efecto de una operación del contexto de otra. Esa segunda es la que permite reordenar el registro para ponerlo en la forma que la transformación necesita, y es también la que introduce buena parte de la dificultad que la lección siguiente detalla.

El segundo escalón es el navegador. Cuando la edición colaborativa se volvió una expectativa de producto en la web, OT encajaba con una precisión notable en el entorno disponible: el documento seguía siendo una cadena de texto normal, el servidor ya existía y estaba conectado por definición, los mensajes eran pequeños y el estado que había que guardar era el documento actual más un poco de historia reciente. Editores como Etherpad, el sistema Google Wave presentado en 2009 y su documento técnico sobre transformación operacional publicado en 2010, y las suites ofimáticas colaborativas que se generalizaron después, llevaron la técnica a una escala de uso que ningún trabajo de laboratorio había visto. La consecuencia cultural es que buena parte de una generación de desarrolladores conoció el problema de la edición concurrente ya envuelto en su solución OT, y esa familiaridad explica tanto la solidez de las implementaciones actuales como la resistencia inicial a mirar la alternativa.