UUID-Kollisionswahrscheinlichkeit-Rechner
Eingaben
| Erzeugte UUIDs | 1.000.000.000 |
|---|---|
| Zufallsbits | 122 |
UUID-Kollisionswahrscheinlichkeit-Rechner
Schätzt die Wahrscheinlichkeit, dass zwei zufällig erzeugte UUIDs kollidieren, ausgehend von der Anzahl der erzeugten UUIDs und der Anzahl der Zufallsbits, mithilfe der Geburtstagsnäherung.
Eingaben
Erzeugung
Ergebnisse
Geben Sie einen Wert ein, um die Ergebnisse zu sehen.
Kollisionswahrscheinlichkeit
Schwellenwerte
UUID-Kollisionswahrscheinlichkeit
Eine UUID (universally unique identifier, universell eindeutiger Bezeichner) ist ein 128-Bit-Wert, mit dem Datensätze, Dateien und Nachrichten gekennzeichnet werden, ohne dass eine zentrale Stelle Nummern vergibt. Ihr Nutzen beruht auf einem wahrscheinlichkeitstheoretischen Versprechen: Wenn alle unabhängig zufällige UUIDs erzeugen, ist die Wahrscheinlichkeit, dass zwei davon übereinstimmen, verschwindend gering. Dieser Rechner quantifiziert dieses Versprechen — ausgehend von der Anzahl der erzeugten Bezeichner und der Anzahl der Zufallsbits je Bezeichner schätzt er die Kollisionswahrscheinlichkeit und die Anzahlen, ab denen Kollisionen zu einem realistischen Anliegen werden.
Warum Eindeutigkeit wahrscheinlichkeitstheoretisch ist
Eine zufällige UUID ist nicht garantiert eindeutig. Sie wird gleichverteilt aus einem riesigen Raum gezogen, und Eindeutigkeit ist eine statistische Beinahe-Gewissheit statt einer logischen. Eine UUID der Version 4 hat 122 Zufallsbits — die übrigen 6 ihrer 128 Bits codieren Version und Variante — was etwa mögliche Werte ergibt. Bei einem so großen Raum ist das zufällige Wiederholen eines Werts außerordentlich unwahrscheinlich, doch die Wahrscheinlichkeit ist nicht exakt null.
Die Geburtstagsnäherung
Kollisionen werden viel früher wahrscheinlich, als die Größe des Raums vermuten lässt, eine Tatsache, die als Geburtstagsproblem bekannt ist. Für einen Raum von Werten wird die Wahrscheinlichkeit, dass mindestens zwei von Bezeichnern kollidieren, gut angenähert durch:
Der 50-%-Punkt — an dem eine Kollision ebenso wahrscheinlich wie unwahrscheinlich ist — wird nahe der Quadratwurzel des Raums erreicht:
Für 122 Zufallsbits sind das etwa Bezeichner, rund 2,7 Trillionen.
Rechenbeispiel
Angenommen, Sie kürzen Bezeichner auf 64 Zufallsbits, um Speicher zu sparen, und erzeugen eine Milliarde davon. Die Kollisionswahrscheinlichkeit beträgt:
p≈1−e−(109)2/(2⋅264)=1−e−1018/3.689×1019=1−e−0.0271≈0.0267Bei 64 Bits tragen eine Milliarde Bezeichner also eine Wahrscheinlichkeit von etwa 2,7 % für mindestens eine Kollision — gering, aber nicht mehr vernachlässigbar. Dieselbe Milliarde Bezeichner als vollständige 122-Bit-UUIDs der Version 4 haben eine Kollisionswahrscheinlichkeit unter .
Was das in der Praxis bedeutet
Für vollständige UUIDs der Version 4 sind Kollisionen in jedem realistischen Maßstab kein praktisches Anliegen; selbst eine Wahrscheinlichkeit von eins zu einer Milliarde zu erreichen würde in der Größenordnung von Bezeichnern erfordern. Die tatsächlichen Risiken liegen anderswo: ein schwacher oder schlecht initialisierter Zufallszahlengenerator, der vorhersagbare oder wiederholte Ausgaben erzeugt, oder das Kürzen von Bezeichnern auf weniger Bits, was die Geburtstagsschranke drastisch näher rückt. Wenn Sie Bezeichner kürzen, berechnen Sie mit der reduzierten Bitzahl neu. Für dieselbe Kollisionsmathematik, angewendet auf Hashfunktionen, siehe den Hash-Kollisionswahrscheinlichkeit.
Diese Zahlen sind Näherungen, die gelten, wenn die Anzahl weit kleiner als die Größe des Raums ist, was für jede realistische Verwendung von UUIDs zutrifft.
Häufig gestellte Fragen (FAQ)
Sind UUIDs garantiert eindeutig?
Nein. Eine zufällige UUID ist nicht garantiert eindeutig — sie wird lediglich aus einem so großen Raum gezogen, dass eine Kollision überwältigend unwahrscheinlich ist. Eine UUID der Version 4 hat 122 Zufallsbits, was etwa 5,3 × 10³⁶ möglichen Werten entspricht.
Bei so vielen Möglichkeiten ist die Wahrscheinlichkeit, denselben Wert zweimal zu erzeugen, für jede realistische Anzahl an Bezeichnern vernachlässigbar, aber nicht exakt null. Systeme, die absolute Eindeutigkeit verlangen, erzwingen sie weiterhin über eine Datenbankbedingung.
Wie viele Zufallsbits hat eine UUID?
Eine UUID ist 128 Bit lang, aber nicht alle davon sind zufällig. In einer UUID der Version 4 (zufällig) sind 6 Bit reserviert, um Version und Variante zu codieren, sodass 122 Zufallsbits verbleiben.
UUIDs der Version 1 mischen einen Zeitstempel und eine Knotenkennung mit einem kleineren Zufallsanteil, und neuere Verfahren wie Version 7 betten einen Zeitstempel neben Zufallsbits ein. Die Kollisionsrechnung hängt nur von der Anzahl der echt zufälligen Bits ab, weshalb dieser Rechner diese Zahl direkt abfragt.
Was ist die Geburtstagsschranke?
Das Geburtstagsproblem zeigt, dass Kollisionen weit früher wahrscheinlich werden, als die Intuition nahelegt. Für einen Raum von 2^b Werten erreicht die Kollisionswahrscheinlichkeit nach etwa √(2^b) Erzeugungen ungefähr 50 % — der Quadratwurzel des Raums, nicht des gesamten Raums. Für 122 Zufallsbits sind das rund 2,7 × 10¹⁸ Bezeichner, sodass selbst die Erzeugung einer Milliarde UUIDs die Kollisionswahrscheinlichkeit verschwindend klein lässt.
Sollte ich mir in der Praxis Sorgen über UUID-Kollisionen machen?
Für UUIDs der Version 4 in jedem realistischen Maßstab lautet die Antwort fast immer nein — Sie müssten in der Größenordnung einer Trillion erzeugen, um eine nennenswerte Wahrscheinlichkeit zu erreichen.
Die praktischen Risiken liegen anderswo: ein schwacher oder unsachgemäß initialisierter Zufallszahlengenerator, der vorhersagbare oder wiederholte Werte erzeugt, oder das Kürzen einer UUID auf weniger Bits, um Speicher zu sparen. Wenn Sie Bezeichner kürzen, berechnen Sie die Wahrscheinlichkeit mit der reduzierten Bitzahl neu, bei der Kollisionen sehr viel früher wahrscheinlich werden.
Weitere Empfehlungen
Hash-Kollisionswahrscheinlichkeit
Kollisionswahrscheinlichkeit unter einer Menge von Hash-Werten abschätzen und ermitteln, wie viele Elemente für eine 50-%-Kollisionschance bei einer gegebenen Hash-Größe benötigt werden.