As colisões de GUID são possíveis?

Eu estou trabalhando em um database no SQL Server 2000 que usa um GUID para cada usuário que usa o aplicativo está vinculado a. De alguma forma, dois usuários acabaram com o mesmo GUID. Eu sei que a Microsoft usa um algoritmo para gerar um GUID random que tem uma chance extremamente baixa de causar colisões, mas é uma colisão ainda possível?

Basicamente não. Eu acho que alguém foi mucking com seu database. Dependendo da versão GUID que você está usando, o valor é exclusivo (para coisas como GUIDs de versão 1) ou exclusivo e imprevisível (para coisas como GUIDs de versão 4). A implementação do SQL Server para sua function NEWID () parece usar um número random de 128 bits, portanto, você não obterá uma colisão.

Para uma chance de 1% de colisão, você precisa gerar cerca de 2.600.000.000.000.000.000 de GUIDs.

Basicamente eles não são possíveis! , as chances são astronomicamente baixas .

Mas … eu sou a única pessoa que eu conheço que teve uma colisão de GUID uma vez (sim!).

E tenho certeza disso, e isso não foi um erro.

Como isso aconteceu, em um pequeno aplicativo que estava sendo executado no Pocket PC, no final de uma operação, um comando que possui um GUID gerado deve ser emitido. O comando depois de ter sido executado no servidor foi armazenado em uma tabela de comandos no servidor junto com a data de execução. Um dia, quando eu estava depurando, emiti o comando module (com o GUID recém-gerado anexado) e nada aconteceu. Eu fiz isso de novo (com o mesmo guid, porque o guid foi gerado apenas uma vez no início da operação), e novamente, e nada, finalmente tentando descobrir porque o comando não está em execução, eu verifiquei a tabela de comando, e o mesmo GUID que o atual foi inserido há 3 semanas. Não acreditando nisso, eu restaurei um database a partir de 2 semanas de backup, e o guia estava lá. Verificado o código, o novo guia foi recém-gerado, sem dúvida. Pow guid collision, aconteceu apenas uma vez, mas eu realmente gostaria de ter ganhado na loteria, a chance é maior :).

Edit: existem alguns fatores que poderiam ter aumentado consideravelmente a chance de isso acontecer, o aplicativo estava sendo executado no emulador PocketPC, e o emulador tem um recurso de salvamento, o que significa que toda vez que o estado é restaurado, a hora local também é restaurada e o guid é baseado no timer interno …. também o algoritmo de geração de guia para o framework compacto pode ser menos completo que por exemplo o COM …

Eles são teoricamente possíveis, mas com números possíveis de 3,4E38, se você criar dezenas de trilhões de GUIDs em um ano, a chance de ter uma duplicata é de 0,00000000006 ( Fonte ).

Se dois usuários acabaram com o mesmo GUID, eu aposto que há um bug no programa que está fazendo com que os dados sejam copiados ou compartilhados.

Primeiro, vamos analisar a chance de colisão de dois GUIDs. Não é, como outras respostas afirmaram, 1 em 2 ^ 128 (10 ^ 38) por causa do paradoxo do aniversário , o que significa que, para 50% de chance de dois GUIDs colidirem, a probabilidade é de 1 em 2 ^ 64 (10 ^ 19) que é muito menor. No entanto, isso ainda é um número muito grande e, como tal, a probabilidade de colisão assumindo que você está usando um número razoável de GUIDs é baixa.

Observe também que os GUIDs não contêm um registro de data e hora ou o endereço MAC, como muitas pessoas também parecem acreditar. Isso era verdadeiro para os GUIDs v1, mas agora os GUIDs v4 são usados, que são simplesmente um número pseudo-random, o que significa que a possibilidade de colisão é possivelmente maior, porque eles não são mais exclusivos de um tempo e uma máquina.

Então, essencialmente, a resposta é sim, as colisões são possíveis. Mas eles são altamente improváveis.

Editar: fixo para dizer 2 ^ 64

As chances de dois GUIDs randoms colidirem (~ 1 em 10 ^ 38) são menores do que a chance de não detectar um pacote TCP / IP corrompido (~ 1 em 10 ^ 10). http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf , página 11. Isto também é verdade para unidades de disco, unidades de CD, etc …

Os GUIDs são estatisticamente exclusivos e os dados que você lê no database são estatisticamente corretos.

Eu consideraria a razor de Occam como um bom guia neste caso. É incrivelmente improvável que você tenha uma colisão de GUID. É muito mais provável que você tenha um bug ou alguém mexendo com seus dados.

