Wie gut ist Java's UUID.randomUUID?

Question

Ich weiß, dass zufällige UUIDs in der Theorie eine sehr, sehr, sehr geringe Kollisionswahrscheinlichkeit haben, aber ich frage mich, wie gut Java's randomUUID() in der Praxis ist, um Kollisionen zu vermeiden? Hat jemand Erfahrungen zu teilen?

Answer 1

UUID verwendet java.security.SecureRandom, das als "kryptografisch stark" gilt. Während die tatsächliche Implementierung nicht spezifiziert ist und zwischen den JVMs variieren kann (was bedeutet, dass alle konkreten Aussagen nur für eine bestimmte JVM gültig sind), schreibt sie jedoch vor, dass die Ausgabe einen statistischen Zufallszahlengenerator-Test bestehen muss.

Es ist immer möglich, dass eine Implementierung subtile Bugs enthält, die all dies zerstören (siehe OpenSSH-Schlüsselgenerierungsfehler), aber ich glaube nicht, dass es einen konkreten Grund gibt, sich um die Zufälligkeit von Java-UUIDs zu sorgen.

Answer 2

Wikipedia hat eine sehr gute Antwort http://de.wikipedia.org/wiki/Universally_unique_identifier#Collisions

die Anzahl der zufälligen Version-4-UUIDs, die generiert werden müssen, um eine Wahrscheinlichkeit von mindestens 50% für mindestens eine Kollision zu haben, beträgt 2,71 Billiarden, berechnet wie folgt:

...

Diese Zahl entspricht der Generierung von 1 Milliarde UUIDs pro Sekunde für etwa 85 Jahre, und eine Datei mit so vielen UUIDs, 16 Bytes pro UUID, wäre etwa 45 Exabytes groß, viele Male größer als die derzeit größten Datenbanken, die im Bereich von Hunderten von Petabytes liegen.

...

Also müssen zur Wahrscheinlichkeit von eins zu einer Milliarde 103 Billionen Version-4-UUIDs generiert werden.

Answer 3

Hat jemand Erfahrung zu teilen?

Es gibt 2^122 mögliche Werte für eine Typ-4 UUID. (Die Spezifikation besagt, dass Sie 2 Bits für den Typ und weitere 4 Bits für eine Versionsnummer verlieren.)

Angenommen, Sie würden 1 Million zufällige UUIDs pro Sekunde generieren, wären die Chancen, dass in Ihrem Leben eine Duplikat auftritt, verschwindend gering. Und um das Duplikat zu erkennen, müssten Sie das Problem lösen, 1 Million neue UUIDs pro Sekunde mit _allen zu vergleichen, die Sie zuvor generiert haben_1!

Die Chancen, dass jemand in der Realität ein Duplikat erlebt hat (d.h. es tatsächlich bemerkt hat), sind noch kleiner als verschwindend gering ... wegen der praktischen Schwierigkeit, nach Kollisionen zu suchen.

Natürlich werden Sie in der Regel einen Pseudo-Zufallszahlengenerator verwenden, nicht eine Quelle von wirklich zufälligen Zahlen. Aber ich denke, wir können sicher sein, dass, wenn Sie einen glaubwürdigen Anbieter für Ihre kryptographisch sicheren Zufallszahlen verwenden, dann wird es kryptographische Stärke haben, und die Wahrscheinlichkeit von Wiederholungen wird die gleiche sein wie bei einem idealen (nicht verzerrten) Zufallszahlengenerator.

Wenn Sie jedoch einen JVM mit einem "fehlerhaften" krypto- zufallszahlengenerator verwenden würden, sind alle Wetten abgeschaltet. (Und das könnte auch einige der Workarounds für "Mangel an Entropie" -Probleme auf einigen Systemen einschließen. Oder die Möglichkeit, dass jemand Ihr JRE manipuliert hat, entweder auf Ihrem System oder weiter oben.)

---

1 - Unter der Annahme, dass Sie "irgendeine Art von binärem btree" verwenden, wie von einem anonymen Kommentator vorgeschlagen, wird jede UUID O(NlogN) Bits RAM-Speicher benötigen, um N verschiedene UUIDs bei niedriger Dichte und zufälliger Verteilung der Bits darzustellen. Multiplizieren Sie das jetzt mit 1.000.000 und der Anzahl der Sekunden, die Sie das Experiment durchführen werden. Ich glaube nicht, dass dies praktisch ist für die Dauer, die benötigt wird, um Kollisionen eines hochwertigen RNG zu testen. Nicht einmal mit (hypothetischen) klugen Darstellungen.

Answer 4

Ich bin kein Experte, aber ich würde annehmen, dass im Laufe der Jahre genügend kluge Menschen den Zufallszahlengenerator von Java betrachtet haben. Daher würde ich auch annehmen, dass zufällige UUIDs gut sind. Sie sollten also wirklich die theoretische Kollisionswahrscheinlichkeit haben (die etwa 1 : 3 × 10^38 für alle möglichen UUIDs beträgt. Weiß jemand, wie sich das für nur zufällige UUIDs ändert? Ist es 1/(16*4) des oben Genannten?)

Aus meiner praktischen Erfahrung habe ich bisher noch keine Kollisionen gesehen. Ich werde wahrscheinlich einen erstaunlich langen Bart haben, wenn ich meine erste bekomme ;)

Answer 5

Viele der Antworten befassen sich damit, wie viele UUIDs generiert werden müssten, um eine 50%ige Chance auf eine Kollision zu erreichen. Aber eine 50%, 25% oder sogar 1%ige Kollisionschance ist für eine Anwendung, in der Kollision praktisch unmöglich sein muss, wertlos.

Weisen Programmierer routinemäßig andere Ereignisse als "unmöglich" ab, die tatsächlich eintreten können?

Wenn wir Daten auf eine Festplatte oder in den Speicher schreiben und sie dann wieder auslesen, nehmen wir selbstverständlich an, dass die Daten korrekt sind. Wir verlassen uns auf die Fehlerkorrektur des Geräts, um jede Beschädigung zu erkennen. Aber die Chance auf unerkannte Fehler liegt tatsächlich bei etwa 2-50.

Wäre es nicht sinnvoll, einen ähnlichen Standard auf zufällige UUIDs anzuwenden? Wenn Sie dies tun, werden Sie feststellen, dass eine "unmögliche" Kollision in einer Sammlung von rund 100 Milliarden zufälligen UUIDs (236.5) möglich ist.

Dies ist eine astronomische Zahl, aber Anwendungen wie die Aufschlüsselung von Rechnungen in einem nationalen Gesundheitssystem oder das Protokollieren von hochfrequenten Sensordaten auf einer großen Anzahl von Geräten könnten definitiv an diese Grenzen stoßen. Wenn Sie gerade den nächsten Per Anhalter durch die Galaxis schreiben, versuchen Sie nicht, jedem Artikel UUIDs zuzuweisen!