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

Question

Il s'agit de cette question . J'utilise le code ci-dessous à partir de cette réponse pour générer un UUID en JavaScript :

'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
    return v.toString(16);
});

Cette solution semblait fonctionner correctement, mais j'obtiens des collisions. Voici ce que j'ai :

• Une application web fonctionnant dans Google Chrome.
• 16 utilisateurs.
• environ 4000 UUIDs ont été générés au cours des deux derniers mois par ces utilisateurs.
• J'ai obtenu environ 20 collisions - par exemple, un nouvel UUID généré aujourd'hui était le même qu'il y a environ deux mois (utilisateur différent).

Quelle est la cause de ce problème et comment puis-je l'éviter ?

Answer 1

Il y a effectivement des collisions, mais seulement sous Google Chrome. Consultez mon expérience sur le sujet dans Problème de générateur de nombres aléatoires dans Google Chrome

Il semble que les collisions ne se produisent que lors des premiers appels de Math.random. En effet, si vous exécutez simplement la méthode createGUID / testGUIDs ci-dessus (qui est évidemment la première chose que j'ai essayée), cela fonctionne sans aucune collision.

Ainsi, pour effectuer un test complet, il faut redémarrer Google Chrome, générer 32 octets, redémarrer Chrome, générer, redémarrer, générer, etc.

Answer 2

Mon avis est que Math.random() est cassé sur votre système pour une raison quelconque (aussi bizarre que cela puisse paraître). C'est le premier rapport que j'ai vu de quelqu'un obtenant des collisions.

node-uuid a un harnais de test que vous pouvez utiliser pour tester la distribution des chiffres hexadécimaux dans ce code. Si cela semble correct, alors ce n'est pas Math.random() alors essayez de substituer l'implémentation de l'UUID que vous utilisez dans le fichier uuid() et voyez si vous obtenez toujours de bons résultats.

[Mise à jour : vient de voir Rapport de Veselin à propos du bug avec Math.random() au démarrage. Puisque le problème ne se pose qu'au démarrage, la node-uuid est peu susceptible d'être utile. Je commenterai plus en détail le lien avec devoluk.com].

Answer 3

Pour que d'autres personnes soient au courant, je rencontrais un nombre étonnamment élevé de collisions apparentes en utilisant la technique de génération d'UUID mentionnée ici. Ces collisions ont continué même après que je sois passé à seedrandom pour mon générateur de nombres aléatoires. J'ai dû m'arracher les cheveux, comme vous pouvez l'imaginer.

J'ai fini par comprendre que le problème était (presque ?) exclusivement lié aux robots d'exploration de Google. Dès que j'ai commencé à ignorer les requêtes avec "googlebot" dans le champ user-agent, les collisions ont disparu. Je suppose qu'ils doivent mettre en cache les résultats des scripts JS d'une manière semi-intelligente, ce qui a pour conséquence que leur navigateur d'araignée ne peut pas être considéré comme se comportant de la même manière que les navigateurs normaux.

Juste un FYI.

Answer 4

Je viens d'effectuer un test rudimentaire de 100 000 itérations dans Chrome en utilisant l'algorithme UUID que vous avez publié, et je n'ai obtenu aucune collision. Voici un extrait de code :

var createGUID = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

var testGUIDs = function(upperlimit) {
    alert('Doing collision test on ' + upperlimit + ' GUID creations.');
    var i=0, guids=[];
    while (i++<upperlimit) {
        var guid=createGUID();
        if (guids.indexOf(guid)!=-1) {
            alert('Collision with ' + guid + ' after ' + i + ' iterations');
        }
        guids.push(guid);
    }
    alert(guids.length + ' iterations completed.');
}

testGUIDs(100000);

Answer 5

Moi aussi, j'avais du mal à générer des identificateurs uniques globaux garantis qui ne soient pas sujets à des collisions. J'ai fini par écrire un plugin javascript qui garantit soi-disant l'unicité.

N'hésitez pas à l'essayer : https://github.com/mongoh/tuid