Su lugar: entre transformación operacional y CRDT

El track lleva varios niveles presentando la transformación operacional y los CRDT como dos escuelas enfrentadas, con una historia de rivalidad académica que hizo que durante dos décadas se leyeran como alternativas excluyentes. Eg-walker desmonta ese encuadre de la forma más incómoda posible para ambas: tomando de cada una la mitad que funcionaba. De la transformación operacional toma la representación —operaciones originales con índices, guardadas tal cual y nunca reescritas— y de los CRDT toma el procedimiento de integración, que coloca las ediciones concurrentes por identidad y no por transformación sucesiva. El resultado no es un compromiso tibio sino una tercera posición con propiedades propias, cuya salida se cree idéntica a la de un CRDT conocido y cuya implementación ya está en producción. Esta lección sitúa el algoritmo en el mapa, explica su parentesco con Fugue y repasa quién lo usa hoy.

Por qué se le llama intermedio

La descripción de Eg-walker como punto intermedio no es una etiqueta cómoda: se puede justificar eje por eje, y hacerlo aclara qué heredó exactamente de cada tradición.

En el eje de la representación es puro linaje de transformación operacional. Lo que se persiste son operaciones con posiciones numéricas, medidas contra el estado que su autor tenía delante, sin ninguna identidad por carácter. Cualquiera que haya leído los trabajos clásicos de esta escuela reconoce el formato al instante, porque es literalmente el suyo.

En el eje de la integración es puro linaje de CRDT. Colocar una operación concurrente no se hace transformándola contra cada operación intermedia, que es el mecanismo que hace intratables las ramas largas, sino traduciéndola a identidades estables y aplicando una regla de desempate determinista. Es el procedimiento de una secuencia convergente, con la única particularidad de que las identidades son temporales.

Y en el eje de la persistencia no es ninguna de las dos, sino algo que ninguna de ellas contemplaba: el estado del documento se declara derivable y se recalcula bajo demanda. La transformación operacional también deriva el estado, pero lo hace transformando y por tanto reescribiendo lo que guarda; los CRDT persisten el estado ya integrado y no derivan nada. La tercera posición —persistir sin reescribir y derivar sin transformar— es la que no estaba ocupada.

Tres ejes, tres respuestas por escuela

  que se persiste
    OT ......... operaciones originales con indices
    CRDT ....... estructura con identidades y lapidas
    Eg-walker .. operaciones originales mas contexto causal

  como se integra lo concurrente
    OT ......... transformando contra las operaciones intermedias
    CRDT ....... por identidad y desempate determinista
    Eg-walker .. por identidad y desempate determinista

  donde vive el estado
    OT ......... derivado, pero la representacion se reescribe
    CRDT ....... materializado y permanente
    Eg-walker .. derivado, con andamio temporal que se descarta

flowchart TB
OT[transformacion operacional] -->|representacion: operaciones originales| EG[Eg walker]
CRDT[crdt de secuencia] -->|integracion: identidades y desempate| EG
EG --> P1[carga rapida y memoria baja en reposo]
EG --> P2[fusion de ramas largas sin coste cuadratico]
EG --> P3[sin servidor central y valido en pares]
style EG fill:#cba6f7,color:#11111b
style P1 fill:#a6e3a1,color:#11111b
style P2 fill:#a6e3a1,color:#11111b
style P3 fill:#a6e3a1,color:#11111b

Hay una tercera herencia que suele pasarse por alto y que es la que decide su encaje en local-first: Eg-walker se puede usar en todos los sitios donde se usa un CRDT, incluidos los sistemas entre pares sin servidor central. Esa propiedad no era obvia de antemano, porque la representación heredada de la transformación operacional viene asociada históricamente a arquitecturas con un servidor que ordena. Aquí la referencia causal explícita sustituye a ese servidor, y por eso la herencia de formato no arrastra la herencia de topología.

El parentesco con Fugue y el problema del entrelazado

Para valorar la calidad de la fusión hace falta un criterio que no sea la convergencia, porque converger es fácil y no dice nada sobre si el resultado es aceptable para una persona. El criterio que la comunidad ha consolidado es el entrelazado, y conviene enunciarlo con un ejemplo. Dos autores escriben a la vez en el mismo punto de un documento vacío: uno teclea la palabra hola y el otro teclea la palabra adios. Todos los algoritmos convergen; la pregunta es a qué. Un resultado aceptable es hola seguido de adios, o adios seguido de hola. Un resultado inaceptable es haodliaos, con las letras de ambos intercaladas.

El entrelazado no es una curiosidad teórica: es un fallo visible que destruye texto y que aparece en la práctica cuando dos personas escriben en el mismo párrafo. Varias familias clásicas de secuencia lo sufren en algún escenario, y durante años se trató como una rareza aceptable. El trabajo que cambió esa conversación fue Fugue, de Matthew Weidner, Joseph Gentle y Martin Kleppmann, que caracterizó el fenómeno con precisión y construyó una familia de algoritmos que lo minimiza de forma demostrable. FugueMax es la variante que alcanza la garantía más fuerte de no entrelazado.

