UUID-Algorithmusprinzipien: Verwenden von Python, um zu zeigen, warum er sich kaum wiederholt

In der verteilten Systementwicklung müssen wir oft eindeutige Bezeichner für Daten generieren. Von primären Datenbankschlüsseln bis hin zu verteilten Cache-Schlüsseln, von Protokollverfolgungs-IDs bis hin zu Nachrichtenwarteschlangen-Nachrichten-IDs stellen diese Szenarien extrem hohe Anforderungen an die Eindeutigkeit von Bezeichnern. Und UUID (Universally Unique Identifier) ist eine ausgezeichnete Lösung für solche Probleme. Heute werden wir uns mit den Algorithmusprinzipien von UUID befassen, es mit Python-Code implementieren und eine Kernfrage beantworten: Warum wiederholen sich UUIDs fast nie?

Was ist UUID?

UUID ist ein standardisierter eindeutiger Bezeichner, der von der IETF (Internet Engineering Task Force) definiert wird. Sein vollständiger Name lautet Universally Unique Identifier. Es handelt sich um eine 128-Bit-Zahl, die normalerweise als 36-Zeichen-String im Format von fünf Segmenten hexadezimaler Zahlen dargestellt wird: 8-4-4-4-12. Zum Beispiel: f81d4fae-7dec-11d0-a765-00a0c91e6bf6.

Hinter dieser scheinbar einfachen Zeichenkette verbirgt sich ein exquisites Algorithmusdesign. Sein hervorstechendstes Merkmal ist, dass er in einem verteilten System ohne die Koordination einer zentralen Autorität global eindeutige Bezeichner generieren kann. Dies bedeutet, dass selbst ohne Netzwerkverbindung die von verschiedenen Geräten generierten UUIDs fast unmöglich zu wiederholen sind.

Die fünf Versionen von UUID

UUID hat nicht nur eine Generierungsmethode, sondern definiert 5 Versionen, die jeweils für unterschiedliche Szenarien geeignet sind:

• Version 1 (basierend auf Zeitstempel und MAC-Adresse): Generiert durch Kombinieren des aktuellen Zeitstempels, der Taktfolge und des Knotens (normalerweise eine MAC-Adresse)
• Version 2 (DCE-Sicherheitsversion): Führt POSIX UID/GID auf der Grundlage von Version 1 ein und wird selten verwendet
• Version 3 (MD5-Hash basierend auf Namespace): Berechnet für den Namespace und den Namen über den MD5-Hash-Algorithmus
• Version 4 (zufällig generiert): Verlässt sich vollständig auf Zufallszahlen für die Generierung
• Version 5 (SHA-1-Hash basierend auf Namespace): Ähnlich wie Version 3, verwendet jedoch den SHA-1-Hash-Algorithmus

In der tatsächlichen Entwicklung werden die Versionen 1 und 4 am häufigsten verwendet. Version 1 eignet sich für Szenarien, die eine Sortierung nach Zeit erfordern, während Version 4 sich für Szenarien mit höheren Anforderungen an die Zufälligkeit eignet.

Generieren von UUID mit Python

Das Modul uuid in der Python-Standardbibliothek bietet Funktionen zum Generieren verschiedener Versionen von UUID. Sehen wir uns an, wie man es benutzt:

import uuid

# Generieren von Version 1 UUID (basierend auf Zeitstempel und MAC-Adresse)
uuid1 = uuid.uuid1()
print(f"Version 1 UUID: {uuid1}")

# Generieren von Version 4 UUID (zufällig generiert)
uuid4 = uuid.uuid4()
print(f"Version 4 UUID: {uuid4}")

# Generieren von Version 3 UUID (MD5-Hash basierend auf Namespace und Name)
namespace = uuid.NAMESPACE_URL
name = "https://example.com"
uuid3 = uuid.uuid3(namespace, name)
print(f"Version 3 UUID: {uuid3}")

# Generieren von Version 5 UUID (SHA-1-Hash basierend auf Namespace und Name)
uuid5 = uuid.uuid5(namespace, name)
print(f"Version 5 UUID: {uuid5}")

Wenn Sie diesen Code ausführen, erhalten Sie eine Ausgabe ähnlich der folgenden:

