Vector clocks: cómo Dynamo y Riak ordenan eventos sin reloj central

Lo esencial

• Un vector clock es un arreglo de contadores, uno por nodo, que reemplaza al reloj de pared para ordenar eventos.
• Leslie Lamport describió la base del concepto en 1978 en su paper sobre relojes lógicos en sistemas distribuidos.
• Amazon Dynamo los usó en 2007 para detectar conflictos de escritura entre réplicas sin coordinador central.
• Riak los implementó en producción y luego migró a dotted version vectors para acotar su crecimiento.
• Dos vector clocks son concurrentes si ninguno domina al otro componente a componente: ahí hay un conflicto real.
• El vector crece sin límite: cada nodo que alguna vez escribió el dato agrega una entrada para siempre.
• Cassandra y el DynamoDB moderno de AWS evitan el vector completo y usan timestamps con last-write-wins.

El problema: no hay un reloj que todos compartan

En una sola máquina, ordenar dos eventos es trivial: uno pasó antes que el otro porque el reloj del sistema lo dice. En un sistema distribuido con varios nodos escribiendo al mismo tiempo, esa certeza desaparece.

Los relojes de pared de cada servidor nunca están perfectamente sincronizados. NTP corrige la diferencia cada cierto tiempo, pero deja un margen de milisegundos que alcanza para invertir el orden real de dos escrituras cercanas.

Si dos réplicas de una base de datos reciben una escritura del mismo registro casi al mismo tiempo, ¿cuál pasó primero? Con reloj de pared, la respuesta puede ser distinta según a qué servidor le preguntes.

Qué es un vector clock

Un vector clock reemplaza el tiempo por un contador lógico. Cada nodo del sistema tiene una posición en un vector de enteros; cuando ese nodo genera un evento, incrementa solo su propia posición.

Con tres réplicas A, B y C, un vector clock se ve como [2, 0, 1]: la réplica A generó dos eventos, B ninguno todavía y C uno. El vector no mide tiempo en segundos, mide cuántos eventos causales conoce cada nodo.

La idea viene del paper de Leslie Lamport de 1978 sobre relojes lógicos: ese trabajo definió los relojes escalares (un único contador por evento) y sentó las bases que Colin Fidge y Friedemann Mattern extendieron a vectores en 1988 para capturar causalidad completa entre procesos.

Cómo se actualiza el vector en cada evento

Las reglas son solo dos. Cuando un nodo genera un evento local (por ejemplo, escribe un dato), incrementa únicamente su propia entrada en el vector.

Cuando un nodo recibe un mensaje de otro nodo, combina ambos vectores tomando el máximo de cada posición y después incrementa su propia entrada. Así el vector resultante conoce todo lo que sabían ambos nodos antes del mensaje.

• Evento local: incrementar solo la posición propia.
• Recepción de mensaje: vector = máximo componente a componente entre ambos, luego incrementar la posición propia.

Comparar dos vector clocks: orden causal y conflictos

Un vector V1 precede causalmente a V2 si cada componente de V1 es menor o igual al componente correspondiente de V2, y al menos uno es estrictamente menor. Eso significa que V1 es un antecesor causal de V2: todo lo que sabía V1 también lo sabe V2.

Si ninguno de los dos vectores domina al otro (cada uno tiene alguna posición mayor que la del otro), los eventos son concurrentes: ocurrieron sin que uno tuviera información del otro. En una base de datos, esto es exactamente un conflicto de escritura real, no un error de sincronización.

Código: implementación mínima en Python

Una implementación de vector clock cabe en pocas líneas. Cada réplica mantiene su propio diccionario nodo-contador:

class VectorClock:
    def __init__(self, node_id, nodes):
        self.node_id = node_id
        self.clock = {n: 0 for n in nodes}

    def increment(self):
        self.clock[self.node_id] += 1

    def merge(self, other):
        for node, count in other.clock.items():
            self.clock[node] = max(self.clock[node], count)

    def happened_before(self, other):
        leq = all(self.clock[n] <= other.clock[n] for n in self.clock)
        return leq and self.clock != other.clock

    def concurrent_with(self, other):
        return not self.happened_before(other) and not other.happened_before(self)

Con dos réplicas que escriben el mismo ítem sin haberse comunicado antes, replica_a.concurrent_with(replica_b) devuelve True. Esa es la señal exacta que Dynamo usa para decidir que hay dos versiones válidas y no puede quedarse con una automáticamente.

El caso real: Amazon Dynamo y los carritos de compra

El paper de Dynamo, publicado por ingenieros de Amazon en 2007, usó vector clocks para resolver un problema concreto: el carrito de compras de Amazon.com debía aceptar escrituras aunque una réplica estuviera desconectada de las demás.

Cuando dos réplicas reciben ediciones distintas del mismo carrito sin sincronizarse entre sí, Dynamo detecta que los vectores son concurrentes y devuelve ambas versiones al cliente. La aplicación las fusiona (en el caso del carrito, uniendo los ítems) en lugar de que el servidor descarte una arbitrariamente.

El diseño completo está documentado en el paper original de Amazon Dynamo (SOSP 2007), que además influyó directamente en el diseño de Cassandra y Riak.

El límite: por qué Riak los reemplazó

El gotcha de los vector clocks es el crecimiento. Cada nodo que alguna vez escribió el dato queda registrado en el vector para siempre, incluso si ese nodo ya no existe. Con miles de clientes escribiendo directamente (como permitía Dynamo en algunos modos), el vector puede volverse más pesado que el dato que acompaña.

Riak documentó este problema y migró a dotted version vectors, una variante que poda entradas obsoletas sin perder la garantía de detectar concurrencia real. El concepto está explicado en la documentación de Riak sobre contexto causal.

Por eso, si tu sistema no necesita resolver conflictos entre escrituras concurrentes (por ejemplo, porque un único líder ordena todas las escrituras), un vector clock completo es complejidad de más: un timestamp con reloj sincronizado y la regla last-write-wins alcanza y sale más barato de operar.

Por qué importa hoy

Cassandra y el DynamoDB gestionado de AWS (que a pesar del nombre no usa vector clocks completos) resolvieron el mismo problema con timestamps de reloj y last-write-wins, aceptando perder alguna escritura rara a cambio de menos complejidad operativa.

Entender vector clocks no es solo historia de bases de datos: es la misma lógica que usan los CRDTs para fusionar ediciones colaborativas y la que hay detrás de cualquier sistema que necesite responder una pregunta simple sin reloj central: ¿este cambio ya sabía del otro, o pasaron al mismo tiempo?