Unique IDs at scale

  • Lesson 15 of 40
  • 13 min
  • Intermediate
  • 12 steps

With a single database, a counter is enough. Once many machines write at the same time, picking the id stops being a detail.

Repeated IDs
0
Bits per ID
64
Calls per 1000 inserts
0
Server 1Server 1Server 2Server 2shard Ashard BTicketserverTicket serverprimary-key indexcompetitornext id: 3813order 3812 · Lucíaorder 3812 · Tomásnext id: 4001one more trip per insertblock 4001–5000block 5001–6000next block: 60013b9e2f71-c0a4-…b7d05e3a-61f2-…UUID v43b9e2f71-c0a4-4d18-9e65-7a2c41f08bd36 bitsversion and variant122 bitsrandom16 bytestwice 64 bitstotal128 bits3b9e2f71-c0a4-…b7d05e3a-61f2-…pages in id orderWhich page does the new row go to?counter idalways the lastrandom idany page at allcold pagessplits, bloat01a1f874-69f4-7…01a1f874-69f5-7…inserts at the endUUID v701a1f874-69f4-7c3e-a51d-9e2b07f4c86148 bitsms since 19706 bitsversion and variant74 bitsrandomtotal128 bitsmachine 1machine 2One 64-bit id1 bitsignalways 041 bitsmilliseconds≈ 69 years10 bitsmachine id1024 machines12 bitssequence4096 per mstime · machine · sequencetotal64 bitsclock −1.5 s · waitingmachine 2Server 1's generatorlast id issued10:15:42.800clock now reads10:15:41.300wait 1.5 s, then go onnever reuses a millisecondmachine 1machine 2reads ids in URLsReading the ids (example)Mon 10:00/orders/20410Tue 10:00/orders/20722≈ 312 orders a daypublic idord_Q7m2Xk9aTemachine 1machine 2Size, order and dependencyDB counter64 bits · orderedone DBblocks64 bits · roughlyticket serviceUUID v4128 bits · unorderednothingUUID v7128 bits · ordereda clockSnowflake-style64 bits · orderedmachine id and clockmachine 1machine 2no duplicates
  • request
  • response

Step 1 of 12

Concept

Every row needs its name

An order, a user, a payment: every row carries an identifier that must never repeat. Other tables store it to point at that row, it shows up in URLs and someone in support reads it out over the phone.

With a single database this comes for free: an auto-increment column (AUTO_INCREMENT, SERIAL or IDENTITY) hands out 3810, 3811, 3812… and the database itself makes sure none is ever repeated.

Step 2 of 12

Problem

Two shards, two counters

The orders table grows and gets split into two shards. Each shard is an independent database with its own counter, and both have just handed out 3812.

Now two different orders share an id. A link to /orders/3812, a cache entry or a refund could refer to either one. And if you ever merge the shards or split them again, the rows collide.

What changed

  • Shard B, with its own counter
  • Order 3812 exists twice

Step 3 of 12

Solution

Option 1: one shared counter

Take the counter out of the shards and into a small service that does one thing: hand out the next number. That is a ticket server. Before every insert, the app server asks it for an id.

Ids are unique again and still ordered by time. In exchange, every insert adds one more network round trip, and if the ticket server goes down, nobody can create anything.

What changed

  • Ticket server
  • Every insert asks for its id first
  • A new single point of failure

Step 4 of 12

Technique

Hand out blocks, not single numbers

Ask less often. Each app server reserves a whole block at once, say 1000 ids, and hands them out from memory. That is one round trip per 1000 inserts, and if the ticket server goes down, each server keeps going until its block runs out.

The price: ids no longer follow creation order across servers (server 2's 5003 may be older than server 1's 4700), and when a server restarts, the numbers it had not used from its block are lost.

What changed

  • Each server reserves 1000 ids per call
  • 1 call per 1000 inserts
  • Strict time order across servers

Step 5 of 12

Solution

Option 2: a number nobody else will pick

Or stop coordinating. A version 4 UUID has 128 bits, 122 of them random. Any server, phone or script can generate one without asking anybody.

Can two come out the same? In theory, yes. In practice, to reach a 50 % chance of a single repeat you would have to generate a billion every second for about 86 years.

What changed

  • Ticket server
  • Each server generates random 128-bit ids
  • Zero coordination

Step 6 of 12

Problem

Random ids inside the index

Inside each shard, the primary key lives in a B-tree sorted by id. With a counter, every new row lands on the last page, which is always in memory. With a random id, it lands on any page at all.

Once the index no longer fits in memory, many inserts first have to read a page from disk, and pages keep splitting all over the tree. Inserts can become several times slower and the index fills up with half-empty pages.

What changed

  • Inside one shard: the primary-key index
  • Inserts spread across every page

Step 7 of 12

Solution

Put the time in front

Keep the randomness, but start with the time. A version 7 UUID spends its first 48 bits on milliseconds since 1970 and fills almost all the rest with random bits.

New ids are larger than old ones, so inserts go back to the end of the index. They still need no coordination, and sorting by id means sorting by creation time again.

What changed

  • UUID v4 → UUID v7
  • Inserts go back to the last page

Step 8 of 12

Solution

Option 3: time, machine and sequence in 64 bits

If you need 64-bit ids, ordered by time and generated at a high rate with no central counter, pack three fields into a single number: that is the idea behind Snowflake-style IDs.

A millisecond timestamp, the id of the machine that generates it and a sequence that counts within each millisecond. Two machines never collide because their machine ids differ; one machine never repeats itself thanks to the sequence.

What changed

  • UUIDs → 64-bit Snowflake-style ids
  • Every server gets a machine id at startup

Step 9 of 12

Problem

The clock steps back

These ids are only unique if a machine's clock never repeats a millisecond. But clocks get corrected: time sync notices server 1 is 1.5 s fast and sets it back. For 1.5 s it would issue ids with times it already used, that is, duplicates.

The defence is simple: the generator remembers the last timestamp it issued. If the clock reads an earlier time, it waits (or refuses to issue ids) until time has passed it.

What changed

  • Server 1's clock steps back 1.5 s
  • The generator waits until it passes its last stamp
  • No duplicates: that server pauses inserts for 1.5 s

Step 10 of 12

Trade-off

What an id says about you

Ids end up in URLs, and people read them. A competitor places an order on Monday (/orders/20410) and another on Tuesday (/orders/20722): now they know you get about 312 orders a day.

Sequential ids are also easy to walk: change /invoices/20410 to /invoices/20411 and see what comes back. And time-based ids reveal the exact moment each thing was created.

What changed

  • A competitor reading ids from URLs
  • Random public ids; internal keys stay ordered

Step 11 of 12

Trade-off

Which id for which job

A single database? Use its counter. Many writers with nothing shared? UUID v7. Compact numeric ids at a very high rate? Snowflake-style.

If you need short numbers and already run a reliable central service, blocks from a ticket server work well too.

Step 12 of 12

Summary

Summary

A per-database counter stops being unique as soon as you split the data into shards.

A ticket server fixes it; handing out blocks removes the extra round trip on every insert.

UUID v4 needs nobody, but scatters inserts across the index; UUID v7 puts the time in front to avoid it.

Snowflake-style: time, machine and sequence in 64 bits; watch for clocks that step back.

Ids give away volume and dates. Never use them as access control.

You will learn

  • See why the database counter breaks when data is split
  • Use a ticket server and hand out blocks of ids
  • Understand UUID v4 and what random keys do to an index
  • Generate time-ordered ids: UUID v7 and Snowflake-style IDs
  • Guard against clocks that step back and ids that give things away