Wir stellen vor: Randflake ID: ein verteilter, einheitlicher, unvorhersehbarer, eindeutiger Zufalls-ID-Generator.

Betrachten Sie eine Situation, in der wir eindeutige 64-Bit-Zufallszahlen generieren müssen und externe Parteien nicht in der Lage sein sollten, die nächste oder vorherige Zahl vorherzusagen.

Hier können wir einen 8-Byte-Zufallswert generieren, prüfen, ob er bereits in der Datenbank existiert, und ihn dann speichern, wenn er eindeutig ist.

Diese Methode hat jedoch mehrere Nachteile. Wir müssen jede generierte Zahl in einer Datenbank speichern, um die Eindeutigkeit zu gewährleisten. Die Notwendigkeit von mindestens einem Roundtrip zur Datenbank führt zu Latenzproblemen, insbesondere in einer verteilten Umgebung, in der Skalierbarkeit entscheidend ist.

Um diese Probleme zu lösen, stellen wir Randflake ID vor: einen verteilten, einheitlichen, unvorhersehbaren, eindeutigen Zufalls-ID-Generator.

Wie funktioniert Randflake ID?

Randflake ID ist inspiriert von Snowflake ID, dem weit verbreiteten k-sortierten ID-Generierungsmechanismus, der von X (ehemals Twitter) entwickelt wurde.

Snowflake ID verwendet den aktuellen Zeitstempel, eine Node ID und einen lokalen Zähler, um einen Bezeichner zu generieren.

Wir haben diesen Ansatz für die Generierung zufälliger eindeutiger IDs erweitert und ein neues Geheimschlüsselelement hinzugefügt.

Die zentrale Idee ist die Hinzufügung einer Blockchiffre-Schicht zum bestehenden eindeutigen ID-Generator, um die Vorhersagbarkeit der Beziehung zwischen Zahlen unmöglich zu machen.

Eine Blockchiffre ist eine grundlegende kryptografische Funktion, die einen Block von Klartext fester Länge in einen Block von Geheimtext gleicher Länge umwandelt. Diese Transformation wird durch einen kryptografischen Schlüssel gesteuert. Das Unterscheidungsmerkmal einer Blockchiffre ist ihre Reversibilität: Sie muss eine Eins-zu-Eins-Funktion (bijektiv) sein, die sicherstellt, dass jede eindeutige Eingabe einer eindeutigen Ausgabe entspricht und umgekehrt. Diese Eigenschaft ist entscheidend für die Entschlüsselung, da sie die Wiederherstellung des ursprünglichen Klartextes aus dem Geheimtext ermöglicht, wenn der richtige Schlüssel angewendet wird.

Durch den Einsatz einer Blockchiffre als Eins-zu-Eins-Funktion können wir garantieren, dass jede eindeutige Eingabe eine entsprechende eindeutige Ausgabe innerhalb des definierten Bereichs erzeugt.

Die Struktur und Designüberlegungen

Aufbauend auf diesen grundlegenden Konzepten wollen wir untersuchen, wie Randflake ID diese Ideen in der Praxis umsetzt.

Die Randflake ID-Struktur umfasst einen 30-Bit-Unix-Zeitstempel mit Sekundengenauigkeit, einen 17-Bit-Node-Identifikator, einen 17-Bit-lokalen Zähler und eine 64-Bit-Blockchiffre, die auf dem sparx64-Algorithmus basiert.

Hier sind einige Designentscheidungen:

• Einige VM-Instanzen in der Google Cloud Platform können die Uhr innerhalb von 0,2 ms synchronisieren, aber diese Genauigkeit ist im öffentlichen Internet oder bei anderen Cloud-Anbietern nicht verfügbar.

• Wir haben eine Sekundengenauigkeit gewählt, weil wir die Uhr zwischen den Nodes nur innerhalb weniger Millisekunden effektiv synchronisieren können.

• Ein 17-Bit-Node-Identifikator ermöglicht 131072 individuelle Generatoren gleichzeitig, die pro Prozess, pro Kern oder pro Thread zugewiesen werden können.

• In Systemen mit hohem Durchsatz kann ein 17-Bit-lokaler Zähler unzureichend sein. Um den Durchsatz zu erreichen, können wir mehrere Generatoren, jeder mit einer eindeutigen Node ID, zuweisen, um in einem einzigen Prozess oder Thread zu arbeiten.

• Wir haben sparx64 als 64-Bit-Blockchiffre übernommen, eine moderne, leichtgewichtige ARX-basierte Blockchiffre.

• Randflake IDs bieten interne Rückverfolgbarkeit, indem sie ihre Ursprungs-Node ID und ihren Zeitstempel nur denen offenbaren, die den geheimen Schlüssel besitzen.

• Der theoretische maximale Durchsatz beträgt 17.179.869.184 ID/s, was für die meisten globalen Anwendungen ausreichend ist.

Pseudocode zur Randflake ID-Generierung

Um den Randflake ID-Generierungsprozess weiter zu veranschaulichen, bietet der folgende Python-Pseudocode eine vereinfachte Implementierung:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sonntag, 27. Oktober 2024 3:33:20 Uhr UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 Bits für Zeitstempel (Lebensdauer von 34 Jahren)
10RANDFLAKE_NODE_BITS = 17  # 17 Bits für Node ID (max. 131072 Nodes)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 Bits für Sequenz (max. 131072 Sequenzen)
12
13# Derived constants
14RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
15RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
16RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
17
18class Randflake:
19    def __init__(self, node_id: int, secret: bytes):
20        self.node_id = int(node_id)
21        self.sequence = int(0)
22        self.rollover = int(time.time())
23        self.sbox = Sparx64(secret)
24
25    def _new_raw(self) -> int:
26        while True:
27            now = int(time.time())
28
29            self.sequence += 1
30            sequence = self.sequence
31
32            if sequence > RANDFLAKE_MAX_SEQUENCE:
33                if now > self.rollover:
34                    self.sequence = 0
35                    self.rollover = now
36                    sequence = 0
37                else:
38                    continue
39
40            timestamp = now - RANDFLAKE_EPOCH_OFFSET
41            return (timestamp << 34) | (self.node_id << 17) | sequence
42
43    def generate(self) -> int:
44        id_raw = self._new_raw()
45        src = struct.pack("<q", id_raw)
46        dst = bytearray(8)
47        self.sbox.encrypt(dst, src)
48        return struct.unpack("<q", dst)[0]

Eine produktionsreife Implementierung von Randflake mit einem Node ID Lease-Mechanismus ist auf GitHub verfügbar.

Weitere Überlegungen

In diesem Abschnitt werden wir einige zusätzliche Überlegungen zur Implementierung von Randflake ID diskutieren.

Node ID-Koordination

Wir schlagen eine Lease-basierte Node ID-Koordination vor.

Bei diesem Ansatz weist ein zentraler Koordinationsdienst jedem Generator eine eindeutige Node ID zu.

Diese Node ID wird während der Lease-Periode nicht neu zugewiesen, um die Eindeutigkeit zu gewährleisten, wodurch die Notwendigkeit häufiger Kommunikation mit dem Koordinationsdienst reduziert wird.

Der Generator, der die Lease hält, kann eine Verlängerung der Lease vom Koordinationsdienst anfordern, wenn die Verlängerungsbedingung erfüllt ist.

Die Verlängerungsbedingung bezieht sich auf eine Reihe von Kriterien, die erfüllt sein müssen, damit die Lease verlängert wird, z. B. dass der Generator noch aktiv ist und die Node ID benötigt.

Der Leaseholder ist der aktuelle Inhaber des Node ID-Bereichs.

Die Lease gilt als aktiv und nicht abgelaufen, wenn sie sich innerhalb ihres gültigen Zeitraums befindet.

Auf diese Weise können wir Roundtrips auf einen pro Lease-Verlängerungsperiode reduzieren, wodurch Latenzzeiten minimiert und die Effizienz in verteilten Systemen verbessert werden.

Abmilderung gegen fehlerhafte Uhr

Der Lease-Dienst muss die Zeitstempelkonsistenz bei der Zuweisung einer Lease überprüfen. Die zugewiesene Lease-Startzeit muss größer oder gleich der letzten Lease-Startzeit sein.

Der Generator sollte die Anfrage ablehnen, wenn der aktuelle Zeitstempel kleiner als die Lease-Startzeit oder größer als die Lease-Endzeit ist.

Dieses Verfahren ist wichtig, um die Eindeutigkeit der generierten IDs zu schützen, wenn die Uhr zurückspringt. Wenn beispielsweise eine Uhr zurückspringt, könnte eine neue Lease mit einer Startzeit zugewiesen werden, die früher als eine zuvor zugewiesene Lease liegt, was potenziell zur Generierung doppelter IDs führen könnte. Durch das Ablehnen von Anfragen mit Zeitstempeln innerhalb einer bestehenden Lease-Periode verhindern wir dieses Szenario und erhalten die Eindeutigkeit der IDs.

Gleichmäßigkeit der ID-Verteilung

Basierend auf dem obigen Histogramm können wir feststellen, dass die Verteilung der generierten Randflake IDs sehr gleichmäßig ist. Dies deutet darauf hin, dass die ID-Verteilung direkt als Sharding-Schlüssel verwendet werden kann.

Fazit

In diesem Artikel haben wir Randflake vorgestellt, einen neuartigen ID-Generierungsalgorithmus, der die Vorteile von Snowflake und Sparx64 kombiniert.

Wir hoffen, dass dieser Artikel Ihnen ein umfassendes Verständnis von Randflake und seiner Implementierung vermittelt hat.

Den vollständigen Quellcode für Randflake finden Sie auf GitHub.

Wenn Sie Fragen oder Anregungen haben, zögern Sie bitte nicht, uns zu kontaktieren. Wir suchen auch Mitwirkende, die Randflake verbessern und in anderen Programmiersprachen implementieren möchten.

Wir planen, einen produktionsreifen Koordinationsdienst für Randflake und Snowflake zu veröffentlichen, der auf GitHub als Open Source verfügbar sein wird. Bleiben Sie dran für Updates!