São colisões GUID possível?

Question

Eu estou trabalhando em um banco de dados em SQL Server 2000 que usa um GUID para cada usuário que usa o aplicativo que está amarrada. De alguma forma, dois usuários acabaram com o mesmo GUID. Eu sei que usa o Microsoft um algoritmo para gerar um GUID aleatório que tem uma baixíssima chance de causar collisons, mas é uma colisão ainda é possível?

Answer 1

Basicamente, não. Acho que alguém foi mucking com o seu banco de dados. Dependendo da versão GUID que você está usando o valor é único (para coisas como a versão 1 GUIDs), ou ambos único e imprevisível (para coisas como a versão 4 GUIDs). A implementação do SQL Server para a sua função NEWID () parece usar um-128 mordeu número aleatório, então você não está indo para obter uma colisão.

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

Answer 2

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

Mas ... Eu sou a única pessoa que o mundo que eu conheço, que tinha um GUID colision uma vez (sim!).

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

Como isso aconteceu, em um pequeno aplicativo que foi executado em Pocket PC, no final de uma operação de um comando que tem um GUID gerado deve ser emitido. O comando depois que ele foi executado no servidor em que foi armazenada em uma tabela de comando no servidor, juntamente com a data de assinatura. Um dia, quando eu estava depurando dei o comando módulo (com o GUID recém-gerado em anexo) 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 por que o comando não está executando, eu verifiquei a mesa de comando, e o mesmo GUID como o atual foi inserido 3 semanas atrás. Não acreditando isso, eu restaurei uma base de dados de 2 semanas backup, eo guid estava lá. Verificado o código, o novo guid foi recém-gerado nenhuma dúvida sobre isso. Pow colisão guid, aconteceu apenas uma vez, mas eu realmente gostaria de ter vencido em lotto em vez disso, a chance é maior :).

Edit: existem alguns fatores que podem ter um grande aumento da chance de isso acontecer, o aplicativo foi executado no emulador PocketPC, eo emulador tem um recurso de economia de estado, o que significa que cada vez que o estado é restaurado a hora local é restaurada também eo guid baseia-se no cronômetro interno .... também o algoritmo de geração de GUID para estrutura compacta pode ser menos completo do que, por exemplo, a cOM ...

Answer 3

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

Se dois usuários acabaram com o mesmo GUID, eu seria capaz de apostar que há um erro no programa que está causando os dados a ser copiado ou compartilhado.

Answer 4

Primeiro vamos olhar para a possibilidade de colisão de dois GUIDs. Não é, como outras respostas afirmaram, 1 em 2 ^ 128 (10 ^ 38) por causa da paradoxo aniversário , o que significa que para uma probabilidade de 50% de duas Guids colidindo a probabilidade é, na verdade, uma em 2 ^ 64 (10 ^ 19), o qual é muito menor. No entanto, este ainda é um número muito grande, e como tal a probabilidade de colisão supondo que você está usando um número razoável de GUIDs é baixa.

Note também que GUIDs não contêm um timestamp ou o endereço MAC como muitas pessoas também parecem acreditar. Isto era verdade para GUIDs v1 mas agora GUIDs v4 são usadas, que são simplesmente um número pseudo-aleatório o que significa que possibilidade de colisão é indiscutivelmente maior, porque eles já não são exclusivos de um tempo e uma máquina.

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

Editar: corrigido para dizer 2 ^ 64

Answer 5

As probabilidades de dois Guids aleatórios de colisão (~ 1 em 10 ^ 38) é menor do que a probabilidade de não detecção de um pacote corrupto TCP / IP (~ 1 em 10 ^ 10). http: //wwwse.inf.tu-dresden .de / data / cursos / SE1 / SE1-2004-lec12.pdf, página 11. Isto também é verdade de unidades de disco, unidades de CD, etc ...

GUIDs são estatisticamente único e os dados lidos a partir do db só é estatisticamente correto.

Answer 6

Eu consideraria navalha de Occam como um bom guia nesse caso. É extremamente improvável que você tem uma colisão GUID. É muito mais provável que você tem um bug, ou alguém mexer com seus dados.

