Kollisionen beim Generieren von UUIDs in JavaScript

Lesezeit: 6 Minuten

Benutzer-Avatar
Muxa

Das bezieht sich auf diese Frage. Ich verwende den folgenden Code aus dieser Antwort, um eine UUID in JavaScript zu generieren:

'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);
});

Diese Lösung schien gut zu funktionieren, aber ich bekomme Kollisionen. Hier ist, was ich habe:

  • Eine Webanwendung, die in Google Chrome ausgeführt wird.
  • 16 Benutzer.
  • etwa 4000 UUIDs wurden in den letzten zwei Monaten von diesen Benutzern generiert.
  • Ich habe ungefähr 20 Kollisionen erhalten – zB war eine heute generierte neue UUID die gleiche wie vor ungefähr zwei Monaten (anderer Benutzer).

Was verursacht dieses Problem und wie kann ich es vermeiden?

  • Kombiniere eine gute Zufallszahl mit der aktuellen Uhrzeit (in Millisekunden). Die Wahrscheinlichkeit, dass die Zufallszahl genau zur gleichen Zeit kollidiert, ist wirklich, wirklich, wirklich gering.

    – jfriend00

    2. August 2011 um 6:33 Uhr


  • @ jfriend00 Wenn Sie das tun müssen, ist es keine “gute Zufallszahl”, nicht einmal eine anständige Pseudo-Zufallszahl.

    – Attila O.

    17. Juli 2012 um 15:14 Uhr

  • was bedeutet die (r&0x3|0x8) Anteil bedeuten / Bewertung zu?

    – Christian

    11. Dezember 2014 um 17:42 Uhr

  • Was ist mit dem Anhängen von Date.now().toString()?

    – Vitim.us

    15. Mai 2015 um 4:48 Uhr

  • Es gibt ein großes Problem in Ihrer Architektur, das nichts mit UUIDs zu tun hat – der Client kann absichtlich kollidierende IDs generieren. Generieren Sie IDs nur von einem System, dem Sie vertrauen. Stellen Sie als Problemumgehung jedoch vom Client generierte IDs mit user_id voran, sodass der gegnerische/fehlerhafte Client nur mit sich selbst kollidieren kann (und dies auf der Serverseite handhaben kann).

    – Dzmitri Laserka

    15. April 2016 um 20:29 Uhr


Benutzer-Avatar
broofa

Meine beste Vermutung ist das Math.random() ist auf Ihrem System aus irgendeinem Grund defekt (so bizarr das klingt). Dies ist der erste Bericht, den ich von jemandem gesehen habe, der Kollisionen bekommen hat.

node-uuid hat ein Testgeschirr die Sie verwenden können, um die Verteilung von Hexadezimalziffern in diesem Code zu testen. Wenn das okay aussieht, dann ist es das nicht Math.random()also versuchen Sie dann, die UUID-Implementierung, die Sie verwenden, in die zu ersetzen uuid() Methode dort und sehen Sie, ob Sie immer noch gute Ergebnisse erzielen.

[Update: Just saw Veselin’s report about the bug with Math.random() at startup. Since the problem is only at startup, the node-uuid test is unlikely to be useful. I’ll comment in more detail on the devoluk.com link.]

  • Danke, ich gehe jetzt mit uuid.js, da es die starke Krypto des Browsers verwendet, falls verfügbar. Mal sehen, ob es Kollisionen gibt.

    – Muxa

    31. August 2011 um 22:21 Uhr


  • Können Sie einen Link zu dem uuid.js-Code bereitstellen, auf den Sie sich beziehen? (Entschuldigung, ich bin mir nicht sicher, welche Bibliothek Sie meinen.)

    – broofa

    7. September 2011 um 16:51 Uhr

  • Hatte bisher keine Kollisionen 🙂

    – Muxa

    12. Februar 2012 um 9:41 Uhr

  • Wie auch immer, wenn es Chrome ist und nur beim Start, könnte Ihre App eine Reihe von, sagen wir, zehn Guids mit der obigen Funktion generieren und verwerfen 🙂

    – Vinko Vrsalović

    21. Januar 2014 um 5:48 Uhr

  • Das Problem ist die begrenzte Entropie, die Sie von Math.random() erhalten. Bei einigen Browsern beträgt die Entropie insgesamt nur 41 Bit. Durch mehrmaliges Aufrufen von Math.random() wird die Entropie nicht erhöht. Wenn Sie wirklich eindeutige v4-UUIDs wollen, müssen Sie einen kryptografisch starken RNG verwenden, der mindestens 122-Bit-Entropie pro generierter UUID erzeugt.

    – mlehmk

    25. September 2015 um 12:28 Uhr


