System design interview question

Design a Unique ID Generator

Q: Why not just use UUIDs, or the database’s auto-increment?

A Snowflake-style layout generated in-process: 41 bits of milliseconds since a custom epoch, 10 bits of worker id (with a couple of those bits identifying the region), and 12 bits of sequence. Each host leases a worker id at startup; everything else is local. This gives 8-byte, roughly time-ordered, decodable ids at millions per second per host. Where ids are exposed publicly and must not leak volume or creation time, wrap them (encrypt or map to a separate public id). Twitter’s Snowflake, Discord and Instagram all use variants of this layout.

Q: How do you split the 64 bits, and what happens when one field runs out?

Use 41 bits of milliseconds counted from a custom epoch set to the launch date (counting from 1970 would waste over half the range), giving about 69 years. Use 10 bits for the worker, split as 2 bits of region and 8 bits of host within the region, and 12 bits of sequence. Write the layout down in one shared library with a decode function, because every team will eventually need to read an id. Plan the end of life: a 69-year horizon is fine, but a 41-bit field started in 1970 would end in 2039.

Q: Uniqueness rests entirely on no two generators sharing a worker id. How do you guarantee that with autoscaling?

At startup each generator takes a free worker id in its region’s block from etcd with a create-if-absent transaction attached to a 10-second lease, renewing every 3 seconds. If renewal fails, it stops issuing ids by second 8, before the lease could expire and be granted to someone else. Released or expired ids are quarantined for longer than the maximum clock skew allowed in the fleet before reuse. The registry is only on the startup path, so its outage stops new generators from starting, not existing ones from issuing.

Q: Your ids depend on the wall clock. What goes wrong with clocks, and how do you stay safe?

The generator keeps last_ms. If now < last_ms by a few milliseconds, it waits until the clock catches up (or keeps using last_ms while sequence remains). If the regression exceeds a threshold, such as 100 ms, it stops issuing, marks itself unhealthy and releases its worker id, because something is badly wrong with the host. Hosts run NTP configured to slew rather than step where possible, and a skew monitor compares each host with peers and reference time, alerting at a few milliseconds and fencing hosts beyond a hard limit by revoking their lease. The same last_ms guard also persists across restarts (written to local disk), so a restart into an earlier time is caught.

Q: Should id generation be a central service everyone calls, or code inside every service?

Ship one small library per major language (they are a few dozen lines) sharing a test suite of layout and edge cases, and run a sidecar that exposes the same generator over a local socket for everything else. Each process or sidecar leases one worker id. A central service is offered only for odd clients, and it hands out batches. The decode function lives in the same library and in an admin tool.

Q: Time-ordered ids are great for B-trees. Are there downsides when you shard by id?

Use the time-ordered id as the primary key inside each shard for insert locality, and choose shards by a hash of the id or, better, by the owning entity (a user id), so writes spread evenly. Use the timestamp embedded in the id for time-based queries and partitioning of append-only tables (for example monthly partitions of an events table), where a hot newest partition is expected and fine.

Hand out a million 64-bit ids a second across many hosts and regions, never twice, roughly in time order, with no central bottleneck and no trust in the wall clock.

Last updated 2026-09-30. Difficulty: medium. Patterns: id-generation, clocks, leases, bit-layout, k-sortable. Reported at Amazon, Google, Microsoft, Stripe, Uber.

Walk through a strong candidate's answer, turn by turn.

The interviewer asks, the candidate answers and draws, and you press Next. Pause to answer yourself at the key decisions, and ask the AI Mentor anything along the way.

Walk through it Take the mock interview

Functional requirements

Generate a unique id. Every call returns an id that has never been returned before, anywhere in the company, ever.
64-bit numeric ids. Fits a BIGINT primary key and a long in every language; half the size of a UUID in every index and cache.
Roughly time-ordered. Ids created later are larger, to within a few milliseconds across hosts (k-sortable), so sorting by id is close to sorting by creation time.
Decodable. Given an id, tools can tell when and where it was generated, which helps debugging and routing.
Out of scope. Short human-readable codes (see Design a URL Shortener), strictly gapless sequences such as invoice numbers (mention how), and cryptographic unguessability.

