Por qué resultó fácil de optimizar: tramos, no caracteres

Un artículo que propone una propiedad de corrección nueva tiene que responder antes o después a la objeción práctica: ¿cuánto cuesta? La respuesta de Fugue es inusualmente buena, y lo interesante no es la cifra sino de dónde sale. No hay ningún truco de compresión propio ni ninguna estructura ingeniosa: las optimizaciones están tomadas de las que ya usaban Yjs y la variante segmentada de RGA, y son las mismas que cualquiera aplicaría. Lo que cambia es que la formulación de Fugue admite esas optimizaciones sin que la semántica se resienta, y esa admisibilidad no es un accidente afortunado. La escritura normal, de izquierda a derecha, produce en el árbol de Fugue una cadena en la que cada nodo es el único hijo derecho del anterior, y una cadena de hijos únicos está completamente determinada por su cabeza y su contenido. Guardar un objeto por carácter en ese caso es guardar la misma información cientos de veces. Colapsarla en un objeto por tramo deja intacta la forma del árbol, y como la propiedad de no intercalación es una propiedad de la forma del árbol, no hay nada que volver a demostrar. Esa es toda la historia, y su resultado son metadatos que ocupan el sesenta por ciento del texto que describen.

La cadena que produce el tecleo normal

Vuelve un momento a la regla de colocación de la lección anterior. Al insertar detrás de un elemento que todavía no tiene hijos derechos, el nodo nuevo se cuelga como hijo derecho de ese elemento. Al teclear una palabra de izquierda a derecha, cada carácter se inserta detrás del anterior, que acaba de nacer y por tanto no tiene ningún hijo derecho todavía. La consecuencia es inevitable y es la clave de todo lo que sigue: una ráfaga de tecleo hacia delante produce una cadena descendente en la que cada nodo es el único hijo derecho de su padre.

Una cadena así no contiene apenas información. El identificador del segundo nodo, del tercero y del centésimo son derivables del identificador de la cabeza y de la posición dentro del tramo, porque los identificadores se asignan secuencialmente dentro de una misma réplica. El padre de cada uno es el anterior. El lado de cada uno es el derecho. Lo único genuinamente distinto entre ellos es el valor. Guardar cien objetos con cien punteros a padre para representar cien caracteres consecutivos es, literalmente, almacenar noventa y nueve veces un dato que ya se conocía.

El colapso consiste en sustituir toda la cadena por un solo objeto, que el artículo llama punto de referencia, y que guarda el identificador de la cabeza, la secuencia de valores y la longitud. Cuando alguien inserta concurrentemente en medio del tramo, el punto de referencia se parte en dos y aparece una bifurcación real, que sí hay que representar. El número de objetos deja entonces de crecer con el número de caracteres y pasa a crecer con el número de puntos de bifurcación, que en un texto escrito por personas es una fracción muy pequeña del total.

Merece la pena razonar por qué esa fracción es tan pequeña, porque es una propiedad de cómo escriben las personas y no del algoritmo. Un párrafo de doscientos caracteres tecleado de corrido es un solo tramo. Volver atrás a corregir una palabra parte ese tramo en dos y crea uno nuevo, de modo que una sesión de escritura con muchas correcciones genera más objetos que una de escritura fluida. Una edición concurrente de otra persona en mitad del párrafo hace lo mismo. Pero incluso en la traza real que se usa para medir, que recoge cada pulsación del proceso completo de escritura de un artículo —con sus correcciones, sus reescrituras y sus borrados—, la razón entre caracteres y objetos sigue siendo lo bastante alta como para que los metadatos ocupen menos que el texto. El colapso no es una apuesta optimista sobre un caso ideal: es una apuesta sobre el comportamiento humano, y la traza demuestra que la apuesta se gana.

flowchart TD
A[tecleo de izquierda a derecha] --> B[cada caracter es el unico hijo derecho del anterior]
B --> C[la cadena queda determinada por el id de cabeza y los valores]
C --> D[un objeto por tramo en vez de un objeto por caracter]
B --> E[una insercion concurrente en medio parte el tramo en dos]
E --> F[el numero de objetos crece con las bifurcaciones reales]
D --> G[168 kB guardados para 105 kB de texto plano]
D --> H[2.4 MB en memoria o 23 bytes por caracter]
style D fill:#a6e3a1,color:#11111b
style G fill:#89b4fa,color:#11111b
style H fill:#89b4fa,color:#11111b

