Les collisions GUID sont-elles possibles?

128

Je travaille sur une base de données dans SQL Server 2000 qui utilise un GUID pour chaque utilisateur qui utilise l'application à laquelle il est lié. 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 une chance extrêmement faible de provoquer des collisions, mais une collision est-elle toujours possible?

Jason Baker
la source
11
Tout le monde dit non, c'est faux.J'ai déjà heurté 1 UniqueIdentifier avec un ensemble de données de moins d'un demi-million d'enregistrements, MSSQL 2008 R2
Behrooz
2
@Behrooz Yikes. Ce n'est pas impossible grâce à notre ami le paradoxe de l'anniversaire, mais c'est toujours incroyablement malchanceux avec des GUID v4 entièrement aléatoires. Peut-être que vous utilisiez une stratégie de génération de GUID plus faible?
Craig Ringer
6
@Behrooz Wow. C'est une chance choquante.
Craig Ringer
6
@Behrooz c'est probablement un nombre pseudo aléatoire défectueux utilisé dans MSSQL (je ne serais pas surpris s'ils ont une graine de 32 bits dans leur générateur ou autre étant donné la qualité de leur logiciel). Le calcul ne ment pas. Cette possibilité est si petite que vous pouvez être 99,9999999999 (et beaucoup de 9 après)% que soit le générateur de guides MSSQL est défectueux (ou peut être un générateur pseudo aléatoire utilisé pour générer des GUID) ou que vous avez fait une erreur.
Alex
2
J'adore comment à ce moment précis, la question et la réponse sélectionnée ont 128 points. Coïncidence? 🤔
Caio Cunha

Réponses:

127

En gros, non. Je pense que quelqu'un a foutu votre base de données. Selon le GUID de version que vous utilisez, la valeur est soit unique (pour des éléments tels que les GUID de la version 1), soit à la fois unique et imprévisible (pour des éléments tels que les GUID de la version 4). L'implémentation de SQL Server pour leur fonction NEWID () semble utiliser un nombre aléatoire de 128 bits, vous n'obtiendrez donc pas de collision.

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

Tom Ritter
la source
3
C'est ce que j'ai pensé, mais je voulais juste m'assurer que je ne pouvais pas l'exclure. Vous ne savez jamais quels types de bogues étranges pourraient apparaître dans un logiciel vieux de 8 ans. :)
Jason Baker
6
En fait, ce n'est plus vrai. C'était vrai pour les GUID v1, mais pas pour ceux v4 actuels. Voir en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm pour plus d'informations.
Greg Beech
97
Votez contre parce que, en principe (dans sa forme la plus brute), vous avez tort de dire "non" à la question "Les collisions GUID sont-elles possibles?". C'est très possible. La probabilité est minime, mais c'est possible. Je déteste avoir l'air pédant - mais SO, c'est être concis et précis.
13
entrez "résoudre [1-exp [- (n ^ 2 / (2 * 2 ^ 128))]> 0.01, n]" dans wolfram alpha pour obtenir le résultat pour 1% ... Attention, bien que ce nombre semble grand dans contexte d'une application, ce n'est certainement pas grand pour le monde entier. Si tous les ordinateurs de la Terre généraient de vrais GUID, ils provoqueraient une collision avec une probabilité de 1% en une seconde environ, en supposant qu'ils puissent générer un GUID chaque nanoseconde (ce qui est probablement assez réaliste de nos jours). Donc, si vous utilisez des GUID pour vos ID de base de données, ils sont uniques. Les GUID pour chaque calcul effectué sur Terre entreront en collision immédiatement.
thesaint
11
Dire «non», ce n'est pas possible, puis dire qu'il y a 1% de chances d'obtenir une collision lorsqu'un certain montant est généré, sont des conflits directs. La réponse correcte doit être théoriquement - oui, une collision peut se produire au hasard. Cependant, les chances d'une collision sont statistiquement plus faibles qu'un astéroïde frappant la Terre, rebondissant sur la Terre et rebondissant sur la Lune pour frapper la Terre une deuxième fois, dans l'heure suivante.
Baaleos
112

Fondamentalement, ils ne sont pas possibles! , les chances sont astronomiquement faibles .

Mais ... je suis la seule personne que je connaisse dans le monde, qui a eu une colision GUID une fois (oui!).

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

