2
willybr
2 min de leitura ·

Por que sistemas distribuídos não confiam no relógio (e o que usam no lugar)

Três servidores, no mesmo instante, mostrando três horários diferentes: 10:00:03, 09:59:58 e 10:00:11. Isso é normal. Mesmo com NTP, relógios de máquinas diferentes desviam, não há garantia nenhuma.

Agora imagine um banco que resolve conflitos com "a última escrita vence", usando esse horário. O cliente A grava um registro no servidor 1, que marca 10:00:03. Um segundo depois, o cliente B grava o mesmo registro no servidor 2, que está atrasado e marca 09:59:59. Na reconciliação, a escrita de B perde, mesmo tendo acontecido depois.

Ninguém recebe erro. O dado simplesmente some.

Lamport: ordenar sem relógio

Em 1978, Leslie Lamport trocou a pergunta "que horas são?" por "o que aconteceu antes do quê?". Cada processo mantém um contador:

evento local:        c = c + 1
enviar mensagem:     c = c + 1, e envia c junto
receber mensagem m:  c = max(c, m.c) + 1

Com isso, se A causou B, então L(A) < L(B). O problema é a volta: L(A) < L(B) não significa que A causou B. Dois eventos sem relação nenhuma também recebem números diferentes, e você não consegue saber se eles foram concorrentes.

Vector clocks: detectar concorrência

A saída é cada nó guardar um contador para cada nó do sistema. Para comparar dois eventos, compara-se posição a posição:

A = [2, 1, 0]
B = [2, 2, 0]   A aconteceu antes de B (todas as posições <=, pelo menos uma <)
C = [3, 0, 0]   B e C são concorrentes (nenhum domina o outro)

Agora o sistema sabe quando duas escritas conflitam de verdade e pode guardar as duas versões ou deixar a aplicação decidir. O custo é que o vetor cresce junto com o número de nós.

Daqui pra frente

É desse custo, e de outras limitações, que saem as variações usadas em produção:

  • Hybrid Logical Clocks, que juntam tempo físico com um contador lógico (CockroachDB e YugabyteDB usam)
  • Version Vectors e Dotted Version Vectors, o que roda dentro de KV stores leaderless como o Riak
  • Matrix Clocks e Bloom Clocks, para quando há milhares de nós e o vetor não cabe mais

O deep dive

Na segunda-feira, 19/10, das 20h às 21h30 (horário de Brasília), o Edward Ribeiro vai percorrer esse caminho inteiro, de Lamport a Bloom Clocks, com exemplos de sistemas reais e os trade-offs de cada abordagem. É o primeiro de dois encontros. O segundo será sobre CRDTs e Operational Transformation.

O evento é online e aberto a qualquer pessoa, organizado pelo Craft & Code Club, uma comunidade de devs que estuda sistemas distribuídos, algoritmos e livros técnicos em grupo.

Se você já usou algum desses relógios em produção, ou já perdeu dado por causa de "última escrita vence", conta aqui nos comentários. Casos reais vão enriquecer a conversa.

Carregando publicação patrocinada...