Tempo e Relógios

O assento A-12 está reservado para o Bruno. Às 10:00:00.040 (tempo real) ele desiste e o libera pelo inventory-1; vinte milissegundos depois, às 10:00:00.060, a Carla o pega pelo inventory-2. As duas atualizações são replicadas para os outros nós, e o armazenamento resolve o conflito com a regra mais comum que existe — last write wins (a última escrita vence) por timestamp. Mas o relógio do inventory-1 está 50 ms adiantado: a liberação do Bruno recebe o carimbo 10:00:00.090, e a reserva da Carla, 10:00:00.060. A liberação "vence", o assento aparece como FREE, e a Carla — que já foi cobrada — fica sem assento. Nenhuma mensagem se perdeu e nenhum código tinha bug: o sistema simplesmente confiou em dois relógios que discordavam.

Um sistema distribuído não tem relógio global. Cada máquina tem o seu, eles se afastam uns dos outros, e o atraso de rede entre elas é variável e desconhecido — então "o que aconteceu primeiro?" não tem resposta de graça. Esta página mostra o que relógios físicos conseguem e não conseguem fazer, e as ferramentas que ordenam eventos sem confiar neles: relógios lógicos, relógios vetoriais, relógios híbridos, TrueTime e simples autoridades únicas.

Dois relógios em toda máquina

Todo sistema operacional oferece dois relógios diferentes, e confundi-los é um bug clássico:

// Wrong: if NTP steps the wall clock during the call, the "duration" can be negative or huge
long start = System.currentTimeMillis();
callPaymentProvider();
long elapsedMs = System.currentTimeMillis() - start;

// Right: the monotonic clock only measures elapsed time, and never goes backwards
long t0 = System.nanoTime();
callPaymentProvider();
long elapsedNs = System.nanoTime() - t0;

Relógios físicos derivam

O relógio de um computador é um oscilador de quartzo, e o quartzo é imperfeito: sua frequência depende da temperatura e do cristal. A deriva é medida em ppm (partes por milhão): 20 ppm significam 20 µs ganhos ou perdidos por segundo — cerca de 1,7 segundo por dia. O Google supõe um limite de 200 ppm para seus servidores¹. Abandonados à própria sorte, os relógios de duas máquinas divergem sem limite.

O NTP (Network Time Protocol) corrige isso perguntando periodicamente a servidores de tempo (organizados em estratos, sendo o estrato 0 formado por relógios atômicos ou GPS) e ajustando o relógio local — aos poucos (slewing) para pequenas diferenças, com um salto (stepping) para grandes. Sua precisão é limitada pelo atraso da rede, que ele não consegue medir exatamente: o NTP supõe que a ida e a volta levaram o mesmo tempo, então atrasos assimétricos viram erro de relógio.

Os servidores sincronizados ficam a poucos milissegundos uns dos outros (um dente de serra: derivam, corrigem, derivam); o que perdeu o NTP se afasta silenciosamente — 24 ms depois de dez minutos a 40 ppm, e mais de três segundos depois de um dia. Nada alerta por padrão. Ordens de grandeza típicas (ilustrativas; dependem muito da montagem):

Por que timestamps não ordenam eventos

A história de abertura, passo a passo. Cada nó carimba sua escrita com o próprio relógio de parede; a replicação entrega as duas escritas aos dois nós; o last-write-wins (LWW) fica com o maior timestamp:

sequenceDiagram
    participant B as Bruno
    participant I1 as inventory-1 (relógio +50 ms)
    participant I2 as inventory-2 (relógio certo)
    participant C as Carla
    B->>I1: libera A-12 (tempo real .040)
    Note over I1: carimbado .090
    C->>I2: reserva A-12 (tempo real .060)
    Note over I2: carimbado .060
    I1->>I2: replica a liberação @ .090
    I2->>I1: replica a reserva @ .060
    Note over I1,I2: LWW: .090 > .060, a liberação vence<br/>a reserva da Carla é descartada em silêncio