Version 1 UUID: f81d4fae-7dec-11d0-a765-00a0c91e6bf6
Version 4 UUID: 3b9a7b3a-9c7d-4e5f-8a9b-0c1d2e3f4a5b
Version 3 UUID: 1b9d6bcd-bbfd-366d-9b5d-ab8dfbbd4bed
Version 5 UUID: 886313e1-3b8a-5372-9b90-0c9aee199e5d

Detaillierte Analyse der UUID-Algorithmusprinzipien

Generierungsprinzip der Version 1 UUID

Die Generierung der Version 1 UUID ist die komplexeste und spiegelt am besten das exquisite Design von UUID wider. Seine 128 Bit bestehen aus den folgenden Teilen:

• 60-Bit-Zeitstempel: Gezählt basierend auf 100-Nanosekunden-Intervallen seit 00:00:00 am 15. Oktober 1582
• 14-Bit-Taktfolge: Wird verwendet, um das Problem der Takt-Rückverfolgung zu behandeln
• 48-Bit-Knotenbezeichner: Normalerweise eine MAC-Adresse, die sicherstellt, dass sich von verschiedenen Geräten generierte UUIDs unterscheiden

Der Pseudocode lautet wie folgt:

def generate_uuid1():
    # Abrufen des aktuellen Zeitstempels (in 100-Nanosekunden-Einheiten)
    timestamp = get_current_timestamp()
    # Abrufen der Taktfolge (zur Behandlung der Takt-Rückverfolgung)
    clock_seq = get_clock_sequence()
    # Abrufen des Knotenbezeichners (normalerweise eine MAC-Adresse)
    node = get_mac_address()
    
    # Kombinieren Sie jeden Teil zu einer 128-Bit-Zahl
    uuid = (timestamp << 68) | (clock_seq << 48) | node
    
    # In Standard-String-Format konvertieren
    return format_uuid(uuid)

Es gibt einige wichtige Punkte zu beachten:

• Zeitstempel-Startpunkt: Der 15. Oktober 1582 wird gewählt, weil dies der Tag ist, an dem der Gregorianische Kalender eingeführt wurde, was von historischer Bedeutung ist.
• Taktfolge: Wenn die Systemuhr zurückverfolgt wird, erhöht sich die Taktfolge, um sicherzustellen, dass die generierte UUID immer noch eindeutig ist, selbst wenn der Zeitstempel kleiner wird.
• Knotenbezeichner: Die Verwendung einer MAC-Adresse kann sicherstellen, dass von verschiedenen Geräten generierte UUIDs nicht in Konflikt stehen, bringt aber auch Datenschutzprobleme mit sich. Daher verwenden einige Implementierungen anstelle von MAC-Adressen zufällig generierte Knotenbezeichner.

Generierungsprinzip der Version 4 UUID

Die Generierung der Version 4 UUID ist relativ einfach und basiert hauptsächlich auf Zufallszahlen:

• 122-Bit-Zufallszahl: Bietet die Hauptgarantie für Eindeutigkeit
• 6 feste Bits: Werden verwendet, um die UUID-Version und -Variante zu identifizieren

Der Pseudocode lautet wie folgt:

def generate_uuid4():
    # Generieren einer 122-Bit-Zufallszahl
    random_bits = generate_random_bits(122)
    # Festlegen von Versionsbits (4 Bits) und Variant-Bits (2 Bits)
    version = 4 << 12
    variant = 2 << 62
    # Alle Teile kombinieren
    uuid = random_bits | version | variant
    # In Standard-String-Format konvertieren
    return format_uuid(uuid)

Die Zufälligkeit der Version 4 UUID ist der Schlüssel zu ihrer Eindeutigkeit, und wir werden ihre Kollisionswahrscheinlichkeit später im Detail besprechen.

Generierungsprinzipien der UUIDs der Versionen 3 und 5

Die UUIDs der Versionen 3 und 5 werden basierend auf Namespaces und Namen generiert, und ihre Prinzipien ähneln sich:

1. Konvertieren der Namespace-UUID in eine Byte-Sequenz
2. Konvertieren des Namens in eine UTF-8-codierte Byte-Sequenz
3. Verketten der Namespace-Bytes und der Namens-Bytes
4. Durchführen einer Hash-Berechnung auf dem verketteten Ergebnis (MD5 für Version 3, SHA-1 für Version 5)
5. Nehmen Sie die ersten 128 Bits des Hash-Ergebnisses und legen Sie die Versionsbits und Variant-Bits fest

