Convertirlo en delta: enviar solo lo que cambió y medir cuánto se ahorra

La clase de las lecciones anteriores es correcta y converge, y tiene un defecto que la vuelve inservible en cuanto sale del cuaderno: para sincronizar dos réplicas hay que enviar el estado entero. Añadir un elemento a una lista de quinientos significa transmitir los quinientos, con todas sus etiquetas y todas sus lápidas, para que el receptor descubra por su cuenta que solo uno era nuevo. La corrección es conocida, se llama difusión por deltas y tiene una elegancia que conviene apreciar antes de implementarla: el delta no es un formato nuevo, ni un registro de operaciones, ni un diff; es un estado del mismo tipo que contiene solo lo que cambió, y se aplica con la misma función de mezcla, que ya es conmutativa, asociativa e idempotente. No hay que demostrar nada nuevo, no hay que escribir un aplicador aparte y no hay que exigir orden de entrega. Lo que sí hay que asumir es una condición de fiabilidad que el estado completo no exigía, y esa asimetría es lo último que aprenderemos midiéndola.

El delta es un estado, no un formato nuevo

La idea que hace corta esta lección es que las operaciones de la estructura ya producen fragmentos de estado válidos. Un alta genera una etiqueta y esa etiqueta, colocada bajo su elemento en un mapa vacío, es un estado perfectamente legítimo que solo contiene esa alta. Una baja genera un puñado de etiquetas retiradas y ese puñado, en un conjunto de bajas por lo demás vacío, es también un estado legítimo. Mezclar cualquiera de los dos con el estado del receptor produce exactamente el efecto de la operación, ni más ni menos, porque la mezcla es una unión y unir con un fragmento es añadir ese fragmento. De ahí se sigue que no hace falta ningún mecanismo nuevo de aplicación, ningún número de secuencia y ninguna garantía de orden. Un delta entregado dos veces no hace daño porque la mezcla es idempotente; dos deltas entregados al revés dan el mismo resultado porque es conmutativa; un delta que llega ya combinado con otro por un intermediario da el mismo resultado que si llegara suelto porque es asociativa. Las tres propiedades que se comprobaron en la tercera lección para el estado completo valen sin cambios para los deltas, y esa herencia es todo lo que hace falta.

const d1 = new ORSet("X"); d1.altas.set("a", new Set(["A:1"]));
const d2 = new ORSet("X"); d2.altas.set("b", new Set(["A:2"]));
const d3 = new ORSet("X"); d3.bajas.add("A:1");
const ordenes = [[d1,d2,d3],[d3,d2,d1],[d2,d3,d1],[d3,d1,d2]];
const huellas = new Set(ordenes.map(
  (o) => serializar(o.reduce((s, d) => ORSet.merge(s, d), new ORSet("B")))
));
console.log("ordenes de deltas:", ordenes.length, "estados distintos:", huellas.size);
console.log("estado:", [...huellas][0]);

ordenes de deltas: 4 estados distintos: 1
estado: {"altas":{"a":["A:1"],"b":["A:2"]},"bajas":["A:1"]}

Fíjate en el tercer orden probado: la baja de A:1 se aplicó antes que el alta que la produjo, y el resultado no cambia. Eso parece imposible desde una intuición de registro de operaciones, donde retirar algo que no existe es un error o un no-op que se pierde, y es trivial aquí porque el conjunto de bajas no es una instrucción sino un hecho almacenado: la etiqueta está muerta desde que se sabe, exista ya el alta correspondiente o llegue mañana.

La subclase que acumula

La implementación no modifica ni un método de la clase original. Añade un campo con un estado pendiente, hace que las dos operaciones registren su efecto también ahí, y expone dos métodos nuevos: uno que entrega lo acumulado y vacía el buzón, otro que aplica un delta recibido. Que add y remove devolvieran la etiqueta emitida y la lista de retiradas, decisión que en la segunda lección parecía cosmética, es lo que permite escribir esto sin duplicar lógica.

class ORSetDelta extends ORSet {
  constructor(replica) { super(replica); this.pendiente = new ORSet(replica); }
  add(elemento) {
    const t = super.add(elemento);
    if (!this.pendiente.altas.has(elemento)) this.pendiente.altas.set(elemento, new Set());
    this.pendiente.altas.get(elemento).add(t);
    return t;
  }
  remove(elemento) {
    const muertas = super.remove(elemento);
    for (const t of muertas) this.pendiente.bajas.add(t);
    return muertas;
  }
  // Entrega lo acumulado y vuelve a empezar
  drenar() { const d = this.pendiente; this.pendiente = new ORSet(this.replica); return d; }
  aplicar(delta) {
    const f = ORSet.merge(this, delta);
    this.altas = f.altas; this.bajas = f.bajas;
    return this;
  }
}

La medida sobre un caso real

Para que la medición signifique algo hace falta un estado con historia: no una lista recién creada sino una que lleve tiempo en uso, con altas de varias réplicas sobre los mismos elementos y con un número apreciable de retiradas acumuladas. Quinientos elementos, cada uno con el alta de una réplica y uno de cada tres con altas independientes de otras dos, más ciento veinte etiquetas retiradas.

