Um GUID é exclusivo 100% do tempo?

https://stackoverflow.com/questions/39771

09-06-2019
|

Pergunta

Ele permanecerá único em vários threads?

Solução

Embora cada Guid gerado não seja garantido, o número total de chaves exclusivas (2¹²⁸ ou 3,4 × 10³⁸) é tão grande que a probabilidade de o mesmo número ser gerado duas vezes é muito pequeno.Por exemplo, considere o universo observável, que contém cerca de 5 × 10²²estrelas;Cada estrela poderia ter 6,8 × 10¹⁵ GUIDs universalmente exclusivos.

De Wikipédia.

Estes são alguns bons artigos sobre como um GUID é feito (para .NET) e como você pode obter o mesmo guia na situação certa.

https://ericlippert.com/2012/04/24/guid-guide-part-one/

https://ericlippert.com/2012/04/30/guid-guide-part-two/

https://ericlippert.com/2012/05/07/guid-guide-part-três/

Outras dicas

A resposta simples é sim.

Raymond Chen escreveu um ótimo artigo em GUIDs e por que substrings de GUIDs são não único garantido.O artigo se aprofunda na maneira como os GUIDs são gerados e nos dados que eles usam para garantir a exclusividade, o que deve ser explicado com bastante profundidade por que eles são :-)

Se você tem medo dos mesmos valores de GUID, coloque dois deles um ao lado do outro.

Guid.NewGuid().ToString() + Guid.NewGuid().ToString();

Se você é muito paranóico, coloque três.

Como observação lateral, eu estava brincando com GUIDs de volume no Windows XP.Este é um layout de partição muito obscuro com três discos e quatorze volumes.

\\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:)
\\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:)
\\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:)
\\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:)
\\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:)
\\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:)
\\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:)
\\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:)
\\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:)
\\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:)
\\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:)
\\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:)
\\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:)
                                     | | | | |
                                     | | | | +-- 6f = o
                                     | | | +---- 69 = i
                                     | | +------ 72 = r
                                     | +-------- 61 = a
                                     +---------- 6d = m

Não é que os GUIDs sejam muito semelhantes, mas o fato de todos os GUIDs conterem a string "mario".Isso é uma coincidência ou há uma explicação por trás disso?

Agora quando pesquisando a parte 4 no GUID encontrei aproximadamente 125.000 acessos com GUIDs de volume.

Conclusão: Quando se trata de GUIDs de volume, eles não são tão exclusivos quanto outros GUIDs.

Sim, um GUID deve sempre ser único.É baseado no hardware e no tempo, além de alguns bits extras para garantir que seja único.Tenho certeza de que é teoricamente possível acabar com dois idênticos, mas extremamente improvável em um cenário do mundo real.

Aqui está um ótimo artigo de Raymond Chen no Guids:

https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Isso não deveria acontecer.No entanto, quando o .NET está sob carga pesada, é possível obter guias duplicados.Tenho dois servidores web diferentes usando dois servidores SQL diferentes.Fui mesclar os dados e descobri que tinha 15 milhões de guias e 7 duplicatas.

Os guias são estatisticamente únicos.As chances de dois clientes diferentes gerarem o mesmo Guid são infinitamente pequenas (assumindo que não há bugs no código de geração do Guid).Você também pode se preocupar com falhas no processador devido a um raio cósmico e decidir que 2 + 2 = 5 hoje.

Vários threads que alocam novos guias obterão valores exclusivos, mas você deve saber que a função que está chamando é thread-safe.Em que ambiente isso está?

Eric Lippert escreveu uma série de artigos muito interessantes sobre GUIDs.

Existem na ordem 2³⁰ Computadores pessoais no mundo (e, claro, muitos dispositivos portáteis ou dispositivos de computação não PC que possuem mais ou menos os mesmos níveis de poder de computação, mas vamos ignorá-los).Vamos supor que colocamos todos esses PCs no mundo na tarefa de gerar GUIDs;se cada um pode gerar, digamos, 2²⁰ Guids por segundo, depois de apenas 2⁷² segundos - cento e cinquenta trilhões de anos - você terá um muito alto chance de gerar uma colisão com seu GUID específico.E as chances de colisão ficam muito boas depois de apenas trinta trilhões de anos.

Teoricamente, não, eles não são únicos.É possível gerar um guia idêntico repetidamente.No entanto, as chances de isso acontecer são tão baixas que você pode presumir que são únicas.

Eu li antes que as chances são tão baixas que você realmente deveria se preocupar com outra coisa - como a combustão espontânea do seu servidor ou outros bugs no seu código.Ou seja, assuma que é único e não crie nenhum código para "capturar" duplicatas - gaste seu tempo em algo mais provável de acontecer (ou seja, qualquer coisa outro).

EU fiz uma tentativa para descrever a utilidade dos GUIDs para o público do meu blog (membros da família não técnicos).A partir daí (via Wikipedia), as chances de gerar um GUID duplicado:

1 em 2 ^ 128
1 em 340 Undecillion (não se preocupe, o Undecillion não está no teste)
1 em 3,4 × 10 ^ 38
1 em 340.000.000.000.000.000.000.000.000.000.000.000.000

Ninguém parece mencionar a matemática real da probabilidade de isso ocorrer.

Primeiro, vamos supor que podemos usar todo o espaço de 128 bits (o Guid v4 usa apenas 122 bits).

Sabemos que a probabilidade geral de NÃO obter uma duplicata em n escolhas é:

(1-1/2¹²⁸)(1-2/2¹²⁸)...(1-(n-1)/2¹²⁸)

Porque 2¹²⁸ é muito maior do que n, podemos aproximar isso para:

(1-1/2¹²⁸)^n(n-1)/2

E porque podemos assumir n é muito maior que 0, podemos aproximar isso para:

(1-1/2¹²⁸)^{n ^ 2/2}

Agora podemos igualar isso à probabilidade “aceitável”, digamos 1%:

(1-1/2¹²⁸)^{n ^ 2/2} = 0.01

Para o qual resolvemos n e pegue:

n = sqrt(2* log 0,01 / log (1-1/2¹²⁸))

Qual Wolfram Alpha será 5.598318 × 10¹⁹

Para colocar esse número em perspectiva, vamos pegar 10.000 máquinas, cada uma com uma CPU de 4 núcleos, fazendo 4Ghz e gastando 10.000 ciclos para gerar um Guid e não fazer mais nada.Levaria então cerca de 111 anos até que eles gerassem uma duplicata.

De http://www.guidgenerator.com/online-guid-generator.aspx

O que é um GUID?

GUID (ou UUID) é um acrônimo para 'Identificador Globalmente Único' (ou 'Identificador Universalmente Único').É um número inteiro de 128 bits usado para identificar recursos.O termo GUID é geralmente usado por desenvolvedores que trabalham com tecnologias Microsoft, enquanto UUID é usado em qualquer outro lugar.

Quão único é um GUID?

128 bits é grande o suficiente e o algoritmo de geração é único o suficiente para que, se 1.000.000.000 GUIDs por segundo fossem gerados durante 1 ano, a probabilidade de uma duplicata seria de apenas 50%.Ou se cada ser humano na Terra gerasse 600 milhões de GUIDs, haveria apenas 50% de probabilidade de duplicação.

MSDN:

Há uma probabilidade muito baixa de que o valor do novo Guid seja totalmente zero ou igual a qualquer outro Guid.

Se o relógio do seu sistema estiver configurado corretamente e não estiver configurado, e se a sua NIC tiver seu próprio MAC (ou seja,você não definiu um MAC personalizado) e seu fornecedor de NIC não reciclou MACs (o que eles não deveriam fazer, mas que ocorre), e se a função de geração de GUID do seu sistema estiver implementada corretamente, seu sistema irá nunca gere GUIDs duplicados.

Se todos no mundo que geram GUIDs seguirem essas regras, seus GUIDs serão globalmente únicos.

Na prática, o número de pessoas que infringem as regras é baixo e é pouco provável que os seus GUIDs “escapem”.Os conflitos são estatisticamente improváveis.

Eu experimentei um GUID duplicado.

Eu uso o scanner de desktop Neat Receipts e ele vem com software de banco de dados proprietário.O software possui um recurso de sincronização com a nuvem e continuei recebendo um erro durante a sincronização.Uma olhada nos registros revelou a linha incrível:

"erros":[{"código":1,"mensagem":"creator_guid:já está levado "," GUID ":" C83E5734-D77A-4B09-B8C1-9623CAC7B167 "}]}

Fiquei um pouco descrente, mas com certeza, quando encontrei um caminho para meu banco de dados local do Neatworks e excluí o registro contendo aquele GUID, o erro parou de ocorrer.

Então, para responder à sua pergunta com evidências anedóticas, não.Uma duplicata é possível.Mas é provável que o motivo pelo qual isso aconteceu não tenha sido devido ao acaso, mas sim ao fato de a prática padrão não ter sido seguida de alguma forma.(Simplesmente não tenho tanta sorte). No entanto, não posso dizer com certeza.Não é meu software.

O suporte ao cliente deles foi EXTREMAMENTE cortês e prestativo, mas eles nunca devem ter encontrado esse problema antes, porque depois de mais de 3 horas no telefone com eles, não encontraram a solução.(FWIW, estou muito impressionado com o Neat, e essa falha, por mais frustrante que seja, não mudou minha opinião sobre o produto deles.)

Um GUID é exclusivo 100% do tempo?

