Componer: un CRDT cuyos valores son CRDT sigue siendo un CRDT

Los tres niveles anteriores dejaron sobre la mesa un catálogo de piezas: contadores que suman contribuciones por réplica, conjuntos que reconcilian altas y bajas con etiquetas, registros que eligen un valor o conservan todos los concurrentes. Cada una resuelve un problema pequeño y cada una viene con su demostración de convergencia. La pregunta que abre este nivel es la que convierte ese catálogo en algo utilizable: qué ocurre cuando se meten unas dentro de otras. La respuesta es un teorema breve y de consecuencias enormes, porque dice que la propiedad se hereda. Una estructura cuyos valores son estructuras convergentes es a su vez convergente, y lo es sin que haya que demostrar nada nuevo sobre el compuesto. Ese resultado es lo que separa una colección de recetas de un lenguaje para modelar documentos, y también lo que explica por qué todas las librerías reales del ecosistema tienen la misma forma general pese a haber nacido en sitios que no se hablaban.

La clausura es un teorema, no una analogía

Conviene recuperar la definición exacta antes de componer nada. Una estructura convergente basada en estado es un semirretículo superior: un conjunto de valores con un orden parcial y una operación de unión que devuelve, para cualesquiera dos valores, la menor cota superior de ambos. Esa operación es conmutativa, asociativa e idempotente, y las actualizaciones locales son inflacionarias, es decir, nunca producen un estado que esté por debajo del anterior en el orden. Las tres propiedades de la unión son lo que hace irrelevante el orden de llegada de los mensajes; el carácter inflacionario de las actualizaciones es lo que impide retroceder. Juntas dan convergencia fuerte: réplicas que han visto el mismo conjunto de actualizaciones tienen el mismo estado, sin coordinación.

El teorema de composición dice lo siguiente. Si se toman dos semirretículos y se forma el producto cartesiano de sus valores, ordenado componente a componente, la estructura resultante es también un semirretículo, y su unión es exactamente la unión de cada componente por separado. La demostración no tiene misterio y merece hacerse una vez: la conmutatividad del par se sigue de la conmutatividad de cada componente, y lo mismo la asociatividad y la idempotencia, porque cada propiedad se verifica coordenada a coordenada sin que las coordenadas se hablen entre sí. Que la menor cota superior del producto sea el par de menores cotas superiores se deduce de que el orden del producto se definió componente a componente.

// Producto de dos estructuras convergentes: la union es puntual
function unirProducto(unirA, unirB) {
  return (x, y) => [unirA(x[0], y[0]), unirB(x[1], y[1])];
}

// Y se generaliza a un registro con campos fijos sin cambiar nada
function unirRegistro(politicas) {
  return (x, y) => {
    const salida = {};
    for (const campo of Object.keys(politicas)) {
      salida[campo] = politicas[campo](x[campo], y[campo]);
    }
    return salida;
  };
}

Lo importante de esa demostración es su forma, no su contenido: es un argumento por inducción estructural disfrazado. Si el producto de dos semirretículos es un semirretículo, entonces el producto de un semirretículo con un producto de semirretículos también lo es, y así hasta cualquier profundidad de anidamiento. No hay un límite en el número de niveles ni una degradación de la garantía a medida que se baja. Un documento con siete niveles de anidamiento converge por la misma razón por la que converge un contador suelto, y esa razón se comprueba una sola vez.

Vale la pena señalar qué papel juega cada una de las tres propiedades, porque en la práctica cada una compra una cosa distinta y confundirlas lleva a diagnósticos erróneos cuando algo falla. La conmutatividad compra la indiferencia al orden de llegada, que es lo que permite usar un transporte que no ordena. La asociatividad compra la libertad de agrupar, que es lo que permite fusionar por lotes, en cascada o en topologías arbitrarias sin que el resultado dependa de la forma del árbol de sincronización. Y la idempotencia compra la tolerancia al reenvío, que es lo que hace seguro reintentar un mensaje sin saber si el anterior llegó. En un sistema real la tercera es la que más se usa y la que menos se menciona, porque las reconexiones son constantes y ningún protocolo honesto puede garantizar entrega exactamente una vez.

Las tres formas de anidar

La composición aparece en la práctica bajo tres formas, y cada una tiene un requisito propio. La primera es el producto de campos fijos: un registro con un conjunto conocido de claves, cada una con su propia estructura. Es la forma más simple y la que se acaba de demostrar. No necesita nada más que las políticas de cada campo, y su coste en metadatos es la suma de los costes individuales.