Com relógios sincronizados dentro de ε, dois eventos separados por menos de ε não podem ser ordenados por seus timestamps — e, em um armazenamento LWW, o nó com o relógio mais adiantado vence todo conflito. O Cassandra usa LWW por coluna por padrão, e o mesmo vale para qualquer lógica de merge "vence o updated_at maior" que você mesmo escreva. LWW é aceitável quando perder uma de duas escritas concorrentes é inofensivo (uma foto de perfil); é perigoso para assentos e dinheiro.

A saída é parar de perguntar aos relógios quando algo aconteceu e perguntar, em vez disso, o que poderia ter influenciado o quê.

Relógios de Lamport

O artigo de Leslie Lamport de 1978³ — um dos mais citados da computação — observou que o que importa é a relação aconteceu-antes (happened-before, →):

• se a e b acontecem no mesmo processo e a vem primeiro, então a → b;
• se a é o envio de uma mensagem e b o seu recebimento, então a → b;
• se a → b e b → c, então a → c (transitividade).

Se nem a → b nem b → a, os eventos são concorrentes (a ∥ b): nenhum poderia ter influenciado o outro.

Um relógio de Lamport é um contador por processo com três regras:

1. Antes de cada evento local, incremente o contador.
2. Ao enviar uma mensagem, anexe o contador.
3. Ao receber uma mensagem com t, faça o contador valer max(local, t) + 1.

sequenceDiagram
    participant O as order
    participant K as consumidor Kafka (inventory)
    participant N as notification
    Note over O: cria o pedido 981 (L=1)
    O->>K: OrderPaid (L=2)
    Note over K: recebe: max(0, 2) + 1 = 3
    Note over N: evento local não relacionado (L=1)
    K->>N: TicketIssued (L=4)
    Note over N: recebe: max(1, 4) + 1 = 5

A garantia tem um só sentido: se a → b, então L(a) < L(b). A recíproca não vale — L(a) < L(b) não prova que a aconteceu antes de b; eles podem ser concorrentes. Desempatar pelo id do nó dá uma ordem total consistente com a causalidade, o que basta para muitos algoritmos (o termo do Raft é um contador no estilo de Lamport). O que um relógio de Lamport não consegue é detectar concorrência.

Relógios vetoriais

Um relógio vetorial mantém um contador por nó. Cada nó incrementa a própria posição em um evento local, anexa o vetor inteiro às mensagens e, ao receber, pega o máximo elemento a elemento (e então incrementa a própria posição). Comparar dois vetores responde à pergunta que os relógios de Lamport não respondem:

• V(a) ≤ V(b) elemento a elemento (e diferentes) → a → b;
• V(b) ≤ V(a) → b → a;
• nenhum dos dois → concorrentes: um conflito real que precisa de resolução.

Três réplicas do carrinho da Carla (contadores [SP, LIS, NYC]):

O armazenamento guarda as duas versões (irmãos, siblings) e pede à aplicação que as mescle — exatamente o que o Dynamo, da Amazon, fazia com o carrinho de compras (merge por união, e é por isso que itens apagados às vezes voltavam)⁴. O Riak expunha o mesmo modelo.

sequenceDiagram
    participant SP as réplica SP
    participant LIS as réplica LIS
    participant NYC as réplica NYC
    Note over SP: adiciona ingresso [1,0,0]
    SP->>LIS: replica [1,0,0]
    SP->>NYC: replica [1,0,0]
    Note over LIS: adiciona estacionamento [1,1,0]
    Note over NYC: remove ingresso [1,0,1]
    LIS->>NYC: replica [1,1,0]
    Note over NYC: [1,1,0] vs [1,0,1]: concorrentes<br/>guarda os dois, mescla na aplicação

Os dois relógios lado a lado, em três serviços do BoxOffice:

O custo é o tamanho: o vetor cresce com o número de nós (ou clientes) que escrevem. Sistemas práticos usam vetores de versão com uma posição por réplica (não por cliente) e podam posições antigas.

Relógios lógicos híbridos

Relógios lógicos capturam causalidade, mas não têm nada a ver com o tempo real — você não consegue perguntar "qual era o estado às 10:00:00?". Relógios físicos ficam perto do tempo real, mas não capturam causalidade. Um relógio lógico híbrido (HLC, hybrid logical clock, Kulkarni et al., 2014)⁵ combina os dois em um único timestamp de tamanho fixo (l, c):

• l é o maior tempo físico que o nó já viu (o do próprio relógio ou o de qualquer mensagem);
• c é um contador lógico que desempata quando l não avança.

import time

class HLC:
    def __init__(self):
        self.l, self.c = 0, 0                 # (physical part in ms, logical counter)

    def now(self):                             # local event or send
        pt = int(time.time() * 1000)
        if pt > self.l:
            self.l, self.c = pt, 0
        else:
            self.c += 1                        # wall clock did not advance: count
        return (self.l, self.c)

    def update(self, ml, mc):                  # on receiving a message stamped (ml, mc)
        pt = int(time.time() * 1000)
        new_l = max(self.l, ml, pt)
        if new_l == self.l == ml:
            self.c = max(self.c, mc) + 1
        elif new_l == self.l:
            self.c += 1
        elif new_l == ml:
            self.c = mc + 1
        else:
            self.c = 0
        self.l = new_l
        return (self.l, self.c)

Timestamps HLC respeitam a causalidade (como os relógios de Lamport), ficam dentro do erro de sincronização em relação ao tempo real (então servem para snapshots do tipo "leia como estava às 10:00:00") e cabem em 64 bits. CockroachDB, YugabyteDB e MongoDB (cluster time) os usam. Eles ainda dependem de um limite para a defasagem dos relógios: o CockroachDB, por exemplo, tem um offset máximo configurado (500 ms por padrão), e um nó que detecta estar mais defasado que isso se desliga em vez de arriscar inconsistência⁶.

TrueTime e Spanner

O Spanner do Google¹ seguiu o caminho oposto: em vez de evitar o tempo físico, torná-lo confiável. Cada data center tem receptores GPS e relógios atômicos, e a API TrueTime não devolve um instante, e sim um intervalo: TT.now() = [earliest, latest], com garantia de conter o tempo verdadeiro, com uma incerteza ε que o artigo relata ser tipicamente de 1–7 ms.

Para tornar as transações externamente consistentes (se T1 confirma antes de T2 começar, o timestamp de T2 é maior), o Spanner usa a espera de commit (commit wait): escolhe o timestamp de commit s = TT.now().latest e então espera até que TT.now().earliest > s antes de tornar o commit visível — isto é, até que s esteja garantidamente no passado em todo lugar.

sequenceDiagram
    participant C as cliente
    participant S as líder do Spanner
    participant TT as TrueTime
    C->>S: commit de T1
    S->>TT: now()
    TT-->>S: [10:00:00.100, 10:00:00.106]
    Note over S: s = .106 (latest), replica via Paxos enquanto isso
    S->>TT: now() até earliest > .106
    TT-->>S: [10:00:00.107, 10:00:00.113]
    S-->>C: confirmado em s = .106
    Note over C,S: qualquer transação posterior recebe s' > .106

O custo da correção é, literalmente, esperar a incerteza passar (em média ~2ε por commit, sobreposto à replicação do Paxos). Um ε menor significa commits mais rápidos, e por isso o Google investe em relógios. A AWS publicou depois uma API open source parecida, a ClockBound, que devolve limites de erro em instâncias EC2.

Ordenação na prática

A maioria dos sistemas nunca implementa relógios vetoriais nem TrueTime. Eles obtêm ordem de fontes mais simples — e vale saber o que cada uma garante:

