Preuve simple que le GUID n'est pas unique [fermé]

Je voudrais prouver qu'un GUID n'est pas unique dans un programme de test simple. Je m'attendais à ce que le code suivant s'exécute pendant des heures, mais il ne fonctionne pas. Comment puis-je le faire fonctionner?

BigInteger begin = new BigInteger((long)0);
BigInteger end = new BigInteger("340282366920938463463374607431768211456",10);  //2^128
for(begin; begin<end; begin++)
  Console.WriteLine(System.Guid.NewGuid().ToString());

J'utilise C #.

Kai, j'ai fourni un programme qui fera ce que vous voulez en utilisant des threads. Il est autorisé sous les conditions suivantes: vous devez me payer 0,0001 $ par heure par cœur de processeur sur lequel vous l'exécutez. Les frais sont payables à la fin de chaque mois civil. Veuillez me contacter pour les détails de mon compte paypal dans les plus brefs délais.

using System;
using System.Collections.Generic;
using System.Linq;

namespace GuidCollisionDetector
{
    class Program
    {
        static void Main(string[] args)
        {
            //var reserveSomeRam = new byte[1024 * 1024 * 100];     // This indeed has no effect.

            Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now);
            // Fill up memory with guids.
            var bigHeapOGuids = new HashSet<Guid>();
            try
            {
                do
                {
                    bigHeapOGuids.Add(Guid.NewGuid());
                } while (true);
            }
            catch (OutOfMemoryException)
            {
                // Release the ram we allocated up front.
                // Actually, these are pointless too.
                //GC.KeepAlive(reserveSomeRam);
                //GC.Collect();
            }
            Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount());


            // Spool up some threads to keep checking if there's a match.
            // Keep running until the heat death of the universe.
            for (long k = 0; k < Int64.MaxValue; k++)
            {
                for (long j = 0; j < Int64.MaxValue; j++)
                {
                    Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount);
                    System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) =>
                    {
                        if (bigHeapOGuids.Contains(Guid.NewGuid()))
                            throw new ApplicationException("Guids collided! Oh my gosh!");
                    }
                    );
                    Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount);
                }
            }
            Console.WriteLine("Umm... why hasn't the universe ended yet?");
        }
    }
}

PS: Je voulais essayer la bibliothèque d'extensions parallèles. C'était facile.

Et utiliser OutOfMemoryException en tant que flux de contrôle semble tout simplement faux.

ÉDITER

Eh bien, il semble que cela attire toujours des votes. J'ai donc résolu le problème GC.KeepAlive (). Et l'a changé pour fonctionner avec C # 4.

Et pour clarifier mes conditions de support: le support n'est disponible que le 28 / Feb / 2010. Veuillez utiliser une machine à remonter le temps pour faire des demandes d'assistance ce jour-là uniquement.

EDIT 2 Comme toujours, le GC fait un meilleur travail que moi pour gérer la mémoire; toute tentative antérieure de le faire moi-même était vouée à l'échec.

Cela durera beaucoup plus que des heures. En supposant qu'il boucle à 1 GHz (ce qu'il ne fera pas - ce sera beaucoup plus lent que cela), il fonctionnera pendant 10790283070806014188970 ans. Ce qui est environ 83 milliards de fois plus long que l'âge de l'univers.

En supposant que la loi Moores soit valable, il serait beaucoup plus rapide de ne pas exécuter ce programme, d'attendre plusieurs centaines d'années et de l'exécuter sur un ordinateur qui est des milliards de fois plus rapide. En fait, tout programme dont l'exécution prend plus de temps qu'il ne faut pour doubler la vitesse du processeur (environ 18 mois) se terminera plus tôt si vous attendez que la vitesse du processeur ait augmenté et achetez un nouveau processeur avant de l'exécuter (sauf si vous l'écrivez pour qu'il peut être suspendu et repris sur un nouveau matériel).

Un GUID n'est théoriquement pas unique. Voici votre preuve:

• Le GUID est un nombre de 128 bits
• Vous ne pouvez pas générer 2 ^ 128 + 1 ou plusieurs GUID sans réutiliser d'anciens GUID

Cependant, si toute la puissance de sortie du soleil était destinée à effectuer cette tâche, il refroidirait bien avant la fin.

Les GUID peuvent être générés à l'aide d'un certain nombre de tactiques différentes, dont certaines prennent des mesures spéciales pour garantir qu'une machine donnée ne générera pas deux fois le même GUID. Trouver des collisions dans un algorithme particulier montrerait que votre méthode particulière pour générer des GUID est mauvaise, mais ne prouverait rien sur les GUID en général.