La segunda es el índice dinámico, es decir, un mapa cuyo conjunto de claves no se conoce de antemano y cambia con el uso. Formalmente es un producto con un número indeterminado de coordenadas, y aquí aparece un requisito nuevo: para que la unión sea puntual hay que decidir qué valor tiene una clave que una réplica no ha visto. La respuesta canónica es el elemento mínimo del semirretículo del valor, el que está por debajo de todos los demás, de modo que unir con él no aporta nada. Si el tipo del valor tiene ese mínimo, el mapa se comporta como un producto infinito representado de forma dispersa y todo funciona. Si no lo tiene, hay que fabricarlo, y esa fabricación es el origen del problema que ocupa la lección siguiente.

Conviene ver por qué la representación dispersa es correcta y no un atajo, porque la intuición inicial suele ser que se está ocultando información. Un producto sobre el conjunto de todas las claves posibles es un objeto infinito, pero casi todas sus coordenadas valen el mínimo, y unir con el mínimo devuelve el otro operando sin alterarlo. Guardar solo las coordenadas que no valen el mínimo es entonces una compresión exacta: la unión dispersa —copiar las claves presentes en un solo lado y fusionar las presentes en ambos— produce el mismo resultado que la unión del producto completo, coordenada a coordenada. Cuando el tipo del valor carece de mínimo, esa equivalencia se rompe, y con ella la corrección del atajo.

La tercera es la secuencia de estructuras, donde el orden lo mantiene una lista convergente con identificadores estables y cada posición aloja a su vez una estructura. Su mecanismo interno es lo bastante difícil como para ocupar el nivel siguiente entero, y aquí basta con tratarla como una caja negra que cumple una promesa: da a cada elemento una identidad que no depende de su sitio y sabe intercalar inserciones concurrentes de forma determinista. Con esa promesa, la composición es de dos piezas independientes: la secuencia gestiona identidad y orden, y cada elemento gestiona su propio contenido. Que ambas responsabilidades estén separadas es lo que permite mover un elemento sin tocar su interior y editar su interior sin tocar el orden.

Las tres formas no son intercambiables y la elección entre ellas tiene consecuencias que duran lo que dure el esquema. Un producto de campos fijos es el más barato en metadatos y el más rígido: añadir un campo nuevo exige que todas las versiones del código sepan qué hacer con él. Un índice dinámico es el más flexible y el que más residuo acumula, porque cada clave que alguna vez existió deja rastro. Una secuencia es la única que sabe expresar orden, y esa capacidad se paga con identificadores de posición que suelen ser el metadato más pesado de todo el documento. Elegir la forma equivocada rara vez impide que algo funcione; lo que hace es fijar un coste que después no se puede renegociar sin migrar.

Conviene además notar que las tres se pueden imitar unas a otras, y que casi siempre es mala idea. Un mapa cuyas claves sean números consecutivos parece una lista y no lo es: no sabe intercalar inserciones concurrentes y produce colisiones en cuanto dos réplicas añaden a la vez. Una lista de pares clave y valor parece un mapa y tampoco lo es: no sabe reconocer que dos entradas hablan de la misma clave y acaba con duplicados que nadie sabe fusionar. Cada forma existe porque resuelve un problema concreto de identidad, y sustituir una por otra traslada ese problema al código de aplicación, donde no hay ninguna demostración que lo respalde.

flowchart TD
DOC[documento raiz como mapa] --> T[titulo registro de ultimo escritor]
DOC --> E[etiquetas conjunto con prioridad al alta]
DOC --> V[vistas contador de contribuciones]
DOC --> C[cuerpo secuencia convergente]
DOC --> M[metadatos mapa anidado]
M --> M1[autor registro]
M --> M2[revisiones contador]
C --> P1[parrafo con formato como mapa]
style DOC fill:#cba6f7,color:#11111b
style M fill:#89b4fa,color:#11111b
style C fill:#a6e3a1,color:#11111b

El diagrama es engañosamente inocente y conviene leerlo dos veces. Cada nodo interno es una estructura convergente completa, con sus metadatos, su política de fusión y su comportamiento ante la concurrencia; cada hoja también. Lo que el árbol representa no es un esquema de datos en el sentido habitual, sino un árbol de políticas de fusión, y la elección de cada nodo es una decisión de producto tomada en tiempo de diseño, que es justamente el instante en que sale más barata.

El mismo resultado del lado de las operaciones

Las librerías reales rara vez son puramente basadas en estado, así que conviene tener la versión operacional del teorema. Ahí una estructura convergente se define de otro modo: hay un conjunto de operaciones, una entrega fiable que respeta el orden causal y la exigencia de que dos operaciones concurrentes cualesquiera conmuten, esto es, que aplicarlas en un orden o en el otro produzca el mismo estado.

