Unique IDs

Generate unique IDs across many machines: auto-increment, UUIDs, Snowflake-style time-ordered IDs worked out bit by bit, and range allocation.

16 minLesson 6 of 8
On this page
  1. The idea
  2. The options
  3. A Snowflake-style ID, bit by bit
  4. Numbers worth remembering
  5. In the interview
  6. Common mistakes
  7. What to practise next

An orders table outgrows one database and is split across 4. Each database keeps its own auto-increment counter, so within a day shard 1 and shard 3 have both created order 1001. Support looks up order 1001 and finds two. The analytics job that merges all shards silently overwrites one with the other.

On one machine, unique IDs are free. Across many machines, every server must hand out IDs no other server will ever produce, ideally without asking anyone first.

The idea

There are three ways to avoid a clash without a central counter on every request: make IDs so random that clashes are practically impossible (UUIDs), build each ID from parts that are unique on their own, such as time plus a machine number plus a counter (Snowflake-style), or hand each server a private block of numbers in advance (range allocation).

Beyond uniqueness, ask three questions. Must the ID fit in 64 bits? Should IDs sort by creation time? Is it a problem if outsiders can guess the next ID or count your orders?

The options

ID schemes compared
OptionGood atBad atPick it when
Auto-incrementSmall, simple, perfectly ordered.One database decides every ID. Guessable, and reveals your volume.One database, now and later, and IDs are not shown to users.
UUID v4 (random)No coordination at all; any machine, even a phone, can make one.128 bits. Random order scatters inserts across the whole index, which slows writes on large tables.You need no ordering and 16 bytes per key is fine.
Time-ordered UUID (v7)Starts with a millisecond timestamp, so IDs sort by time and index inserts stay at the end. No machine numbers.Still 128 bits. Leaks creation time.128 bits is fine and you want ordering without any setup.
Snowflake-style 64-bit Usual defaultFits in a 64-bit integer, roughly time-ordered, millions per second per machine.Each generator needs a unique machine number, and it trusts the clock.IDs must be 64-bit and sortable: posts, messages, orders at scale.
Range allocationDense integers; one allocator call per block of, say, 1,000.Needs a highly available allocator. Order is only per block.Short codes and compact numbers, as in a URL shortener.

Range allocation is the simplest to run when you already have a small, reliable allocator: a server asks for "the next 1,000", gets 7,000 to 7,999, and hands them out from memory. If it crashes, the unused numbers are skipped, which is harmless. The allocator is called once per thousand IDs, so it needs high availability but almost no capacity.

How unlikely is a UUID v4 clash? It has 122 random bits. By the birthday estimate, n IDs collide with probability about n² ÷ 2123. For a trillion IDs: (1012)² ÷ (1.06 × 1037) ≈ 10−13. Treat it as never, provided the random generator is a good one.

A Snowflake-style ID, bit by bit

Split a 64-bit integer into fields. Because the timestamp sits in the highest bits, sorting IDs as numbers sorts them by time.

timestamp (ms) machine sequence 1 41 bits 10 bits 12 bits 0 1,000,000,000 37 5
The 64 bits of one ID, with the example worked below. Widths are not to scale; the timestamp field is the largest.
  • Sign, 1 bit: always 0, so the ID stays positive in languages with signed 64-bit integers.
  • Timestamp, 41 bits: milliseconds since an epoch you choose, such as your launch date. 241 ms = 2.2 × 1012 ms, about 70 years before it runs out.
  • Machine, 10 bits: 210 = 1,024 generators can run at once.
  • Sequence, 12 bits: a counter that resets every millisecond. 212 = 4,096 IDs per ms per machine, so about 4 million a second each.

Build the example: shift each field into place and add. 1,000,000,000 × 222 = 4,194,304,000,000,000. Then 37 × 212 = 151,552. Then the sequence, 5. The ID is 4,194,304,000,151,557. Reading it back is the reverse: divide by 222 for the timestamp, and so on.

The split is yours to tune. Fewer machines and more sequence bits suits a few very busy generators; a shorter timestamp in seconds lasts longer but sorts less finely.

Two generators, a burst, a clock jump, a lost leaseUse the arrows or ← → keys
  1. Two generators, a burst, a clock jump, a lost lease, step 1Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service Amachine 37Order service BCoordinationserviceOrders DBmachine no.machine no.insertinsert
    A
    37

    1Service A starts and claims a free machine number from the coordination service, held by a lease. It gets 37.

  2. Two generators, a burst, a clock jump, a lost lease, step 2Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service Amachine 37Order service Bmachine 38CoordinationserviceOrders DBmachine no.machine no.insertinsert
    A
    37
    B
    38

    2Service B claims 38. From now on neither talks to anyone to make an ID.

  3. Two generators, a burst, a clock jump, a lost lease, step 3Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service Aseq 5Order service BCoordinationserviceOrders DBmachine no.machine no.insertinsert
    timestamp
    1,000,000,000
    machine
    37
    sequence
    5

    3At millisecond 1,000,000,000, A makes its sixth ID of that millisecond, so the sequence is 5: ID 4,194,304,000,151,557.

  4. Two generators, a burst, a clock jump, a lost lease, step 4Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service AOrder service Bseq 0CoordinationserviceOrders DBmachine no.machine no.insertinsert
    timestamp
    1,000,000,000
    machine
    38
    sequence
    0

    4In the same millisecond, B makes its first ID: 4,194,304,000,155,648. Same time, different machine bits, so no clash.

  5. Two generators, a burst, a clock jump, a lost lease, step 5Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service Aseq full, waitOrder service BCoordinationserviceOrders DBmachine no.machine no.insertinsert
    timestamp
    1,000,000,001
    machine
    37
    sequence
    4095

    5A burst: A uses all 4,096 sequence numbers within one millisecond. The next request waits for the clock to tick, under 1 ms.

  6. Two generators, a burst, a clock jump, a lost lease, step 6Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service Aclock went backOrder service BCoordinationserviceOrders DBmachine no.machine no.insertinsert
    last used
    1,000,000,002
    clock now
    999,999,999

    6Time sync moves A's clock back 3 ms. Reusing those milliseconds could repeat an ID, so A refuses to issue IDs until its clock passes the last timestamp it used.

  7. Two generators, a burst, a clock jump, a lost lease, step 7Order service A to Coordination service (machine no.); Order service B to Coordination service (machine no.); Order service A to Orders DB (insert); Order service B to Orders DB (insert).Order service Alease lost: stopOrder service BCoordinationserviceOrders DBmachine no.machine no.insertinsert
    A
    stopped
    B
    38

    7A loses contact with the coordination service and its lease runs out. Number 37 may be given to a new server, so A must stop making IDs. Two generators with one number would collide.

1 / 7

Numbers worth remembering

  • 210 ≈ 1 thousand, 220 ≈ 1 million, 230 ≈ 1 billion, 240 ≈ 1 trillion.
  • A 64-bit ID is 8 bytes; a UUID is 16 bytes, or 36 characters as text. On a billion rows and their indexes, that difference is many gigabytes.
  • Snowflake-style capacity: 4,096 per ms × 1,000 ms = about 4 million IDs a second per machine.
Estimate: How long the timestamp lasts

A 41-bit field counts milliseconds since your chosen epoch. Roughly how long until it overflows?

You know
  • 41 bits of milliseconds
  • A year is about 3.16 × 107 seconds

Show the working
  1. 241 = 2,199,023,255,552 ms ≈ 2.2 × 1012 ms
  2. ÷ 1,000 = 2.2 × 109 seconds
  3. ÷ 3.16 × 107 ≈ 69.6, call it 70 years

Estimate 70 years (anything from 25 years to 200 years is a good answer)

Choosing the epoch as your launch date instead of 1970 is what makes the 70 years start now.

In the interview

IDs come up whenever data is sharded or written from many servers, and in any design that shows items in time order (feeds, chats). State the requirements first: "IDs must be unique across shards, fit in 64 bits, and roughly sort by time, so I'd use a Snowflake-style generator inside each service."

IDs for chat messages
Interviewer

How do you assign message IDs?

You

Messages are written on many servers and shown in time order, so I'd use 64-bit Snowflake-style IDs: 41 bits of milliseconds, 10 bits of machine number, 12 bits of sequence. Each server gets its machine number from a lease at startup, and then makes IDs locally.

Interviewer

Two messages in the same chat land on different servers in the same millisecond. Which comes first?

You

The machine bits decide, so the order is arbitrary within that millisecond, and clocks on different servers differ by a few ms anyway. For a chat that is fine. If exact order inside a conversation mattered, I'd have one owner per conversation assign a sequence number.

Follow-ups you should expect:

  • "What if the clock goes backwards?" Refuse or wait until it passes the last timestamp used; alert if the jump is large.
  • "How are machine numbers assigned?" From a coordination service with a lease, or from configuration. The lease must be held while generating.
  • "Can outsiders learn anything from your IDs?" Yes. Sequential IDs reveal volume, and time-based ones reveal when a record was made. Where that matters, show users a separate random public ID.
  • "Why not UUIDs?" Fine if 128 bits is acceptable; prefer a time-ordered version so index inserts stay sequential.

Common mistakes

Quick check

Your layout uses 10 machine bits and 12 sequence bits. How many IDs can one machine make in one second at most?

Which ID choice fits best: 64-bit keys, sorted by time, written by 200 servers?

What to practise next

Clocks, leases and lost machines are the theme of reliability and failure. To see range allocation inside a full design, work through Design a URL Shortener; for time-ordered IDs, Design a Chat App.