Unique ID Generation - Complete Deep Dive

Prerequisites: Database Sharding, Terminology Used in: Unique ID Generator, URL Shortener, Chat System, Twitter/X — every design that creates records at scale

Why this is a real interview topic

The moment you shard, AUTO_INCREMENT stops working — two shards will happily hand out ID 1000. So “how do you generate IDs?” is really “have you thought about what breaks when you shard?”

There are five requirements, and they conflict:

Time-sortable and not-guessable are in direct tension. Naming that tension is most of a good answer.

The options

Snowflake — know this one cold

64 bits, split into meaningful fields:

 1        41 bits              10 bits        12 bits
┌─┬──────────────────────┬──────────────┬──────────────┐
│0│      timestamp       │  machine id  │   sequence   │
└─┴──────────────────────┴──────────────┴──────────────┘
 │         │                    │              │
 │         │                    │              └─ 4,096 IDs per ms per machine
 │         │                    └─ 1,024 machines
 │         └─ ms since a custom epoch → 2^41 ms ≈ 69 years
 └─ sign bit, always 0 so the ID is a positive signed 64-bit int

Capacity: 4,096 × 1,024 = 4.2 million IDs per millisecond = 4.2 billion/second. More than enough for anything.

Why the fields are in that order: timestamp first means the ID sorts by time when compared as an integer. Put the machine ID first and you’d get IDs clustered by machine instead — useless for sorting and bad for index locality.

public class SnowflakeGenerator {
    private static final long EPOCH = 1735689600000L;  // 2025-01-01, custom epoch
    private static final long MACHINE_BITS = 10L;
    private static final long SEQUENCE_BITS = 12L;
    private static final long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1;  // 4095

    private final long machineId;
    private long lastTimestamp = -1L;
    private long sequence = 0L;

    public SnowflakeGenerator(long machineId) {
        if (machineId < 0 || machineId >= (1L << MACHINE_BITS))
            throw new IllegalArgumentException("machineId out of range");
        this.machineId = machineId;
    }

    public synchronized long nextId() {
        long now = System.currentTimeMillis();

        if (now < lastTimestamp) {
            // Clock moved backwards (NTP correction). Refusing is safer than
            // risking a duplicate — see the clock-skew section below.
            throw new IllegalStateException(
                "Clock moved backwards by " + (lastTimestamp - now) + "ms");
        }

        if (now == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) now = waitNextMillis(lastTimestamp);  // 4096 used up
        } else {
            sequence = 0L;
        }

        lastTimestamp = now;
        return ((now - EPOCH) << (MACHINE_BITS + SEQUENCE_BITS))
             | (machineId << SEQUENCE_BITS)
             | sequence;
    }

    private long waitNextMillis(long last) {
        long now = System.currentTimeMillis();
        while (now <= last) now = System.currentTimeMillis();
        return now;
    }
}

The three things interviewers probe about Snowflake:

1. How does a machine get its ID?

• ZooKeeper/etcd sequential node — robust, adds a coordination dependency at startup only
• Kubernetes StatefulSet ordinal (pod-0 → 0) — free and stable, my usual answer
• Derived from the private IP’s last octets — no coordination, but collides if subnets are reused
• Config/env var — simplest, and someone will eventually deploy two pods with the same value

⚠️ Duplicate machine IDs are the silent killer. Two machines with the same ID producing IDs in the same millisecond generate identical IDs. Whatever scheme you use, it must make duplicates impossible, not just unlikely.

2. What about clock skew / NTP going backwards? Three defensible answers:

• Refuse to generate while now < lastTimestamp (what the code above does) — correctness over availability. Usually right, since the window is milliseconds.
• Wait it out if the drift is small (a few ms), fail if large.
• Borrow from the sequence — some implementations bump a logical counter to stay monotonic without the wall clock.

Also: run NTP with slew mode rather than step adjustments so the clock is nudged rather than jumped, and use a monotonic clock where you can.

