Notes
Requirements
Requirements first. Unique across every machine and every restart. Ideally sixty-four bits, so indexes stay small. Roughly ordered by time, so new rows append to the end of a B-tree and 'newest first' is just a sort on id. A hundred thousand ids a second with sub-millisecond latency, without a network call per id. And, if ids are exposed in URLs, not trivially guessable.
- unique across every machine
- and every restart
- fits 64 bits (index size,
- JSON-safe as a string)
- roughly time-ordered (index
- locality, "newest first")
- 100k+ IDs/s, sub-ms
- no central call per ID
- not guessable, if exposed
DB sequences
Option one, the database sequence. It's simple, dense and ordered, and perfect while you have one database. With shards, two shards hand out the same numbers. The old trick is to give each server an offset and step, odd numbers on one and even on the other, but adding a server means changing the step everywhere. And every insert depends on that database being up.
- AUTO_INCREMENT / SEQUENCE
- + simple, dense, ordered
- - one DB = bottleneck + SPOF
- - shards collide
- multi-primary trick:
- server 1: 1, 3, 5 ...
- server 2: 2, 4, 6 ...
- (step = number of servers)
- - adding a server = renumber
UUIDs
Option two, UUIDs. Version four is a hundred and twenty-two random bits, generated anywhere with no coordination and practically no collision risk. But it's a hundred twenty-eight bits, and random order means each insert lands on a random B-tree page, causing page splits and cache misses at scale. Version seven, standardised in twenty twenty-four, starts with a millisecond timestamp, so ids are time-ordered while still needing no coordination. The cost is still a hundred twenty-eight bits.
- UUIDv4: 122 random bits
- + no coordination at all
- - 128 bits, random order:
- inserts land all over the
- B-tree → page splits, cache
- misses
- UUIDv7 (RFC 9562): 48-bit
- ms timestamp + random bits
- + time-ordered, no coordination
- - still 128 bits
Range allocation
Option three, range allocation. A generator asks a small database for a block of ten thousand ids in one atomic update, then serves them from memory. One database round trip per ten thousand ids. Prefetch the next block when eighty percent is used, so there's no pause. Ids are sixty-four bits and dense, and no clock is involved. A crash just wastes the rest of a block, and ids are only ordered within each generator.
UPDATE id_ranges SET next = next + 10000 WHERE name = 'order' RETURNING next - 10000; serve 10,000 ids from memory prefetch next block at 80% + 64-bit, dense, no clock - crash wastes rest of block - order only per server
Snowflake
Option four, the Snowflake layout, which is what most interviewers expect. Pack sixty-four bits as one sign bit, forty-one bits of milliseconds since a custom epoch, ten bits of worker id, and twelve bits of sequence. Forty-one bits of milliseconds lasts about sixty-nine years. Ten bits allow a thousand twenty-four workers. Twelve bits allow four thousand ninety-six ids per millisecond per worker, about four million a second each. And because time is the high bits, ids sort by creation time.
| 1 | 41 bits | 10 bits | 12 bits | | 0 | ms since | worker | sequence| | | epoch | id | in ms | 2^41 ms ≈ 69.7 years 2^10 = 1,024 workers 2^12 = 4,096 ids per ms per worker = 4M ids/s sorts by time, 64-bit, local
Generating one
Generating one id is a few lines. Read the current millisecond. If it's the same as last time, bump the sequence; if the sequence wraps past four thousand ninety-five, spin until the next millisecond. If time moved forward, reset the sequence to zero. Then shift the timestamp left by twenty-two bits and combine it with the worker id and the sequence. It runs in nanoseconds, usually as a library inside each service rather than a network call.
now = current_ms()
if now == last_ms:
seq = (seq + 1) & 4095
if seq == 0: now = wait_next_ms()
elif now > last_ms: seq = 0
else: clock went back → handle
last_ms = now
return ((now - EPOCH) << 22)
| (worker << 12) | seq Worker ids
The worker id is the part that must be coordinated, once at startup rather than per id. If two live generators share a worker id, they will produce duplicates. Lease the id from etcd or ZooKeeper with a time to live, keep renewing it, and stop issuing ids if renewal fails. Simpler setups use a Kubernetes StatefulSet ordinal or static config. Some designs split the ten bits into region and machine.
- must be unique among live
- generators, always
- lease from etcd/ZooKeeper
- with a TTL; renew it; stop
- issuing if renewal fails
- or: StatefulSet ordinal,
- config per host, or bits
- split into region + machine
Clock problems
The dangerous failure is the clock going backwards, from an NTP correction or a virtual machine migration. If it jumps back forty milliseconds, the generator would reuse timestamps and could repeat ids. Always remember the last timestamp used. For a small jump, just wait until the clock passes it. For a large jump, refuse to issue ids, alert and take the node out. Configure NTP to slew time gradually rather than step it.
- NTP step or VM migration
- moves time back 40 ms
- → same ms + same seq again
- → DUPLICATE ids
- small jump: wait until
- clock passes last_ms
- big jump: refuse, alert,
- take the node out
- prefer NTP slewing (smear)
- persist last_ms on restart
Edge cases
A few more edges. If one worker needs more than four thousand ninety-six ids in a millisecond, it waits a millisecond, or you rebalance bits from worker to sequence. Snowflake ids are only roughly sorted: two workers in the same millisecond have arbitrary relative order, so never use ids for exact causal ordering. Pick a recent custom epoch to get the full sixty-nine years. And JavaScript numbers lose precision above fifty-three bits, so send ids to browsers as strings.
- sequence exhausted (4,096 in
- one ms): wait ~1 ms; or use
- fewer worker bits, more seq
- ids are only k-sorted:
- two workers, same ms → order
- between them is arbitrary
- epoch: pick a recent custom
- epoch (more years left)
- JS numbers: 53 bits → send
- as strings
Exposure
Think about what ids reveal. If a customer sees order ten thousand five hundred twelve today and ten thousand five hundred forty tomorrow, they know you sold twenty-eight orders. Sequential ids also invite enumeration: just try the next invoice number. Snowflake ids leak their creation time. For public URLs, use a random token or an encrypted id, and always check access on every lookup regardless.
- sequential ids leak volume:
- order 10,512 → order 10,540
- a day later = 28 orders/day
- and allow enumeration of
- /invoice/10513
- Snowflake leaks timestamp
- public: random token or
- encrypted id; always check
- access on every lookup
Choosing
Choosing. Need sixty-four bits, time ordering and huge throughput: Snowflake, as a library in each service with leased worker ids. Want zero coordination and can afford a hundred twenty-eight bits: UUID version seven. Want dense ids and don't trust clocks: range allocation. Need short public codes, like a URL shortener: random base sixty-two strings with a uniqueness check on insert.
- need 64-bit + time order,
- very high rate: Snowflake
- want zero coordination,
- 128-bit ok: UUIDv7
- dense ids, no clock trust:
- range allocation
- short public codes: random
- base62 + uniqueness check
Sizing
Sizing. Two hundred thousand ids a second sounds like a lot, but one Snowflake worker can make four million a second, so throughput is never the limit. The limits are the worker id space, a thousand twenty-four live generators, and the id width. With ten billion rows, sixty-four-bit ids instead of a hundred twenty-eight save eighty gigabytes in every index that contains the id, including foreign keys. And forty-one bits of milliseconds lasts about sixty-nine years.
peak 200,000 ids/s overall Snowflake: 4M/s per worker → capacity is never the issue 1,024 worker ids → enough for ~1,000 live generators storage: 8 B vs 16 B per id 10B rows × 8 B = 80 GB saved per index that holds it lifetime: 2^41 ms ≈ 69 years
Say it like this
In the interview, state the requirements, then draw the sixty-four bits: forty-one for milliseconds, ten for worker, twelve for sequence, and do the arithmetic out loud. Say it runs as a library, with worker ids leased from etcd. Explain how you handle the clock going backwards. Then compare the alternatives, UUID version seven and range blocks, and why plain auto-increment fails once you shard.
- requirements: 64-bit, time-
- sortable, 100k/s, no SPOF
- Snowflake: 41 ms | 10 worker
- | 12 seq; library per service
- worker ids: etcd leases
- clock back: wait or refuse
- alternatives: UUIDv7,
- range blocks, and why not
- auto-increment on shards