Generator de ID-uri Snowflake - Creează ID-uri Distribuite Unice

Ce este un generator de ID-uri Snowflake?

Un generator de ID-uri Snowflake creează un număr unic de 64 de biți dintr-un marcaj temporal, un identificator al mașinii și un număr de secvență. Twitter a creat formatul în 2010 pentru a atribui fiecărui tweet un identificator pe care multe servere îl puteau genera simultan, fără să se întrebe vreodată „a fost folosit deja acest număr?”. Acest instrument creează un ID Snowflake din valorile introduse și arată cum umplu aceste valori cei 64 de biți.

Cum funcționează acest generator de ID-uri Snowflake

Generatorul primește patru valori de intrare:

• Marcaj temporal: un marcaj temporal Unix în milisecunde. Lăsați câmpul necompletat pentru a folosi ora curentă.
• ID mașină: un număr întreg de la 0 la 31 (5 biți). Acesta este „ID-ul workerului” original al Twitter.
• ID centru de date: un număr întreg de la 0 la 31 (5 biți).
• Număr de secvență: un număr întreg de la 0 la 4095 (12 biți), utilizat pentru a diferenția ID-urile create în aceeași milisecundă.

Instrumentul combină cele patru valori într-un singur ID de 64 de biți. Apoi afișează rezultatul în format binar, împărțit în segmentele pentru marcajul temporal, centrul de date, mașină și secvență.

Marcajul temporal este măsurat de la un punct de pornire fix numit epoca Twitter: 4 noiembrie 2010, la 1:42:54,657 UTC, adică 1.288.834.974.657 milisecunde după epoca Unix. Acest generator nu permite modificarea acelui punct de pornire. Fiecare ID produs este măsurat de la aceeași dată fixă.

Structura unui ID Snowflake

Un ID Snowflake este un număr întreg de 64 de biți, împărțit în patru părți citite de la bitul cel mai semnificativ în jos:

Bitul inițial este întotdeauna 0, astfel încât un ID Snowflake este întotdeauna un număr pozitiv. Câmpul de marcaj temporal de 41 de biți și câmpul de secvență de 12 biți sunt cele două părți care fac ID-urile Snowflake utile pentru sortare: ID-urile create mai târziu au un segment de marcaj temporal mai mare, deci apar după cele create mai devreme.

Formula unui ID Snowflake

Generatorul construiește ID-ul cu formula:

$d = t - 1288834974657$

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

unde d este delta, t marca temporală introdusă în milisecunde, I identificatorul final, c identificatorul centrului de date, m identificatorul mașinii, iar s numărul de secvență.

<< este o deplasare la stânga la nivel de biți. Deplasarea unui număr la stânga cu 22 de biți este echivalentă cu înmulțirea lui cu 2²², adică 4.194.304. Valorile deplasărilor (22, 17, 12) provin direct din lățimile câmpurilor: câmpul de secvență are 12 biți, astfel încât ID-ul mașinii este deplasat cu 12 biți; câmpul mașinii are 5 biți, astfel încât ID-ul centrului de date este deplasat cu 17 biți (12 + 5); și așa mai departe.

Cum se calculează un ID Snowflake: exemplu rezolvat

Să presupunem că cineva introduce:

• Marcaj temporal: 1.288.834.975.657 (exact la 1.000 ms după epoca Twitter)
• ID centru de date: 1
• ID mașină: 1
• Număr de secvență: 0

Pasul 1 — Calcularea diferenței. Se scade epoca din marcajul temporal: 1.288.834.975.657 − 1.288.834.974.657 = 1.000.

Pasul 2 — Deplasarea fiecărui câmp la poziția sa.

• Marcaj temporal: 1.000 << 22 = 4.194.304.000
• ID centru de date: 1 << 17 = 131.072
• ID mașină: 1 << 12 = 4.096
• Secvență: 0

Pasul 3 — Combinarea prin OR la nivel de biți. Deoarece niciunul dintre câmpurile deplasate nu se suprapune, adunarea lor dă același rezultat ca aplicarea operației OR:

4.194.304.000 + 131.072 + 4.096 + 0 = 4.194.439.168

Acesta este ID-ul Snowflake pentru datele introduse. Vizualizarea rezultatului împarte din nou același șir binar de 64 de biți într-un bloc de marcaj temporal de 41 de biți, un bloc pentru centrul de date de 5 biți, un bloc pentru mașină de 5 biți și un bloc de secvență de 12 biți, astfel încât structura numărului rămâne vizibilă.