Não garantido, pois existem diversas formas de gerar um.No entanto, você pode tentar calcular a chance de criar dois GUIDs idênticos e terá a ideia:um GUID tem 128 bits, portanto, existem 2¹²⁸ GUIDs distintos – muito mais do que há estrelas no universo conhecido.Leia o artigo da Wikipédia para mais detalhes.

Os algoritmos GUID geralmente são implementados de acordo com a especificação GUID v4, que é essencialmente uma string pseudo-aleatória.Infelizmente, estes se enquadram na categoria de "provavelmente não único", da Wikipedia (não sei por que tantas pessoas ignoram essa parte):"...outras versões do GUID têm diferentes propriedades e probabilidades de exclusividade, variando de exclusividade garantida a provável não exclusividade."

As propriedades pseudo-aleatórias do JavaScript do V8 Math.random() são TERRÍVEIS em termos de exclusividade, com colisões geralmente ocorrendo após apenas alguns milhares de iterações, mas o V8 não é o único culpado.Já vi colisões de GUID no mundo real usando implementações PHP e Ruby de GUIDs v4.

Como está se tornando cada vez mais comum escalar a geração de ID em vários clientes e clusters de servidores, a entropia sofre um grande golpe - as chances de a mesma semente aleatória ser usada para gerar um escalonamento de ID (o tempo é frequentemente usado como uma semente aleatória em geradores pseudo-aleatórios) e as colisões de GUID aumentam de "provavelmente não exclusivas" para "muito provavelmente causarão muitos problemas".

Para resolver esse problema, decidi criar um algoritmo de ID que pudesse ser dimensionado com segurança e oferecer melhores garantias contra colisões.Isso é feito usando o carimbo de data/hora, um contador de cliente na memória, impressão digital do cliente e caracteres aleatórios.A combinação de fatores cria uma complexidade aditiva que é particularmente resistente a colisões, mesmo se você escaloná-la em vários hosts:

http://usecuid.org/

Eu percebi que os GUIDs não eram exclusivos durante testes de unidade multithread/multiprocessos (também?).Eu acho que isso tem a ver com, todas as outras coisas sendo iguais, a propagação idêntica (ou falta de propagação) de geradores pseudo-aleatórios.Eu estava usando-o para gerar nomes de arquivos exclusivos.Achei que o sistema operacional é muito melhor nisso :)

Alerta de trollagem

Você pergunta se os GUIDs são 100% exclusivos.Isso depende do número de GUIDs entre os quais deve ser exclusivo.À medida que o número de GUIDs se aproxima do infinito, a probabilidade de GUIDs duplicados se aproxima de 100%.

Num sentido mais geral, isto é conhecido como “problema do aniversário” ou “paradoxo do aniversário”.A Wikipedia tem uma visão geral muito boa em:Wikipedia - Problema de aniversário

Em termos muito aproximados, a raiz quadrada do tamanho do pool é uma aproximação aproximada de quando você pode esperar 50% de chance de duplicação.O artigo inclui uma tabela de probabilidade do tamanho do pool e várias probabilidades, incluindo uma linha para 2^128.Portanto, para uma probabilidade de colisão de 1%, você esperaria escolher aleatoriamente 2,6 * 10 ^ 18 números de 128 bits.Uma chance de 50% requer 2,2*10^19 escolhas, enquanto SQRT(2^128) é 1,8*10^19.

Claro, esse é apenas o caso ideal de um processo verdadeiramente aleatório.Como outros mencionaram, muita coisa depende disso aleatório aspecto - quão bons são o gerador e a semente?Seria bom se houvesse algum suporte de hardware para ajudar nesse processo, que seria mais à prova de balas, exceto que qualquer coisa pode ser falsificada ou virtualizada.Suspeito que essa possa ser a razão pela qual os endereços MAC/carimbos de data e hora não são mais incorporados.

A resposta de "Um GUID é 100% exclusivo?" e simples "Não" .

Se você deseja 100% de exclusividade do GUID, faça o seguinte.
1. gerar GUID
2. verifique se esse GUID existe na coluna da tabela onde você está procurando exclusividade
3. se existir, vá para a etapa 1, caso contrário, etapa 4
4. use este GUID como exclusivo.

A parte mais difícil não é gerar um Guid duplicado.

O mais difícil é projetar um banco de dados para armazenar todos os gerados para verificar se realmente está duplicado.

Do WIKI:

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

insira a descrição da imagem aqui

Este número é equivalente a gerar 1 bilhão de UUIDs por segundo durante cerca de 85 anos, e um arquivo contendo tantos UUIDs, a 16 bytes por UUID, teria 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

GUID significa Identificador Único Global

Em resumo:(A pista está no nome)

Em detalhe:Os GUIDs são projetados para serem exclusivos;eles são calculados usando um método aleatório baseado no relógio do computador e no próprio computador. Se você estiver criando muitos GUIDs no mesmo milissegundo na mesma máquina, é possível que eles correspondam, mas para quase todas as operações normais eles devem ser considerados únicos.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow