Unique ID generation
IDs that are unique, roughly ordered and made without a central counter.
01The intuition
The problem it solves
A school gives every new student a roll number from a register: the next free number. One register, one pen, no duplicates. A system that creates 100,000 orders a second across 500 servers cannot pass one register around. A single counter in a database would take a round trip for every ID, about a millisecond each, so one counter can hand out at most a thousand or so a second, a hundred times too few, and it is a single point of failure.
You might reach for a random 128-bit UUID: no coordination, no collisions in practice. It works, but the IDs are 36 characters, say nothing about time, and when used as a database key they insert into random places in the index, which is slow. What most large systems want is an ID that is unique, short, roughly increasing with time so that newer rows sort after older ones, and made on each server without asking anyone.
Build it one piece at a time
Step 1: give each server a range. A central service hands server A the numbers 1 to 1,000, server B 1,001 to 2,000, and so on. Each server counts within its range in memory and asks for a new range when it runs out. Coordination drops to one call per thousand IDs. IDs are unique, but not ordered across servers, and a crash wastes the rest of a range.
Step 2: put time in the ID. Build a 64-bit number from pieces: 41 bits of milliseconds since a chosen epoch, 10 bits of machine ID, 12 bits of sequence within the millisecond. This is the Snowflake layout.
| Bits | Field | Range | What it buys |
|---|---|---|---|
| 41 | milliseconds since epoch | 69 years | IDs sort by time |
| 10 | machine ID | 1,024 machines | no two machines collide |
| 12 | sequence | 4,096 per ms per machine | many IDs in one millisecond |
Each server generates IDs with no network call: read the clock, reuse the sequence if the millisecond is the same, else reset it to 0.
Step 3: assign machine IDs safely. Two servers with the same machine ID will collide. Hand out machine IDs from a coordination store with a lease at startup, or derive them from a stable fact such as the pod number, and refuse to start without one.
Step 4: handle the clock going backwards. A time sync can set the clock back 10 ms, and the server would reissue timestamps it already used. The generator remembers the last timestamp it issued; if the clock is behind it, it either waits until the clock catches up or keeps using the last timestamp and burns sequence numbers. It never issues a smaller time.
Step 5: when you need strict order, use a sequencer per shard. Snowflake IDs from different machines within the same millisecond are not in arrival order, and machine clocks differ by milliseconds anyway. Where order matters exactly, like positions in a log or bids on one item, route all events for that key to one process that hands out consecutive numbers, and accept that this process is a serial bottleneck for that key only.
Why it works, with the numbers
A single machine's capacity is the sequence width per millisecond:
4,096 per ms × 1,000 ms = about 4 million IDs per second per machine, 4 billion across 1,024 machines
with zero network calls on the hot path. Uniqueness follows from the structure: two IDs can only be equal if they share the millisecond, the machine and the sequence, and the machine ID is unique by construction while the sequence is unique within a machine's millisecond. The failure modes are duplicate machine IDs, a clock rollback that is not guarded, and running out of the 41-bit time field after 69 years, which is a note for your successors.
The trade-off you must say out loud
Random IDs trade index locality and time-ordering for zero setup; structured IDs trade a machine-ID registry and clock care for short, sortable keys. Say how machine IDs are assigned, how clock rollback is handled, and whether "roughly ordered" is enough or a per-key sequencer is needed. The follow-up is "can an ID leak information", and the answer is yes: a time-based ID reveals when it was created and roughly how many exist, so public IDs sometimes get an extra layer of encoding.
Where it shows up in the 100 Google problems
- Distributed unique ID generator: the question itself; ranges versus Snowflake, clock rollback and machine ID assignment are the deep dives.
- URL shortener: a counter-derived ID encoded in base 62 is the short code; a per-server range removes the central counter.
- Google Drive: every file and version needs an ID that is unique across regions.
- Stock trading: order IDs can be Snowflake-style, but the matching sequence number comes from the single matcher per symbol.