Colisões de timestamps em nanossegundos são comuns

• Em sistemas modernos, onde vários núcleos físicos leem o relógio ao mesmo tempo, até timestamps em nanossegundos se sobrepõem facilmente, e em medições simultâneas em 4 núcleos físicos cerca de 5% de todas as amostras colidem
• Projetos que usam timestamps brutos como identificadores únicos são arriscados, e a frequência de colisões varia conforme o sistema operacional e a forma de execução
• O time.Now() do Go registra tanto o tempo absoluto quanto o tempo relativo com base em um relógio monotônico, permitindo verificar separadamente a diferença entre chamadas consecutivas e a duplicação de timestamps absolutos
• No Linux com thread única, o tempo sempre aumentou e o menor incremento observado foi de 32ns, mas quando as threads são separadas, o mesmo tempo absoluto é observado
• No Mac OS X, o tempo absoluto tem resolução de microssegundos, então há muito mais colisões, e mesmo em thread única é frequente observar casos em que o relógio monotônico não aumenta

---

Frequência de colisões revelada em leituras simultâneas

• A pergunta central é com que frequência colisões de timestamps em nanossegundos realmente acontecem em sistemas modernos
• Ao ler o relógio simultaneamente em 4 núcleos físicos, cerca de 5% de todas as amostras colidem
• Mesmo usando apenas 2 threads em um sistema de 4 núcleos, cerca de 2% dos timestamps se sobrepõem
• Portanto, assumir que apenas timestamps brutos em nanossegundos podem gerar IDs únicos não é seguro

Método de teste e diferenças por sistema operacional

• O programa de teste foi escrito em Go
• O time.Now() do Go registra, a cada chamada, o tempo absoluto e o tempo relativo com base em um relógio monotônico
  • O teste compara a diferença relativa entre timestamps consecutivos
  • A duplicação dos próprios timestamps absolutos também é verificada

• Linux

  • Em thread única, o tempo absoluto e o monotônico sempre aumentam
  • O menor incremento observado no sistema medido foi de 32ns
  • Entre threads, cerca de 5% dos casos apresentam tempo absoluto exatamente igual ao de outra thread

• Mac OS X

  • Como o tempo absoluto tem resolução de microssegundos, no mesmo teste ocorrem muitas colisões
  • Mesmo em thread única, foi observado com frequência que o relógio monotônico não aumenta

[GN⁺]

Comentários do Hacker News

• Uma forma de evitar esse tipo de problema é usar IDs com componente de tempo e número sequencial juntos
  Por exemplo, o UUIDv7 tem um componente de tempo em milissegundos, um campo que aumenta para cada evento dentro do mesmo milissegundo e também bits aleatórios suficientes para tornar astronomicamente baixa a chance de colisão entre IDs gerados em máquinas diferentes
  Claro, como o número de bits é finito, o sequencial pode estourar se houver eventos demais no mesmo intervalo de tempo, colisões entre máquinas podem realmente acontecer e a operação de incremento pode exigir sincronização da CPU, limitando a taxa de geração de eventos
  Mesmo assim, em escala prática, o UUIDv7 funciona muito bem

  • Meio por acaso, me sinto como um viajante do tempo: lembro de uma conversa de uns 10 anos atrás, em um encontro técnico, sobre alguém gerando mais de 1000 UUIDs por milissegundo, sofrendo com problemas de unicidade e insatisfeito com as opções disponíveis na época
    Não consigo encontrar direito na internet há quanto tempo o UUIDv7 existe
  • Não entendo por que o componente de tempo seria necessário para começar
    Ele só consome bits dentro do UUID e praticamente não contribui para a entropia
  • Também combina bem com a ordem de classificação em bancos de dados populares como PostgreSQL
    Ainda não faz parte do núcleo, mas existem várias excelentes extensões de pg que oferecem uuidv7, além de usá-lo diretamente no nível da aplicação
  • O problema do UUID é que ele é totalmente difícil de ler
    Vai além de ser difícil de entender; é muito complicado até distinguir visualmente um do outro
    Por isso, em alguns casos, um identificador sem nenhuma informação ou ruído além do mínimo necessário pode ser útil
  • Dependendo do caso de uso, nem é preciso tratar a situação de “mesmo milissegundo”, o que economiza alguns ciclos
    Em geral, um contador incremental que pode estourar, em qualquer formato, junto com alguns bits aleatórios já basta, e se for bem implementado, ambos podem ser feitos sem desvios