function poblar(replica, elementos, retiradas) {
  const s = new ORSetDelta(replica);
  for (let i = 0; i < elementos; i++) {
    const e = "articulo-" + String(i).padStart(4, "0");
    const etiquetas = new Set(["R0:" + (i + 1)]);   // todos llevan el alta de R0
    if (i % 3 === 0) etiquetas.add("R1:" + (i + 1)).add("R2:" + (i + 1));  // altas independientes
    s.altas.set(e, etiquetas);
  }
  for (let i = 0; i < retiradas; i++) s.bajas.add("R0:" + (i + 1));
  s.drenar();
  return s;
}

const A = poblar("A", 500, 120);
console.log("elementos:", A.altas.size, "vivos:", A.values().length, "bajas:", A.bajas.size);
const completo = serializar(A);
console.log("estado completo:", completo.length, "bytes");

A.add("articulo-nuevo-1");
A.add("articulo-nuevo-2");
A.remove("articulo-0042");
const d = A.drenar();
console.log("delta de 3 operaciones:", serializar(d).length, "bytes");
console.log("delta:", serializar(d));
console.log("razon completo/delta:", (completo.length / serializar(d).length).toFixed(1), "a 1");

elementos: 500 vivos: 420 bajas: 120
estado completo: 17319 bytes
delta de 3 operaciones: 91 bytes
delta: {"altas":{"articulo-nuevo-1":["A:1"],"articulo-nuevo-2":["A:2"]},"bajas":["R1:43","R2:43"]}
razon completo/delta: 190.3 a 1

Diecisiete mil bytes frente a noventa y uno, una razón de 190 a 1 para tres operaciones. Y el contenido del delta merece una lectura porque enseña algo que el número esconde: la retirada de articulo-0042 no aparece como una instrucción de borrar ese elemento, aparece como las dos etiquetas que estaban vivas, R1:43 y R2:43. La tercera etiqueta del elemento, R0:43, no está porque ya figuraba entre las bajas y la eliminación observada solo marca lo vivo. El delta es literalmente el efecto, y por eso ninguna réplica que lo reciba necesita saber qué elemento se pretendía retirar ni en qué estado estaba.

flowchart LR
OP[operacion local] --> EST[estado completo]
OP --> PEN[buzon pendiente] --> DR[drenar] --> RED[envio por la red]
RED --> AP[aplicar en la otra replica] --> EST2[estado remoto]
style RED fill:#a6e3a1,color:#11111b
style PEN fill:#89b4fa,color:#11111b

La diferencia acumulada importa más que la puntual, porque es la que se paga cada mes. Cincuenta sincronizaciones de una operación cada una, comparando lo que costaría enviar el estado completo cada vez con lo que cuesta enviar los deltas.

let full = 0, dlt = 0;
const perdido = [];
const B = poblar("B", 500, 120);
B.aplicar(d);
for (let ronda = 0; ronda < 50; ronda++) {
  A.add("extra-" + ronda);
  const dd = A.drenar();
  dlt += serializar(dd).length;
  full += serializar(A).length;
  if (ronda === 17) { perdido.push(dd); continue; }   // este delta se pierde
  B.aplicar(dd);
}
console.log("50 rondas -> estado completo:", full, "bytes | deltas:", dlt, "bytes");
console.log("ahorro:", (100 - (dlt / full) * 100).toFixed(2), "por ciento");
console.log("con un delta perdido convergen:", serializar(A) === serializar(B));
B.aplicar(perdido[0]);                                 // retransmision del que falto
console.log("tras retransmitir convergen:", serializar(A) === serializar(B));

50 rondas -> estado completo: 894166 bytes | deltas: 2083 bytes
ahorro: 99.77 por ciento
con un delta perdido convergen: false
tras retransmitir convergen: true

Casi novecientos mil bytes frente a dos mil ochenta y tres. Y lo importante no es el porcentaje sino la forma de las dos curvas: el coste del estado completo crece con el tamaño del conjunto y se paga entero en cada sincronización, de modo que el gasto por operación empeora a medida que el documento madura; el coste del delta depende solo de cuántas operaciones se hicieron desde la última entrega y es indiferente a lo grande que sea el conjunto. Un producto que sincroniza por estado completo se vuelve más caro cuanto más lo usa la gente, que es exactamente la propiedad contraria a la deseable.

La condición que los deltas sí exigen

Todo lo anterior tiene una contrapartida que hay que enunciar con honestidad, porque es la única diferencia real entre las dos formas de sincronizar y suele descubrirse tarde. Enviar el estado completo es autorreparador: si un envío se pierde, el siguiente contiene todo lo del anterior y el sistema se recupera solo. Los deltas no tienen esa propiedad, porque cada uno contiene información que no está en ningún otro. Basta perder uno, y por eso el bucle anterior descartaba a propósito el delta de la ronda diecisiete: las dos últimas líneas de su salida son la prueba, con un delta perdido convergen: false y, solo después de retransmitirlo, tras retransmitir convergen: true.

Las dos réplicas quedaron divergentes de forma permanente, sin ningún error visible y sin ninguna forma de darse cuenta por sí solas. La divergencia no se cura sola ni con más sincronizaciones, porque los deltas siguientes no contienen lo perdido; solo se cura retransmitiendo el que faltaba, cosa que solo puede hacer alguien que sepa que faltaba. De ahí que un sistema de deltas necesite siempre dos piezas que un sistema de estado completo no necesita: un acuse por parte del receptor de hasta dónde ha recibido, y un camino de reparación cuando ese acuse revela un hueco.