Puesto en código, el objeto que sustituye a la cadena es notablemente pobre, y esa pobreza es la medida exacta de cuánta redundancia había antes.

// Un punto de referencia sustituye a toda una cadena de hijos unicos.
// En lugar de un objeto por caracter, un objeto por tramo.
const tramo = {
  idCabeza: "r7:1042",       // identificador del primer nodo de la cadena
  padre: "r3:88",            // padre de la cabeza
  lado: "derecha",           // lado por el que cuelga la cabeza
  valores: "para siempre",   // los trece caracteres consecutivos
};

// Los identificadores interiores no se almacenan: se derivan del offset,
// porque cada replica los asigna de forma secuencial.
function idEnOffset(tramo, offset) {
  const [replica, contador] = tramo.idCabeza.split(":");
  return `${replica}:${Number(contador) + offset}`;
}

// Una insercion concurrente en mitad del tramo lo parte en dos.
// Ahi si aparece una bifurcacion real que ocupa objetos nuevos.
function partir(tramo, offset) {
  return [
    { ...tramo, valores: tramo.valores.slice(0, offset) },
    {
      idCabeza: idEnOffset(tramo, offset),
      padre: idEnOffset(tramo, offset - 1),
      lado: "derecha",
      valores: tramo.valores.slice(offset),
    },
  ];
}

Obsérvese que la función que parte un tramo no consulta ninguna política de fusión, no compara marcas de tiempo y no decide nada: solo reorganiza objetos preservando exactamente la misma relación de parentesco. Esa es la prueba operativa de que la compresión es una transformación de representación y no de semántica. Si al partir un tramo hiciera falta tomar alguna decisión sobre el orden, la compresión estaría tocando el comportamiento observable y habría que rehacer las demostraciones.

Los números sobre una traza real

La evaluación no usa cargas sintéticas. Reproduce una traza real de edición en la que se capturó cada pulsación del proceso de escritura del código fuente de un artículo de diecisiete páginas: 182.315 inserciones de un carácter y 77.463 borrados de un carácter, con un documento final de 104.852 caracteres sin contar lápidas. El texto plano ocupa 105 kB. Se midieron tres implementaciones propias y tres bibliotecas del ecosistema, con cinco ejecuciones de calentamiento y diez de medida.

DOCUMENTO GUARDADO   texto plano de referencia 105 kB

  implementacion        tamano      guardar     cargar
  Fugue                 168 kB       20 ms       13 ms
  Fugue simple        1.021 kB      583 ms      334 ms
  FugueMax simple     1.237 kB      788 ms      522 ms
  Automerge-Wasm        129 kB      180 ms    2.746 ms
  Yjs                   160 kB       17 ms       63 ms
  Y-Wasm                160 kB        5 ms       15 ms

USO EN VIVO POR UN SOLO USUARIO

  implementacion       memoria    bytes por op   ops por segundo
  Fugue                 2,4 MB         46            94.000
  Fugue simple         64,8 MB        151            17.000
  FugueMax simple      71,9 MB        188            16.000
  Automerge-Wasm            -         126            52.000
  Yjs                   3,3 MB         29            39.000

TRAZA REPETIDA CIEN VECES   10,5 millones de caracteres

  Fugue    17.845 kB guardados   1.405 ms guardar    640 ms cargar   223 MB
  Yjs      15.989 kB guardados     479 ms guardar  2.316 ms cargar   294 MB

Antes de interpretar las cifras conviene saber qué mide cada columna, porque cada una corresponde a un momento distinto de la vida de una aplicación local-first y no son intercambiables. El tamaño guardado determina el espacio en disco y el tráfico cuando la sesión se cierra y se vuelve a abrir. El tiempo de carga es latencia de arranque percibida directamente por el usuario, y es la métrica que más suele descuidarse. La memoria aproxima el peso de la pestaña mientras el documento está abierto. Los bytes por operación miden lo que viaja por la red en cada pulsación. Y las operaciones por segundo miden el margen disponible antes de que el modelo se convierta en el cuello de botella. Todo se midió en un mismo entorno modesto y descrito con detalle —Node.js sobre una máquina de cuatro núcleos y dieciséis gigabytes— con cinco ejecuciones de calentamiento y diez de medida, lo que permite comparar sin discutir sobre el banco de pruebas.

