La idea: guardar la operación original, no el andamio

La lección anterior terminó con una distinción que ahora hay que convertir en estructura de datos: el hecho de que ocurrió una edición es permanente, y el aparato que hizo falta para integrarla es circunstancial. Eg-walker, presentado por Joseph Gentle y Martin Kleppmann en EuroSys 2025, toma esa distinción literalmente y la lleva hasta el final. Lo único que persiste es una lista inmutable y solo-añadir de las operaciones originales, es decir, exactamente lo que el usuario hizo, expresado con posiciones numéricas como lo expresaría un algoritmo de transformación operacional, más una referencia a lo que ese usuario veía en el momento de hacerlo. Nada de identificadores por carácter, nada de punteros a vecinos, nada de lápidas persistidas. El texto no está guardado en ningún sitio: se calcula. Esta lección construye ese modelo de datos pieza a pieza y examina qué se gana, qué se pierde y qué obliga a replantear.

Lo que persiste cada escuela ante la misma sesión

La comparación más instructiva es la más concreta: alguien escribe la palabra hola, borra la última letra y escribe una i. Tres pulsaciones más dos, y cuatro caracteres visibles al final. Veamos qué queda guardado en cada caso.

Un algoritmo de transformación operacional guarda las operaciones tal como se produjeron, con índices numéricos: inserta en la posición cero, inserta en la uno, borra en la tres. Es una representación compactísima, apenas mayor que el texto, y su debilidad conocida es que esos índices solo son válidos respecto a un estado concreto del documento, de modo que integrar una operación ajena exige transformarla contra todo lo que ocurrió mientras tanto. Cuando dos ramas divergen mucho, ese trabajo crece hasta hacer inviable la fusión de historias largas sin un servidor que imponga un orden común.

Un CRDT de secuencia guarda lo contrario: no las operaciones sino su efecto ya traducido a una estructura con identidades estables, que es precisamente lo que le permite integrar cualquier operación en cualquier orden sin transformar nada. Paga por ello el precio de la lección anterior, que es conservar esa estructura entera y para siempre.

Sesion: escribir hola, borrar la a, escribir la i

  Transformacion operacional
    ins 0 h | ins 1 o | ins 2 l | ins 3 a | del 3 | ins 3 i
    compacto, pero cada indice depende del estado exacto del autor

  CRDT de secuencia
    seis elementos con id, vecino izquierdo, vecino derecho y lapida
    integrable en cualquier orden, pero permanente y voluminoso

  Eg-walker
    las mismas seis operaciones con indices
    mas, en cada una, que operaciones habia visto su autor

La tercera fila es la propuesta entera, y su economía salta a la vista: se parece a la primera en tamaño y a la segunda en capacidad. El único añadido respecto a la representación de la transformación operacional es la referencia causal, y ese añadido es lo que sustituye a toda la maquinaria de identidades de la segunda.

El grafo de eventos: la operación y lo que su autor veía

La pieza que convierte una lista de operaciones con índices en algo con sentido global es la referencia causal, y conviene entender exactamente qué guarda y por qué basta con eso. Cada evento apunta a sus padres, es decir, al conjunto de eventos que su autor había integrado en el instante de producirlo. Ese conjunto define sin ambigüedad el estado del documento contra el cual los índices de esa operación son correctos.

// Un evento: la operacion original mas su contexto causal
const evento = {
  id: { agente: "a7", seq: 412 },        // identidad del evento, no del caracter
  padres: [{ agente: "b1", seq: 88 }],   // que habia visto el autor al emitirlo
  op: { tipo: "ins", pos: 3, texto: "i" }, // indice, como en transformacion operacional
};

// El grafo completo es una lista solo-anadir de eventos como el anterior
const grafo = [];
function registrar(ev) {
  if (grafo.some((e) => mismoId(e.id, ev.id))) return; // idempotente
  grafo.push(ev);                                       // nunca se modifica lo ya escrito
}

Fíjate en un detalle decisivo: el identificador es del evento, no del carácter. Un evento puede insertar veinte caracteres de golpe y sigue siendo un solo registro. La identidad que la lección anterior repartía carácter a carácter aquí se reparte operación a operación, y las operaciones son órdenes de magnitud menos numerosas que los caracteres cuando la gente escribe de forma normal.

El grafo resultante es un grafo dirigido acíclico exactamente igual al de un sistema de control de versiones distribuido, con la misma semántica: las aristas son la relación de precedencia causal, las ramas son divergencias que aún no se han fusionado y las cabezas son los eventos sin descendientes conocidos. Todo lo que aprendiste en el nivel de relojes lógicos sobre resúmenes por cabezas, cálculo de diferencias y ancestros comunes se aplica aquí sin traducción.