Benutzer-Avatar
Veselin Kulow

Zwar gibt es Kollisionen, aber nur unter Google Chrome. Lesen Sie meine Erfahrungen zum Thema in Problem mit dem Zufallszahlengenerator von Google Chrome

Es scheint, als würden Kollisionen nur bei den ersten Aufrufen von Math.random auftreten. Denn wenn Sie einfach die Methode createGUID / testGUIDs oben ausführen (was offensichtlich das erste war, was ich versucht habe), funktioniert es einfach ohne jegliche Kollisionen.

Um also einen vollständigen Test durchzuführen, muss man Google Chrome neu starten, 32 Byte generieren, Chrome neu starten, generieren, neu starten, generieren usw.

  • Das ist ziemlich besorgniserregend – hat jemand einen Fehlerbericht erstellt?

    – UpTheCreek

    21. September 2011 um 19:24 Uhr

  • Besonders gefällt der Link zu besseren Zufallszahlengeneratoren in Javascript: baagoe.com/en/RandomMusings/javascript

    – Leopard

    3. Oktober 2011 um 6:35 Uhr

  • Leider ist der Link jetzt kaputt 🙁

    – Guss

    12. Juli 2013 um 17:09 Uhr

  • web.archive.org/web/20120503063359/http://baagoe.com/en/…

    – Beni Cherniavsky-Paskin

    29. August 2013 um 5:19 Uhr

  • Kann jemand bestätigen, ob dieser Fehler behoben wurde?

    – Xdrone

    5. Mai 2014 um 17:26 Uhr

Benutzer-Avatar
Ken Smith

Nur damit andere Leute sich dessen bewusst sind – ich bin mit der hier erwähnten UUID-Generierungstechnik auf eine überraschend große Anzahl offensichtlicher Kollisionen gestoßen. Diese Kollisionen setzten sich auch nach dem Wechsel fort zufällig für meinen Zufallszahlengenerator. Da habe ich mir die Haare ausgerissen, wie Sie sich vorstellen können.

Irgendwann fand ich heraus, dass das Problem (fast?) ausschließlich mit den Web-Crawler-Bots von Google zusammenhängt. Sobald ich anfing, Anfragen mit „googlebot“ im User-Agent-Feld zu ignorieren, verschwanden die Kollisionen. Ich vermute, dass sie die Ergebnisse von JS-Skripten auf halbintelligente Weise zwischenspeichern müssen, mit dem Endergebnis, dass man sich nicht darauf verlassen kann, dass sich ihr Spidering-Browser so verhält, wie es normale Browser tun.

Nur ein FYI.

  • Hatte das gleiche Problem mit unserem Metriksystem. Es wurden Tausende von UUID-Kollisionen mit dem Modul „node-uuid“ zum Generieren von Sitzungs-IDs im Browser festgestellt. Es stellte sich heraus, dass es die ganze Zeit über Googlebot war. Vielen Dank!

    – domck

    27. März 2017 um 17:47 Uhr

Benutzer-Avatar
Benutzer533676

Ich habe gerade einen rudimentären Test von 100.000 Iterationen in Chrome mit dem von Ihnen geposteten UUID-Algorithmus durchgeführt, und ich habe keine Kollisionen erhalten. Hier ist ein Code-Snippet:

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);

Die Antwort, die diese UUID-Lösung ursprünglich gepostet hat, wurde am 28.06.2017 aktualisiert:

EIN guter Artikel von Chrome-Entwicklern Erörterung des Zustands der PRNG-Qualität von Math.random in Chrome, Firefox und Safari. tl; dr – Ab Ende 2015 ist es “ziemlich gut”, aber keine kryptografische Qualität. Um dieses Problem zu beheben, finden Sie hier eine aktualisierte Version der obigen Lösung, die ES6 verwendet, die crypto API und ein bisschen JS-Zauberei, die ich nicht loben kann:

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());

Benutzer-Avatar
Briguy37

Die Antworten hier befassen sich mit “Was verursacht das Problem?” (Chrome Math.random Seed-Problem), aber nicht “Wie kann ich es vermeiden?”.

Wenn Sie immer noch suchen, wie Sie dieses Problem vermeiden können, habe ich diese Antwort vor einiger Zeit als modifizierte Version der Broofa-Funktion geschrieben, um genau dieses Problem zu umgehen. Es funktioniert, indem die ersten 13 Hex-Zahlen durch einen Hex-Teil des Zeitstempels versetzt werden, was bedeutet, dass selbst wenn Math.random auf demselben Seed ist, immer noch eine andere UUID generiert wird, es sei denn, sie wird genau in derselben Millisekunde generiert.

1186800cookie-checkKollisionen beim Generieren von UUIDs in JavaScript

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy