El recorrido: reproducir el efecto sin conservar el andamio

Guardar solo las operaciones originales sería una idea barata si no hubiera que responder a la pregunta que la hace difícil: cómo se colocan bien dos ediciones concurrentes cuyos índices son mutuamente incorrectos, sin conservar de forma permanente las identidades que un CRDT usaría para ello. La respuesta de Eg-walker es que esas identidades se fabrican durante la fusión, se usan mientras hacen falta y se tiran después. El recorrido del grafo mantiene simultáneamente dos versiones del mismo estado interno —aquella contra la que un evento fue emitido y aquella donde todo lo conocido está aplicado— y navega entre ambas retrocediendo y avanzando eventos según se mueve de rama en rama. Esta lección desmonta ese mecanismo y explica por qué su coste se concentra exactamente donde hay concurrencia real y desaparece donde no la hay, que es la razón última de todo el resultado.

El estado interno: traducir índices a identidades y volver

El recorrido tiene un solo trabajo y conviene enunciarlo con precisión antes de cualquier detalle. Un evento dice inserta en la posición tres, y esa posición está medida contra el estado que su autor tenía delante. Para saber dónde va esa inserción en el estado que contiene además todo lo que otros hicieron en paralelo, hay que traducir: convertir el índice tres en la identidad del carácter que ocupaba ese hueco para el autor, colocar la inserción respecto a esa identidad con una regla de desempate estable, y traducir el resultado de vuelta a un índice del estado final para aplicarlo al texto.

Esa traducción necesita una estructura que asocie identidades y posiciones, y esa estructura es exactamente el andamio de un CRDT de secuencia. La diferencia con el nivel anterior no está en su forma sino en su duración: aquí nace al empezar la fusión y muere al terminarla. La implementación práctica es un árbol equilibrado que mantiene en cada nodo cuántos caracteres visibles cuelgan de él, de modo que localizar la posición mil es un descenso logarítmico en lugar de un recorrido lineal.

// El andamio efimero: identidades solo mientras dura la fusion
const interno = crearArbol(); // cada nodo conoce cuantos visibles cuelgan de el

function aplicarEvento(ev) {
  const idDestino = interno.identidadEnPosicion(ev.op.pos, ev.padres);
  const colocado = interno.insertarJunto(idDestino, ev.id, ev.op.texto);
  return interno.posicionVisibleDe(colocado); // indice en el estado final
}

Merece la pena señalar que la regla de desempate que decide qué inserción va antes cuando dos caen en el mismo hueco no es un detalle libre: es la que determina que dos réplicas produzcan el mismo texto, y también la que determina si el resultado es legible o si entrelaza las palabras de dos autores. La lección final vuelve sobre ese punto al hablar del parentesco con otras familias de secuencia.

Conviene también nombrar la asimetría entre inserción y borrado, porque simplifica mucho el modelo mental. Una inserción necesita la traducción completa, porque hay que decidir dónde va respecto a lo que otros insertaron en el mismo punto. Un borrado necesita menos: identifica un carácter que ya existe y lo marca como no visible en el estado interno, y si dos réplicas borran el mismo carácter el resultado es el mismo sin necesidad de desempatar nada, porque borrar es idempotente. Esa asimetría explica por qué las lápidas del andamio temporal son baratas aquí y carísimas en un CRDT: no es que sean distintas, es que aquí solo viven lo que dura el recorrido.

Preparación y efecto: dos versiones del mismo estado

La dificultad técnica del recorrido aparece en cuanto el grafo tiene ramas, y su solución es la contribución más característica del algoritmo. Cuando se procesa un evento de la rama izquierda después de haber procesado eventos de la derecha, el estado interno contiene cosas que el autor del evento izquierdo no había visto. Traducir su índice contra ese estado daría un resultado incorrecto, porque el índice se midió contra un estado más pequeño.

Un enfoque ingenuo simularía una réplica por cada rama, con su copia del estado interno, y eso multiplicaría el consumo por el número de ramas. Eg-walker usa solo dos réplicas simuladas y las guarda en la misma estructura de datos: cada elemento del andamio lleva un estado según la versión de preparación, que es aquella contra la cual se miden los índices del evento que se está procesando, y un estado según la versión de efecto, que es aquella donde está aplicado todo lo conocido.

Un elemento del andamio durante el recorrido

  identidad ......... a7:412
  estado preparacion  no insertado todavia para este evento
  estado efecto ..... insertado y visible en el resultado

  El indice del evento se cuenta sobre el estado de preparacion
  El indice que se aplica al texto se cuenta sobre el estado de efecto

Esta duplicación es lo que permite consultar dos realidades a la vez sin duplicar la estructura. Para calcular la identidad que el autor tenía en su posición tres se cuenta sobre el estado de preparación; para saber dónde aplicar el resultado en el documento final se cuenta sobre el estado de efecto. Ambos recuentos viven en el mismo árbol y se mantienen con el mismo descenso.

