Generátor Snowflake ID - Vytvorte jedinečné distribuované ID

Čo je generátor identifikátorov Snowflake?

Generátor identifikátorov Snowflake vytvára jedinečné číslo s dĺžkou 64 bitov z časovej pečiatky, identifikátora stroja a poradového čísla. Twitter vytvoril tento formát v roku 2010, aby každý tweet dostal identifikátor, ktorý mohli súčasne vytvárať mnohé servery bez toho, aby sa navzájom pýtali: „Bolo už toto číslo použité?“ Tento nástroj vytvorí jeden identifikátor Snowflake zo zadaných hodnôt a ukáže, ako tieto hodnoty vypĺňajú 64 bitov.

Ako tento generátor identifikátorov Snowflake funguje

Generátor prijíma štyri vstupy:

• Časová pečiatka: časová pečiatka Unixu v milisekundách. Ak ju necháte prázdnu, použije sa aktuálny čas.
• Identifikátor stroja: celé číslo od 0 do 31 (5 bitov). Ide o pôvodný „identifikátor pracovného uzla“ Twitteru.
• Identifikátor dátového centra: celé číslo od 0 do 31 (5 bitov).
• Poradové číslo: celé číslo od 0 do 4095 (12 bitov), ktoré slúži na rozlíšenie identifikátorov vytvorených v rovnakej milisekunde.

Nástroj spojí štyri hodnoty do jedného identifikátora s dĺžkou 64 bitov. Výsledok potom zobrazí v binárnej podobe, rozdelený na časti obsahujúce časovú pečiatku, dátové centrum, stroj a poradové číslo.

Časová pečiatka sa meria od pevne stanoveného počiatočného bodu nazývaného epocha Twitteru: 4. novembra 2010, 1:42:54,657 UTC alebo 1 288 834 974 657 milisekúnd po epoche Unixu. Tento generátor neumožňuje zmeniť tento počiatočný bod. Každý identifikátor, ktorý vytvorí, sa meria od toho istého pevného dátumu.

Štruktúra identifikátora Snowflake

Identifikátor Snowflake je celé číslo s dĺžkou 64 bitov rozdelené na štyri časti, ktoré sa čítajú od bitu s najvyššou významnosťou smerom nadol:

Úvodný bit je vždy 0, takže identifikátor Snowflake je vždy kladné číslo. 41-bitová časová pečiatka a 12-bitové pole poradového čísla sú dve časti, vďaka ktorým sa identifikátory Snowflake dajú užitočne triediť: identifikátory vytvorené neskôr majú väčší úsek časovej pečiatky, a preto sa zoradia za skoršie identifikátory.

Vzorec identifikátora Snowflake

Generátor vytvára identifikátor podľa tohto vzorca:

$d = t - 1288834974657$

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

kde d je rozdiel, t zadaná časová pečiatka v milisekundách, I výsledný identifikátor, c identifikátor dátového centra, m identifikátor stroja a s poradové číslo.

<< je bitový posun doľava. Posun čísla doľava o 22 bitov je rovnaký ako jeho vynásobenie číslom 2²² alebo číslom 4 194 304. Veľkosti posunov (22, 17, 12) vyplývajú priamo zo šírok polí: pole poradového čísla má šírku 12 bitov, takže identifikátor stroja je posunutý o 12 bitov; pole stroja má šírku 5 bitov, takže identifikátor dátového centra je posunutý o 17 bitov (12 + 5) a podobne.

Ako vypočítať identifikátor Snowflake: riešený príklad

Predpokladajme, že niekto zadá:

• Časová pečiatka: 1 288 834 975 657 (presne 1 000 ms po epoche Twitteru)
• Identifikátor dátového centra: 1
• Identifikátor stroja: 1
• Poradové číslo: 0

Krok 1 — Zistite rozdiel. Odčítajte epochu od časovej pečiatky: 1 288 834 975 657 − 1 288 834 974 657 = 1 000.

Krok 2 — Posuňte každé pole na príslušné miesto.

• Časová pečiatka: 1 000 << 22 = 4 194 304 000
• Identifikátor dátového centra: 1 << 17 = 131 072
• Identifikátor stroja: 1 << 12 = 4 096
• Poradové číslo: 0

Krok 3 — Spojte hodnoty bitovou operáciou OR. Keďže sa žiadne posunuté polia neprekrývajú, ich sčítanie dá rovnaký výsledok ako operácia OR:

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

Toto je identifikátor Snowflake pre tento vstup. Zobrazenie výsledku nástroja rozdelí ten istý 64-bitový binárny reťazec späť na 41-bitový blok časovej pečiatky, 5-bitový blok dátového centra, 5-bitový blok stroja a 12-bitový blok poradového čísla, takže štruktúra čísla zostane viditeľná.

