Design a unique ID generator

Every row in a database needs a name nobody else has: order 1029, user 88, message 7731. That name is its id, and the column that holds it is the primary key. On one database this is easy, because the database counts 1, 2, 3 for you. Spread the writes across many machines and nobody is counting any more.

Then one day two rows get the same id. Nothing crashes. The write succeeds, the API returns 200, and one record quietly overwrites the other. You find out weeks later when a customer says an order disappeared, and by then the evidence is gone. Watch how this design makes one id without ever asking another machine.

This question 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. That is why interviewers like it.

A few words first, because the whole page uses them:

• A bit is a single 0 or 1. A 64 bit number is the size a database calls bigint.
• A timestamp here is a count of milliseconds since some starting moment, called the epoch.
• Sortable means that if you sort ids from small to large, you also get them in roughly the order they were created.

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.

What you are building#

Back of the envelope#

If this kind of estimate is new, the back of the envelope chapter walks through the method. Move the sliders and watch the middle row.

That middle row is the one people miss. At 10,000 writes a second across 64 hosts, each host makes about 0.16 ids per millisecond. The counter bits exist for bursts, not for steady traffic.

Step 2: Propose the high level design#

Where an id comes from#

Before the bit layout, it helps to see why the obvious answers fail. Each one is a real thing teams ship, and each one breaks at a specific moment.

The first rung is why this question exists at all. Sharding splits one database into many, and the auto increment counter does not survive the split, as the partitioning chapter points out.

Think of shop counters printing receipts. If every receipt number reads "10:42:05, counter 3, receipt 17", no counter ever needs to ask another what number comes next, and two receipts can only clash if two counters both think they are counter 3. Hold on to that last part: it is the weak point of the whole design.

The contract, in bits#

There is no REST API here. The contract is the bit layout, and every other system will depend on it forever, so it goes on the whiteboard first.

Here is one id built by hand, with the standard split of 41 bits of time, 10 bits of machine and 12 bits of counter. Say the time is 1,000 milliseconds after our epoch, the machine is 7, and this is the third id in that millisecond, so the counter is 2.

• Time goes in the highest bits: 1,000 shifted left by 22 places is 1,000 × 4,194,304 = 4,194,304,000.
• Machine goes in the middle: 7 shifted left by 12 places is 7 × 4,096 = 28,672.
• Counter goes at the end: 2.
• Add them: 4,194,332,674.

Because time sits in the highest bits, any id made one millisecond later is bigger, whatever machine made it. That is all "sortable" means here. Drag the slider to see the trade between machines and counter.

The sign bit stays at zero on purpose. Java's long is signed, and many systems downstream treat the id as a signed number. Setting the top bit would make ids negative, and negative ids break sort order in exactly the place you relied on it.

The epoch is custom, not 1970. With a 2010 epoch, 41 bits of milliseconds lasts until about 2079. Counting from 1970, more than half of those years would already be spent.

The whole system on one whiteboard#

Figure 1 is the same path as the picture at the top, with the alarms added.

Walking Figure 1:

1. A write arrives at any instance. There are 64 of them and they do not talk to each other. Stateless means an instance keeps nothing another instance would need, so any of them can take any request.
2. The instance asks its own in-process generator for an id. This is a function call, not a request over the network.
3. The generator reads the clock and compares it with the last timestamp it issued. If time has gone backwards it refuses. That is the first deep dive.
4. 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 (network time protocol, the service that keeps a machine's clock in line with real time) keeps the clock honest. Both sit off the write path, and both are where this design goes wrong when it goes wrong.

There is no id service in Figure 1, and that is worth saying out loud. A central id service would put a network call inside every write, and it would need to be more available than the database it feeds.

Step 3: Design deep dive#

The clock is not a monotonic counter#

Monotonic means "only ever goes up". Snowflake swaps coordination for trust in the local clock: time only moves forward, so ids only move forward. Except a machine's clock does not only move forward. It drifts, and when NTP corrects it, the correction can jump it backwards. Time and clocks shows how far off a clock can be. Step through what that does to an id.

Snowflake implementations that quietly carry on are the ones that produce the duplicate nobody notices for a month. Name both defences in the interview: slew to make it rare, and the guard to make it safe.

What is actually wrong with a UUID#

UUID v4 is 128 bits, 122 of them random. Collisions are genuinely not the problem: you would need to generate billions of them before one becomes likely. The problem is what random ids do to the database.

A database index on the id works like a phone book kept in sorted order. In most databases it is a B-tree: sorted pages of keys, with the busy pages kept in memory and the rest on disk. (Indexes and storage engines explain it from the start.)

• Time ordered ids are like new names that always sort to the end of the phone book. Every new row lands on the last page, which is already in memory, next to the row inserted a millisecond ago.
• Random ids are like new names that land anywhere. Every new row goes to a random page, which usually has to be read from disk, changed, and written back. At high write rates the same insert rate causes far more disk work, the index fragments, and the part of it you use stops fitting in memory.

There is also the width. A UUID stored as text is 36 bytes, or 16 as raw binary, against 8 for a bigint, and that cost repeats in every secondary index and every foreign key.

UUID v7 fixes the ordering by putting a millisecond timestamp in its first 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.

Where the machine id comes from#

The whole scheme is only unique if no two live processes hold the same machine id. Remember the receipt counters: two counters both calling themselves counter 3 is the only way receipts clash. Getting this right is not free.

The last sentence of that rung is the one people forget. A lease can expire during a network partition while the process keeps running and thinks it is fine. If it keeps generating, and the number has gone to someone else, both make identical ids. How leases expire, and why the holder does not know it lost one, is in leader election and locks.

Break it#

The dial here is not traffic. It is the health of the two things this design cannot avoid: the clock and the lease.

Both red states produce duplicate ids, and neither produces an error by itself. That is what makes this design worth being careful with: it fails silently, and in both cases the safe move is to stop, not to continue.

Trade-offs#

The level bar#

One moment from this round, answered three ways. Pick the one you think is staff level before the labels appear. (What changes at senior and staff explains the gap.)

Then run the question cold, with a 45 minute timer and no notes, and score the run on the five things this question is really testing.

Interview replay#

Checkpoint#