Design a unique ID generator

In 2 minutes

I would use a 64-bit, time-ordered ID built locally by many small generators, with no call to a central server per ID. The layout is one unused sign bit, 41 bits of milliseconds since our launch date, 10 bits of worker number and 12 bits of sequence. That lasts about 70 years, allows 1,024 generators, and lets each generator make 4,096 IDs per millisecond. At 100,000 IDs a second over 20 generators, each handles 5,000 a second, so capacity is not the problem. The risks are duplicates. To stop two live generators sharing a worker number, each takes a lease from a small consistent registry at startup and stops issuing if it cannot renew. To stop a clock that moves back, each generator remembers its last timestamp, waits out a small step, refuses a large one, raises an alert, and saves its highest timestamp so a restart cannot go back in time. If 128 bits were allowed, I would use UUIDv7 instead, because it needs no registry. The trade-off is rough ordering rather than strict ordering, which is what removes the bottleneck.

The question

Clarifying questions

• How big can an ID be: 64 bits, or is 128 bits fine? A 64-bit number fits a normal integer column and halves index size. A 128-bit ID has room for random bits and needs no coordination.
• Must IDs be sorted by time, and how strictly? Roughly sorted IDs make inserts append to the end of an index. Strict global order needs a single sequencer, which is a bottleneck.
• How many IDs a second, and from how many machines? The rate decides how many bits you need for the per-millisecond sequence and for the worker number.
• Is it a problem if people can guess or count IDs? Time-based IDs leak when a row was made and roughly how many exist. If that matters, the public handle must be a separate random token.
• Can the service rely on synced clocks across machines? Time-based IDs assume clocks that are close to correct. You must decide what to do when one is not.

Requirements

Functional

• Return a new ID that has never been returned before, anywhere in the system.
• IDs fit in 64 bits and sort roughly by creation time.
• Many generators can run at once, with no call to a central server for each ID.
• A generator that restarts or loses its clock never repeats an ID.

Non-functional

• Throughput: 100,000 IDs a second across the fleet, with room to grow 100 times.
• Latency: p99 under 2 ms per ID.
• Uniqueness: zero duplicates, even during failover.
• Availability of 99.99% for ID creation, with no single point of failure.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real service.
• 100,000 IDs a second at peak, spread over 20 generators.
• 10 billion rows in the largest table, each indexed by its ID.
• A year is about 31.6 billion milliseconds (365.25 days × 86,400 s × 1,000).

The arithmetic:

• Load per generator: 100,000 ÷ 20 generators → 5,000 IDs a second each
• Capacity per generator: 12 sequence bits = 2^12 = 4,096 IDs per millisecond × 1,000 ms → 4,096,000 a second, over 800 times the load
• Timestamp lifetime: 2^41 ms = 2.2 trillion ms ÷ 31.6 billion ms per year → ≈ 69.7 years from the chosen epoch
• Worker slots: 10 worker bits = 2^10 → 1,024 generators at most
• Index size of the key: 10 billion × 8 bytes, against 10 billion × 16 bytes for a UUID → 80 GB against 160 GB, before index overhead

High-level design

An App service that needs an ID asks an ID generator. Each generator builds a 64-bit number locally from three things: the current time in milliseconds, its own worker number, and a counter that resets every millisecond. No generator talks to another to make an ID.

The only shared piece is the Worker registry. When a generator starts, it takes a lease on a free worker number, which guarantees no two live generators share one. The generator reads the current time from the Time source, an NTP-synced clock, and refuses to issue IDs if the clock is behind where it was before. A Skew alert channel tells people when that happens.

The app then stores its row in the Database under that ID. Because the time bits come first, new IDs are larger than old ones, so inserts land at the end of the index instead of scattering across it.

How a request flows

Create a new ID

1. The app service asks a nearby generator for an ID.
2. The generator reads the clock, in milliseconds since a custom start date.
3. If this is the same millisecond as the last ID, the sequence goes up by one. If it is a later one, the sequence resets to zero.
4. The generator packs time, worker number and sequence into one 64-bit number and returns it.
5. The app stores its new row under that ID. Rows sort by ID, which is roughly by creation time.

A generator starts

1. On startup the generator asks the registry for a free worker number and takes a lease on it.
2. The registry grants one number with a lease that must be renewed every few seconds.
3. The generator reads the clock and compares it with the last timestamp it saved before stopping.
4. If the clock is ahead of that saved time, the generator begins to serve IDs. Otherwise it waits.

The clock moves backwards

1. The app service asks a generator for an ID, as usual.
2. The generator reads the clock.
3. The time is earlier than the last ID's timestamp, so issuing now could repeat an ID.
4. The generator raises a skew alert, then waits out a small step back or stops issuing for a large one.
5. The app gets an error and retries on another generator, which has its own worker number.

Deep dive: the 64-bit layout and its limits

A time-ordered ID packs three fields into one 64-bit number, most significant bits first:

• 1 bit, unused. It keeps the number positive when a language or database reads it as a signed integer.
• 41 bits of timestamp. Milliseconds since a custom epoch.
• 10 bits of worker number. Which generator made it.
• 12 bits of sequence. A counter that resets every millisecond.