Bien sûr, les GUID peuvent entrer en collision. Étant donné que les GUID sont de 128 bits, il suffit d'en générer 2^128 + 1et par le principe du pigeonhole il doit y avoir une collision.

Mais lorsque nous disons qu'un GUID est unique, ce que nous voulons vraiment dire, c'est que l'espace clé est si grand qu'il est pratiquement impossible de générer accidentellement le même GUID deux fois (en supposant que nous générons des GUID au hasard).

Si vous générez une séquence de nGUID de manière aléatoire, la probabilité d'au moins une collision est approximativement p(n) = 1 - exp(-n^2 / 2 * 2^128)(c'est le problème d'anniversaire avec le nombre d'anniversaires possibles 2^128).

   n     p(n)
2^30 1.69e-21
2^40 1.77e-15
2^50 1.86e-10
2^60 1.95e-03

Pour rendre ces chiffres concrets, 2^60 = 1.15e+18. Donc, si vous générez un milliard de GUID par seconde, il vous faudra 36 ans pour générer 2^60des GUID aléatoires et même alors, la probabilité que vous ayez une collision est toujours 1.95e-03. Vous êtes plus susceptible d'être assassiné à un moment donné de votre vie ( 4.76e-03) que de trouver une collision au cours des 36 prochaines années. Bonne chance.

Si vous vous inquiétez de l'unicité, vous pouvez toujours acheter de nouveaux GUID afin de pouvoir jeter vos anciens. J'en mettrai sur eBay si vous le souhaitez.

Personnellement, je pense que le "Big Bang" a été provoqué lorsque deux GUID sont entrés en collision.

Vous pouvez montrer qu'en O (1) le temps avec une variante de l' algorithme de bogosort quantique .

Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();

Deux GUID quelconques sont très probablement uniques (pas égaux).

Voir cette entrée SO , et de Wikipedia

Bien que chaque GUID généré ne soit pas garanti d'être unique, le nombre total de clés uniques (2 ^ 128 ou 3,4 × 10 ^ 38) est si grand que la probabilité qu'un 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 étoiles; chaque étoile pourrait alors avoir 6,8 × 10 ^ 15 GUID universellement uniques.

Donc, vous devrez probablement attendre encore plusieurs milliards d'années et espérer que vous en frapperez un avant l'univers, car nous savons qu'il arrive à sa fin.