Veja o artigo do Identificador Exclusivo Global da Wikipedia. Existem várias maneiras de gerar GUIDs. Aparentemente, a maneira antiga (?) Usava o endereço Mac, um registro de data e hora até uma unidade muito pequena e um contador exclusivo (para gerenciar gerações rápidas no mesmo computador), tornando-os duplicados quase impossíveis. Mas esses GUIDs foram descartados porque podem ser usados ​​para rastrear usuários …

Eu não tenho certeza do novo algoritmo usado pela Microsoft (o artigo diz que uma seqüência de GUIDs pode ser prevista, parece que eles não usam mais timestamp? O artigo da Microsoft ligado acima diz outra coisa …).

Agora, os GUIDs são cuidadosamente projetados para serem, por nome, globalmente exclusivos, então arriscarei que seja impossível, ou de probabilidade muito muito baixa. Eu procuraria em outro lugar.

Duas máquinas Win95 que possuem placas ethernet com endereços MAC duplicados emitirão GUIDs duplicados sob condições rigorosamente controladas, especialmente se, por exemplo, a energia for desativada no edifício e ambas forem inicializadas exatamente ao mesmo tempo.

Eu sei que as pessoas gostam da resposta de que os GUIDs são mágicos e garantidos como únicos, mas, na realidade, a maioria dos GUIDs são apenas números randoms de 121 bits (sete dos bits são desperdiçados na formatação). Se você não se sentir confortável usando um grande número random, não se sinta confortável usando um GUID.

O código usado para gerar um GUID pode ter um bug? Sim, claro que poderia. Mas a resposta é a mesma que seria para um bug do compilador – o seu próprio código tem uma magnitude maior de bugs, então olhe lá primeiro.

Claro que é possível …. Provável? Não é provável, mas é possível.

Lembre-se, a mesma máquina está gerando cada GUID (o servidor), portanto, muito da “aleatoriedade” que é baseada em informações específicas da máquina é perdida.

Apenas para sorrisos, tente o seguinte script … (funciona no SQL 2005, não tenho certeza sobre 2000)

 declare @table table ( column1 uniqueidentifier default (newid()), column2 int, column3 datetime default (getdate()) ) declare @counter int set @counter = 1 while @counter < = 10000 begin insert into @table (column2) values (@counter) set @counter = @counter + 1 end select * from @table select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2 

Executar isso repetidamente (leva menos de um segundo) produz um intervalo bastante amplo a partir do primeiro seleto, mesmo com um intervalo de tempo EXTREMAMENTE curto. Até agora, o segundo select não produziu nada.

Impossível se os usuários tiverem máquinas diferentes com placas de rede e, mesmo que não, ainda é um risco quase teórico extremamente marginal.

Pessoalmente, eu procuraria em outro lugar, pois é mais provável que seja um bug em vez de um confronto de GUID …

Desde que você não corte bits do GUID para torná-lo mais curto.

Claro que é possível, e talvez até provável. Não é como se cada GUID estivesse em uma parte aleatória do espaço numérico possível. No caso em que dois segmentos tentaram gerar um simultaneamente, bloqueando algum tipo de function GUID centralizada com um semáforo em torno dele, eles poderiam acabar com o mesmo valor.

Vou começar com “Eu não sou uma pessoa em rede, então posso fazer frases completamente incoerentes depois”.

Quando trabalhei na Illinois State University, tínhamos dois desktops da Dell, pedidos em horários diferentes. Colocamos o primeiro na rede, mas quando tentamos colocar o segundo na rede começamos a receber erros malucos. Depois de muita solução de problemas, foi determinado que as duas máquinas estavam produzindo o mesmo GUID (não sei ao certo para que, mas as inutilizava na rede). A Dell substituiu as duas máquinas como defeituosas.

É altamente improvável que você NEWID() colisões de GUID se as estiver gerando por meio de algo como a function NEWID() no SQL Server (embora, é claro, possível, como outras respostas enfatizaram). Uma coisa que eles não apontaram é que, na verdade, é bem provável que você colida em colisões se estiver gerando GUIDs em JavaScript nos navegadores em estado selvagem. Não só existem problemas com o RNG em navegadores diferentes, mas também tenho problemas com os spiders do Google que armazenam em cache os resultados de funções desse tipo e acabam transmitindo repetidamente o mesmo GUID para nossos sistemas.

Veja as várias respostas aqui para mais detalhes:

Colisões ao gerar UUIDs em JavaScript?