OR-Set: etiquetar la adición, no el elemento

El diagnóstico de la lección anterior era preciso y su corrección resulta casi decepcionante por lo pequeña: dejar de tratar el valor de un elemento como su identidad. Cada adición recibe un identificador propio, irrepetible y generado localmente sin preguntar a nadie, y una retirada deja de referirse al elemento para referirse a las adiciones concretas que quien retiraba tenía delante en ese momento. Ese cambio de una sola línea en el modelo de datos arregla todo lo que estaba roto: volver a añadir funciona, dos réplicas que añaden lo mismo a la vez siguen viendo un solo elemento, y una retirada concurrente con una adición ya no la alcanza. La estructura resultante se llama conjunto de observaciones y eliminaciones, y es la que hay debajo de los conjuntos de Automerge, de Yjs, de Riak y de prácticamente cualquier sistema que se tome esto en serio. No porque converja mejor —el conjunto de dos fases también converge— sino porque converge a lo que la gente esperaba.

Etiquetar el acto, no la cosa

El estado guarda, por cada elemento, el conjunto de etiquetas con las que ha sido añadido alguna vez, y aparte un conjunto de etiquetas retiradas. Un elemento está presente si le queda al menos una etiqueta viva. Añadir genera una etiqueta nueva; retirar toma las etiquetas vivas que esta réplica conoce en este instante y las marca. Las dos partes siguen siendo conjuntos de solo crecimiento, así que la convergencia se hereda del producto igual que en la lección anterior.

function crear(replica) {
  return { replica, reloj: 0, altas: new Map(), muertas: new Set() };
}

function nuevaEtiqueta(s) {
  s.reloj += 1;
  return s.replica + ":" + s.reloj;
}

function vivas(s, e) {
  const todas = s.altas.get(e);
  return todas ? [...todas].filter((t) => !s.muertas.has(t)) : [];
}

function anadir(s, e) {
  if (!s.altas.has(e)) s.altas.set(e, new Set());
  const t = nuevaEtiqueta(s);
  s.altas.get(e).add(t);
  return t;
}

function retirar(s, e) {
  for (const t of vivas(s, e)) s.muertas.add(t);   // solo lo observado
}

function contiene(s, e) {
  return vivas(s, e).length > 0;
}

La mezcla es de nuevo componente a componente, con la única sutileza de que el primer componente es un mapa de conjuntos y hay que unir los conjuntos internos en lugar de sustituirlos. Es el error de implementación más frecuente de toda esta familia de estructuras, y produce pérdidas silenciosas que solo se manifiestan bajo concurrencia real.

function mezclar(a, b) {
  const altas = new Map();
  for (const [e, etiquetas] of [...a.altas, ...b.altas]) {
    altas.set(e, new Set([...(altas.get(e) ?? []), ...etiquetas]));   // unir, nunca reemplazar
  }
  return {
    replica: a.replica,
    reloj: Math.max(a.reloj, b.reloj),
    altas,
    muertas: new Set([...a.muertas, ...b.muertas]),
  };
}

Con esto, volver a añadir deja de ser un problema y deja de serlo por una razón estructural, no por un caso especial en el código: la etiqueta que genera la nueva alta no ha existido nunca antes, de modo que no puede figurar en ningún conjunto de retiradas, presente o futuro. Una baja solo puede matar lo que vio, y no puede haber visto algo que aún no existía.

const s = crear("A");
anadir(s, "urgente");        // etiqueta A:1
retirar(s, "urgente");       // mata A:1
contiene(s, "urgente");      // false

anadir(s, "urgente");        // etiqueta A:2, nunca observada por nadie
contiene(s, "urgente");      // true: el usuario recupera su etiqueta

Gana la adición, y no por casualidad

El caso interesante no es el secuencial sino el concurrente, y es donde la estructura toma partido. Supón que una réplica retira un elemento mientras otra, sin haber visto esa retirada, lo añade de nuevo. La baja mata las etiquetas que observó; la etiqueta de la nueva alta no estaba entre ellas; al mezclar, el elemento sigue teniendo una etiqueta viva y por tanto permanece. La política se llama gana la adición, y no es un efecto colateral: es una consecuencia directa de haber definido la retirada sobre lo observado en lugar de sobre el valor.

flowchart TD
A1[A anade cafe con etiqueta A uno] --> S[B recibe la etiqueta A uno]
A2[A anade cafe otra vez con etiqueta A dos] --> M[mezcla final]
S --> B1[B retira cafe y mata solo A uno]
B1 --> M
M --> R[cafe sigue vivo por la etiqueta A dos]
style B1 fill:#f9e2af,color:#11111b
style R fill:#a6e3a1,color:#11111b

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

anadir(A, "cafe");             // A:1
B = mezclar(B, A);             // B ya conoce A:1
anadir(A, "cafe");             // A:2, concurrente con lo que hara B
retirar(B, "cafe");            // B mata A:1, la unica que vio

const final = mezclar(B, A);
contiene(final, "cafe");       // true: A:2 sobrevivio
vivas(final, "cafe");          // ["A:2"]

Que esta sea la política correcta no es evidente a priori, y conviene sostenerlo con argumentos en lugar de con costumbre. El primero es de asimetría de daños, el mismo criterio que el nivel 23 aplicaba a la comunicación: un elemento que permanece cuando alguien esperaba que desapareciera produce una molestia visible y reparable en un segundo, mientras que un elemento que desaparece cuando alguien acababa de crearlo produce una pérdida de trabajo que a veces ni se detecta. Entre dos errores posibles se elige sistemáticamente el que el usuario puede corregir.

El segundo es de intencionalidad, y es más fino. Quien añade está aportando información que no existía; quien retira actúa sobre información que ya conocía. Si ambas acciones son concurrentes, la retirada se tomó sobre un mundo que ya no era el actual, y respetar la adición equivale a decir que una decisión tomada con información incompleta no debe anular una aportación que nunca llegó a considerar. El tercero es de reparabilidad, y es el que zanja la discusión en la práctica: si el elemento permanece y no era eso lo que se quería, la persona vuelve a retirarlo y esta vez la retirada sí verá todas las etiquetas; si desaparece y tampoco era eso, tiene que recordar qué había, reconstruirlo y reescribirlo, suponiendo que se dé cuenta. Una política reparable en un gesto es preferible a una irreparable aunque acierte más a menudo.

El coste, y la variante que lo acota

Nada de esto es gratis y conviene mirar la factura antes de celebrar. El conjunto guarda ahora una etiqueta por cada adición que haya ocurrido jamás, más una entrada por cada etiqueta retirada: un elemento que se añade y se quita mil veces deja mil etiquetas y mil retiradas, aunque el valor visible sea un único dato o ninguno. El almacenamiento pasa a depender del número de operaciones y no del tamaño de los datos, y ese cambio de régimen sorprende a casi todo el mundo la primera vez que mide un documento real. Existe una optimización clásica que reduce de forma drástica la parte peor, y descansa en una observación sencilla: un conjunto de etiquetas generadas por la misma réplica con contadores consecutivos se describe con un solo número. Si cada réplica lleva un vector de versiones con el contador máximo que ha visto de cada una, una etiqueta está muerta cuando el vector la cubre y sin embargo no aparece entre las vivas, de modo que las retiradas dejan de almacenarse una a una y pasan a deducirse.

// Variante resumida: en lugar de guardar las muertas, se deducen del vector
function cubierta(vector, etiqueta) {
  const [replica, n] = etiqueta.split(":");
  return (vector[replica] ?? 0) >= Number(n);
}

function estaMuerta(estado, e, etiqueta) {
  const vivasDelElemento = estado.altas.get(e) ?? new Set();
  return cubierta(estado.vector, etiqueta) && !vivasDelElemento.has(etiqueta);
}

const estado = { vector: { A: 5, B: 2 }, altas: new Map([["cafe", new Set(["A:4"])]]) };
estaMuerta(estado, "cafe", "A:2");   // true: cubierta y ausente
estaMuerta(estado, "cafe", "A:4");   // false: sigue viva
estaMuerta(estado, "cafe", "A:9");   // false: aun no la hemos visto

El cambio de escala es considerable: el registro de lo eliminado pasa de crecer con el número de retiradas a crecer con el número de réplicas, que es un orden de magnitud distinto y además está bajo control. Pero fíjate en lo que no ha ocurrido. El vector sigue sin poder desaparecer, sigue creciendo con cada dispositivo que escriba alguna vez, y sigue siendo imprescindible para no resucitar. Se ha cambiado la forma de la lápida y se ha comprimido muchísimo; no se ha eliminado. Esa distinción es el asunto entero de la lección que cierra el nivel.

Dónde gana la adición y no debería

Cerrar la lección declarando que la política es la correcta sería repetir el error que el nivel 23 dedicó cinco lecciones a desmontar. Gana la adición es el valor por defecto acertado, y como todo valor por defecto acertado, existen dominios en los que es exactamente lo contrario de lo que hace falta, y conviene reconocerlos porque suelen ser los de mayor consecuencia.

La buena noticia es que invertir la política no exige otra estructura ni otra demostración: se cambia únicamente la función de lectura, que pasa a considerar muerto un elemento si tiene alguna etiqueta retirada aunque le queden vivas. El almacén no se toca, la convergencia no se toca, y las etiquetas siguen sirviendo para lo que servían. Es la confirmación práctica de lo que la primera lección adelantó: el almacén está resuelto y ya no volverá a discutirse; lo único que se discute a partir de aquí es qué función lo lee y cuánto cuesta guardar lo que esa función necesita.