Engineering Atlas › System Design Interviews

Generating unique IDs in a distributed system

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

When the pattern shows up in interviews

"Design a URL shortener" (short codes), "Design Twitter" (tweet IDs that sort by time), "Design WhatsApp" (message IDs for ordering and dedupe), sharded databases where auto-increment no longer works, and any idempotency key. The interviewer is checking whether you can list the required properties and match a scheme to them, and whether you know the failure modes: duplicate worker IDs, clock rollback, and IDs leaking business volume.

Properties to decide first

Central sequence and block allocation

A single database sequence is strictly increasing and trivially unique, but every insert depends on one node. Two common fixes: give each of N databases a different offset with a step of N, or hand out blocks. MySQL's auto_increment_increment and auto_increment_offset produce the series offset + N × increment and apply to every table on the server, not one (MySQL docs). With block allocation, a service atomically bumps a counter by 1,000 (UPDATE counters SET next = next + 1000 WHERE name = 'order' RETURNING next) and then issues those 1,000 IDs from memory. A crash wastes the rest of the block, which is fine because uniqueness, not density, is the requirement. Flickr's "ticket servers" are the classic example of a dedicated sequence service: each ID is a REPLACE INTO on a one-row MySQL table followed by LAST_INSERT_ID(), and two servers with increment 2 and offsets 1 and 2 issue odd and even IDs so either can fail without coordination (Flickr).

Random IDs

UUIDv4 has 122 random bits, so collisions are practically impossible without any coordination. The costs are 16 bytes per key, no time ordering, and scattered B-tree inserts. RFC 9562 still says to use UUIDv4 when an ID must be unguessable for security purposes, because time-based versions reveal creation order (RFC 9562, section 8).

Time-ordered IDs

Snowflake, published by Twitter in 2010, uses 1 unused sign bit, 41 bits of milliseconds since a custom epoch (about 69 years of range), 10 bits of machine ID (1,024 machines), and 12 bits of sequence (4,096 IDs per millisecond per machine). Its stated goal was IDs "k-sorted" within 1 second, aiming for tens of milliseconds, with no coordination between machines (Snowflake README); the original Scala service is archived, but the format lives on. IDs from one worker strictly increase; IDs across workers are ordered to within clock skew. Variants move the boundaries: Instagram generated IDs inside Postgres with 41 bits of time, 13 bits of logical shard ID, and 10 bits from a per-shard sequence (Wikipedia); Discord uses 42 bits of time from a 2015 epoch, 5 bits of worker, 5 bits of process and a 12-bit increment (Discord docs).

UUIDv7, standardised in RFC 9562 (May 2024, which obsoletes RFC 4122), puts a 48-bit Unix millisecond timestamp in the top bits and fills the rest with version bits and randomness, giving time ordering with no worker IDs. The RFC says new systems should prefer UUIDv7 over the older time-based v1 and v6 (RFC 9562). Databases now generate it natively: PostgreSQL 18 (September 2025) added uuidv7() (PostgreSQL 18 release notes). ULID is a similar 128-bit design (48 bits of time, 80 random) encoded as 26 Crockford base-32 characters; its monotonic mode increments the random part within a millisecond and throws an error if that overflows (ULID spec).

Short codes

A URL shortener wants 7-character codes. Base62 over a 64-bit counter gives about 3.5 trillion codes in 7 characters (62^7). A raw counter makes codes guessable, so either encode a bijective scramble of the counter (a small Feistel network or multiply by an odd constant mod 2^n) or draw random codes and retry on the rare collision through a unique index. The system-design-primer's Pastebin answer takes the hash route: Base62 of an MD5 over IP and timestamp, truncated to 7 characters, regenerated if it already exists.

Down the stack

Layer 1The contract

Every issued ID is unique within its scope forever, including across restarts and failovers. For Snowflake: IDs from one worker strictly increase; IDs from different workers are ordered by timestamp to within clock skew plus one millisecond; the generator either returns an ID or a clear error (clock moved backwards, sequence exhausted), and never a duplicate. Generation is local and takes well under a microsecond.

Layer 2The mechanism

A Snowflake generator keeps last_ms and sequence. On each call it reads the clock. If now > last_ms, it resets the sequence to 0. If equal, it increments; on overflow past 4,095 it waits for the next millisecond. If now < last_ms, the clock went backwards, so it waits or refuses, because continuing would reissue timestamps it already used. The ID is (now - epoch) << 22 | worker << 12 | sequence. Worker IDs must be unique among live generators: assign them from a lease in ZooKeeper or etcd (an ephemeral node or a key with a TTL that the process renews), from a StatefulSet pod ordinal, or from a database table claimed at startup. A UUIDv7 layout is: 48 bits unix_ts_ms, 4 bits version (0111), 12 bits rand_a, 2 bits variant, 62 bits rand_b; RFC 9562 allows using rand_a as a sub-millisecond counter for monotonicity within one generator.

Layer 3The machine

Reading the clock with clock_gettime(CLOCK_REALTIME) goes through the vDSO without a syscall and costs tens of nanoseconds, so a generator can issue millions of IDs per second per core; a call to a central ticket server costs a network round trip of hundreds of microseconds. NTP daemons normally slew the clock gradually (chrony's default maximum slew is one twelfth, 83,333 ppm) and step it only when configured to, typically with makestep at boot (chrony docs); a leap second, a manual date change, VM migrations or misconfigured hosts can jump backwards, which is why the generator must check. In a B-tree index, an increasing key always lands on the rightmost leaf page, so inserts touch one hot page that stays in memory and pages fill completely. A random UUID lands on a random leaf among millions: each insert may read a page from disk, pages split and end up roughly half to three quarters full, and the working set becomes the entire index. InnoDB stores rows in the primary key's clustered index and copies the primary key into every secondary index, so a 16-byte random key inflates and fragments all of them.

Why it's built this way

  1. A central counter costs a network round trip per ID and a single point of failure, so generate locally.
  2. Local generators must not collide, so each gets a unique worker ID (or enough randomness that collisions are negligible).
  3. Databases index sorted keys efficiently, so put the timestamp in the high bits to make keys increase over time.
  4. Clocks can go backwards, so the generator remembers the last timestamp and refuses to reuse it.
  5. 64-bit integers are cheap everywhere, so pack time, worker and sequence into one word instead of using 128 bits.

Diagram

flowchart TD
    S["NextID(now)"] --> C{"now vs last_ms"}
    C -->|"now before last_ms"| E["Error or wait: clock moved backwards"]
    C -->|"same millisecond"| I["sequence += 1"]
    C -->|"now after last_ms"| Z["sequence = 0, last_ms = now"]
    I --> O{"sequence over 4095?"}
    O -->|"yes"| W["Wait for next ms (or error)"]
    O -->|"no"| B["Pack: 41-bit time, 10-bit worker, 12-bit sequence"]
    Z --> B

Worked example

A messaging platform needs IDs for about 400,000 messages per second at peak across 160 API servers, each running 4 generator processes: 640 generators, under the 1,024 that 10 bits allow. Each generator averages about 625 IDs per second, under one per millisecond, so the 4,096-per-millisecond sequence has a large margin even for a 50-times burst on one process.

Generators lease worker IDs from etcd with a 10-second TTL renewed every 3 seconds. A process that cannot renew stops issuing IDs before its lease could be handed to someone else. The custom epoch is 2024-01-01, so 41 bits last until roughly 2093.

Messages are stored in a table clustered by (conversation_id, message_id); because message IDs increase over time, new messages append to the end of each conversation's range and "latest 50 messages" is a short range scan. The web client receives IDs as strings, because JavaScript numbers are doubles that represent integers exactly only up to 2^53 − 1 and would silently round 64-bit IDs (MDN).

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Single DB sequenceDense, strictly increasing, trivialBottleneck, single point of failure, leaks volumeOne database, modest scale
Block allocation (hi-lo)Rare coordination, 64-bit, mostly orderedGaps, ordering only within a blockSharded services needing numeric IDs
UUIDv4No coordination at all, opaque128-bit, random index inserts, unorderedLow write rates, external opaque IDs
UUIDv7 / ULIDNo coordination, time-ordered128-bit, exposes creation timeNew systems wanting sortable UUIDs
Snowflake64-bit, time-ordered, very fastWorker ID assignment, clock sensitivityHigh-throughput event or message IDs

Pitfalls in production

Leadership lens

Check yourself

  1. Why do Snowflake IDs from different workers only roughly sort by time?

    Show answer

    Each worker uses its own clock, so skew between machines can order two IDs differently from their real creation order by up to the skew.

  2. A generator sees now 5 ms earlier than last_ms. What must it do?

    Show answer

    Wait until the clock passes last_ms or return an error; issuing IDs with the earlier timestamp could duplicate IDs already issued.

  3. Why do random UUID primary keys hurt insert performance in a large B-tree?

    Show answer

    Each insert lands on a random leaf page, so the whole index must stay in memory to avoid disk reads, and random page splits leave pages partly empty.

  4. How many IDs can one Snowflake worker issue per second at most?

    Show answer

    4,096 per millisecond, so about 4.1 million per second.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →