Das Geburtstagsproblem bei IDs
Zufällig erzeugte Kennungen wie UUIDs werden in Datenbanken, verteilten Systemen und APIs verwendet, weil sie ohne zentrale Vergabe auskommen. Die Frage ist, wie sicher sie eindeutig sind. Die Antwort liefert das Geburtstagsproblem: Schon bei 23 Personen haben mit über 50 Prozent Wahrscheinlichkeit zwei am selben Tag Geburtstag. Ebenso steigt das Risiko doppelter IDs nicht linear mit der Menge, sondern mit ihrem Quadrat.
Bei b Zufallsbits gibt es 2^b mögliche Werte. Werden n IDs erzeugt, gibt es n × (n − 1) ÷ 2 Paare, und jedes Paar stimmt mit Wahrscheinlichkeit 1 ÷ 2^b überein. Die Wahrscheinlichkeit für mindestens eine Kollision ist sehr genau 1 − e hoch minus Paare ÷ 2^b. Das Risiko von 50 Prozent wird bei etwa 1,18 × 2^(b/2) IDs erreicht, also bei der Quadratwurzel des Wertebereichs.
Eine UUID der Version 4 enthält nach RFC 9562 genau 122 Zufallsbits, die übrigen 6 Bit kennzeichnen Version und Variante. Version 7 kombiniert einen Zeitstempel in Millisekunden mit 74 Zufallsbits; dort ist für das Risiko die Zahl der IDs pro Millisekunde entscheidend, nicht die Gesamtzahl.
Wann reicht welche Länge?
Für die meisten Anwendungen sind 122 Bit mehr als genug. Selbst bei Billionen von IDs bleibt das Risiko weit unter dem von Hardwarefehlern oder Softwarefehlern. Kritisch werden kurze IDs: 32 Bit, etwa acht Hexadezimalzeichen, erreichen 50 Prozent Kollisionsrisiko bereits bei rund 77.000 IDs. Kurze Links, Bestellnummern oder Gutscheincodes brauchen deshalb entweder ausreichend Zeichen oder eine Prüfung auf Duplikate.
Voraussetzung ist ein guter Zufallsgenerator. Werden IDs mit einem schwachen Pseudozufallsgenerator oder nach einem Neustart mit gleichem Startwert erzeugt, können Kollisionen viel häufiger auftreten, als die Rechnung erwarten lässt. Für sicherheitsrelevante IDs wie Sitzungstoken sollte immer ein kryptografisch sicherer Generator verwendet werden.
Wer die Zeichenlänge statt der Bits kennt, rechnet um: Ein Hexadezimalzeichen trägt 4 Bit, ein Base64-Zeichen 6 Bit, ein Zeichen aus Ziffern und Kleinbuchstaben gut 5,17 Bit. Bei Formaten mit festen Teilen, etwa Präfixen, Zeitstempeln oder Prüfziffern, zählen nur die tatsächlich zufälligen Bits.
Auch ohne Rechnung gilt eine Faustregel: Die halbe Bitlänge ist ungefähr der Zweierlogarithmus der Menge, ab der Kollisionen wahrscheinlich werden. Bei 64 Bit sind das gut 4 Milliarden IDs. Eine Datenbank mit eindeutigem Index fängt seltene Duplikate zusätzlich ab. Das allgemeine Geburtstagsproblem rechnet der Geburtstagsparadoxon-Rechner.
Tipps und typische Fehler
IDs eindeutig halten.
- Zufall: Sicherer Generator.
- Bits: Nur Zufallsanteil.
- Index: Eindeutig setzen.
- Kurz: Duplikate prüfen.
Mehr zum Thema Wahrscheinlichkeit und Zufall
Häufige Fragen
Wie wahrscheinlich ist eine doppelte UUID?
Bei einer Milliarde UUIDs der Version 4 liegt die Wahrscheinlichkeit bei etwa 10⁻¹⁹, also praktisch null.
Ab wie vielen IDs wird eine Kollision wahrscheinlich?
Ab etwa der Quadratwurzel des Wertebereichs, bei b Bit also rund 1,18 × 2^(b/2) IDs.
Wie viele Zufallsbits hat eine UUID v4?
122 Bit; die übrigen 6 Bit legen Version und Variante fest.
Ist UUID v7 sicherer als v4?
Nicht in Bezug auf Kollisionen insgesamt; v7 ist sortierbar, hat aber weniger Zufallsbits je Millisekunde.
Wie viele Zeichen braucht eine kurze ID?
Für eine Million IDs mit sehr kleinem Risiko etwa 60 Zufallsbits, also rund 10 Base64-Zeichen.
- UUID Kollision Wahrscheinlichkeit
- UUID doppelt
- Kollisionswahrscheinlichkeit IDs
- Geburtstagsproblem Hash
- Zufalls-ID Länge
- UUID v4 eindeutig
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.