Um ID Snowflake (Twitter, 2010) empacota em um inteiro de 64 bits um timestamp de 41 bits em milissegundos, um id de máquina de 10 bits e uma sequência de 12 bits por milissegundo — até 4.096 ids por milissegundo por máquina, únicos sem coordenação e aproximadamente ordenáveis por tempo. O UUIDv7 (RFC 9562, 2024)⁷ padroniza a mesma ideia em um UUID de 128 bits com um prefixo de 48 bits em milissegundos Unix: índices B-tree ficam compactos porque as chaves novas são acrescentadas no fim, em vez de espalhadas como os UUIDv4 aleatórios.

// 64-bit id: 41 bits of ms since a custom epoch | 10 bits machine id | 12 bits sequence
final class Snowflake {
    private static final long EPOCH = 1735689600000L;   // 2025-01-01T00:00:00Z
    private final long machineId;                         // 0..1023, assigned per instance
    private long lastMs = -1, seq = 0;

    Snowflake(long machineId) { this.machineId = machineId; }

    synchronized long next() {
        long now = System.currentTimeMillis();
        if (now < lastMs) now = lastMs;                   // clock stepped back: do not go backwards
        if (now == lastMs) {
            seq = (seq + 1) & 0xFFF;                      // 4096 ids per ms
            if (seq == 0) while ((now = System.currentTimeMillis()) <= lastMs) { }  // wait next ms
        } else {
            seq = 0;
        }
        lastMs = now;
        return ((now - EPOCH) << 22) | (machineId << 12) | seq;
    }
}

    var holdId = UUID.randomUUID();
    var expiresAt = OffsetDateTime.now(ZoneOffset.UTC).plus(holdTtl);
@Scheduled(fixedDelay = 5000)
@Transactional
public void expireHolds() {
    int freed = jdbc.sql("""
            WITH expired AS (
                UPDATE inventory.holds SET status = 'EXPIRED'
                WHERE id IN (SELECT id FROM inventory.holds
                             WHERE status = 'ACTIVE' AND expires_at < now()
                             ORDER BY expires_at
                             LIMIT 500
                             FOR UPDATE SKIP LOCKED)
                RETURNING id)
            UPDATE inventory.seats
            SET status = 'AVAILABLE', hold_id = NULL, version = version + 1
            WHERE status = 'HELD' AND hold_id IN (SELECT id FROM expired)""")
            .update();
    if (freed > 0) {
        log.info("expired holds freed {} seats", freed);
    }
}

Como se conecta

flowchart LR
    DRIFT["deriva do relógio<br/>NTP, PTP"] --> LWW["LWW perde escritas"]
    LWW --> VV["vetores de versão, CRDTs<br/>→ Replicação e Consistência"]
    HB["aconteceu-antes"] --> LAM["relógios de Lamport"]
    LAM --> TERMS["termos do Raft, fencing tokens<br/>→ Consenso"]
    HB --> VEC["relógios vetoriais"] --> VV
    DRIFT --> HLC["relógios lógicos híbridos"]
    LAM --> HLC
    DRIFT --> TT["TrueTime<br/>commit wait"]
    HLC --> SNAP["snapshots consistentes<br/>CockroachDB, YugabyteDB"]
    TT --> SNAP
    AUTH["autoridade única<br/>now() do banco, offsets do Kafka"] --> PRAC["ordenação na prática"]
    IDS["Snowflake, UUIDv7"] --> PRAC

Componentes da paleta que fornecem ordem ou tempo: sql (sequences, now() no primário) · kafka (offsets por partição) · scheduler (gatilhos por relógio de parede — cuidado com a defasagem) · cache (expiração por TTL). Continua em: Mensageria — Kafka (ordenação por chave), Estudo de caso: encurtador de URL (ids únicos), Observabilidade (defasagem de relógio em traces).

Pontos-chave