La composición se apoya en una observación casi tonta y muy útil. Una operación sobre un documento compuesto es una operación sobre un subobjeto concreto más la ruta que lleva hasta él. Dos operaciones dirigidas a subobjetos distintos conmutan de forma trivial, porque tocan partes disjuntas del estado y ninguna puede alterar el efecto de la otra. Dos operaciones dirigidas al mismo subobjeto conmutan si y solo si conmutan en la estructura de ese subobjeto, que es precisamente lo que su demostración individual ya garantizaba. No queda ningún caso por cubrir.

// Una operacion compuesta es ruta mas operacion local
const op = { ruta: ["metadatos", "revisiones"], tipo: "incrementar", delta: 1 };

function aplicar(nodo, ruta, opLocal) {
  if (ruta.length === 0) return nodo.tipo.aplicar(nodo, opLocal);
  const [clave, ...resto] = ruta;
  const hijo = nodo.hijos[clave];
  return { ...nodo, hijos: { ...nodo.hijos, [clave]: aplicar(hijo, resto, opLocal) } };
}

Hay una condición escondida en ese razonamiento que las implementaciones descuidadas incumplen. Para que la ruta identifique al mismo subobjeto en todas las réplicas, la ruta no puede ser una secuencia de nombres legibles: tiene que apuntar a identidades estables, porque un nombre puede haber sido reasignado y una posición puede haber cambiado por inserciones concurrentes. Es la misma razón por la que las secuencias convergentes no usan índices numéricos. Si la ruta se resuelve por nombre en el momento de aplicar, dos réplicas pueden acabar aplicando la misma operación a subobjetos distintos, y entonces la conmutación deja de estar garantizada por una razón que no aparece en ninguna demostración: se rompió la hipótesis de que ambas hablaban del mismo objeto.

Hay una segunda condición escondida que afecta al transporte y que la composición hereda sin avisar. La demostración operacional supone entrega causal, es decir, que ninguna operación se aplica antes que otra de la que depende. En una estructura suelta esa exigencia es fácil de razonar porque todas las operaciones se refieren al mismo objeto. En un compuesto aparece una dependencia nueva y menos evidente: la operación que crea un subobjeto precede causalmente a todas las que se dirigen a él. Si el transporte permite que una escritura llegue antes que la creación de su destino, el receptor tiene una operación dirigida a una identidad que no conoce y debe encolarla, no descartarla. Descartarla es la forma más silenciosa que existe de perder datos en este tipo de sistemas, y es un fallo que solo se manifiesta bajo latencias asimétricas o reordenamientos poco frecuentes.

Lo que la clausura no te regala

Merece la pena ser muy explícito sobre el alcance del teorema, porque su formulación optimista invita a leerlo como una garantía general y no lo es. La clausura promete convergencia: todas las réplicas llegarán al mismo estado. No promete que ese estado sea válido según las reglas de tu dominio, y no lo promete precisamente porque la unión se definió componente a componente. Si dos campos del mismo registro están ligados por una invariante, la fusión los reconcilia por separado y puede producir una combinación que ninguna réplica escribió y que ninguna habría escrito. Es el conflicto semántico que ya apareció al bajar la granularidad, y componer no lo cura: lo hereda y lo multiplica por la profundidad del árbol.

Tampoco regala la existencia del elemento mínimo. Un registro de último escritor no tiene un valor natural por debajo de todos los demás, y un contador de suma pura tampoco lo tiene si su dominio son los enteros con signo. Cuando el tipo del valor carece de mínimo, la representación de una clave ausente deja de ser neutra y pasa a ser una decisión con consecuencias observables.

Y no regala la gestión del residuo. Cada pieza compuesta arrastra sus propios metadatos —etiquetas, lápidas, vectores, identificadores de posición— y el compuesto arrastra la suma de todos ellos, más el suyo propio. Un árbol de mil nodos con estructuras convergentes en las hojas puede tener un peso de metadatos que domine al contenido por un orden de magnitud, y la compactación tiene que descender por el árbol respetando la política de cada nivel.

Y no regala, por último, nada relativo al rendimiento de lectura. La unión componente a componente es lineal en el número de componentes, de modo que fusionar un documento entero cuesta un recorrido completo del árbol aunque el cambio afecte a una sola hoja. En un editor con decenas de cambios por segundo esa linealidad es la diferencia entre una aplicación fluida y una inservible, y la salida —fusionar solo el subárbol alcanzado por las operaciones entrantes y propagar hacia arriba únicamente lo necesario— no se deduce del teorema: hay que construirla, y hay que construirla sin romper la equivalencia con la fusión completa, que es lo que las pruebas de propiedades deben vigilar.