Comment créer un GUID / UUID

Question

J'essaie de créer des identifiants uniques au niveau mondial en JavaScript. Je ne sais pas quelles routines sont disponibles sur tous les navigateurs, à quel point le générateur de nombres aléatoires intégré est "aléatoire" et semé, etc.

Le GUID / UUID doit comporter au moins 32 caractères et rester dans la gamme ASCII afin d'éviter tout problème lors de leur transmission.

Answer 1

[Modifié le 2021-10-16 pour refléter les dernières bonnes pratiques pour produire des UUIDs conformes à la RFC4122].

La plupart des lecteurs voudront utiliser les uuid module . Il est bien testé et soutenu.

En crypto.randomUUID() est une norme émergente qui est prise en charge par les Node.js et un nombre croissant de navigateurs .

Si aucune de ces méthodes ne vous convient, il y a celle-ci (basée sur la réponse originale à cette question) :

function uuidv4() {
  return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
    (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
  );
}

console.log(uuidv4());

Remarque : L'utilisation de tous Les générateurs d'UUID qui s'appuient sur Math.random() sont fortement déconseillés. (y compris les extraits présentés dans les versions précédentes de cette réponse) pour raisons mieux expliquées ici . TL;DR : Les solutions basées sur Math.random()ne fournissent pas de bonnes garanties d'unicité.

Answer 2

Les UUID (Universally Unique IDentifier), également connus sous le nom de GUID (Globally Unique IDentifier), selon la norme RFC 4122 sont des identificateurs conçus pour offrir certaines garanties d'unicité.

Bien qu'il soit possible d'implémenter des UUID conformes à la RFC en quelques lignes de code JavaScript (voir par exemple Réponse de @broofa (voir ci-dessous), il existe plusieurs pièges courants :

• Format d'identification non valide (les UUID doivent être de la forme " xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx "où x est l'un des éléments suivants : [0-9, a-f] M est l'un de [1-5], et N est [8, 9, a ou b]
• Utilisation d'une source d'aléa de faible qualité (telle que Math.random )

Par conséquent, les développeurs qui écrivent du code pour des environnements de production sont encouragés à utiliser une implémentation rigoureuse et bien maintenue telle que le programme uuid module.

Answer 3

J'aime beaucoup la propreté Réponse de Broofa est, mais il est regrettable que les les mauvaises mises en œuvre des Math.random laisser la possibilité d'une collision.

Voici un exemple similaire RFC4122 version 4 qui résout ce problème en décalant les 13 premiers nombres hexagonaux par une portion hexagonale de l'horodatage, et une fois épuisés, les décalages par une portion hexagonale des microsecondes depuis le chargement de la page. De cette façon, même si Math.random est sur la même graine, les deux clients devraient générer l'UUID exactement au même nombre de microsecondes depuis le chargement de la page (si le temps de haute performance est pris en charge) ET exactement à la même milliseconde (ou plus de 10 000 ans plus tard) pour obtenir le même UUID :

function generateUUID() { // Public Domain/MIT
    var d = new Date().getTime();//Timestamp
    var d2 = ((typeof performance !== 'undefined') && performance.now && (performance.now()*1000)) || 0;//Time in microseconds since page-load or 0 if unsupported
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random() * 16;//random number between 0 and 16
        if(d > 0){//Use timestamp until depleted
            r = (d + r)%16 | 0;
            d = Math.floor(d/16);
        } else {//Use microseconds since page-load if supported
            r = (d2 + r)%16 | 0;
            d2 = Math.floor(d2/16);
        }
        return (c === 'x' ? r : (r & 0x3 | 0x8)).toString(16);
    });
}

var onClick = function(){
    document.getElementById('uuid').textContent = generateUUID();
}
onClick();

#uuid { font-family: monospace; font-size: 1.5em; }

<p id="uuid"></p>
<button id="generateUUID" onclick="onClick();">Generate UUID</button>

Voici un petit jeu à tester.

---

Extrait modernisé pour ES6

const generateUUID = () => {
  let
    d = new Date().getTime(),
    d2 = (performance && performance.now && (performance.now() * 1000)) || 0;
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, c => {
    let r = Math.random() * 16;
    if (d > 0) {
      r = (d + r) % 16 | 0;
      d = Math.floor(d / 16);
    } else {
      r = (d2 + r) % 16 | 0;
      d2 = Math.floor(d2 / 16);
    }
    return (c == 'x' ? r : (r & 0x7 | 0x8)).toString(16);
  });
};

const onClick = (e) => document.getElementById('uuid').textContent = generateUUID();

document.getElementById('generateUUID').addEventListener('click', onClick);

onClick();

#uuid { font-family: monospace; font-size: 1.5em; }

<p id="uuid"></p>
<button id="generateUUID">Generate UUID</button>

