Un GUID est-il unique à 100%?

Un GUID est-il unique à 100%?

Restera-t-il unique sur plusieurs threads?

    Bien que chaque GUID généré ne soit pas unique, le nombre total de clés uniques (2 ^ 128 ou 3.4 × 10 ^ 38) est si grand que la probabilité que le même nombre soit généré deux fois est très faible. Par exemple, considérons l’univers observable, qui contient environ 5 × 10 ^ 22 écanvass; chaque écanvas pourrait alors avoir 6,8 × 10 ^ 15 GUID universellement uniques.

    De Wikipedia .


    Ce sont quelques bons articles sur la façon dont un GUID est créé (pour .NET) et comment vous pouvez obtenir le même guid dans la bonne situation.

    http://ericlippert.com/2012/04/24/guid-guide-part-one/

    http://ericlippert.com/2012/04/30/guid-guide-part-two/

    http://ericlippert.com/2012/05/07/guid-guide-part-three/

    La réponse simple est oui.

    Raymond Chen a écrit un excellent article sur les GUID et pourquoi les sous-chaînes de GUID ne sont pas garanties uniques. L’article aborde de manière approfondie la manière dont les GUID sont générés et les données qu’ils utilisent pour assurer l’unicité, ce qui devrait vous aider à expliquer pourquoi ils sont 🙂

    Si vous avez peur des mêmes valeurs GUID, mettez-en deux côte à côte.

     Guid.NewGuid().ToSsortingng() + Guid.NewGuid().ToSsortingng(); 

    Si vous êtes trop paranoïaque, mettez-en trois.

    En guise de note, je jouais avec les GUID de volume dans Windows XP. Ceci est une disposition de partition très obscure avec trois disques et quatorze volumes.

     \\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:) \\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:) \\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:) \\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:) \\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:) \\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:) \\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:) \\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:) \\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:) \\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:) \\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:) \\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:) \\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:) | | | | | | | | | +-- 6f = o | | | +---- 69 = i | | +------ 72 = r | +-------- 61 = a +---------- 6d = m 

    Ce n’est pas que les GUID soient très similaires, mais le fait que tous les GUID contiennent la chaîne “mario”. Est-ce une coïncidence ou y a-t-il une explication à cela?

    Maintenant, lorsque vous parcourez la partie 4 du GUID, j’ai trouvé environ 125 000 visites avec des GUID de volume.

    Conclusion: En ce qui concerne les GUID de volume, ils ne sont pas aussi uniques que les autres GUID.

    Oui, un GUID doit toujours être unique. Il est basé sur le matériel et le temps, plus quelques bits supplémentaires pour vous assurer qu’il est unique. Je suis sûr qu’il est théoriquement possible de se retrouver avec deux identiques, mais extrêmement improbable dans un scénario réel.

    Voici un excellent article de Raymond Chen sur Guids:

    http://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

    Cela ne devrait pas arriver. Cependant, lorsque .NET est soumis à une lourde charge, il est possible d’obtenir des doublons. J’ai deux serveurs Web différents utilisant deux serveurs SQL différents. Je suis allé fusionner les données et j’ai trouvé 15 millions de guids et 7 doublons.

    Les règles sont statistiquement uniques. Les cotes de deux clients différents générant le même Guid sont infiniment petits (en supposant qu’il n’y ait pas de bogues dans le code générateur de Guid). Vous pouvez aussi vous soucier de la puissance de votre processeur à cause d’un rayon cosmique et décider que 2 + 2 = 5 aujourd’hui.

    Plusieurs threads allouant de nouveaux guids obtiendront des valeurs uniques, mais vous devez vous assurer que la fonction que vous appelez est thread-safe. De quel environnement s’agit-il?

    Eric Lippert a écrit une série d’articles très intéressants sur les GUID.

    Il y a sur la commande 2 30 ordinateurs personnels dans le monde (et bien sûr beaucoup d’appareils portables ou d’appareils informatiques non-PC qui ont plus ou moins les mêmes niveaux de puissance de calcul, mais les ignorons). Supposons que nous mettions tous ces ordinateurs dans le monde à la tâche de générer des GUID; Si chacun peut générer, disons, 2 20 GUID par seconde, après seulement 2 72 secondes environ – cent cinquante milliards d’années – vous aurez de grandes chances de générer une collision avec votre GUID spécifique. Et les chances de collision sont plutôt bonnes après seulement 30 000 milliards d’années.

    • Guide GUID, première partie
    • Guide GUID, deuxième partie
    • Guide GUID, troisième partie

    Théoriquement, non, ils ne sont pas uniques. Il est possible de générer un guid identique à plusieurs resockets. Cependant, les chances que cela se produise sont si faibles que vous pouvez supposer qu’elles sont uniques.

    J’ai lu précédemment que les chances sont si faibles que vous devriez vraiment insister sur autre chose – comme votre serveur qui brûle spontanément ou d’autres bogues dans votre code. En d’autres termes, supposons que ce soit unique et ne construise aucun code pour “intercepter” les doublons – consacrez votre temps à quelque chose de plus susceptible de se produire (c.-à-d. Autre chose).

    J’ai tenté de décrire l’utilité des GUID sur mon audience de blog (membres de la famille non techniques). De là (via Wikipedia), les chances de générer un GUID en double:

    • 1 sur 2 ^ 128
    • 1 sur 340 undecillion (ne vous inquiétez pas, undecillion n’est pas sur le quiz)
    • 1 sur 3,4 × 10 ^ 38
    • 1 sur 340 000 000 000 000 000 000 000 000 000 000 000 000

    De http://www.guidgenerator.com/online-guid-generator.aspx

    Qu’est-ce qu’un GUID?

    GUID (ou UUID) est un acronyme pour «Globally Unique Identifier» (ou «Universally Unique Identifier»). C’est un nombre entier de 128 bits utilisé pour identifier les ressources. Le terme GUID est généralement utilisé par les développeurs travaillant avec les technologies Microsoft, alors que l’UUID est utilisé partout ailleurs.

    Quel est le caractère unique d’un GUID?

    128 bits est assez grand et l’algorithme de génération est suffisamment unique pour que, si 1 000 000 000 de GUID par seconde étaient générés pendant un an, la probabilité d’un doublon ne serait que de 50%. Ou si chaque humain sur Terre générait 600 000 000 de GUID, la probabilité d’un doublon serait de 50%.

    Aucun ne semble mentionner le calcul réel de la probabilité que cela se produise.

    Tout d’abord, supposons que nous puissions utiliser tout l’espace de 128 bits (le Guid v4 n’utilise que 122 bits).

    Nous soaps que la probabilité générale de ne pas obtenir de doublon dans n choix est la suivante:

    (1-1 / 2 128 ) (1-2 / 2 128 ) … (1- (n-1) / 2 128 )

    Parce que 2 128 est beaucoup plus grande que n , on peut se rapprocher de ceci:

    (1-1 / 2 128 ) n (n-1) / 2

    Et comme nous pouvons supposer que n est beaucoup plus grand que 0, nous pouvons approximer cela pour:

    (1-1 / 2 128 ) n ^ 2/2

    Maintenant, nous pouvons assimiler cela à la probabilité “acceptable”, disons 1%:

    (1-1 / 2 128 ) n ^ 2/2 = 0,01

    Ce que nous résolvons pour n et obtenir:

    n = sqrt (2 * log 0.01 / log (1-1 / 2 128 ))

    Quel Wolfram Alpha va-t-il arriver à 5.598318 × 10 19

    Pour mettre ce chiffre en perspective, prenons 10000 machines, chacune ayant un processeur à 4 cœurs, effectuant 4 GHz et dépensant 10 000 cycles pour générer un guidage et ne rien faire d’autre. Il faudrait alors environ 111 ans avant de générer un doublon.

    J’ai rencontré un GUID en double.

    J’utilise le scanner de bureau Neat Receipts et il est livré avec un logiciel de firebase database propriétaire. Le logiciel a une fonction de synchronisation avec le cloud et j’ai continué à recevoir une erreur lors de la synchronisation. Un regard sur les journaux a révélé la ligne impressionnante:

    “errors”: [{“code”: 1, “message”: “creator_guid: est déjà pris”, “guid”: “C83E5734-D77A-4B09-B8C1-9623CAC7B167”}]}

    J’étais un peu incrédule, mais sûrement, lorsque j’ai trouvé un moyen d’entrer dans ma firebase database locale neatworks et de supprimer l’enregistrement contenant ce GUID, l’erreur a cessé de se produire.

    Donc, pour répondre à votre question avec des preuves anecdotiques, non. Un duplicata est possible. Mais il est probable que la raison pour laquelle cela s’est produit n’était pas due au hasard, mais parce que les pratiques standard n’étaient pas respectées d’une manière ou d’une autre. (Je ne suis pas si chanceux) Cependant, je ne peux pas dire avec certitude. Ce n’est pas mon logiciel.

    Leur support client était EXTRÊMEMENT courtois et serviable, mais ils ne devaient jamais avoir rencontré ce problème auparavant, car après 3 heures ou plus passées au téléphone avec eux, ils n’ont pas trouvé la solution. (FWIW, je suis très impressionné par Neat, et ce pépin, même frustrant, n’a pas changé mon opinion sur leur produit.)

    Si votre horloge système est correctement configurée et si votre carte réseau a son propre MAC (c’est-à-dire que vous n’avez pas défini de MAC personnalisée) et que votre fournisseur de carte réseau ne recycle pas les MAC mais qui a été connu pour se produire), et si la fonction de génération de GUID de votre système est correctement implémentée, votre système ne générera jamais de GUID en double.

    Si tout le monde sur Terre qui génère des GUID suit ces règles, vos GUID seront globalement uniques.

    En pratique, le nombre de personnes qui enfreignent les règles est faible et leurs GUID ne sont pas susceptibles de “s’échapper”. Les conflits sont statistiquement improbables.

    MSDN :

    Il y a une très faible probabilité que la valeur du nouveau Guid soit à zéro ou égale à tout autre Guid.

    Un GUID est-il unique à 100%?

    Non garanti, car il y a plusieurs façons d’en générer un. Cependant, vous pouvez essayer de calculer les chances de créer deux GUID identiques et vous avez l’idée: un GUID a 128 bits, il ya donc 2 128 GUID distincts, bien plus qu’il n’ya d’écanvass dans l’univers connu. Lisez l’ article de Wikipedia pour plus de détails.

    J’ai constaté que les GUID n’étaient pas uniques lors des tests unitaires multi-thread / multi-process (aussi?). Je suppose que cela a à voir avec, toutes les autres choses étant égales par ailleurs, l’ensemencement identique (ou l’absence de semis) de générateurs pseudo-aléatoires. Je l’utilisais pour générer des noms de fichiers uniques. J’ai trouvé que le système d’exploitation est beaucoup mieux à faire ça 🙂

    Alerte à la traîne

    Vous demandez si les GUID sont 100% uniques. Cela dépend du nombre de GUID dont il doit être unique. À mesure que le nombre de GUID se rapproche de l’infini, la probabilité de duplication de GUID est proche de 100%.

    Les algorithmes GUID sont généralement implémentés conformément à la spécification GUID v4, qui est essentiellement une chaîne pseudo-aléatoire. Malheureusement, ceux-ci entrent dans la catégorie des “probablement non uniques” , de Wikipedia (je ne sais pas pourquoi tant de personnes ignorent ce bit): “… d’autres versions GUID ont des propriétés et des probabilités uniques , allant de l’unicité garantie à probablement non-unicité. ”

    Les propriétés pseudo-aléatoires de JavaScript Math.random() de V8 sont TERRIBLES à l’unicité, les collisions arrivant souvent après quelques milliers d’itérations, mais V8 n’est pas le seul coupable. J’ai vu des collisions GUID réelles en utilisant les implémentations PHP et Ruby des GUID v4.

    Comme il devient de plus en plus courant de réduire la génération d’ID sur plusieurs clients et grappes de serveurs, l’entropie prend un grand succès – les chances qu’une même graine aléatoire soit utilisée pour générer un ID augmentent (le temps est souvent utilisé comme graine aléatoire) dans les générateurs pseudo-aléatoires), et les collisions GUID dégénèrent de “probablement non unique” à “très susceptible de causer beaucoup de problèmes”.

    Pour résoudre ce problème, je me suis efforcé de créer un algorithme d’identification capable d’évoluer en toute sécurité et de mieux garantir les collisions. Pour ce faire, il utilise l’horodatage, un compteur client en mémoire, une empreinte client et des caractères aléatoires. La combinaison de facteurs crée une complexité additive particulièrement résistante aux collisions, même si vous la redimensionnez sur plusieurs hôtes:

    http://usecuid.org/

    Dans un sens plus général, on parle de “problème d’anniversaire” ou de “paradoxe de l’anniversaire”. Wikipedia a une bonne vue d’ensemble sur: Wikipedia – Birthday Problem

    En termes très grossiers, la racine carrée de la taille du pool est une approximation approximative du moment où vous pouvez vous attendre à une probabilité de 50% de duplication. L’article comprend un tableau de probabilités de la taille du pool et des différentes probabilités, y compris une ligne pour 2 ^ 128. Donc, pour une probabilité de collision de 1%, vous vous attendriez à choisir au hasard 2,6 * 10 ^ 18 nombres de 128 bits. Une probabilité de 50% nécessite 2,2 * 10 ^ 19, tandis que SQRT (2 ^ 128) est de 1,8 * 10 ^ 19.

    Bien sûr, ce n’est que le cas idéal d’un processus vraiment aléatoire. Comme d’autres l’ont mentionné, il ya beaucoup de choses à faire au hasard – à quel point le générateur et la graine sont-ils bons? Ce serait bien s’il y avait un support matériel pour aider avec ce processus qui serait plus à l’épreuve des balles, sauf que tout peut être falsifié ou virtualisé. Je soupçonne que cela pourrait être la raison pour laquelle les adresses MAC et les horodatages ne sont plus intégrés.

    La réponse de “Est-ce qu’un GUID est 100% unique?” est simplement “non” .

    • Si vous souhaitez que le GUID soit unique à 100%, procédez comme suit.

      1. générer le GUID
      2. vérifier si ce GUID existe dans la colonne de la table où vous recherchez uniquensess
      3. si existe alors aller à l’étape 1 sinon étape 4
      4. utilisez ce GUID comme unique.