flowchart TB
B[base comun del grafo] --> I1[rama izquierda evento e1]
B --> D1[rama derecha evento f1]
I1 --> I2[rama izquierda evento e2]
D1 --> M[punto de fusion]
I2 --> M
M --> P[al saltar de rama se retroceden los eventos ajenos]
P --> A[al fusionar se avanzan de nuevo]
style P fill:#f9e2af,color:#11111b
style A fill:#a6e3a1,color:#11111b

Retroceder y avanzar: mover el andamio en el tiempo

El diagrama nombra las dos operaciones que dan movilidad al recorrido. Retroceder un evento consiste en actualizar el estado de preparación para que se comporte como si ese evento aún no hubiera ocurrido; avanzarlo es lo contrario, hacer que vuelva a tener efecto. Ninguna de las dos toca el estado de efecto ni el texto resultante: solo mueven la ventana desde la cual se interpretan los índices del evento que toca procesar.

El recorrido, entonces, funciona así. Se ordenan los eventos de forma topológica, respetando la precedencia causal. Antes de procesar cada evento se compara la versión de preparación actual con los padres de ese evento; los eventos que están aplicados en la preparación pero que el autor no había visto se retroceden, y los que el autor sí había visto pero no están aplicados se avanzan. Solo entonces se traduce el índice. El estado de efecto, mientras tanto, crece de forma monótona y nunca retrocede.

// Ajustar la ventana de preparacion a lo que veia el autor del evento
function prepararPara(ev, estado) {
  for (const otro of estado.aplicadosEnPreparacion) {
    if (!esAncestroDe(otro, ev.padres)) retroceder(otro, estado);
  }
  for (const necesario of alcanzablesDesde(ev.padres)) {
    if (!estado.aplicadosEnPreparacion.has(necesario)) avanzar(necesario, estado);
  }
}

El coste de estos ajustes es real y hay que nombrarlo sin adornos: en un grafo con mucha concurrencia entrelazada, el recorrido puede retroceder y avanzar el mismo evento varias veces, y eso es trabajo de CPU que un CRDT convencional no hace porque su estructura ya venía colocada. Los autores lo reconocen abiertamente. El argumento no es que ese trabajo sea despreciable, sino que se paga en el único momento en que hay algo que decidir, y que a cambio habilita optimizaciones de representación que compensan de sobra.

Las versiones críticas y el vaciado del estado interno

Queda la pieza que cierra el argumento y que explica por qué todo esto acaba siendo barato. Hay puntos del grafo por los que pasa toda la historia: versiones que son ancestro de todo lo que viene después y descendiente de todo lo que vino antes, sin ninguna rama que las esquive. En un documento escrito por personas, esos puntos aparecen continuamente, porque basta con que todos los participantes se hayan sincronizado una vez para que el grafo se estreche a un solo hilo.

En esos puntos —los autores los llaman versiones críticas— ocurre algo notable: ningún evento futuro podrá ser concurrente con ningún evento anterior, porque todos los eventos futuros descienden de esa versión y todos los anteriores son sus ancestros. Y si nada futuro puede ser concurrente con nada pasado, entonces las identidades que el andamio guardaba para colocar lo pasado no le sirven a nadie nunca más. Se pueden tirar todas. El estado interno se vacía por completo y el recorrido continúa desde cero, con el texto acumulado como única herencia.

Conviene detenerse en la segunda tarjeta porque es la que convierte una idea elegante en una garantía de ingeniería. Sin vaciado, el andamio crecería con el documento y el algoritmo tendría el mismo problema que quería resolver, solo que desplazado al momento de la carga. Con vaciado, el pico de memoria queda determinado por el tramo de grafo más concurrente que haya que atravesar, que en la práctica es el trabajo de una sesión offline o de unas horas de edición simultánea, no el de dos años.

Un grafo real visto por tramos

  lunes .......... un autor, sin ramas ....... version critica al final
  martes ......... dos autores en paralelo ... andamio activo, se vacia al sincronizar
  miercoles ...... nadie edita ............... sin andamio
  jueves ......... un autor offline y otro no  andamio al fusionar, se vacia despues

  el pico de memoria lo fija el martes, no la suma de la semana

La detección de esas versiones es barata y no requiere recorrer nada dos veces: mientras se avanza en orden topológico, una versión es crítica si en ese punto solo hay una cabeza pendiente, es decir, si todo lo procesado converge en un único evento del que colgará todo lo que falta. Es la misma comprobación que hace un sistema de control de versiones para saber si el historial está en una sola línea, y tiene el mismo coste, que es prácticamente ninguno.