Vector clocks: un contador por réplica

El reloj de Lamport te dio un orden total y una implicación en un solo sentido: si un evento causó a otro, su marca es estrictamente menor. La recíproca no vale, y esa asimetría es precisamente la que arruina la detección de conflictos, porque dos escrituras genuinamente independientes reciben marcas comparables y el sistema las trata como si una precediera a la otra. El vector clock ataca el problema por la vía estructural: en lugar de un número, cada evento carga un mapa con un contador por réplica. Lo que se compra con esa dimensión adicional no es una implicación mejor, es una equivalencia, y de ahí sale la única forma exacta de responder a la pregunta que todo motor de sincronización necesita responder alguna vez: estos dos cambios, ¿uno viene del otro, o se produjeron sin saber nada el uno del otro?

Del escalar al vector

Un reloj de Lamport comprime toda la historia causal de un evento en un entero, y toda compresión tan agresiva pierde información. Del hecho de que L(a) sea menor que L(b) no se deduce absolutamente nada sobre la relación entre ambos, porque el contador de una réplica también avanza por eventos que no guardan ninguna relación con a. La pérdida tiene nombre técnico —el reloj satisface la condición débil del reloj pero no la fuerte— y una consecuencia práctica devastadora: un sistema que ordene escrituras por marca de Lamport no puede distinguir entre una escritura que conocía a la anterior y otra que la ignoraba por completo. Ambas le llegan como una pareja ordenada, y las trata igual.

El vector clock hace exactamente lo contrario de comprimir: conserva una coordenada por réplica. Si el sistema tiene n réplicas, el sello de un evento es un punto en un espacio de n dimensiones, y ese punto codifica, coordenada a coordenada, cuántos eventos de cada réplica pertenecen al pasado causal del evento sellado. No es una aproximación ni un resumen heurístico: es un inventario contable exacto del cono de luz pasado de ese evento. Todo lo demás de esta lección se deduce de ahí.

Las reglas de mantenimiento son tres y no admiten variantes. Cada réplica incrementa su propia coordenada —solo la suya, nunca otra— cuando produce un evento local. Al enviar un mensaje adjunta una copia completa de su vector. Al recibir uno toma el máximo puntual entre su vector y el que llega, y después incrementa su propia coordenada, porque la recepción también es un evento de esa réplica.

// Cada replica mantiene un mapa disperso: id de replica -> contador
function crearReloj(idPropio) {
  return { idPropio, v: Object.create(null) };
}

function eventoLocal(reloj) {
  const v = reloj.v;
  v[reloj.idPropio] = (v[reloj.idPropio] ?? 0) + 1; // solo la coordenada propia
  return { ...v }; // el sello inmutable que viaja con el evento
}

function alRecibir(reloj, selloRemoto) {
  const v = reloj.v;
  for (const id of Object.keys(selloRemoto)) {
    v[id] = Math.max(v[id] ?? 0, selloRemoto[id]); // maximo puntual, coordenada a coordenada
  }
  v[reloj.idPropio] = (v[reloj.idPropio] ?? 0) + 1; // recibir tambien es un evento local
  return { ...v };
}

La interpretación coordenada a coordenada merece decirse despacio porque es lo que después permite leer un sello de un vistazo. Si el sello de un evento tiene un cinco en la coordenada de la réplica r, significa que las cinco primeras operaciones de r están en su pasado causal y la sexta no. Ni más ni menos: no dice cuándo ocurrieron, no dice por qué camino llegó la información y no dice si r sigue viva. Dice qué sabía el autor del evento en el instante de producirlo, que es justo el dato que la causalidad necesita.

Dos detalles de implementación que parecen menores y no lo son. El primero: el vector es un mapa disperso y la ausencia de una clave significa cero, nunca desconocido. Almacenar los ceros explícitos multiplica el tamaño sin añadir información. El segundo: la identidad de réplica tiene que ser estable a lo largo de toda la vida de esa réplica. Un cliente que genera un identificador nuevo en cada arranque no es un cliente con un reloj: es una réplica nueva en cada arranque, y su vector crece sin límite mientras el sistema pierde la capacidad de reconocer que ya vio sus escrituras anteriores.

sequenceDiagram
participant A as Replica A
participant B as Replica B
participant C as Replica C
Note over A: evento a1 sellado 1-0-0
A->>B: mensaje con sello 1-0-0
Note over B: recibe y sella b1 como 1-1-0
Note over C: evento c1 sellado 0-0-1 sin saber de A
B->>C: mensaje con sello 1-1-0
Note over C: recibe y sella c2 como 1-1-2
Note over A,C: a1 precede a c2 pero a1 y c1 son concurrentes

La regla de comparación

Con los vectores en la mano la relación de orden es el orden producto, y conviene enunciarla con cuidado porque casi todos los errores de esta materia nacen de enunciarla mal. Un vector V domina a W cuando para todo índice i se cumple V[i] >= W[i]. La dominación es estricta si además difieren en al menos una coordenada, y esa dominación estricta es la que escribimos W < V. Y aquí está la parte que no tiene análogo en un escalar: puede ocurrir perfectamente que ni V domine a W ni W domine a V, porque cada uno gana en coordenadas distintas. A ese caso lo llamamos concurrencia, y no es un empate ni un fallo de resolución: es una tercera respuesta legítima.