Dos autores insertan a la vez en el mismo hueco

  entrelazado ....... h a o d l i a o s   destruye ambas aportaciones
  no entrelazado .... h o l a a d i o s   una despues de otra, legible
  no entrelazado .... a d i o s h o l a   el orden lo decide el desempate

La afirmación relevante para este nivel es que se cree que Eg-walker es isomorfo a FugueMax, es decir, que ante las mismas operaciones produce el mismo resultado. Conviene leer las dos partes de la frase con cuidado. La primera parte es una buena noticia sustancial: significa que el algoritmo no compra su rendimiento a costa de la calidad de la fusión, sino que hereda la mejor garantía disponible frente al entrelazado. La segunda parte es el matiz honesto: se cree, y esa formulación prudente refleja que el enunciado se apoya en el análisis del comportamiento de ambos y no en una demostración formal cerrada de equivalencia.

Que la relación se pueda plantear siquiera dice algo importante sobre la naturaleza del trabajo. Si dos algoritmos con representaciones internas radicalmente distintas —uno que guarda un árbol de identidades permanente y otro que no guarda ninguna— producen la misma salida ante las mismas entradas, entonces lo que define un algoritmo de secuencia no es su estructura de datos sino su función de fusión, es decir, la regla que decide dónde va cada inserción concurrente. La estructura es implementación; la regla es semántica. Esa separación es la que permite que el nivel entero exista, porque autoriza a cambiar por completo lo primero sin tocar lo segundo.

Tiene además una consecuencia práctica inmediata y muy útil al implementar: se pueden usar los casos de prueba de una familia para validar la otra. Si construyes tu propia versión del algoritmo, la forma más rápida de ganar confianza es generar historias aleatorias con concurrencia, ejecutarlas contra una implementación de FugueMax y contra la tuya, y comprobar que el texto resultante coincide carácter a carácter. Es una prueba diferencial barata que detecta exactamente los errores que las pruebas de convergencia no ven, porque converger a un texto entrelazado también es converger.

Quién lo implementa y qué usar para qué

El estado de las implementaciones es más maduro de lo que sugiere la fecha de publicación, porque el trabajo de ingeniería precedió al artículo en lugar de seguirlo. Es un orden poco habitual y explica varias cosas: el algoritmo se depuró contra trazas reales antes de tener nombre, y el artículo describe algo que ya funcionaba en lugar de proponer algo que habría que construir.

Que exista una implementación de referencia legible junto a una optimizada no es un detalle menor y merece un comentario, porque marca una diferencia de calidad frente a buena parte de la literatura de esta materia. Los algoritmos de texto colaborativo tienen una historia larga de resultados publicados cuyas implementaciones eran inaccesibles o cuyas descripciones omitían el detalle que hacía falta para reproducirlas, y esa opacidad es la razón de que se hayan publicado varias correcciones de algoritmos clásicos años después de su aparición. Poder leer el algoritmo completo en un lenguaje corriente, sin la ofuscación que introduce cualquier optimización seria, es lo que permite auditarlo de verdad.

// Lo que cambia al adoptarlo no es la API, es el modelo de persistencia
guardar(documento);        // antes: volcar la estructura completa del CRDT
anexar(eventosNuevos);     // ahora: anadir al final del registro de eventos

// Y lo que aparece nuevo es una pregunta de producto
// cuanta historia conservas, y donde la cortas si decides cortarla

La adopción, por tanto, no se decide comparando funciones sino comparando lo que se guarda. La superficie de uso de estas bibliotecas es muy parecida entre sí: insertar, borrar, obtener texto, aplicar un cambio remoto, suscribirse a los cambios. Lo que cambia por debajo es el formato en disco y su curva de crecimiento, y esa es exactamente la parte que resulta cara de migrar más adelante. Elegir aquí es elegir con qué vas a vivir dentro de tres años.

Qué deja este nivel más allá del algoritmo

Antes del cierre conviene resumir qué queda en pie de los cinco temas del nivel, porque el conjunto forma un argumento y no una colección de datos. El diagnóstico fue que un CRDT de secuencia guarda un metadato por cada carácter que existió, incluidos los borrados, y que ese metadato domina la memoria y el tiempo de carga. La idea fue guardar en su lugar una lista inmutable y solo-añadir de las operaciones originales, con su contexto causal, y tratar el texto como algo derivable. El mecanismo fue recorrer el grafo levantando un andamio temporal, retrocediendo y avanzando eventos según la rama, y vaciándolo por completo en cada versión crítica. Los resultados fueron un orden de magnitud menos de memoria en reposo, cargas desde disco órdenes de magnitud más rápidas y un peor caso comparable. Y el lugar es una tercera posición que combina la representación de una escuela con la integración de la otra.

Queda pendiente una pregunta que este nivel no responde y que el track aborda más adelante: qué hacer cuando el registro de eventos, que crece de forma monótona, se vuelve demasiado grande por sí solo. Eg-walker traslada el problema del tamaño desde la estructura viva hasta el archivo histórico, y ese archivo se comprime mucho mejor y se lee de forma secuencial, pero no es infinito. La compactación, la poda de historia y el direccionamiento por contenido son las herramientas de esa conversación, y tienen su propio bloque de niveles.