Unde sunt utilizate ID-urile Snowflake

Twitter a creat formatul pentru a atribui tweeturilor ID-uri unice, ordonate aproximativ temporal, pe mii de mașini de baze de date, fără un contor central pe care fiecare server ar fi trebuit să îl verifice. Ulterior, Discord și Instagram au adoptat modele similare de ID-uri de 64 de biți pentru mesaje și postări. Aceeași idee apare în fragmentarea bazelor de date, în ID-urile comenzilor pentru sistemele de comerț electronic și în jurnalele de evenimente ale aplicațiilor distribuite. Este potrivită pentru orice situație în care multe mașini atribuie ID-uri independent și acestea trebuie totuși să fie ordonate aproximativ după timp.

Limitările ID-urilor Snowflake

Un generator Snowflake de producție își păstrează în mod normal propriul ceas: mărește numărul de secvență pentru fiecare ID creat în aceeași milisecundă și așteaptă următoarea milisecundă când secvența ajunge la 4.095. Acest instrument nu păstrează starea între calcule. El creează un singur ID din valorile introduse, ceea ce îl face util pentru explorarea formatului, dar diferit de un serviciu de producție activ.

Designul are limite fixe, indiferent de serviciul care îl implementează:

• Epocă fixă: acest generator acceptă numai marcaje temporale de la 4 noiembrie 2010 inclusiv (epoca Twitter). Datele anterioare nu pot fi codificate.
• Limita superioară a marcajului temporal: câmpul de marcaj temporal de 41 de biți se epuizează în jurul lui iulie 2080. După aceea, diferența față de epocă nu mai încape în 41 biți.
• Limita secvenței: o singură mașină poate emite numai 4.096 ID-uri distincte (0–4095) în aceeași milisecundă înainte ca valorile să se repete.
• Spațiul pentru mașini: cu câte 5 biți pentru ID-ul mașinii și ID-ul centrului de date, o implementare are 1.024 identități distincte de mașini (32 × 32) disponibile fără coliziuni.
• Ordine locală, nu globală: ID-urile se sortează corect unele față de celelalte numai dacă provin de la mașini cu ceasuri sincronizate. Deriva ceasurilor între mașini poate afecta ordinea temporală strictă.

Istoricul ID-ului Snowflake

Twitter a anunțat formatul ID-ului Snowflake în 2010 ca înlocuitor pentru ID-urile simple de baze de date cu incrementare automată, care nu se extind bine pe multe servere de baze de date independente. Numele a pornit de la ideea că, asemenea fulgilor de zăpadă reali, niciunul dintre ID-urile generate nu este identic cu altul. Ulterior, designul a fost publicat ca sursă deschisă și copiat, în forme modificate, de alte platforme mari care aveau aceeași nevoie: ID-uri unice și sortabile, generate simultan de multe mașini.

Întrebări frecvente

Ce este un ID Snowflake? Un ID Snowflake este un număr de 64 de biți alcătuit dintr-un marcaj temporal, un identificator al mașinii și un număr de secvență, conceput astfel încât multe mașini să poată genera ID-uri unice fără să se coordoneze între ele.

Care este formula unui ID Snowflake? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, unde epoca este o dată de început fixă, iar << este o deplasare la stânga la nivel de biți.

Pot schimba epoca în acest generator? Nu. Acest instrument măsoară întotdeauna marcajul temporal de la epoca Twitter fixă, 4 noiembrie 2010. Nu există niciun câmp pentru stabilirea unei alte date de început.

Decodifică acest instrument un ID Snowflake existent? Nu. El creează numai un ID nou din marcajul temporal, ID-ul mașinii, ID-ul centrului de date și numărul de secvență introduse, apoi afișează împărțirea în biți a acelui ID nou.

Câte ID-uri Snowflake poate genera o singură mașină într-o milisecundă? Până la 4.096, deoarece câmpul de secvență are 12 biți (valorile de la 0 la 4.095).

Până în ce an poate acest generator să producă marcaje temporale valide? Până în jurul lui iulie 2080. Câmpul de marcaj temporal de 41 de biți poate conține cel mult aproximativ 69,7 ani măsurați de la epoca fixă 2010, după care valoarea depășește capacitatea câmpului.

Referințe

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