Les collisions GUID sont-elles possibles?

Question

Je travaille sur une base de données dans SQL Server 2000 qui utilise un GUID pour chaque utilisateur utilisant l'application à laquelle elle est liée. D'une manière ou d'une autre, deux utilisateurs se sont retrouvés avec le même GUID. Je sais que Microsoft utilise un algorithme pour générer un GUID aléatoire qui a très peu de chances de provoquer des collisions, mais une collision est-elle toujours possible?

Answer 1

En gros, non. Je pense que quelqu'un est allé fouiller avec votre base de données. Selon la version du GUID que vous utilisez, la valeur est unique (pour des éléments tels que les GUID de version 1) ou unique et imprévisible (pour des éléments tels que les GUID de version 4). L'implémentation de SQL Server pour leur fonction NEWID () semble utiliser un nombre aléatoire de 128 bits, de sorte que vous n'allez pas avoir une collision.

Pour un risque de collision de 1%, vous devez générer environ 2 600 000 000 000 000 .

Answer 2

En gros, ils ne sont pas possibles! , les chances sont faibles en astronomie .

Mais ... je suis la seule personne au monde que je connaisse, qui a déjà eu une collision GUID (ouais!).

Et j'en suis sûr, et que ce n'était pas une erreur.

Comment cela s’est-il produit, dans une petite application qui fonctionnait sur Pocket PC, à la fin d’une opération, une commande comportant un GUID généré doit être émise. La commande après son exécution sur le serveur a été stockée dans une table de commandes sur le serveur avec la date d'exécution. Un jour, alors que je déboguais, j’ai lancé la commande de module (avec le GUID nouvellement généré attaché) et rien ne s’est produit. Je l'ai refait (avec le même guid, car le guid n'a été généré qu'une fois au début de l'opération), et encore une fois, et rien, essayant enfin de savoir pourquoi la commande ne s'exécute pas, j'ai vérifié la table de commandes, et le même GUID que celui actuel a été inséré il y a 3 semaines. Sans croire cela, j'ai restauré une base de données à partir de 2 semaines de sauvegarde, et le GUID était là. Vérifié le code, le nouveau guide a été fraîchement généré aucun doute à ce sujet. La collision de Pow guid, n’est arrivée qu’une fois, mais j’aurais vraiment aimé pouvoir gagner au loto, les chances sont plus grandes :).

Modifier: certains facteurs auraient pu augmenter considérablement les chances que cela se produise. L'application était exécutée sur l'émulateur PocketPC et l'émulateur disposait d'une fonctionnalité d'enregistrement de l'état, ce qui signifie que chaque fois que l'état est restauré, l'heure locale est également restauré et le guid est basé sur le temporisateur interne .... de plus, l'algorithme de génération de guid pour un framework compact pourrait être moins complet que par exemple celui de COM ...

Answer 3

Ils sont théoriquement possibles, mais avec les numéros 3.4E38 possibles, si vous créez des dizaines de milliards de GUID dans une année, le risque d’avoir un doublon est de 0,00000000006 ( Source ).

Si deux utilisateurs se retrouvaient avec le même GUID, je parierais qu’un bogue dans le programme provoque la copie ou le partage des données.

Answer 4

Commençons par examiner le risque de collision de deux GUID. Ce n’est pas, comme d’autres réponses l’ont indiqué, 1 sur 2 ^ 128 (10 ^ 38) à cause du paradoxe de l'anniversaire , ce qui signifie que sur 50% de chances que deux GUID entrent en collision, la probabilité est en réalité de 1 sur 2 ^ 64 (10 ^ 19), ce qui est beaucoup plus petit. Toutefois, il s’agit toujours d’un très grand nombre et, de ce fait, la probabilité de collision si vous utilisez un nombre raisonnable de GUID est faible.

Notez également que les GUID ne contiennent pas d’horodatage ni d’adresse MAC, contrairement à ce que beaucoup de gens semblent croire. C'était le cas pour les GUID v1, mais les maintenant v4 sont simplement des nombres pseudo-aléatoires ce qui signifie que le risque de collision est sans doute plus élevé car ils ne sont plus propres à une époque et à une machine.

