Unique ID generator
Every row, message and event needs an id that is unique across the whole fleet, ideally sortable by creation time, ideally 64 bits, and minted without a network call. Random 128-bit UUIDs give uniqueness with no coordination but are big and scatter database inserts. A database counter gives small ordered ids but puts one server on every write. The standard answer is a Snowflake-style id: 41 bits of milliseconds since a custom epoch, 10 bits of worker id, 12 bits of per-millisecond sequence. O(1) and no I/O per id, 4,096 ids per ms per worker, about 70 years of range. The coordination moves to startup (claim a unique worker id), and the risk moves to the clock.
The problem
Section titled “The problem”A single database’s AUTO_INCREMENT is the easy answer until you shard: two shards both produce id 1001, and the one database that hands out ids becomes a bottleneck and a single point of failure. Twitter hit this in 2010 when moving tweets off MySQL, and built Snowflake.
What an id is asked to do:
| Goal | What it means | Pulls toward |
|---|---|---|
| Unique | Never the same id twice, across all machines, forever | Coordination, or enough random bits |
| Sortable by time | Newer ids compare greater, so ORDER BY id ≈ ORDER BY created_at |
Time in the high bits, trusting clocks |
| Compact | Fits a 64-bit integer column and index | Few bits, so a tight budget |
| No per-id coordination | Minting doesn’t wait on another machine | Local generation |
| Not guessable (sometimes) | Public ids don’t reveal volume or let you enumerate records | Randomness, opaque encodings |
You can’t have all five at once: 64 bits is too few for safe randomness, and time ordering leaks creation time.
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | next_id() returns a unique 64-bit integer; ids are roughly ordered by creation time; ids can be decoded into (time, worker, sequence) for debugging. |
Must ids be strictly increasing, or is “roughly” (k-sorted) fine? 64 or 128 bits? Numeric or string? |
| Scale | 200k ids/s fleet-wide at peak, a few thousand processes, bursty per process. | Peak per process, not just total? How many processes, including during deploys? |
| Latency | Microseconds; no network call per id. | Is a batched network call acceptable? |
| Lifetime | Ids stay valid and ordered for decades. | Expected system lifetime? |
| Availability | Minting continues if any shared component is down. | Can a process start up while the coordinator is down? |
| Out of scope | Human-friendly short codes (that’s the URL shortener), gap-free numbering (invoice numbers need a ledger, not this). |
Back of the envelope
Section titled “Back of the envelope”The bit budget is fixed at 63 usable bits. The question is whether your busiest process fits in the sequence field and your process count fits in the worker field, with room to spare during deploys.
What to say out loud: “Per-process throughput is nowhere near the 4,096-per-millisecond ceiling. The constraint is worker ids: about 400 processes now, double during deploys, against 1,024. I’d keep 10 worker bits but assign them with leases that expire, so dead pods give their ids back.”
API and data model
Section titled “API and data model”next_id() -> int64 -- local call, no I/Odecode(id) -> (time_ms, worker, sequence) -- for logs and debugging only
64-bit layout (Twitter Snowflake): bit 63 0 -- sign bit unused, ids stay positive bits 62..22 milliseconds since epoch -- 41 bits ≈ 69.7 years bits 21..12 worker id -- 10 bits = 1,024 workers bits 11..0 sequence within the ms -- 12 bits = 4,096 ids/ms/worker
On the wire: a decimal string, e.g. "2006515713438650368"Two decisions hide in that sketch:
- Ordering is “k-sorted”, not strict. Two workers minting in the same millisecond are ordered by worker id, not by which came first, and clocks on different machines differ by a few ms. So ids are ordered across the fleet only to within clock skew. Within one worker they are strictly increasing. If a consumer needs a strict total order, it needs a single sequencer (one partition, one log), not a cleverer id.
- Ids leak information. A time-ordered id reveals when a record was created, and a per-worker sequence reveals volume. For public-facing ids that must not be enumerable (invoice links, share tokens), use a separate random token, or encrypt the id with a block cipher before exposing it.
High-level design
Section titled “High-level design”There is almost no “system” on the hot path: the generator is a library. The design is the startup handshake, the clock, and the fallbacks.
| Component | Role | Why it’s there |
|---|---|---|
| Id library (in every service) | Reads the clock, keeps the last timestamp and sequence, packs the bits. | Minting is a local operation: no network, no single point of failure. |
| Coordinator (etcd / ZooKeeper) | Hands out worker ids under leases at startup. | Uniqueness depends on no two live processes sharing a worker id. |
| Time source (NTP / PTP) | Keeps clocks close together and moving forward. | The time field is only as good as the clock. |
| Ticket DB (alternative) | Hands out id ranges for schemes without time in the id. | Small, dense, ordered ids when you can afford a round trip per range. |
Deep dive: choosing a scheme
Section titled “Deep dive: choosing a scheme”| Scheme | Size | Sortable | Coordination per id | Main risk |
|---|---|---|---|---|
DB AUTO_INCREMENT |
64-bit | Strictly | Every insert, one DB | Single writer; can’t shard |
| Ticket server (Flickr, 2010) | 64-bit | Per server | One round trip per id (or per range) | The ticket DB; Flickr ran two, one odd and one even |
| Range / segment allocation | 64-bit | Roughly | One round trip per block | Gaps after crashes; ordering only across blocks |
| UUIDv4 | 128-bit | No | None | Index locality; size |
| UUIDv7 / ULID | 128-bit | By ms | None | Size; same-ms ids are random-ordered unless a counter is used |
| MongoDB ObjectId | 96-bit | By second | None | Seconds, not ms; per-process random + counter |
| Snowflake | 64-bit | By ms (k-sorted) | None (worker id at startup) | Clock going backwards; worker id reuse |
Random ids need no coordination, but the birthday bound decides how many random bits are enough: collisions become likely around 2^(b/2) ids, not 2^b. Drag the rate:
Takeaways: 64 random bits are not enough for a busy system (a coin flip after about 5 billion ids); 122 bits (UUIDv4) are enough for anything. UUIDv7 can only collide within one millisecond, so its risk depends on the per-ms rate; RFC 9562 lets implementations use some of the random bits as a counter, which removes same-process collisions and keeps same-ms ids ordered.
Deep dive: the Snowflake layout
Section titled “Deep dive: the Snowflake layout”The 63 bits are a budget, and every field trades against the others. Start from a real system’s layout, then fit it to requirements:
2006515713438650368 (19 digits).| System | Time | Worker / shard | Sequence | Notes |
|---|---|---|---|---|
| Twitter Snowflake | 41 bits, ms, epoch Nov 2010 | 10 (5 datacenter + 5 worker) | 12 | 4,096 ids/ms/worker; ~69 years |
| Discord | 41 bits, ms, epoch 2015 | 10 (5 worker + 5 process) | 12 | Sent as strings in JSON |
| 41 bits, ms, epoch 2011 | 13 (logical shard) | 10 | Generated in PL/pgSQL inside each Postgres shard; the id says which shard holds the row | |
| Sonyflake | 39 bits, 10 ms units | 16 (machine) | 8 | 174 years, but only 25.6k ids/s per machine |
Why the order matters. Time in the high bits means numeric order is time order. Putting the shard in the id (Instagram) means you can route a lookup by id with no directory. The distributed thinking page has a bit-level view of the packing with a clock-skew ordering demo.
Running out of sequence. If a worker uses all 4,096 sequence numbers in one millisecond, it must not wrap to 0 (that would repeat an id). The options: wait for the next millisecond (Twitter’s original), or treat the time field as a logical clock that may run slightly ahead of real time and catch up later. Either way, it’s rare if the sequence field fits your peak; the estimate above checks that.
Deep dive: clocks and worker ids
Section titled “Deep dive: clocks and worker ids”Uniqueness rests on two assumptions: no two live processes share a worker id, and a worker’s clock never repeats a millisecond it already used. Both fail in practice.
Clocks that go backwards. NTP can step a clock back, a VM can resume from a pause, a leap second can repeat. Options, from strict to lenient:
| Policy | Behaviour | Cost |
|---|---|---|
| Refuse | Error until the clock passes the last timestamp used (Twitter’s original Snowflake threw “Clock moved backwards”) | Requests fail for the gap; fine for ms, bad for minutes |
| Wait | Sleep until the clock catches up | Latency spike equal to the gap |
| Logical time | Keep using the last timestamp (and its sequence) until real time catches up | Ids drift ahead of wall time; must bound the drift |
| Change worker id | Re-register under a new worker id, whose past ids can’t collide | Uses up worker ids |
Production systems combine them: tolerate a small step without failing, refuse and alert on a large one, persist the last timestamp so a restart doesn’t go back in time, and configure NTP to slew rather than step.
Assigning worker ids. Static config breaks with autoscaling. Deriving it from the IP address (Sonyflake uses the low 16 bits of a private IP) works until two hosts share those bits across networks. The robust option is a lease from a coordinator:
on startup: for w in 0 .. 2^worker_bits - 1: if coordinator.create_if_absent("/idgen/workers/" + w, owner = me, lease_ttl = 30 s): worker_id <- w; break if none free: fail startup -- out of worker ids: alert, don't guess
every 10 s: if not coordinator.renew(lease): stop minting ids immediately -- after the TTL another process may hold this worker id, so a process that -- cannot renew must stop before its lease could have expiredRanges instead of time. If ids need to be small and dense rather than time-ordered, hand out blocks from a counter:
take_block(size): -- one atomic statement on the ticket DB; returns the new upper bound UPDATE ranges SET next = next + size WHERE name = 'orders' RETURNING next return [next - size, next)
next_id(): if current block is used up: switch to the prefetched block (or take_block now) if less than 20% of current block left and no prefetch in flight: prefetch in background return current.next++Deep dive: ids in storage
Section titled “Deep dive: ids in storage”The id is usually a primary key, so its shape affects the database more than the generator does.
- B-tree locality. InnoDB clusters rows by primary key; Postgres keeps a B-tree index on it. Time-ordered keys append at the right edge: the hot leaf pages stay in cache and fill completely. Random UUIDv4 keys insert all over the tree: pages split and are left half full, and the working set becomes the whole index. This is the main practical reason to prefer UUIDv7 over v4.
- Size. 8 bytes vs 16 per key, and every secondary index stores the primary key again. At 100 billion rows that’s hundreds of GB.
- Sharding by id. Range-partitioning on a time-ordered id sends all new writes to the last shard. Hash-partition the id, or partition by another key and embed the shard id in the id itself (Instagram).
- Exposing ids. Time-ordered ids are fine as internal keys; for public URLs consider a random token or an encrypted id so outsiders can’t infer volume (the “German tank problem”).
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Clock steps backwards | Possible duplicate ids, or refusals | Never mint below the last timestamp used; small gap: hold; large gap: refuse, alert, fail health checks; NTP slewing |
| Two processes share a worker id | Duplicates in the same ms; unique-key violations | Leased worker ids; stop minting when the lease can’t be renewed |
| Worker ids exhausted | New instances fail to start | Enough worker bits for 2× peak processes; short lease TTLs so dead ones free up |
| Sequence exhausted in a ms | Calls stall for up to 1 ms | Size the sequence for the busiest process; spread hot traffic over more processes |
| Coordinator down | Running processes fine; new ones can’t start | Keep the coordinator off the per-id path; cache the last lease for restarts within its TTL |
| Ticket DB down | Minting stops once ranges run out | Large ranges plus prefetch; two ticket servers (odd/even) |
| JS clients round ids | Ids that don’t match; “not found” | Serialize as strings |
| Epoch runs out | Ids wrap or overflow | Choose the epoch and tick for the system’s lifetime, then add margin |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
next_id (Snowflake) |
O(1): a clock read, compare, increment, shifts; ≈ tens of ns | O(1): last timestamp + sequence per process |
next_id (UUIDv4 / v7) |
O(1): random bytes (+ clock) | none shared |
next_id (ranges) |
O(1) amortised; one DB round trip per block | one counter row per sequence name |
| Worker id claim | O(W) tries worst case at startup; renew every few seconds | one lease per process |
decode(id) |
O(1) shifts and masks | — |
| Key storage | — | 8 B (Snowflake) vs 16 B (UUID) per key, per index |
| Throughput ceiling | 2^sequence_bits per tick per worker; 4.1M/s per worker for 12 bits at 1 ms | — |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Sortable? 64 or 128 bits? Peak per process? How many processes? Public or internal?
- Options (10 min). Auto-increment, UUIDv4, ticket server, UUIDv7, Snowflake. One line each on why it does or doesn’t fit.
- Design Snowflake (10 min). The bit layout and what each field buys; capacity from the estimate; the epoch; strings on the wire.
- Hard parts (15 min). Clock going backwards, sequence exhaustion, worker id assignment with leases, what happens during a partition.
- Storage and stretch (5 min). B-tree locality, sharding by id, k-ordering limits.
Follow-ups to expect: “Can ids be strictly increasing across the fleet?” Only with a single sequencer; Snowflake is k-sorted within clock skew. “Multi-region?” Give each region a slice of the worker id space (that’s what Twitter’s 5 datacenter bits are). “How do you test it?” Inject the clock: step it back, freeze it, and drive 5,000 calls into one ms; property-test that ids are unique and increasing per worker; run two generators with the same worker id in a test and see the duplicate.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Twitter’s original Snowflake README (2010): the 41/10/12 layout, the “roughly sorted” (k-sorted) requirement, and why they needed it when leaving MySQL.
- Discord developer docs: Snowflakes and Sonyflake: two production variants, one with a 2015 epoch and string serialization, one with 10 ms ticks and 16 machine bits.
- Flickr: Ticket Servers, Distributed Unique Primary Keys on the Cheap:
REPLACE INTOon MySQL, and two servers for odd and even ids. - RFC 9562: Universally Unique IDentifiers (2024): UUIDv4 and the new time-ordered UUIDv7, including counters for same-millisecond ordering.
Concept pages to drill: Bit manipulation · Time handling · Distributed thinking · Randomization · Indexing · Edge cases