Esa continuidad no es solo pedagógica, también es operativa. El protocolo de sincronización entre dos réplicas es el mismo que ya conoces: intercambiar cabezas, calcular qué le falta a cada una recorriendo el grafo hacia atrás desde las cabezas ajenas, y enviar únicamente esos eventos. No hace falta una sesión, ni un orden acordado, ni que las dos partes estén de acuerdo sobre nada previo. Y como los eventos son inmutables e idempotentes, reenviar de más no rompe nada, lo que permite protocolos de transporte deliberadamente simples.

flowchart LR
R[raiz del documento] --> A1[a7 emite ins 0 h]
A1 --> A2[a7 emite ins 1 o]
A2 --> B1[b1 emite ins 2 mundo]
A2 --> C1[c3 emite del 1]
B1 --> M[fusion: ambas ramas son padres]
C1 --> M
style M fill:#cba6f7,color:#11111b
style B1 fill:#89b4fa,color:#11111b
style C1 fill:#89b4fa,color:#11111b

Una precisión sobre los padres que evita un malentendido habitual: no hace falta enumerar todo lo que el autor había visto, sino únicamente las cabezas de ese conjunto, es decir, los eventos que no eran ancestros de ningún otro evento visto. El resto se deduce recorriendo el grafo hacia atrás. En la enorme mayoría de los casos hay una sola cabeza y la lista de padres tiene un elemento; solo tras integrar una rama ajena aparece un evento con dos.

Las dos ramas azules del diagrama son el caso interesante y el que ocupa la lección siguiente: dos operaciones con índices calculados sobre el mismo estado padre, ninguna de las cuales sabe de la otra. Sus índices son mutuamente incorrectos, y sin embargo el grafo contiene toda la información necesaria para colocarlas bien, porque cada una declara con exactitud contra qué estado se midió.

Por qué la lista puede ser inmutable y solo-añadir

Que el registro sea de solo-añadir no es una elección estética sino una consecuencia de qué se está guardando, y sus efectos prácticos son mayores de lo que parece a primera vista. Un evento describe algo que ya sucedió en un contexto que ya está determinado; ninguna información futura puede alterarlo, porque su verdad no depende del estado global sino del estado local que su autor tenía delante. La transformación operacional clásica, en cambio, reescribe las operaciones al integrarlas, y por eso lo que guarda no es estable.

La escritura incremental merece un comentario aparte porque es la ventaja que más cambia la experiencia de uso y la que menos se menciona. En un CRDT convencional, persistir el documento implica volcar o actualizar una estructura grande, y las bibliotecas resuelven eso con formatos comprimidos que hay que regenerar cada cierto tiempo. Aquí el guardado es un anexado al final de un archivo, la operación más barata que ofrece cualquier sistema de ficheros, y su coste es proporcional a lo que el usuario acaba de escribir y no a lo que el documento ya contenía.

El estado del documento como función derivada

La consecuencia conceptual de este modelo de datos es la que hay que interiorizar antes de pasar al recorrido: en Eg-walker el documento no es un objeto almacenado que se actualiza, sino el resultado de aplicar una función al grafo. El texto es una vista materializada de la historia, y la estructura con identidades y lápidas que la lección anterior describía como el documento pasa a ser un intermedio temporal que se fabrica cuando hace falta calcular esa vista y se destruye después.

// El texto no se guarda: se deriva del grafo
function textoDe(grafo, hastaVersion) {
  const orden = ordenTopologico(grafo, hastaVersion);
  let estadoInterno = crearEstadoVacio();   // el andamio, efimero
  for (const ev of orden) estadoInterno = integrar(estadoInterno, ev);
  return proyectar(estadoInterno);          // el texto visible
}
// Terminada la llamada, estadoInterno queda sin referencias y se recolecta

Esto no es gratis, y conviene decir con claridad qué se paga. Derivar el estado desde cero para un documento con historia larga es caro, así que un sistema práctico mantiene el texto visible en memoria y le aplica las operaciones nuevas de forma incremental, reservando el recorrido completo para los casos en que de verdad hace falta. La lección siguiente muestra que esos casos son menos y más acotados de lo que se teme, y la cuarta muestra cuánto cuestan cuando se miden en trazas reales.

Hay una segunda contrapartida que conviene anticipar porque cambia el diseño del producto y no solo el del algoritmo: el registro crece de forma monótona y nada lo reduce por sí solo. En un CRDT esa acumulación estaba escondida dentro de la estructura y se percibía como memoria; aquí está explícita en un archivo cuyo tamaño se puede mirar. Es más honesta y también más incómoda, porque obliga a decidir de forma consciente cuánta historia se conserva, dónde se corta si se corta y qué se pierde al hacerlo. Esa decisión existía antes igual, solo que nadie la tomaba.