[Mise à jour:] Comme le soulignent les commentaires ci-dessous, les nouveaux GUID MS sont V4 et n'utilisent pas l'adresse MAC dans le cadre de la génération de GUID (je n'ai cependant vu aucune indication d'une implémentation V5 de MS, donc si quelqu'un a un lien confirmant que faites le moi savoir). Cependant, avec la V4, le temps est toujours un facteur et les chances de ne pas dupliquer les GUID restent si faibles qu'elles ne sont pas pertinentes pour une utilisation pratique. Vous ne seriez certainement pas susceptible de générer un GUID en double à partir d'un seul test système tel que l'OP tentait de le faire.

La plupart de ces réponses manquent un point essentiel sur l'implémentation GUID de Microsoft. La première partie du GUID est basée sur un horodatage et une autre partie est basée sur l'adresse MAC de la carte réseau (ou un nombre aléatoire si aucune carte réseau n'est installée).

Si je comprends bien, cela signifie que la seule façon fiable de dupliquer un GUID serait d'exécuter des générations de GUID simultanées sur plusieurs machines où les adresses MAC étaient les mêmes ET où les horloges sur les deux systèmes étaient au même moment exact lorsque la génération s'est produite (l'horodatage est basé sur des millisecondes si je comprends bien) .... même alors, il y a beaucoup d'autres bits dans le nombre qui sont aléatoires, donc les chances sont toujours très faibles.

À toutes fins pratiques, les GUID sont universellement uniques.

Il y a une assez bonne description du GUID MS sur le blog "The Old New Thing"

Voici une petite méthode d'extension astucieuse que vous pouvez utiliser si vous souhaitez vérifier l'unicité de guid à de nombreux endroits de votre code.

internal static class GuidExt
{
    public static bool IsUnique(this Guid guid)
    {
        while (guid != Guid.NewGuid())
        { }
        return false;
    }
}

Pour l'appeler, il suffit d'appeler Guid.IsUnique chaque fois que vous générez un nouveau guid ...

Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
    throw new GuidIsNotUniqueException();
}

... diable, je recommanderais même de l'appeler deux fois pour m'assurer qu'il a bien fonctionné au premier tour.

Compter jusqu'à 2 ^ 128 - ambitieux.

Imaginons que nous pouvons compter 2 ^ 32 ID par seconde et par machine - pas si ambitieux, car ce n'est même pas 4,3 milliards par seconde. Permet de dédier 2 ^ 32 machines à cette tâche. En outre, permet à 2 ^ 32 civilisations de consacrer chacune les mêmes ressources à la tâche.

Jusqu'à présent, nous pouvons compter 2 ^ 96 ID par seconde, ce qui signifie que nous compterons pendant 2 ^ 32 secondes (un peu plus de 136 ans).

Maintenant, tout ce dont nous avons besoin est d'obtenir 4 294 967 296 civilisations pour consacrer chacune 4 294 967 296 machines, chaque machine capable de compter 4 294 967 296 ID par seconde, uniquement pour cette tâche pour les 136 prochaines années environ - je suggère que nous commencions cette tâche essentielle dès maintenant; -)

Eh bien, si le temps d'exécution de 83 milliards d'années ne vous fait pas peur, pensez que vous devrez également stocker les GUID générés quelque part pour vérifier si vous en avez un double; stocker 2 ^ 128 nombres de 16 octets ne vous demanderait d'allouer que 4951760157141521099596496896 téraoctets de RAM à l'avance, donc imaginez que vous avez un ordinateur qui pourrait s'adapter à tout cela et que vous trouvez en quelque sorte un endroit pour acheter des modules DIMM de téraoctets à 10 grammes chacun, combinés, ils peser plus de 8 masses terrestres, vous pouvez donc le déplacer sérieusement hors de l'orbite actuelle, avant même d'appuyer sur "Exécuter". Réfléchissez bien!

for(begin; begin<end; begin)
    Console.WriteLine(System.Guid.NewGuid().ToString());

Vous n'incrémentez pas, begindonc la condition begin < endest toujours vraie.

Si les collisions GUID sont un problème, je recommanderais plutôt d' utiliser le ScottGuID .

Vraisemblablement, vous avez des raisons de croire que l'algorithme de production de Guids ne produit pas de nombres vraiment aléatoires, mais qu'il tourne en fait avec une période << 2 ^ 128.

Par exemple, la méthode RFC4122 utilisée pour dériver des GUID qui fixe les valeurs de certains bits.

La preuve du cyclisme dépendra de la taille possible de la période.

Pour de petites périodes, la table de hachage de hachage (GUID) -> GUID avec remplacement lors d'une collision si les GUID ne correspondent pas (se terminent s'ils le font) peut être une approche. Pensez également à n'effectuer le remplacement qu'une fraction aléatoire du temps.

En fin de compte, si la période maximale entre les collisions est suffisamment grande (et n'est pas connue à l'avance), n'importe quelle méthode ne donnera qu'une probabilité que la collision soit trouvée si elle existait.

Notez que si la méthode de génération de Guids est basée sur l'horloge (voir la RFC), il peut ne pas être possible de déterminer si des collisions existent, car (a) vous ne pourrez pas attendre assez longtemps pour que l'horloge se termine, ou (b) vous ne pouvez pas demander suffisamment de Guids dans un tick d'horloge pour forcer une collision.

Vous pouvez également être en mesure d'afficher une relation statistique entre les bits du Guid ou une corrélation de bits entre les Guids. Une telle relation pourrait rendre hautement probable que l'algorithme est défectueux sans nécessairement pouvoir trouver une collision réelle.

Bien sûr, si vous voulez simplement prouver que les Guids peuvent entrer en collision, alors une preuve mathématique, pas un programme, est la réponse.

Je ne comprends pas pourquoi personne n'a mentionné la mise à niveau de votre carte graphique ... Si vous aviez un NVIDIA Quadro FX 4800 haut de gamme ou quelque chose (192 cœurs CUDA), cela irait plus vite ...

Bien sûr, si vous pouviez vous permettre quelques NVIDIA Qadro Plex 2200 S4 (à 960 cœurs CUDA chacun), ce calcul crierait vraiment . NVIDIA serait peut-être prêt à vous en prêter quelques-uns pour une "démonstration technologique" en tant que coup de pub?

Ils voudraient sûrement faire partie de ce calcul historique ...

Mais devez-vous être sûr d'avoir un double, ou ne vous en souciez que s'il peut y en avoir un. Pour être sûr que vous avez deux personnes avec le même anniversaire, vous avez besoin de 366 personnes (sans compter l'année bissextile). Pour qu'il y ait plus de 50% de chances d'avoir deux personnes avec le même anniversaire, vous n'avez besoin que de 23 personnes. Voilà le problème d'anniversaire .

Si vous avez 32 bits, vous n'avez besoin que de 77 163 valeurs pour avoir plus de 50% de chances de doublon. Essaye le:

Random baseRandom = new Random(0);

int DuplicateIntegerTest(int interations)
{
    Random r = new Random(baseRandom.Next());
    int[] ints = new int[interations];
    for (int i = 0; i < ints.Length; i++)
    {
        ints[i] = r.Next();
    }
    Array.Sort(ints);
    for (int i = 1; i < ints.Length; i++)
    {
        if (ints[i] == ints[i - 1])
            return 1;
    }
    return 0;
}

void DoTest()
{
    baseRandom = new Random(0);
    int count = 0;
    int duplicates = 0;
    for (int i = 0; i < 1000; i++)
    {
        count++;
        duplicates += DuplicateIntegerTest(77163);
    }
    Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates);
}

1000 iterations had 737 with duplicates

Maintenant, 128 bits, c'est beaucoup, donc vous parlez toujours d'un grand nombre d'articles, ce qui vous donne toujours un faible risque de collision. Vous auriez besoin du nombre d'enregistrements suivant pour les cotes données en utilisant une approximation:

• 0,8 milliard de milliards pour un risque de collision de 1/1 000
• 21,7 milliards de milliards pour 50% de risques de collision
• 39,6 milliards de milliards pour 90% de risques de collision

Il y a environ 1 e14 e-mails envoyés par an, il faudrait donc environ 400 000 ans à ce niveau avant d'avoir 90% de chances d'en avoir deux avec le même GUID, mais c'est très différent de dire que vous devez faire fonctionner un ordinateur 83 milliards fois l'âge de l'univers ou que le soleil se refroidirait avant d'en trouver un doublon.

Ne manquez-vous pas tous un point majeur?

Je pensais que les GUID ont été générés en utilisant deux choses qui rendent les chances qu'ils soient uniques à l'échelle mondiale assez élevées. La première est qu'ils sont ensemencés avec l'adresse MAC de la machine sur laquelle vous vous trouvez et deux ils utilisent l'heure à laquelle ils ont été générés plus un nombre aléatoire.

Donc, sauf si vous l'exécutez sur la machine réelle et exécutez toutes vos suppositions dans le plus petit laps de temps que la machine utilise pour représenter une heure dans le GUID, vous ne générerez jamais le même nombre, quel que soit le nombre de suppositions que vous prenez en utilisant l'appel système.

Je suppose que si vous connaissez la façon dont un GUID est fait, cela raccourcirait considérablement le temps de deviner.

Tony

Vous pouvez hacher les GUID. De cette façon, vous devriez obtenir un résultat beaucoup plus rapidement.

Oh, bien sûr, exécuter plusieurs threads en même temps est également une bonne idée, de cette façon, vous augmenterez les chances qu'une condition de concurrence critique génère deux fois le même GUID sur des threads différents.

Les GUID sont de 124 bits car 4 bits contiennent le numéro de version.

1. Allez au laboratoire de cryogénie à New York.
2. Congelez-vous pendant (environ) 1990 ans.
3. Obtenez un emploi chez Planet Express.
4. Achetez un tout nouveau processeur. Construisez un ordinateur, exécutez le programme et placez-le en lieu sûr avec une machine à mouvement pseudo-perpétuel comme la machine apocalyptique.
5. Attendez que la machine à remonter le temps soit inventée.
6. Sautez vers le futur en utilisant la machine à voyager dans le temps. Si vous avez acheté un processeur 1YHz 128 bits, allez à 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 psaprès lorsque vous avez commencé à exécuter le programme.
7. ...?
8. PROFIT!!!

... Cela prend au moins des 10,783,127années même si vous aviez un processeur 1YHz qui est 1,000,000,000,000,000(ou 1,125,899,906,842,624si vous préférez utiliser le préfixe binaire) fois plus rapide qu'un processeur 1GHz.

Donc, plutôt que d'attendre la fin du calcul, il vaudrait mieux nourrir les pigeons qui ont perdu leur maison parce que d'autres npigeons ont pris la maison. :(

Ou, vous pouvez attendre jusqu'à ce que l'ordinateur quantique 128 bits soit inventé. Ensuite, vous pouvez prouver que le GUID n'est pas unique, en utilisant votre programme dans un délai raisonnable (peut-être).

Avez-vous essayé begin = begin + new BigInteger((long)1)à la place de begin ++?

Si le nombre d'UUID généré suit la loi de Moore, l'impression de ne jamais manquer de GUID dans un avenir prévisible est fausse.

Avec 2 ^ 128 UUID, cela ne prendra que 18 mois * Log2 (2 ^ 128) ~ = 192 ans, avant de manquer de tous les UUID.

Et je crois (sans aucune preuve statistique quoi que ce soit) au cours des dernières années depuis l'adoption massive d'UUID, la vitesse que nous générons UUID augmente beaucoup plus rapidement que la loi de Moore ne l'exige. En d'autres termes, nous avons probablement moins de 192 ans avant de devoir faire face à la crise UUID, c'est beaucoup plus tôt que la fin de l'univers.

Mais comme nous ne les manquerons certainement pas d'ici la fin de 2012, nous laisserons à d'autres espèces le soin de s'inquiéter du problème.

Les chances d'un bogue dans le code de génération de GUID sont beaucoup plus élevées que les chances de l'algorithme générant une collision. Les chances d'un bogue dans votre code pour tester les GUID sont encore plus grandes. Abandonner.

Le programme, bien que ses erreurs, montre la preuve qu'un GUID n'est pas unique. Ceux qui tentent de prouver le contraire manquent de raison. Cette déclaration prouve simplement la faible implémentation de certaines des variations de GUID.

Un GUID n'est pas nécessairement unique par définition, il est très unique par définition. Vous venez d'affiner le sens de hautement. En fonction de la version, de l'implémentateur (MS ou autres), de l'utilisation de VM, etc., votre définition de changements importants. (voir le lien dans le post précédent)

Vous pouvez raccourcir votre table de 128 bits pour prouver votre point. La meilleure solution consiste à utiliser une formule de hachage pour raccourcir votre table avec des doublons, puis à utiliser la valeur complète une fois que le hachage entre en collision et en fonction de cette recréer un GUID. Si vous exécutez à partir de différents emplacements, vous stockerez vos paires de hachage / clés complètes dans un emplacement central.

Ps: Si le but est juste de générer x nombre de valeurs différentes, créez une table de hachage de cette largeur et vérifiez simplement la valeur de hachage.

Pas de p ** s sur le feu de joie ici, mais cela se produit en fait, et oui, je comprends la plaisanterie que vous avez donnée à ce gars, mais le GUID est unique en principe seulement, je suis tombé sur ce fil parce qu'il y a un bug dans l'émulateur WP7, ce qui signifie que chaque fois qu'il démarre, il donne le même GUID la première fois qu'il est appelé! Donc, où en théorie vous ne pouvez pas avoir de conflit, s'il y a un problème lors de la génération de cette interface graphique, vous pouvez obtenir des doublons

http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310

Étant donné qu'une partie de la génération de Guid est basée sur le temps de la machine actuelle, ma théorie pour obtenir un Guid en double est la suivante:

1. Effectuer une nouvelle installation de Windows
2. Créez un script de démarrage qui réinitialise l'heure au 01-01-2010 12:00:00 juste au démarrage de Windows.
3. Juste après le script de démarrage, il déclenche votre application pour générer un Guid.
4. Clonez cette installation de Windows, afin d'exclure toute différence subtile pouvant survenir lors des démarrages ultérieurs.
5. Réimaginez le disque dur avec cette image et démarrez la machine plusieurs fois.

Pour moi .. le temps qu'il faut à un seul cœur pour générer un UUIDv1 garantit qu'il sera unique. Même dans une situation multicœur si le générateur d'UUID ne permet de générer qu'un seul UUID à la fois pour votre ressource spécifique (gardez à l'esprit que plusieurs ressources peuvent totalement utiliser les mêmes UUID, mais peu probable car la ressource fait intrinsèquement partie de l'adresse), alors vous aura plus qu'assez d'UUID pour vous durer jusqu'à ce que l'horodatage soit épuisé. À ce stade, je doute vraiment que vous vous en souciez.

Voici également une solution:

int main()
{
  QUuid uuid;
  while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { }
  std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl;
}

Remarque: nécessite Qt, mais je vous garantis que si vous le laissez fonctionner suffisamment longtemps, il pourrait en trouver un.

(Remarque: en fait, maintenant que je le regarde, il peut y avoir quelque chose dans l'algorithme de génération qui empêche deux uuids générés par la suite qui entrent en collision - mais j'en doute un peu).

La seule solution pour prouver que les GUID ne sont pas uniques serait d'avoir un pool de GUID mondial. Chaque fois qu'un GUID est généré quelque part, il doit être enregistré auprès de l'organisation. Ou diable, nous pourrions inclure une normalisation dont tous les générateurs GUID ont besoin pour l'enregistrer automatiquement et pour cela, il a besoin d'une connexion Internet active!