Snowflake ID Generator - Eindeutige verteilte IDs erstellen

Was ist ein Snowflake-ID-Generator?

Ein Snowflake-ID-Generator erstellt aus einem Zeitstempel, einer Maschinenkennung und einer Sequenznummer eine eindeutige 64-Bit-Zahl. Twitter entwickelte das Format im Jahr 2010, damit jeder Tweet eine Kennung erhielt, die viele Server gleichzeitig erzeugen konnten, ohne sich gegenseitig fragen zu müssen: „Wurde diese Nummer bereits verwendet?“ Dieses Tool erstellt aus den eingegebenen Werten eine Snowflake-ID und zeigt, wie diese Werte die 64 Bits belegen.

So funktioniert dieser Snowflake-ID-Generator

Der Generator verwendet vier Eingaben:

• Zeitstempel: ein Unix-Zeitstempel in Millisekunden. Leer lassen, um die aktuelle Zeit zu verwenden.
• Maschinen-ID: eine ganze Zahl von 0 bis 31 (5 Bits). Dies ist Twitters ursprüngliche „Worker-ID“.
• Rechenzentrums-ID: eine ganze Zahl von 0 bis 31 (5 Bits).
• Sequenznummer: eine ganze Zahl von 0 bis 4095 (12 Bits), mit der IDs unterschieden werden, die in derselben Millisekunde erstellt wurden.

Das Tool kombiniert die vier Werte zu einer 64-Bit-ID. Anschließend zeigt es das Ergebnis als Binärzahl, aufgeteilt in die Segmente für Zeitstempel, Rechenzentrum, Maschine und Sequenz.

Der Zeitstempel wird ab einem festen Ausgangspunkt gemessen, der als Twitter-Epoche bezeichnet wird: 4. November 2010, 1:42:54,657 UTC beziehungsweise 1.288.834.974.657 Millisekunden nach der Unix-Epoche. Dieser Generator ermöglicht keine Änderung dieses Ausgangspunkts. Jede erzeugte ID wird ab demselben festen Datum gemessen.

Struktur einer Snowflake-ID

Eine Snowflake-ID ist eine 64-Bit-Ganzzahl, die in vier Teile aufgeteilt und vom höchstwertigen Bit abwärts gelesen wird:

Das führende Bit ist immer 0, daher ist eine Snowflake-ID stets eine positive Zahl. Das 41-Bit-Zeitstempelfeld und das 12-Bit-Sequenzfeld sind die beiden Teile, die Snowflake-IDs für die Sortierung geeignet machen: Später erzeugte IDs haben ein größeres Zeitstempelsegment und werden daher nach früheren IDs sortiert.

Formel für Snowflake-IDs

Der Generator erstellt die ID mit dieser Formel:

$d = t - 1288834974657$

$I = (d << 22) \mathbin{|} (c << 17) \mathbin{|} (m << 12) \mathbin{|} s$

Dabei steht d für die Differenz, t für den eingegebenen Zeitstempel in Millisekunden, I für die fertige ID, c für die Rechenzentrums-ID, m für die Maschinen-ID und s für die Sequenznummer.

<< ist eine Linksverschiebung von Bits. Eine Verschiebung einer Zahl um 22 Bits nach links entspricht der Multiplikation mit 2²² beziehungsweise mit 4.194.304. Die Verschiebungswerte (22, 17, 12) ergeben sich direkt aus den Feldbreiten: Das Sequenzfeld ist 12 Bits breit, daher liegt die Maschinen-ID 12 Bits weiter oben; das Maschinenfeld ist 5 Bits breit, daher liegt die Rechenzentrums-ID 17 Bits weiter oben (12 + 5), und so weiter.

So wird eine Snowflake-ID berechnet: Durchgerechnetes Beispiel

Angenommen, jemand gibt Folgendes ein:

• Zeitstempel: 1.288.834.975.657 (genau 1.000 ms nach der Twitter-Epoche)
• Rechenzentrums-ID: 1
• Maschinen-ID: 1
• Sequenznummer: 0

Schritt 1 — Differenz bestimmen. Die Epoche vom Zeitstempel abziehen: 1.288.834.975.657 − 1.288.834.974.657 = 1.000.

Schritt 2 — Jedes Feld an die richtige Position verschieben.

• Zeitstempel: 1.000 << 22 = 4.194.304.000
• Rechenzentrums-ID: 1 << 17 = 131.072
• Maschinen-ID: 1 << 12 = 4.096
• Sequenz: 0

Schritt 3 — Mit bitweisem ODER kombinieren. Da sich keines der verschobenen Felder überschneidet, ergibt ihre Addition dasselbe Ergebnis wie die ODER-Verknüpfung:

4.194.304.000 + 131.072 + 4.096 + 0 = 4.194.439.168

Das ist die Snowflake-ID für diese Eingabe. Die Ergebnisansicht des Tools teilt dieselbe 64-Bit-Binärzeichenfolge wieder in einen 41-Bit-Zeitstempelblock, einen 5-Bit-Rechenzentrumsblock, einen 5-Bit-Maschinenblock und einen 12-Bit-Sequenzblock auf, sodass die Struktur der Zahl sichtbar bleibt.

Wo Snowflake-IDs verwendet werden

Twitter entwickelte das Format, um Tweets über Tausende von Datenbankmaschinen hinweg eindeutige, ungefähr zeitlich geordnete IDs zu geben, ohne einen zentralen Zähler, den jeder Server prüfen müsste. Discord und Instagram übernahmen später ähnliche 64-Bit-ID-Entwürfe für Nachrichten und Beiträge. Dasselbe Prinzip findet sich bei der Datenbankpartitionierung, bei Bestell-IDs für E-Commerce-Systeme und in Ereignisprotokollen verteilter Anwendungen. Es eignet sich überall dort, wo viele Maschinen unabhängig IDs vergeben und diese dennoch ungefähr nach ihrer Zeit sortiert werden müssen.

Einschränkungen von Snowflake-IDs

Ein Snowflake-Generator im Produktivbetrieb führt normalerweise eine eigene laufende Uhr: Für jede ID, die in derselben Millisekunde erstellt wird, erhöht er die Sequenznummer und wartet auf die nächste Millisekunde, sobald die Sequenz 4.095 erreicht. Dieses Tool speichert zwischen Berechnungen keinen Zustand. Es erstellt eine ID aus den jeweils eingegebenen Werten. Dadurch eignet es sich zur Untersuchung des Formats, unterscheidet sich aber von einem laufenden Produktivdienst.

Das Design hat unabhängig von der jeweiligen Implementierung feste Grenzen:

• Feste Epoche: Dieser Generator akzeptiert nur Zeitstempel ab 4. November 2010 (der Twitter-Epoche). Frühere Daten können nicht codiert werden.
• Obergrenze des Zeitstempels: Das 41-Bit-Zeitstempelfeld läuft ungefähr im Juli 2080 über. Danach passt die Differenz zur Epoche nicht mehr in 41 Bits.
• Sequenzgrenze: Eine Maschine kann in derselben Millisekunde nur 4.096 verschiedene IDs (0–4095) vergeben, bevor sich Werte wiederholen würden.
• Maschinenadressraum: Mit jeweils 5 Bits für Maschinen-ID und Rechenzentrums-ID stehen einer Bereitstellung 1.024 verschiedene Maschinenkennungen (32 × 32) zur kollisionsfreien Vergabe zur Verfügung.
• Lokale, nicht globale Sortierung: IDs lassen sich nur dann korrekt miteinander vergleichen, wenn sie von Maschinen mit synchronisierten Uhren stammen. Eine Uhrabweichung zwischen Maschinen kann die strikte zeitliche Reihenfolge beeinträchtigen.

Geschichte der Snowflake-ID

Twitter kündigte das Snowflake-ID-Format im Jahr 2010 als Ersatz für einfache, automatisch inkrementierte Datenbank-IDs an, die sich nicht über viele unabhängige Datenbankserver hinweg skalieren lassen. Der Name geht auf die Vorstellung zurück, dass wie bei echten Schneeflocken keine zwei erzeugten IDs gleich sind. Das Design wurde später als Open-Source-Software veröffentlicht und von anderen großen Plattformen in abgewandelter Form übernommen, die dasselbe benötigten: eindeutige, sortierbare IDs, die von vielen Maschinen gleichzeitig erzeugt werden.

Häufig gestellte Fragen

Was ist eine Snowflake-ID? Eine Snowflake-ID ist eine 64-Bit-Zahl aus einem Zeitstempel, einer Maschinenkennung und einer Sequenznummer. Sie ist so ausgelegt, dass viele Maschinen eindeutige IDs erzeugen können, ohne sich untereinander abzustimmen.

Wie lautet die Formel für die Snowflake-ID? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, wobei die Epoche ein festes Anfangsdatum ist und << eine Linksverschiebung von Bits bezeichnet.

Kann ich die Epoche in diesem Generator ändern? Nein. Dieses Tool misst den Zeitstempel immer ab der festen Twitter-Epoche, 4. November 2010. Es gibt kein Feld, in dem ein anderes Anfangsdatum festgelegt werden kann.

Kann dieses Tool eine vorhandene Snowflake-ID decodieren? Nein. Es erstellt nur aus dem eingegebenen Zeitstempel, der Maschinen-ID, der Rechenzentrums-ID und der Sequenznummer eine neue ID und zeigt anschließend die Bitaufteilung dieser neuen ID.

Wie viele Snowflake-IDs kann eine Maschine pro Millisekunde erzeugen? Bis zu 4.096, da das Sequenzfeld 12 Bits breit ist (Werte von 0 bis 4.095).

Bis zu welchem Jahr kann dieser Generator gültige Zeitstempel erzeugen? Bis ungefähr Juli 2080. Das 41-Bit-Zeitstempelfeld kann gemessen ab der festen 2010-Epoche höchstens etwa 69,7 Jahre aufnehmen. Danach läuft der Wert aus dem Feld über.

Referenzen

1. „Snowflake wird angekündigt.“ Twitter Engineering Blog, 2010.
2. "Snowflake ID." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID