Design a Unique ID Generator: Snowflake, UUID & Ticket Servers

Every system you design needs IDs: orders, tweets, payments, messages, short URLs. In a single database you never think about it because AUTO_INCREMENT does the job. The moment you shard the database or run many app servers writing in parallel, "give me the next ID" becomes a distributed systems problem.

Interviewers ask this question on its own, and also as a sub-problem inside URL shorteners, chat apps and feeds. This guide covers every mainstream approach with its exact trade-offs, then implements Snowflake properly, including the clock and worker-ID problems most tutorials skip.

Step 1: Requirements for a Distributed ID Generator

Ask before choosing. "Unique ID" can mean very different things:

• Uniqueness: globally unique across all shards and services. Non-negotiable.
• Size: must it fit in a 64-bit integer (BIGINT)? 64-bit keys make indexes and foreign keys much smaller than 128-bit ones.
• Ordering: should IDs sort by creation time? "Roughly sorted" (k-sorted) is often enough for feeds and pagination; strictly monotonic across the whole system is far more expensive.
• Throughput: for example, 100,000 IDs per second at peak, with headroom to 1 million.
• Latency and availability: ID generation sits on every write path, so it must be sub-millisecond and must not become a single point of failure.
• Density: are gaps acceptable? Invoice numbers in India under GST rules must follow a consecutive series per financial year, so that case needs a different design than order IDs.
• Exposure: will IDs be visible to users? Sequential public IDs let competitors estimate your order volume and enable enumeration attacks.

A reasonable target for the interview: 64-bit, roughly time-ordered, unique, 100k+/s, highly available, no central coordination per ID. That set of requirements points straight at Snowflake, but you earn credit by showing why the alternatives fail.

Step 2: Capacity Estimates

Assume an e-commerce and payments platform at Indian scale: during a sale event, say 50,000 orders per second, each creating about 20 rows that need IDs (order, items, payment attempts, events, notifications). That is 1 million IDs per second at peak.

The last row is why 64-bit matters: every secondary index and foreign key repeats the primary key, so doubling key width ripples through the whole database. For more practice turning traffic into numbers, see back-of-the-envelope estimation.

Approach 1: Database Auto-Increment

The simplest option: let one database generate every ID. It is unique, dense and perfectly ordered. The problems appear as you scale:

• Single point of failure and bottleneck: every insert in every service waits on one machine.
• Breaks under sharding: each shard's auto-increment starts at 1, so shard A and shard B both produce order 1001.
• Leaks information: order 100234 today and 100934 tomorrow tells anyone you took about 700 orders.

Multi-master with step and offset

MySQL lets each server use auto_increment_increment and auto_increment_offset. With 3 servers and increment 3, server 1 issues 1, 4, 7…; server 2 issues 2, 5, 8…; server 3 issues 3, 6, 9…. Unique and coordination-free, but IDs are no longer ordered across servers, and adding a fourth server means changing the step everywhere without collisions, which is painful.

Approach 2: Ticket Servers (the Flickr Approach)

Flickr described a "ticket server": a dedicated MySQL instance with a single-row table whose only job is incrementing a number. A client runs:

CREATE TABLE tickets64 (
  id   BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  stub CHAR(1) NOT NULL DEFAULT '',
  PRIMARY KEY (id),
  UNIQUE KEY stub (stub)
) ENGINE=InnoDB;

REPLACE INTO tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

REPLACE deletes and re-inserts the single row, bumping the auto-increment, and LAST_INSERT_ID() is per-connection, so concurrent clients get distinct values. To remove the single point of failure, Flickr ran two ticket servers, one with offset 1 and one with offset 2, both with increment 2: odd and even IDs. Clients round-robin, and if one dies the other carries on.

Making ticket servers fast: segment allocation

One round trip per ID is slow. Instead, hand out ranges. An app server asks for a block of 1,000 IDs, receives [45,001 – 46,000] by atomically doing UPDATE seq SET max_id = max_id + 1000 WHERE name='order', then serves them from memory. Meituan's open-source Leaf "segment mode" adds a double buffer: when the current segment is 10% consumed, fetch the next one in the background so no request ever waits on the database.

• Pros: 64-bit, numeric, near-sequential, simple to reason about, database can be any SQL store.
• Cons: still depends on a database; ordering is only per allocator, not global (two app servers hand out interleaved ranges); restarting an app server wastes the rest of its block, creating gaps.

Segment allocation is the right answer when you want small numeric IDs but are fine with gaps, for example short-URL counters. It shows up again in the key-generation step of Pastebin system design.

Approach 3: UUIDs (v4 and v7)

A UUID is a 128-bit value. Generating one needs no network call at all, which is the strongest availability story possible.

UUID v4: random

Version 4 sets 6 bits for version and variant and fills the other 122 bits with random data. Collision probability for n UUIDs is approximately n²/(2 × 2¹²²); you would need about 2.7 × 10¹⁸ UUIDs for a 50% chance of a single collision. The realistic risk is a broken random source, not the math.

The real problem is index locality. B-tree primary keys (InnoDB clusters rows by primary key) work best when new keys go to the right edge of the tree. Random v4 keys land on random leaf pages, causing page splits, poor buffer-pool hit rates and fragmented indexes once the table outgrows memory. Postgres secondary indexes suffer similarly. Why that happens is explained in database indexing and B-trees.

UUID v7: time-ordered

RFC 9562 (published in 2024) standardised UUID v7: the first 48 bits are a Unix timestamp in milliseconds, then 4 version bits, 12 bits (rand_a, optionally used as a sub-millisecond counter), 2 variant bits and 62 more bits (rand_b). New v7 UUIDs sort roughly by creation time, so inserts hit the right side of the B-tree, while keeping 74 bits of randomness for uniqueness without coordination.

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    unix_ts_ms (48 bits)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  unix_ts_ms (cont.)           | ver=7 |    rand_a (12 bits)   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var|                  rand_b (62 bits)                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        rand_b (cont.)                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

ULID is an older, similar idea (48-bit ms timestamp + 80 random bits, encoded as 26 Crockford base32 characters). If your language has a v7 library, prefer the standard.

Approach 4: Twitter Snowflake and Its 64-Bit Layout

Twitter built Snowflake around 2010 when moving from MySQL to Cassandra, which has no auto-increment. Their requirements were exactly ours: 64-bit, roughly sorted, generated at very high rates without coordination.

• Sign bit (1): always 0, so IDs are positive in languages with signed 64-bit integers (Java's long).
• Timestamp (41): milliseconds since a custom epoch, such as your launch date. Using the Unix epoch would waste ~56 years of range before your company even existed. Twitter's epoch is 1288834974657 (November 2010).
• Machine ID (10): 1,024 distinct generators. Often split as 5 bits datacenter + 5 bits worker.
• Sequence (12): counter within the same millisecond on the same worker, reset each new millisecond.

Because the timestamp occupies the high bits, sorting IDs numerically sorts them by time (to millisecond precision, and across machines only as well as their clocks agree). That gives free chronological pagination: "tweets older than ID X" is a primary-key range scan.

Dry run: building one ID

Custom epoch: 2024-01-01T00:00:00Z = 1,704,067,200,000 ms. Current time: 2026-10-10T09:15:00.000Z = 1,791,623,700,000 ms. Datacenter 3, worker 17, this is the 6th ID in this millisecond (sequence 5).

1. Timestamp delta. 1,791,623,700,000 − 1,704,067,200,000 = 87,556,500,000.
2. Machine ID. (3 << 5) | 17 = 96 + 17 = 113.
3. Shift and combine. (87,556,500,000 << 22) | (113 << 12) | 5 = 367,238,578,176,462,853.
4. Decode check. id >> 22 returns 87,556,500,000; (id >> 12) & 1023 returns 113; id & 4095 returns 5.

With this epoch the 41-bit timestamp runs out in September 2093. Writing down when your IDs overflow is a small detail that interviewers notice.

Snowflake Implementation in Java and Python

public final class Snowflake {
    private static final long EPOCH = 1704067200000L;   // 2024-01-01T00:00:00Z
    private static final int WORKER_BITS = 10;
    private static final int SEQUENCE_BITS = 12;
    private static final long MAX_WORKER = (1L << WORKER_BITS) - 1;    // 1023
    private static final long SEQUENCE_MASK = (1L << SEQUENCE_BITS) - 1; // 4095
    private static final long MAX_BACKWARD_MS = 5;

    private final long workerId;
    private long lastTs = -1L;
    private long sequence = 0L;

    public Snowflake(long workerId) {
        if (workerId < 0 || workerId > MAX_WORKER)
            throw new IllegalArgumentException("workerId out of range: " + workerId);
        this.workerId = workerId;
    }

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

        if (ts < lastTs) {                       // clock moved backwards
            long drift = lastTs - ts;
            if (drift > MAX_BACKWARD_MS)
                throw new IllegalStateException("Clock moved back " + drift + " ms; refusing");
            ts = waitUntil(lastTs);              // small drift: wait it out
        }

        if (ts == lastTs) {
            sequence = (sequence + 1) & SEQUENCE_MASK;
            if (sequence == 0) ts = waitUntil(lastTs + 1);   // 4096 used this ms
        } else {
            sequence = 0;
        }

        lastTs = ts;
        return ((ts - EPOCH) << (WORKER_BITS + SEQUENCE_BITS))
                | (workerId << SEQUENCE_BITS)
                | sequence;
    }

    private long waitUntil(long target) {
        long ts = System.currentTimeMillis();
        while (ts < target) {
            Thread.onSpinWait();
            ts = System.currentTimeMillis();
        }
        return ts;
    }

    public static long timestampOf(long id) { return (id >> 22) + EPOCH; }
    public static long workerOf(long id)    { return (id >> 12) & MAX_WORKER; }
    public static long sequenceOf(long id)  { return id & SEQUENCE_MASK; }

    public static void main(String[] args) {
        Snowflake gen = new Snowflake((3 << 5) | 17);
        java.util.Set<Long> seen = new java.util.HashSet<>();
        long prev = -1;
        for (int i = 0; i < 1_000_000; i++) {
            long id = gen.nextId();
            if (!seen.add(id) || id <= prev) throw new AssertionError("bad id " + id);
            prev = id;
        }
        long id = gen.nextId();
        System.out.println(id + " worker=" + workerOf(id) + " seq=" + sequenceOf(id)
                + " at=" + java.time.Instant.ofEpochMilli(timestampOf(id)));
    }
}

