Relógios Lógicos Híbridos: Fazendo o Last-Write-Wins Significar a Escrita Mais Recente

A maior parte do código de resolução de conflitos que já li começa do mesmo jeito: carimba cada escrita com time.Now() e, em caso de empate, mantém o timestamp mais novo. Last-write-wins. Sobrevive à demo. Perde dados na primeira vez em que duas réplicas recebem escritas com poucos milissegundos de diferença e relógios que discordam entre si.

A armadilha é sutil. "Última escrita" soa como se significasse "o evento que aconteceu depois". Com um relógio de parede, significa "o evento do nó com a leitura de relógio mais alta". São frases diferentes, e a distância entre elas é exatamente o desvio de relógio (skew) entre nós. O NTP em hardware comum deixa relógios com dezenas de milissegundos de diferença num dia bom, e minutos de diferença num dia ruim. Então o last-write-wins silenciosamente recompensa qualquer máquina que esteja adiantada, independentemente da ordem causal.

Entrei nesse caminho logo depois de escrever sobre por que uma função de merge de CRDT converge. Aquele post resolveu o problema na camada da estrutura de dados: faça o merge comutativo, associativo e idempotente, e o relógio deixa de importar. Este post resolve o mesmo problema uma camada abaixo, no próprio timestamp. Se eu conseguir fazer o timestamp respeitar a causalidade, o last-write-wins simples volta a ficar correto — e eu consigo manter um único valor comparável em vez de carregar metadados por elemento.

Esse timestamp existe. É o Relógio Lógico Híbrido (Hybrid Logical Clock), formalizado no artigo de 2014 Logical Physical Clocks and Consistent Snapshotting in Globally Distributed Databases de Kulkarni, Demirbas e colegas. Ele também é o padrão silencioso dentro do SQL distribuído moderno: CockroachDB, YugabyteDB e MongoDB todos rodam HLC em vez do TrueTime da Google, baseado em GPS e relógios atômicos. Vale uma olhada nova, já que um dos coautores hoje trabalha com relógios na MongoDB Research e o design continua aparecendo em relatos de produção.

Onde o last-write-wins de relógio de parede descarta a escrita mais recente

Aqui está o entrelaçamento concreto. O relógio físico do nó A marca 1000 ms. O do nó B marca 995 ms — cinco milissegundos atrasado, bem dentro do erro normal do NTP.

Um usuário escreve x = 1 no nó A. A carimba como 1000. A escrita se replica para B. A lógica de aplicação de B reage e escreve x = 2, um sucessor causal estrito: ela só existe porque a escrita de A chegou. B a carimba com seu próprio relógio: 995.

Agora ambas as escritas se encontram num merge. O last-write-wins compara 1000 contra 995 e mantém x = 1. A escrita causalmente posterior — aquela que aconteceu depois e por causa da primeira — perde, porque o cristal de quartzo de B roda ligeiramente devagar. Nenhum erro, nenhuma linha de log. O valor simplesmente está errado, e permanece errado.

A imagem abaixo traça esse entrelaçamento e o que o HLC faz com ele.

​

O que o contador realmente compra

Um timestamp HLC é um par: (l, c). O componente l acompanha o tempo físico — ele fica próximo do relógio de parede. O componente c é um pequeno contador inteiro que desempata quando o tempo físico não consegue. A comparação é lexicográfica: compare l primeiro, depois c.

Duas regras governam como o par se move. Em um evento local, pegue o maior entre o l armazenado e o relógio físico atual. Se l não se moveu (o tempo físico não avançou além dele), incremente o contador. Se l se moveu, zere o contador. Ao receber um timestamp remoto, pegue o maior entre o l armazenado, o l remoto e o relógio físico atual, e então ajuste o contador para que o resultado seja estritamente maior do que ambas as entradas.

Essa regra de recebimento é o jogo inteiro. Quando B processa o (1000, 0) de A enquanto seu próprio relógio marca 995, ele adota l = 1000 — o máximo — e ajusta c = 1. A escrita seguinte de B vira (1000, 1), que ordena estritamente depois de (1000, 0) de A. O sucessor causal vence, mesmo que o relógio de hardware de B nunca tenha alcançado 1000. O contador carregou a ordem que o relógio de parede não conseguiu.

A preocupação não óbvia é o contador disparar sem controle. Se um laço de mensagens movimentado continua empurrando l à frente do tempo físico, será que c cresce sem limite? A versão ingênua do artigo de fato deriva sem limites. O algoritmo HLC não, e a razão é mecânica: toda vez que o tempo físico avança além de l, o contador zera. Os autores provam que c permanece limitado — sob a suposição mínima de que o relógio físico de um nó tica ao menos uma vez entre dois de seus próprios eventos, c < N·(ε + 1), onde ε é o limite de desvio de relógio e N a quantidade de nós. Nos experimentos deles o contador na maior parte ficou em um único dígito. Com 16 bits ele tem folga até 65.536; você precisaria dessa quantidade de eventos dentro de um único tique físico para estourar, o que não acontece na prática.

Esse limite é o que torna a codificação compacta segura. O artigo empacota tudo em 64 bits: 48 bits para l e 16 para c. O CockroachDB usa o mesmo formato. Um int64, uma comparação, e você tem um timestamp que é monotônico por nó e consistente com a causalidade entre nós.

A implementação, em um único arquivo

Aqui está uma versão Go autocontida. O relógio físico é injetado como uma função para que o desvio seja reproduzível em vez de depender do host.

package main

import (
	"fmt"
	"sync"
)

// Clock is a Hybrid Logical Clock. wall is the physical-time component in
// milliseconds; counter breaks ties when wall does not move.
type Clock struct {
	mu      sync.Mutex
	wall    int64
	counter int64
	now     func() int64 // injectable physical clock, in ms
}

func New(now func() int64) *Clock { return &Clock{now: now} }

// Local stamps a local event and returns the new timestamp.
func (c *Clock) Local() (int64, int64) {
	c.mu.Lock()
	defer c.mu.Unlock()
	prev := c.wall
	c.wall = max64(prev, c.now())
	if c.wall == prev {
		c.counter++
	} else {
		c.counter = 0
	}
	return c.wall, c.counter
}

// Receive merges a remote timestamp into this clock and returns the new one.
func (c *Clock) Receive(rWall, rCounter int64) (int64, int64) {
	c.mu.Lock()
	defer c.mu.Unlock()
	prev := c.wall
	c.wall = max64(prev, rWall, c.now())
	switch {
	case c.wall == prev && c.wall == rWall:
		c.counter = max64(c.counter, rCounter) + 1
	case c.wall == prev:
		c.counter++
	case c.wall == rWall:
		c.counter = rCounter + 1
	default:
		c.counter = 0
	}
	return c.wall, c.counter
}

// Pack folds the timestamp into one int64: 48 bits wall, 16 bits counter.
func Pack(wall, counter int64) int64 { return wall<<16 | (counter & 0xFFFF) }

func max64(xs ...int64) int64 {
	m := xs[0]
	for _, x := range xs[1:] {
		if x> m {
			m = x
		}
	}
	return m
}

func main() {
	// Two nodes. Node B's physical clock is stuck 5 ms behind A's.
	clockA := int64(1000)
	clockB := int64(995)
	a := New(func() int64 { return clockA })
	b := New(func() int64 { return clockB })

	// A stamps a write, then sends it to B.
	wA, cA := a.Local()

	// B receives A's write. Its slow wall clock must not lose the ordering.
	wB, cB := b.Receive(wA, cA)
	if Pack(wB, cB) <= Pack(wA, cA) {
		panic("causality lost: B's stamp is not after A's")
	}

	// B stamps a follow-up event without its physical clock advancing.
	w2, c2 := b.Local()
	if Pack(w2, c2) <= Pack(wB, cB) {
		panic("monotonicity lost: counter did not advance")
	}
	if c2 != cB+1 {
		panic("counter should have incremented by exactly one")
	}

	fmt.Printf("A:(%d,%d)  B<-A:(%d,%d)  B next:(%d,%d)\n", wA, cA, wB, cB, w2, c2)
}

Rode com go run hlc.go. Ele imprime:

Algumas linhas carregam o peso. Em Receive, o ramo case c.wall == rWall é a correção do desvio: o relógio físico de B marca 995, então max64(0, 1000, 995) é 1000, que é igual ao l remoto mas não ao l antigo de B, então o contador vira rCounter + 1 = 1. Esse único incremento é o que faz o carimbo de B ordenar depois do de A. O switch de quatro vias parece exagerado, mas cada ramo responde a uma pergunta — l veio do relógio local, do carimbo remoto, de ambos, ou de nenhum — e ajusta o contador para ficar estritamente à frente do que quer que tenha adotado. Pack é a codificação do artigo; deslocar wall 16 bits à esquerda e fazer um or com o contador mascarado dá um único int64 comparável.

Mantenho a comparação fora do tipo do relógio de propósito. A única tarefa do relógio é produzir carimbos monotônicos e causais; decidir qual escrita vence é tarefa da camada de merge, e é apenas Pack(a) < Pack(b).

Para os testes, eu exercito a mesma lógica de três formas: um teste de regressão fixando exatamente o entrelaçamento de desvio acima, um teste de monotonicidade que carimba eventos enquanto o relógio de parede está congelado e verifica se o contador tanto sobe quanto zera quando o relógio avança, e um fuzz com seed que roda cinco mil passos aleatórios de local-ou-receive em três nós com desvio e afirma que os carimbos de cada nó permanecem estritamente crescentes. O fuzz é o que paga o seu lugar — um caso escrito à mão nunca atinge o entrelaçamento que você esqueceu.

O que o HLC não te dá

O HLC ordena eventos. Ele não detecta que dois eventos foram concorrentes. Essa é a mesma limitação dos relógios de Lamport, e ela importa mais do que parece à primeira vista. Se dois nós escrevem de forma independente sem nenhuma mensagem entre eles, o HLC ainda produz dois timestamps comparáveis e o last-write-wins ainda descarta um. A ordem que ele impõe é arbitrária para escritas genuinamente concorrentes — apenas acontece de ser consistente e monotônica, então toda réplica descarta a mesma. Você obtém convergência, não consciência de conflito. Para de fato detectar "essas duas escritas conflitam, exiba ambas", você precisa de vetores de versão ou de um CRDT — que é justamente a razão pela qual a abordagem de função de merge e o HLC resolvem metades diferentes do problema.

O HLC também não faz o desvio de relógio desaparecer. Ele limita e mascara o desvio até ε; além disso, a ordenação quebra. É aqui que mora o custo de produção. O CockroachDB roda HLC com um deslocamento máximo de relógio estático, 500 ms por padrão, e uma transação de leitura carrega um intervalo de incerteza de [ts, ts + max_offset]. Se uma leitura vê um valor carimbado dentro dessa janela, o banco de dados não consegue provar que o valor está no passado em vez de ser um artefato de desvio, então ele reinicia a transação em um timestamp mais alto. Esse reinício é latência real, paga para converter "provavelmente ordenado" em "comprovadamente ordenado". Aperte o deslocamento e você reduz a janela de incerteza mas aumenta o risco de cruzá-la; a própria orientação do CockroachDB trata o padrão de 500 ms como uma margem de segurança, não como um alvo.

E quando o desvio excede o limite, o HLC não disfarça — o sistema se protege em vez disso. Um nó do CockroachDB que detecta seu relógio derivando mais de 80% do deslocamento máximo (400 ms no padrão) em relação a uma maioria dos pares se desliga, em vez de servir leituras possivelmente desordenadas. Essa é a forma honesta do trade-off: o HLC te compra ordenação correta sobre NTP comum desde que os relógios fiquem dentro do limite, e o fallback para violá-lo é um nó morto, não corrupção silenciosa. O MongoDB, que usa HLC para tempo-de-cluster e consistência causal, pende para o outro lado — mais reinícios de transação e esperas mais longas em leituras causais em vez de auto-desligamento.

Quando recorrer a ele

Recorra a um HLC quando você precisar de um único timestamp monotônico e causalmente consistente e não puder arcar com metadados por chave: stores multiversão, leituras de snapshot, registradores last-write-wins onde você quer que a escrita mais recente de fato vença, e ordenação de eventos entre serviços que já trocam mensagens. É O(1) por evento, ele aproveita o NTP que você já roda, e encaixa em qualquer lugar onde você hoje chama time.Now().

Pule ele quando a última escrita realmente for a intenção e um único escritor for dono da chave — um relógio de parede simples está ótimo e é mais barato de raciocinar. Pule ele quando você precisar detectar atualizações concorrentes em vez de ordená-las silenciosamente; isso é território de vetor de versão ou CRDT. E não o trate como substituto de relógios sincronizados: o HLC limita o dano do desvio, ele não elimina o desvio, e o custo de reinício por incerteza escala com o quanto seus relógios se afastam.

Conclusões acionáveis:

• Substitua timestamps de relógio de parede no last-write-wins por um par HLC (l, c); compare lexicograficamente para que a escrita causalmente posterior vença sob desvio.
• Injete o relógio físico atrás de uma interface para poder fixar o desvio e escrever uma regressão determinística mais um fuzz com seed.
• Empacote l e c em um único valor de 64 bits (48 bits / 16 bits) — o limite comprovado do contador torna 16 bits seguros.
• Reserve orçamento para o custo de incerteza: limites de deslocamento de relógio mais apertados significam menos reinícios mas menos folga antes que um nó tenha que se isolar.

Use-o para timestamps causais monotônicos sobre NTP comum. Evite-o quando precisar de detecção de concorrência, quando um único escritor torna o last-write-wins de relógio de parede correto, ou quando estiver tentado a interpretá-lo como uma correção de sincronização de relógio que ele nunca pretendeu ser.