Snowflake ID Generator - Eindeutige verteilte IDs erstellen

Was ist ein Snowflake-ID-Generator?

Ein Snowflake-ID-Generator erzeugt aus einem Zeitstempel, einer Maschinenkennung und einer Sequenznummer eine eindeutige 64-Bit-Zahl. Twitter schuf das Format 2010, damit Maschinen, die IDs erzeugen, sich nicht untereinander abstimmen müssen. Viele Server können gleichzeitig IDs erzeugen, ohne zu fragen: „Wurde diese Zahl schon vergeben?“ Dieses Werkzeug bildet aus den eingegebenen Werten eine Snowflake-ID und zeigt, wie diese Werte die 64 Bits füllen.

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 Werkzeug fügt die vier Werte zu einer 64-Bit-ID zusammen und zeigt das Ergebnis aufgeteilt in Zeitstempel-, Maschinen- und Sequenzsegment an.

Der Zeitstempel wird ab einem festen Startpunkt gemessen, der Twitter-Epoche: 4. November 2010, 1:42:54,657 UTC, also 1.288.834.974.657 Millisekunden nach der Unix-Epoche. Dieser Generator erlaubt es nicht, diesen Startpunkt zu ändern; jede erzeugte ID wird ab diesem einen 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:

1delta = timestamp - 1288834974657
2id = (delta << 22) | (dataCenterId << 17) | (machineId << 12) | sequence
3

<< 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 Werkzeugs teilt dieselbe 64-Bit-Binärzeichenfolge wieder in einen 41-Bit-Zeitstempelblock, einen 10-Bit-Maschinenblock und einen 12-Bit-Sequenzblock auf, sodass die Gestalt der Zahl sichtbar bleibt.

Wo Snowflake-IDs verwendet werden

Twitter schuf das Format, um eindeutige, ungefähr nach Zeit geordnete IDs über viele Maschinen hinweg zu erhalten, ohne einen zentralen Zähler, den jeder Server prüfen müsste. Andere Plattformen übernahmen die Idee. Discord etwa gibt an, dass es das Snowflake-Format von Twitter verwendet, um seine IDs zu bilden. Dieselbe Idee findet sich beim Sharding von Datenbanken, bei Bestell-IDs in E-Commerce-Systemen und bei Ereignisprotokollen in verteilten Anwendungen: überall dort, wo viele Maschinen unabhängig voneinander IDs vergeben und diese trotzdem ungefähr nach Zeit sortiert bleiben sollen.

Einschränkungen von Snowflake-IDs

Ein produktiver Snowflake-Generator führt normalerweise eine eigene laufende Uhr: Er erhöht die Sequenznummer für jede in derselben Millisekunde erzeugte ID und wartet auf die nächste Millisekunde, sobald die Sequenz 4.095 erreicht. Dieses Werkzeug hat zwischen Berechnungen kein Gedächtnis. Es bildet eine ID aus dem jeweils eingegebenen Zeitstempel, den IDs und der Sequenznummer, was es nützlich macht, um das Format zu erkunden, aber von einem laufenden Produktivdienst unterscheidet.

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 etwa im Juli 2080 aus. 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 entwickelte Snowflake, als es seinen Speicher von MySQL auf Cassandra umstellte, das keine Funktion für fortlaufende IDs besitzt. Die Entwurfsziele waren IDs unter 64 Bit, die eindeutig, ungefähr nach Zeit geordnet und direkt sortierbar sind. Die erste Version erschien 2010 und wurde später eingestellt zugunsten einer internen Neuentwicklung. Andere große Plattformen übernahmen den Entwurf in abgewandelter Form, weil sie dasselbe brauchten: 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 Werkzeug 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 Werkzeug 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 etwa Juli 2080. Das 41-Bit-Zeitstempelfeld kann, gemessen ab der festen Epoche von 2010, höchstens etwa 69,7 Jahre aufnehmen (Twitters Hinweise runden dies auf 69 Jahre), danach läuft der Wert über das Feld hinaus.

Referenzen

1. Twitter. Snowflake README (Tag snowflake-2010), GitHub. Snowflake README — unkoordinierte, ungefähr nach Zeit geordnete IDs unter 64 Bit; 41-Bit-Zeit (69 Jahre), 10-Bit-Maschinen-ID (1.024 Maschinen), 12-Bit-Sequenz (4.096 pro Maschine und Millisekunde); veranlasst durch den Wechsel von MySQL zu Cassandra.
2. Twitter. IdWorker.scala (Tag snowflake-2010), GitHub. Snowflake IdWorker.scala — twepoch = 1288834974657; 5 Worker-Bits, 5 Rechenzentrums-Bits, 12 Sequenz-Bits; Verschiebungen um 12, 17 und 22.
3. Discord. API Reference: Snowflakes. Discord-API-Referenz — Discord verwendet für seine IDs das Snowflake-Format von Twitter.
4. Twitter. Snowflake README (master), GitHub. Hinweis zur Einstellung von Snowflake — Die erste Version erschien 2010 und wurde eingestellt.