El diseño antes del código: qué guarda, qué identifica y qué arrastra la baja

Escribir un conjunto que converge es sorprendentemente fácil si las tres decisiones de diseño se toman antes y sorprendentemente imposible si se toman sobre la marcha. La tentación es abrir el editor y empezar por la clase, porque la estructura parece obvia —un conjunto de cosas presentes y otro de cosas retiradas— y porque el código que sale de esa intuición compila, pasa las pruebas secuenciales y funciona durante meses hasta el día en que dos personas tocan el mismo elemento sin conexión. Esta lección no escribe todavía la implementación: la diseña. Fijaremos qué guarda el estado y por qué no puede guardar menos, qué información lleva dentro cada etiqueta y por qué esa forma concreta y no otra, y sobre todo por qué la operación de borrado no puede ser una función del elemento sino que tiene que arrastrar consigo el conjunto exacto de etiquetas que quien borraba tenía delante. Las tres decisiones se justifican aquí ejecutando las alternativas equivocadas y mirando cómo fallan.

Las dos estructuras ingenuas, y cómo fallan

El primer diseño que se le ocurre a cualquiera guarda dos conjuntos de valores: los añadidos y los retirados, y considera presente lo que está en el primero y no en el segundo. Es una estructura legítima, tiene nombre propio en la literatura y converge perfectamente. El problema no es que converja mal, es a qué converge. Comprobémoslo con el caso más banal que existe: alguien añade algo, se arrepiente y lo quita; otra persona, sin haber visto nada, añade lo mismo.

function crearIngenuo() { return { vivos: new Set(), muertos: new Set() }; }
function anadirIngenuo(s, e) { s.vivos.add(e); }
function quitarIngenuo(s, e) { s.muertos.add(e); }
function contieneIngenuo(s, e) { return s.vivos.has(e) && !s.muertos.has(e); }
function mezclarIngenuo(a, b) {
  return {
    vivos: new Set([...a.vivos, ...b.vivos]),
    muertos: new Set([...a.muertos, ...b.muertos]),
  };
}

const A = crearIngenuo();
const B = crearIngenuo();

anadirIngenuo(A, "leche");   // A anade
quitarIngenuo(A, "leche");   // A se arrepiente y quita
anadirIngenuo(B, "leche");   // B, sin haber visto nada, anade lo mismo

const fin = mezclarIngenuo(A, B);
console.log("A contiene leche:", contieneIngenuo(A, "leche"));
console.log("B contiene leche:", contieneIngenuo(B, "leche"));
console.log("tras mezclar   :", contieneIngenuo(fin, "leche"));
console.log("muertos        :", [...fin.muertos]);

A contiene leche: false
B contiene leche: true
tras mezclar   : false
muertos        : [ 'leche' ]

Ahí está el fallo, y conviene mirarlo despacio antes de arreglarlo. La marca de muerte se puso sobre la cadena leche, y esa cadena es la misma que escribió B. El arrepentimiento de A, que era una decisión sobre su alta, se convirtió al mezclar en una sentencia sobre cualquier alta con ese valor, incluidas las que no existían cuando se tomó. El trabajo de B desapareció sin error, sin aviso y sin rastro.

El segundo diseño ingenuo intenta arreglarlo poniendo etiquetas, pero coloca la etiqueta en el sitio equivocado: la deriva del elemento, de modo que el mismo valor produce siempre la misma etiqueta. Es cómodo porque no necesita estado ni contador, y es exactamente igual de defectuoso.

function etiquetaDeterminista(e) { return "tag-" + e; }
const altas = new Set(), bajas = new Set();
altas.add(etiquetaDeterminista("leche"));
bajas.add(etiquetaDeterminista("leche"));
altas.add(etiquetaDeterminista("leche"));   // volver a anadir: misma etiqueta, ya muerta
console.log("etiqueta por elemento -> vive leche:",
  [...altas].some((t) => !bajas.has(t)));

etiqueta por elemento -> vive leche: false

Volver a añadir dejó de funcionar. Una etiqueta derivada del valor no identifica un acto, identifica una cosa, y las cosas no tienen historia: la segunda alta es indistinguible de la primera y hereda su muerte. La conclusión que ordena todo el nivel se deduce de estos dos experimentos y merece enunciarse sin adornos: la unidad de identidad no puede ser el elemento, tiene que ser la adición.

Qué lleva dentro cada etiqueta

Decidido que se etiqueta el acto, queda elegir la forma de la etiqueta, y la elección no es cosmética porque determina qué se podrá hacer después. Hay tres candidatos razonables y cada uno regala unas propiedades y cobra otras.

Elegiremos el par formado por identificador de réplica y contador local, escrito como una cadena con dos puntos en medio para que las trazas sean legibles. La decisión se justifica por la única propiedad que la alternativa aleatoria no tiene: es comprimible. Un conjunto de etiquetas emitidas por la misma réplica con contadores seguidos se describe con un solo número, y esa propiedad es la que permitirá, tres lecciones más adelante, que el estado deje de crecer con el número de operaciones. Empezar por el par cuando parece innecesario evita reescribirlo todo cuando deja de serlo.

El contador exige a cambio una disciplina que conviene fijar ahora porque es la fuente de un fallo desagradable y difícil de diagnosticar. El contador es monótono, lo incrementa únicamente su propia réplica, y tiene que persistirse junto al estado. Una réplica que reinicia y vuelve a empezar en cero reemite etiquetas que ya usó, y esas etiquetas pueden estar retiradas en otra parte de la red: el resultado es un elemento nuevo que nace muerto, en un dispositivo distinto y semanas después. El identificador de réplica, por su lado, se genera una vez por instalación y no se comparte jamás entre dispositivos.

Por qué la baja tiene que arrastrar lo observado

Queda la tercera decisión, que es la que de verdad separa una estructura que converge bien de una que converge a lo que nadie quería. La pregunta es qué recibe la operación de borrado. La respuesta ingenua es el elemento. La respuesta correcta es el elemento más el conjunto de etiquetas vivas que esta réplica tenía delante en el instante de borrar, que es lo que la literatura llama eliminación observada. La diferencia se ve mejor comparando una baja que barre todas las etiquetas conocidas con una que barre solo las observadas.

const { ORSet } = require("./orset.js");

// La baja no lleva contexto y mata tambien lo que no llego a ver
const A = new ORSet("A"), B = new ORSet("B");
A.add("leche");                      // A:1
const tB = B.add("leche");           // B:1, concurrente
const bajaSinContexto = new ORSet("A");
bajaSinContexto.bajas.add("A:1"); bajaSinContexto.bajas.add(tB);
const fin = ORSet.merge(ORSet.merge(A, B), bajaSinContexto);
console.log("baja sin contexto     -> vive leche:", fin.has("leche"));

// La baja lleva solo lo observado: la correcta
const C = new ORSet("A"), D = new ORSet("B");
C.add("leche"); D.add("leche");
C.remove("leche");                   // solo mata A:1
console.log("baja observada        -> vive leche:", ORSet.merge(C, D).has("leche"),
  "vivas:", ORSet.merge(C, D).vivas("leche"));

baja sin contexto     -> vive leche: false
baja observada        -> vive leche: true vivas: [ 'B:1' ]

flowchart TD
P[que recibe la operacion de borrado] --> V[el valor del elemento]
P --> O[el valor mas las etiquetas observadas]
V --> V1[la marca alcanza altas que aun no existian]
V1 --> V2[se pierde trabajo concurrente sin aviso]
O --> O1[la marca alcanza solo lo que se vio]
O1 --> O2[el alta concurrente sobrevive por su etiqueta nueva]
style V2 fill:#f38ba8,color:#11111b
style O2 fill:#a6e3a1,color:#11111b

Lo interesante es que la eliminación observada no necesita ninguna maquinaria adicional para lograr eso. No consulta relojes, no compara vectores, no pregunta a nadie. Se limita a leer el estado local en el momento de ejecutarse y a convertir esa lectura en el alcance de la operación, con lo que la información causal que necesita ya estaba delante y era gratis. Una baja concurrente con un alta no la alcanza por la razón más simple imaginable: no puede haber visto una etiqueta que todavía no existía.

El contrato que queda fijado

Antes de implementar conviene escribir lo que la estructura promete, porque será lo que las pruebas de la tercera lección comprueben y porque un contrato escrito antes es una especificación mientras que uno escrito después es una descripción. Son cinco cláusulas y ninguna sobra.

La primera es de estado: la estructura guarda un mapa de elemento a conjunto de etiquetas que lo añadieron, más un conjunto plano de etiquetas retiradas, más los dos datos locales que no forman parte del estado compartido —identificador de réplica y contador—. La segunda es de lectura: un elemento está presente si y solo si alguna de sus etiquetas no figura entre las retiradas. La tercera es de alta: añadir emite una etiqueta nueva que no ha existido nunca y no consulta nada más. La cuarta es de baja: retirar marca exactamente las etiquetas vivas observadas en ese instante y ninguna otra. La quinta es de mezcla: la unión se hace componente a componente, uniendo los conjuntos internos del mapa y nunca reemplazándolos.