import threading
import time

EPOCH_MS = 1_704_067_200_000          # 2024-01-01T00:00:00Z
WORKER_BITS, SEQ_BITS = 10, 12
MAX_WORKER = (1 << WORKER_BITS) - 1
SEQ_MASK = (1 << SEQ_BITS) - 1
MAX_BACKWARD_MS = 5


class Snowflake:
    def __init__(self, worker_id: int):
        if not 0 <= worker_id <= MAX_WORKER:
            raise ValueError("worker_id out of range")
        self.worker_id = worker_id
        self.last_ts = -1
        self.seq = 0
        self.lock = threading.Lock()

    @staticmethod
    def _now() -> int:
        return time.time_ns() // 1_000_000

    def _wait_until(self, target: int) -> int:
        ts = self._now()
        while ts < target:
            ts = self._now()
        return ts

    def next_id(self) -> int:
        with self.lock:
            ts = self._now()
            if ts < self.last_ts:
                drift = self.last_ts - ts
                if drift > MAX_BACKWARD_MS:
                    raise RuntimeError(f"clock moved back {drift} ms")
                ts = self._wait_until(self.last_ts)
            if ts == self.last_ts:
                self.seq = (self.seq + 1) & SEQ_MASK
                if self.seq == 0:
                    ts = self._wait_until(self.last_ts + 1)
            else:
                self.seq = 0
            self.last_ts = ts
            return ((ts - EPOCH_MS) << (WORKER_BITS + SEQ_BITS)) | (self.worker_id << SEQ_BITS) | self.seq


def decode(i: int) -> dict:
    return {"ts_ms": (i >> 22) + EPOCH_MS, "worker": (i >> 12) & MAX_WORKER, "seq": i & SEQ_MASK}


if __name__ == "__main__":
    gen = Snowflake((3 << 5) | 17)
    ids = [gen.next_id() for _ in range(200_000)]
    assert len(set(ids)) == len(ids) and ids == sorted(ids)
    print(ids[-1], decode(ids[-1]))
    print(decode(367238578176462853))   # the dry-run ID

Things to point out when you write this in an interview: the lock (or a lock-free CAS on a packed state) is required because two threads could otherwise read the same lastTs and sequence; the sequence overflow path busy-waits for the next millisecond, which caps throughput at 4,096/ms instead of producing duplicates; and the IDs are strictly increasing per worker but only roughly ordered across workers.

A subtle problem: low-traffic sequences

If most milliseconds produce only one ID, the sequence is almost always 0, so IDs end in the same low bits. If you later shard by id % 16, every row goes to one shard. Fixes: shard by a hash of the ID, or start each new millisecond's sequence at a small random value. This is a nice detail to raise if sharding is part of the discussion; see sharding strategies explained.

