Design a Distributed Unique ID Generator: 64-Bit, Sortable, No Coordination

Listen

Listen. Every ID must be unique across the whole system, forever. It should fit in sixty-four bits, so it works as a database bigint and an efficient index key. IDs should roughly sort by creation time, so the newest rows cluster together and you can page by ID. Non-functionally: a million IDs a second across the fleet, generated in well under a millisecond, with no single point of failure.

The questions that change the design. Must IDs be strictly increasing, or just roughly by time? Roughly is fine. Are gaps allowed? Yes. Must they be unguessable? No, authorization protects the data. How many machines generate IDs? Up to about a thousand. How long must the scheme last? Decades. Each answer removes a hard constraint, so ask them before designing.

Ask scale

Ask about scale. A million IDs a second across two hundred servers is five thousand per server, about five per millisecond. Sixty-four bits holds around eighteen quintillion values, and even a million a second for fifty years uses about one and a half quadrillion. So we are not short of numbers. The hard part is handing them out without any server waiting on another.

peak: 1,000,000 ids/s
200 servers ≈ 5,000 ids/s each
≈ 5 per millisecond per server

64 bits ≈ 1.8 × 10^19 values
at 1M/s for 50 years:
  10^6 × 3 × 10^7 × 50
  ≈ 1.5 × 10^15 ids
→ space is plenty; the hard
  part is avoiding coordination

Define API

Define the API. The best interface is an in-process library: next ID returns a long, with a batch version. Helpers decode an ID into its time, worker and sequence, and compute the smallest possible ID for a timestamp, which lets you query a time range using the primary key. A network service that returns IDs is possible, but a local call avoids a network hop per ID.

in-process library:
  long nextId()
  long[] nextIds(n)

helpers:
  parse(id) → { time_ms,
    worker, seq }
  minIdAt(time) → for range
    queries by time

optional service: GET /ids?n=100

Data model

Here the data model is the ID itself. Sixty-four bits: one sign bit kept at zero, forty-one bits of milliseconds since a custom epoch, ten bits of worker ID, and twelve bits of sequence. Forty-one bits of milliseconds last about sixty-nine years. Ten bits allow a thousand twenty-four workers. Twelve bits allow four thousand ninety-six IDs per millisecond per worker. Time comes first, so IDs sort by time.

64 bits:
  1  sign (always 0)
  41 ms since a custom epoch
  10 worker id (0 to 1,023)
  12 sequence (0 to 4,095)

41 bits of ms ≈ 69 years
4,096 per ms per worker
  ≈ 4M ids/s per worker
1,024 workers

High-level design

First, the naive option, so you can explain why it fails. One database with an auto-increment counter, and every service asks it for the next ID. Each ID costs a network round trip, every request contends on one counter, and if that database is down, nobody in the company can create anything. With sharded databases, per-shard auto-increments collide with each other. So we need something else.

Compare the options. A random UUID needs no coordination but is a hundred twenty-eight bits and random, which scatters inserts across a B-tree index. UUID version seven is time-ordered, a strong choice if a hundred twenty-eight bits is acceptable. Database steps and range blocks fit sixty-four bits, but need a coordinator to stay up. The time plus worker plus sequence layout is sixty-four bits, sorted, and coordinates only at startup. Choose it.

The high-level design. Each process embeds the generator library. At startup it leases a unique worker ID from etcd or ZooKeeper, say three hundred seventeen. After that, every call reads the local clock, combines the milliseconds, the worker ID and a sequence counter, and returns an ID with no network call at all. The coordinator is touched once per process start, so it can be briefly down without stopping anyone.

                bits sort coord
UUID v4 random  128  no    none
UUID v7 time    128  yes   none
DB step (k, N)  64   ~     per id
range blocks    64   ~     per blk
Snowflake-style 64   yes   at boot

v4: random → index churn
blocks: coordination service
  must be up to get more
choice: Snowflake-style

Deep dive: layout

Deep dive one: building an ID. Pick a custom epoch, like the start of twenty twenty-four, so the forty-one bits last sixty-nine years from your launch, not from nineteen seventy. Take milliseconds since that epoch, shift left twenty-two bits, OR in the worker ID shifted left twelve, and OR in the sequence. Within the same millisecond, increment the sequence; in a new millisecond, reset it to zero.

epoch = 2024-01-01T00:00Z
now   = 1,000 days later
ms    = 86,400,000,000

id = (ms     << 22)
   | (worker << 12)
   |  seq

same ms → seq + 1
new ms  → seq = 0

Deep dive: worker IDs

Deep dive two: worker IDs. If two processes ever share a worker ID, they will generate identical IDs in the same millisecond. So lease them: create a key for worker three seventeen in etcd with a thirty-second TTL and renew it every ten seconds. If a process loses its lease, it must stop issuing IDs. Simpler setups use a stable host or pod ordinal. You can split the ten bits into region and machine.

Deep dive: clocks

Deep dive three: clocks. An NTP correction can move the system clock backwards, and then you could reuse a timestamp and sequence you already issued. Always remember the last millisecond used. If the clock is behind it by a few milliseconds, wait until it catches up. If it is far behind, refuse to issue IDs and alert. Configure NTP to slew time gradually rather than step it. Concepts episode thirty-two covers clocks.

Deep dive: sequence

Deep dive four: sequence overflow. If one worker is asked for more than four thousand ninety-six IDs within one millisecond, the sequence would wrap to zero and repeat. So when it reaches the maximum, wait for the next millisecond. With our numbers, about five per millisecond per worker, this only happens in extreme bursts. Also, on restart, wait at least a millisecond, so a fresh process cannot reuse the last millisecond's sequences.

4,096 ids in 1 ms on one worker
→ seq would wrap to 0: collision

rule: if seq == 4095
  busy-wait for the next ms

we need ~5 per ms per worker:
  overflow is a burst edge case
restart in the same ms? store
  last_ms or sleep 1 ms at boot

Deep dive: ordering

Deep dive five: what ordering do you actually get? On one worker, IDs strictly increase. Across workers, they are ordered only to within the clock skew between machines, a few milliseconds. That is fine for newest-first feeds, pagination and index locality. If a feature truly needs a strict total order, like messages in one chat, assign a sequence per conversation from a single owner instead.

Deep dive: pitfalls

Some practical pitfalls interviewers love. JavaScript numbers are exact only up to fifty-three bits, so send sixty-four-bit IDs as strings in JSON or the browser silently corrupts them. Time-based IDs reveal when something was created and hint at your volume; if that matters, expose a separate random public ID. And because new IDs are always the largest, never range-partition by ID, or every insert lands on the last shard; hash-partition instead.

Trade-offs

Trade-offs. We gained local, sub-microsecond generation with no hop per ID, at the price of trusting clocks and leases. Monitor clock offset on every host, how often generators wait for sequence overflow, lease renewals, and duplicate-key errors in databases, which should always be zero. At ten times the machines, rebalance the bit split, for example fewer sequence bits and more worker bits.

Interview summary

The summary. Sixty-four-bit IDs made of forty-one bits of time, ten of worker and twelve of sequence, generated locally by a library in each process. Worker IDs are leased from etcd with a TTL, so no two processes share one. If the clock goes backwards, wait or refuse. If the sequence fills, wait for the next millisecond. IDs are roughly time-sorted. And if a hundred twenty-eight bits is acceptable, UUID version seven is a solid standard alternative.