Monotonía: por qué borrar es más difícil que añadir

Hay una consecuencia de las dos lecciones anteriores que casi nadie ve venir y que decide la forma de todas las estructuras que construiremos después. Si la mezcla devuelve siempre una cota superior de sus dos argumentos, entonces la mezcla no olvida nada, jamás. Y si no olvida nada, un estado que retroceda en el orden no puede sobrevivir: en cuanto sincronice con una réplica que aún tenga el estado anterior, la mezcla devolverá el anterior, porque es el mayor de los dos. El retroceso no es que esté prohibido por convención: es que resulta invisible, lo revierte la propia definición de la mezcla. De ahí sale la asimetría fundamental de todo este campo, la que hace que añadir sea gratis y borrar sea un problema de ingeniería con presupuesto propio, y de ahí salen las lápidas, que son el modo de escribir un borrado sin retroceder.

El estado solo puede subir

La condición se enuncia en una línea. Toda actualización local debe ser inflacionaria: aplicada a un estado x, produce un estado y con x <= y. Dicho en castellano llano, una escritura puede añadir información al estado de su réplica, o dejarlo igual, pero nunca puede dejarlo con menos información de la que tenía.

La razón por la que esto no es una recomendación sino una obligación estructural cabe en un párrafo. Supón que una réplica retrocede: pasa de x a un z con z <= x y z distinto de x. Antes o después sincroniza con otra réplica que todavía conserva x, y la mezcla calcula la cota superior mínima de z y de x, que es x, porque x ya era cota superior de ambos. El retroceso desaparece. No hay error, no hay excepción, no hay aviso: el sistema hace exactamente lo que se le pidió, que era no perder información, y lo que la réplica intentaba era perderla. Una escritura que retrocede no es una escritura arriesgada; es una escritura que no ocurre.

Conviene ver el mismo hecho desde la otra cara, porque así se entiende por qué el diseño es tan rígido. La convergencia se sostiene sobre que el estado de una réplica sea siempre el supremo de todo lo que ha visto. Si una actualización local pudiera bajar por debajo de ese supremo, el estado dejaría de ser función del conjunto entregado y pasaría a depender del momento exacto en que ocurrió el retroceso respecto de las sincronizaciones, que es precisamente la dependencia del orden que estamos eliminando. La monotonía no es un requisito adicional: es lo que hace que las tres propiedades de la lección anterior sirvan de algo.

Conviene separar dos palabras que se confunden constantemente porque suenan igual y significan cosas distintas. Una función es monótona cuando respeta el orden: si x <= y, entonces su imagen de x es menor o igual que su imagen de y. Una actualización es inflacionaria cuando el resultado contiene a la entrada: x <= f(x). Lo que se exige a las actualizaciones locales es lo segundo, que es lo que impide el retroceso; lo que la mezcla cumple por ser cota superior mínima es lo primero, y es lo que garantiza que mezclar información nueva nunca empeore la posición de nadie. Los dos requisitos se necesitan y no se implican mutuamente, así que en una revisión de código hay que buscarlos por separado.

En la familia basada en operaciones el mismo principio se presenta con otra ropa. Allí no hay estados que viajen, pero el efecto de una operación tampoco puede deshacer el de otra ya aplicada, porque las operaciones concurrentes deben conmutar y una revocación no conmuta con aquello que revoca. Deshacer, en los dos mundos, exige registrarlo como un hecho nuevo en lugar de ejecutarlo como una marcha atrás.

La resurrección: por qué borrar rompe lo que añadir no rompe

Bajemos al caso concreto que sufre todo el mundo la primera vez. Modela un conjunto compartido con la unión como mezcla, que es el semirretículo más natural del mundo. Añadir un elemento es inflacionario y por tanto correcto: el conjunto crece, la mezcla lo respeta, y dos réplicas que añaden elementos distintos convergen a los dos elementos sin discutir. Ahora borra.