Non-functional requirements

Throughput (1 M ids/s peak across the fleet). Every write in every service needs one, often several.
Latency (< 1 µs in-process, < 1 ms as a service). Ids are on the critical path of every insert; a network hop per id is often too slow.
Availability (no single point of failure). If ids cannot be generated, nothing can be written. A central id service is a company-wide outage waiting to happen.
Uniqueness (zero duplicates, ever). This is the requirement that drives the hardest trade-off: generating without coordination means each generator must own a disjoint space, and the clock it relies on can go backwards.
Lifetime (≥ 50 years). The bit budget for time must not run out within the system’s life.

Back-of-envelope estimates

Ids per millisecond per worker: 4,096. A 12-bit sequence gives 2^12 = 4,096 ids per millisecond per worker, about 4 M per second from a single process. Far above what one host needs.
Maximum workers: 1,024. 10 bits of worker id = 2^10 = 1,024 concurrent generators. Enough for a large fleet if ids are generated per host or per pod; more bits come from the sequence or time if needed.
Lifetime of 41 bits of milliseconds: ~69 years. 2^41 ms = 2.2 × 10^12 ms ÷ (1000 × 86 400 × 365) ≈ 69.7 years from the custom epoch. Choose the epoch as the system’s launch date, not 1970, or you waste 56 of those years.
Fleet capacity: ~4 B ids/s. 1,024 workers × 4,096 per ms × 1,000 = ~4.2 B ids/s: over 4,000 times the 1 M/s peak. The layout is not the bottleneck; the clock and worker assignment are where it can fail.
UUID storage overhead: +8 bytes per id, per index. A UUID is 16 bytes against 8 for a 64-bit id. A table with 10 B rows and three indexes containing the id carries an extra 10 B × 8 B × 4 ≈ 320 GB.
Waiting out a clock step: up to the size of the step. If the clock jumps back 5 ms, a generator that refuses to reuse time must wait 5 ms before issuing again. Small steps are absorbed; a jump of seconds means stop and alert.

Components

Services: Every service that writes data: orders, messages, payments. They call next_id() in-process and use the result as a primary key, a message id or an idempotency key.
ID generator (library / sidecar per host): Composes ids locally from the current millisecond, the worker id it holds a lease on, and a per-millisecond sequence. No network call per id. Refuses to issue if its clock moved backwards or its lease is uncertain.
Host clock (NTP / PTP-disciplined): The wall clock the generator reads. Usually within a few milliseconds of true time, but it can step backwards when NTP corrects it, and it can be wrong on a misconfigured host.
Worker-id registry (etcd / ZooKeeper leases): Hands each generator an unused worker id under a lease that must be renewed every few seconds. Guarantees no two live generators hold the same id, and records when an id was last released.
Orchestrator (Kubernetes): Starts and stops the hosts and pods that run generators. Churn here (autoscaling, deploys) is why worker ids must be leased rather than configured by hand.
Clock-skew monitor: Compares every host’s clock with reference time and with peers, alerts on drift beyond a few milliseconds, and can fence a host whose clock is wrong before it issues bad ids.
Region 2 generators: Generators in another region. They draw worker ids from a disjoint block (or carry region bits), so the regions never need to coordinate.
Segment service (range allocator): An alternative mode for counters that must be dense and strictly increasing within one table: hands out ranges of 1,000 numbers from a ticket table, double-buffered so a client never waits.
Ticket table (one row per sequence): A tiny relational table holding the next free number for each named sequence. Touched once per range, so a single primary with a standby is plenty.
Consumer databases (B-tree primary keys): Where the ids end up as keys. Time-ordered ids append to the right edge of a B-tree, which keeps inserts cache-friendly, but can concentrate writes on one shard if data is range-partitioned by id.
ID decoder (admin tool): Splits an id back into timestamp, region, worker and sequence. Used in debugging ("when was this order created and by which host?") and to route by time.

User flows

