Bases de datos distribuidas y el tiempo - Orden causal y relojes lógicos

Por qué el tiempo global es imposible

En un servidor único, cada evento puede tener una marca de tiempo única y el orden de los eventos está completamente determinado. Los sistemas distribuidos renuncian a ese lujo. Múltiples nodos mantienen sus propios relojes y la latencia de red es impredecible, por lo que decidir cuál de dos eventos ocurrió primero es fundamentalmente difícil. El problema no es pereza de ingeniería; es una propiedad de los sistemas físicamente separados.

Incluso con sincronización NTP, persiste un desfase de milisegundos a decenas de milisegundos. Si el evento A ocurrió a las 12:00:00.005 en el nodo A y el evento B ocurrió a las 12:00:00.008 en el nodo B, el orden real no puede determinarse dentro de los márgenes de error de NTP. Esta incertidumbre desafía fundamentalmente la consistencia transaccional en bases de datos distribuidas, y el campo ha dedicado décadas a desarrollar soluciones alternativas.

Relojes de Lamport - Orden parcial mediante causalidad

El reloj lógico de Leslie Lamport (1978) rastrea la causalidad (la relación «ocurrió antes que») entre eventos sin depender del tiempo físico. Cada nodo mantiene un contador, lo incrementa en eventos locales, lo adjunta a los mensajes salientes y lo actualiza a max(local, recibido) + 1 al recibir un mensaje. El resultado es una marca de tiempo que respeta el orden causal incluso sin sincronización de reloj.

Los relojes de Lamport garantizan que si A causa B, entonces la marca de tiempo de A es menor que la de B. Sin embargo, lo inverso no se cumple: una marca de tiempo menor no implica causalidad. El sistema no puede distinguir eventos concurrentes de eventos causalmente relacionados. Los relojes vectoriales se inventaron para superar esta limitación al transportar más información.

Relojes vectoriales - Detectar concurrencia

Un reloj vectorial en un sistema de N nodos representa el tiempo como un vector de N dimensiones, un contador por nodo. Comparar los vectores de dos eventos permite determinar si uno ocurrió antes que el otro (un vector domina al otro elemento a elemento) o si son concurrentes (ninguno domina). Dynamo de Amazon (artículo de 2007) utilizó relojes vectoriales para detectar conflictos de escritura.

La desventaja es que el vector crece con el clúster. Los sistemas con miles de nodos adjuntan miles de contadores a cada mensaje, y la sobrecarga en ancho de banda y almacenamiento se vuelve sustancial. Los sistemas prácticos podan los vectores o migran a alternativas como el Reloj Lógico Híbrido para evitar este problema de escalabilidad.

TrueTime de Google Spanner - Abrazar la incertidumbre

Spanner de Google (2012) adopta un enfoque único al exponer la incertidumbre del reloj físico en su API. La API de TrueTime devuelve el tiempo actual como un intervalo [más temprano, más tardío], no un valor único. Al instalar receptores GPS y relojes atómicos en cada centro de datos, Spanner mantiene la incertidumbre típicamente por debajo de unos 7 milisegundos.

Las transacciones de Spanner esperan a que el intervalo de incertidumbre de TrueTime transcurra antes de confirmar (commit-wait), garantizando así consistencia externa (linealizabilidad). Con 7 ms de incertidumbre, cada transacción añade 7 ms de espera. El diseño intercambia hardware dedicado (GPS más relojes atómicos) por garantías fuertes de transacciones distribuidas que otros sistemas tienen dificultades para igualar.

Reloj Lógico Híbrido - El compromiso práctico

El Reloj Lógico Híbrido (HLC) combina relojes físicos y lógicos en un solo par de marca de tiempo (tiempo_físico, contador_lógico). El tiempo físico domina normalmente, pero los eventos dentro del mismo milisegundo físico se ordenan por el contador lógico. CockroachDB adopta HLC para ofrecer consistencia fuerte sin requerir hardware especializado.

El atractivo de HLC es que funciona en servidores ordinarios sincronizados con NTP y produce marcas de tiempo cercanas al tiempo físico legible por humanos. No alcanza la rigurosidad de Spanner, pero dentro de los márgenes de error de NTP proporciona consistencia práctica, resolviendo conflictos dentro de la ventana de incertidumbre mediante reintentos. Para la mayoría de las bases de datos distribuidas que no pueden instalar GPS en sus centros de datos, HLC representa el punto medio más razonable.