Relojes lógicos: marcas de tiempo de Lamport, relojes vectoriales y relojes híbridos

Qué es

El artículo de Lamport de 1978 (aparece en su página de publicaciones, citado) define la relación «ocurrió antes de» ("happened before"): el evento a precede a b si ambos ocurren en el mismo proceso en ese orden, si a es el envío de un mensaje y b su recepción, o por transitividad. Un reloj de Lamport es un contador por proceso: se incrementa en cada evento local, se adjunta a cada mensaje y, al recibir uno, se fija el contador en el máximo entre el valor local y el recibido, más uno. Si a ocurrió antes que b, entonces clock(a) < clock(b); el recíproco no se cumple, de modo que marcas iguales o cercanas no dicen nada sobre la causalidad. Si se desempata con un identificador de proceso, se obtiene un orden total.

Un reloj vectorial, tal como se describe en el artículo de Dynamo (citado), es una lista de pares (nodo, contador) adjunta a cada versión de un objeto. Al comparar dos vectores se ve si una versión desciende de la otra o si están en ramas paralelas; así detecta Dynamo las escrituras en conflicto, que se reconcilian en la lectura.

Los relojes lógicos híbridos (HLC) combinan ambas ideas. La documentación de CockroachDB (citada) describe un HLC como un componente físico cercano a la hora de pared local más un componente lógico que distingue eventos con el mismo valor físico, de modo que el tiempo HLC es siempre mayor o igual que la hora de pared y aun así ordena los eventos relacionados causalmente.

Por qué importa

La estrategia «gana la última escritura según la marca de tiempo» descarta actualizaciones sin avisar cuando el desfase entre relojes es mayor que el tiempo transcurrido entre dos escrituras. Los datos replicados, los clientes que pueden funcionar sin conexión y los despliegues multirregión se topan todos con este problema.

Cómo aplicarlo

• Da a cada registro mutable un contador de versión que aumente en cada escritura y úsalo para el control de concurrencia optimista (UPDATE ... WHERE version = $seen); es un reloj de Lamport por registro.
• En flujos de eventos, ordena por número de secuencia dentro de una partición, no por la marca de tiempo del productor.
• Cuando varias réplicas aceptan escrituras, mantén un vector de versiones por registro o usa un tipo de datos con una fusión definida (un CRDT), y expón los conflictos en lugar de elegir un ganador según el reloj de pared.
• Usa marcas de tiempo de reloj de pared para mostrar datos y para la retención, y anota en el diseño la fuente del reloj (sincronizada mediante NTP o no).

Trampas

Los relojes vectoriales crecen con el número de escritores y requieren reglas de poda. Los relojes de Lamport ordenan, pero no pueden detectar la concurrencia. Un reloj monótono de una máquina no dice nada sobre el reloj de otra.