Con version vectors: la diferencia se calcula con una resta

La primera lección dejó planteado el problema y su suelo teórico; esta desarrolla la respuesta más simple que existe y que, precisamente por simple, es la que usan casi todas las bibliotecas de edición colaborativa que se despliegan hoy. La idea cabe en una frase: si cada operación se identifica por el par formado por quién la hizo y en qué número de secuencia suya, y cada réplica recuerda hasta qué número ha recibido de cada uno de los demás, entonces intercambiar esos resúmenes basta para que ambos lados calculen exactamente lo que le falta al otro, sin ambigüedad, sin probabilidad de error y en una sola ida y vuelta. No hay descenso, no hay filtros, no hay estimaciones: hay una resta. La pregunta interesante no es por qué funciona, que es evidente, sino qué obligaciones contrae quien lo adopta, porque esa resta solo da la respuesta correcta mientras se cumplan dos condiciones silenciosas que el código no comprueba y que el tiempo erosiona: que el historial detrás del vector siga intacto y que el número de participantes no crezca sin control. Esta lección desarrolla el mecanismo, mide su coste real y delimita con precisión los dos escenarios donde deja de servir.

La resta que responde a la pregunta

El punto de partida es la identificación de operaciones que el nivel de relojes lógicos ya estableció. Cada operación nace en una réplica concreta y recibe un número de secuencia local que se incrementa de uno en uno y jamás se reutiliza. El par formado por el identificador de la réplica y ese número es el nombre global de la operación, único sin coordinación alguna. Un vector de versiones es entonces la tabla que asocia a cada réplica conocida el mayor número de secuencia suyo que se ha recibido de forma contigua desde el uno.

Con esa estructura, la reconciliación se vuelve aritmética. Una réplica envía su vector, que ocupa unas decenas de bytes; la otra lo compara con el suyo entrada a entrada y, para cada actor donde su contador sea mayor, sabe que le debe todas las operaciones de ese actor en el intervalo comprendido entre ambos números. Ni siquiera hace falta que ninguno de los dos tenga la lista de identificadores: los intervalos describen conjuntos densos y se transmiten con dos números.

// Lo que le falta al remoto es todo lo que hay por encima de su contador
function faltantesParaElRemoto(vvLocal, vvRemoto) {
  const rangos = [];
  for (const actor of Object.keys(vvLocal)) {
    const desde = vvRemoto[actor] ?? 0;
    const hasta = vvLocal[actor];
    if (hasta > desde) rangos.push({ actor, desde, hasta });
  }
  return rangos;
}

// El intercambio completo cabe en una ida y vuelta
async function sincronizar(remoto) {
  const suyo = await remoto.pedirVector();
  await remoto.recibir(leerRangos(faltantesParaElRemoto(vectorLocal(), suyo)));
  await recibir(await remoto.pedirRangos(faltantesParaElRemoto(suyo, vectorLocal())));
}

Este es exactamente el protocolo que implementan las bibliotecas de edición colaborativa más extendidas: se codifica el vector de estado, se envía, y el otro extremo responde con una actualización que contiene solo lo que falta y que se puede aplicar sin más contexto. La eficiencia es notable porque el coste del mensaje inicial no depende del tamaño del documento ni del número de operaciones acumuladas, sino solamente de cuántos actores distintos han escrito en él alguna vez. Y el resultado es exacto: no hay falsos positivos que reparar ni segundas pasadas que programar.

flowchart LR
A[replica A envia su vector] --> B[replica B resta entrada a entrada]
B --> C[B envia los rangos que faltan a A]
B --> D[B pide los rangos que le faltan a el]
C --> E[convergencia en una ida y vuelta]
D --> E
style A fill:#89b4fa,color:#11111b
style E fill:#a6e3a1,color:#11111b

Lo que hay que conservar para que la resta valga

La primera condición silenciosa es la contigüidad. Un contador que dice cuarenta significa que se han recibido las operaciones de la uno a la cuarenta sin huecos, y toda la aritmética depende de eso. Si el transporte entrega desordenado y la implementación aplica lo que le llega según llega, aparecerán huecos y el contador se quedará atascado en el número anterior al primer hueco, de modo que en la siguiente sincronización se pedirán de nuevo operaciones ya recibidas. La solución clásica es no aplicar nada hasta que sus dependencias estén completas y mantener aparte una lista de excepciones para lo que llegó adelantado.