Generate an id in-process. The hot path: no network, no lock contention beyond one atomic, a few nanoseconds. Uniqueness comes from the worker id; ordering from the timestamp.
1. A service asks the generator for the next id.
2. The generator reads the current millisecond since the custom epoch. It uses the wall clock (it must be comparable across hosts) but never trusts it blindly: it remembers the last millisecond it used and compares.
3. If it is the same millisecond as the last id, it increments the sequence; if later, the sequence resets to zero. The (last_ms, sequence) pair is updated with one compare-and-swap, so many threads can generate concurrently without a lock. Resetting to a random small value instead of zero avoids every id at a quiet moment ending in ...000, which skews some hash partitions.
4. It composes the id from the bit fields and returns it. 1 sign bit (always 0) · 41 bits of milliseconds · 10 bits of worker id (including region bits) · 12 bits of sequence. The result is positive, fits a signed 64-bit integer, and sorts by time.
5. The service uses it as a primary key; inserts land at the right edge of the B-tree. Because ids grow over time, new rows append to the last index page instead of random pages: fewer page splits and a hot working set that stays in memory. UUIDv4 keys, by contrast, scatter inserts across the whole index.
6. Later, an engineer decodes an id to see when and where it was generated. Shifting the bits back out gives the millisecond, region, worker and sequence. "This duplicate order came from worker 417 in region 1 at 14:03:22.118" turns a mystery into a lookup.
A new host gets a worker id. Worker ids are the only thing generators must coordinate on, and only at startup. Leases make it automatic and safe under churn.
1. The orchestrator starts a pod; its generator asks the registry for a free worker id. The registry picks an id in this region’s block that is unclaimed and was released longer ago than the maximum allowed clock skew, so a crashed previous holder cannot have issued ids in the same milliseconds.
2. The generator renews its lease every few seconds. If a renewal fails, the generator does not know whether it still owns the id, so it stops issuing ids before the lease could expire (renew at 3 s on a 10 s lease, stop at 8 s). Refusing is safe; issuing with a lost id is not.
3. On shutdown it releases the id; the registry records the release time. A released id stays quarantined for a short period before reuse, longer than the maximum clock skew allowed in the fleet.
4. Generators in another region draw from their own block. With 2 region bits and 8 worker bits, or simply disjoint ranges of worker ids per region, regions never coordinate at all, and a partition between them cannot cause duplicates.
A burst: 10,000 ids in one millisecond on one host. The scale-breaking case for a single worker: the 12-bit sequence runs out within a millisecond. The generator must wait, never wrap.
1. A batch job requests ids in a tight loop. At 4,096 per millisecond the sequence for the current millisecond is exhausted after a quarter of the batch.
2. When the sequence overflows, the generator spins until the clock reaches the next millisecond. Wrapping the sequence back to zero in the same millisecond would duplicate ids. Waiting costs under a millisecond and caps each worker at ~4 M ids/s, far above any real need.
3. For sustained high rates, the job uses more workers or batch allocation. A heavy job can lease several worker ids (one per thread). Some generators also allow borrowing a few milliseconds from the future during bursts, at the cost of ids slightly ahead of real time.
4. Alternatively, a client takes a whole range from the segment service. For bulk imports where time order does not matter, one round trip yields 1,000 or 100,000 numbers, and the client hands them out locally.
The clock jumps backwards. The failure that causes duplicate ids in naive implementations. The generator detects it and refuses to reuse time; the monitor catches hosts whose clocks are wrong.
1. NTP steps the host clock back by 5 ms. Usually NTP slews (speeds up or slows down the clock gradually), but after a long drift or a restart it can step. A VM migrating between hosts can also see time jump.
2. The generator sees a current millisecond lower than its last one. Issuing now would produce ids in milliseconds it has already used, with sequence numbers starting from zero: duplicates. This check is the single most important line in the generator.
3. For a small step, it waits until the clock catches up to its last millisecond. A 5 ms wait is invisible to callers. Internally the generator could also keep issuing from its last millisecond’s remaining sequence if any is left.
4. For a large step, it stops issuing, reports unhealthy, and releases its worker id. A host whose clock went back by seconds cannot be trusted. Health checks fail, traffic moves to other hosts, and an operator or automation investigates. Duplicates are worse than an unavailable host.
5. The skew monitor flags hosts whose clocks drift from their peers and can fence them. Revoking the host’s lease in the registry stops its generator immediately, even if the host itself has not noticed anything wrong.
Dense sequences with range allocation. When a table needs small, increasing numbers (order numbers shown to customers), a ticket table hands out ranges so the database is touched once per thousand ids.
1. The client library asks the segment service for the next range of the "order_number" sequence.
2. The segment service advances the sequence row atomically.
3. The client hands out numbers from memory and fetches the next range when 20 % remain. Double buffering: the next range is fetched in the background before the current one runs out, so the database being slow for a moment never blocks an insert.
4. A client that crashes loses the rest of its range: gaps, never duplicates. If the business truly needs gapless numbers (some invoicing rules), assign them inside the same transaction that commits the record, from a per-shard counter, and accept that this serialises those inserts.