Comment cela s'est-il passé, dans une petite application qui fonctionnait sur Pocket PC, à la fin d'une opération, une commande avec un GUID généré doit être émise. La commande après son exécution sur le serveur, elle 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 émis la commande de module (avec le GUID nouvellement généré) et rien ne s'est passé. Je l'ai fait à nouveau (avec le même guid, car le guid n'a été généré qu'une seule 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 des commandes, et le même GUID que l'actuel a été inséré il y a 3 semaines. Ne croyant pas 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 GUID a été fraîchement généré sans aucun doute à ce sujet.

Edit: certains facteurs auraient pu augmenter considérablement les chances que cela se produise, l'application fonctionnait sur l'émulateur PocketPC et l'émulateur dispose d'une fonction de sauvegarde de l'état, ce qui signifie que chaque fois que l'état est restauré, l'heure locale est également restaurée et le guid est basé sur le temporisateur interne .... aussi l'algorithme de génération de guid pour le framework compact pourrait être moins complet que par exemple celui COM ...

Pop Catalin
la source
38
Vote positif. Enregistrer l'état et relire générerait vraiment des guids en double.
Joshua
35
Ce qui s'est probablement passé, c'est qu'il s'agissait d'une "mauvaise" implémentation GUID. Les cotes théoriques étaient très faibles, mais sur Pocket PC ?? Qui peut dire qu'ils n'ont pas pris un raccourci qui a poussé ces chances dans la catégorie «improbable, mais possible».
Dave Dopson
9
Ce n'est pas parce que quelque chose a une très faible probabilité de se produire que cela ne se produira pas.
Renan
3
Comme je l'ai dit ci-dessus, les chances que cela se produise sont si faibles qu'il est prudent de supposer que vous avez fait une erreur ou que MSSQL utilise un PRNG défectueux ( en.wikipedia.org/wiki/Pseudorandom_number_generator ). Par exemple, il est probable que ce PRNG soit initialisé avec une graine de petite taille. Les PRNG défectueux ne sont pas rares (voir schneier.com/paper-prngs.html ) - par exemple, un défaut a été récemment découvert dans le SDK Android - android-developers.blogspot.com/2013/08 / ...
Alex
2
@Alex, l'erreur était "Save State and Restore" de l'émulateur, qui restaure toute l'image de l'émulateur, y compris l'horloge de l'émulateur. Ainsi, après des milliers d'opérations de restauration sur un an, une collision guid a été générée. Vous avez raison, il y a eu une erreur!
Pop Catalin
34

Ils sont théoriquement possibles, mais avec 3,4E38 nombres possibles, si vous créez des dizaines de billions de GUID en un an, la probabilité d'avoir un doublon est de 0,0000000000006 ( Source ).

Si deux utilisateurs finissaient avec le même GUID, je parierais qu'il y a un bogue dans le programme qui provoque la copie ou le partage des données.

Ben Hoffstein
la source
"mais avec 3,4E38 numéros possibles" - non. Deux GUID générés presque simultanément sur la même machine se retrouveraient avec des GUID extrêmement similaires.
Kirk Strauser
4
Cela dépendra de la façon dont le GUID est généré, et certaines implémentations basées sur le temps CPU ou les millisecondes exagéreront (espérons-le) tout calcul basé sur deux GUID générés à quelques millisecondes l'un de l'autre.
Dalin Seivewright
4
Avec plus d'un processeur sur une machine, si un GUID est basé sur l'heure et l'adresse MAC, alors chaque cœur peut émettre le même GUID au même moment.
AndyM
12
Je suis à peu près sûr que toute implémentation de GUID décente ne le sera pas
Guillaume86
1
@MatthewLock Le paradoxe de l'anniversaire est couvert dans la source. Vérifiez le lien.
Zero3 du
21

Regardons d'abord 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 pour 50% de chances que deux GUID entrent en collision, la probabilité est en fait de 1 sur 2 ^ 64 (10 ^ 19) qui est beaucoup plus petit. Cependant, il s'agit toujours d'un très grand nombre et, en tant que tel, la probabilité de collision en supposant que vous utilisez un nombre raisonnable de GUID est faible.

Notez également que les GUID ne contiennent pas d'horodatage ou d'adresse MAC comme beaucoup de gens semblent également le croire. C'était vrai pour les GUID v1, mais maintenant les GUID v4 sont utilisés, qui sont simplement un nombre pseudo-aléatoire, ce qui signifie que la possibilité de collision est sans doute plus élevée car ils ne sont plus uniques à un moment et à une machine.

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

Edit: fixe pour dire 2 ^ 64

Greg Beech
la source
2
Bien que je sois d'accord avec tous vos faits, soyez prudent avec vos calculs. Dire que vous avez 1 chance sur 10 ^ 19 que deux GUID entrent en collision dépend du nombre de GUID dans l'ensemble. Pour cette chance, vous avez besoin d'environ 2 ^ 32 GUID, donc dans presque tous les scénarios du monde réel, les chances sont beaucoup plus faibles.
DocMax
1
Vous avez une faute de frappe 1 in 10^64 (10^19), ce que je pense devrait être 1 in 2^64 (10^19). Je suis également très confus quant à la façon dont vous pensez que le paradoxe de l'anniversaire s'applique à seulement 2 chiffres. Je suppose que vous avez regardé en.wikipedia.org/wiki/Birthday_paradox . Le tableau indique le nombre de guides dont vous avez besoin pour une probabilité donnée de doublon. À partir de cette table, une probabilité de 1 sur 10 ^ 18 nécessite 2,6 * 10 ^ 10 guids, pas quelque chose de proche de seulement deux GUID.
Tony Lee
Un point - les guids v1 sont toujours largement utilisés et reposent sur l'adresse MAC, en particulier dans les bases de données car ils ont des caractéristiques souhaitables. Voir UuidCreateSequential et son wrapper SQL Server NewSequentialID ( msdn.microsoft.com/en-us/library/windows/desktop/… ).
EBarr
18

Les chances de collision de deux GUID aléatoires (~ 1 sur 10 ^ 38) sont inférieures à celles de ne pas détecter un paquet TCP / IP corrompu (~ 1 sur 10 ^ 10). http://wwwse.inf.tu-dresden.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 que vous lisez à partir de la base de données ne sont statistiquement correctes.

Tony Lee
la source
Etes-vous sûr que je ne pourrais pas armer mon réseau si moins de 1 paquet sur 10 ^ 28 est corrompu?
Joshua
13

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

Jason Jackson
la source
1
En fait, dans cette situation, le rasoir d'Occam n'est pas du tout un bon guide! Le rasoir d'Occam dit que le cas avec le moins d'hypothèses est le plus susceptible d'être correct. Dans cette situation, le cas d'une collision GUID est en fait beaucoup plus simple, mais le rasoir d'Occam ne s'applique pas à une situation comme celle-ci où nous savons déjà que l'un des cas est incroyablement improbable.
lockstock
11

Voir l'article de Wikipédia sur l' identifiant mondial unique . Il existe plusieurs façons de générer des GUID. Apparemment, l'ancienne (?) Façon utilisait l'adresse Mac, un horodatage jusqu'à une unité très courte et un compteur unique (pour gérer les générations rapides sur le même ordinateur), donc les dupliquer est presque impossible. Mais ces GUID ont été supprimés car ils pouvaient être utilisés pour traquer les utilisateurs ...

Je ne suis pas sûr du nouvel algorithme utilisé par Microsoft (l'article dit qu'une séquence de GUID peut être prédite, on dirait qu'ils n'utilisent plus d'horodatage? L'article de Microsoft lié ci-dessus dit autre chose ...).

Maintenant, les GUID sont soigneusement conçus pour être, par leur nom, uniques au monde, donc je risquerai que ce soit impossible ou de très très très faible probabilité. Je chercherais ailleurs.

PhiLho
la source
6
Eric post 1
Nat
4
Eric post 2
Nat
4
Eric post 3
Nat
9

Deux machines Win95 qui ont des cartes Ethernet avec des adresses MAC en double émettront des GUIDS en double dans des conditions étroitement contrôlées, en particulier si, par exemple, l'alimentation se coupe dans le bâtiment et les deux démarrent exactement au même moment.

Joshua
la source
Est-il courant que deux machines différentes aient la même adresse MAC Ethernet?
Dave Lucre
@DaveLucre: Non, mais des incidents ont été enregistrés.
Joshua
Je suis vraiment curieux de savoir comment cela se produit. Est-il plus probable avec des machines virtuelles qui génèrent de manière aléatoire un MAC pour chaque carte réseau? Je n'ai jamais entendu parler de NIC physiques fabriqués avec des MAC en double! En quelque sorte, jette une énorme clé dans les travaux si cela est possible!
Dave Lucre
Hou la la! Merci pour le lien @Joshua! Quelle foutue colossale!
Dave Lucre
@DaveLucre J'ai utilisé des NIC USB très bon marché où TOUS sont fabriqués avec le même MAC. Mais bien sûr, cela n'a rien à voir avec les mathématiques de l'aléatoire, et tout à voir avec la paresse du fabricant.
rudolfbyker
5

Je vais commencer par "Je ne suis pas un réseauteur, alors je peux faire des phrases complètement incohérentes.".

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 rend toutes deux inutilisables sur le réseau). Dell a en fait remplacé les deux machines comme étant défectueuses.

