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?
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.
Es ist immer möglich, dass eine Implementierung subtile Fehler enthält ... - Oder (eine Aluhut aufsetzend) ... absichtliche subtile Mängel. <:-)
@osa: Das Nichtproduzieren von Kollisionen (mehr als bei perfekter Zufälligkeit zu erwarten ist) ist so ziemlich die niedrigste Qualitätserfordernis für einen Zufallszahlengenerator, während kryptographische Stärke die höchste ist. Mit anderen Worten, ein kryptographisch starker Zufallszahlengenerator wird auf jeden Fall nicht mehr Kollisionen produzieren als erwartet.
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.
Ich würde auch von dieser Seite zitieren: "Die Wahrscheinlichkeit für ein Duplikat läge bei etwa 50%, wenn jeder Mensch auf der Erde 600 Millionen UUIDs besitzt."
@Markus: völlig falsch. Die Wahrscheinlichkeit von Kollisionen für gute Pseudozufallszahlengeneratoren, insbesondere kryptographisch starke, unterscheidet sich nicht von "echter" Zufälligkeit.
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.
"(Und um das Duplikat zu erkennen, müssten Sie das Problem lösen, 1 Million neue UUIDs pro Sekunde mit allen zu vergleichen, die zuvor generiert wurden!)" - dieser Teil ist relativ unkompliziert, vorausgesetzt, Sie haben Ihre UUIDs in einer Art binärer Baumstruktur gespeichert, es wäre einfach nur ein Baumabstieg pro neuer UUID. Sie müssten sie nicht tatsächlich individuell mit allen zuvor generierten UUIDs vergleichen.
"Die Wahrscheinlichkeit, dass in Ihrem Leben ein Duplikat auftritt, wäre verschwindend gering", wofür werden uns zukünftige Generationen verurteilen...
Vielleicht würden sie uns verurteilen für die Annahme, dass es unrealistisch ist, 10^6 eindeutige IDs pro Sekunde zu generieren. Oder 10^12. Oder dass vielleicht nicht erkennen, dass es so etwas wie eine Zufallszahl nicht gibt. Oder etwas anderes, das schwer vorstellbar ist. Aber ... hey ... die Menschen urteilen schon seit Ewigkeiten über ihre Vorfahren, und es hat nichts geändert.
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 ;)
Von Wikipedia: ... Mit anderen Worten, nur nachdem für die nächsten 100 Jahre jeden Tag 1 Milliarde UUIDs generiert wurden, wäre die Wahrscheinlichkeit, nur ein Duplikat zu erstellen, etwa 50%.
Bei einem früheren Arbeitgeber hatten wir eine eindeutige Spalte, die eine zufällige UUID enthielt. Wir hatten in der ersten Woche nach der Bereitstellung eine Kollision. Sicher, die Chancen stehen niedrig, aber sie sind nicht null. Deshalb enthält Log4j 2 UuidUtil.getTimeBasedUuid. Es generiert eine UUID, die für 8.925 Jahre eindeutig ist, solange Sie nicht mehr als 10.000 UUIDs/Millisekunde auf einem einzigen Server generieren.
Es wird nach der Wahrscheinlichkeit einer Kollision gefragt. Die Implikation ist, dass er sicherstellen möchte, diese zu vermeiden.
Die Kollision war höchstwahrscheinlich auf eine defekte Quelle der Zufälligkeit für das Nachfüllen der PRNGs zurückzuführen. Ich denke jedoch, dass es möglich war, dass es auf reines Glück zurückzuführen war.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
14 Stimmen
In meiner Erfahrung habe ich noch nie eine Kollision gesehen ;-)
4 Stimmen
Die Algorithmen sind in RFC1422 spezifiziert: ietf.org/rfc/rfc4122.txt
8 Stimmen
@skaffman: Das RFC sagt überhaupt nichts über den verwendeten Algorithmus zur Generierung der Zufallszahlen aus.
5 Stimmen
Da es sich um eine offene Frage handelt, werde ich keine Antwort als die richtige Antwort markieren. Stattdessen werde ich jeder Antwort, die ich gut finde, eine Stimme geben :)
9 Stimmen
Von Wikipedia: ... Mit anderen Worten, nur nachdem 1 Milliarde UUIDs pro Sekunde für die nächsten 100 Jahre generiert wurden, läge die Wahrscheinlichkeit, nur einen einzigen Duplikat zu erstellen, bei etwa 50%.
0 Stimmen
Wir haben bisher 2 Kollisionen erlebt. Ich weiß nicht, wie es uns gelungen ist, sie zu verursachen :(
0 Stimmen
Die Quintessenz ist also, dass eine Kollision möglich ist. Es ist möglich, dass die ersten 2 UUIDs, die Sie generieren, identisch sind. Unwahrscheinlich, ja.
1 Stimmen
@MaVRoSCy es ist "mindestens einer" und nicht nur "einer"
1 Stimmen
Wenn Sie nicht zwei IDs innerhalb derselben Sekunde generieren müssen, ist es zu 100 % sicher für das aktuelle Datum + die Uhrzeit.