3. What if you exhaust 4,096 IDs in one millisecond? Spin until the next millisecond (as above). If you routinely hit that, you need more machine IDs, not more sequence bits — and you can rebalance the bit split (e.g. 41/12/10 for fewer machines and more per-ms throughput) since the split is yours to choose.

Say this: “Snowflake, with machine IDs from the StatefulSet ordinal so duplicates are structurally impossible. 41 bits of ms timestamp gives 69 years from a custom epoch, and I’d refuse to issue IDs if the clock steps backwards rather than risk a duplicate. It’s 64 bits, so it’s half the index size of a UUID and it sorts by time.”

UUID v4 vs UUID v7 — and why random IDs hurt

The random-insert problem, concretely:

UUID v4 inserts land uniformly across the B-tree:
  → every insert dirties a different page
  → the working set is the ENTIRE index, not just the hot end
  → once the index exceeds RAM, each insert becomes a random disk read
  → page splits everywhere → fragmentation → bloat
  → MySQL InnoDB is worst hit: the PK is clustered, so random PKs
    physically scatter your row data too

UUID v7 / Snowflake inserts land at the right edge:
  → the same few pages stay hot in cache
  → sequential writes, minimal splits, dense pages

This is a measurable, order-of-magnitude difference on write-heavy tables — not a micro-optimization. It’s the single best reason to prefer v7 over v4 in 2026.

⚠️ Never store a UUID as a 36-char string. char(36) is 36 bytes plus overhead vs 16 bytes binary — and it’s in every index and every foreign key. Use uuid in Postgres, BINARY(16) in MySQL.

ULID vs UUID v7: essentially the same idea (48-bit ms + randomness). ULID’s advantage is its canonical form: 26 characters of Crockford base32, no hyphens, case-insensitive, lexicographically sortable as a string — which matters if IDs land in S3 keys, log filenames, or a KV store’s sort key. UUID v7 wins on standardization and native DB support. Either is a good answer; UUID v7 is the safer default now.

Ticket servers and range allocation

A central service hands out IDs. The naive version (one round trip per ID) is a bottleneck, so hand out ranges:

App A → "give me 1000 IDs" → ticket server returns [1000, 1999]
App A now serves 1,000 IDs locally with zero network calls
App B → gets [2000, 2999]

The ticket server itself is just a row: UPDATE counters SET value = value + 1000 RETURNING value.

Flickr’s classic HA trick: two MySQL servers, one issuing odd IDs and one even (auto_increment_offset 1 and 2, auto_increment_increment 2). Either can die without stopping ID generation. Elegant, and a great thing to be able to name.

⚠️ Gaps are fine; assuming density is not. If your business logic infers “we have N orders” from the max ID, range allocation and Snowflake both break that assumption. Count rows.

Public-facing IDs — the security half

Sequential public IDs are two vulnerabilities at once:

1. Enumeration / IDOR — /orders/1001 invites /orders/1002. (Authorization is the real fix; unguessable IDs are defense in depth.)
2. Business intelligence leak — sign up twice a week apart, subtract the IDs, and you know a competitor’s growth rate. This has genuinely leaked real companies’ numbers.

The standard answer: separate internal and external IDs.

internal id:  Snowflake bigint      → PK, foreign keys, joins, sorting
external id:  random 22-char slug   → URLs, API responses
              (unique index on it)

You get index locality and unguessability, at the cost of one extra indexed column.

Base62 encoding (for short URLs — this comes up constantly):

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n: int) -> str:
    if n == 0: return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return ''.join(reversed(out))

The capacity math to have ready:

62^6 ≈ 56.8 billion      ← 6 chars is plenty for most URL shorteners
62^7 ≈ 3.5 trillion

⚠️ Base62 of a sequential counter is still sequential — aZ, b0, b1. Encoding is compression, not obfuscation. If you need unguessable short codes, generate random ones and check for collisions (or use a keyed permutation of the counter, e.g. Feistel/hashids, which is bijective so it needs no lookup table).