• Relacionado a isso, eu era gerente de programa responsável pelo log de eventos de segurança do Windows
  Quando as coisas acontecem ao mesmo tempo ou em momentos muito próximos em sistemas multicore, o escalonamento de threads pode afetar fortemente o que é observado
  Por exemplo, o quantum da thread pode acabar antes de ela chegar à chamada de sistema que obtém o timestamp, ou antes de passar o buffer para enfileirar o evento e marcar o timestamp depois
  De fato, em sistemas multiprocessados do Windows nos anos 2000, era muito comum que entradas do log de eventos parecessem fora de ordem, e também não dava para confiar demais na precisão dos timestamps do log
  O limite inferior seguro era, na prática, 1 segundo, e lembro que alguns componentes truncavam ou arredondavam os timestamps

• Se você precisa de um identificador único, basta usar um UUID versão 4, ou seja, um UUID aleatório
  A probabilidade de colisão é parecida com a chance de um dinossauro adulto aparecer de repente no seu quarto por causa de flutuações quânticas

  • Eu aceito esse risco
    Falando mais sério, se der para usar, um valor incremental tradicional provavelmente é o melhor
    É rápido e barato, especialmente em bancos de dados, mas há problemas de privacidade e segurança porque dá para inferir informações a partir do valor do ID
    Nesses casos, ou ao lidar com sistemas distribuídos, UUID é melhor
  • O v7 parece melhor porque resolve o problema de localidade do v4 e, ainda assim, a chance de ganhar na loteria é muito maior do que a de gerar uma colisão
  • Eu queria ver como seria o cálculo da “chance de um dinossauro aparecer de repente no quarto”
  • Então isso significa que a probabilidade de algo ruim acontecer dobrou mais ou menos, e eu não posso aceitar isso

• Mesmo que a resolução seja de nanossegundos, fico curioso sobre qual é a precisão real do relógio do computador
  É difícil imaginar que seja realmente em nível de nanossegundos, e isso me lembra das vezes em que eu insistia para os alunos, nas aulas de laboratório de física, que o menor número mostrado por um instrumento não é a mesma coisa que sua exatidão

  • Se for um dispositivo operando acima de 1GHz, é perfeitamente possível que o relógio incremente a cada nanossegundo
    Mas isso não significa que ele seja exato nesse nível, e em sistemas multicore os relógios entre os núcleos podem não estar sincronizados nesse grau
    O ARMv8 garante que o relógio incremente no mínimo a 1GHz, mas no Intel e em ARMs anteriores a situação é mais complicada
  • Na prática, é nanossegundo mesmo

• A BEAM VM de Erlang/Elixir expõe essa diferença de forma muito clara. É a distinção entre monotonicamente crescente e estritamente monotonicamente crescente
  https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
  “Em uma sequência de valores monotonicamente crescentes, todo valor que tem um valor anterior é maior ou igual a esse valor anterior”
  Isso pode ser usado pela função https://www.erlang.org/doc/man/erlang.html#monotonic_time-0
  https://www.erlang.org/doc/apps/erts/time_correction.html#st...
  “Em uma sequência de valores estritamente monotonicamente crescentes, todo valor que tem um valor anterior é maior que esse valor anterior”
  Valores estritamente monotônicos implicam algum tipo de sincronização ou coordenação, e isso traz custo de desempenho quando há muitos processos simultâneos
  Esse recurso é fornecido pela função https://www.erlang.org/doc/man/erlang.html#unique_integer-1, e a documentação também alerta que valores estritamente monotonicamente crescentes são inerentemente caros de gerar e não escalam bem, então o modificador monotonic só deve ser passado quando for realmente necessário

  • Até os próprios valores de referência do Erlang não são criados com um gerador global estritamente monotônico, mas internamente consistem em um par formado por um identificador monotônico comum e o PID do processo solicitante
    Em outras palavras, é algo parecido com UUIDv1 ou https://en.wikipedia.org/wiki/Snowflake_ID
    Ou seja, identificadores globais estritamente monotônicos só são realmente necessários quando se precisa de um vencedor de primeira/última gravação imediatamente consistente
    Em vez disso, se for possível usar um vencedor de primeira/última gravação eventualmente consistente, por exemplo quando eventos de escrita entram em um event store ou fila onde são linearizados por ID e, entre escritas “concorrentes”, apenas a de maior prioridade de ID é mantida enquanto as outras podem ser descartadas durante o processamento ou na leitura, eu consideraria primeiro um par compactado (nodeID, seq)
    Se for preciso ordenação global de eventos, vale considerar especialmente algo no formato Snowflake ID: (timestampMajor, nodeID, timestampMinor, seq)