La réponse est donc essentiellement oui, les collisions sont possibles. Mais ils sont hautement improbables.

Edit: corrigé pour dire 2 ^ 64

Answer 5

Les risques de collision entre deux GUID aléatoires (~ 1 sur 10 ^ 38) sont inférieurs à ceux de ne pas détecter un paquet TCP / IP corrompu (~ 1 sur 10 ^ 10). http: //wwwse.inf.tu-dresd .de / data / courses / SE1 / SE1-2004-lec12.pdf , page 11. Cela vaut également pour les lecteurs de disque, les lecteurs de CD, etc. ...

Les GUID sont statistiquement uniques et les données lues à partir de la base de données ne sont statistiquement correctes.

Answer 6

Je considérerais le le rasoir d'Occam comme un bon guide dans ce cas. Il est extrêmement improbable que vous ayez une collision de GUID. Il est beaucoup plus probable que vous ayez un bogue ou que quelqu'un manipule vos données.

Answer 7

Voir l'article

Deux ordinateurs Win95 équipés de cartes Ethernet avec des adresses MAC dupliquées émettent des GUID dupliqués dans des conditions étroitement contrôlées, en particulier si, par exemple, le courant est coupé dans le bâtiment et que les deux démarrent exactement au même moment.

Je connais des gens qui aiment bien dire que les GUID sont magiques et garantis comme uniques, mais en réalité, la plupart des GUID ne sont que des nombres aléatoires de 121 bits (sept de ces bits sont perdus en formatage). Si vous ne vous sentez pas à l'aise avec l'utilisation d'un grand nombre aléatoire, vous ne devriez pas utiliser un GUID.

Le code utilisé pour générer un GUID pourrait-il contenir un bogue? Oui, bien sûr que ça pourrait. Mais la réponse est la même que pour un bogue de compilateur - votre propre code est un ordre de grandeur plus susceptible d’être bogué, alors regardez-le d’abord.

Bien sûr que c'est possible ... Probable? Peu probable, mais c'est possible.

N'oubliez pas que la même machine génère tous les GUID (le serveur), ce qui explique le "caractère aléatoire". qui est basé sur des informations spécifiques à la machine est perdu.

Juste pour les grimaces, essayez le script suivant ... (fonctionne sur SQL 2005, pas sûr de 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

L'exécution répétée de cette opération (en moins d'une seconde) produit une plage assez large à partir de la première sélection, même avec un intervalle de temps EXTREMEMENT court. Jusqu'à présent, le second choix n'a rien produit.

Impossible si les utilisateurs ont des machines différentes avec des cartes réseau, et même si ce n’est pas le cas, le risque presque théorique est extrêmement marginal.

Personnellement, je chercherais ailleurs, car c’est plus probablement un bogue qu’un conflit de GUID ...

À condition bien sûr de ne pas couper les bits du GUID pour le raccourcir.

Bien sûr que c'est possible et peut-être même probable. Ce n'est pas comme si chaque GUID se trouvait dans une partie aléatoire de l'espace numérique possible. Si deux threads tentaient d'en générer un simultanément, en excluant une sorte de fonction GUID centralisée entourée d'un sémaphore, ils pourraient se retrouver avec la même valeur.

Je ferai précéder ceci par "Je ne suis pas un réseauteur, je peux donc faire des phrases complètement incohérentes à la suite de".

Lorsque je travaillais à l’Illinois State University, nous avions deux ordinateurs de bureau Dell, commandés à des moments différents. Nous avons mis le premier sur le réseau, mais lorsque nous avons essayé de mettre le second sur le réseau, nous avons commencé à recevoir des erreurs folles. Après beaucoup de dépannage, il a été déterminé que les deux machines produisaient le même GUID (je ne sais pas exactement pourquoi, mais cela les a rendues inutilisables sur le réseau). Dell a en réalité remplacé les deux machines car défectueuses.