Answer 4

Réponse de broofa est plutôt astucieux, en effet - impressionnant d'intelligence, vraiment... Conforme à la RFC4122, assez lisible et compact. Génial !

Mais si vous regardez cette expression régulière, ces nombreuses replace() les rappels, toString() et Math.random() (où il n'utilise que quatre bits du résultat et gaspille le reste), vous pouvez commencer à vous poser des questions sur les performances. En effet, joelpt a même décidé de lancer une RFC pour la vitesse des GUID génériques avec generateQuickGUID .

Mais pouvons-nous obtenir la vitesse et Conformité au RFC ? Je réponds par l'affirmative ! Peut-on maintenir la lisibilité ? Eh bien... Pas vraiment, mais c'est facile si vous suivez le mouvement.

Mais d'abord, mes résultats, comparés à ceux de Broofa, guid (la réponse acceptée), et la réponse non conforme à la norme RFC, à savoir generateQuickGuid :

                  Desktop   Android
           broofa: 1617ms   12869ms
               e1:  636ms    5778ms
               e2:  606ms    4754ms
               e3:  364ms    3003ms
               e4:  329ms    2015ms
               e5:  147ms    1156ms
               e6:  146ms    1035ms
               e7:  105ms     726ms
             guid:  962ms   10762ms
generateQuickGuid:  292ms    2961ms
  - Note: 500k iterations, results will vary by browser/CPU.

Ainsi, à ma sixième itération d'optimisations, j'ai battu la réponse la plus populaire de plus de 12 fois La réponse acceptée par plus d'un million de personnes. 9 fois et la réponse rapide et non conforme de 2 à 3 fois . Et je suis toujours conforme à la norme RFC 4122.

Comment ? J'ai mis la source complète sur http://jsfiddle.net/jcward/7hyaC/3/ et sur http://jsperf.com/uuid-generator-opt/4

Pour l'expliquer, commençons par le code de broofa :

function broofa() {
    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);
    });
}

console.log(broofa())

Il remplace donc x avec n'importe quel chiffre hexadécimal aléatoire, y avec des données aléatoires (sauf en forçant les deux premiers bits à 10 selon la spécification du RFC), et l'expression rationnelle ne correspond pas à l'expression - ou 4 pour qu'il n'ait pas à s'en occuper. Très, très habile.

La première chose à savoir est que les appels de fonction sont coûteux, tout comme les expressions régulières (bien qu'il n'en utilise qu'une seule, elle comporte 32 rappels, un pour chaque correspondance, et dans chacun des 32 rappels, elle appelle Math.random() et v.toString(16)).

Le premier pas vers la performance consiste à éliminer le RegEx et ses fonctions de rappel et à utiliser une simple boucle à la place. Cela signifie que nous devons nous occuper de la fonction - et 4 caractères, alors que le broofa n'en a pas. Notez également que nous pouvons utiliser l'indexation des tableaux de chaînes pour conserver l'architecture de son modèle de chaîne :

function e1() {
    var u='',i=0;
    while(i++<36) {
        var c='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'[i-1],r=Math.random()*16|0,v=c=='x'?r:(r&0x3|0x8);
        u+=(c=='-'||c=='4')?c:v.toString(16)
    }
    return u;
}

console.log(e1())

Il s'agit essentiellement de la même logique interne, sauf que nous vérifions les éléments suivants - ou 4 et l'utilisation d'une boucle while (au lieu de replace() callbacks) nous permet d'obtenir une amélioration de près de 3 fois !

L'étape suivante n'est pas très importante sur l'ordinateur de bureau, mais elle fait une grande différence sur les téléphones portables. Faisons moins d'appels à Math.random() et utilisons tous ces bits aléatoires au lieu d'en jeter 87% avec un tampon aléatoire qui est décalé à chaque itération. Déplaçons également la définition du modèle hors de la boucle, juste au cas où cela serait utile :

function e2() {
    var u='',m='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx',i=0,rb=Math.random()*0xffffffff|0;
    while(i++<36) {
        var c=m[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
        u+=(c=='-'||c=='4')?c:v.toString(16);rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
    }
    return u
}

console.log(e2())

Cela nous permet d'économiser 10 à 30 % en fonction de la plateforme. Ce n'est pas si mal. Mais l'étape suivante consiste à se débarrasser complètement des appels à la fonction toString grâce à un classique de l'optimisation : la table de recherche. Une simple table de recherche à 16 éléments permet d'effectuer le travail de toString(16) en beaucoup moins de temps :

function e3() {
    var h='0123456789abcdef';
    var k='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx';
    /* same as e4() below */
}
function e4() {
    var h=['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'];
    var k=['x','x','x','x','x','x','x','x','-','x','x','x','x','-','4','x','x','x','-','y','x','x','x','-','x','x','x','x','x','x','x','x','x','x','x','x'];
    var u='',i=0,rb=Math.random()*0xffffffff|0;
    while(i++<36) {
        var c=k[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
        u+=(c=='-'||c=='4')?c:h[v];rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
    }
    return u
}

console.log(e4())

L'optimisation suivante est un autre classique. Puisque nous ne traitons que quatre bits de sortie à chaque itération de la boucle, réduisons le nombre de boucles de moitié et traitons huit bits à chaque itération. C'est délicat car nous devons toujours gérer les positions de bits conformes à la RFC, mais ce n'est pas trop difficile. Nous devons alors créer une table de recherche plus grande (16x16, ou 256) pour stocker 0x00 - 0xFF, et nous ne la construisons qu'une seule fois, en dehors de la fonction e5().

var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e5() {
    var k=['x','x','x','x','-','x','x','-','4','x','-','y','x','-','x','x','x','x','x','x'];
    var u='',i=0,rb=Math.random()*0xffffffff|0;
    while(i++<20) {
        var c=k[i-1],r=rb&0xff,v=c=='x'?r:(c=='y'?(r&0x3f|0x80):(r&0xf|0x40));
        u+=(c=='-')?c:lut[v];rb=i%4==0?Math.random()*0xffffffff|0:rb>>8
    }
    return u
}

console.log(e5())

J'ai essayé un e6() qui traite 16 bits à la fois, en utilisant toujours les 256 éléments. LUT et a montré les rendements décroissants de l'optimisation. Bien qu'il y ait eu moins d'itérations, la logique interne a été compliquée par l'augmentation du traitement, et la performance a été la même sur l'ordinateur de bureau, mais seulement 10 % plus rapide sur le mobile.

La dernière technique d'optimisation à appliquer - dérouler la boucle. Puisque nous bouclons un nombre fixe de fois, nous pouvons techniquement écrire tout cela à la main. J'ai essayé une fois avec une seule variable aléatoire, r Je n'ai cessé de le réaffecter et les performances ont chuté. Mais avec quatre variables assignées à des données aléatoires à l'avance, puis en utilisant la table de recherche et en appliquant les bits RFC appropriés, cette version les surpasse toutes :

var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e7()
{
    var d0 = Math.random()*0xffffffff|0;
    var d1 = Math.random()*0xffffffff|0;
    var d2 = Math.random()*0xffffffff|0;
    var d3 = Math.random()*0xffffffff|0;
    return lut[d0&0xff]+lut[d0>>8&0xff]+lut[d0>>16&0xff]+lut[d0>>24&0xff]+'-'+
    lut[d1&0xff]+lut[d1>>8&0xff]+'-'+lut[d1>>16&0x0f|0x40]+lut[d1>>24&0xff]+'-'+
    lut[d2&0x3f|0x80]+lut[d2>>8&0xff]+'-'+lut[d2>>16&0xff]+lut[d2>>24&0xff]+
    lut[d3&0xff]+lut[d3>>8&0xff]+lut[d3>>16&0xff]+lut[d3>>24&0xff];
}

console.log(e7())

Modualisé : http://jcward.com/UUID.js - UUID.generate()

Ce qui est amusant, c'est que la génération de 16 octets de données aléatoires est la partie la plus facile. Toute l'astuce consiste à l'exprimer en string conforme à la RFC, et il est le plus étroitement réalisé avec 16 octets de données aléatoires, une boucle non roulée et une table de recherche.

J'espère que ma logique est correcte - il est très facile de faire une erreur dans ce genre de travail fastidieux. Mais les résultats me semblent bons. J'espère que vous avez apprécié cette course folle à l'optimisation du code !

Attention : Mon objectif principal était de montrer et d'enseigner des stratégies d'optimisation potentielles. D'autres réponses couvrent des sujets importants tels que les collisions et les nombres réellement aléatoires, qui sont importants pour générer de bons UUID.

Answer 5

Voici un code basé sur RFC 4122 section 4.4 (Algorithmes de création d'un UUID à partir d'un nombre réellement aléatoire ou pseudo-aléatoire).

function createUUID() {
    // http://www.ietf.org/rfc/rfc4122.txt
    var s = [];
    var hexDigits = "0123456789abcdef";
    for (var i = 0; i < 36; i++) {
        s[i] = hexDigits.substr(Math.floor(Math.random() * 0x10), 1);
    }
    s[14] = "4";  // bits 12-15 of the time_hi_and_version field to 0010
    s[19] = hexDigits.substr((s[19] & 0x3) | 0x8, 1);  // bits 6-7 of the clock_seq_hi_and_reserved to 01
    s[8] = s[13] = s[18] = s[23] = "-";

    var uuid = s.join("");
    return uuid;
}