É seguro assumir que um GUID sempre será único?

123

Eu sei que há uma possibilidade minuciosa de um conflito, mas se eu gerasse um lote de 1000 GUIDs (por exemplo), seria seguro assumir que todos são únicos para salvar os testes de cada um?

Pergunta bônus

Uma maneira ideal de testar um GUID quanto à exclusividade? Filtro Bloom talvez?

Tom Savage
fonte
2
possível duplicação de Um GUID é exclusivo 100% do tempo?
ChrisF
29
Não se todos nós manter esmagou o botão de recarga on this site: wasteaguid.info
mipadi
12
Eu culpo todos os meus erros por colisões GUID. Tem que acontecer algum tempo, certo?
Michael
8
É muito mais provável que um tubarão com uma linda coloração com padrão xadrez caia do céu e esmague seu computador em pedaços, então eu afirmaria que tomar precauções contra isso é uma alocação de recursos mais apropriada como parte de sua redução geral de riscos plano.
David Gladfelter
4
@ mipadi: ótimo link! Eu posso imaginar algum desenvolvedor em algum lugar reclamando "Guuuuys! Pare de desperdiçar os GUIDs! Eu preciso deles!"
FrustratedWithFormsDesigner

Respostas:

360

Sim você pode. Como os GUIDs têm 128 bits de comprimento, existe uma possibilidade minúscula de um conflito - mas a palavra "minuto" não é nem de longe forte o suficiente. Existem tantos GUIDs que, se você gerar vários trilhões deles aleatoriamente, é mais provável que seja atingido por um meteorito do que ter uma colisão (da Wikipedia ). E se você não os estiver gerando aleatoriamente, mas estiver usando, por exemplo, o algoritmo de endereço MAC e carimbo de data e hora, eles também serão únicos, pois os endereços MAC são únicos entre os computadores e os carimbos de hora são exclusivos no seu computador . computador.

Editar 1: para responder à sua pergunta sobre bônus, a maneira ideal de testar um conjunto de GUIDs quanto à exclusividade é apenas assumir que todos eles são únicos. Por quê? Porque, dado o número de GUIDs que você está gerando, as chances de uma colisão com GUID são menores do que as chances de um raio cósmico inverter um pouco na memória do computador e estragar a resposta dada por qualquer algoritmo "preciso" que você gostaria para correr. (Veja esta resposta StackOverflow para a matemática.)

Há um número enorme de GUIDs por aí. Para citar o Guia do Mochileiro das Galáxias de Douglas Adams :

"O espaço", diz, "é grande. Realmente grande. Você simplesmente não vai acreditar no quão imensamente grande é. Quero dizer, você pode pensar que é um longo caminho até o químico, mas isso é apenas um amendoim para o espaço" , ouço…"

E como existem cerca de 7 × 10 22 estrelas no universo e pouco menos de 2 128 GUIDs, existem aproximadamente 4,86 ​​× 10 15 - quase cinco quatrilhões - de GUIDs para cada estrela. Se cada uma dessas estrelas tivesse um mundo com uma população próspera como a nossa, então, ao redor de todas as estrelas, todos os humanos ou alienígenas que já viveram teriam direito a mais de 45 mil GUIDs. Para todas as pessoas na história, em todas as estrelas do universo. O espaço da GUID está no mesmo nível de abrangência que o tamanho de todo o universo. Você não precisa se preocupar.

( Edit 2: Refletindo sobre isto: wow eu não tinha percebido. Mim mesmo que isso significava O espaço GUID é incompreensivelmente maciça Eu sou uma espécie de no temor dele...)

Antal Spector-Zabusky
fonte
1
Além disso, o WolframAlpha relata que, para todas as células de todas as pessoas que já viveram, existem 36 trilhões de UUIDs. Você tem 10^14células em seu corpo e 106,5 bilhões de pessoas já viveram. Ou, 2.385 * 10^23UUIDs para cada centavo na dívida pública dos EUA.
precisa saber é o seguinte
5
Embora os números ainda sejam altos, as chances de uma colisão com GUID são superiores a 50% em 2 ^ 64 GUIDs.
NullUserException 22/10/12
1
Em 2 ^ 64 GUIDs, isso reduziria os números para menos de um (0,00026) por estrela no Universo e 2 * 10 ^ (- 15) para cada humano ou alienígena que já viveu. Isso ainda permitiria mais de 170 milhões de GUIDs para todos os humanos que já viveram, então acho que ainda somos bons.
NullUserException 23/10/12
12
Vale ressaltar que uma colisão de GUID também é apenas um problema se estiver no mesmo espaço de negócios. A GUID eu uso para identificar um componente em um pedaço de software poderia ser o mesmo que um GUID que você usa em uma fila de banco de dados em seu próprio aplicativo sem causar quaisquer problemas
James Thorpe
1
O fato de que existem 2 ^ 128 GUIDS é irrelevante, e você não é "ainda bem" em 50% de chance de colisão, você não está mesmo bom em 0,0000001%
BlackTigerX
40

Resposta curta: para fins práticos, sim.

No entanto, você deve considerar o paradoxo do aniversário!

Eu calculei algumas probabilidades de colisão representativas. Com UUIDs de 122 bits, conforme especificado no artigo da Wikipedia , a probabilidade de colisão é 1/2 se você gerar pelo menos 2.71492e18UUIDs. Com 10 ^ 19 UUIDs, a probabilidade é 0,999918. Com 10 ^ 17 UUIDs, 0.000939953.

Alguns números para comparação podem ser encontrados na Wikipedia. Assim, você pode atribuir com segurança um UUID para cada humano que viveu, cada galáxia no universo observável, cada peixe no oceano e cada formiga individual na Terra. No entanto , as colisões são quase certas se você gerar um UUID para cada transistor que a humanidade produz em um ano, cada inseto na Terra, cada grão de areia na Terra, cada estrela no universo observável ou qualquer coisa maior.

Se você gerar 1 bilhão de UUIDs por segundo, levaria cerca de 36 anos para obter uma probabilidade de colisão de 10%.

Eventualmente, provavelmente haverá uma colisão entre o conjunto de UUIDs gerados ao longo da história humana. Ainda assim, a probabilidade de que UUIDs colididos sejam usados ​​para o mesmo objetivo é muito pequena, portanto não há problema na prática.

Caracol mecânico
fonte
13
Isto é como as extremidades do universo ... Alguns programador apenas assume suas GUIDs sempre será único para o seu mega-Estrela da Morte ...
pkr298
Como os UUIDs são baseados em dados não aleatórios, 36 anos são - você só precisa se preocupar com cada milissegundo individualmente.
Mjaggard 14/0518
Os UUIDs @mjaggard são baseados em dados aleatórios. Qualquer tipo moderno, pelo menos.
Trejkaz
8

Uma análise da possibilidade de colisão está disponível na Wikipedia: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Conforme mencionado no link, isso será afetado pelas propriedades do gerador de números aleatórios.

Há também a possibilidade de um bug no código do gerador GUID; embora as chances sejam baixas, elas provavelmente são maiores do que as chances de uma colisão com base na matemática.

Um filtro Bloom pode ser apropriado; pode dizer rapidamente se um GUID é único, mas há uma chance de uma falsa indicação de uma colisão. Um método alternativo se você estiver testando um lote de cada vez é classificar o lote e comparar cada elemento sucessivo.

Mark Ransom
fonte
5

Em geral, sim, é seguro assumir.

Se o seu gerador de GUID for realmente aleatório, as possibilidades de um conflito em 1000 GUIDs são extraordinariamente pequenas.

Obviamente, isso pressupõe um bom gerador de GUID. Portanto, a questão é realmente quanto você confia na ferramenta que está usando para gerar GUID e ela tem seus próprios testes?

Haacked
fonte
0

Embora uma colisão seja possível, é ALTAMENTE improvável. (Matemática aqui .) É seguro assumir que eles são de fato distintos.

VeeArr
fonte