Esa lista de excepciones, que en la literatura aparece con nombres como nube de puntos o vector con intervalos, es el primer sitio donde el mecanismo empieza a pagar. Mientras el transporte sea razonable, la lista está casi siempre vacía y el coste es nulo. En un transporte con pérdidas, reordenaciones y reconexiones frecuentes, la lista crece y el resumen deja de ser un vector compacto para convertirse en un conjunto de intervalos cuyo tamaño depende de lo maltratada que venga la red. Conviene medirlo en condiciones reales antes de dar por bueno el tamaño del mensaje de saludo.

La segunda condición silenciosa es más grave porque no se manifiesta en el tamaño de nada, sino en la corrección. La resta devuelve intervalos, y alguien tiene que ser capaz de leer las operaciones de esos intervalos y transmitirlas. Es decir: el vector es un índice sobre un historial, y solo funciona mientras ese historial exista. Todo lo que el nivel de compactación estableció sobre podar el registro de operaciones choca de frente con esta obligación, porque podar por debajo del contador del participante más rezagado deja al vector apuntando a operaciones que ya nadie guarda.

Cuando el vector crece: réplicas, clientes y poda

El coste en metadatos es lineal en el número de actores distintos que han escrito alguna vez, y esa frase esconde una trampa. En un sistema con una decena de servidores el vector ocupa unos cientos de bytes y no se nota. En un sistema donde cada dispositivo de cada usuario es un actor, y donde a veces cada pestaña del navegador o cada reinstalación genera un identificador nuevo, el número de actores no está acotado por la arquitectura sino por el uso, y crece de forma monótona porque una entrada del vector no se puede quitar sin más.

Tamano del vector con identificador de 16 bytes y contador de 4

  16 actores ......... unos 320 bytes    irrelevante
  1 000 actores ...... unos 20 KB        mayor que muchos documentos
  50 000 actores ..... cerca de 1 MB     el saludo cuesta mas que el estado

  y si el vector es por clave y no por documento, multiplicar por el numero de claves

La última línea del cuadro es la que hunde los almacenes de clave y valor que versionan cada entrada por separado. Ahí el coste no es un vector sino un vector por clave, y con clientes que escriben directamente el número de entradas por vector crece hasta que los metadatos superan a los datos. La respuesta madura de esa familia de sistemas fue dejar de usar el identificador del cliente como actor y usar el del servidor que atiende la escritura, guardando aparte el punto concreto que la identifica; el vector vuelve a estar acotado por el número de servidores, que sí es una magnitud de arquitectura.

Queda entonces la tentación de podar el vector, quitando entradas de actores que llevan mucho tiempo inactivos. Es correcto solo bajo una condición que hay que poder demostrar: que todas las réplicas del sistema han visto ya todas las operaciones de ese actor, lo que la literatura llama estabilidad causal, y demostrarlo requiere saber quiénes son todas las réplicas y tener noticias recientes de cada una. En una topología abierta, donde cualquiera puede aparecer con una copia antigua, esa demostración no existe, y podar sin ella significa que la reaparición de una réplica antigua producirá reenvíos que ya no se pueden distinguir de operaciones nuevas.

Dónde encaja de verdad y por dónde se escapa

El territorio natural del mecanismo es fácil de describir: población de actores acotada y conocida, sincronización frecuente, historial que se conserva íntegro o que se poda con un horizonte generoso, y elementos identificados por pares densos y contiguos. Bajo esas condiciones no hay nada mejor, y cualquier alternativa de este nivel resultaría más cara y más complicada sin aportar exactitud adicional. Es el caso de un documento colaborativo con unos pocos participantes, y por eso es lo que hacen las bibliotecas del track.

Fuera de ese territorio el mecanismo no se rompe de golpe sino que se degrada por dos flancos distintos. Por el flanco de la población, cuando los actores se cuentan por miles y el saludo empieza a pesar más que el contenido, lo que obliga a cambiar quién es actor o a resumir el vector de otra manera. Por el flanco del tiempo, cuando la retención del historial no puede seguir el ritmo de los dispositivos que vuelven tarde, lo que obliga a tener otro mecanismo para reconciliar contra una instantánea en lugar de contra un registro.

Los dos flancos apuntan a lo mismo y anticipan la lección siguiente. Cuando el vector deja de servir, lo que hace falta es un mecanismo que no dependa ni de recordar nada sobre el interlocutor ni de conservar la historia, sino solo del estado actual de ambos lados. El árbol de hashes es exactamente eso, y por eso los sistemas serios llevan los dos: la resta para el noventa y nueve por ciento de las sincronizaciones y la comparación estructural para el uno por ciento en que la resta no se puede calcular o no se puede servir.