Each field sets a limit. 41 bits hold 2^41 milliseconds, about 69.7 years. Pick the epoch as your launch date, not 1970. Starting in 1970 would run out around the year 2039. Ten worker bits allow 1,024 generators, and many teams split them into a data centre part and a machine part. Twelve sequence bits allow 4,096 IDs per millisecond per generator. If a generator uses them all inside one millisecond, it waits for the next millisecond.

Because the timestamp is in the high bits, a larger ID is almost always a later ID. Two different generators in the same millisecond can produce IDs in either order, so say 'roughly sorted' and not 'strictly ordered'. That is enough to make database inserts land at the end of the index instead of splitting pages all over it.

One practical trap: JavaScript numbers are accurate only up to 2^53, so a 64-bit ID loses its low bits when parsed from JSON. Send IDs to browsers as strings.

If your numbers change, shift bits between fields. A smaller fleet and a busier service might trade worker bits for sequence bits. Document the layout, because every ID ever made depends on it.

Deep dive: a clock that moves backwards

The danger is simple. If the clock goes back, the generator may reach a millisecond it has already used. With the same worker number and a sequence that restarts at zero, it would then repeat an ID. Clocks do go back: a time-sync daemon may step the clock, a virtual machine may be paused and resumed, and a leap second may be handled badly.

The generator defends itself in three layers.

1. Remember the last timestamp. Before issuing, compare the clock with the last timestamp used. If the clock is not behind, carry on.
2. Handle a small step back by waiting. If the clock is a few milliseconds behind, sleep until it catches up, then continue. Callers see a tiny delay and no error.
3. Refuse a large step back. If the gap is more than a threshold you choose, stop issuing IDs from this generator, raise an alert, and return errors so callers use another generator. Another worker number cannot clash.

A restart is the same problem in disguise. Save the highest timestamp to durable storage every second or so, and on startup refuse to issue until the clock is past that saved value. Otherwise a machine that boots with a wrong clock could reuse a whole range.

Prevention helps too. Configure the sync daemon to adjust the clock gradually (slewing) rather than jump it. Alert on drift above a few milliseconds, and take a bad machine out of service before it hits a limit. Use the system's monotonic clock to measure how long you waited, never the wall clock.

Deep dive: worker numbers, and the alternatives

Two live generators with the same worker number can issue the same ID in the same millisecond. So worker numbers must be unique among live generators. Hard-coding them in config works for a fixed fleet but is fragile when machines autoscale or are replaced.

A better way is leases. A small, strongly consistent registry hands out the lowest free number with a time limit, and the generator renews it by heartbeat. If it cannot renew in time, it stops issuing IDs. The registry does not give that number to anyone else until the lease has expired plus a safety margin that is longer than the worst clock error. Only generator start-up touches the registry, so it is never on the hot path of an ID.

Here are the alternatives, and when each is right.

• UUIDv4. 122 random bits in 128. It needs no coordination and clashes are astronomically unlikely. But it is twice the size, not sortable, and random inserts scatter across a B-tree index, which slows writes at scale.
• UUIDv7. A 48-bit millisecond timestamp followed by random bits. It sorts by time like our layout and needs no worker registry, at 128 bits.
• A database ticket server. One table with an auto-increment column hands out numbers. It is simple and strictly increasing, but it is a bottleneck and a single point of failure. Two servers giving odd and even numbers fix the failure but lose the global order.

My choice depends on one question. If 128 bits are acceptable, UUIDv7 gives sorted IDs with the least moving parts. If the ID must fit in 64 bits, as with an integer key that is passed everywhere, use the time-ordered layout with leased workers.

Trade-offs

• ID format: 64-bit time, worker and sequence over UUIDv4. It is half the size and sorts by time, so inserts append to the index. The cost is a worker registry and care with clocks.
• Worker numbers: Leased from a registry over Fixed numbers in each machine's config. Leases survive autoscaling and replaced machines with no human step. The cost is one more small, consistent service that start-up depends on.
• A clock that goes backwards: Wait for a small step, refuse a large one over Keep issuing from the last timestamp. Refusing is always safe, since other generators carry on. Borrowing from the last timestamp can run the sequence out and so repeat IDs.
• Ordering: Roughly sorted by time over Strict global order from one sequencer. No central bottleneck and generators work independently. The cost is that IDs from two generators in the same millisecond can be in either order.

Common follow-up questions

Can two IDs from different generators arrive out of order?
Yes. Inside one millisecond, any generator may be first, and clocks differ by a little. The promise is rough ordering, which is enough for index locality. If you need strict ordering for a business rule, store a separate sequence or use a single-writer log for that case.

What if you need more than 1,024 generators?
Move bits. Take them from the sequence, since 4,096 per millisecond is far more than most generators need, and give them to the worker field. Or coarsen the timestamp to 10 ms units, which makes the 41 bits last ten times longer and frees bits for other fields.

Can users guess the next ID?
Time-based IDs are not secret. They show roughly when a row was made, and counting them estimates volume. Keep them internal, and expose a separate random token for anything public, such as a share link.

What if a generator uses all 4,096 sequence values within one millisecond?
It waits until the next millisecond and starts the sequence at zero. That means one generator would have to produce over four million IDs a second to hit the limit. If you ever do, add generators rather than bits.