John Kraft
la source
3
C'était spécifiquement le GUID. Cela avait quelque chose à voir avec le GUID généré par les machines lorsqu'elles rejoignaient le réseau. Il a fallu plusieurs semaines à Dell pour remplacer les machines, car ils ont dit qu'il était impossible que les GUID soient les mêmes. Nous avons pu reproduire le problème, Dell a repris les machines et avons pu produire les mêmes résultats sur leurs réseaux. Ils ont fini par remplacer les deux machines. Comme je l'ai dit, je ne suis pas un réseauteur, mais je me souviens précisément que c'était un problème avec les GUID.
John Kraft
5

Je sais que les gens aiment la bonne réponse selon laquelle les GUID sont magiques et garantis uniques, mais en réalité, la plupart des GUID ne sont que des nombres aléatoires de 121 bits (sept des bits sont gaspillés lors du formatage). Si vous ne vous sentez pas à l'aise d'utiliser un grand nombre aléatoire, vous ne devriez pas vous sentir à l'aise avec un GUID.

Rick Yorgason
la source
11
Je vous recommande également de ne pas utiliser de réseaux. Ou des ordinateurs. Les bits de parité ne peuvent pas faire grand-chose!
Rushyo
Tu as mal compris. Il y a deux choses que j'essayais de dire dans cet article: 1) Si vous avez besoin d'un grand nombre aléatoire, utilisez un grand nombre aléatoire. L'utilisation d'un GUID comme grand nombre aléatoire est inutilement trompeuse. (2)
Rick Yorgason
4
Ce dont je suis pleinement conscient. Vous avez dit «si vous ne vous sentiez pas à l'aise d'utiliser un grand nombre aléatoire». mais les GUID sont si uniques que vous constaterez que presque tout le reste d'un ordinateur est plus aléatoire, même les opérations que vous tenez pour acquises. Il y a plus de chances qu'un problème de mémoire anormal brise votre colonne d'identité qu'une (vraie) collision GUID se produise. Vous ne devriez pas vous sentir «mal à l'aise» à leur sujet. S'ils ne sont pas idéaux pour le scénario, très bien - mais ils n'ont pas besoin de prudence particulière.
Rushyo
3
Je suppose que cela ne va nulle part, mais ce que les gens essaient de vous expliquer, c'est que les mécanismes de détection d'erreurs dans le matériel commun comme les cartes réseau ou les disques durs utilisent des algorithmes qui ont plus de chances de ne pas détecter une erreur que vous d'obtenir une collision GUID, donc si vous comptez sur ceux-ci, vous pouvez aussi compter sur les GUID
Guillaume86
1
@ Rick, dépend de la taille de votre numéro. Certainement pas avec un entier de 4 octets ou un bigint de 8 octets. GUID = 16 octets, vous aurez donc besoin d'une implémentation personnalisée de grand nombre de 16 octets pour obtenir les mêmes 2 ^ 128 combinaisons possibles. Donc, d'une manière générale, si vous utilisez des nombres aléatoires int "normaux" ou bigint, le risque de collision avec un GUID est plus faible (en excluant les considérations d'algo aléatoires pour chacun).
Wim Hollebrandse
3

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

Mark Ransom
la source
2

Bien sûr, 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), de sorte qu'une grande partie du «caractère aléatoire» basé sur des informations spécifiques à la machine est perdue.

FlySwat
la source
1

Juste pour sourire, 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 (prend moins d'une seconde) produit une plage assez large à partir de la première sélection, même avec un intervalle de temps EXTRÊMEMENT court. Jusqu'à présent, la deuxième sélection n'a rien produit.

GalactiqueCowboy
la source
1
Vous avez besoin de 15 zéros supplémentaires à la fin du compteur pour avoir 50% de chances d'un doublon. Mais, pour l'amour de Pete, ne le faites pas!
Jim Birchall
0

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

Personnellement, je chercherais ailleurs car il s'agit plus probablement d'un bug plutôt que d'un conflit GUID ...

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

Richard Harrison
la source
Les GUID seraient générés sur le serveur, de sorte que les cartes réseau de l'utilisateur n'entrent pas en jeu.
Tom Ritter
0

Bien sûr, 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. Dans le cas où deux threads tentaient d'en générer un simultanément, à l'exception d'une sorte de fonction GUID centralisée avec un sémaphore autour, ils pourraient se retrouver avec la même valeur.

Kirk Strauser
la source
0

Il est très peu probable que vous rencontriez des collisions de GUID si vous les générez via quelque chose comme le NEWID() fonction de SQL Server (bien que bien sûr possible, comme l'ont souligné d'autres réponses). Une chose qu'ils n'ont pas soulignée est qu'il est en fait très probable que vous rencontriez des collisions si vous générez des GUID en JavaScript sur des navigateurs sauvages. Non seulement il y a parfois des problèmes dans le RNG dans différents navigateurs, mais j'ai également rencontré des problèmes où les araignées Google semblent mettre en cache les résultats de fonctions comme celle-ci et ont fini 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?

Ken Smith
la source