Quitar un elemento hace el conjunto más pequeño, es decir, baja en el orden. La réplica que borra queda por debajo de donde estaba, y en cuanto sincroniza con cualquier réplica que todavía tenga el elemento, la unión lo devuelve. El elemento reaparece. Este es el fenómeno que la literatura llama resurrección, y el punto pedagógico importante es que no es un fallo: la mezcla ha calculado correctamente la cota superior mínima de dos conjuntos, uno de los cuales contenía el elemento. Es el teorema funcionando bien sobre un modelo mal planteado.

flowchart LR
A[replica A tenia x y lo borra] --> M[sincronizacion]
B[replica B nunca supo del borrado y tiene x] --> M
M --> R[la union devuelve x otra vez]
R --> N[no es un fallo es la cota superior minima]
style R fill:#f38ba8,color:#11111b
style N fill:#f9e2af,color:#11111b

// El borrado ingenuo se deshace solo en la primera mezcla
const join = (a, b) => new Set([...a, ...b]);

let A = new Set(["tarea1", "tarea2"]);
let B = new Set(["tarea1", "tarea2"]);

A.delete("tarea2");        // A retrocede en el orden: ahora sabe menos
const tras = join(A, B);   // Set { "tarea1", "tarea2" }
// El borrado no ha sobrevivido, y el codigo de mezcla es impecable

La asimetría que esto revela es la idea central de la lección y conviene decirla sin adornos: en un semirretículo, la información positiva se propaga sola y la información negativa no existe. Que un elemento esté presente es un hecho que una réplica puede afirmar y que la mezcla conserva. Que un elemento esté ausente no es un hecho: es la ausencia de un hecho, y una ausencia no se distingue de un desconocimiento. Cuando la réplica B mira su conjunto y ve tarea2, no tiene manera de saber si A la borró o si A sencillamente todavía no la había visto. Las dos situaciones tienen exactamente la misma huella en los datos, y por eso la mezcla las trata igual.

Quien haya estudiado algo de lógica reconocerá aquí una vieja distinción con otro traje. Una base de datos centralizada puede permitirse la hipótesis de mundo cerrado: lo que no está registrado se considera falso, porque hay un único registro y es completo por definición. Un sistema replicado sin árbitro vive necesariamente en mundo abierto: lo que no está en mi copia puede ser falso o puede ser simplemente algo que aún no me han contado, y no tengo forma de distinguirlo desde dentro. Todas las dificultades del borrado se siguen de ahí, y también la solución, que consiste en dejar de razonar por ausencia y empezar a registrar explícitamente lo negativo.

Las lápidas: escribir el borrado como una adición

De la observación anterior sale la solución, y es la única posible: si la ausencia no se puede representar, hay que convertir el borrado en presencia de algo. Se registra un hecho nuevo y positivo —«este elemento fue borrado»— que se propaga como cualquier otro y que la mezcla conserva como cualquier otro. Ese registro se llama lápida.

La estructura mínima que lo implementa lleva dos conjuntos: el de elementos añadidos y el de elementos borrados. La mezcla es la unión componente a componente, que es un semirretículo por la construcción de producto que vimos en la segunda lección, así que las tres propiedades se heredan y no hay nada nuevo que demostrar. El valor que ve el usuario ya no es el estado: es una vista derivada, calculada al leer restando el segundo conjunto del primero.

// Dos conjuntos que solo crecen, y una vista derivada al leer
const vacio = () => ({ anadidos: new Set(), borrados: new Set() });

const anadir = (s, x) => ({ ...s, anadidos: new Set([...s.anadidos, x]) });
const borrar = (s, x) => ({ ...s, borrados: new Set([...s.borrados, x]) });

const join = (a, b) => ({
  anadidos: new Set([...a.anadidos, ...b.anadidos]),
  borrados: new Set([...a.borrados, ...b.borrados]),
});

const ver = (s) => new Set([...s.anadidos].filter((x) => !s.borrados.has(x)));
// El estado interno solo sube. Lo que mengua es la vista, que no es el estado.

