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

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

Basicamente, não. Acho que alguém mexeu com seu banco de dados. Dependendo da GUID da versão que você está usando, o valor é exclusivo (para itens como GUIDs da versão 1) ou é único e imprevisível (para itens como GUIDs da versão 4). A implementação do SQL Server para a função NEWID () parece usar um número aleatório de 128 bits, portanto você não terá uma colisão.

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

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

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

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

Como isso aconteceu, em um aplicativo pequeno 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 após a execução 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. Fiz isso novamente (com o mesmo guia, porque o guia foi gerado apenas uma vez no início da operação) e, novamente, e nada, finalmente tentando descobrir por que o comando não está sendo executado, verifiquei a tabela de comandos, e o mesmo GUID que o atual foi inserido há 3 semanas. Não acreditando nisso, restaurei um banco de dados a partir de 2 semanas de backup e o guia estava lá. Verificado o código, o novo guia foi gerado recentemente, sem dúvida.

Edit: existem alguns fatores que podem ter aumentado muito a chance de isso acontecer, o aplicativo estava sendo executado no emulador PocketPC e o emulador possui um recurso de salvar estado, 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 guid para estrutura compacta pode ser menos completo do que, por exemplo, o COM ...

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

Se dois usuários terminassem com o mesmo GUID, eu apostaria que há um erro no programa que está causando a cópia ou o compartilhamento dos dados.

Primeiro, vamos analisar a chance de colisão de dois GUIDs. Não é, como outras respostas declararam, 1 em 2 ^ 128 (10 ^ 38) devido ao paradoxo do aniversário , o que significa que, para uma chance de 50% de dois GUIDs colidirem com a probabilidade, na verdade, é 1 em 2 ^ 64 (10 ^ 19) que é muito menor. No entanto, esse 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 carimbo de data / hora ou o endereço MAC, como muitas pessoas também parecem acreditar. Isso era verdade para os GUIDs v1, mas agora os GUIDs v4 são usados, que são simplesmente um número pseudo-aleatório, o que significa que a possibilidade de colisão é sem dúvida maior porque eles não são mais exclusivos de um tempo e uma máquina.

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

Editar: corrigido para dizer 2 ^ 64

As chances de dois GUIDs aleatórios colidirem (~ 1 em 10 ^ 38) são menores 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. Isso também vale para unidades de disco, unidades de CD, etc.

Os GUIDs são estatisticamente exclusivos e os dados que você lê do banco de dados são apenas estatisticamente corretos.

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

Veja o identificador globalmente exclusivo da Wikipedia . Existem várias maneiras de gerar GUIDs. Aparentemente, a maneira antiga (?) Usava o endereço Mac, um carimbo de data / hora para uma unidade muito curta e um contador exclusivo (para gerenciar gerações rápidas no mesmo computador), tornando-os duplicados é quase impossível. Mas esses GUIDs foram descartados porque poderiam ser usados ​​para rastrear usuários ...

Não tenho certeza do novo algoritmo usado pela Microsoft (o artigo diz que uma sequência de GUIDs pode ser prevista, parece que eles não usam mais o carimbo de data / hora? O artigo da Microsoft vinculado acima diz outra coisa ...).

Agora, os GUIDs são cuidadosamente projetados para serem, por nome, globalmente únicos, então arriscarei que seja impossível ou com probabilidade muito, 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 estritamente controladas, especialmente se, por exemplo, a energia cair no prédio e as duas inicializarem exatamente ao mesmo tempo.

Eu prefácio isso com "Eu não sou uma pessoa de rede, então posso fazer frases completamente incoerentes a seguir".

Quando trabalhei na Illinois State University, tínhamos dois desktops da Dell, encomendados em momentos diferentes. Colocamos o primeiro na rede, mas quando tentamos colocar o segundo na rede, começamos a receber erros malucos. Após muita solução de problemas, determinou-se que as duas máquinas estavam produzindo o mesmo GUID (não sei exatamente para que, mas as inutilizava na rede). Na verdade, a Dell substituiu ambas as máquinas com defeito.

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 aleatórios 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 aleatório, não deverá se sentir confortável usando um GUID.

O código usado para gerar um GUID pode conter um erro? Sim, claro que poderia. Mas a resposta é a mesma que seria para um bug do compilador - seu próprio código tem ordens de magnitude com maior probabilidade de serem bugs, portanto, olhe primeiro.

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

Lembre-se de que a mesma máquina está gerando todos os GUID (o servidor); portanto, grande parte da "aleatoriedade" 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 uma faixa bastante ampla desde a primeira seleção, 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 se não houver, ainda é um risco quase teórico extremamente marginal.

Pessoalmente, eu procuraria em outro lugar, pois é mais provável que um bug do que um choque GUID ...

É claro que você não deve cortar o GUID para reduzi-lo.

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 de dois encadeamentos tentarem gerar um simultaneamente, com exceção de algum tipo de função GUID centralizada com um semáforo ao redor, eles podem acabar com o mesmo valor.

É altamente improvável que você tenha colisões com GUID se as estiver gerando por meio de algo como o NEWID() função 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ê entre em colisão se estiver gerando GUIDs em JavaScript em navegadores. Às vezes, não só existem problemas no RNG em diferentes navegadores, como também encontrei problemas em que as aranhas do Google parecem armazenar em cache os resultados de funções como essa e acabam passando repetidamente o mesmo GUID para nossos sistemas.

Veja as várias respostas aqui para obter mais detalhes:

Colisões ao gerar UUIDs em JavaScript?