Sie haben wahrscheinlich bereits UUIDs in Ihren Projekten verwendet und dachten, sie seien einzigartig. Schauen wir uns die Hauptaspekte der Implementierung an und sehen, warum UUIDs praktisch einzigartig sind, da es eine winzige Möglichkeit gibt, dass dieselben Werte auftreten.
Die moderne Implementierung von UUIDs lässt sich auf RFC 4122 zurückführen, in dem fünf verschiedene Ansätze zur Generierung dieser Kennungen beschrieben werden. Wir werden jeden von ihnen durchgehen und die Implementierung von Version 1 und Version 4 durchgehen.
Theorie
UUID (Universal Unique IDentifier) ist eine 128-Bit-Zahl, die in der Softwareentwicklung als eindeutige Kennung für Elemente verwendet wird. Die klassische Textdarstellung besteht aus einer Reihe von 32 hexadezimalen Zeichen, die im 8-4-4-4-12-Muster durch Bindestriche in fünf Gruppen unterteilt sind.
Zum Beispiel:
3422b448-2460-4fd2-9183-8000de6f8343
UUID-Implementierungsinformationen sind in diese scheinbar zufällige Folge von Zeichen eingebettet:
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
Die Werte an den Positionen M und N definieren die Version bzw. Variante der UUID.
Ausführung
Die Versionsnummer wird durch die vier höchstwertigen Bits an Position M identifiziert. Heute gibt es die folgenden Versionen:
Möglichkeit
Dieses Feld definiert die Vorlage der in die UUID eingebetteten Informationen. Die Interpretation aller anderen Bits in der UUID hängt vom Wert der Variante ab.
Wir bestimmen es durch die ersten 1-3 höchstwertigen Bits an Position N.
Heutzutage wird am häufigsten Option 1 verwendet, bei der
MSB0gleich 1und MSB1gleich ist 0. Dies bedeutet , dass Platzhalter gegeben - Bits ausgewählt 8, 9, Aoder B.
Notiz:
1 0 0 0 = 8
1 0 0 1 = 9
1 0 1 0 = A
1 0 1 1 = B.
Wenn Sie also an Position N eine UUID mit solchen Werten sehen, ist dies die Kennung in Option 1.
Version 1 (Zeit + eindeutige oder zufällige Host-ID)
In diesem Fall wird die UUID wie folgt generiert: Einige identifizierende Eigenschaften des Geräts, das die UUID generiert, werden zur aktuellen Zeit hinzugefügt, meistens ist es die MAC-Adresse (auch als Knoten-ID bezeichnet).
Die Kennung wird durch Verketten einer 48-Bit-MAC-Adresse, eines 60-Bit-Zeitstempels, einer 14-Bit- "eindeutigen" Taktsequenz und 6 Bits erhalten, die für Versions- und Varianten-UUIDs reserviert sind.
Die Taktsequenz ist einfach ein Wert, der jedes Mal erhöht wird, wenn die Uhr geändert wird.
Der in dieser Version verwendete Zeitstempel ist die Anzahl der 100-Nanosekunden-Intervalle seit dem 15. Oktober 1582, dem Datum, an dem der Gregorianische Kalender erstellt wurde.
Möglicherweise kennen Sie das Unix-Zeitsystem seit Beginn einer Epoche. Es ist nur eine andere Art von Tag Null. Es gibt Dienste im Web, mit denen Sie eine zeitliche Darstellung in eine andere umwandeln können. Lassen Sie uns also nicht näher darauf eingehen.
Obwohl diese Implementierung recht einfach und zuverlässig aussieht, kann diese Methode aufgrund der Verwendung der MAC-Adresse des Computers, auf dem die Kennung generiert wird, nicht als universell angesehen werden. Besonders wenn Sicherheit das Hauptkriterium ist. Daher werden in einigen Implementierungen anstelle der Knotenkennung 6 zufällige Bytes verwendet, die einem kryptografisch geschützten Zufallszahlengenerator entnommen wurden.
Das Erstellen von UUID Version 1 sieht folgendermaßen aus:
- Die niedrigstwertigen 32 Bits des aktuellen UTC-Zeitstempels werden verwendet. Dies sind die ersten 4 Bytes (8 Hex-Zeichen) der UUID [
TimeLow]. - Die mittleren 16 Bits des aktuellen UTC-Zeitstempels werden verwendet. Dies sind die nächsten 2 Bytes (4 Hex-Zeichen) [
TimeMid]. - Die nächsten 2 Bytes (4 Hex-Zeichen) verketten die 4 Bits der UUID-Version mit den verbleibenden 12 MSBs des aktuellen UTC-Zeitstempels (der insgesamt 60 Bits enthält) [
TimeHighAndVersion]. - Die nächsten 1-3 Bits definieren die UUID-Versionsvariante. Die verbleibenden Bits enthalten eine Taktsequenz, die dieser Implementierung eine geringe Zufälligkeit verleiht. Dies vermeidet Kollisionen, wenn mehrere UUID-Generatoren auf demselben System ausgeführt werden: Entweder wird die Systemuhr für den Generator zurückgesetzt oder die Zeitänderung wird verlangsamt [
ClockSequenceHiAndRes && ClockSequenceLow]. - Die letzten 6 Bytes (12 Hexadezimalzeichen, 48 Bit) sind die "Knoten-ID", die normalerweise die Generator-MAC-Adresse [
NodeID] ist.
Die UUID der Version 1 wird mithilfe der Verkettung generiert:
TimeLow + TimeMid + TimeHighAndVersion + (ClockSequenceHiAndRes && ClockSequenceLow) + NodeID
Da diese Implementierung taktabhängig ist, müssen wir mit Kantensituationen umgehen. Um die Korrelation zwischen Systemen zu minimieren, wird die Taktsequenz standardmäßig als Zufallszahl verwendet - dies erfolgt nur einmal im gesamten Lebenszyklus des Systems. Dies gibt uns den zusätzlichen Vorteil, Knoten-IDs zu unterstützen, die systemübergreifend übertragen werden können, da die anfängliche Taktsequenz völlig unabhängig von der Knoten-ID ist.
Denken Sie daran, dass der Hauptzweck der Verwendung einer Taktsequenz darin besteht, unserer Gleichung eine gewisse Zufälligkeit hinzuzufügen. Die Taktsequenzbits verlängern den Zeitstempel und berücksichtigen Situationen, in denen mehrere UUIDs generiert werden, noch bevor sich der Prozessortakt ändert. Auf diese Weise vermeiden wir, dass dieselben Bezeichner erstellt werden, wenn die Uhr zurückgesetzt wird (Gerät ist ausgeschaltet) oder sich die Knotenbezeichner ändern. Wenn die Uhr zurückgesetzt ist oder hätte zurückgesetzt werden können (z. B. während das System ausgeschaltet war) und der UUID-Generator nicht überprüfen kann, ob die Kennungen mit späteren Zeitstempeln als dem angegebenen Uhrwert generiert wurden, muss die Uhrfolge geändert werden. Wenn wir den vorherigen Wert kennen, können wir ihn einfach erhöhen.Andernfalls muss es zufällig oder mit einem hochwertigen PRNG eingestellt werden.
Version 2 (Sicherheit einer verteilten Computerumgebung)
Der Hauptunterschied dieser Version zur vorherigen besteht darin, dass anstelle von "Zufälligkeit" in Form der niedrigstwertigen Bits der Taktsequenz hier eine Identifikationskennlinie des Systems verwendet wird. Oft ist dies nur die ID des aktuellen Benutzers. Version 2 wird seltener verwendet, sie unterscheidet sich kaum von Version 1, also fahren wir fort.
Version 3 (Name + MD5-Hash)
Wenn eindeutige Bezeichner zum Benennen oder Benennen von Informationen benötigt werden, wird normalerweise UUID Version 3 oder Version 5 verwendet.
Sie codieren alle "benannten" Entitäten (Sites, DNS, Klartext usw.) in einen UUID-Wert. Am wichtigsten ist, dass dieselbe UUID für denselben Namespace oder Text generiert wird.
Beachten Sie, dass der Namespace selbst eine UUID ist.
let namespace = “digitalbunker.dev”
let namespaceUUID = UUID3(.DNS, namespace)
// Ex:
UUID3(namespaceUUID, “/category/things-you-should-know-1/”)
4896c91b-9e61-3129-87b6-8aa299028058
UUID3(namespaceUUID, “/category/things-you-should-know-2/”)
29be0ee3-fe77-331e-a1bf-9494ec18c0ba
UUID3(namespaceUUID, “/category/things-you-should-know-3/”)
33b06619-1ee7-3db5-827d-0dc85df1f759
In dieser Implementierung wird der UUID-Namespace in eine mit dem Eingabenamen verkettete Folge von Bytes konvertiert und dann mit MD5 gehasht, was zu 128 Bit für die UUID führt. Wir schreiben dann einige der Bits neu, um die Version und die Versionsinformationen genau zu reproduzieren, und lassen den Rest unberührt.
Es ist wichtig zu verstehen, dass weder ein Namespace noch ein Eingabename basierend auf der UUID berechnet werden können. Dies ist eine irreversible Operation. Die einzige Ausnahme ist Brute-Force, wenn einer der Werte (Namespace oder Text) dem Angreifer bereits bekannt ist.
Bei gleicher Eingabe sind die generierten UUIDs der Versionen 3 und 5 deterministisch.
Version 4 (PRNG)
Einfachste Implementierung.
6 Bits sind für Version und Variante reserviert, es sind noch 122 Bits übrig. Diese Version generiert einfach 128 zufällige Bits und ersetzt dann 6 davon durch Versions- und Versionsdaten.
Solche UUIDs hängen vollständig von der Qualität des PRNG (Pseudozufallszahlengenerator) ab. Wenn sein Algorithmus zu einfach ist oder ihm Anfangswerte fehlen, steigt die Wahrscheinlichkeit, dass sich Bezeichner wiederholen.
In modernen Sprachen wird am häufigsten UUID Version 4 verwendet.
Die Implementierung ist recht einfach:
- Wir erzeugen 128 zufällige Bits.
- Schreiben Sie einige der Bits mit der richtigen Version und den richtigen Versionsinformationen neu:
- Nehmen Sie das siebte Bit und
0x0FUND, um das hohe Knabbern zu beseitigen. Und dann wird0x40OR verwendet, um Version 4 zuzuweisen. - Dann nehmen wir das neunte Byte, führen die
0x3FUND-Operation für c und die0x80ODER-Operation für c aus.
- Nehmen Sie das siebte Bit und
- Konvertieren Sie 128 Bit in Hex und fügen Sie Bindestriche ein.
Version 5 (Name + SHA-1-Hash)
Der einzige Unterschied zu Version 3 besteht darin, dass wir anstelle von MD5 den SHA-1-Hashing-Algorithmus verwenden. Diese Version wird der dritten vorgezogen (SHA-1> MD5).
Trainieren
Einer der wichtigen Vorteile von UUIDs besteht darin, dass ihre Einzigartigkeit nicht von einer zentralen Genehmigungsbehörde oder von der Koordinierung zwischen verschiedenen Systemen abhängt. Jeder kann eine UUID mit der Gewissheit erstellen, dass auf absehbare Zeit niemand anderes diesen Wert generiert.
Dies ermöglicht es, von verschiedenen Teilnehmern erstellte Kennungen in einer Datenbank zu kombinieren oder Kennungen mit einer vernachlässigbaren Kollisionswahrscheinlichkeit zwischen Datenbanken zu verschieben.
UUIDs können als Primärschlüssel in Datenbanken, als eindeutige Namen für hochgeladene Dateien und als eindeutige Namen für beliebige Webquellen verwendet werden. Sie benötigen keine zentrale Berechtigungsbehörde, um sie zu generieren. Dies ist jedoch eine zweischneidige Lösung. Aufgrund des Fehlens eines Controllers ist es unmöglich, die generierten UUIDs zu verfolgen.
Es gibt noch einige weitere Nachteile, die behoben werden müssen. Inhärente Zufälligkeit erhöht die Sicherheit, erschwert jedoch das Debuggen. Außerdem kann die UUID in einigen Situationen redundant sein. Angenommen, es ist nicht sinnvoll, 128 Bit zu verwenden, um Daten mit einer Gesamtgröße von weniger als 128 Bit eindeutig zu identifizieren.
Einzigartigkeit
Wenn Sie genügend Zeit haben, können Sie möglicherweise einen Wert wiederholen. Besonders im Fall von Version 4. In Wirklichkeit ist dies jedoch nicht der Fall. Wenn Sie über 100 Jahre eine Milliarde UUIDs pro Sekunde generieren würden, wäre die Wahrscheinlichkeit, dass sich einer der Werte wiederholt, etwa 50%. Dies ist im Hinblick auf die Tatsache, dass das PRNG eine ausreichende Menge an Entropie (wahre Zufälligkeit) bereitstellt, andernfalls ist die Wahrscheinlichkeit eines Doppels höher. Ein anschaulicheres Beispiel: Wenn Sie 10 Billionen UUIDs generiert haben, beträgt die Wahrscheinlichkeit, dass zwei identische Werte angezeigt werden, 0,00000006%.
Und im Fall von Version 1 wird die Uhr nur in 3603 auf Null zurückgesetzt. Wenn Sie also nicht vorhaben, Ihren Dienst bis 1583 am Laufen zu halten, sind Sie in Sicherheit.
Die Wahrscheinlichkeit des Auftretens eines Doppels bleibt jedoch bestehen, und in einigen Systemen versuchen sie, dies zu berücksichtigen. In den allermeisten Fällen können UUIDs jedoch als völlig einzigartig angesehen werden. Wenn Sie mehr Beweise benötigen, finden Sie hier eine einfache Visualisierung der Kollisionswahrscheinlichkeit in der Praxis.