Interview patterns · Design 11

Unique IDs at scale

How to generate unique IDs across many servers: auto-increment and its limits, UUIDv4 versus UUIDv7 and ULID, Snowflake's bit layout, clock skew and ID blocks.

IntermediateInterview priority: Medium35 min
On this page
  1. The problem: the counter that cannot be shared
  2. Signals that you are facing it
  3. The idea: make each ID unique by construction
  4. The toolbox
  5. Worked example: what 8 bytes saves
  6. When not to bother
  7. Which case studies use it
  8. In the interview
  9. Quiz

The problem: the counter that cannot be shared

An online shop numbers its orders with the database's AUTO_INCREMENT: 1, 2, 3... It is simple, compact and ordered. Then the shop grows:

  • Orders are sharded across four databases. Each has its own counter, so shards A and B both create order 1001. Any table, report or event stream that combines them now has two different orders with one ID.
  • The mobile app wants to create an order offline and sync it later, but it cannot know the next number without asking the server.
  • A competitor places an order on Monday (ID 50,210) and another on Tuesday (ID 53,890) and now knows the shop takes about 3,700 orders a day. Customers can also guess other customers' order URLs by adding one.

One database handing out numbers is a single point of coordination. At scale you want IDs that many machines can create independently, that never collide, and ideally that still sort by time.

Signals that you are facing it

  • Data is sharded or written in several regions, and records need a global identity.
  • Clients must create records offline or before talking to the server (drafts, chat messages sent from a phone).
  • Very high write rates: hundreds of thousands of new rows a second.
  • IDs appear in public URLs and must not reveal volume or be guessable.
  • You want "newest first" lists sorted by ID, without a separate timestamp index.

The idea: make each ID unique by construction

There are only three ways to make IDs unique without a central check on each one:

  1. Randomness: pick enough random bits that a collision is practically impossible (UUIDv4).
  2. Partition the ID space: give each generator its own slice, so generators can never pick the same value (Snowflake's machine number, ID blocks).
  3. Time plus one of the above: put a timestamp first so IDs sort by creation time (UUIDv7, ULID, Snowflake).

The toolbox

Auto-increment and database sequences

The database keeps a counter. 8 bytes, perfectly ordered, human-readable. Catch: one writer owns the counter, it leaks volume, and shards collide. MySQL's auto_increment_increment and auto_increment_offset (shard 1 issues 1, 5, 9...; shard 2 issues 2, 6, 10...) patch the collision for a fixed number of shards, but resharding breaks the scheme.

Two shards, two counters, one duplicated ID

UUIDv4: random

A UUID (universally unique identifier) is 128 bits, written as 36 characters like 9b2f6c1e-4d3a-4f8e-a1b2-7c9d0e5f3a21. Version 4 fills 122 of those bits with randomness. Any machine, phone or browser can generate one with no coordination. You would need to generate about 2.7 × 10<sup>18</sup> of them for even a 50% chance of a single collision.

Catch: random values make poor database keys. In a B-tree index (the sorted structure most databases use for primary keys) each new row lands on a random page. Once the index is larger than memory, inserts keep reading cold pages from disk and splitting half-full pages, and write throughput can drop several-fold compared with ordered keys. UUIDs are also twice the size of a BIGINT, and in MySQL's InnoDB every secondary index stores the primary key, so the cost multiplies.

UUIDv7 and ULID: time first, then random

UUIDv7 (standardised in RFC 9562, 2024) puts a 48-bit Unix timestamp in milliseconds at the front, then 74 random bits (the remaining 6 bits mark the version and variant). New IDs are larger than old ones, so inserts go to the right-hand edge of the index like auto-increment, while any machine can still generate them. PostgreSQL 18 has a built-in uuidv7(); most languages have a library.

ULID is the same idea in a different encoding: 48-bit millisecond timestamp plus 80 random bits, written as 26 characters of Crockford base32 (01JD3Q8Z5X4G7R2M9KQ1T6VBNC), which sorts correctly as text.

Catch: still 16 bytes, and the creation time is readable by anyone who sees the ID.

Snowflake: a 64-bit, time-ordered ID

Twitter's Snowflake (2010) packs a sortable ID into a signed 64-bit integer, so it fits a BIGINT column and is half the size of a UUID.

The Snowflake bit layout

BitsFieldGives
1Sign, always 0Positive numbers in signed 64-bit types
41Milliseconds since a custom epoch2<sup>41</sup> ms ≈ 69.7 years of IDs; sorting by ID sorts by time
10Machine (worker) ID1,024 generators that can never collide with each other
12Sequence within the millisecond4,096 IDs per millisecond per machine, about 4 million a second

Each generator needs a unique machine ID, assigned from configuration, a Kubernetes StatefulSet ordinal, or a short-lived lease in ZooKeeper or etcd. Discord and many others use this layout or a variant. Instagram's version runs inside Postgres: 41 bits of time, 13 bits of logical shard ID and 10 bits of a per-shard sequence, so the ID also says which shard holds the row.

A minimal generator:

import threading
import time

EPOCH_MS = 1_704_067_200_000      # 2024-01-01T00:00:00Z: our custom epoch

def now_ms() -> int:
    return time.time_ns() // 1_000_000

class Snowflake:
    def __init__(self, machine_id: int):
        if not 0 <= machine_id < 1024:
            raise ValueError("machine_id must fit in 10 bits")
        self.machine_id = machine_id
        self.last_ms = -1
        self.seq = 0
        self.lock = threading.Lock()

    def next_id(self) -> int:
        with self.lock:
            now = now_ms()
            if now < self.last_ms:                    # the clock went backwards
                if self.last_ms - now > 1000:
                    raise RuntimeError("clock moved back over 1 s; refusing to issue IDs")
                while now < self.last_ms:
                    time.sleep(0.0005)
                    now = now_ms()
            if now == self.last_ms:
                self.seq = (self.seq + 1) & 0xFFF
                if self.seq == 0:                     # all 4,096 used: wait for the next ms
                    while now <= self.last_ms:
                        now = now_ms()
            else:
                self.seq = 0
            self.last_ms = now
            return ((now - EPOCH_MS) << 22) | (self.machine_id << 12) | self.seq

Snowflake IDs are k-sorted: roughly in time order across machines, exactly in order only within one machine, because two machines' clocks differ by a few milliseconds.

ID blocks (ranges)

A central counter is fine if you don't hit it for every ID. Each app server reserves a block of, say, 1,000 IDs with one atomic update (UPDATE id_blocks SET next = next + 1000 WHERE name = 'orders' RETURNING next) and hands them out from memory. This is often called hi/lo. Flickr ran two "ticket servers" (one issuing odd numbers, one even) for the same purpose.

Blocks of IDs from an allocator, and the gap a crash leaves

Catch: IDs are only roughly ordered (server 2 may issue 2,001 before server 1 issues 1,500), a crash leaves gaps, and the allocator must be highly available. It is a good fit for short, numeric public IDs such as a URL shortener's, which then encodes the number in base62.

Comparing the options

OptionSizeSorted by time?CoordinationGood forWeak at
Auto-increment8 BYesEvery ID, one DBSingle databaseShards, offline, leaks volume
UUIDv416 BNoNoneClient-side IDs, unguessable tokensIndex locality, size
UUIDv7 / ULID16 BYes (ms)NoneDefault for new distributed tablesSize; leaks creation time
Snowflake8 BRoughlyMachine ID onceHuge write rates, compact keysClock skew; machine-ID management
ID blocks8 BRoughlyOnce per blockShort numeric IDsGaps; allocator must stay up

Worked example: what 8 bytes saves

A chat service stores 100 billion messages. Keys are either Snowflake (8 bytes) or UUIDv7 (16 bytes). Each message row's ID appears in the primary key and in two secondary indexes (in InnoDB a secondary index stores the primary key).

  • Extra bytes with UUIDs: 8 bytes × 3 places × 100 × 10<sup>9</sup> rows = 2.4 TB, before replication. With replication factor 3, 7.2 TB.
  • Throughput is not the concern: at 500,000 messages a second, 200 Snowflake generators each issue 2,500 a second, a tiny fraction of their 4 million a second ceiling.
  • Lifetime: with a 2024 epoch, 41 bits of milliseconds last until around 2093.

That is a real saving, but UUIDv7 needs no machine IDs and works in the client. For most systems below billions of rows, UUIDv7 is the simpler default; Snowflake earns its keep at very large scale or when IDs must be 64-bit.

When not to bother

  • One database, no plans to shard. BIGINT identity columns are the fastest, smallest, simplest option. Use a separate random token for anything public.
  • The ID is a secret. Session tokens, password-reset links and API keys need cryptographic randomness (128+ bits from a secure generator), not a time-ordered ID that is partly predictable.
  • You need gap-free numbering. Invoices in some countries must be consecutive with no gaps. None of these schemes guarantees that; it needs a single serialised counter per series, written in the same transaction as the invoice.

Which case studies use it

In the interview

Your turn: IDs for a multi-region chat app

A chat app runs in three regions. Phones send messages while offline and sync later. Messages must appear in order within a conversation, and the client must be able to retry a send without creating a duplicate. Choose the ID scheme(s).

Compare with our answer
  • The phone generates a UUIDv7 (or ULID) for each message. It doubles as the idempotency key: retries carry the same ID, and the server ignores a second insert.
  • Ordering within a conversation should not rely on IDs from different devices, whose clocks disagree. The server assigns a per-conversation sequence number when it accepts the message (in the conversation's home shard or region).
  • Display order uses the server sequence; the client ID is for deduplication and local display before sync.
  • If 64-bit keys are needed for storage efficiency, the server can also assign a Snowflake ID with a region bit or per-region machine-ID range.

A strong answer mentions: client-generated IDs for offline creation and dedupe · why device clocks can't order messages · a server-assigned sequence per conversation · UUIDv7/ULID over v4 for index locality · region-unique machine IDs if Snowflake is used.

Your turn: the requirement changes

A team switched from auto-increment to UUIDv4 primary keys on a 2-billion-row MySQL table to support sharding. Insert throughput dropped by 70% and the buffer pool hit rate fell. What happened, and what would you change?

Compare with our answer

Random UUIDs scatter inserts across the whole primary-key B-tree. In InnoDB the table is clustered by primary key, so each insert touches a random leaf page; with a 2-billion-row table most of those pages are not in the buffer pool, so inserts need disk reads, cause page splits and leave pages half full. Every secondary index also stores the 16-byte key.

A strong answer mentions:

  • B-tree locality: ordered keys append at the right edge; random keys hit random pages.
  • Clustered index in InnoDB makes it worse: the whole row moves with the key.
  • Switch to a time-ordered key: UUIDv7 or ULID, or a 64-bit Snowflake ID.
  • Store UUIDs as BINARY(16), never as a 36-character string.
  • Keep a separate random public ID if URLs must not reveal creation time.
Unique IDs on one page
  • Uniqueness without coordination comes from randomness, partitioning the ID space, or both, with time first for ordering.
  • Auto-increment: 8 B, ordered; breaks with shards, offline clients; leaks volume.
  • UUIDv4: 122 random bits, no coordination; random inserts hurt B-tree indexes.
  • UUIDv7 (RFC 9562): 48-bit ms timestamp + 74 random bits. ULID: 48 + 80 bits, 26 chars. Good default.
  • Snowflake: 1 sign + 41 ms + 10 machine + 12 sequence = 64 bits; 4,096/ms/machine; ~69 years per epoch.
  • Clock backwards: track last timestamp, wait or refuse; slew NTP; unique constraint as safety net.
  • Machine IDs by lease, never by copied config. Send 64-bit IDs to JavaScript as strings.
  • ID blocks (hi/lo): one DB write per 1,000 IDs; gaps on crash; good for short base62 codes.
  • Secrets need cryptographic randomness; gap-free invoice numbers need one serialised counter.
Check what stuck

1. A team shards orders across 8 Postgres databases, each with its own identity column. What goes wrong first?

2. A Snowflake generator issues 4,096 IDs within the current millisecond. What should it do for the next request?

3. After an NTP correction, a service briefly inserts duplicate primary keys. It uses a Snowflake-style generator. What is the best fix?

4. Which situation suits UUIDv4 better than UUIDv7?

5. A front-end displays tweet 1,856,912,345,678,901,234 as 1,856,912,345,678,901,200. Why?

6. A URL shortener wants short, numeric IDs encoded in base62, generated by 50 app servers at 20,000 links per second. What fits best?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.