Generátor Snowflake ID - Vytvořte jedinečná distribuovaná ID

Co je generátor ID Snowflake?

Generátor ID Snowflake vytváří jedinečné 64bitové číslo z časového razítka, identifikátoru stroje a pořadového čísla. Twitter tento formát vytvořil v 2010, aby každý tweet dostal identifikátor, který mohlo současně vytvářet mnoho serverů, aniž by se navzájem ptaly: „Bylo už toto číslo použito?“ Tento nástroj vytvoří jedno ID Snowflake ze zadaných hodnot a ukáže, jak tyto hodnoty vyplní 64 bitů.

Jak tento generátor ID Snowflake funguje

Generátor přijímá čtyři vstupy:

• Časové razítko: unixové časové razítko v milisekundách. Ponecháním prázdného pole se použije aktuální čas.
• ID stroje: celé číslo od 0 do 31 (5 bitů). Jde o původní „ID pracovníka“ společnosti Twitter.
• ID datového centra: celé číslo od 0 do 31 (5 bitů).
• Pořadové číslo: celé číslo od 0 do 4095 (12 bitů), které slouží k rozlišení ID vytvořených během stejné milisekundy.

Nástroj spojí čtyři hodnoty do jednoho 64bitového ID. Výsledek pak zobrazí v binární podobě, rozdělený na části s časovým razítkem, datovým centrem, strojem a pořadovým číslem.

Časové razítko se měří od pevného počátečního bodu zvaného epocha Twitteru: 4. listopadu 2010, 1:42:54,657 UTC neboli 1 288 834 974 657 milisekund po unixové epoše. Tento generátor neumožňuje tento počáteční bod změnit. Každé vytvořené ID se měří od tohoto jediného pevného data.

Struktura ID Snowflake

ID Snowflake je 64bitové celé číslo rozdělené na čtyři části, čtené od nejvýznamnějšího bitu směrem dolů:

Úvodní bit je vždy 0, takže ID Snowflake je vždy kladné číslo. 41bitové časové razítko a 12bitové pole pořadového čísla jsou dvě části, díky nimž lze ID Snowflake řadit: ID vytvořená později mají větší část s časovým razítkem, a proto se řadí za dřívější ID.

Vzorec ID Snowflake

Generátor sestavuje ID podle tohoto vzorce:

$d = t - 1288834974657$

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

kde d je rozdíl, t zadané časové razítko v milisekundách, I výsledné ID, c ID datového centra, m ID stroje a s pořadové číslo.

<< je bitový posun doleva. Posun čísla doleva o 22 bitů je totéž jako jeho vynásobení hodnotou 2²² neboli 4 194 304. Velikosti posunů (22, 17, 12) přímo vycházejí z šířek polí: pole pořadového čísla má šířku 12 bitů, takže ID stroje je posunuto o 12 bitů; pole stroje má šířku 5 bitů, takže ID datového centra je posunuto o 17 bitů (12 + 5); a tak dále.

Jak vypočítat ID Snowflake: názorný příklad

Předpokládejme, že někdo zadá:

• Časové razítko: 1 288 834 975 657 (přesně 1 000 ms po epoše Twitteru)
• ID datového centra: 1
• ID stroje: 1
• Pořadové číslo: 0

Krok 1 — Zjištění rozdílu. Od časového razítka odečtěte epochu: 1 288 834 975 657 − 1 288 834 974 657 = 1 000.

Krok 2 — Posunutí každého pole na správné místo.

• Časové razítko: 1 000 << 22 = 4 194 304 000
• ID datového centra: 1 << 17 = 131 072
• ID stroje: 1 << 12 = 4 096
• Pořadové číslo: 0

Krok 3 — Spojení pomocí bitového OR. Protože se žádná z posunutých polí nepřekrývají, jejich sečtením získáme stejný výsledek jako bitovým OR:

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

To je ID Snowflake pro tento vstup. Zobrazení výsledku v nástroji rozdělí stejný 64bitový binární řetězec zpět na 41bitový blok časového razítka, 5bitový blok datového centra, 5bitový blok stroje a 12bitový blok pořadového čísla, takže struktura čísla zůstane viditelná.