Sharding interaction

Two patterns worth knowing:

Embed the shard in the ID. Reserve bits (or reuse the machine-ID field) for a shard number, so any service can route a request from the ID alone with no lookup table.

Instagram's approach: 41 bits time | 13 bits shard id | 10 bits per-shard sequence

The trade-off: the shard is now baked into the ID forever, so resharding means IDs whose embedded shard is a lie. You handle it with a mapping layer for moved ranges — which is exactly the kind of trade-off worth stating out loud.

Offset sequences per shard. Shard 0 issues 1, 5, 9…; shard 1 issues 2, 6, 10…. Simple, no coordination, but adding shards breaks the scheme.

Interview application

URL shortener: “Snowflake for the internal ID, then base62-encode a random 7-character code for the public short URL with a uniqueness check on insert — encoding the counter directly would make every URL guessable, which is a scraping and privacy problem. At 100M links, 62^7 keeps collision probability negligible, and a single retry on the unique-index violation handles the rest.”

Chat system: “Snowflake message IDs, because time-sortability gives me cursor pagination and ‘messages after X’ without a separate timestamp index. Per-conversation ordering matters more than global ordering, so I only need monotonicity within a conversation — and since a conversation is pinned to a partition, the per-node sequence handles it.”

E-commerce orders: “Internal Snowflake bigint for the PK and all foreign keys. Public order numbers are a separate random alphanumeric, because sequential order numbers let a competitor measure our order volume by placing two orders a week apart.”

Common Interview Questions

Q: “Why not just use auto-increment?” A: “It works until you shard — two shards independently issue ID 1000. It’s also a single point of failure for writes, and the IDs leak your volume publicly. Fine for a single-DB system, and it’s the right answer if you’re not sharding.”

Q: “UUID or Snowflake?” A: “Snowflake if I control the servers: 64 bits instead of 128, time-sortable, and index-friendly. UUID v7 if IDs must be generated client-side or offline with zero coordination — it’s also sortable, just twice the bytes. I’d avoid UUID v4 as a primary key because random inserts scatter B-tree writes across the whole index, which collapses write throughput once the index exceeds RAM.”

Q: “How do you assign machine IDs?” A: “Kubernetes StatefulSet ordinals — stable, unique by construction, no extra dependency. Otherwise a ZooKeeper/etcd sequential node at startup. The requirement is that duplicates are impossible, because two machines sharing an ID will emit identical IDs in the same millisecond.”

Q: “What if the clock goes backwards?” A: “Refuse to generate until the clock catches up, rather than risk duplicates — the window is usually milliseconds. I’d also configure NTP to slew rather than step so the clock is never jumped, and monitor drift.”

Q: “Are Snowflake IDs strictly ordered globally?” A: “No — only monotonic per generator. Two IDs from different machines in the same millisecond have an arbitrary relative order. They’re roughly time-ordered, which is enough for pagination and sorting but not for anything requiring a total order. If I need a total order I need consensus, and I’d question the requirement first.”

Q: “How do you avoid collisions in a random short code?” A: “Unique index on the code plus retry on violation. With 62^7 ≈ 3.5 trillion codes and 100M in use, the collision rate is tiny, so retries are rare. The alternative — pre-generating a pool of unused codes in a table and handing them out — trades storage for guaranteed O(1) allocation with no retry loop, which is nicer under a flash of traffic.”

Q: “Client-generated or server-generated IDs?” A: “Client-generated (UUID v7/ULID) makes retries naturally idempotent — the client can safely resend because the ID doubles as an idempotency key — and it lets an offline-first app create records with no network. The cost is 128 bits, plus you must never trust the client’s ID for anything security-relevant. Server-generated is more compact and controlled. For a mobile-first app with offline support, client-generated wins.”

Decision Framework