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

128

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?

Jason Baker
fonte
11
Todo mundo que diz que não está errado. Eu já colidi 1 UniqueIdentifier com um conjunto de dados de menos de meio milhão de registros, MSSQL 2008 R2
Behrooz
2
@Behrooz Yikes. Não é impossível graças ao nosso amigo o paradoxo do aniversário, mas ainda é incrivelmente azarado com GUIDs v4 totalmente aleatórios. Talvez você estivesse usando uma estratégia de geração de GUID mais fraca?
Craig Ringer
6
@Behrooz Wow. Que sorte chocante.
Craig Ringer
6
@Behrooz, este é provavelmente um número pseudo-aleatório defeituoso usado no MSSQL (eu não ficaria surpreso se eles tivessem uma semente de 32 bits em seu gerador ou algo semelhante, dada a qualidade de seu software). A matemática não mente. Essa possibilidade é tão pequena que é possível 99,9999999999 (e muitos 9 após)% que o gerador de guia MSSQL está com defeito (ou pode ser um gerador pseudo-aleatório que é usado para gerar GUIDs) ou você cometeu um erro.
12124 Alex
2
Adoro como, neste exato momento, a pergunta e a resposta selecionada têm 128 pontos. Coincidência? 🤔
Caio Cunha

Respostas:

127

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.

Tom Ritter
fonte
3
Era o que eu imaginava, mas eu só queria ter certeza de que não podia descartar isso. Você nunca sabe que tipos de bugs estranhos podem aparecer no software de 8 anos. :)
Jason Baker
6
Na verdade, isso não é mais verdade. Isso era verdade para os GUIDs da v1, mas não para os atuais da v4. Consulte en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm para obter mais informações.
Greg Beech
96
Voto negativo porque, em princípio (na sua forma mais bruta), você está errado ao dizer "não" à pergunta "As colisões do GUID são possíveis?". É muito possível A probabilidade disso é pequena, mas é possível. Eu odeio parecer pedante - mas SO é tudo sobre ser conciso e preciso.
13
digite "resolver [1-exp [- (n ^ 2 / (2 * 2 ^ 128))]> 0,01, n]" em wolfram alpha para obter o resultado para 1% ... Tenha em atenção que, embora esse número pareça grande em contexto de UMA aplicação, certamente não é grande para o mundo inteiro. Se todos os computadores do mundo gerassem GUIDs verdadeiros, eles causariam uma colisão com 1% de probabilidade em cerca de um segundo, supondo que eles possam gerar um GUID a cada nanossegundo (o que provavelmente é bastante realista atualmente). Portanto, se você usar GUIDs para seus IDs de banco de dados, eles serão exclusivos. GUIDs para todos os cálculos feitos na Terra colidirão imediatamente.
thesaint
11
Dizer 'não' não é possível e dizer que há 1% de chance de colisão quando uma certa quantia é gerada, são conflitos diretos. A resposta correta deve ser teoricamente - sim, uma colisão pode acontecer aleatoriamente. No entanto, as chances de uma colisão são estatisticamente menores do que um asteróide atingindo a Terra, ricocheteando na Terra e se recuperando da Lua para atingir a Terra uma segunda vez, na próxima hora.
precisa saber é
112

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 ...

Pop Catalin
fonte
38
Votado. Salvar estado e repetição realmente gerariam guias duplicados.
217 Joshua Joshua
35
Provavelmente, o que aconteceu foi uma implementação de GUID "ruim". As probabilidades teóricas eram muito baixas, mas no Pocket PC? Quem pode dizer que eles não adotaram um atalho que elevou essas probabilidades à categoria "improvável, mas possível".
quer
9
Só porque algo tem uma probabilidade muito baixa de acontecer não significa que não vai acontecer.
Renan
3
Como eu disse acima, as chances são tão pequenas que é seguro supor que você cometeu um erro ou o MSSQL usa um PRNG com defeito ( en.wikipedia.org/wiki/Pseudorandom_number_generator ). Por exemplo, é provável que este PRNG seja inicializado com uma semente de tamanho pequeno. PRNGs defeituosos não são raros (ver schneier.com/paper-prngs.html ) - por exemplo, um defeito foi descoberto recentemente no SDK Android - android-developers.blogspot.com/2013/08/... + usenix.org/conference/woot14 / workshop-programme / presentation /…
Alex
2
@Alex, o erro foi "Salvar estado e restauração" do emulador, que restaura toda a imagem do emulador, incluindo o relógio do emulador. Portanto, após milhares de operações de restauração ao longo de um ano, uma colisão de guia foi gerada. Você está certo, houve um erro!
Pop Catalin
34

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.

Ben Hoffstein
fonte
"mas com 3.4E38 números possíveis" - não. Dois GUIDs gerados quase simultaneamente na mesma máquina acabariam com GUIDs extremamente semelhantes.
22410 Kirk Strauser
4
Isso dependeria de como o GUID é gerado, e algumas implementações baseadas no tempo da CPU ou em milissegundos (espero) exagerarão qualquer cálculo baseado em dois GUIDs gerados a partir de milissegundos terá uma grande diferença.
Dalin Seivewright 31/10/08
4
Com mais de um processador em uma máquina, se um guia for baseado no tempo e no endereço mac, cada núcleo poderá emitir o mesmo guia no mesmo momento.
AndyM 19/02/10
12
Tenho certeza de que qualquer implementação GUID decente não vai
Guillaume86
1
@MatthewLock O paradoxo do aniversário é coberto na fonte. Verifique o link.
Zero3 11/01
21

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

