Designing a Unique ID Generator

Every row needs an id. On one database that is a solved problem — the database hands you one. Across many machines it becomes a genuine design question, and it is a favourite interview warm-up precisely because the whole thing turns on a single trade-off you can state in one sentence.

That sentence is: sortability versus coordination. Everything below is a different point on that line.

What you are actually being asked for

“Unique” is the easy requirement. The interesting ones are the others, and which of them you need decides the answer:

Notice that several conflict. Sortable-by-time means the id leaks when the row was created. Unguessable means not sortable, unless you work at it. Small fights unguessable directly — there is no such thing as a short unpredictable id.

So the first move in an interview is to ask which of these actually matter, exactly as in the framework post.

Auto-increment

Start here, because it is what you get for free and because knowing precisely when it stops working is most of the answer.

The database keeps a counter. It is small, sorted, and free.

CREATE TABLE bookings (
    id BIGSERIAL PRIMARY KEY   -- 8 bytes, monotonic, allocated by Postgres
);

It fails in exactly two situations, and both are worth naming.

Sharding. Each shard has its own counter, so every shard produces id 1, 2, 3. The classic patch is to give each shard a different starting point and step — shard 0 does 1, 5, 9; shard 1 does 2, 6, 10 — which works and then makes adding a fifth shard a migration.

Exposure. A sequential id in a URL tells the world two things you did not intend to publish:

   /bookings/1042        someone signs up, gets 1042
   /bookings/1109        a week later, 1109
                         -> you have 67 bookings a week

   and /bookings/1041, /bookings/1040, ... are all valid ids to try.

That second line is the security problem. Guessable identifiers turn any authorisation weakness into a bulk extraction, because there is no discovery step. It is why the Airbnb post insists on 404 rather than 403 for foreign-owned resources: a 403 confirms the id exists, and confirming existence on an enumerable id is a slow read of your entire table.

UUIDs

128 random bits. No coordination at all — any machine generates one alone, and collisions are not a practical concern.

   v4  550e8400-e29b-41d4-a716-446655440000
       122 random bits. Unguessable. Completely unordered.

   v7  0190b3f5-4a2c-7000-8f1e-3c9a5b7d2e01
       └─ 48-bit millisecond timestamp ─┘ + random
       Time-ordered AND unguessable-enough.

The difference between them matters more than it looks, and it is about how databases store indexes.

A B-tree index is kept sorted. Inserting sequential keys always appends to the rightmost page, which stays in memory and packs full. Inserting random keys writes to a random page every time — so the index cannot stay cached, pages split half-empty, and the index grows larger and slower than it needs to be.

   sequential inserts        random inserts (UUIDv4)

   [..][..][..][XX]          [X.][.X][..][X.][.X][..]
                 ^                ^     ^        ^
        one hot page,        writes land anywhere;
        always cached        the whole index must stay cached
                             or every insert is a disk read

On a large table that is a real, measurable difference in write throughput. UUIDv7 was standardised specifically to fix it: a millisecond timestamp in the high bits makes the values roughly increasing, so inserts are near-sequential again while the low bits keep them unguessable. If you are choosing a UUID version today, choose v7.

The other cost is size. 16 bytes against 8, in every index and every foreign key — and 36 bytes if stored as text, which is a mistake worth avoiding explicitly.

How unlikely is a collision, really?

Worth being able to answer, because “UUIDs are unique” is a claim and not a guarantee — they are random, so collision is merely improbable.

UUIDv4 has 122 random bits. The birthday paradox says collisions become likely at roughly the square root of the space, which is 2⁶¹:

   2^61  ≈  2.3 quintillion ids before a 50% chance of ONE collision

   At a billion ids per second, that is ~73 years.
   At any realistic rate, it will not happen.

So the honest statement is “collision is not a practical concern” rather than “collision is impossible”, and the difference matters in one place: the random number source. UUIDv4 is only that unlikely if the bits are genuinely unpredictable. Seeded from a poor source — a fresh container with no entropy, a language default that is not cryptographically secure — two machines can generate the same sequence, and then collisions arrive immediately rather than never.

The practical consequence is small but real: use the platform’s UUID function rather than building one from a general-purpose random generator, and keep the unique constraint on the column regardless. It costs nothing and it turns an astronomically unlikely event into a caught error rather than silent data corruption.

Both, which is usually the answer

The requirements conflict, so stop trying to satisfy them with one value. StayHub gives every row two ids, each doing the job it is good at:

class PublicIdMixin:
    """A UUID the API exposes, alongside the BIGINT primary key the database joins on.

    Two ids per row is deliberate. Integers make fast, small foreign keys; a sequential integer in
    a URL also tells the world how many rows you have and invites `/properties/1`, `/properties/2`.
    The UUID is the only id that ever leaves the process.
    """

    public_id: Mapped[uuid.UUID] = mapped_column(
        PGUUID(as_uuid=True), default=uuid.uuid4, unique=True, nullable=False, index=True
    )

The internal BIGINT is what foreign keys reference and what joins run on: 8 bytes, sequential, cache-friendly. The public_id UUID is the only id that ever appears in a URL, a JSON response or a log line.

   INSIDE                            OUTSIDE
   bookings.property_id -> 7         /properties/89c69134-4b96-49ee-8329-...
   8 bytes, joins fast               16 bytes, unguessable, opaque
   never leaves the process          never used as a foreign key

The costs are honest: every table carries a second unique index, and every lookup by public id is one index hop rather than a direct primary-key hit. In exchange, enumeration is impossible, your row counts are private, and internal ids can be renumbered during a migration without breaking a single external reference.

This pattern is worth having in your pocket, because “which id do you expose?” is a question that comes up in most schema discussions and most people have not separated the two concerns.

Sortable and unguessable at once

The conflict at the top of this post has a partial resolution worth knowing, because interviewers like it: you can have time-ordering internally and opacity externally by encrypting the id on the way out.

   stored:   1042              sequential, small, sortable
   exposed:  "k7Bq2xNfR4"      format-preserving encryption of 1042

   decrypt on the way in -> 1042
   nobody can walk the sequence without the key

The database keeps every benefit of a sequential key, and the outside world sees something it cannot iterate. The costs are a key to manage — rotating it invalidates every URL ever issued — and a layer of encoding in every request path.

It is genuinely used, and it is more machinery than most systems need. The two-id approach above buys the same external property with an index lookup instead of a key-management problem, which is usually the better trade.

Ticket server

One central service hands out ids. Everyone asks it.

Simple, and it gives you strictly increasing 64-bit ids with no coordination logic anywhere else. The problems are the obvious ones: it is a single point of failure, and it adds a network round trip to every insert.

The mitigation is batching, and it is what makes the approach viable: each server requests a block of a thousand ids and hands them out locally, so the round trip happens once per thousand rows rather than once per row. The cost is gaps in the sequence when a server restarts holding unused ids — which matters only if you were treating the id as a count, and you should not be.

Batching, concretely

   server A: "give me 1000 ids"  ──> ticket server ──> 1000-1999
   server B: "give me 1000 ids"  ──> ticket server ──> 2000-2999

   Both now hand out ids locally, no network call per row.
   A restarts having used 400 -> 600 ids are lost. Nobody cares.

The block size is the dial. Larger blocks mean fewer round trips and bigger gaps on restart; smaller blocks the reverse. A thousand is a sensible default for most write rates, and the “nobody cares” is the important part — the moment somebody does care about the gaps, they are using the id as a count, and that is the bug.

Availability is still the weak point. If the ticket server is down, every application server keeps working until its block is exhausted, so the outage is survivable for a while rather than immediate — which is a much better failure mode than one round trip per insert and worth saying out loud.

Snowflake

The answer when you need time-sortable, coordination-free, 64-bit ids at high volume. Twitter published the design and the name stuck.

Pack meaning into the bits instead of asking anyone:

    0 | 41 bits timestamp     | 10 bits machine | 12 bits sequence
    ^   ^                       ^                 ^
    │   ms since a custom       which machine     counter within
    │   epoch (~69 years)       (1024 of them)    the same ms (4096)
    │
    unused, so the number is positive as a signed 64-bit int

   Result: 4,096 ids per millisecond per machine
           = ~4.1 million per second per machine
           and 64 bits total, sortable by time

Three design choices in that layout are worth understanding, because they are what an interviewer will probe.

The custom epoch. Counting milliseconds from your service’s launch rather than from 1970 buys back the decades you would otherwise waste, extending the usable range to roughly 69 years.

The machine id must be assigned, not chosen. Two machines with the same id generating in the same millisecond produce identical ids. In practice this comes from a coordination service or from the orchestrator — and “how do machines get their ids?” is the standard follow-up question.

The sequence handles the same millisecond. 4,096 per machine per millisecond, and if you exhaust it you wait for the next millisecond. That is a hard local ceiling, and it is generous.

The failure everyone forgets

Snowflake assumes time moves forward. It does not always:

   t = 1000   generate ids with timestamp 1000
              NTP corrects the clock backwards
   t = 995    generate ids with timestamp 995

   Those ids were already issued. Collision.

A clock adjustment — NTP correcting drift, a leap second, a VM resuming from a snapshot — can move time backwards. The standard defence is to record the last timestamp used and refuse to generate while the clock is behind it, rather than producing ids you know may be duplicates. Refusing is uncomfortable and it is correct; the alternative is silent corruption that surfaces as a unique-constraint violation somewhere unrelated, weeks later.

This is the detail that separates a memorised description from an understood one, so it is worth volunteering rather than waiting to be asked.

Running out, and other bounds

Worth being able to answer “when does this break?” for each scheme, because the answers differ by many orders of magnitude:

The second row is the one that actually bites people. A 32-bit auto-increment on a high-throughput table — events, log lines, clicks — runs out, and the failure is inserts stopping entirely. Using BIGSERIAL from the start costs four extra bytes per row and removes the problem permanently, which is why StayHub uses it everywhere.

Short codes, which is a different problem

URL shorteners want the opposite of everything above: as few characters as possible, because a human reads them out.

   base62 = [0-9a-zA-Z]

   62^6 =        56 billion
   62^7 =      3.5 trillion
   62^8 =    218 trillion

Two approaches, and they fail differently.

Encode a counter. Take an auto-increment id and write it in base62. Uniqueness comes free from the counter, codes are as short as possible, and no collision check is needed. The cost is that codes are sequential and therefore enumerable — anyone can walk your entire database of links — and they leak your volume.

Generate randomly and check. Pick seven random characters, insert, and let a unique constraint reject a collision; retry on rejection. Unguessable, and the retry loop only terminates quickly while the keyspace is sparse.

Which is where the arithmetic from the estimation post settles it. At 100 million links a day for five years:

   182 billion rows / 3.5 trillion possible codes  =  ~5% occupancy

   -> a random 7-character code collides ~5% of the time
   -> retries terminate almost immediately
   -> 6 characters would be 56 billion possibilities
      against 182 billion rows: impossible.

So: seven characters, generated randomly, with the unique constraint as the guard. That is the concurrency post’s principle again — do not check whether the code is taken and then insert it, just insert it and let the constraint decide.

Gaps are normal, and that is fine

A detail that surprises people the first time they notice it: sequences produce gaps. A transaction that rolls back has already consumed its id and does not give it back.

   INSERT ... -> id 1042    committed
   INSERT ... -> id 1043    ROLLED BACK — 1043 is gone forever
   INSERT ... -> id 1044    committed

This is deliberate. Handing the id back would require the sequence to be transactional, which would mean every insert waiting on a lock held by every other insert — turning your id generator into the bottleneck the concurrency post describes. Sequences are non-transactional on purpose, and gaps are the price.

It only matters if you were using the id as a count, or expecting MAX(id) to equal the number of rows. Neither is safe, and code that relies on either is code that will be wrong the first time a transaction rolls back.

Storing them properly

A practical detail that costs real performance and is easy to get wrong: store a UUID as 16 bytes, not as 36 characters.

-- 16 bytes, compared as an integer pair
public_id UUID NOT NULL UNIQUE

-- 36 bytes, compared character by character, and it accepts '' and 'banana'
public_id VARCHAR(36) NOT NULL UNIQUE

The text version is more than twice the size in the table and in every index, comparisons are slower, and the column no longer rejects nonsense. Databases without a native UUID type usually have a 16-byte binary alternative, which is the right target there.

The same discipline applies at the API boundary: accept and emit the canonical hyphenated string, and parse it into a real UUID type immediately. StayHub does this by typing the route parameter, so a malformed id is a 422 before any code runs rather than a database error later.

Ids in URLs are not access control

The most important caveat in this post, because unguessable ids invite exactly the wrong conclusion.

A UUID makes an id hard to guess. It does not make it secret. Ids leak through browser history, referrer headers, server logs, screenshots, support tickets and shared links. Anyone who has ever legitimately seen a resource keeps its id forever.

So the id is a name, and every request still needs an authorisation check. What the UUID buys is that a missing check is not immediately exploitable at scale — an attacker cannot enumerate. That is defence in depth, and treating it as the defence itself is the mistake the term “security through obscurity” was coined for.

Changing your mind later

The question that decides how much this matters: how expensive is it to switch schemes after launch?

Expensive, and asymmetrically so. Every foreign key holds a copy of the id, so changing the primary key means rewriting every table that references it — plus every cached value, every external system that stored one, and every URL anyone has bookmarked.

   ADD a new id alongside          cheap — one column, one backfill
   CHANGE what URLs expose         expensive — old links break forever
   CHANGE the internal primary key very expensive — every FK, every index

Which suggests the practical strategy: decide the external id carefully and the internal one casually. The internal key can be migrated with effort and nobody outside notices. The external one is a public contract from the first request that returns it.

It also explains why the two-id pattern is worth adopting before you need it. A row with both ids from day one can have its internal key renumbered, its tables re-sharded, even its database replaced, without a single external reference changing — because nothing outside ever knew the internal id existed. Adding a public id to a table whose sequential ids are already in a million URLs is the migration you were trying to avoid.

Choosing

Composite and natural keys

One more option that gets forgotten: sometimes the right id is not generated at all.

A natural key is a value the domain already guarantees is unique — an ISBN, a country code, an email address. A composite key is several columns together, which is the right shape for a join table:

CREATE TABLE property_amenities (
    property_id BIGINT NOT NULL REFERENCES properties(id),
    amenity_id  BIGINT NOT NULL REFERENCES amenities(id),
    PRIMARY KEY (property_id, amenity_id)   -- no surrogate id needed
);

Adding an id BIGSERIAL to that table would buy nothing and cost an index. The composite primary key already enforces the rule that matters — a property cannot list the same amenity twice — which is the concurrency post’s principle appearing yet again: encode the invariant in the key.

The warning about natural keys is that they change. Email addresses get updated, product codes get reissued, and a country splits in two. Anything that can change is a poor primary key, because changing it means updating every foreign key that references it. The conventional advice — surrogate key as the primary key, natural key as a unique constraint beside it — exists because that keeps both properties without the cascade.

The summary

• The trade is sortability against coordination. Everything else follows.
• Random ids hurt B-tree inserts. UUIDv7 exists to fix exactly that; prefer it to v4 for stored keys.
• Two ids per row is often right — a small sequential one inside, an opaque one outside.
• Sequential ids in URLs leak volume and invite enumeration.
• Snowflake trusts the clock, so it must refuse to generate when the clock moves backwards.
• Size short codes with arithmetic, not by preference.
• Let a unique constraint catch collisions. Never check-then-insert.

And the reason this question is a good interview warm-up: it is small enough to answer completely in ten minutes, and it still requires you to ask what the requirements are, do a piece of arithmetic, name a trade-off, and describe a failure mode. That is the whole framework in miniature.

That is the last of the mechanisms. Next, the case studies begin: designing a URL shortener, which uses this post’s arithmetic directly.