Relógios lógicos: timestamps de Lamport, vector clocks e relógios híbridos

O que é

O artigo de Lamport de 1978 (listado na página de publicações dele, citado) define a relação "aconteceu antes" ("happened before"): o evento a precede o evento b se ambos ocorrem no mesmo processo nessa ordem, se a é o envio de uma mensagem e b é o recebimento dela, ou por transitividade. Um relógio de Lamport é um contador por processo: ele é incrementado a cada evento local, anexado a cada mensagem e, ao receber uma mensagem, o contador passa a ser o máximo entre o valor local e o valor recebido, mais um. Se a aconteceu antes de b, então clock(a) < clock(b); o inverso não vale, de modo que timestamps iguais ou próximos não dizem nada sobre causalidade. Desempatar com um identificador de processo produz uma ordem total.

Um vector clock, como descrito no artigo do Dynamo (citado), é uma lista de pares (nó, contador) anexada a cada versão de um objeto. Comparar dois vetores mostra se uma versão descende da outra ou se estão em ramos paralelos, e é assim que o Dynamo detecta escritas conflitantes, que são reconciliadas na leitura.

Os relógios lógicos híbridos (HLC) combinam as duas ideias. A documentação do CockroachDB (citada) descreve um HLC como um componente físico, próximo da hora de parede local, mais um componente lógico que distingue eventos com o mesmo valor físico. Assim, o tempo do HLC é sempre maior ou igual à hora de parede e ainda ordena eventos relacionados causalmente.

Por que importa

A estratégia "o último a escrever vence, segundo o timestamp" descarta atualizações silenciosamente quando o desvio entre os relógios é maior do que o intervalo entre duas escritas. Dados replicados, clientes com suporte offline e implantações multirregião enfrentam esse problema.

Como aplicar

• Dê a cada registro mutável um contador de versão que aumenta a cada escrita e use-o para concorrência otimista (UPDATE ... WHERE version = $seen); isso é um relógio de Lamport por registro.
• Em fluxos de eventos, ordene pelo número de sequência dentro de uma partição, não pelo timestamp do produtor.
• Onde várias réplicas aceitam escritas, mantenha um version vector por registro ou use um tipo de dados com merge definido (um CRDT), e exponha os conflitos em vez de escolher um vencedor pelo relógio de parede.
• Use timestamps de relógio de parede para exibição e retenção, e registre no design a fonte do relógio (com ou sem disciplina por NTP).

Armadilhas

Os vector clocks crescem com o número de escritores e exigem regras de poda. Os relógios de Lamport ordenam, mas não conseguem detectar concorrência. Um relógio monotônico em uma máquina não diz nada sobre o relógio de outra máquina.