Algoritmos de sincronización: LWW, relojes vectoriales y CRDT

Resumen

• Cuando varias copias de un dato aceptan cambios por separado, tarde o temprano divergen y hace falta una regla para que vuelvan a coincidir.
• Last-write-wins es la regla más simple, pero descarta cambios; los relojes vectoriales detectan conflictos reales; los CRDT los evitan por diseño.
• La elección depende del dato: una preferencia, un contador y una lista de compras necesitan algoritmos distintos.

¿Cuál es el problema que resuelven estos algoritmos?

Resuelven qué hacer cuando dos réplicas de un mismo dato se modificaron sin comunicarse y después se reencuentran. A esto se le llama reconciliación o convergencia.

Pasa en más lugares de los que parece: una app de notas usada en el teléfono y en la computadora, un carrito de compras abierto en dos pestañas, una base de datos replicada en varias regiones o cualquier aplicación offline-first. En todos los casos, exigir que cada escritura se coordine con las demás copias antes de aceptarse haría el sistema lento o inutilizable sin red. Por eso muchos sistemas aceptan escrituras locales y prometen consistencia eventual: si dejan de llegar cambios, todas las réplicas terminan iguales.

La pregunta difícil es cómo terminan iguales sin perder información importante.

¿Por qué no basta con comparar la hora de cada cambio?

Porque los relojes físicos de distintos equipos no están perfectamente sincronizados, y el orden real de los eventos no siempre coincide con lo que marca cada reloj.

Leslie Lamport lo planteó en 1978 en Time, Clocks, and the Ordering of Events in a Distributed System: en un sistema distribuido, “antes” y “después” solo están bien definidos cuando un evento pudo influir en el otro. Si dos cambios ocurren sin que ninguna réplica supiera del otro, son concurrentes, y ninguna marca de tiempo resuelve eso de forma honesta.

¿Qué es last-write-wins y cuándo sirve?

Last-write-wins (LWW) conserva la versión con la marca de tiempo más reciente y descarta la otra. Es fácil de implementar y siempre converge, pero pierde datos en silencio.

type Registro<T> = { valor: T; ts: number; replica: string };

function mergeLww<T>(a: Registro<T>, b: Registro<T>): Registro<T> {
  if (a.ts !== b.ts) return a.ts > b.ts ? a : b;
  // Desempate determinista para que todas las réplicas elijan lo mismo
  return a.replica > b.replica ? a : b;
}

Fíjate en el desempate: sin él, dos réplicas con la misma marca de tiempo podrían elegir valores distintos y nunca converger.

LWW funciona bien para datos donde “el último valor” es lo que importa y perder una edición concurrente es tolerable: el tema visual elegido, la última ubicación conocida, el estado de un interruptor. Funciona mal para contadores (dos incrementos concurrentes terminan contando uno) y para listas (un elemento agregado en una réplica desaparece si la otra sobrescribe la lista entera).

Una mejora común es aplicar LWW por campo y no por documento completo: si una réplica cambió el título y otra la descripción, se conservan ambos cambios.

¿Qué son los relojes de Lamport?

Son contadores lógicos que cada réplica incrementa y adjunta a sus eventos, de modo que si un evento causó otro, el primero siempre tiene un número menor.

Las reglas del artículo de Lamport se resumen en dos: cada réplica incrementa su contador antes de cada evento, y al recibir un mensaje ajusta su contador al máximo entre el propio y el recibido, más uno. Con un desempate por identificador de réplica, esto da un orden total que respeta la causalidad.

La limitación es importante: si el evento A tiene número 5 y el B tiene 7, no se puede saber si A causó B o si ocurrieron por separado. Para detectar conflictos reales hace falta más información.

¿Qué es un reloj vectorial y cómo detecta conflictos?

Un reloj vectorial guarda un contador por cada réplica; comparando dos vectores se sabe si un cambio sucedió después de otro o si ambos fueron concurrentes.

La idea la introdujeron de forma independiente Colin Fidge y Friedemann Mattern a finales de los años 80. Cada réplica incrementa su propia posición al modificar el dato, y al fusionar se toma el máximo posición por posición.

type Vector = Record<string, number>;

type Orden = "antes" | "despues" | "igual" | "concurrente";

function comparar(a: Vector, b: Vector): Orden {
  const claves = new Set([...Object.keys(a), ...Object.keys(b)]);
  let aMenor = false, bMenor = false;
  for (const k of claves) {
    const va = a[k] ?? 0, vb = b[k] ?? 0;
    if (va < vb) aMenor = true;
    if (vb < va) bMenor = true;
  }
  if (aMenor && bMenor) return "concurrente"; // conflicto real
  if (aMenor) return "antes";
  if (bMenor) return "despues";
  return "igual";
}

// { tel: 2, pc: 1 } vs { tel: 1, pc: 2 }  ->  "concurrente"