Answer 7

identificador exclusivo global . Existem várias maneiras de gerar GUIDs. Aparentemente, o velho (?) Caminho usado endereço Mac, um timestamp para baixo para um curto espaço de unidade e um balcão único (para gerir gerações rápidos no mesmo computador), tornando-os assim duplicar é quase impossível. Mas esses GUIDs foram retiradas porque eles poderiam ser usados ??para rastrear usuários ...

Eu não tenho certeza do novo algoritmo usado pelo Microsoft (o artigo diz uma seqüência de GUIDs pode ser previsto, parece que eles não timestamp uso? O artigo Microsoft ligada acima diz outra coisa ...).

Agora, GUIDs são cuidadosamente projetado para ser, pelo nome, globalmente únicos, por isso vou arriscar é impossível, ou muito muito muito baixa probabilidade. Gostaria de olhar em outro lugar.

Answer 8

máquinas Two Win95 que têm placas de rede com endereços MAC duplicados emitirá GUIDS duplicadas sob condições estritamente controladas, especialmente se, por exemplo, a energia é desligada no edifício e ambos inicialização exatamente ao mesmo tempo.

Answer 9

Eu sei que pessoas como a resposta sentir-se bem que GUIDs são mágicas e garantido para ser único, mas, na realidade, a maioria dos GUIDs são apenas 121 bits números aleatórios (sete dos bits são desperdiçados em formatação). Se você não se sentir confortável usando um número aleatório grande, então você não deve se sentir confortável usando um GUID.

Answer 10

Será que o código usado para gerar um GUID tem um bug nele? Sim, claro que podia. Mas a resposta é a mesma que seria para um bug do compilador -. Seu próprio código é ordens de magnitude mais propensos a ser buggy, assim que olhar lá primeiro

Answer 11

É 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), assim que um monte de "aleatoriedade", que é baseado em informações máquina específica é perdido.

Answer 12

Apenas para sorrisos, tente o seguinte script ... (obras sobre 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

A execução deste repetidamente (leva menos de um segundo) produz uma gama bastante ampla a partir da primeira escolha, mesmo com um intervalo de tempo extremamente curto. Até agora, a qualquer segundo SELECT não produziu.

Answer 13

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

Pessoalmente eu procurar em outro lugar como o mais provável é um erro em vez de um confronto GUID ...

O fornecimento é claro que você não cortar pedaços fora do GUID para torná-lo mais curto.

Answer 14

Claro que é possível, e talvez até mesmo provável. Não é como se cada GUID está em uma parte aleatória do possível número espaço. No caso em que dois tópicos tentou gerar um simultaneamente, salvo algum tipo de função GUID centralizada com um semáforo em torno dele, eles poderiam acabar com o mesmo valor.

Answer 15

Eu vou prefácio isto com "Eu não sou uma pessoa de rede, para que eu possa fazer sentenças completamente incoerentes seguintes.".

Quando eu trabalhava na Universidade Estadual de Illinois, tivemos dois desktops Dell, ordenou em momentos diferentes. Nós colocamos o primeiro na rede, mas quando tentámos para colocar o segundo na rede que começou a receber erros loucos. Depois de muita resolução de problemas, determinou-se que ambas as máquinas estavam produzindo o mesmo GUID (não tenho certeza exatamente o que para, mas fez os dois inutilizável na rede). Dell realmente substituído ambas as máquinas como defeituoso.

Answer 16

É altamente improvável que você vai correr em colisões GUID se você está gerando-los através de algo como a função NEWID() no SQL Server (embora, é claro possível, como outras respostas têm enfatizado). Uma coisa que eles não têm apontado é que é realmente muito provável que você vai correr em colisões Se você é GUIDs de geração em JavaScript em navegadores em estado selvagem. Não só existem, por vezes, problemas no RNG em diferentes navegadores, mas eu também executar em problemas onde as aranhas do Google parecem armazenar em cache os resultados de funções como essa, e acabou repetidamente passando o mesmo GUID até nossos sistemas.

Veja as várias respostas aqui para mais detalhes:

Colisões quando UUIDs de geração em JavaScript?