Unique ID Generator

Snowflake-style IDs

Design a way for many servers to hand out unique 64-bit IDs that sort by creation time, without asking each other before every ID.

Overview

Every new row (a post, an order, a message) needs a primary key. On one database an auto-increment column does the job. Once the data is split across many databases, each one counting on its own would hand out the same numbers, and sending every insert to one central counter makes that counter a bottleneck and a single point of failure.

The interview question is how to make IDs that are unique everywhere, fit in 64 bits, and sort by time, while each server makes them locally. The usual answer is a Snowflake-style ID: the time in the top bits, then a worker number, then a counter. The follow-ups are where the marks are: who hands out worker numbers, what happens when a clock jumps back, and what happens when a worker needs more IDs in a millisecond than the counter holds.

The formats themselves (UUIDv4, UUIDv7, ULID, Snowflake) are covered in the topic UUID, ULID and Snowflake IDs. This problem walks the design and the failure cases.

Questions to ask first

How many IDs, at peak? — About 1 million a second across all services; 250,000 on average
Must IDs fit in 64 bits? — Yes: they are primary keys in many tables and indexes
Must they sort by time? — Roughly, within a few milliseconds; no strict global order
Can there be gaps? — Yes; only uniqueness and rough order matter
May IDs reveal creation time? — Yes, for internal keys; public tokens use something else
How long must the scheme last? — Decades: plan for at least 50 years

What you will be able to do

Pick an ID scheme from the requirements and defend it against auto-increment, ticket servers and UUIDs.
Split 64 bits into time, worker and sequence, and work out the limits each split gives.
Hand out worker IDs with leases, and reuse them safely when hosts come and go.
Explain what the generator does when the clock moves backwards or a burst uses up a millisecond.
Write a thread-safe generator that runs, and decode an ID back into its parts.

Key concepts

Snowflake layout
Custom epoch
Worker ID leases
Sequence overflow
Clock moving backwards
Ticket servers
UUIDv7
k-sorted IDs
Embedded library vs service

Functional requirements

Return a unique 64-bit integer ID on request, from inside any service
IDs made later are larger, within a few milliseconds
Return a batch of IDs in one call
Decode an ID into its time, worker and sequence for debugging

Non-functional requirements

No two IDs are ever the same, including across restarts and failovers
No network call per ID; generating one takes microseconds (a target we chose)
Keeps issuing IDs if the lease store is down, for at least one lease period
Lasts at least 50 years from the chosen epoch
Fits a signed 64-bit integer, so every language and database can store it

Interview questions

Why not just use a UUID?
Walk me through the bit layout. Why those widths?
How do workers get their IDs, and what if two hosts get the same one?
What happens when the clock goes backwards?
Are IDs from different machines in order?
Library or service?
Do these IDs leak information?
How would you run this across regions?