Generador d'ID de Snowflake - Crear ID Distribuïts Únics

Què és un generador d’IDs Snowflake?

Un generador d’IDs Snowflake crea un nombre únic de 64 bits a partir d’una marca de temps, un identificador de màquina i un número de seqüència. Twitter va crear el format el 2010 per donar a cada tuit un identificador que molts servidors poguessin generar alhora, sense haver-se de preguntar mútuament «aquest número ja s’ha utilitzat?». Aquesta eina crea un ID Snowflake a partir dels valors introduïts i mostra com aquests valors ocupen els 64 bits.

Com funciona aquest generador d’IDs Snowflake

El generador rep quatre entrades:

• Marca de temps: una marca de temps Unix en mil·lisegons. Deixeu-ho en blanc per utilitzar l’hora actual.
• ID de màquina: un enter de 0 a 31 (5 bits). Aquest és l’«ID de treballador» original de Twitter.
• ID del centre de dades: un enter de 0 a 31 (5 bits).
• Número de seqüència: un enter de 0 a 4095 (12 bits), que s’utilitza per distingir els IDs creats en el mateix mil·lisegon.

L’eina combina els quatre valors en un ID de 64 bits. A continuació, mostra el resultat en binari, dividit en els segments de marca de temps, centre de dades, màquina i seqüència.

La marca de temps es mesura des d’un punt d’inici fix anomenat època de Twitter: 4 de novembre del 2010, 1:42:54,657 UTC, o 1.288.834.974.657 mil·lisegons després de l’època Unix. Aquest generador no permet canviar aquest punt d’inici. Cada ID que produeix es mesura a partir d’aquesta única data fixa.

Estructura de l’ID Snowflake

Un ID Snowflake és un enter de 64 bits dividit en quatre parts, que es llegeixen començant pel bit més significatiu:

El bit inicial sempre és 0, de manera que un ID Snowflake sempre és un nombre positiu. El camp de marca de temps de 41 bits i el camp de seqüència de 12 bits són les dues parts que fan que els IDs Snowflake siguin útils per ordenar-los: els IDs creats més tard tenen un segment de marca de temps més gran i, per tant, apareixen després dels anteriors en l’ordenació.

Fórmula de l’ID Snowflake

El generador crea l’ID amb aquesta fórmula:

$d = t - 1288834974657$

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

on d és el delta, t la marca de temps introduïda en mil·lisegons, I l’ID final, c l’ID del centre de dades, m l’ID de màquina i s el número de seqüència.

<< és un desplaçament de bits cap a l’esquerra. Desplaçar un nombre cap a l’esquerra 22 bits equival a multiplicar-lo per 2²², és a dir, per 4.194.304. Les quantitats de desplaçament (22, 17, 12) provenen directament de les amplades dels camps: el camp de seqüència té una amplada de 12 bits, de manera que l’ID de màquina se situa 12 bits més amunt; el camp de màquina té una amplada de 5 bits, de manera que l’ID del centre de dades se situa 17 bits més amunt (12 + 5); i així successivament.

Com calcular un ID Snowflake: exemple resolt

Suposem que algú introdueix:

• Marca de temps: 1.288.834.975.657 (exactament 1.000 ms després de l’època de Twitter)
• ID del centre de dades: 1
• ID de màquina: 1
• Número de seqüència: 0

Pas 1 — Trobar el delta. Resteu l’època de la marca de temps: 1.288.834.975.657 − 1.288.834.974.657 = 1.000.

Pas 2 — Desplaçar cada camp fins a la seva posició.

• Marca de temps: 1.000 << 22 = 4.194.304.000
• ID del centre de dades: 1 << 17 = 131.072
• ID de màquina: 1 << 12 = 4.096
• Seqüència: 0

Pas 3 — Combinar amb OR bit a bit. Com que cap dels camps desplaçats se superposa, sumar-los dona el mateix resultat que aplicar-hi OR:

4.194.304.000 + 131.072 + 4.096 + 0 = 4.194.439.168

Aquest és l’ID Snowflake per a aquesta entrada. La vista de resultats de l’eina torna a dividir la mateixa cadena binària de 64 bits en un bloc de marca de temps de 41 bits, un bloc de centre de dades de 5 bits, un bloc de màquina de 5 bits i un bloc de seqüència de 12 bits, de manera que l’estructura del nombre continua sent visible.

