Design a unique ID generator
Read firstSharding
Two rows in a distributed system end up with the same id. Nothing crashes. The write succeeds, the API returns 200, and one of the two records quietly overwrites the other. You find out weeks later when a customer says an order disappeared, and by then the evidence is gone.
That is why this question gets asked. It is small enough to answer completely in twenty minutes, and every part of the answer is a real decision with a real failure attached to it.
Step 1: Understand the problem#
Every answer here is a number, and every number closes off a design. Ask before you draw a single bit.
| You ask | They say | What it settles |
|---|---|---|
| How many ids a second, at peak, across how many hosts? | About 10,000 a second across 64 hosts, with room to grow. | How many bits the sequence counter needs. At this rate each host makes well under one id per millisecond, so the sequence is there for bursts, not for throughput. |
| Do the ids have to sort by creation time? | Roughly. Range scans and time ordered pagination depend on it. | A timestamp in the high bits, and it rules out UUID v4 immediately. It also means you must say "roughly" out loud, because clocks on different hosts disagree. |
| How wide can an id be? | 64 bits. It has to fit a bigint. | The entire budget. Everything from here is dividing 64 bits between time, machine and counter, and every bit one field takes is a bit another loses. |
| Are these ids ever visible to users? | Yes, in URLs. | Two consequences. Consecutive ids leak your volume to anyone who watches, and you cannot use them as a security boundary. If they had to be unguessable, this design is the wrong one and you need random bits instead. |
| Can a generator call another service to get an id? | No. This sits inside every write. | No central id service, so ids are made in the application process. Coordination is allowed at startup and nowhere else. |
| How long does the scheme have to last? | Decades. Nobody wants to migrate primary keys. | 41 bits of milliseconds from a custom epoch, not the Unix epoch. Starting the clock on deploy day buys back every year since 1970 that you were never going to use. |
What you are building#
- Generate ids that are unique across the whole fleet. Without coordination on the hot path.
- Roughly sortable by creation time. So a range scan and an index on the id both do useful work.
- 64 bits, so it fits a bigint. Half the storage of a UUID and it indexes far better.
- 10,000 ids a second at peak, with headroom.
- Under 1ms to generate, because this sits inside every write.
- No single point of failure on the generation path.
- Ids must not be guessable in sequence if they are ever exposed publicly.
- Short human friendly codes. Different problem, covered in the URL shortener page.
- Cryptographically random tokens for sessions or password resets. Those need real entropy and must never be time ordered.
- Global ordering guarantees. These ids are roughly ordered, not a consensus sequence, and pretending otherwise causes bugs.
Back of the envelope#
A millisecond timestamp needs 41 bits to cover 50 years. Everything left over is split between naming the host and counting within a millisecond, and the numbers above show the counter needs very few of those bits.
That last point is the one people miss. At 10,000 writes a second across 64 hosts, each host is producing well under one id per millisecond. The sequence bits exist for bursts, not for sustained throughput.
Step 2: Propose the high level design#
The contract, in bits#
There is no REST API here. The contract is the bit layout, and it is what every other system will depend on forever, so it is the thing to get on the whiteboard first.
A 64 bit id is a bit budget, and every bit you spend on one field is a bit the others do not get. This is Twitter's Snowflake scheme, which almost everyone copies.
Drag the slider and watch the trade.
The default 10 and 12 split is 1,024 machines and 4,096 ids per machine per millisecond, which is four million ids a second per host. That is the standard for a reason.
The sign bit is left at zero on purpose. Java's long is signed, and a lot of systems
downstream will treat the id as a signed integer. Setting the top bit gives them negative
ids, and negative ids break sort order in exactly the place you were relying on it.
The epoch is custom, not 1970. Starting the clock at the day you deploy buys back every year since 1970 that you were never going to use. With a 2010 epoch, 41 bits lasts until about 2079. With the Unix epoch it would already be more than half spent.
The scheme is only unique if no two live processes hold the same machine id, and that is not free. Hardcoding it in config breaks the first time someone copies a deployment. Deriving it from the IP breaks when addresses get reused. The usual answer is a short-lived lease from ZooKeeper, etcd or a database row that the process renews, so a dead host's id returns to the pool only after its lease expires.
The whole system on one whiteboard#
Walking Figure 1:
- A write arrives at any instance. There are 64 of them and they do not talk to each other.
- The instance asks its own in-process generator for an id. This is a function call, not a request.
- The generator reads the clock and compares it with the last timestamp it issued. If time has gone backwards it refuses, which is the subject of the first deep dive.
- The id goes into the insert. Total added latency is a few hundred nanoseconds.
The two dashed arrows are the only coordination in the design. A machine id is leased at startup and renewed in the background, and NTP keeps the clock honest. Both are off the write path, and both are where this design goes wrong when it goes wrong.
There is no id service in Figure 1. That is the point of the design, and it is worth saying out loud: a central id service would put a network call inside every write, and inherit an availability requirement stricter than the database it feeds.
Two things in Figure 1 can hand out a duplicate id without raising a single error. Which two, and what would you do about each?
Step 3: Design deep dive#
The clock is not a monotonic counter#
Snowflake trades coordination for a hard dependency on the local clock. Time only moves forward, so ids only move forward. Except time does not only move forward.
There are two defences and you should name both.
Configure NTP to slew rather than step, so corrections are applied by running the clock slightly slow until it catches up, instead of jumping. This makes backwards movement rare rather than routine.
Then handle it anyway. Keep the last timestamp you issued. If the clock reads earlier than that, do not generate. Either wait until the clock passes the last timestamp, which is correct and costs latency, or refuse and fail the request loudly. What you must not do is generate anyway and hope. Snowflake implementations that quietly carry on are the ones that produce the duplicate nobody notices for a month.
What is actually wrong with a UUID#
UUID v4 is 122 random bits. Collisions are genuinely not the problem: you would need to generate billions of them before a collision becomes likely. The problem is what random ids do to a database.
A B-tree index keeps entries in sorted order. Insert with a time ordered key and every new row lands at the right hand edge of the tree, in a page that is already in memory, next to the row inserted a millisecond ago. Insert with a random key and every new row lands in a random page, which usually has to be read from disk first, modified, and written back. At scale the difference is not subtle: the same insert rate produces far more disk activity, the index fragments, and the working set stops fitting in memory.
There is also the width. A UUID stored as a 36 character string is 36 bytes, or 16 as raw binary, against 8 for a bigint. That cost repeats in every secondary index and every foreign key.
UUID v7 fixes the ordering by putting a millisecond timestamp in the high bits, which makes it a reasonable choice when you want a standard format and do not want to run a machine id lease. It is still 128 bits.
Break it#
The dial here is not traffic. It is the health of the one dependency this design cannot avoid.
Read every step as text
- healthy · Healthy. NTP is slewing, the lease is renewed, ids increase. Nothing in this picture makes a network call to generate an id.
- burst · Degraded. A batch import asks for more than 4,096 ids inside one millisecond. The sequence is exhausted, so the generator blocks until the clock ticks. Correct behaviour, but it shows up as a latency spike and it is worth alerting on.
- clock skew · Degraded. This host is 30ms ahead of the rest of the fleet. Ids from here sort slightly ahead of ids generated later elsewhere. Nothing is broken, but "roughly sortable" now means roughly, and any logic that assumes strict ordering across hosts is already wrong.
- clock steps back · Down. The clock moved backwards past a timestamp already used. A generator that keeps going emits a duplicate id. A generator that remembers its last timestamp refuses to emit and either waits or errors, which is the only safe answer.
- lease lost · Down. The lease expired during a network partition and another host was handed machine id 7. Two live processes now share a machine id, so they will produce identical ids within the same millisecond. The process must stop generating the moment it cannot confirm its lease.
Both of the red states produce duplicate ids, and neither of them produces an error by itself. That is what makes this design worth being careful with: its failure mode is silent, and the safe behaviour in both cases is to stop rather than to continue.
Trade-offs#
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Snowflake style 64 bit ids | No coordination on the write path, time sortable, half the width of a UUID and far better index locality. | A machine id to allocate and a hard dependency on a well behaved clock. | High write volume where the id is a primary key and ordering earns its keep. |
| UUID v4 | Zero infrastructure, generate anywhere including the client, no coordination of any kind. | 128 bits, and random insert order that fragments B-tree indexes and blows up the working set. | Low write volume, or ids created offline on a device, or when the id is not the clustered key. |
| UUID v7 | A standard format with a timestamp prefix, so it sorts and indexes almost as well as Snowflake, with no machine id to lease. | Still 128 bits, and still leaks creation time. | You want time ordering without running a coordination service. Often the pragmatic middle. |
| Database ticket server | Trivially correct, strictly increasing, no clock involved. | A network round trip per id and a single point of failure, unless you hand out ranges, which brings back gaps. | Modest scale where correctness matters more than throughput, or as the id source behind a range allocator. |
Interview replay#
Checkpoint#
1. What is the strongest argument against UUID v4 as a primary key at high write volume?
2. The machine id lease expires during a network partition while the process keeps serving traffic. What must the process do?
3. You move machine id from 10 bits to 14 bits, keeping the layout at 64 bits. What did you just give up?
- 64 bits: 1 sign, 41 time, 10 machine, 12 sequence. The Snowflake split everyone copies.
- 41 bits of milliseconds is 69 years from your own epoch, which is why you never start at 1970.
- 1,024 machines, 4,096 ids per machine per millisecond. Four million a second per host.
- 10,000 ids a second across 64 hosts is under one per millisecond each. The sequence bits are for bursts, not throughput.
I would use a Snowflake style 64 bit id: a millisecond timestamp against a custom epoch in the high bits, then a machine id, then a sequence counter for ids created within the same millisecond. It generates in process with no network call, so it does not put a dependency inside every write, and being time ordered means inserts land at the right edge of the index instead of scattering across it the way UUID v4 does. The machine id comes from a lease in ZooKeeper or etcd, and the process must stop generating if it cannot renew that lease. The one real risk is the clock: I would set NTP to slew rather than step, track the last timestamp issued, and refuse to generate if the clock ever reads earlier than that, because the failure mode here is a duplicate primary key with no error next to it.