Greg Beech
fonte
2
Embora eu concorde com todos os seus fatos, tenha cuidado com sua matemática. Dizer que você tem uma chance de 1 em 10 ^ 19 de dois GUIDs colidirem depende de quantos GUIDs estão no conjunto. Para essa chance, você precisa de ~ 2 ^ 32 GUIDs; portanto, em quase todos os cenários do mundo real, as chances são muito menores.
DocMax 9/10/08
1
Você tem um erro de digitação 1 in 10^64 (10^19), o que eu acho que deveria ser 1 in 2^64 (10^19). Também estou muito confuso como você acha que o paradoxo do aniversário se aplica a apenas 2 números. Suponho que você tenha consultado en.wikipedia.org/wiki/Birthday_paradox . A tabela mostra quantos guias você precisa para uma determinada probabilidade de duplicação. A partir dessa tabela, a probabilidade de 1 em 10 ^ 18 requer 2,6 * 10 ^ 10 guias, nada próximo a apenas dois GUIDs.
Tony Lee
Um ponto - os guias v1 ainda são amplamente utilizados e dependem do endereço MAC, principalmente nos bancos de dados, pois possuem características desejáveis. Consulte UuidCreateSequential e seu wrapper do SQL Server, NewSequentialID ( msdn.microsoft.com/en-us/library/windows/desktop/… ).
EBarr
18

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.

Tony Lee
fonte
Tem certeza de que eu não poderia blindar minha rede para que menos de 1 em 10 ^ 28 pacotes estejam corrompidos?
Joshua
13

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.

Jason Jackson
fonte
1
Na verdade, nessa situação, a navalha de Occam não é um bom guia! A Navalha de Occam diz que o caso com o mínimo de suposições provavelmente está correto. Nessa situação, o caso de colisão com GUID é realmente muito mais simples, mas o Razcam da Occam não se aplica a uma situação como essa em que já sabemos que um dos casos é incrivelmente improvável.
Lockstock 14/08/19
11

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.

PhiLho
fonte
6
Eric post 1
Nat
4
Eric post 2
Nat
4
Eric post 3
Nat
9

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.

Joshua
fonte
É comum que duas máquinas diferentes tenham o mesmo endereço MAC Ethernet?
Dave Lucre
@DaveLucre: Não, mas os incidentes foram registrados.
Joshua
Estou realmente curioso sobre como isso acontece. É mais provável que as VMs gerem aleatoriamente um MAC para cada NIC? Eu nunca ouvi falar de placas de rede físicas sendo fabricadas com MACs duplicados! Tipo de lança uma chave de boca maciça nos trabalhos, se isso é possível!
Dave Lucre
Uau! Obrigado pelo link @ Josué! Que confusão colossal!
Dave Lucre
@DaveLucre Eu usei algumas NICs USB muito baratas, onde TODAS elas são fabricadas com o mesmo MAC. Mas, é claro, isso não tem nada a ver com a matemática da aleatoriedade, e tudo a ver com a preguiça do fabricante.
Rudolfbyker 03/12/19
5

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.

John Kraft
fonte
3
Era especificamente o GUID. Tinha algo a ver com o GUID gerado pelas máquinas quando elas ingressaram na rede. A Dell levou várias semanas para substituir as máquinas, porque elas disseram que era impossível os GUIDs serem os mesmos. Conseguimos reproduzir o problema, a Dell retirou as máquinas e produzimos os mesmos resultados em suas redes. Eles acabaram substituindo as duas máquinas. Como eu disse, não sou uma pessoa de rede, mas lembro-me especificamente de que havia um problema com os GUIDs.
John Kraft
5

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.

Rick Yorgason
fonte
11
Recomendamos também que você não use redes. Ou computadores. Os bits de paridade podem fazer tanto!
Rushyo 03/02
Você entendeu mal. Há duas coisas que eu estava tentando dizer neste post: 1) Se você precisar de um grande número aleatório, use um grande número aleatório. Usar um GUID como um grande número aleatório é desnecessariamente enganoso. (2)
Rick Yorgason 18/03
4
O que eu tenho plena consciência. Você declarou "se não se sentiria confortável usando um grande número aleatório". mas os GUIDs são tão únicos que você acha que praticamente todo o resto de um computador é mais aleatório, mesmo as operações que você considera óbvias. Há mais chances de que uma falha de memória esquisita quebre sua coluna de identidade do que uma colisão GUID (verdadeira). Você não deve se sentir 'desconfortável' com eles. Se eles não são ideais para o cenário, tudo bem - mas eles não precisam de cuidado especial.
Rushyo 22/03
3
Eu acho que isso não vai a lugar nenhum, mas o que as pessoas estão tentando explicar é que os mecanismos de detecção de erros em hardware comum, como placas de rede ou discos rígidos, usam algoritmos com maiores chances de não detectar um erro do que você de obter uma colisão GUID; você contar com estes, você poderia muito bem contar com GUIDs
Guillaume86
1
@ Rick, depende do tamanho do seu número. Definitivamente não com um 4 byte int ou 8 byte bigint. GUID = 16 bytes, portanto, você precisará de uma implementação personalizada de grande número de 16 bytes para obter as mesmas 2 ^ 128 combinações possíveis. Então, de um modo geral, se estiver usando números aleatórios int ou bigint 'normais', a chance de colisões com um GUID é menor (deixando de fora algumas considerações aleatórias para cada um).
Wim Hollebrandse
3

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.

Mark Ransom
fonte
2

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.

FlySwat
fonte
1

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.

GalacticCowboy
fonte
1
Você precisa de outros 15 zeros no final do balcão para ter 50% de chance de duplicar. Mas, pelo amor de Pete, não faça isso!
22610 Jim Jim Chachall
0

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.

Richard Harrison
fonte
Os GUIDs seriam gerados no servidor, para que as placas de rede do usuário não entrassem em jogo.
Tom Ritter
0

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.

Kirk Strauser
fonte
0

É 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?

Ken Smith
fonte