const IGUAL = "igual", ANTES = "antes", DESPUES = "despues", CONCURRENTE = "concurrente";

function comparar(a, b) {
  let menorEnAlguna = false;
  let mayorEnAlguna = false;

  for (const id of new Set([...Object.keys(a), ...Object.keys(b)])) {
    const x = a[id] ?? 0; // ausente significa cero, no desconocido
    const y = b[id] ?? 0;
    if (x < y) menorEnAlguna = true;
    if (x > y) mayorEnAlguna = true;
    if (menorEnAlguna && mayorEnAlguna) return CONCURRENTE; // salida temprana
  }

  if (menorEnAlguna) return ANTES;
  if (mayorEnAlguna) return DESPUES;
  return IGUAL;
}

La estructura algebraica que hay debajo merece un momento de atención, porque explica por qué esto encaja tan bien con lo que ya sabes de fusiones. El conjunto de vectores con el máximo puntual como operación forma un semirretículo superior: la operación es idempotente, conmutativa y asociativa, y el máximo de dos vectores es su supremo, el vector más pequeño que domina a ambos. Esas tres propiedades son exactamente las que una función de fusión necesita para tolerar reenvíos, reordenamientos y entregas duplicadas sin cambiar el resultado. El vector clock no es solo un reloj: es el mismo tipo de objeto matemático que un CRDT de estado, y por eso se compone con ellos sin fricción.

La condición fuerte del reloj

La propiedad que justifica todo el coste se enuncia en una línea: para dos eventos cualesquiera a y b, se cumple V(a) < V(b) si y solo si a precede causalmente a b. Las dos direcciones. El reloj de Lamport solo te daba la de ida; el vector te da también la de vuelta, y de la vuelta se sigue el corolario que de verdad usas a diario: dos eventos son concurrentes exactamente cuando sus vectores son incomparables. No aproximadamente, no con falsos positivos que después habrá que filtrar. Exactamente.

Dicho con más precisión, el vector clock es una inmersión isomorfa del conjunto parcialmente ordenado de los eventos en el retículo de los enteros no negativos de dimensión n con el orden producto. La palabra clave es isomorfa: la estructura de orden se conserva íntegra en los dos sentidos, de modo que trabajar con los vectores es indistinguible de trabajar con el grafo causal completo, solo que sin guardar el grafo.

Y hay un resultado que conviene conocer porque convierte el coste de la lección tres en algo muy distinto de un defecto de implementación. Charron-Bost demostró en 1991 que la dimensión n es necesaria: para un sistema de n procesos con causalidad arbitraria no existe ningún reloj de dimensión menor que n capaz de caracterizar la relación de precedencia. Es una cota inferior, no una carencia del algoritmo. Cuando en la tercera lección discutas estrategias de poda estarás negociando con un teorema, y por eso ninguna de esas estrategias será gratis.

Lo que compra en local-first

El escenario canónico cabe en tres frases. Editas el título de un documento en el portátil sin conexión. Editas el mismo título en el móvil, también sin conexión. Ambos dispositivos vuelven a la red. Con una marca de tiempo de pared, el sistema compara dos números, se queda con el mayor y descarta el otro en silencio: nadie sabrá jamás que hubo una decisión, y ni siquiera es cierto que ganara la edición más reciente, porque los relojes de dos dispositivos no coinciden. Con vectores, la comparación devuelve concurrencia, y a partir de ese verdadero se abre el abanico de políticas que sí puedes defender ante un usuario.

Hay un segundo uso menos comentado y muy rentable: el vector como filtro de idempotencia. Antes de aplicar un evento, una réplica compara su vector con el sello del evento y, si ya lo domina, lo descarta sin tocar el estado. Esa comprobación exacta es lo que permite construir sincronización sobre transportes baratos y poco fiables, reenviar por si acaso y no perder el sueño con los duplicados.

El tercer uso es el que convierte el vector en un mecanismo de entrega y no solo de diagnóstico. Un evento puede aplicarse cuando su sello indica que es el siguiente de su réplica y que todo lo que su emisor había visto ya está en tu estado; si no, se guarda en una zona de espera hasta que llegue lo que falta. Esa condición se lee directamente del vector y no necesita ningún acuerdo previo entre las réplicas.

function esEntregable(vLocal, sello, origen) {
  for (const id of Object.keys(sello)) {
    const esperado = id === origen ? (vLocal[id] ?? 0) + 1 : vLocal[id] ?? 0;
    if (sello[id] > esperado) return false; // falta algo de su pasado causal
  }
  return true;
}

function intentarEntregar(reloj, pendientes, aplicar) {
  let progreso = true;
  while (progreso) { // desbloquear uno puede desbloquear a otros
    progreso = false;
    for (const ev of [...pendientes]) {
      if (!esEntregable(reloj.v, ev.sello, ev.origen)) continue;
      pendientes.delete(ev);
      alRecibir(reloj, ev.sello);
      aplicar(ev);
      progreso = true;
    }
  }
}

Fíjate en la forma del bucle: cada entrega puede habilitar otras, así que hay que reintentar la cola completa hasta que un pase entero no consiga aplicar nada. Y observa lo que ese código no hace: no espera confirmaciones, no negocia una sesión, no pide nada al emisor. Toda la coordinación está codificada en el sello, que es exactamente la razón por la que este mecanismo sobrevive a una red que se corta a mitad de frase.