Design a unique ID generator
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.
Before you scroll: why not just use a UUID v4? Give one reason that is about the database rather than about collisions.
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.
The numbers
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.
The layout
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 design
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.
Deep dive one: 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.
Deep dive two: 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.
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?
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.