Kde se ID Snowflake používají

Twitter vytvořil tento formát, aby tweetům napříč tisíci databázových strojů přiděloval jedinečná, přibližně časově seřazená ID bez centrálního čítače, který by musel kontrolovat každý server. Discord a Instagram později přijaly podobné 64bitové návrhy ID pro zprávy a příspěvky. Stejná myšlenka se objevuje při horizontálním dělení databází, u ID objednávek v systémech elektronického obchodu a v protokolech událostí distribuovaných aplikací. Hodí se všude tam, kde mnoho strojů přiděluje ID nezávisle a zároveň je potřebuje přibližně řadit podle času.

Omezení ID Snowflake

Produkční generátor Snowflake obvykle udržuje vlastní průběžné hodiny: pro každé ID vytvořené během stejné milisekundy zvýší pořadové číslo a po dosažení 4 095 počká na další milisekundu. Tento nástroj si mezi výpočty nic nepamatuje. Vytvoří jedno ID z libovolně zadaných hodnot, takže je užitečný k prozkoumání formátu, ale liší se od služby běžící v produkci.

Návrh má bez ohledu na konkrétní implementaci služby pevně daná omezení:

• Pevná epocha: tento generátor přijímá pouze časová razítka od 4. listopadu 2010 (epochy Twitteru) včetně. Starší data nelze zakódovat.
• Horní mez časového razítka: 41bitové pole časového razítka se vyčerpá přibližně v červenci 2080. Poté se rozdíl od epochy již nevejde do 41 bitů.
• Omezení pořadového čísla: jeden stroj může během stejné milisekundy vydat pouze 4 096 různých ID (0–4095), než by se hodnoty začaly opakovat.
• Prostor pro stroje: s 5 bity pro ID stroje i ID datového centra má nasazení k dispozici 1 024 různých identit strojů (32 × 32), které lze přidělit bez kolizí.
• Lokální, nikoli globální řazení: ID se navzájem správně seřadí pouze tehdy, pocházejí-li ze strojů se synchronizovanými hodinami. Rozdíly hodin mezi stroji mohou narušit striktní časové pořadí.

Historie ID Snowflake

Twitter oznámil formát ID Snowflake v 2010 jako náhradu jednoduchých automaticky se zvyšujících ID databáze, která nelze škálovat napříč mnoha nezávislými databázovými servery. Název vychází z představy, že stejně jako skutečné sněhové vločky nejsou žádná dvě vytvořená ID stejná. Návrh byl později uvolněn jako open source a v upravené podobě ho převzaly další velké platformy, které potřebovaly totéž: jedinečná ID seřaditelná podle času, generovaná mnoha stroji současně.

Často kladené otázky

Co je ID Snowflake? ID Snowflake je 64bitové číslo složené z časového razítka, identifikátoru stroje a pořadového čísla, navržené tak, aby mnoho strojů mohlo vytvářet jedinečná ID bez vzájemné koordinace.

Jaký je vzorec ID Snowflake? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, kde epocha je pevné počáteční datum a << označuje bitový posun doleva.

Lze v tomto generátoru změnit epochu? Ne. Tento nástroj vždy měří časové razítko od pevné epochy Twitteru, 4. listopadu 2010. Neexistuje pole pro nastavení jiného počátečního data.

Dekóduje tento nástroj existující ID Snowflake? Ne. Pouze vytvoří nové ID ze zadaného časového razítka, ID stroje, ID datového centra a pořadového čísla a poté zobrazí rozklad bitů tohoto nového ID.

Kolik ID Snowflake může jeden stroj vygenerovat za milisekundu? Až 4 096, protože pole pořadového čísla má šířku 12 bitů (hodnoty od 0 do 4 095).

Do kterého roku může tento generátor vytvářet platná časová razítka? Přibližně do července 2080. Pole časového razítka o šířce 41 bitů může od pevné epochy 2010 pokrýt nejvýše přibližně 69,7 roku, poté hodnota přeteče přes rozsah pole.

Reference

1. „Oznámení Snowflake.“ Technologický blog Twitteru, 2010.
2. "Snowflake ID." Wikipedie, https://en.wikipedia.org/wiki/Snowflake_ID