Warum UUIDs praktisch nie kollidieren (auch ohne Überprüfung)

Eine gewöhnliche zufällige UUID wird unabhängig erzeugt, von einer beliebigen Anzahl völlig unkoordinierter Systeme, ohne zentrale Instanz, die die nächste verfügbare Kennung vergibt, und ohne Abgleich mit einer Liste bereits verwendeter Kennungen – und trotzdem sind Kollisionen praktisch etwas, das nie passiert. Das ist eine wirklich gewagte Behauptung, die allein auf Wahrscheinlichkeit statt auf Koordination beruht, und um zu verstehen, warum sie zutrifft, braucht es dieselbe kontraintuitive Mathematik, die ein viel berühmteres Rätsel erklärt: Wie wenige Menschen müssen in einem Raum sein, bevor es wahrscheinlich wird, dass zwei von ihnen am selben Tag Geburtstag haben?

Das klassische Geburtstagsparadoxon fragt, wie viele Menschen in einem Raum versammelt sein müssen, bevor die Chance, dass zwei von ihnen denselben Geburtstag haben, bei über 50 Prozent liegt, und die Antwort – nur 23 Personen, bei 365 möglichen Geburtstagen – überrascht die meisten, die intuitiv eine Zahl viel näher an 365 selbst erwarten. Der Grund, warum die wahre Antwort so viel kleiner ausfällt, liegt darin, dass der relevante Vergleich nicht lautet „teilt irgendeine bestimmte Person meinen Geburtstag", sondern „teilt irgendein Paar, aus allen möglichen Paaren im Raum, einen Geburtstag" – und die Anzahl möglicher Paare wächst weit schneller als die Anzahl der Personen, denn bei 23 Personen gibt es bereits 253 verschiedene Paare, jedes davon eine unabhängige Gelegenheit für eine Übereinstimmung. Genau dieses mathematische Muster – die Anzahl der Vergleichsmöglichkeiten wächst quadratisch, während die Anzahl der Elemente nur linear wächst – nennt man das Geburtstagsproblem, und es gilt direkt für jede Situation mit zufälligen Werten aus einem festen Raum, die auf Duplikate geprüft werden, UUIDs eingeschlossen.

Eine gewöhnliche zufällige UUID (Version 4) schöpft aus einem Raum von 122 wirklich zufälligen Bits – eine Handvoll der insgesamt 128 Bits ist durch die Formatspezifikation selbst festgelegt, um die Version zu kennzeichnen –, was bedeutet, dass die Gesamtzahl möglicher Werte 2 hoch 122 beträgt, eine kaum vorstellbar große Zahl. Wendet man dieselbe Geburtstagsparadoxon-Logik an, die für das 365-Tage-Beispiel gilt, nur hochskaliert auf diesen weitaus größeren Raum, erhält man den Punkt, an dem eine Kollision wahrscheinlich wird: Es müssten etwa 2,7 Trillionen UUIDs erzeugt werden, bevor die Wahrscheinlichkeit einer Kollision zwischen zweien von ihnen auf etwa 50 Prozent steigt – zum Vergleich: Das sind mehr UUIDs, als es geschätzte Sandkörner an allen Stränden der Erde gibt. Ein einzelnes System, oder selbst eine große Zahl kombinierter Systeme, das UUIDs mit jedem realistischen Tempo der realen Welt erzeugt, würde einen Zeitraum brauchen, der das Alter des Universums bei Weitem übersteigt, um sich dieser Schwelle auch nur anzunähern – das ist die eigentliche mathematische Grundlage dafür, UUID-Kollisionen in der Praxis als etwas zu behandeln, das man nicht prüfen muss.

UUID Version 7, die neuerdings speziell standardisiert wurde, um Kennungen zu erzeugen, die sich grob chronologisch sortieren lassen, erreicht das, indem sie einen Zeitstempel mit Millisekundengenauigkeit in die führenden Bits der Kennung setzt, statt wie Version 4 den gesamten Wert mit Zufallsdaten zu füllen. Das könnte so klingen, als würde es die Garantie der Kollisionsresistenz schwächen, da nun ein Teil des Werts vorhersehbar statt zufällig ist – doch die restlichen Bits sind weiterhin mit derselben Menge echter Zufallsdaten gefüllt wie zuvor, und da zwei UUIDs, die in genau derselben Millisekunde erzeugt werden, immer noch exakt übereinstimmende Zufallsreste bräuchten, bleibt die praktische Kollisionsresistenz bei jeder realistischen Erzeugungsrate vergleichbar mit der von Version 4. Was v7 tatsächlich ändert, ist eine andere, unabhängige Eigenschaft – die Sortierreihenfolge –, nicht die hier besprochene Kollisionsmathematik, und es lohnt sich, beides gedanklich getrennt zu halten: Einzigartigkeit ergibt sich aus der schieren Größe des Zufallsraums, während Sortierbarkeit daher kommt, wo der Zeitstempel innerhalb des Werts sitzt.

Weil die Kollisionswahrscheinlichkeit wirklich, nicht nur beiläufig, vernachlässigbar ist, können Systeme völlig unabhängig voneinander eindeutige Kennungen erzeugen – eine mobile App, die offline ohne Netzwerkverbindung arbeitet, eine serverlose Funktion, die in Millisekunden entsteht und wieder verschwindet, tausend parallel laufende Microservice-Instanzen gleichzeitig – ganz ohne Koordination untereinander und ohne zentrales Register, das mitführt, was bereits vergeben wurde, und trotzdem mit der mathematisch fundierten Erwartung, dass keine zwei dieser Kennungen je kollidieren werden. Genau das ist eine Eigenschaft, die eine zentral vergebene, fortlaufende Kennung ohne eine gemeinsame koordinierende Instanz, die alles verlangsamt, nie bieten könnte – und genau deshalb wurden zufällige UUIDs zur Standardwahl für verteilte Systeme, die Kennungen brauchen, mit denen kein Koordinationsschritt sonst mithalten könnte.