Design a Unique ID Generator

• 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.

• 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.

• 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.

• 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.

1. 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.
   3. If it is the same millisecond as the last id, it increments the sequence; if later, the sequence resets to zero.
   4. It composes the id from the bit fields and returns it.
   5. The service uses it as a primary key; inserts land at the right edge of the B-tree.
   6. Later, an engineer decodes an id to see when and where it was generated.
2. 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.
   2. The generator renews its lease every few seconds.
   3. On shutdown it releases the id; the registry records the release time.
   4. Generators in another region draw from their own block.
3. 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.
   2. When the sequence overflows, the generator spins until the clock reaches the next millisecond.
   3. For sustained high rates, the job uses more workers or batch allocation.
   4. Alternatively, a client takes a whole range from the segment service.
4. 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.
   2. The generator sees a current millisecond lower than its last one.
   3. For a small step, it waits until the clock catches up to its last millisecond.
   4. For a large step, it stops issuing, reports unhealthy, and releases its worker id.
   5. The skew monitor flags hosts whose clocks drift from their peers and can fence them.
5. 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.
   4. A client that crashes loses the rest of its range: gaps, never duplicates.

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

Good answers name: Snowflake-style 64-bit: time + worker + sequence, generated locally, UUIDv7 / ULID (time-ordered, 128 bits, random tail), UUIDv4, Database auto-increment or a central ticket server per id.

Our pick: 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.

1. 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.
2. 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.
3. 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.
4. 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.

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

Good answers name: 1 sign · 41 ms · 10 worker (2 region + 8 host) · 12 sequence, custom epoch, Fewer sequence bits, more worker bits, Second resolution with more sequence bits.

Our pick: 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.

1. 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.
2. 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.
3. 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.

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

Good answers name: Lease worker ids from a consensus store (etcd / ZooKeeper) with renewals and a reuse quarantine, Static configuration per host, Derive the worker id from the host’s IP or MAC address.

Our pick: 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.

1. 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.
2. 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.
3. 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.

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

Good answers name: Wall clock with a last-millisecond guard: wait on small regressions, refuse and alert on large ones; fleet skew monitoring, Logical counter seeded from the clock at startup, Hybrid logical clocks.

Our pick: 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.

1. 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.
2. 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.
3. 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.

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

Good answers name: In-process library, with a local sidecar for languages without one, Central id service, batched, Each database generates its own ids.

Our pick: 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.

1. 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.
2. 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.

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

Good answers name: Time-ordered ids as keys; shard by hash of the id (or by an owner id), never by id range, Range-partition by id, Random ids (UUIDv4) everywhere.

Our pick: 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.

1. 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).
2. 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.