Kde sa používajú identifikátory Snowflake

Twitter vytvoril tento formát na prideľovanie jedinečných, približne časovo zoradených identifikátorov tweetom v tisícoch databázových strojov bez centrálneho počítadla, ktoré by musel kontrolovať každý server. Discord a Instagram neskôr prijali podobné návrhy identifikátorov s dĺžkou 64 bitov pre správy a príspevky. Rovnaká myšlienka sa používa pri horizontálnom rozdeľovaní databáz, pri identifikátoroch objednávok v systémoch elektronického obchodu a v protokoloch udalostí distribuovaných aplikácií. Hodí sa všade tam, kde mnoho strojov prideľuje identifikátory nezávisle a zároveň ich treba približne zoradiť podľa času.

Obmedzenia identifikátorov Snowflake

Produkčný generátor Snowflake zvyčajne udržiava vlastné priebežné počítadlo: pre každý identifikátor vytvorený v rovnakej milisekunde zvýši poradové číslo a po dosiahnutí hodnoty 4 095 počká na ďalšiu milisekundu. Tento nástroj si medzi výpočtami nič nepamätá. Vytvorí jeden identifikátor z ľubovoľných zadaných hodnôt, takže je užitočný na skúmanie formátu, ale líši sa od produkčnej služby v reálnom čase.

Návrh má pevné obmedzenia bez ohľadu na to, ktorá služba ho implementuje:

• Pevná epocha: tento generátor prijíma iba časové pečiatky od 4. novembra 2010 vrátane (epocha Twitteru). Skoršie dátumy nemožno zakódovať.
• Horná hranica časovej pečiatky: 41-bitové pole časovej pečiatky sa vyčerpá približne v júli 2080. Potom sa rozdiel od epochy nezmestí do 41 bitov.
• Obmedzenie poradového čísla: jeden stroj môže v rovnakej milisekunde prideliť iba 4 096 rôznych identifikátorov (0–4095), kým by sa hodnoty začali opakovať.
• Priestor pre stroje: keďže identifikátor stroja aj identifikátor dátového centra majú po 5 bitov, nasadenie má k dispozícii 1 024 rôznych identít strojov (32 × 32), ktoré možno prideliť bez kolízií.
• Lokálne, nie globálne usporiadanie: identifikátory sa navzájom správne zoradia iba vtedy, ak pochádzajú zo strojov so synchronizovanými hodinami. Rozdiely medzi hodinami strojov môžu narušiť striktné časové usporiadanie.

História identifikátora Snowflake

Twitter oznámil formát identifikátorov Snowflake v roku 2010 ako náhradu jednoduchých automaticky sa zvyšujúcich databázových identifikátorov, ktoré sa nedajú škálovať naprieč mnohými nezávislými databázovými servermi. Názov vznikol z predstavy, že podobne ako skutočné snehové vločky sa žiadne dva vygenerované identifikátory nepodobajú. Návrh bol neskôr zverejnený ako open source a v upravenej podobe ho prevzali ďalšie veľké platformy, ktoré potrebovali to isté: jedinečné identifikátory zoraditeľné podľa času, generované mnohými strojmi súčasne.

Najčastejšie otázky

Čo je identifikátor Snowflake? Identifikátor Snowflake je číslo s dĺžkou 64 bitov tvorené časovou pečiatkou, identifikátorom stroja a poradovým číslom. Je navrhnutý tak, aby mnoho strojov mohlo vytvárať jedinečné identifikátory bez vzájomnej koordinácie.

Aký je vzorec identifikátora Snowflake? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, kde epocha je pevne stanovený počiatočný dátum a << je bitový posun doľava.

Dá sa v tomto generátore zmeniť epocha? Nie. Tento nástroj vždy meria časovú pečiatku od pevnej epochy Twitteru, 4. novembra 2010. Neexistuje pole na nastavenie iného počiatočného dátumu.

Dekóduje tento nástroj existujúci identifikátor Snowflake? Nie. Vytvára iba nový identifikátor zo zadanej časovej pečiatky, identifikátora stroja, identifikátora dátového centra a poradového čísla a potom zobrazí rozklad bitov tohto nového identifikátora.

Koľko identifikátorov Snowflake môže jeden stroj vygenerovať za milisekundu? Až 4 096, pretože pole poradového čísla má šírku 12 bitov (hodnoty od 0 po 4 095).

Do ktorého roku môže tento generátor vytvárať platné časové pečiatky? Približne do júla 2080. 41-bitové pole časovej pečiatky môže obsahovať najviac približne 69,7 roka meraného od pevnej epochy 2010, po ktorej hodnota pretečie mimo rozsahu poľa.

Referencie

1. „Oznamujeme Snowflake.“ Blog technického tímu Twitteru, 2010.
2. "Snowflake ID." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID