System Design HLD-11.01
Generating unique IDs at scale
Auto-increment vs UUIDv4, UUIDv7 and ULID, ticket servers, and Snowflake ids: uniqueness without coordination, sortability and index locality.
The big idea
Every order, message, photo and payment needs an id that no other record will ever have. On one database this is free: an auto-incrementing primary key hands out 1, 2, 3. Shard the data across 64 databases ( Partitioning and sharding ) and each one counts from 1 on its own, so two orders get id 1. Funnel every insert through one central counter and you have rebuilt the single bottleneck sharding was meant to remove.
So id generation at scale is a balancing act between four properties: unique without talking to anyone, compact (64 bits fits in a native integer; 128 bits doubles index size), roughly sortable by time so new rows land at the end of indexes and "newest first" is just "largest id first", and not too revealing (sequential ids tell competitors how many orders you take a day).
Think of how tickets are numbered at a large event with many entrances. Instead of every gate phoning one central desk for the next number, each gate prints numbers made of the time, its own gate number and a local counter. No two gates ever print the same ticket, and sorting tickets still roughly sorts them by entry time.
How it works
Step 1: Auto-increment and ticket servers
A database sequence is perfect until you outgrow one database. One escape is a ticket server: a dedicated database whose only job is handing out the next number, used by all shards. Flickr popularized this, running two ticket servers, one handing out odd numbers and one even, for availability. It works, but every insert waits on a network call to the ticket server, it can become a write bottleneck, and with two servers ids are no longer strictly ordered by time.
Step 2: UUIDs and ULIDs
A UUIDA 128-bit universally unique identifier; version 4 is almost entirely random, version 7 starts with a millisecond timestamp so values sort by creation time. is a 128-bit value any machine can generate without coordination. UUIDv4 is 122 random bits: the chance of a collision is negligible, but random values are bad for indexes. Each insert lands at a random place in the B-tree ( Indexes and B-trees ), touching a different page every time, so the working set of the index stops fitting in memory and inserts slow down as the table grows.
UUIDv7, standardized in RFC 9562 in 2024, fixes this by putting a 48-bit millisecond timestamp first and random bits after it. New ids are larger than old ones, so inserts append near the end of the index, while still needing no coordination. ULID is an earlier format with the same idea: a 48-bit timestamp plus 80 random bits, written as 26 characters in a readable base 32. Both are still 128 bits.
Step 3: Snowflake: 64 bits, no coordination, roughly sorted
Twitter's SnowflakeA 64-bit id scheme that combines a timestamp, a generator (machine or shard) id and a per-millisecond sequence, so every machine can create unique, roughly time-ordered ids independently. packs three fields into one 64-bit integer:
- 41 bits of time: milliseconds since a custom epoch. 2^41 ms is about 69 years.
- 10 bits of machine id: up to 1,024 generators, each assigned a unique number once (by config or a coordination service, Coordination services (ZooKeeper, etcd) ).
- 12 bits of sequence: a counter that resets every millisecond, so one machine can create 4,096 ids per millisecond.
Uniqueness needs no runtime coordination: two machines differ in the machine bits, and one machine never repeats a (millisecond, sequence) pair. Because time is the most significant field, ids sort by creation time, roughly: two machines in the same millisecond produce ids ordered by machine number, and machines' clocks differ slightly. That is "k-sorted": ordered to within a small time window.
Try it
Try this:
- Press Generate a few times. The ids grow, and the decoded timestamps match the clock. Look at the bits: only the low timestamp bits change between ids a few milliseconds apart.
- Press "Generate 3 in same ms". The timestamp stays the same and the sequence counts 0, 1, 2. What must a generator do if it needs a 4,097th id in one millisecond?
- Change the machine id, generate, and compare with earlier ids from the same millisecond. Then switch to the Instagram layout: more bits for the shard, fewer for the sequence.
Going deeper
Clocks moving backwards
Snowflake trusts the local clock. If NTP steps the clock back by 5 ms, the generator could reissue timestamps it already used and create duplicates ( Time and clocks ). Generators refuse to issue ids until the clock catches up with the last timestamp they used, and when the sequence overflows within a millisecond, they wait for the next one.
Leaking information and guessability
Time-ordered ids reveal when something was created, and sequential ones reveal volume. If ids appear in public URLs, consider a separate random public id or an encrypted or encoded form, and never rely on ids being unguessable for security; check authorization on every access.
Ids that carry the shard
Instagram's variant puts the logical shard id in the middle bits, so given any id you know which shard holds the row without a lookup. It is generated inside PostgreSQL, so no separate id service is needed.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Auto-increment | A single database; simple, compact, ordered | Sharding and multi-region writes; reveals volume |
| Ticket server | Moderate scale wanting simple numeric ids | A network hop per id; bottleneck and failure point |
| UUIDv4 | Generating anywhere, including clients and offline devices | 128 bits; random inserts hurt B-tree indexes; no time order |
| UUIDv7 / ULID | Coordination-free ids that are index friendly and time ordered | Still 128 bits; reveal creation time |
| Snowflake-style 64-bit | High-volume systems wanting compact, time-ordered ids | Machine id assignment and clock discipline required |
Common mistakes
- Using random UUIDv4 as the primary key of a huge, insert-heavy table and wondering why inserts slow down.
- Assuming time-ordered ids are strictly ordered across machines; they are only roughly ordered.
- Reusing a machine id on two live generators, which silently creates duplicates.
- Ignoring clock steps backwards in a Snowflake generator.
- Exposing sequential ids in URLs and leaking business volume, or treating ids as secrets.
In the wild
Twitter's June 2010 post explains that while moving from MySQL to Cassandra and sharded MySQL it lost the database's built-in way to generate unique ids. It needed tens of thousands of ids per second, highly available, fitting in 64 bits, and roughly sortable so tweets posted around the same time get nearby ids, with the aim of keeping that ordering within a second. That pushed it to an uncoordinated design: each id is composed of a timestamp, a worker number and a sequence number.
Instagram wanted ids that are sortable by time, ideally 64 bits, and that add as few new moving parts as possible. It rejected application-generated ids such as UUIDs (128 bits or more, some with no natural order), a separate Snowflake service (more infrastructure, including ZooKeeper) and ticket servers (a potential write bottleneck). Its ids use 41 bits for milliseconds since a custom epoch, 13 bits for the logical shard and a 10-bit sequence, allowing 1,024 ids per shard per millisecond, generated by PL/pgSQL inside each PostgreSQL shard.
Check yourself
-
Why do random UUIDv4 primary keys slow down inserts on a large table?
Show answer
B. Each insert lands at a random place in the B-tree, touching pages all over the index Random keys destroy index locality; time-ordered ids append near the end instead.
-
A Snowflake generator has 12 sequence bits. How many ids can one machine make per millisecond?
Show answer
B. 4,096 2 to the 12 is 4,096; after that it must wait for the next millisecond.
-
Two different machines generate ids in the same millisecond. How are they guaranteed different?
Show answer
B. Their machine id bits differ Each generator has a unique machine id, so the middle bits never match.
-
The server's clock is stepped back 5 ms. What should a Snowflake generator do?
Show answer
B. Refuse to issue ids until the clock passes the last timestamp it used Reusing past timestamps could repeat (time, sequence) pairs and create duplicates.
Recap
- Auto-increment needs a central counter, which does not scale across shards.
- UUIDv4 needs no coordination but is 128 bits and scatters index inserts; UUIDv7 and ULID put time first.
- Snowflake packs 41 bits of time, a machine id and a per-ms sequence into 64 bits.
- Time-first ids are roughly sortable and index friendly, but only k-sorted across machines.
- Assign machine ids carefully, guard against clocks going backwards, and do not treat ids as secrets.
Next up
- Crack the system design round learning path