Générateur d'ID Snowflake - Créer des ID Distribués Uniques

Qu’est-ce qu’un générateur d’identifiants Snowflake ?

Un générateur d’identifiants Snowflake construit un nombre unique de 64 bits à partir d’un horodatage, d’un identifiant de machine et d’un numéro de séquence. Twitter a créé ce format en 2010 pour attribuer à chaque tweet un identifiant que de nombreux serveurs pouvaient produire simultanément, sans jamais se demander les uns aux autres « ce nombre a-t-il déjà été utilisé ? ». Cet outil construit un identifiant Snowflake à partir des valeurs saisies et montre comment ces valeurs occupent les 64 bits.

Fonctionnement de ce générateur d’identifiants Snowflake

Le générateur accepte quatre entrées :

• Horodatage : un horodatage Unix en millisecondes. Laissez ce champ vide pour utiliser l’heure actuelle.
• Identifiant de machine : un entier compris entre 0 et 31 (5 bits). Il s’agit de l’« identifiant de travailleur » d’origine de Twitter.
• Identifiant de centre de données : un entier compris entre 0 et 31 (5 bits).
• Numéro de séquence : un entier compris entre 0 et 4095 (12 bits), utilisé pour distinguer les identifiants créés au cours de la même milliseconde.

L’outil combine les quatre valeurs en un seul identifiant de 64 bits. Il affiche ensuite le résultat sous forme binaire, réparti entre ses segments d’horodatage, de centre de données, de machine et de séquence.

L’horodatage est mesuré à partir d’un point de départ fixe appelé époque Twitter : 4 novembre 2010, à 1:42:54,657 UTC, soit 1 288 834 974 657 millisecondes après l’époque Unix. Ce générateur ne permet pas de modifier ce point de départ. Chaque identifiant qu’il produit est mesuré à partir de cette même date fixe.

Structure d’un identifiant Snowflake

Un identifiant Snowflake est un entier de 64 bits réparti en quatre parties, lues du bit de poids fort vers le bit de poids faible :

Le bit initial vaut toujours 0, si bien qu’un identifiant Snowflake est toujours un nombre positif. Le champ d’horodatage de 41 bits et le champ de séquence de 12 bits sont les deux parties qui rendent les identifiants Snowflake faciles à trier : les identifiants créés plus tard ont un segment d’horodatage plus grand et sont donc classés après les précédents.

Formule d’un identifiant Snowflake

Le générateur construit l’identifiant avec la formule suivante :

$d = t - 1288834974657$

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

où d est le décalage, t l’horodatage saisi en millisecondes, I l’identifiant final, c l’identifiant du centre de données, m l’identifiant de la machine et s le numéro de séquence.

<< désigne un décalage de bits vers la gauche. Décaler un nombre de 22 bits vers la gauche revient à le multiplier par 2²², soit 4 194 304. Les valeurs de décalage (22, 17, 12) proviennent directement de la largeur des champs : le champ de séquence occupe 12 bits, donc l’identifiant de machine est décalé de 12 bits ; le champ de machine occupe 5 bits, donc l’identifiant du centre de données est décalé de 17 bits (12 + 5), et ainsi de suite.

Comment calculer un identifiant Snowflake : exemple détaillé

Supposons qu’une personne saisisse :

• Horodatage : 1 288 834 975 657 (exactement 1 000 ms après l’époque Twitter)
• Identifiant du centre de données : 1
• Identifiant de machine : 1
• Numéro de séquence : 0

Étape 1 — Calculer le décalage. Soustrayez l’époque de l’horodatage : 1 288 834 975 657 − 1 288 834 974 657 = 1 000.

Étape 2 — Placer chaque champ à la bonne position.

• Horodatage : 1 000 << 22 = 4 194 304 000
• Identifiant du centre de données : 1 << 17 = 131 072
• Identifiant de machine : 1 << 12 = 4 096
• Séquence : 0

Étape 3 — Combiner avec un OU bit à bit. Comme aucun des champs décalés ne se chevauche, leur addition donne le même résultat que leur combinaison par OU :

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

Il s’agit de l’identifiant Snowflake correspondant à ces entrées. La vue des résultats de l’outil répartit la même chaîne binaire de 64 bits en un bloc d’horodatage de 41 bits, un bloc de centre de données de 5 bits, un bloc de machine de 5 bits et un bloc de séquence de 12 bits, afin de garder visible la structure du nombre.

Domaines d’utilisation des identifiants Snowflake

Twitter a conçu ce format pour attribuer à des tweets des identifiants uniques et approximativement ordonnés dans le temps, sur des milliers de machines de bases de données, sans compteur central que chaque serveur aurait dû consulter. Discord et Instagram ont ensuite adopté des conceptions similaires d’identifiants de 64 bits pour les messages et les publications. La même idée apparaît dans le partitionnement de bases de données, les identifiants de commande des systèmes de commerce électronique et les journaux d’événements des applications distribuées. Elle convient à toute situation où de nombreuses machines attribuent des identifiants indépendamment tout en ayant besoin qu’ils soient approximativement triés par date.

Limites des identifiants Snowflake

En production, un générateur Snowflake conserve normalement sa propre horloge : il augmente le numéro de séquence pour chaque identifiant créé au cours de la même milliseconde et attend la milliseconde suivante lorsque la séquence atteint 4 095. Cet outil ne conserve aucun état entre les calculs. Il construit un identifiant à partir des valeurs saisies, ce qui le rend utile pour explorer le format, mais le distingue d’un service de production actif.

La conception présente des limites fixes, quel que soit le service qui l’implémente :

• Époque fixe : ce générateur n’accepte que les horodatages correspondant à 4 novembre 2010 ou à une date ultérieure (l’époque Twitter). Les dates antérieures ne peuvent pas être encodées.
• Limite de l’horodatage : le champ d’horodatage de 41 bits arrive à saturation vers juillet 2080. Après cette date, le décalage par rapport à l’époque ne tient plus dans 41 bits.
• Limite de la séquence : une seule machine ne peut émettre que 4 096 identifiants distincts (0–4095) au cours d’une même milliseconde avant que les valeurs ne se répètent.
• Espace des machines : avec 5 bits pour chacun des identifiants de machine et de centre de données, un déploiement dispose de 1 024 identités de machine distinctes (32 × 32) à attribuer sans collisions.
• Ordonnancement local, et non global : les identifiants ne sont correctement triés les uns par rapport aux autres que s’ils proviennent de machines dont les horloges sont synchronisées. La dérive des horloges entre les machines peut rompre l’ordre temporel strict.

Historique de l’identifiant Snowflake

Twitter a annoncé le format d’identifiant Snowflake en 2010 pour remplacer les identifiants de base de données à auto-incrémentation, qui ne passent pas à l’échelle sur de nombreux serveurs de bases de données indépendants. Le nom vient de l’idée que, comme les vrais flocons de neige, deux identifiants générés ne sont jamais identiques. La conception a ensuite été publiée en logiciel libre et copiée, sous une forme modifiée, par d’autres grandes plateformes qui avaient le même besoin : générer simultanément, sur de nombreuses machines, des identifiants uniques et triables.

Foire aux questions

Qu’est-ce qu’un identifiant Snowflake ? Un identifiant Snowflake est un nombre de 64 bits composé d’un horodatage, d’un identifiant de machine et d’un numéro de séquence, conçu pour que de nombreuses machines puissent générer des identifiants uniques sans se coordonner.

Quelle est la formule d’un identifiant Snowflake ? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, où l’époque est une date de départ fixe et où << désigne un décalage de bits vers la gauche.

Puis-je modifier l’époque dans ce générateur ? Non. Cet outil mesure toujours l’horodatage à partir de l’époque Twitter fixe, 4 novembre 2010. Aucun champ ne permet de définir une autre date de départ.

Cet outil décode-t-il un identifiant Snowflake existant ? Non. Il construit uniquement un nouvel identifiant à partir de l’horodatage, de l’identifiant de machine, de l’identifiant du centre de données et du numéro de séquence saisis, puis affiche la répartition en bits de ce nouvel identifiant.

Combien d’identifiants Snowflake une machine peut-elle générer par milliseconde ? Jusqu’à 4 096, puisque le champ de séquence occupe 12 bits (valeurs de 0 à 4 095).

Jusqu’à quelle année ce générateur peut-il produire des horodatages valides ? Jusqu’à environ juillet 2080. Le champ d’horodatage de 41 bits peut contenir au maximum environ 69,7 années mesurées depuis l’époque fixe de 2010, après quoi la valeur dépasse la capacité du champ.

Références

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