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

Eu sei que há uma possibilidade minúscula de um conflito, mas se eu gerar um lote de 1000 GUIDs (por exemplo), seria seguro assumir que todos eles são exclusivos para salvar o teste de cada um?

Pergunta bônus

Uma maneira ideal de testar um GUID para exclusividade? Filtro de flores, talvez?

Sim você pode. Como os GUIDs têm 128 bits, há reconhecidamente uma possibilidade minúscula de um conflito – mas a palavra “minuto” está longe de ser forte o suficiente. Existem tantos GUIDs que se você gerar vários trilhões deles aleatoriamente, você ainda terá mais chances de ser atingido por um meteorito do que ter uma só colisão (da Wikipedia ). E se você não os estiver gerando aleatoriamente, mas usando, por exemplo, o algoritmo de endereço MAC e carimbo de data e hora, eles também serão únicos, já que os endereços MAC são únicos entre os computadores e os registros de data e hora são exclusivos em seu computador . computador.

Editar 1: Para responder à sua pergunta de bônus, a melhor maneira de testar um conjunto de GUIDs para exclusividade é apenas assumir que eles são todos únicos. Por quê? Porque, dado o número de GUIDs que você está gerando, as chances de uma colisão GUID são menores do que as chances de um raio cósmico virar um pouco na memory do seu computador e estragar a resposta dada por qualquer algoritmo “preciso” que você se importaria. para correr. (Veja esta resposta do StackOverflow para as contas.)

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

“Espaço”, diz, “é grande. Realmente grande. Você só não vai acreditar em quão imensamente imensamente grande é. Quero dizer, você pode achar que é um longo caminho até a farmácia, mas isso é apenas amendoim para o espaço.” , ouço…”

E como há 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 – GIDs para cada estrela. Se cada uma dessas estrelas tivesse um mundo com uma população próspera como a nossa, então, em torno de cada uma das estrelas, todo ser humano ou alienígena que já tivesse vivido teria direito a mais de quarenta e cinco mil GUIDs. Para cada pessoa na história em todas as estrelas do universo. O espaço do GUID está no mesmo nível de imensidão que o tamanho do universo inteiro. Você não precisa se preocupar.

( Edit 2: Refletindo sobre isso: wow. Eu não tinha me percebido o que isso significava. O espaço do GUID é incompreensivelmente massivo. Eu estou admirado com isso.)

Resposta curta: para fins práticos, sim.

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

Eu calculei algumas probabilidades de colisão representativas. Com UUIDs de 122 bits, conforme especificado no artigo da Wikipédia , a probabilidade de colisão é de 1/2 se você gerar pelo menos 2.71492e18 UUIDs. Com 10 ^ 19 UUIDs, a probabilidade é de 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 os UUIDs colididos sejam usados ​​para o mesmo propósito é muito pequena, então não há problema na prática.

Em geral, sim, é seguro assumir.

Se o seu gerador GUID for verdadeiramente random, as possibilidades de um conflito dentro de um 1000 GUIDs são extraordinariamente pequenas.

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

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

Como mencionado no link, isso será afetado pelas propriedades do gerador de números randoms.

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

Um filtro Bloom pode ser apropriado; Ele 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.

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

Geralmente é uma suposição bastante segura.

http://en.wikipedia.org/wiki/Globally_Unique_Identifier

É um GUID exclusivo 100% do tempo?

    Intereting Posts