Design a Unique ID Generator

Alice’s phone and Bob’s phone both send a chat message. Two API pods persist those rows in the same millisecond. Both writers look at the table, see the highest id is 1000, and both want id = 1001.

  Alice "landed"                 Bob "on my way"
         │                              │
         ▼                              ▼
      API pod A                      API pod B
         │                              │
         └──────── same millisecond ────┘
                      │
                      ▼
              both choose id 1001

That is the whole problem. The rows must get different primary keys. The pods must not wait on a mutex in another region just to mint a number.

The main design question is:

How do we mint IDs that are unique across processes, preferably sortable by time, without a hot central counter?

We will start with a counter in one process. UUIDs, database sequences, Snowflake, clock rollback, and worker-id allocation appear when that counter is no longer enough.

Generate and decode sample IDs in the Snowflake / ULID generator.

1. Clarify the problem

“Design a unique ID generator” can mean a 64-bit integer library, a string ULID, a human invoice number, or a per-chat sequence. Those are different products. I would ask:

• Numeric (64-bit int) or string?
• Must IDs sort roughly by creation time?
• Roughly unique, or globally unique across restarts and regions?
• How many IDs per second per worker, and fleet-wide?
• One region or many?
• Are IDs public in URLs, or internal only?
• Must they be hard to guess, or is uniqueness enough?
• Do we need human numbers such as INV-2026-000123?
• Do we need a gapless per-conversation order, as in chat?

If the interviewer gives no extra constraints, I would state:

Need                 64-bit unique IDs (string ULID if they prefer text)
Sort                 Roughly time-ordered; helps indexes and “recent” reads
Rate                 10k+ IDs/s per service instance at peak
Uniqueness           Must not collide across the fleet, including after restart
Regions              Start one region; multi-region must still be unique
Public               IDs may appear in URLs; they are not a secret
Human numbers        Out of scope (invoices)
Per-chat order       Out of scope (conversation sequences)

A chat message id can be a Snowflake. A chat sequence number cannot. That distinction will keep coming back.

2. Functional and non-functional requirements

The system must:

1. Mint an ID that is unique across all writers.
2. Prefer IDs that increase roughly with time.
3. Work without a single global lock on every mint.
4. Survive process restart without colliding with IDs already issued.
5. Support enough workers for a typical Kubernetes fleet.
6. Optionally decode an ID to timestamp and worker for debugging.

The first version does not include:

• human ticket numbers (INV-2026-…);
• per-conversation sequences;
• cryptographic unguessability as a security boundary;
• a public “ID as a service” product for third parties.

Message / object id     unique, roughly sortable
Chat sequence           monotonic per conversation, not global
Invoice number          human, gap-tolerant, allocated in the money DB

Those three look similar on a whiteboard. They are not interchangeable.

Edge cases

• NTP steps the clock backward.
• A crashed pod’s worker id is reused in the same millisecond.
• Two regions independently assign worker 7.
• One worker needs more than 4096 IDs in one millisecond.
• A VM pause or stop-the-world GC freezes “now,” then jumps.
• The custom epoch’s 41-bit window runs out (~70 years).
• A forked process inherits the same worker id and sequence state.
• A client retries create and expects the same id back.

The last one is not the generator’s job. Idempotent create is a client key, as in WhatsApp. NextID() always returns a fresh value.

3. Estimate the scale

Assume a mid-size chat product. These are planning values, not a 10-K.

DAU                            20 million
Messages / user / day          25
Messages / day                 500 million
Average                        ~5,800 msg/s
Peak (5–10×)                   30,000–60,000 msg/s
Other IDs (receipts, media)    similar order
Fleet IDs at peak              ~100,000 / s
API pods                       80
IDs / pod / s                  ~1,250

A Twitter-style Snowflake worker can mint 4096 IDs per millisecond, about 4.1 million IDs/s on one process, before it must wait for the next millisecond. Per-pod capacity is not the problem. Coordination is.

Now put a central database sequence on that path:

80 pods  ×  1,250 IDs/s  =  100,000 nextval() / s
                          on one sequence, one primary

nextval() is fast on a healthy local primary — tens of thousands per second is ordinary. It is still a hotspot:

• every mint is a network round trip plus a write on one WAL stream;
• 80 chat pods now share fate with that primary;
• a cross-region hop of 50–80 ms makes 100k IDs/s impractical;
• failover of the sequence owner pauses every insert in the product.