Deep dives

Which kind of id

Why not just use UUIDs, or the database’s auto-increment?

Auto-increment works on one database and gives small, ordered ids, but it is a single point of contention and breaks the moment data is sharded: two shards hand out the same numbers. UUIDv4 needs no coordination at all, but it is 128 bits, random (so inserts scatter across indexes), and says nothing about when it was created.

The useful middle is an id that each generator can create on its own, that is small, and that sorts roughly by time. Getting it requires giving each generator its own slice of the id space and a trustworthy notion of time.

Snowflake-style 64-bit: time + worker + sequence, generated locally chosen
UUIDv7 / ULID (time-ordered, 128 bits, random tail) situational: when 128-bit keys are acceptable and avoiding worker-id management is worth the space
UUIDv4 situational: public identifiers that must not be guessable or reveal volume
Database auto-increment or a central ticket server per id rejected

The answer: A Snowflake-style layout generated in-process: 41 bits of milliseconds since a custom epoch, 10 bits of worker id (with a couple of those bits identifying the region), and 12 bits of sequence. Each host leases a worker id at startup; everything else is local. This gives 8-byte, roughly time-ordered, decodable ids at millions per second per host. Where ids are exposed publicly and must not leak volume or creation time, wrap them (encrypt or map to a separate public id). Twitter’s Snowflake, Discord and Instagram all use variants of this layout.

Can a competitor learn your order volume from your ids?

Yes: two order ids a day apart reveal roughly how many ids were generated between them, and the timestamp is in plain sight. If that matters, expose a different public id (a random or encrypted token) and keep the Snowflake id internal.

When would you choose UUIDv7 instead?

When you cannot or do not want to manage worker ids (many short-lived clients, edge devices, offline creation) and can afford 16 bytes. UUIDv7 keeps the time ordering that makes indexes happy, and its random bits make collisions vanishingly unlikely without any coordination.

Do these ids work as idempotency keys?

Only if the client generates the id once and reuses it on retries. An id generated per attempt is different each time and defeats idempotency. The rule is about where the id is created, not its format.

Why 64 bits rather than a larger layout with more room?

Because 64 bits is the largest integer every language, database and JSON parser handles natively (with the caveat that JavaScript needs ids sent as strings above 2^53). Larger ids become strings or byte arrays everywhere, which costs more than the bits it buys.

Spending 64 bits

How do you split the 64 bits, and what happens when one field runs out?

Every bit spent on one field is taken from another. More time bits mean a longer lifetime; more worker bits mean more generators; more sequence bits mean more ids per millisecond per generator. The sign bit is reserved so ids stay positive in languages with signed integers.

The budget has to match the system: how many generators will run at once over its lifetime, the peak rate per generator, and how long the system will exist.

1 sign · 41 ms · 10 worker (2 region + 8 host) · 12 sequence, custom epoch chosen
Fewer sequence bits, more worker bits situational: tens of thousands of short-lived generators, each issuing few ids
Second resolution with more sequence bits situational: long-lived archival ids where ordering within a second does not matter

The answer: Use 41 bits of milliseconds counted from a custom epoch set to the launch date (counting from 1970 would waste over half the range), giving about 69 years. Use 10 bits for the worker, split as 2 bits of region and 8 bits of host within the region, and 12 bits of sequence. Write the layout down in one shared library with a decode function, because every team will eventually need to read an id. Plan the end of life: a 69-year horizon is fine, but a 41-bit field started in 1970 would end in 2039.

