Conception d'un générateur d'ID uniques : Snowflake, UUIDv7 et ULID comparés

Votre service de commandes utilise depuis des années une clé Postgres BIGSERIAL. Puis la table orders est répartie sur quatre shards, la séquence de chaque shard attribue la commande 10452, et le support découvre deux clients derrière un même numéro de commande. Ou bien l'application mobile a besoin d'un ID avant même de pouvoir joindre le serveur.

Les ID cessent d'être gratuits dès que plus d'une machine les crée. Les options échangent taille, ordre de tri, coordination par ID et ménagement de l'index B-tree. Cet article compare les séquences, les ticket servers, UUIDv4, UUIDv7, ULID et les ID de type Snowflake, puis conçoit un générateur de type Snowflake : disposition des bits, baux de worker ID, sauts d'horloge et calcul des collisions.

Exigences pour des ID distribués

• Uniques, pour toujours. Entre shards, régions et redémarrages.
• À peu près triés par le temps, pour que la pagination WHERE id > ? et les index ordonnés par le temps fonctionnent. Le Snowflake original de Twitter promettait un ordre entre machines à la seconde près.
• Compacts. 64 bits tiennent dans un BIGINT ; 128 bits doublent chaque clé.
• Aucune coordination par ID. L'objectif de Snowflake était au moins 10 000 ID par seconde et par processus, chacun en moins de 2 ms.
• Sûrs à exposer, sans révéler plus que prévu.

Six façons de générer des ID

Une séquence de base de données convient tant qu'une seule base écrit chaque ligne et casse dès que plusieurs bases se partagent un espace d'ID. Elle laisse des trous, car nextval n'est jamais annulé, et dans PostgreSQL un CACHE supérieur à 1 garde les valeurs distinctes mais désordonnées entre sessions. Des numéros de commande séquentiels révèlent aussi votre volume de commandes.

Un ticket server centralise la séquence. Les ticket servers MySQL de Flickr étaient deux machines, l'une émettant des nombres impairs et l'autre pairs, les clients alternant entre elles. Louer des blocs d'ID supprime l'appel par ID, comme dans la conception d'un raccourcisseur d'URL.

UUIDv7, ULID et Snowflake placent un horodatage en tête, si bien que les ID créés ensemble se trient ensemble ; seul Snowflake tient en 64 bits, au prix des worker ID et d'une dépendance à l'horloge.

La disposition des bits de Snowflake

La version de Twitter de 2010 utilisait ce découpage avec une epoch en novembre 2010, si bien que ses ID s'épuisent en juillet 2080. Depuis l'epoch Unix, 41 bits s'épuiseraient en septembre 2039 ; placez donc l'epoch près de votre lancement. Chaque instance garde sa dernière milliseconde et un compteur :

// Next is called with g.mu held.
func (g *Generator) Next() (int64, error) {
	if time.Now().After(g.leaseDeadline) {
		return 0, ErrLeaseLost // another instance may own this worker ID now
	}
	now := time.Now().UnixMilli()
	if now < g.lastMs {
		if g.lastMs-now > 5 {
			return 0, ErrClockMovedBack
		}
		now = g.waitUntil(g.lastMs) // small step back: wait it out
	}
	if now == g.lastMs {
		g.seq = (g.seq + 1) & 0xFFF // 12 bits
		if g.seq == 0 {             // 4,096 IDs used in this millisecond
			now = g.waitUntil(g.lastMs + 1)
		}
	} else {
		g.seq = 0
	}
	g.lastMs = now
	return (now-epochMs)<<22 | g.workerID<<12 | g.seq, nil
}

Un worker émet jusqu'à 4,1 millions d'ID par seconde ; le RPC qui l'entoure est la vraie limite, donc laissez les clients récupérer les ID par lots. Les ID dépassent 2^53 environ 25 jours après l'epoch, au-delà du Number.MAX_SAFE_INTEGER de JavaScript ; envoyez-les donc sous forme de chaînes JSON, comme le font les API de X et de Discord.

Le découpage est un budget. Discord utilise 42 bits pour le temps et répartit les bits de nœud entre worker et processus. Instagram générait les ID à l'intérieur de chaque shard PostgreSQL avec un ID de shard sur 13 bits, ce qui aide quand vous shardez une base de données. Sonyflake compte en unités de 10 ms pour durer 174 ans, à 256 ID par 10 ms et par instance.

Attribuer les worker ID

Snowflake n'a pas besoin de coordination par ID, seulement par processus : deux générateurs actifs avec le même worker ID peuvent émettre le même ID.