A regional sequence is fine for a modest monolith. It is the wrong default once you have many writers, a second region, or you refuse to couple “can Alice send a message” to “is the ID database up.”

Storage of the IDs themselves is noise: 100k IDs/s × 8 bytes is about 800 KB/s. IDs are primary keys; they are kept forever. Bandwidth is not the story.

4. What fails

Three answers show up in every interview. Each is right for some job and wrong as a global ID generator.

MAX(id)+1

Two transactions read the same maximum.

pod A: SELECT MAX(id) → 1000
pod B: SELECT MAX(id) → 1000
pod A: INSERT 1001
pod B: INSERT 1001     ← collision or unique-constraint error

You already rejected this for WhatsApp sequences and invoice numbers. A unique constraint turns silent corruption into an error. That is not a sequencer.

A per-conversation counter is fine: the lock is one chat, not the planet. A global max is not.

UUID v4

128 random bits (122 of them actually random after version and variant). No coordination. Unique enough for this problem. No worker registry. No clock story.

The costs:

• not time-sortable, so “recent messages” cannot range-scan the primary key;
• 128 bits, twice a bigint, fatter indexes;
• random inserts scatter across a B-tree (page splits, worse cache locality).

UUID v4 is the correct default when you do not care about order or integer width: object storage keys, idempotency keys, many public resource ids. It is a weak answer if the interviewer asked for sortable 64-bit IDs.

Database SERIAL / SEQUENCE

Unique. Coordinated. Gaps on rollback (Postgres nextval() does not undo). That last part is fine for object ids.

The failure is operational, not mathematical. Every service trip to one sequence makes that sequence a write hotspot, a latency tax, and a single availability domain. Use it when the writer already lives next to that database and the rate is modest — invoice year counters are this case. Do not put it on the chat hot path across 80 pods and two regions.

5. Start with a single-node counter

One API process. One integer.

last_id = 1000

NextID():
  last_id += 1
  return last_id

Alice gets 1001. Bob, on the same pod a moment later, gets 1002. Uniqueness is trivial. Sort is perfect. Latency is a register increment.

Ship that to production with a second replica:

          ┌────────────┐
 Alice ─► │  pod A     │  last_id = 1000 → issues 1001
          └────────────┘

          ┌────────────┐
 Bob   ─► │  pod B     │  last_id = 1000 → issues 1001
          └────────────┘

Each pod has its own memory. Sticky sessions do not fix retries, rolling deploys, or two devices. A Redis INCR or a Postgres sequence fixes uniqueness and re-creates the hotspot from section 3.

The constraint is now clear: each writer must be able to mint locally, and the IDs must still be unique when two writers share a millisecond.

That is the job a timestamp, a worker id, and a per-millisecond sequence do together.

6. Snowflake: 64 bits

Twitter-style Snowflake packs three facts into a signed 64-bit integer. The top bit stays unused so the value stays positive in a signed bigint.

 63        63  62                22  21        17  16        12  11         0
┌────────────┬─────────────────────┬─────────────┬─────────────┬────────────┐
│  unused    │  timestamp (ms)     │  datacenter │   worker    │  sequence  │
│  1 bit     │  41 bits            │  5 bits     │   5 bits    │  12 bits   │
└────────────┴─────────────────────┴─────────────┴─────────────┴────────────┘
     0            ms since epoch         0–31          0–31         0–4095

Some write-ups fold datacenter and worker into one 10-bit worker (0–1023). Same idea. The tool uses the 5+5 split.

What each field is for:

timestamp   milliseconds since a custom epoch  → roughly sortable
datacenter  which region / cluster             → multi-region uniqueness
worker      which process                      → two pods never collide
sequence    IDs in this millisecond, this worker

Walk one mint. Custom epoch T0. Now is T0 + 1_700_000_000_000 ms. Worker (dc=1, worker=4). First ID in that millisecond:

timestamp  = 1_700_000_000_000
dc         = 1
worker     = 4
sequence   = 0

id = (timestamp << 22) | (dc << 17) | (worker << 12) | sequence

The same millisecond on the same worker: sequence 1, then 2, up to 4095. A second worker uses a different worker field, so the integers differ even when the timestamp matches.

same ms, worker 4, seq 0   →  …| 00001 | 00100 | 000000000000
same ms, worker 4, seq 1   →  …| 00001 | 00100 | 000000000001
same ms, worker 7, seq 0   →  …| 00001 | 00111 | 000000000000

Why these widths:

41 bits is a product choice, not a law. More timestamp bits mean fewer worker bits. State the layout and the epoch; do not pretend there is one official Snowflake.

Play with bits in the Snowflake / ULID generator.

7. Worker-id allocation

Two workers that share (datacenter, worker) and the same millisecond will emit the same IDs. The layout only works if those fields are unique among live minters.

pod A  worker_id = 7  ──┐
                        ├── same ms, both start seq at 0  → collision
pod B  worker_id = 7  ──┘

Options, simplest first:

1. Config / env
   WORKER_ID=7 on each pod. Fine for five boxes. Drift is manual.

2. Kubernetes StatefulSet ordinal
   chat-0 … chat-31 map to worker 0–31. Unique while the set is unique.
   Replica count must stay inside the bit budget.

3. Lease from etcd / ZooKeeper / a small SQL table
   On start: claim an id, refresh a lease, release on shutdown.
   Best when pods are cattle and the count moves.

4. Hash of host + pod name
   Fast, no registry. Birthday collisions on 1024 buckets as the fleet grows.
   Only safe with a collision check against a registry.

I would pick StatefulSet ordinals for a small, stable fleet and a lease once autoscaling is routine. I would not hash into 10 bits and hope.

Worker reuse after a crash

Pod chat-7 dies. Kubernetes starts a new chat-7 with the same worker id. If the new process issues sequence 0 in the same millisecond the old process already used, the IDs collide.

t = 12:00:00.441   old chat-7 issues seq 0, 1, 2
                   process crashes
t = 12:00:00.441   new chat-7 starts, issues seq 0   ← duplicate

Mitigation: persist last_issued_timestamp (and last sequence) for that worker, or wait until the clock is past the last time that worker issued. A lease that outlives the millisecond window plus a stored watermark is the Senior answer. “We assign worker ids uniquely” is not enough if reuse is instant.

Do not reuse a worker id across regions. Encode the region in the datacenter bits, or keep separate bit spaces.

8. Clock rollback and NTP

Snowflake’s sort and uniqueness both assume now does not go backward on a worker.

NTP (the usual way servers correct time) can step the clock, not just slew it. A step from 12:00:00.500 back to 12:00:00.400 is a rollback.

last_ts = 12:00:00.500   already issued seq 0..40
now     = 12:00:00.400   NTP stepped back

If we mint with ts=400, seq=0:
  we recreate IDs from an earlier millisecond

Rule:

if now < last_ts:
  refuse to issue   (or wait until now >= last_ts)
  increment a clock_rollback metric
  log last_ts, now, worker_id

Waiting is acceptable for a few milliseconds. Refusing is better for a large step (seconds). Do not paper over a 2-second jump by minting on a stale timestamp; you will collide or lie about time.

Related clock bugs:

Clock jumps forward     IDs stay unique; you skip a time range. Usually OK.
Leap smear              Fine if the OS smears; a hard step is a rollback.
VM pause / STW GC       “now” stalls, then leaps. Treat a backward reading
                        as rollback; a forward leap as a new timestamp.
Two regions             Clocks disagree by tens of ms. Global sort is
                        approximate. Uniqueness still holds if worker bits
                        include the region.

Prefer the OS monotonic clock only for durations. The timestamp field must be wall-clock milliseconds since the epoch, or IDs will not sort across processes.

9. Sequence overflow

One worker, one millisecond, 4096 IDs already issued.

t = 12:00:00.441
seq = 0, 1, 2, …, 4095     ← 12 bits full

NextID() options:
  wait until t >= 12:00:00.442, then seq = 0
  or return an error to the caller

Wait is the usual library behavior. The wait is at most one millisecond if the clock is healthy. At 1,250 IDs/s per pod you will not hit 4096 in a millisecond. You can hit it on a bursty batch job that mints in a tight loop on one worker.

Error is right when the caller would rather fail than stall a request thread — for example a synchronous HTTP worker with a 5 ms budget. Then the caller retries, ideally on another worker.

Do not wrap the sequence and reuse 0 in the same millisecond. That is a collision by construction.

A forward clock jump after overflow is fine: new timestamp, sequence resets. A backward clock after overflow is section 8 again.

10. ULID and UUID v7

Snowflake needs a worker registry (or an equivalent unique slot). Some teams do not want that.

