2P-Set: correcto, convergente e inservible

La lección anterior estableció el requisito con precisión: borrar exige evidencia positiva, esa evidencia debe añadirse sin destruir nada, y la lectura debe poder relacionarla con lo que niega. La estructura que satisface los tres de la forma más directa imaginable se llama conjunto de dos fases, y consiste en llevar dos conjuntos de solo crecimiento en paralelo, uno con todo lo que se ha añadido alguna vez y otro con todo lo que se ha retirado. Converge, y lo hace sin ningún argumento nuevo: hereda la demostración de la primera lección sin modificarla. Y sin embargo, salvo en un puñado de dominios muy concretos, no se debe usar. El motivo no es un fallo de corrección ni un coste inasumible, sino algo bastante más interesante desde el punto de vista de la ingeniería: hace algo perfectamente definido, perfectamente predecible y perfectamente contrario a lo que cualquier persona espera de un conjunto. Esta lección lo construye entero y luego explica con exactitud dónde muere.

Dos conjuntos que solo crecen, y su producto

El estado es un par. El primer componente registra las altas, el segundo las bajas, y ninguno de los dos retira nunca nada. Añadir inserta en el primero, retirar inserta en el segundo, y la lectura devuelve lo que está en el primero y no en el segundo. La mezcla no necesita saber nada de la semántica: aplica la unión a cada componente por separado.

function crear() {
  return { altas: new Set(), bajas: new Set() };
}

function anadir(s, e) {
  s.altas.add(e);
  return s;
}

function retirar(s, e) {
  s.bajas.add(e);
  return s;
}

function contiene(s, e) {
  return s.altas.has(e) && !s.bajas.has(e);
}

function valor(s) {
  return new Set([...s.altas].filter((e) => !s.bajas.has(e)));
}

function mezclar(a, b) {
  return {
    altas: new Set([...a.altas, ...b.altas]),
    bajas: new Set([...a.bajas, ...b.bajas]),
  };
}

La corrección no requiere demostración nueva, y merece la pena ver por qué, porque el argumento se reutilizará muchas veces en los niveles siguientes. El producto cartesiano de dos semirretículos, con la mezcla aplicada componente a componente, es un semirretículo: la idempotencia, la conmutatividad y la asociatividad se verifican en cada coordenada por separado y por tanto se verifican en el par. Cualquier estructura que se pueda descomponer en piezas convergentes independientes es convergente sin trabajo adicional, y eso convierte la composición en la herramienta principal de diseño de esta disciplina.

Hay un detalle que suele confundir en la primera lectura y que conviene despejar: no hace falta exigir que todo lo que está en bajas esté también en altas. Una baja puede llegar antes que el alta a la que se refiere, y eso ocurre de verdad en cuanto la red entrega desordenado o dos réplicas se sincronizan por caminos distintos. La lectura lo maneja sin ninguna excepción: si la baja llega primero, el elemento simplemente nunca llega a verse cuando el alta aparezca. Prohibir ese caso obligaría a esperar y a coordinar, que es exactamente lo que estamos evitando.

flowchart LR
A[conjunto de altas: solo crece] --> V[funcion de lectura]
B[conjunto de bajas: solo crece] --> V
V --> D[visible si esta en altas y no esta en bajas]
D --> F[entrar en bajas es un viaje sin retorno]
style B fill:#f9e2af,color:#11111b
style F fill:#f38ba8,color:#11111b

El almacén sube aunque el valor baje

Aquí aparece la distinción que la primera lección anunció y que ahora se puede palpar. El estado —el par de conjuntos— crece de forma monótona sin excepción, y por eso la mezcla es un supremo y la convergencia está garantizada. El valor visible, en cambio, puede encoger, porque la función de lectura resta. Que el valor no sea monótono no compromete nada: la convergencia es una propiedad del estado, no de su proyección. Dos réplicas con el mismo par calculan el mismo valor, y eso es todo lo que se pedía.

const A = crear();
const B = crear();

anadir(A, "informe");
let sincronizado = mezclar(B, A);      // B ya conoce el alta
retirar(sincronizado, "informe");      // B lo retira

const final = mezclar(A, sincronizado);
contiene(final, "informe");            // false: la baja viaja y persiste
mezclar(final, A).altas.size;          // 1: el almacen nunca encoge