1. Configuration statique. Chaque hôte reçoit un WORKER_ID. Convient à une flotte fixe ; un fichier de configuration copié crée des doublons.
2. Ordinaux de StatefulSet. Kubernetes numérote les pods d'un StatefulSet à partir de 0 et étiquette chacun avec apps.kubernetes.io/pod-index (stable depuis la v1.32), que la downward API transmet. Les ordinaux ne sont uniques qu'au sein d'un StatefulSet dans un cluster, et supprimer un pod de force peut laisser deux pods avec le même ordinal.
3. Baux dans etcd ou ZooKeeper. Au démarrage, l'instance réclame la plus petite clé libre, comme /idgen/workers/17, avec une transaction qui ne réussit que si la clé est absente, sur un bail de 10 secondes renouvelé toutes les 3 secondes. Si l'instance meurt, la clé expire. Le Snowflake de Twitter en 2010 utilisait un nœud éphémère ZooKeeper et refusait de démarrer si son horloge s'écartait de plus de 10 secondes de la moyenne de ses pairs.

env:
  - name: WORKER_ID
    valueFrom:
      fieldRef:
        fieldPath: metadata.labels['apps.kubernetes.io/pod-index']

Les baux demandent deux règles. Cessez d'émettre des ID dès que le dernier keepalive réussi est plus ancien que le TTL accordé moins une marge, pour qu'une instance en pause ou partitionnée s'arrête avant qu'une autre puisse réclamer son ID. Et sauvegardez une high-water mark : toutes les quelques secondes, stockez un horodatage légèrement en avance sur l'horloge dans une clé séparée, n'émettez jamais d'ID au-delà, et faites attendre le détenteur suivant jusqu'à ce que son horloge la dépasse. etcd garde les deux cohérents grâce à Raft.

Quand l'horloge recule

Les démons NTP ajustent en général l'horloge par slew, en la faisant tourner un peu plus vite ou plus lentement, mais la font sauter pour de grands écarts : ntpd saute au-delà de 128 ms par défaut, et avec le mode leap second par défaut de chrony, le noyau recule l'horloge d'une seconde pour une seconde intercalaire insérée. La documentation de chrony conseille de ne sauter qu'au démarrage :

makestep 1.0 3      # step (if off by over 1 s) only in the first three updates
leapsecmode slew    # absorb a leap second by slewing, not by stepping back

Pour un saut qui passe, choisissez une règle :

Celui de Twitter échouait. Attendre quelques millisecondes, puis échouer avec une alerte, est un défaut raisonnable. Mesurer le temps avec CLOCK_MONOTONIC, qui ne recule jamais, protège un processus en cours ; la high-water mark couvre les redémarrages.

UUIDv7 et index B-tree

La RFC 9562, publiée en mai 2024, a remplacé la RFC 4122 et défini UUIDv7 : un horodatage Unix de 48 bits en millisecondes, 4 bits de version, 2 bits de variante et 74 bits pour l'aléatoire, ou pour un compteur quand vous avez besoin d'un ordre strict dans la milliseconde. L'horodatage dure jusqu'à l'an 10889.

La RFC avertit que les UUID sans ordre temporel ont une mauvaise localité d'index, avec des effets sur les B-trees qui peuvent être spectaculaires. Dans PostgreSQL, les nouvelles clés v7 vont à la page feuille la plus à droite, et les splits y laissent les pages remplies à 90 %, le fillfactor B-tree par défaut. Les clés v4 aléatoires touchent n'importe quelle page : l'index entier devient le working set, les pages pleines se scindent, et après chaque checkpoint la première modification de chaque page écrit la page entière dans le WAL. InnoDB de MySQL copie en outre la clé primaire dans chaque index secondaire, si bien qu'une clé de 16 octets les fait tous grossir.

PostgreSQL 18 a ajouté uuidv7() en septembre 2025. Stockez les UUID en binaire de 16 octets, pas en 36 caractères de texte. Et v7 révèle son heure de création ; la RFC recommande v4 partout où un ID joue un rôle de sécurité.

ULID

La spécification ULID a la même forme : un horodatage de 48 bits en millisecondes et 80 bits aléatoires. Son texte de 26 caractères en base32 de Crockford, sans I, L, O ni U, se trie correctement comme chaîne et se lit bien dans les URL. Le mode monotonic ajoute 1 dans une milliseconde, ce qui garde l'ordre mais rend la valeur suivante devinable. ULID est une spécification communautaire ; pour les clés de base de données, UUIDv7 offre la même chose avec un support natif.

Quelle est la probabilité d'une collision ?

Pour n ID avec b bits aléatoires, la probabilité d'une collision quelconque est d'environ n² / 2^(b+1). Les ID préfixés par le temps ne peuvent entrer en collision que dans une même milliseconde, donc c'est le débit qui compte, pas le total. À 1 million d'ID par seconde pendant un an, répartis uniformément :

Les schémas aléatoires échouent avec une probabilité faible et calculable. Snowflake n'échoue que par l'exploitation, mais alors avec certitude. Gardez dans les deux cas une contrainte d'unicité.

Le diagramme du générateur d'ID de type Snowflake

Comment le lire :

• Les clients appellent NextId() sur l'une des trois instances, qui répondent depuis la mémoire : la dernière milliseconde et un compteur de 12 bits.
• etcd détient chaque worker ID sur un bail de 10 secondes, plus les horodatages sauvegardés.
• NTP garde les horloges proches (arête en pointillés) ; chrony ne saute qu'au démarrage.
• Le service Order écrit des lignes dans Postgres, où les ID croissants atterrissent sur la page B-tree la plus à droite.
• La barre montre les 64 bits à l'échelle ; le bloc Markdown liste les réglages.

Dessiner clairement la génération d'ID

• Dessinez la disposition des bits à l'échelle. Elle montre le budget d'un coup d'œil.
• Montrez d'où viennent les worker ID, avec le TTL du bail. Les doublons commencent là.
• Dessinez l'horloge comme une dépendance. Le générateur n'est correct que dans la mesure où son horloge l'est.
• Écrivez les règles de défaillance sur le canevas : horloge reculée, bail perdu, redémarrage. L'exemple de diagramme de conception système place des chiffres à côté des boîtes de la même façon.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez un Cadre du pack Base pour le service d'ID, avec trois nœuds Conteneur ambre du pack C4 Model à l'intérieur : id-gen-0 à id-gen-2, un worker ID chacun.
3. Ajoutez deux nœuds Conteneur à gauche pour les services Payment et Order, et un nœud Postgres du pack Données en dessous.
4. À droite, ajoutez un Conteneur violet pour etcd, un Serveur bleu du pack Réseau pour NTP et un bloc Markdown du pack Base avec les réglages.
5. Reliez-les : NextId() des deux clients vers le cadre, INSERT vers Postgres, le bail vers etcd et une arête pointillée de synchronisation d'heure depuis NTP.
6. En dessous, ajoutez quatre nœuds rectangulaires Ellipse du pack Base, dimensionnés 1 : 41 : 10 : 12, pour la disposition des bits, et quelques notes Texte de Base.

Un organigramme Mermaid de la conception devient un premier brouillon modifiable avec le convertisseur Mermaid. L'exemple utilise 14 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Qu'est-ce qu'un ID Snowflake ? Un ID de 64 bits construit à partir d'un horodatage, d'un worker ID et d'une séquence par milliseconde, introduit par Twitter en 2010. Les générateurs fonctionnent sans se parler, et les ID se trient à peu près par heure de création.

UUIDv7 est-il meilleur qu'ULID ? Les deux contiennent un horodatage de 48 bits en millisecondes et des bits aléatoires. UUIDv7 est un standard de l'IETF avec un support en base de données, comme uuidv7() dans PostgreSQL 18 ; ULID a une forme texte plus courte. Pour les clés de base de données, préférez UUIDv7.

Dois-je utiliser UUIDv4 ou UUIDv7 comme clé primaire ? UUIDv7 pour la plupart des tables : les nouvelles valeurs se trient après les anciennes, donc les insertions restent près du bord droit de l'index. Utilisez UUIDv4 là où un ID ne doit pas révéler son heure de création.

Combien d'ID par seconde un générateur Snowflake peut-il produire ? 4 096 par milliseconde et par worker, soit environ 4,1 millions par seconde, ou 4,2 milliards sur 1 024 workers. L'appel réseau autour du générateur est généralement la vraie limite.

Que se passe-t-il quand l'horloge recule ? Le générateur ne doit pas réutiliser une milliseconde qu'il a peut-être déjà utilisée. Il peut échouer jusqu'à ce que l'horloge rattrape son retard, attendre, ou tenir une horloge logique qui avance sur le temps réel ; celui de Twitter échouait.

Commencez gratuitement — un siège, sans carte bancaire.