Les collisions GUID sont-elles possibles?

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?

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.

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

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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?