Esa última línea del comentario contiene la distinción más sutil de la lección y merece un párrafo propio. La monotonía es una condición sobre el estado interno, no sobre lo que el usuario percibe. El usuario ve desaparecer una tarea de la lista y con toda razón dice que se ha borrado; internamente no ha desaparecido nada, se ha añadido una constancia. El sistema crece hacia arriba mientras la interfaz muestra una lista que encoge, y no hay contradicción entre ambas cosas porque hablan de objetos distintos. Todo el arte de diseñar estas estructuras consiste en encontrar la pareja adecuada de estado monótono y función de lectura.

// La vista mengua mientras el estado interno crece: no hay contradiccion
let s = vacio();
s = anadir(s, "tarea1");
s = anadir(s, "tarea2");
ver(s).size;                       // 2 elementos visibles

s = borrar(s, "tarea2");
ver(s).size;                       // 1 elemento visible
s.anadidos.size + s.borrados.size; // 3 hechos almacenados: el estado ha subido

// Y ahora lo importante: mezclar con una replica que no vio el borrado
join(s, { anadidos: new Set(["tarea1", "tarea2"]), borrados: new Set() });
// La vista sigue teniendo 1 elemento: la lapida ha sobrevivido a la mezcla

Que ese cálculo ocurra al leer tiene un coste que conviene anticipar. Si la vista se recalcula entera en cada lectura, una lista con muchos borrados paga en cada repintado; la salida habitual es materializar la vista y actualizarla de forma incremental cuando llega una mezcla, que es exactamente el problema de mantenimiento incremental que tratamos al hablar de reactividad sobre la base de datos local. La estructura convergente y la vista materializada son dos objetos distintos con ciclos de vida distintos, y confundirlos es una fuente inagotable de fallos sutiles.

Esta variante concreta, la de los dos conjuntos, tiene una limitación conocida que conviene enunciar para no llevarse una sorpresa: un elemento borrado no se puede volver a añadir, porque su lápida sigue ahí para siempre y la vista lo seguirá restando. Levantar esa limitación exige dar identidad propia a cada adición —una etiqueta única por cada vez que alguien añade— y hacer que el borrado se lleve por delante solo las etiquetas que quien borró había visto. Así una adición concurrente con un borrado sobrevive, porque su etiqueta no estaba entre las observadas, y la estructura pasa a tener una semántica explícita en la que añadir gana. Esa construcción es el asunto de los niveles siguientes; aquí basta con retener de dónde sale la necesidad.

La factura: una lápida no se tira sin saber que todos la han visto

Queda el problema que ninguna de estas estructuras esconde y que en producción determina si el diseño aguanta: las lápidas ocupan sitio. Un conjunto del que se ha borrado un millón de elementos guarda un millón de constancias, y esa memoria viaja en cada sincronización completa y se guarda en cada dispositivo, incluido el móvil viejo del usuario.

Antes de elegir política conviene medir, y medir aquí es más fácil de lo que parece. Instrumenta el tamaño serializado del estado y el número de lápidas por documento, y contrasta ambas cifras con el número de elementos visibles: la relación entre las dos es el indicador que de verdad importa, porque un documento con cien elementos y cuarenta mil lápidas está anunciando un problema que aparecerá en los dispositivos más lentos mucho antes que en tu portátil. Conviene además probar el arranque en frío con ese estado inflado, que es el escenario en el que la factura se cobra entera y de golpe.

Fíjate en lo que ocurre con la primera de las cuatro, porque es honesto reconocerlo: recoger lápidas de forma segura reintroduce una forma de acuerdo entre réplicas. Es un acuerdo mucho más benigno que el que evitamos al principio, porque no está en el camino crítico de ninguna escritura —nadie espera a nadie para escribir, ni para leer, ni para sincronizar— y su único efecto es retrasar la liberación de memoria hasta que la información esté disponible. Pero es acuerdo, y por eso ningún sistema real de este tipo puede prometer a la vez metadatos acotados y tolerancia a réplicas que desaparecen durante un tiempo ilimitado. Hay que elegir, y la elección se documenta, no se esconde.