Der Vorteil dieser Methode besteht darin, dass für denselben Namespace und Namen immer dieselbe UUID generiert werden kann, was in einigen Szenarien sehr nützlich ist.

Warum wiederholen sich UUIDs fast nie?

Dies ist die Frage, die alle am meisten beschäftigt. Die Eindeutigkeit von UUID wird durch die folgenden Aspekte gewährleistet:

1. Riesiger Raum UUID ist 128 Bit lang, was bedeutet, dass es insgesamt 2^128 mögliche UUIDs gibt. Wie groß ist diese Zahl? Sie beträgt ungefähr 3,4×10^38. Um Ihnen ein intuitives Verständnis zu vermitteln:

   • Die Anzahl der Sandkörner auf der Erde beträgt ungefähr 7,5×10^18
   • Die Anzahl der Sterne im beobachtbaren Universum beträgt ungefähr 10^22
   • 2^128 ist ungefähr 3,4×10^16 mal die Anzahl der Sterne im beobachtbaren Universum Dies bedeutet, dass es selbst wenn wir 1 Billion UUIDs pro Sekunde generieren, etwa 10^18 Jahre dauern würde, um alle möglichen UUIDs zu erschöpfen, was weitaus länger ist als das Alter des Universums (etwa 13,8 Milliarden Jahre).

2. Gut gestaltete Zufälligkeit Für Version 4 UUID werden alle 122 Bits zufällig generiert. Laut der Wahrscheinlichkeitstheorie ist die Wahrscheinlichkeit einer Kollision zwischen zwei zufällig generierten UUIDs extrem gering. Konkret kann nach dem Generieren von n UUIDs die Wahrscheinlichkeit einer Kollision anhand der Näherungsformel berechnet werden: P(n) ≈ n² / (2×2^128) Wenn n=10^12 ist, beträgt die Kollisionswahrscheinlichkeit ungefähr 10^24 / (2×3,4×10^38) ≈ 1,47×10^-15, was eine fast vernachlässigbare Wahrscheinlichkeit ist.

3. Eindeutigkeit in Zeit und Raum Für Version 1 UUID, in der zusätzlich zum Inkrement des Zeitstempels, das die Eindeutigkeit von auf demselben Gerät generierten UUIDs gewährleistet, der Knotenbezeichner (normalerweise eine MAC-Adresse) auch die Eindeutigkeit von auf verschiedenen Geräten generierten UUIDs gewährleistet. Da MAC-Adressen weltweit eindeutig sind, wird in Kombination mit dem kontinuierlich ansteigenden Zeitstempel die Eindeutigkeit der UUID aus sowohl Zeit- als auch Raumdimensionen gewährleistet.

4. Behandlung der Takt-Rückverfolgung In verteilten Systemen ist die Takt-Rückverfolgung ein häufiges Problem (z. B. wenn der NTP-Server die Zeit anpasst). Version 1 UUID behandelt dieses Problem über die Taktfolge: Wenn eine Takt-Rückverfolgung erkannt wird, erhöht sich die Taktfolge, um sicherzustellen, dass die generierte UUID immer noch eindeutig ist, selbst wenn der Zeitstempel kleiner wird.

Wahrscheinlichkeit einer UUID-Kollision in praktischen Anwendungen

Obwohl UUIDs theoretisch kollidieren können, ist diese Wahrscheinlichkeit in praktischen Anwendungen so gering, dass sie ignoriert werden kann. Sehen wir uns einige konkrete Zahlen an:

• Beim Generieren von 1 Milliarde Version 4 UUIDs beträgt die Kollisionswahrscheinlichkeit ungefähr 10^-18
• Beim Generieren von 1 Billion Version 4 UUIDs beträgt die Kollisionswahrscheinlichkeit ungefähr 10^-15
• Selbst beim Generieren von 10^20 Version 4 UUIDs (was erfordern würde, dass jede Person auf der Erde 1 Million UUIDs pro Sekunde für 100 Jahre generiert) beträgt die Kollisionswahrscheinlichkeit nur etwa 10^-8

Um diese Wahrscheinlichkeit intuitiver zu verstehen, gibt es eine anschauliche Metapher: Die Wahrscheinlichkeit, von einem Meteoriten getroffen zu werden, ist höher als die Wahrscheinlichkeit, zwei identische UUIDs zu generieren.