Handling Clock Skew and Clocks Moving Backwards

Snowflake's uniqueness rests on one assumption: a worker never reuses a (timestamp, sequence) pair. A clock that jumps backwards breaks that. It happens more than you would expect: NTP corrections, VM live migration, leap-second handling, or an operator fixing a wrong system time.

Some variants borrow future time instead of waiting: when the sequence overflows they advance a logical timestamp beyond the wall clock and catch up later. This keeps latency flat under bursts but lets IDs run ahead of real time, which is fine as long as the drift is bounded and monitored.

Assigning Worker IDs in a Real Fleet

If two workers share a machine ID, they produce identical IDs within the same millisecond. With static servers you configure IDs by hand; in Kubernetes with autoscaling, pods come and go constantly. Options:

1. Coordination service lease. On startup, the worker creates an ephemeral sequential node in ZooKeeper or takes a lease key in etcd for the lowest free ID 0–1023. If the worker dies, its session expires and the ID frees up. Twitter's original Snowflake used ZooKeeper.
2. StatefulSet ordinal. Kubernetes StatefulSet pods are named idgen-0, idgen-1… Combine the ordinal with a cluster/region number for the datacenter bits.
3. Database registry. A table of (worker_id, host, heartbeat_at); claim a free row with a conditional update, refresh the heartbeat, reclaim rows not refreshed for several minutes.
4. Bigger machine field. Sonyflake uses 16 machine bits (often derived from the private IP's lower 16 bits), 8 sequence bits and a 39-bit timestamp in 10 ms units (about 174 years). More machines, fewer IDs per machine per time unit.

Danger case: a worker loses its lease because of a long GC pause but keeps running and generating IDs, while a new worker grabs the same ID. Defend by checking lease validity before generating and stopping generation if the lease could have expired.

Embedding the shard instead of the worker: Instagram's variant

Instagram described generating IDs inside PostgreSQL: 41 bits of milliseconds, 13 bits of logical shard ID and 10 bits from a per-shard sequence modulo 1,024. The ID itself tells you which shard holds the row, so routing needs no lookup. That is a useful trick whenever data is sharded by entity.

Comparison: Which ID Generator Should You Pick?

Deployment: Library or Service?

Embedded library: zero network hops, no extra service to run, but every pod needs a unique worker ID, and with thousands of pods across services you can exhaust 1,024 IDs. Central ID service: a handful of replicas own the worker IDs; callers fetch IDs over gRPC, ideally in batches of 100–1,000 to amortise the hop. It is simpler to operate worker IDs and clock monitoring, at the cost of a network dependency on the write path. Many companies start with a library and move to a service when pod counts grow.

How This Question Shows Up in Interviews

It appears standalone ("design an ID generator for a distributed system") and embedded in larger designs: short-code generation in a URL shortener, message IDs in chat, tweet IDs in a news feed design, or partition keys in a distributed key-value store.

Follow-ups you should be ready for

• "What happens at 4,097 requests in one millisecond?" The worker waits for the next millisecond. If that is too slow, add workers or borrow sequence bits from the machine field.
• "Why not just use UUIDs?" 128 bits doubles index size, v4 is unordered; v7 fixes ordering but not size. Fine if the interviewer does not need 64-bit.
• "Can users guess IDs?" Yes, Snowflake IDs are predictable and leak creation time. Never rely on ID secrecy for authorisation; check ownership on every request.
• "How does the frontend handle these IDs?" Send them as strings in JSON. JavaScript numbers lose precision above 2⁵³ (9,007,199,254,740,992), and Snowflake IDs exceed that quickly.
• "Multi-region?" Allocate datacenter bits per region, so regions never collide, and accept that cross-region ordering is approximate.

Red flags interviewers notice

• Choosing Math.random() or timestamp alone as the ID.
• Drawing a central "ID database" that every write calls synchronously, with no batching.
• Saying Snowflake IDs are "globally strictly ordered".
• Not knowing what limits the design: 41 bits of time, 10 bits of workers, 12 bits of sequence.
• Ignoring clocks entirely. The clock is the most fragile component in the whole design.

A strong five-minute answer: state requirements, dismiss auto-increment and UUID v4 with one reason each, draw the 64-bit layout with the 69-year and 4-million-per-second numbers, describe the clock-backwards and worker-ID solutions, and mention v7 as the low-infrastructure alternative. That covers everything an interviewer usually wants to hear.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.