Tres lecturas que importan más que las cifras concretas. La primera: los metadatos del CRDT ocupan solo el sesenta por ciento del texto literal, o veintitrés bytes por carácter en memoria, o trece bytes si se cuentan también los caracteres borrados que siguen presentes como lápidas. Eso refuta directamente la crítica más repetida contra los CRDT para texto, que es que su sobrecarga por carácter los hace inviables. La segunda: el rendimiento en vivo está tan lejos de ser un cuello de botella que la comparación es casi cómica —noventa y cuatro mil operaciones por segundo son unos once microsegundos por operación, mientras que una persona teclea alrededor de diez caracteres por segundo y un documento colaborativo típico tiene menos de cien participantes simultáneos—. La tercera: el tamaño guardado incluso disminuye cuando se borra texto, a pesar de las lápidas, porque el colapso en tramos también agrupa los borrados consecutivos.

Hay una columna que en un contexto local-first merece más atención de la que suele recibir, y es el tiempo de carga. Trece milisegundos frente a dos mil setecientos cuarenta y seis es una diferencia de dos órdenes de magnitud, y no se manifiesta como una cifra en una tabla sino como la sensación de que la aplicación arranca o no arranca. En una arquitectura donde la copia local es la fuente de verdad, cada apertura del documento es una reconstrucción del estado a partir de lo guardado, de modo que esa métrica se paga en cada sesión y en cada pestaña. Es exactamente el problema del arranque en frío, y conviene evaluarla con al menos tanto cuidado como el tamaño en disco, que es lo que casi todo el mundo compara primero.

La última tabla estira la prueba hasta un extremo deliberadamente absurdo: la misma traza repetida cien veces, un documento final de diez millones y medio de caracteres, varias veces más largo que Guerra y paz. El resultado no es que el algoritmo brille, sino algo más útil: sigue siendo tolerable. Diecisiete megabytes guardados, menos de un segundo y medio para guardar, poco más de medio segundo para cargar y doscientos veintitrés megabytes de memoria. Ningún editor colaborativo real trabaja con documentos así, y ese es justamente el sentido de la medición: establecer que el techo está muy por encima de cualquier caso de uso plausible, de modo que las decisiones de producto puedan tomarse sin pensar en él.

Lo que costaba antes y por qué

La pregunta que queda es por qué esto era difícil en las estructuras anteriores, y la respuesta separa nítidamente dos maneras de identificar la posición de un elemento en una lista replicada.

Hay un matiz que conviene precisar para no exagerar el argumento. RGA sí admite agrupación en tramos —de hecho la variante segmentada de RGA es una de las inspiraciones declaradas de la implementación de Fugue— y Yjs también. La diferencia no es que Fugue inventara la compresión, sino que consigue la no intercalación maximal sin renunciar a ella. Ese es el equilibrio que no se había alcanzado antes: los algoritmos que comprimían bien intercalaban, y el algoritmo que en 2019 intentó no intercalar ni siquiera convergía. Fugue ocupa por primera vez las dos casillas a la vez.

Queda por señalar el precio concreto de la maximalidad, porque el artículo no lo esconde. FugueMax necesita anotar en cada hijo derecho su origen derecho, y eso se nota: en las implementaciones directas, el documento guardado de FugueMax ocupa 1.237 kB frente a los 1.021 kB de Fugue, y su rendimiento en vivo es algo peor. Por eso la implementación optimizada que se publicó y que adoptó la biblioteca Collabs en su versión 0.6.1 es la de Fugue, no la de FugueMax: Fugue se queda solo ligeramente por debajo de la propiedad y las ejecuciones en que ambos difieren son raras. Es una elección de ingeniería perfectamente defendible precisamente porque la distancia entre ambos está caracterizada y demostrada, no estimada.