ULID is a 128-bit value, usually a 26-character Crockford Base32 string: 48 bits of timestamp (milliseconds) plus 80 bits of randomness. Lexicographic sort matches time order. No worker id. Collision chance is the random part — fine at chat scale.

UUID v7 is the same idea in UUID clothing: 48-bit Unix milliseconds, version bits, then random. It fits columns and libraries that already speak UUID. It is time-sortable, unlike v4.

UUID v4     random, 128-bit, no coordination, not sortable
UUID v7     time prefix + random, 128-bit, no worker registry
ULID        time prefix + random, 26-char string, no worker registry
Snowflake   time + worker + sequence, 64-bit, needs unique worker slots

Pick ULID or UUID v7 when the interviewer wants strings, or when you refuse to allocate worker ids. Pick Snowflake when you want a compact bigint primary key and you can operate worker slots.

Trade-off: 128-bit random-suffix IDs still scatter a little inside one millisecond. Snowflake sequences are packed. Indexes are a bit kinder to Snowflake at very high insert rates. For most products the difference is smaller than the operational cost of a worker registry.

Try both shapes in the tool.

11. When not to use Snowflake

Snowflake is a distributed object id. It is not a ticket number and not a chat cursor.

Human invoice numbers

Finance wants INV-2026-000123, consecutive-looking, printable, scoped by year or company. A 64-bit Snowflake is an ugly, unpredictable “invoice number.” Allocate INV-2026-… with a database counter in the same transaction as the invoice row, as in the invoice generation walkthrough. Gaps on rollback are allowed. Duplicates are not. The UUID (or Snowflake) can still be the primary key; the pretty number is a separate column.

Do not show INV-1842… to anyone.

Per-chat sequences

WhatsApp-style resume is after_sequence=1000 inside one conversation. That number must be monotonic per chat, not roughly-time-global. Two messages in c_ab at the same millisecond still need 1001 then 1002 for that conversation, and those values must not come from a fleet-wide Snowflake. Use an atomic per-conversation counter. The WhatsApp design is the full argument.

message_id      Snowflake / ULID     unique object name
sequence        per conversation     order, pagination, gap detect
invoice_number  year counter         human / legal label

Other poor fits

Unguessable capability URLs     Snowflake leaks time and worker. Use random.
Gapless statutory sequences     Snowflake has gaps by design (unused seq, rollback).
Tiny monolith, one primary      SERIAL next to the row is simpler.

12. APIs and where the generator lives

Most products should not open a network hop to mint an id. Embed the generator as a library.

NextID() -> int64

Call it inside the request that needs a primary key. No HTTP. Worker id is assigned at process start (ordinal or lease). Decode is a local bit split, useful in support tools.

If several languages must share one implementation, or you want a single place that hands out worker leases, expose a small internal service:

Request:

POST /internal/ids
{
  "count": 1
}

Response:

HTTP 200 OK
{
  "ids": [1842648371928371201]
}

Batch request when a job needs many:

POST /internal/ids
{
  "count": 100
}

HTTP 200 OK
{
  "ids": [1842648371928371201, 1842648371928371202]
}

Clock rollback or an exhausted worker lease:

HTTP 503 Service Unavailable
{
  "error": {
    "code": "ID_GENERATOR_UNAVAILABLE",
    "message": "clock rolled back; not issuing ids"
  }
}

count is a batch size, not an idempotency key. Retrying POST /internal/ids mints new ids. The chat create path still uses (sender_id, client_message_id) so Alice’s retry does not insert a second row.

Library     NextID() in-process. Default. No extra SPOF.
Service     Extra hop, extra failure mode. Use for polyglot or leased workers.
Sidecar     Rarely worth it; same hop cost as a service on localhost.

I would start with a library. I would not put ID minting on the public internet. If it is a service, authenticate cluster-internal callers and rate-limit it so a broken client cannot burn a worker’s sequence space.

13. Failure scenarios

Degraded behavior is narrow: it is better to refuse an id than to emit a duplicate. Chat send fails loudly. A silent collision corrupts every secondary index that trusted uniqueness.

14. Observability

Log request_id, worker_id, datacenter_id, last_ts, and now on refuse paths. Do not log every successful mint at 100k/s — sample.

Metrics that matter:

ids_issued_total                  {dc, worker}
id_mint_latency_seconds
clock_rollback_total              {dc, worker}
sequence_overflow_total
id_mint_wait_ms                   time spent waiting for next ms
worker_lease_renew_fail_total
unique_constraint_conflict_total  backstop on the insert path

