Conceitos
Relógios, skew e tempo monotônico
Intuição
Imagine dois colegas em escritórios diferentes, cada um com um relógio de parede acertado à mão: os dois nunca marcam exatamente a mesma hora, e de vez em quando alguém reajusta o seu, às vezes até para trás. Se cada um anota 'terminei às 10h03' num bilhete, comparar os bilhetes para saber quem terminou primeiro é pouco confiável, e como o relógio pode voltar, nem medir quanto uma tarefa levou é seguro. Para medir duração, use um cronômetro que só anda para frente, que não serve para comparar escritórios; para ordenar os bilhetes, numere os passos na ordem em que um influenciou o outro ('meu bilhete vem depois do que eu li') ou admita 'foi entre 10h02 e 10h04' e espere a dúvida passar antes de afirmar qualquer ordem.
Como funciona
Cada máquina tem seu relógio de parede, que diverge dos demais (skew, por causa da deriva) e é corrigido por sincronização, o que pode fazê-lo saltar para trás; já um relógio monotônico só avança, serve para medir durações e timeouts na mesma máquina, mas seus valores não são comparáveis entre máquinas. Lamport parte do fato de que, em um sistema distribuído, o atraso das mensagens não é desprezível em relação ao tempo entre eventos e os relógios físicos não são perfeitamente precisos; por isso define a relação happened-before como a menor relação que satisfaz três condições (eventos no mesmo processo seguem a ordem de execução; o envio de uma mensagem precede o seu recebimento; e a transitividade), o que dá só uma ordem parcial em que eventos sem caminho causal entre si são concorrentes. O relógio lógico implementa essa ordem com um contador por processo: ele é incrementado a cada evento, enviado junto com a mensagem, e o destinatário ajusta o seu para um valor maior que o recebido e não menor que o atual (em implementações comuns, o maior dos dois mais um), com desempate por uma ordem arbitrária fixa entre os processos (por exemplo, o identificador) para formar uma ordem total. A condição vale em um só sentido: se A aconteceu antes de B, o timestamp de A é menor, mas um timestamp menor não prova que A aconteceu antes de B; além disso, a ordem não enxerga causalidade que passe por um canal externo e pode contradizer a ordem que os usuários percebem, o que o paper chama de comportamento anômalo. O Spanner segue o outro caminho e expõe a incerteza do relógio físico com a API TrueTime, em que TT.now() devolve um intervalo [earliest, latest] garantido de conter o tempo absoluto; a hora de referência vem de time masters com GPS e relógios atômicos, que um daemon consulta periodicamente (a cada 30 segundos, com deriva aplicada de 200 microssegundos por segundo, valores da época do paper); entre consultas, a deriva aplicada faz a incerteza crescer de 0 a cerca de 6 ms, o atraso de comunicação até os time masters soma mais cerca de 1 ms, e em produção variava tipicamente em dente de serra entre cerca de 1 e 7 ms, com média de cerca de 4 ms na maior parte do tempo. Para garantir consistência externa (se T1 faz commit antes de T2 começar, o timestamp de T1 é menor), o coordenador escolhe um timestamp de commit não menor que TT.now().latest, calculado depois que o pedido de commit chega a ele (regra Start) e só libera os dados da transação quando TT.after(timestamp) é verdadeiro (Commit Wait). Se a incerteza cresce, o Spanner apenas espera mais: fica mais lento, mas continua correto enquanto o limite de incerteza anunciado pelo TrueTime for válido.
Na prática
Para medir duração, definir timeouts ou controlar quanto tempo algo demorou, use o relógio monotônico da própria máquina, porque o relógio de parede pode saltar após uma sincronização. Para decidir a ordem de eventos entre máquinas, não confie na hora de parede de nós diferentes: quando basta respeitar causalidade, use contadores lógicos no estilo de Lamport, lembrando que um timestamp menor não prova que um evento veio antes do outro, pois os dois podem ser concorrentes. Quando a ordem precisa respeitar o tempo real visto de fora, como em transações com consistência externa, é preciso limitar a incerteza do relógio e pagar a espera no commit, como faz o Spanner com o TrueTime.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.