Snowflake ID-generator - Opprett unike distribuerte ID-er

Hva er en Snowflake-ID-generator?

En Snowflake-ID-generator bygger et unikt tall på 64 bit ut fra et tidsstempel, en maskinidentifikator og et sekvensnummer. Twitter opprettet formatet i 2010 for å gi hver tweet en identifikator som mange servere kunne produsere samtidig, uten å måtte spørre hverandre «har dette nummeret allerede blitt brukt?». Dette verktøyet bygger én Snowflake-ID fra de angitte verdiene og viser hvordan disse verdiene fyller 64 bit.

Slik fungerer denne Snowflake-ID-generatoren

Generatoren tar imot fire inndata:

• Tidsstempel: et Unix-tidsstempel i millisekunder. La feltet stå tomt for å bruke gjeldende klokkeslett.
• Maskin-ID: et heltall fra 0 til 31 (5 bit). Dette er Twitters opprinnelige «worker-ID».
• Datasenter-ID: et heltall fra 0 til 31 (5 bit).
• Sekvensnummer: et heltall fra 0 til 4095 (12 bit), brukt til å skille mellom ID-er som opprettes i samme millisekund.

Verktøyet kombinerer de fire verdiene til én ID på 64 bit. Deretter viser det resultatet som binærtall, delt inn i segmentene for tidsstempel, datasenter, maskin og sekvens.

Tidsstempelet måles fra et fast starttidspunkt kalt Twitter-epoken: 4. november 2010, 1:42:54,657 UTC, eller 1 288 834 974 657 millisekunder etter Unix-epoken. Denne generatoren lar ikke dette starttidspunktet endres. Hver ID den produserer, måles fra denne ene faste datoen.

Snowflake-ID-ens struktur

En Snowflake-ID er et heltall på 64 bit, delt inn i fire deler som leses fra den mest signifikante biten og nedover:

Den første biten er alltid 0, så en Snowflake-ID er alltid et positivt tall. Tidsstempelfeltet på 41 bit og sekvensfeltet på 12 bit er de to delene som gjør Snowflake-ID-er egnet for sortering: ID-er som lages senere, har et større tidsstempelsegment og sorteres derfor etter tidligere ID-er.

Formel for Snowflake-ID

Generatoren bygger ID-en med denne formelen:

$d = t - 1288834974657$

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

der d er differansen, t det angitte tidsstempelet i millisekunder, I den ferdige ID-en, c datasenter-ID-en, m maskin-ID-en og s sekvensnummeret.

<< er en venstreforskyvning av biter. Å forskyve et tall mot venstre med 22 biter tilsvarer å multiplisere det med 2²², eller 4 194 304. Forskyvningsmengdene (22, 17, 12) følger direkte av feltbreddene: Sekvensfeltet er 12 biter bredt, så maskin-ID-en ligger 12 biter opp; maskinfeltet er 5 biter bredt, så datasenter-ID-en ligger 17 biter opp (12 + 5); og så videre.

Slik beregnes en Snowflake-ID: et gjennomregnet eksempel

Anta at noen skriver inn:

• Tidsstempel: 1 288 834 975 657 (nøyaktig 1 000 ms etter Twitter-epoken)
• Datasenter-ID: 1
• Maskin-ID: 1
• Sekvensnummer: 0

Trinn 1 — Finn differansen. Trekk epoken fra tidsstempelet: 1 288 834 975 657 − 1 288 834 974 657 = 1 000.

Trinn 2 — Forskyv hvert felt på plass.

• Tidsstempel: 1 000 << 22 = 4 194 304 000
• Datasenter-ID: 1 << 17 = 131 072
• Maskin-ID: 1 << 12 = 4 096
• Sekvens: 0

Trinn 3 — Kombiner med bitvis OR. Siden ingen av de forskjøvne feltene overlapper, gir det samme resultat å legge dem sammen som å kombinere dem med OR:

4 194 304 000 + 131 072 + 4 096 + 0 = 4 194 439 168

Dette er Snowflake-ID-en for disse inndataene. Resultatvisningen deler den samme binærstrengen på 64 bit tilbake i en tidsstempelblokk på 41 bit, en datasenterblokk på 5 bit, en maskinblokk på 5 bit og en sekvensblokk på 12 bit, slik at tallets oppbygning forblir synlig.

Hvor Snowflake-ID-er brukes

Twitter utviklet formatet for å gi tweets unike, omtrent tidsordnede ID-er på tvers av tusenvis av databasemaskiner, uten en sentral teller som alle serverne måtte kontrollere. Discord og Instagram tok senere i bruk lignende ID-design på 64 bit for meldinger og innlegg. Den samme ideen brukes i databaseskåring, ordre-ID-er i netthandelssystemer og hendelseslogger i distribuerte applikasjoner. Den passer i alle situasjoner der mange maskiner tildeler ID-er uavhengig av hverandre, men likevel trenger at de er omtrent tidsordnet.

Begrensninger ved Snowflake-ID-er

En Snowflake-generator i produksjon holder normalt sin egen løpende klokke: den øker sekvensnummeret for hver ID som opprettes i samme millisekund, og venter til neste millisekund når sekvensen når 4 095. Dette verktøyet har ikke minne mellom beregningene. Det bygger én ID fra verdiene som oppgis, noe som gjør det nyttig for å utforske formatet, men forskjellig fra en aktiv produksjonstjeneste.

Designet har faste begrensninger, uavhengig av hvilken tjeneste som implementerer det:

• Fast epoke: Denne generatoren godtar bare tidsstempler på eller etter 4. november 2010 (Twitter-epoken). Tidligere datoer kan ikke kodes.
• Grense for tidsstempelet: Tidsstempelfeltet på 41 bit går tomt rundt juli 2080. Etter dette får differansen fra epoken ikke plass i 41 bit.
• Sekvensbegrensning: Bare 4 096 forskjellige ID-er (0–4095) kan utstedes av én maskin i samme millisekund før verdiene begynner å gjentas.
• Maskinrom: Med 5 bit hver for maskin-ID og datasenter-ID har en installasjon 1 024 forskjellige maskinidentiteter (32 × 32) å tildele uten kollisjoner.
• Lokal, ikke global, sortering: ID-er sorteres bare korrekt mot hverandre hvis de kommer fra maskiner med synkroniserte klokker. Klokkedrift mellom maskiner kan bryte den strenge tidsrekkefølgen.

Snowflake-ID-ens historie

Twitter kunngjorde Snowflake-ID-formatet i 2010 som en erstatning for enkle, autoinkrementerende database-ID-er, som ikke skalerer på tvers av mange uavhengige databaseservere. Navnet kom fra ideen om at ingen genererte ID-er er like, akkurat som ekte snøfnugg. Designet ble senere gjort tilgjengelig som åpen kildekode og kopiert, i modifisert form, av andre store plattformer som trengte det samme: unike, sorterbare ID-er generert av mange maskiner samtidig.

Ofte stilte spørsmål

Hva er en Snowflake-ID? En Snowflake-ID er et tall på 64 bit som består av et tidsstempel, en maskinidentifikator og et sekvensnummer, utformet slik at mange maskiner kan generere unike ID-er uten å samordne seg med hverandre.

Hva er formelen for en Snowflake-ID? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, der epoken er en fast startdato og << er en venstreforskyvning av biter.

Kan jeg endre epoken i denne generatoren? Nei. Dette verktøyet måler alltid tidsstempelet fra den faste Twitter-epoken, 4. november 2010. Det finnes ikke noe felt for å angi en annen startdato.

Dekoder dette verktøyet en eksisterende Snowflake-ID? Nei. Det bygger bare en ny ID fra det angitte tidsstempelet, maskin-ID-en, datasenter-ID-en og sekvensnummeret, og viser deretter bitoppdelingen for den nye ID-en.

Hvor mange Snowflake-ID-er kan én maskin generere per millisekund? Opptil 4 096, siden sekvensfeltet er 12 bit bredt (verdier fra 0 til 4 095).

Frem til hvilket år kan denne generatoren produsere gyldige tidsstempler? Frem til omtrent juli 2080. Tidsstempelfeltet på 41 bit kan inneholde høyst rundt 69,7 år målt fra den faste 2010-epoken, før verdien flyter over feltet.

Referanser

1. «Announcing Snowflake.» Twitter Engineering Blog, 2010.
2. "Snowflake ID." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID