Relógios lógicos são contadores que substituem o tempo físico em sistemas distribuídos para determinar a ordem causal entre eventos, sem depender de sincronização de relógio entre máquinas.
Proposto por Leslie Lamport em 1978 no paper Time, Clocks, and the Ordering of Events in a Distributed System, um dos textos mais citados em ciência da computação.
Por que relógios físicos não bastam
Em um sistema distribuído, cada máquina tem seu próprio relógio. Esses relógios derivam ao longo do tempo (clock drift) e podem até andar para trás após sincronização com NTP. A diferença entre duas máquinas em produção é facilmente de centenas de milissegundos.
Se o processo A registra um evento às 10:00:00.100 e o processo B registra outro às 10:00:00.050, a diferença de 50ms não é suficiente para concluir que o evento de B aconteceu antes. O relógio de B pode estar adiantado.
Comparar timestamps físicos entre máquinas diferentes não garante ordem causal. Lamport propôs substituir “quando no relógio de parede” por “o que causou o quê”.
A relação happens-before (→)
A relação → (lê-se “acontece antes de”) define causalidade sem depender de tempo físico:
- Se
aebsão eventos no mesmo processo eaocorre antes deb:a → b - Se
aé o envio de uma mensagem ebé o recebimento dessa mesma mensagem:a → b - Transitividade: se
a → beb → c, entãoa → c
Quando nem a → b nem b → a, os eventos são concorrentes (a ∥ b): aconteceram sem que um causasse o outro.
Processo 1: A ──→ B ────────────────→ E
\ ↗
mensagem /
\ /
Processo 2: C ──→ D ──→ F
A → B (mesmo processo)
B → D (B enviou mensagem, D recebeu)
D → F (mesmo processo)
B → F (transitividade)
A ∥ C (concorrentes: nenhum causou o outro)
Relógio de Lamport
Cada processo mantém um contador inteiro LC, inicialmente 0. As três regras:
- Antes de qualquer evento local:
LC = LC + 1 - Antes de enviar uma mensagem:
LC = LC + 1; enviaLCjunto com a mensagem - Ao receber uma mensagem com timestamp
T:LC = max(LC, T) + 1
Processo 1: LC=1 LC=2 LC=4
A ─────→ B ──mensagem──→ E(LC=5)
↑
Processo 2: LC=1 LC=2 LC=3 recebe msg(T=2) → LC=max(3,2)+1=4
C ──→ D ──→ F(LC=4)
Propriedade garantida: se a → b, então LC(a) < LC(b).
Propriedade que NÃO vale: LC(a) < LC(b) não implica a → b. O relógio de Lamport dá uma ordem parcial, não detecta concorrência. Dois eventos concorrentes podem ter LCs diferentes, e não há como distinguir isso de uma relação causal.
Vector Clocks: detectando concorrência
Proposto por Fidge e Mattern em 1988. Cada processo mantém um vetor de contadores, um por processo no sistema.
Para um sistema com 3 processos [P1, P2, P3], cada processo carrega VC = [c1, c2, c3].
Regras:
- Antes de evento local em
Pi:VC[i] = VC[i] + 1 - Antes de enviar mensagem em
Pi:VC[i] = VC[i] + 1; envia o vetor inteiro - Ao receber mensagem com vetor
VMemPi:VC[j] = max(VC[j], VM[j])para todoj; depoisVC[i] = VC[i] + 1
P1: [1,0,0] ──→ [2,0,0] ──mensagem──────────────────────→ recebe
P2: [0,1,0] recebe msg de P1 → [2,2,0] ──→ [2,3,0]
P3: [0,0,1] ──→ [0,0,2]
Comparação entre vetores:
VC(a) ≤ VC(b)se todoVC(a)[i] ≤ VC(b)[i]:acausalmente precedebVC(a) = VC(b): mesmo evento- Nem
VC(a) ≤ VC(b)nemVC(b) ≤ VC(a): eventos concorrentes
Essa última propriedade é o que o relógio de Lamport não consegue expressar.
Lamport vs Vector Clocks
| Característica | Lamport | Vector Clock |
|---|---|---|
| Espaço por mensagem | O(1), um inteiro | O(n), um inteiro por processo |
Detecta a → b | Sim (se LC(a) < LC(b), pode ser) | Sim (preciso) |
| Detecta concorrência | Não | Sim |
Detecta b → a dado LC(a) < LC(b) | Não | Sim |
| Escalabilidade | Alta | Degradação com muitos processos |
Para sistemas com dezenas de nós, o vetor cresce e o overhead de transmissão aumenta. Variantes como Dotted Version Vectors e Interval Tree Clocks resolvem esse problema para casos específicos.
Aplicações práticas
Bancos de dados distribuídos: Riak e Amazon Dynamo usam vector clocks para detectar conflitos de escrita. Quando dois clientes escrevem no mesmo dado sem coordenação, o vetor revela que os eventos são concorrentes e a aplicação pode decidir como reconciliar (merge, last-write-wins, ou apresentar conflito ao usuário).
CRDTs: estruturas de dados que resolvem conflitos automaticamente (contadores, sets, registros) dependem de causalidade para aplicar operações na ordem correta independentemente da ordem de chegada.
Git: o grafo de commits é um vector clock informal. O merge detecta que dois commits são concorrentes (branches paralelos) e pede reconciliação. git log --graph é a visualização da relação →.
Consistência causal em bancos: sistemas EL que oferecem consistência causal (como MongoDB com causal sessions ou Cosmos DB) usam tokens de causalidade derivados de vector clocks para garantir que uma sessão nunca veja um estado anterior ao que já leu.
Depuração distribuída: ferramentas como Jepsen reconstroem a ordem causal de operações em testes de sistemas distribuídos usando exatamente a relação → para encontrar violações de consistência.
Conexões
- teorema-cap: consistência no CAP pressupõe linearizabilidade; relógios lógicos são o mecanismo que sistemas causalmente consistentes usam como alternativa
- pacelc: consistência causal é um dos modelos intermediários entre forte e eventual no eixo EL vs EC
- db-nosql: Cassandra, Riak e DynamoDB usam variantes de vector clocks para detecção e resolução de conflitos
- gcp-spanner: Spanner usa TrueTime (relógio físico de alta precisão via GPS/atômico) para ordenação global, evitando relógios lógicos ao custo de infraestrutura especializada
Referências
- Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (1978, CACM)
- Colin Fidge, Timestamps in Message-Passing Systems That Preserve the Partial Ordering (1988)
- Friedemann Mattern, Virtual Time and Global States of Distributed Systems (1989)
- Martin Kleppmann, Designing Data-Intensive Applications, cap. 8 e 9
- Marc Shapiro et al., A Comprehensive Study of Convergent and Commutative Replicated Data Types (2011), sobre CRDTs e causalidade