Il est très peu probable que vous rencontriez des conflits de GUID si vous les générez via quelque chose comme la fonction NEWID () dans SQL Server (bien que possible, comme d'autres réponses l'ont souligné) . Une chose qu’ils n’ont pas soulignée, c’est qu’il est fort probable que des collisions surviennent si vous générez des GUID en JavaScript sur des navigateurs à l'état sauvage. Non seulement il y a parfois des problèmes dans le générateur de ressources aléatoires dans différents navigateurs, mais j'ai également rencontré des problèmes dans lesquels les araignées de Google semblaient mettre en cache les résultats de telles fonctions et finissaient par transmettre à plusieurs reprises le même GUID à nos systèmes.

Voir les différentes réponses ici pour plus de détails:

Collisions lors de la génération d'UUID en JavaScript?

Answer 8

Answer 9

Answer 10

Deux ordinateurs Win95 équipés de cartes Ethernet avec des adresses MAC dupliquées émettent des GUID dupliqués dans des conditions étroitement contrôlées, en particulier si, par exemple, le courant est coupé dans le bâtiment et que les deux démarrent exactement au même moment.

Answer 11

Je connais des gens qui aiment bien dire que les GUID sont magiques et garantis comme uniques, mais en réalité, la plupart des GUID ne sont que des nombres aléatoires de 121 bits (sept de ces bits sont perdus en formatage). Si vous ne vous sentez pas à l'aise avec l'utilisation d'un grand nombre aléatoire, vous ne devriez pas utiliser un GUID.

Le code utilisé pour générer un GUID pourrait-il contenir un bogue? Oui, bien sûr que ça pourrait. Mais la réponse est la même que pour un bogue de compilateur - votre propre code est un ordre de grandeur plus susceptible d’être bogué, alors regardez-le d’abord.

Bien sûr que c'est possible ... Probable? Peu probable, mais c'est possible.

N'oubliez pas que la même machine génère tous les GUID (le serveur), ce qui explique le "caractère aléatoire". qui est basé sur des informations spécifiques à la machine est perdu.

Juste pour les grimaces, essayez le script suivant ... (fonctionne sur SQL 2005, pas sûr de 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

L'exécution répétée de cette opération (en moins d'une seconde) produit une plage assez large à partir de la première sélection, même avec un intervalle de temps EXTREMEMENT court. Jusqu'à présent, le second choix n'a rien produit.

Impossible si les utilisateurs ont des machines différentes avec des cartes réseau, et même si ce n’est pas le cas, le risque presque théorique est extrêmement marginal.

Personnellement, je chercherais ailleurs, car c’est plus probablement un bogue qu’un conflit de GUID ...

À condition bien sûr de ne pas couper les bits du GUID pour le raccourcir.

Bien sûr que c'est possible et peut-être même probable. Ce n'est pas comme si chaque GUID se trouvait dans une partie aléatoire de l'espace numérique possible. Si deux threads tentaient d'en générer un simultanément, en excluant une sorte de fonction GUID centralisée entourée d'un sémaphore, ils pourraient se retrouver avec la même valeur.

Je ferai précéder ceci par "Je ne suis pas un réseauteur, je peux donc faire des phrases complètement incohérentes à la suite de".

Lorsque je travaillais à l’Illinois State University, nous avions deux ordinateurs de bureau Dell, commandés à des moments différents. Nous avons mis le premier sur le réseau, mais lorsque nous avons essayé de mettre le second sur le réseau, nous avons commencé à recevoir des erreurs folles. Après beaucoup de dépannage, il a été déterminé que les deux machines produisaient le même GUID (je ne sais pas exactement pourquoi, mais cela les a rendues inutilisables sur le réseau). Dell a en réalité remplacé les deux machines car défectueuses.

Answer 12

Je connais des gens qui aiment bien dire que les GUID sont magiques et garantis comme uniques, mais en réalité, la plupart des GUID ne sont que des nombres aléatoires de 121 bits (sept de ces bits sont perdus en formatage). Si vous ne vous sentez pas à l'aise avec l'utilisation d'un grand nombre aléatoire, vous ne devriez pas utiliser un GUID.

Answer 13

Le code utilisé pour générer un GUID pourrait-il contenir un bogue? Oui, bien sûr que ça pourrait. Mais la réponse est la même que pour un bogue de compilateur - votre propre code est un ordre de grandeur plus susceptible d’être bogué, alors regardez-le d’abord.

Answer 14

Bien sûr que c'est possible ... Probable? Peu probable, mais c'est possible.

N'oubliez pas que la même machine génère tous les GUID (le serveur), ce qui explique le "caractère aléatoire". qui est basé sur des informations spécifiques à la machine est perdu.

Answer 15

Juste pour les grimaces, essayez le script suivant ... (fonctionne sur SQL 2005, pas sûr de 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

L'exécution répétée de cette opération (en moins d'une seconde) produit une plage assez large à partir de la première sélection, même avec un intervalle de temps EXTREMEMENT court. Jusqu'à présent, le second choix n'a rien produit.

Answer 16

Impossible si les utilisateurs ont des machines différentes avec des cartes réseau, et même si ce n’est pas le cas, le risque presque théorique est extrêmement marginal.

Personnellement, je chercherais ailleurs, car c’est plus probablement un bogue qu’un conflit de GUID ...

À condition bien sûr de ne pas couper les bits du GUID pour le raccourcir.

Answer 17

Bien sûr que c'est possible et peut-être même probable. Ce n'est pas comme si chaque GUID se trouvait dans une partie aléatoire de l'espace numérique possible. Si deux threads tentaient d'en générer un simultanément, en excluant une sorte de fonction GUID centralisée entourée d'un sémaphore, ils pourraient se retrouver avec la même valeur.

Answer 18

Je ferai précéder ceci par "Je ne suis pas un réseauteur, je peux donc faire des phrases complètement incohérentes à la suite de".

Lorsque je travaillais à l’Illinois State University, nous avions deux ordinateurs de bureau Dell, commandés à des moments différents. Nous avons mis le premier sur le réseau, mais lorsque nous avons essayé de mettre le second sur le réseau, nous avons commencé à recevoir des erreurs folles. Après beaucoup de dépannage, il a été déterminé que les deux machines produisaient le même GUID (je ne sais pas exactement pourquoi, mais cela les a rendues inutilisables sur le réseau). Dell a en réalité remplacé les deux machines car défectueuses.

Answer 19

Il est très peu probable que vous rencontriez des conflits de GUID si vous les générez via quelque chose comme la fonction NEWID () dans SQL Server (bien que possible, comme d'autres réponses l'ont souligné) . Une chose qu’ils n’ont pas soulignée, c’est qu’il est fort probable que des collisions surviennent si vous générez des GUID en JavaScript sur des navigateurs à l'état sauvage. Non seulement il y a parfois des problèmes dans le générateur de ressources aléatoires dans différents navigateurs, mais j'ai également rencontré des problèmes dans lesquels les araignées de Google semblaient mettre en cache les résultats de telles fonctions et finissaient par transmettre à plusieurs reprises le même GUID à nos systèmes.

Voir les différentes réponses ici pour plus de détails:

Collisions lors de la génération d'UUID en JavaScript?

Answer 20

Answer 21

Il est très peu probable que vous rencontriez des conflits de GUID si vous les générez via quelque chose comme la fonction NEWID () dans SQL Server (bien que possible, comme d'autres réponses l'ont souligné) . Une chose qu’ils n’ont pas soulignée, c’est qu’il est fort probable que des collisions surviennent si vous générez des GUID en JavaScript sur des navigateurs à l'état sauvage. Non seulement il y a parfois des problèmes dans le générateur de ressources aléatoires dans différents navigateurs, mais j'ai également rencontré des problèmes dans lesquels les araignées de Google semblaient mettre en cache les résultats de telles fonctions et finissaient par transmettre à plusieurs reprises le même GUID à nos systèmes.

Voir les différentes réponses ici pour plus de détails:

Answer 22