You need 2,000 generators in one region. What changes?

Borrow bits from the sequence: 11 host bits and 11 sequence bits gives 2,048 hosts at 2,048 ids per millisecond each, still millions per second per host. Changing the layout only affects new ids; old ids still decode with the old layout if a version bit or a cut-over date is recorded.

Why does the sign bit matter?

Java, Go’s int64 and SQL BIGINT are signed. If the top bit were used, ids generated after a certain date would become negative and sort before older ones, breaking ordering and confusing every tool that assumes positive keys.

How do JavaScript clients handle 64-bit ids?

JavaScript numbers are exact only up to 2^53, so large ids are silently rounded. Send ids as strings in JSON APIs, and use BigInt where arithmetic is needed. This is a classic production bug with Snowflake ids.

Giving every generator its own id

Uniqueness rests entirely on no two generators sharing a worker id. How do you guarantee that with autoscaling?

Static configuration ("host 17 is worker 17") breaks as soon as hosts are replaced automatically: a new pod gets an address nobody configured, or two pods are accidentally given the same number. With deploys and autoscaling, generators start and stop all day.

A crashed generator is the subtle case. It may have issued ids up to the moment of the crash. If its worker id is handed to a new generator immediately, and the new host’s clock is a few milliseconds behind, the new generator can issue ids in the same milliseconds with the same worker id: duplicates.

Lease worker ids from a consensus store (etcd / ZooKeeper) with renewals and a reuse quarantine chosen
Static configuration per host rejected
Derive the worker id from the host’s IP or MAC address rejected

The answer: At startup each generator takes a free worker id in its region’s block from etcd with a create-if-absent transaction attached to a 10-second lease, renewing every 3 seconds. If renewal fails, it stops issuing ids by second 8, before the lease could expire and be granted to someone else. Released or expired ids are quarantined for longer than the maximum clock skew allowed in the fleet before reuse. The registry is only on the startup path, so its outage stops new generators from starting, not existing ones from issuing.

The generator is partitioned from etcd but its host is fine. What happens?

It cannot renew its lease, so it stops issuing before the lease expires. Calls fail over to other hosts. It feels harsh, but the alternative is that etcd expires the lease, gives the id to a new generator, and both issue ids at once.

Why not use ZooKeeper sequential nodes to number workers?

They hand out ever-increasing numbers, which would run past 1,024 after enough restarts. You still need to map them into a fixed range of reusable ids, which brings back the lease and quarantine logic.

How long should the quarantine be?

Longer than the worst clock difference you allow between hosts plus the time a crashed generator could have kept issuing after losing its lease. With skew bounded to 100 ms by monitoring and a stop-before-expiry rule, a quarantine of a few seconds is ample; minutes is cheap insurance.

Not trusting the clock

Your ids depend on the wall clock. What goes wrong with clocks, and how do you stay safe?

Host clocks drift and are corrected by NTP. Usually NTP slews the clock gradually, but it can step it backwards, virtual machines can see time jump after migration, and a misconfigured host can be seconds or hours off. A generator that blindly uses the current time will reuse milliseconds it already used.

A monotonic clock never goes backwards, but it is not comparable between hosts, so it cannot give ids that sort across the fleet. The generator needs the wall clock for ordering and a defence for when it misbehaves.

Wall clock with a last-millisecond guard: wait on small regressions, refuse and alert on large ones; fleet skew monitoring chosen
Logical counter seeded from the clock at startup situational: when ordering is irrelevant and only uniqueness matters
Hybrid logical clocks situational: databases that need causally ordered timestamps, such as CockroachDB

The answer: The generator keeps last_ms. If now < last_ms by a few milliseconds, it waits until the clock catches up (or keeps using last_ms while sequence remains). If the regression exceeds a threshold, such as 100 ms, it stops issuing, marks itself unhealthy and releases its worker id, because something is badly wrong with the host. Hosts run NTP configured to slew rather than step where possible, and a skew monitor compares each host with peers and reference time, alerting at a few milliseconds and fencing hosts beyond a hard limit by revoking their lease. The same last_ms guard also persists across restarts (written to local disk), so a restart into an earlier time is caught.

What about leap seconds?

With a stepped leap second the clock repeats a second, which is exactly the backwards case the guard handles by waiting. Many providers instead smear the leap second over a day, which keeps clocks monotonic and avoids the wait entirely.

If ids only need to be unique, why care about time at all?

Because ordering is valuable: B-tree inserts append instead of scattering, recent data clusters together, and ids can be decoded for debugging. If you truly only need uniqueness, a counter per worker would do, but you would give up those benefits.

How close to time order are ids from different hosts?

Within the clock skew between them, typically a few milliseconds with good NTP, and within microseconds with PTP. Two ids from different hosts a millisecond apart can be out of order. Say this clearly: the ids are k-sortable, not strictly ordered.

Library, sidecar or central service

Should id generation be a central service everyone calls, or code inside every service?

A central id service is simple to reason about and easy to change, but it puts a network hop on every insert and makes the service a dependency of everything: if it is down, nobody can write.

A library inside every service has no network hop and no shared dependency, but it must be implemented consistently in every language, and each instance needs a worker id.

In-process library, with a local sidecar for languages without one chosen
Central id service, batched situational: small fleets, or as a fallback for clients that cannot run the library
Each database generates its own ids rejected

The answer: Ship one small library per major language (they are a few dozen lines) sharing a test suite of layout and edge cases, and run a sidecar that exposes the same generator over a local socket for everything else. Each process or sidecar leases one worker id. A central service is offered only for odd clients, and it hands out batches. The decode function lives in the same library and in an admin tool.

How do you test that no duplicates are ever produced?

Property tests on the generator with a fake clock that jumps forwards and backwards and with many threads; a fleet-wide canary that samples generated ids into a store with a uniqueness constraint; and alerts on any unique-key violation in consumer databases, which would be the first symptom of a real duplicate.

A team writes its own generator with the same layout but forgets the clock guard. How would you catch it?

Make the shared library the only approved way, enforce it in code review and dependency checks, and watch for duplicate-key errors in databases. Decoding the worker id of a duplicate points straight at the offending generator.

Ids as database keys

Time-ordered ids are great for B-trees. Are there downsides when you shard by id?

Within one database, time-ordered keys append to the end of the primary key index: inserts touch the same few pages, which stay in memory, and page splits are rare. Random keys (UUIDv4) insert all over the index, causing far more disk I/O at scale.

Across shards, the same property can hurt: if data is range-partitioned by id, every new row goes to the shard holding the newest range, which becomes a hot spot while the others sit idle.

Time-ordered ids as keys; shard by hash of the id (or by an owner id), never by id range chosen
Range-partition by id rejected
Random ids (UUIDv4) everywhere situational: when unguessability is required and the data volume is modest

The answer: Use the time-ordered id as the primary key inside each shard for insert locality, and choose shards by a hash of the id or, better, by the owning entity (a user id), so writes spread evenly. Use the timestamp embedded in the id for time-based queries and partitioning of append-only tables (for example monthly partitions of an events table), where a hot newest partition is expected and fine.

Can you extract creation time from the id instead of storing a created_at column?

Yes, to millisecond precision, and some systems do to save space. Keep a real created_at when the business meaning of creation time differs from id generation time (an imported record, a backdated order).

Why do UUIDv4 primary keys slow down large tables?

Each insert goes to a random leaf page of the index. Once the index is larger than memory, most inserts need a page read from disk and cause page splits throughout the tree, so write throughput drops sharply and the index becomes fragmented.

The theory behind it

Unique ids, ordering and time: Auto-increment vs UUID vs Snowflake vs ULID/UUIDv7, time-ordered ids, id generation at scale, clock skew, logical clocks, and why "ordered by time" is harder than it sounds.
Consensus, leases and coordination: Leader election, Raft and Paxos at interview depth, ZooKeeper and etcd, distributed locks and why they are fencing tokens, plus how to avoid needing coordination at all.
Choosing a database: Relational vs document vs wide-column vs key-value vs graph vs search vs time-series; how to pick storage from the access pattern, design keys and indexes, and answer "why not Postgres?".