• No FreeBSD não existe CLOCK_MONOTONIC_RAW, então com isso comentado parece estar tudo bem
  Eu tinha entendido que, se houvesse colisões, alguns timestamps deveriam se repetir, mas não consigo produzir colisões
  clock_getres(CLOCK_REALTIME, ...)=1 ns, clock_getres(CLOCK_MONOTONIC, ...)=1 ns, e mesmo em 30 amostras a diferença continuou aumentando na faixa aproximada de 29~71ns

  • O importante é se foi executado simultaneamente em 4 núcleos, como o autor fez

• No fim das contas, em algum momento isso não desce para uma questão de arquitetura de conjunto de instruções?
  Uma CPU rodando a 3GHz obtém 3 ciclos de clock por nanossegundo
  Parece bem possível que, com otimização do compilador, chamadas em assembly para ler o registrador de relógio acabem ficando coladas uma na outra
  Se chamadas consecutivas a time.Now() acontecerem dentro de 3 ciclos de clock, não sei se é justo esperar precisão de nanossegundo realmente única

  • No x86_64 do Linux usa-se RDTSC e o valor é corrigido com o que foi lido do VDSO, então isso pode de fato acontecer muito rápido
  • Mesmo em chips modernos, ler um registrador contador de ciclos ainda leva algo como 20 ciclos
    Mesmo que colisões sejam relativamente raras, acontecer algumas vezes por dia é muito pior do que “quase nunca acontece”

• Isso me lembrou a lenda sobre o Lotus Notes
  Dizem que antigamente ele usava timestamps com resolução de 1 segundo como IDs únicos
  Quando havia colisão, simplesmente somava-se 1 segundo, e no fim as colisões ficaram tão frequentes que os itens passaram a ter horários no futuro

• Tempo absolutamente preciso é uma questão de segurança
  Projetistas de CPU introduzem jitter de relógio intencionalmente há muito tempo, desde a época do Alpha da DEC, para impedir previsibilidade total
  No x86 também, se você executar 3 ou 4 vezes, salvar os valores em registradores e só olhar depois que terminar, provavelmente verá que as diferenças de tempo não são exatamente iguais

  • Fico curioso se existe alguma fonte para isso
    Não estou encontrando muita coisa, mas se isso inclui até os primeiros x86, é surpreendente que o problema de segurança de relógios precisos já fosse reconhecido tão cedo
    Pessoalmente, acho que antes deste milênio eu não saberia desse problema, e teria suposto que o jitter de relógio observado seria explicado por algo como interrupções
    Não quer dizer que esteja errado; só queria saber mais

• Já vi gente demais surpresa com colisões de timestamps em milissegundos ou microssegundos
  O tipo mais memorável e mais odiado para mim é o de montar um timestamp com duas chamadas de sistema
  Uma chamada pega os dígitos mais altos e a outra os mais baixos; por causa de preempção do processo, se os dígitos altos forem lidos antes e os dígitos baixos passarem de 99x para 00x, é possível criar um timestamp anterior ao instante que realmente causou a criação daquela entidade
  Aí alguns códigos quebram de forma bem espetacular, e pelo menos duas vezes eu vi loop infinito
  Se você não decorar que isso deve ser sempre evitado, os testes passam em 99,5% das vezes, e aí precisa aparecer alguém com excelente faro para padrões e notar que “o mesmo teste ficou vermelho uma vez por semana durante um mês e meio”
  É tempo demais para uma bomba lógica sobreviver dentro de código de CI/CD antes de ser corrigida

  • O exemplo mais memorável foi num atendimento de suporte em que eu disse “parece haver uma condição de corrida”, e a resposta foi: “esses dois eventos aconteceram exatamente no mesmo instante, então não pode ser uma condição de corrida”