Quão bom é o UUID.randomUUID do Java?

Eu sei que UUIDs randomizados têm uma probabilidade muito, muito, muito baixa de colisão na teoria, mas estou me perguntando, na prática, quão bom randomUUID()é o Java em termos de não ter colisão? Alguém tem alguma experiência para compartilhar?

Usos de UUID java.security.SecureRandom, que deveriam ser "criptograficamente fortes". Embora a implementação real não seja especificada e possa variar entre JVMs (o que significa que quaisquer declarações concretas feitas são válidas apenas para uma JVM específica), ela exige que a saída seja aprovada em um teste estatístico de gerador de números aleatórios.

É sempre possível que uma implementação contenha erros sutis que arruinam tudo isso (consulte o bug de geração de chaves do OpenSSH), mas não acho que exista qualquer razão concreta para se preocupar com a aleatoriedade do Java UUIDs.

A Wikipedia tem uma resposta muito boa http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

o número de UUIDs da versão aleatória 4 que precisam ser gerados para ter uma probabilidade de 50% de pelo menos uma colisão é de 2,71 quintilhões, calculado da seguinte forma:

...

Esse número equivale a gerar 1 bilhão de UUIDs por segundo por cerca de 85 anos, e um arquivo contendo muitos UUIDs, com 16 bytes por UUID, seria cerca de 45 exabytes, muitas vezes maior que os maiores bancos de dados existentes atualmente, que estão em a ordem de centenas de petabytes.

...

Portanto, para que haja uma chance em um bilhão de duplicação, 103 U $ 3 trilhões de UUIDs da versão 4 devem ser gerados.

Alguém tem alguma experiência para compartilhar?

Existem 2^122valores possíveis para um UUID do tipo 4. (A especificação diz que você perde 2 bits para o tipo e mais 4 bits para um número de versão.)

Supondo que você gerasse 1 milhão de UUIDs aleatórios por segundo, as chances de uma duplicação ocorrerem durante a sua vida seriam muito pequenas. E para detectar a duplicata, você teria que resolver o problema de comparar 1 milhão de novos UUIDs por segundo com todos os UUIDs que você gerou anteriormente ¹ !

As chances de alguém ter experimentado (ou seja, de fato notado ) uma duplicata na vida real são ainda menores do que as surpreendentemente pequenas ... devido à dificuldade prática de procurar colisões.

Agora, é claro, você normalmente estará usando um gerador de números pseudo-aleatórios, não uma fonte de números verdadeiramente aleatórios. Mas acho que podemos ter certeza de que, se você estiver usando um provedor confiável para seus números aleatórios de força criptográfica, será uma força criptográfica, e a probabilidade de repetições será a mesma que para um gerador de números aleatórios ideal (não tendencioso) .

No entanto, se você usar uma JVM com um gerador de números cripto-aleatórios "quebrado", todas as apostas serão desativadas. (E isso pode incluir algumas das soluções alternativas para problemas de "falta de entropia" em alguns sistemas. Ou a possibilidade de alguém ter mexido com o seu JRE, no seu sistema ou no upstream.)

^{1 - Supondo que você tenha usado "algum tipo de btree binário", como proposto por um comentarista anônimo, cada UUID precisará de O(NlogN)bits de memória RAM para representar NUUIDs distintos, assumindo baixa densidade e distribuição aleatória dos bits. Agora multiplique isso por 1.000.000 e o número de segundos pelos quais você executará o experimento. Não acho que seja prático pelo tempo necessário para testar colisões de um RNG de alta qualidade. Nem mesmo com representações inteligentes (hipotéticas).}

Eu não sou um especialista, mas eu diria que pessoas inteligentes o suficiente olharam para o gerador de números aleatórios do Java ao longo dos anos. Portanto, eu também consideraria que UUIDs aleatórios são bons. Portanto, você realmente deve ter a probabilidade de colisão teórica (que é de cerca de 1: 3 × 10 ^ 38 para todos os UUIDs possíveis. Alguém sabe como isso muda apenas para UUIDs aleatórios? É isso 1/(16*4)?)

Pela minha experiência prática, nunca vi colisões até agora. Provavelmente terei uma barba surpreendentemente longa no dia em que receber minha primeira;)

Em um ex-empregador, tínhamos uma coluna única que continha um uuid aleatório. Tivemos uma colisão na primeira semana após a implantação. Claro, as chances são baixas, mas não são zero. É por isso que o Log4j 2 contém UuidUtil.getTimeBasedUuid. Ele gerará um UUID exclusivo por 8.925 anos, desde que você não gere mais de 10.000 UUIDs / milissegundo em um único servidor.

O esquema de geração original para UUIDs era concatenar a versão UUID com o endereço MAC do computador que está gerando o UUID e com o número de intervalos de 100 nanossegundos desde a adoção do calendário gregoriano no Ocidente. Ao representar um único ponto no espaço (o computador) e no tempo (o número de intervalos), a chance de uma colisão nos valores é efetivamente nula.

Muitas das respostas discutem quantos UUIDs teriam que ser gerados para atingir 50% de chance de uma colisão. Mas uma chance de colisão de 50%, 25% ou até 1% não vale nada para um aplicativo em que a colisão deve ser (virtualmente) impossível.

Os programadores rotineiramente descartam como "impossíveis" outros eventos que podem e ocorrem?

Quando gravamos dados em um disco ou memória e os lemos novamente, assumimos que os dados estão corretos. Contamos com a correção de erros do dispositivo para detectar qualquer corrupção. Mas a chance de erros não detectados é de 2 a ⁵⁰ .

Não faria sentido aplicar um padrão semelhante a UUIDs aleatórios? Se o fizer, verá que uma colisão "impossível" é possível em uma coleção de cerca de 100 bilhões de UUIDs aleatórios (2 ^36,5 ).

Esse é um número astronômico, mas aplicações como cobrança detalhada em um sistema nacional de saúde ou registro de dados de sensores de alta frequência em uma grande variedade de dispositivos podem definitivamente atingir esses limites. Se você estiver escrevendo o próximo Guia do Mochileiro das Galáxias, não tente atribuir UUIDs a cada artigo!

Como a maioria das respostas se concentrou na teoria, acho que posso acrescentar algo à discussão dando um teste prático que fiz. No meu banco de dados, tenho cerca de 4,5 milhões de UUIDs gerados usando o Java 8 UUID.randomUUID (). Os seguintes são apenas alguns que eu descobri:

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

c0f55f62 -4979-4e87-8cd9-1c556894e2bb

b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64

4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

Se fosse realmente aleatório, a probabilidade de ter esse tipo de UUIDs semelhantes seria consideravelmente baixa (veja editar), já que estamos considerando apenas 4,5 milhões de entradas. Portanto, embora essa função seja boa, em termos de não ter colisões, para mim não parece tão bom quanto seria em teoria.

Editar :

Muitas pessoas parecem não entender essa resposta, então vou esclarecer meu argumento: sei que as semelhanças são "pequenas" e estão longe de ser uma colisão completa. No entanto, eu só queria comparar o UUID.randomUUID () do Java com um verdadeiro gerador de números aleatórios, que é a questão real.

Em um gerador de números aleatórios verdadeiro, a probabilidade de ocorrência do último caso seria em torno de 0,007%. Portanto, acho que minha conclusão permanece.

A fórmula é explicada neste artigo da wiki en.wikipedia.org/wiki/Birthday_problem

Eu jogo na loteria no ano passado e nunca ganhei ... mas parece que a loteria tem vencedores ...

doc: http://tools.ietf.org/html/rfc4122

Tipo 1: não implementado. colisão é possível se o uuid for gerado no mesmo momento. O impl pode ser sincronizado artificialmente para contornar esse problema.

Tipo 2: nunca vê uma implementação.

Tipo 3: md5 hash: possível colisão (128 bits-2 bytes técnicos)

Tipo 4: aleatório: possível colisão (como loteria). observe que o implemento jdk6 não usa um aleatório seguro "verdadeiro" porque o algoritmo PRNG não é escolhido pelo desenvolvedor e você pode forçar o sistema a usar um PRNG "ruim". Portanto, seu UUID é previsível.

Tipo 5: sha1 hash: não implementado: é possível colisão (160 bits-2 bytes técnicos)

Temos usado o UUID aleatório do Java em nosso aplicativo há mais de um ano e isso muito extensivamente. Mas nunca encontramos uma colisão.