Por que UUIDs praticamente nunca colidem (mesmo sem verificação)

Um UUID aleatório padrão é gerado de forma independente por qualquer quantidade de sistemas totalmente descoordenados, sem nenhuma autoridade central distribuindo o próximo identificador disponível e sem nenhuma verificação contra uma lista de identificadores já em uso — e, apesar disso, colisões são, para efeitos práticos, algo que praticamente nunca acontece. Essa é uma afirmação genuinamente ousada, que se apoia inteiramente em probabilidade em vez de coordenação, e entender por que ela se sustenta exige o mesmo trecho de matemática contraintuitiva que explica um quebra-cabeça muito mais famoso: quão poucas pessoas precisam estar em uma sala antes que seja provável que duas delas compartilhem o mesmo aniversário.

O clássico paradoxo do aniversário pergunta quantas pessoas precisam se reunir em uma sala antes de haver uma chance maior que 50% de que duas delas compartilhem um aniversário, e a resposta — apenas 23 pessoas, contra 365 aniversários possíveis — surpreende a maioria das pessoas, que intuitivamente esperam que o número esteja muito mais perto de 365. O motivo de a resposta real ser tão menor é que a comparação relevante não é "alguma pessoa específica compartilha meu aniversário", mas sim "algum par, entre todos os pares possíveis na sala, compartilha um aniversário" — e o número de pares possíveis cresce muito mais rápido do que o número de pessoas, já que, com 23 pessoas, já existem 253 pares distintos, cada um sendo uma oportunidade independente de coincidência. Esse padrão matemático exato — o número de oportunidades de comparação crescendo de forma quadrática enquanto o número de itens cresce apenas de forma linear — é chamado de problema do aniversário, e se aplica diretamente a qualquer situação envolvendo valores aleatórios tirados de um espaço fixo e verificados quanto a duplicatas, o que inclui perfeitamente os UUIDs.

Um UUID aleatório padrão (versão 4) tira valores de um espaço de 122 bits genuinamente aleatórios — um punhado dos 128 bits totais é fixado pela própria especificação do formato para identificar a versão — o que significa que o número total de valores possíveis é 2 elevado a 122, um número quase incompreensivelmente grande. Aplicando o mesmo raciocínio do paradoxo do aniversário usado no exemplo dos 365 dias, mas em escala para esse espaço muito maior, chega-se ao ponto em que uma colisão se torna provável: seria preciso gerar aproximadamente 2,7 quintilhões de UUIDs antes de a probabilidade de dois colidirem subir para perto de 50% — para efeito de comparação, isso é mais UUIDs do que a quantidade estimada de grãos de areia em todas as praias da Terra. Um único sistema, ou até um grande número de sistemas combinados, gerando UUIDs em qualquer taxa realista do mundo real, levaria um tempo muito maior do que a idade do universo para chegar perto desse limiar, o que é a base matemática real para tratar colisões de UUID como algo que não precisa ser verificado na prática.

O UUID versão 7, padronizado mais recentemente especificamente para produzir identificadores que se ordenam de forma aproximadamente cronológica, consegue isso colocando um timestamp com precisão de milissegundo nos bits iniciais do identificador, em vez de preencher o valor inteiro com dados aleatórios como a versão 4 faz. Isso pode parecer que enfraqueceria a garantia de resistência a colisões, já que parte do valor agora é previsível em vez de aleatória — mas os bits restantes continuam sendo preenchidos com a mesma quantidade de dados genuinamente aleatórios de antes, e como dois UUIDs gerados no mesmíssimo milissegundo ainda precisam que o restante aleatório coincida exatamente para colidir, a resistência prática a colisões continua comparável à da versão 4 para qualquer taxa realista de geração. O que a v7 realmente muda é uma propriedade diferente e sem relação — a ordem de classificação — não a matemática de colisão discutida aqui, e vale a pena manter os dois conceitos separados: a unicidade vem do puro tamanho do espaço aleatório, enquanto a capacidade de ordenação vem de onde o timestamp fica posicionado dentro do valor.

Como a probabilidade de colisão é genuína, não apenas superficialmente, insignificante, os sistemas conseguem gerar identificadores completamente independentes — um aplicativo móvel funcionando offline sem conexão de rede, uma função serverless que sobe e desaparece em milissegundos, mil instâncias paralelas de microsserviço rodando simultaneamente — com zero coordenação entre elas e nenhum registro central acompanhando o que já foi emitido, e ainda assim ter uma expectativa matematicamente sólida de que dois desses identificadores nunca vão colidir. Essa é exatamente a propriedade que um identificador sequencial emitido centralmente nunca poderia oferecer sem uma autoridade coordenadora compartilhada deixando tudo mais lento, e é o motivo completo pelo qual os UUIDs aleatórios se tornaram a escolha padrão para sistemas distribuídos que precisam de identificadores em um ritmo que nenhuma etapa de coordenação conseguiria acompanhar.