On s’utilitzen els IDs Snowflake

Twitter va crear el format per donar als tuits IDs únics i aproximadament ordenats cronològicament en milers de màquines de bases de dades, sense un comptador central que tots els servidors haguessin de consultar. Més tard, Discord i Instagram van adoptar dissenys d’IDs similars de 64 bits per als missatges i les publicacions. La mateixa idea apareix en la fragmentació de bases de dades, els IDs de comanda dels sistemes de comerç electrònic i els registres d’esdeveniments de les aplicacions distribuïdes. És adequada per a qualsevol entorn en què moltes màquines assignin IDs de manera independent i encara calgui ordenar-los aproximadament per temps.

Limitacions dels IDs Snowflake

Un generador Snowflake de producció normalment manté el seu propi rellotge en funcionament: augmenta el número de seqüència per a cada ID creat en el mateix mil·lisegon i espera el mil·lisegon següent quan la seqüència arriba a 4.095. Aquesta eina no conserva memòria entre càlculs. Crea un ID a partir dels valors introduïts, cosa que la fa útil per explorar el format, però diferent d’un servei de producció en funcionament.

El disseny té límits fixos, independentment del servei que l’implementi:

• Època fixa: aquest generador només accepta marques de temps iguals o posteriors a 4 de novembre del 2010 (l’època de Twitter). Les dates anteriors no es poden codificar.
• Límit superior de la marca de temps: el camp de marca de temps de 41 bits s’esgota aproximadament el juliol de 2080. Després d’això, el delta respecte de l’època ja no cap en 41 bits.
• Límit de la seqüència: una sola màquina només pot emetre 4.096 IDs diferents (0–4095) en el mateix mil·lisegon abans que els valors es repeteixin.
• Espai de màquines: amb 5 bits per a cada ID de màquina i ID de centre de dades, una implementació disposa de 1.024 identitats de màquina diferents (32 × 32) per assignar sense col·lisions.
• Ordenació local, no global: els IDs només s’ordenen correctament entre ells si provenen de màquines amb rellotges sincronitzats. La deriva dels rellotges entre màquines pot trencar l’ordenació temporal estricta.

Història de l’ID Snowflake

Twitter va anunciar el format d’ID Snowflake el 2010 com a substitut dels IDs simples de base de dades auto-incrementals, que no escalen entre molts servidors de bases de dades independents. El nom prové de la idea que, com els flocs de neu reals, no hi ha dos IDs generats que siguin iguals. Més tard, el disseny es va publicar com a programari lliure i altres grans plataformes el van copiar, amb modificacions, perquè necessitaven el mateix: IDs únics i ordenables generats per moltes màquines alhora.

Preguntes freqüents

Què és un ID Snowflake? Un ID Snowflake és un nombre de 64 bits format per una marca de temps, un identificador de màquina i un número de seqüència, dissenyat perquè moltes màquines puguin generar IDs únics sense coordinar-se entre elles.

Quina és la fórmula de l’ID Snowflake? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, on l’època és una data d’inici fixa i << és un desplaçament de bits cap a l’esquerra.

Puc canviar l’època en aquest generador? No. Aquesta eina sempre mesura la marca de temps a partir de l’època fixa de Twitter, 4 de novembre del 2010. No hi ha cap camp per establir una data d’inici diferent.

Aquesta eina descodifica un ID Snowflake existent? No. Només crea un ID nou a partir de la marca de temps, l’ID de màquina, l’ID del centre de dades i el número de seqüència introduïts, i després mostra el desglossament dels bits d’aquest ID nou.

Quants IDs Snowflake pot generar una màquina per mil·lisegon? Fins a 4.096, ja que el camp de seqüència té una amplada de 12 bits (valors de 0 a 4.095).

Fins a quin any pot produir marques de temps vàlides aquest generador? Fins aproximadament al juliol de 2080. El camp de marca de temps de 41 bits pot contenir com a màxim aproximadament 69,7 anys mesurats des de l’època fixa de 2010, després dels quals el valor desborda el camp.

Referències

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