Anwendungsszenarien von UUID

Die Eigenschaften von UUID machen es in vielen Szenarien sehr nützlich:

• Verteilte Datenbanken: In Sharded Databases kann UUID als global eindeutiger Primärschlüssel verwendet werden, um ID-Konflikte zwischen verschiedenen Shards zu vermeiden.
• Verteilter Cache: Als Cache-Schlüssel, der sicherstellt, dass von verschiedenen Knoten generierte Cache-Schlüssel nicht in Konflikt stehen.
• Protokollverfolgung: In verteilten Systemen kann die Verwendung von UUID als Verfolgungs-ID die vollständige Verknüpfung von Anforderungen über Dienste hinweg verfolgen.
• Nachrichtenwarteschlangen: Als eindeutiger Bezeichner von Nachrichten, der eine idempotente Verarbeitung von Nachrichten gewährleistet.
• Dateibenennung: In verteilten Dateisystemen kann die Verwendung von UUID als Dateiname Namenskonflikte vermeiden.
• Sitzungsidentifizierung: Als eindeutiger Bezeichner von Benutzersitzungen ist sie sicherer als automatisch inkrementierende IDs und nicht leicht zu erraten.

Vor- und Nachteile von UUID

Vorteile

• Globale Eindeutigkeit: Eindeutigkeit kann in verteilten Systemen ohne Koordination gewährleistet werden.
• Keine zentrale Autorität erforderlich: Der Generierungsprozess hängt nicht von einem zentralen Server ab.
• Plattformübergreifende Kompatibilität: Der UUID-Standard wird weitgehend unterstützt, und fast alle Programmiersprachen verfügen über entsprechende Implementierungen.
• Umfangreiche Informationen: Version 1 UUID enthält Zeitinformationen, und die Generierungszeit kann ungefähr beurteilt werden.

Nachteile

• Lange Länge: Die Länge von 36 Zeichen ist viel länger als die automatisch inkrementierende ID, was die Speicher- und Übertragungskosten erhöhen kann.
• Unordnung: UUID ist ungeordnet und nicht als Primärschlüssel geeignet, der sortiert werden muss.
• Schlechte Lesbarkeit: Im Vergleich zu automatisch inkrementierenden IDs weist UUID eine schlechte Lesbarkeit auf.

Zusammenfassung

UUID ist ein exquisites Schema zur Generierung eindeutiger Kennungen. Es stellt sicher, dass sich in verteilten Systemen generierte Kennungen fast nie durch einen riesigen Raum, eine durchdachte Zufälligkeit und die Kombination aus Zeit und Raum wiederholen.

Ob es sich um die Generierungsmethode von Version 1 basierend auf Zeitstempel und MAC-Adresse oder um Version 4 basierend auf Zufallszahlen handelt, jede hat ihre anwendbaren Szenarien. In der tatsächlichen Entwicklung können wir die entsprechende UUID-Version entsprechend den spezifischen Anforderungen auswählen.

Obwohl UUID nicht perfekt ist, können seine Länge und Unordnung einige Probleme mit sich bringen, aber in den meisten verteilten Systemen überwiegen seine Vorteile bei weitem seine Nachteile, und es ist die bevorzugte Option für die Implementierung global eindeutiger Kennungen.

Wenn Sie das nächste Mal UUID in Ihrem Code verwenden, sollten Sie über das exquisite Design hinter diesen 36 Zeichen nachdenken und darüber, wie es Ihre Daten im riesigen digitalen Raum eindeutig kennzeichnet.

Leapcell: Das Beste von Serverless Webhosting

Abschließend möchte ich eine Plattform empfehlen, die sich am besten für die Bereitstellung von Python-Diensten eignet: Leapcell

🚀 Erstellen Sie mit Ihrer Lieblingssprache

Entwickeln Sie mühelos in JavaScript, Python, Go oder Rust.

🌍 Stellen Sie unbegrenzt viele Projekte kostenlos bereit

Zahlen Sie nur für das, was Sie nutzen – keine Anfragen, keine Gebühren.

⚡ Pay-as-You-Go, keine versteckten Kosten

Keine Leerlaufgebühren, nur nahtlose Skalierbarkeit.

📖 Entdecken Sie unsere Dokumentation

🔹 Folgen Sie uns auf Twitter: @LeapcellHQ