Compáralo con el intento ingenuo de la lección anterior y verás qué ha cambiado exactamente. Allí el borrado hacía descender el estado y la mezcla lo deshacía; aquí el borrado hace ascender el estado por el otro componente, y la mezcla lo propaga en lugar de anularlo. La misma operación de usuario, expresada como afirmación en vez de como omisión, pasa de imposible a trivial. Ese es todo el truco, y es el que las estructuras restantes van a refinar sin abandonarlo nunca.

La condena: lo que entra en bajas no vuelve

Y llegamos al punto donde la estructura se rompe como herramienta de propósito general. Como el conjunto de bajas solo crece y la lectura resta incondicionalmente, un elemento que ha sido retirado alguna vez está muerto en todos los futuros posibles del sistema. Volver a añadirlo no hace nada: la alta se inserta obedientemente, no cambia el resultado, y no hay error, ni aviso, ni forma de detectarlo desde fuera.

const s = crear();

anadir(s, "urgente");
contiene(s, "urgente");    // true
retirar(s, "urgente");
contiene(s, "urgente");    // false

anadir(s, "urgente");      // el usuario vuelve a crear la etiqueta
contiene(s, "urgente");    // false: la baja es absorbente
s.altas.has("urgente");    // true: el alta esta ahi, pero no se vera jamas

Las dos últimas líneas describen el peor modo de fallo que puede tener una interfaz. La operación se ejecuta, el estado la registra, no se produce ninguna condición de error que un desarrollador pueda observar, y el efecto es nulo. Si la aplicación aplica el cambio de forma optimista —y en local-first lo aplica siempre, porque esa es la promesa— el usuario ve la etiqueta aparecer y desaparecer sin explicación un momento después, cuando llegue la primera mezcla. Es indistinguible de un producto averiado, y no hay ningún mensaje que se pueda mostrar que no sea vergonzoso.

El atajo que se intenta a continuación es previsible: si el problema es que el valor está condenado, cambia el valor. Añade un sufijo, un contador o una marca al nombre para que la etiqueta urgente recreada no sea la misma cadena que la anterior. Funciona, en el sentido más pobre de la palabra, y rompe todo lo demás: el conjunto deja de deduplicar, dos réplicas que crean la misma etiqueta a la vez producen dos elementos visibles distintos, la igualdad de valores deja de significar igualdad de cosas y la comparación se vuelve responsabilidad de cada punto de lectura. Es una solución que traslada el problema desde la estructura de datos hasta cada consulta que la use.

El diagnóstico: la identidad estaba en el sitio equivocado

Ese atajo fallido, sin embargo, apunta hacia la solución correcta, y verlo con claridad es el objetivo real de la lección. El conjunto de dos fases se equivoca en una única decisión, tomada tan al principio que ni siquiera parece una decisión: usar el valor del elemento como su identidad. Bajo esa premisa, todas las adiciones de la etiqueta urgente son el mismo suceso, indistinguible y único, y por tanto una sola baja las alcanza a todas, incluidas las que todavía no han ocurrido. La estructura no tiene forma de expresar que la baja se refería a la primera alta y no a la segunda, porque para ella la primera y la segunda son la misma cosa.

// La baja no apunta a un hecho, apunta a un valor: alcanza a todo el futuro
const bajas = new Set(["urgente"]);

const alta1 = { elemento: "urgente", cuando: "lunes" };
const alta2 = { elemento: "urgente", cuando: "viernes" };

bajas.has(alta1.elemento);   // true
bajas.has(alta2.elemento);   // true: la del viernes muere por algo del lunes

La corrección consiste en separar las dos nociones que estaban colapsadas: el elemento, que es lo que el usuario ve y compara, y la adición, que es un suceso concreto ocurrido en una réplica concreta y que merece un identificador propio. Con esa separación, una baja deja de referirse a un valor para referirse a un conjunto de adiciones concretas, y todo lo que la estructura hacía mal se corrige de golpe: volver a añadir crea un suceso nuevo al que ninguna baja anterior apunta, y dos adiciones concurrentes del mismo valor siguen siendo un solo elemento visible porque el valor sigue siendo el criterio de igualdad para la lectura. Esa es la estructura de la lección siguiente, y en cuanto se ve el diagnóstico deja de parecer un invento y pasa a parecer inevitable.