Cuando el resultado es "antes" o "despues", se conserva la versión más nueva sin miedo a perder nada. Cuando es "concurrente", el sistema sabe que hay un conflicto genuino y puede guardar ambas versiones para que la aplicación o el usuario decidan.

El costo: el vector crece con el número de réplicas que han escrito el dato, y hay que decidir qué hacer con las versiones hermanas.

¿Qué es un CRDT?

Un CRDT (Conflict-free Replicated Data Type) es una estructura de datos diseñada para que las réplicas se puedan modificar sin coordinación y siempre converjan al mismo estado.

El concepto lo formalizaron Marc Shapiro, Nuno Preguiça, Carlos Baquero y Marek Zawirski en Conflict-free Replicated Data Types (SSS 2011). El artículo describe dos familias:

• Basados en estado: las réplicas intercambian su estado completo y lo combinan con una función de fusión que es conmutativa, asociativa e idempotente. No importa el orden ni si un mensaje llega dos veces.
• Basados en operaciones: las réplicas intercambian operaciones que conmutan entre sí, lo que exige que la capa de red las entregue (en orden causal cuando corresponde).

El ejemplo más simple es un contador que solo crece (G-Counter). Cada réplica cuenta sus propios incrementos y la fusión toma el máximo por réplica:

def incrementar(estado: dict, replica: str) -> None:
    estado[replica] = estado.get(replica, 0) + 1

def fusionar(a: dict, b: dict) -> dict:
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in a.keys() | b.keys()}

def valor(estado: dict) -> int:
    return sum(estado.values())

# Teléfono suma 2 y computadora suma 1 sin conexión:
tel, pc = {"tel": 2}, {"pc": 1}
assert valor(fusionar(tel, pc)) == 3   # no se pierde ningún incremento

Con la misma lógica se construyen estructuras más útiles: contadores que suben y bajan (dos G-Counter, uno para sumas y otro para restas), registros LWW y conjuntos como el OR-Set (observed-remove set), donde cada elemento agregado lleva una etiqueta única y un borrado solo elimina las etiquetas que la réplica ya había visto. Así, si alguien agrega “leche” al carrito mientras otra persona borra una “leche” anterior, la nueva no desaparece.

¿Se pueden usar CRDT para texto colaborativo?

Sí, existen CRDT de secuencia que permiten que varias personas escriban el mismo documento a la vez. Asignan a cada carácter un identificador que define su posición de forma estable, de modo que las inserciones concurrentes quedan en un orden determinista.

El otro enfoque clásico para edición colaborativa es la transformación operacional (OT), que ajusta cada operación según las que ocurrieron en paralelo y, en la práctica, suele apoyarse en un servidor central que ordena los cambios. Ambos enfoques conviven. El sitio crdt.tech mantiene una bibliografía extensa si quieres profundizar.

¿Qué costos tienen los CRDT?

El precio de la convergencia automática es metadata extra y una semántica que no siempre coincide con lo que el usuario espera.

• Metadata: identificadores por elemento, vectores de versión y marcas de borrado (tombstones) que ocupan espacio. Hay trabajos dedicados solo a reducirla, como la versión optimizada del OR-Set sin tombstones (Bieniusa et al., 2012).
• Semántica fija: un CRDT converge, pero converge a su regla. Si dos personas cambian el precio de un mismo producto a valores distintos, un registro LWW elegirá uno; “convergió” no significa “hizo lo correcto para el negocio”.
• Invariantes globales: un CRDT no puede garantizar por sí solo reglas como “el saldo nunca es negativo” o “solo queda una unidad”. Para eso hace falta coordinación.

¿Qué algoritmo conviene elegir?

Elige por tipo de dato, no por sistema completo. Una misma aplicación suele combinar varias estrategias:

Tipo de dato	Estrategia razonable
Preferencias, estados simples	LWW por campo
Contadores (likes, visitas)	CRDT de contador
Listas y conjuntos (etiquetas, carrito)	OR-Set u otro CRDT de conjunto
Texto colaborativo	CRDT de secuencia u OT
Datos con reglas estrictas (saldos, stock único)	Coordinación con el servidor
Datos valiosos con conflicto posible	Relojes vectoriales y resolución explícita

Y no olvides la capa de transporte: aunque el algoritmo de fusión sea perfecto, los cambios tienen que llegar. Eso depende de reintentos seguros e idempotentes, que explicamos en colas de reintentos. Si además tu sistema atiende a muchos clientes con datos aislados, la forma de particionar esos datos importa tanto como el algoritmo; lo vemos en modelo de datos multi-tenant.

Para cerrar

Sincronizar no es copiar datos de un lado a otro: es decidir qué significa que dos versiones “estén de acuerdo”. LWW responde con simplicidad, los relojes vectoriales con honestidad sobre los conflictos y los CRDT con garantías matemáticas. Conocer los tres te permite elegir, dato por dato, cuánto estás dispuesto a perder a cambio de no coordinar.