Alert on clock_rollback_total and lease failures. A single overflow wait is noise; a sustained overflow on one worker means a batch job is pinned to one process.

Support should be able to decode an id to {timestamp, dc, worker, sequence} without a database. That is how you answer “which pod minted this row?”

Security: treat Snowflake ids as public labels, not capabilities. They leak creation time and a coarse worker. Rate-limit create endpoints so an attacker cannot use id spacing as a traffic oracle. Do not put the generator on a public URL.

15. Final architecture

Embedded library — the usual answer:

 Client
   │
   ▼
 API pod
   │  NextID()  ← in-process Snowflake
   │    timestamp  (wall clock, guarded against rollback)
   │    datacenter (config)
   │    worker     (ordinal or lease)
   │    sequence   (per-ms counter)
   │
   ▼
 Message DB
   PRIMARY KEY = snowflake
   UNIQUE (sender_id, client_message_id)

On start
  claim worker slot (ordinal or lease)
  load last_ts watermark for that slot

On NextID
  now = wall_ms()
  if now < last_ts: wait or refuse
  if now == last_ts:
      seq += 1
      if seq overflows: wait for next ms
  else:
      seq = 0
  persist watermark (memory; disk if reuse is a risk)
  return pack(now, dc, worker, seq)

If you added an ID service, it sits beside the API, not in front of the user:

 API pods  ──POST /internal/ids──►  ID service replicas
                                      each replica: unique worker
                                      lease store (etcd / SQL)

Mental model:

Need sortable 64-bit, high QPS     → Snowflake library
Need sortable string, no registry  → ULID / UUID v7
Need no sort, simplest             → UUID v4
Need INV-2026-000123               → DB counter next to the invoice
Need chat resume order             → per-conversation sequence

16. Interview-ready summary

Key decisions to remember

1. Never MAX(id)+1 across nodes.
2. A single-node counter dies the moment a second pod starts.
3. UUID v4 is unique and simple; it is not sortable or compact.
4. A central SERIAL is unique and becomes a hotspot at fleet scale.
5. Snowflake = timestamp + unique worker + per-ms sequence.
6. Assign worker ids uniquely; reuse needs a watermark past last_ts.
7. On clock rollback, wait or refuse — do not mint.
8. On sequence overflow, wait for the next millisecond (or error).
9. Embed NextID() as a library unless you have a polyglot/lease reason.
10. Do not use Snowflake for invoice numbers or per-chat sequences.

Likely interviewer follow-up questions

• Numeric or string? Why 64-bit?
• How do two pods in the same millisecond not collide?
• How do you assign worker ids in Kubernetes?
• What if a pod crashes and the replacement reuses worker 7?
• What does NTP stepping backward do to your generator?
• 4096 IDs in one millisecond — wait or fail?
• Why not UUID v7 for everything?
• Multi-region: bits or separate epochs?
• Library or service?
• How is this different from a WhatsApp sequence or an invoice number?
• Can someone guess the next id?

Senior-level points that differentiate the answer

• Open with the two-pod 1001 collision, not a bit table.
• Treat worker reuse and clock rollback as the real bugs, not the bit widths.
• Separate object ids from conversation sequences and human ticket numbers.
• Persist a per-worker watermark so a fast restart cannot replay a millisecond.
• Fail closed on rollback: a refused mint is better than a duplicate.
• Decode IDs in support tools; alert on rollback and lease loss.
• Say when SERIAL or UUID v4 is the better, smaller design.

A 1–2 minute verbal answer

I would mint 64-bit Snowflake-style IDs locally: a millisecond timestamp, a unique worker id, and a per-millisecond sequence. That way two API pods inserting a chat message in the same millisecond cannot both choose 1001, and we do not round-trip to a central sequence on every send. I would assign worker ids with a StatefulSet ordinal or a lease, never a bare hash into 10 bits. If a worker is reused after a crash, I wait until the clock is past that worker’s last issued timestamp. If NTP steps backward, I stop issuing rather than recreate old ids. Sequence overflow waits for the next millisecond. I would embed NextID() as a library. UUID v4 if I do not need sort or compactness; ULID or UUID v7 if I want time-order without a worker registry. I would not use Snowflake for INV-2026-… or for per-conversation chat sequences.

Generate samples in the Snowflake / ULID generator. Drill the one-minute form on the questions hub. For the broader interview framework, see the System Design Interview Complete Guide.