Design a Unique ID Generator

Generating unique IDs sounds trivial until you remove the single database that was quietly handing out auto-increment values. In a distributed system with hundreds of services creating rows, events, and messages, you need IDs that are unique across the whole fleet, cheap to generate, and — ideally — sortable by creation time. This is a compact, high-signal interview question because the “obvious” answers each fail a specific requirement, and the good answer (Snowflake) is elegant.

Understanding the Problem

Functional Requirements

• Globally unique: No two IDs ever collide, across all machines, forever.
• Roughly time-sortable: IDs generated later should sort after earlier ones. This makes database indexes efficient and lets you order records without a separate timestamp column.
• Numeric / compact: Prefer a 64-bit integer. It is small, index-friendly, and fast to compare — unlike a 128-bit string.

Non-Functional Requirements

• High throughput: Tens of thousands to millions of IDs per second across the fleet.
• Low latency: ID generation must be effectively free — a local operation, not a network round trip.
• High availability: No single point of failure. One dead machine must not stop ID generation anywhere else.
• No coordination per ID: Talking to a central service for every ID does not scale.

The tension is between uniqueness (easiest with central coordination) and scalability / availability (easiest with no coordination). The whole design is about resolving that tension.

Core Entities and APIs

API Design

nextId() -> int64        # Local call, no network, returns a unique 64-bit ID

That is the entire interface. The interesting part is what happens behind it.

The approaches, compared

High-Level Design

The generator is an embedded library inside every service process that needs IDs. That is what makes nextId() a local call: no network hop, and no shared service that can go down. The alternative is a standalone ID service (a small fleet that hands out IDs, often in batches) when many languages need the same scheme or there are more short-lived processes than the 1024 machine ids allow. It is the same Snowflake logic behind a network call, with an extra dependency.

Each generator has three parts:

• Machine id assignment: at startup the node claims a unique 10-bit id from a coordinator (ZooKeeper/etcd) and holds it with an ephemeral lease.
• Clock source: the local wall clock in milliseconds, kept in line by NTP and guarded against moving backwards.
• Sequence counter: an in-memory 12-bit counter that resets every millisecond.

  ┌────────────────────────┐
  │ ZooKeeper / etcd       │   claim machine id at startup,
  │ (machine id pool)      │   renew lease periodically
  └───────────▲────────────┘   (never per ID)
              │
  ┌───────────┴──────────────────────────────────┐
  │ Service process                              │
  │                                              │
  │  app code ──nextId()──►  Snowflake library   │
  │           ◄──int64 ID──  ├─ machine id (10b) │
  │                          ├─ clock (ms, 41b)  │◄── NTP
  │                          └─ sequence  (12b)  │
  └──────────────────────────────────────────────┘

Request flow: the caller invokes nextId(); the library reads the clock; if it is still the same millisecond it increments the sequence (waiting for the next millisecond if all 4096 are used), otherwise resets it to 0; then it shifts timestamp, machine id and sequence into one 64-bit integer. The coordinator is touched only at startup and lease renewal, never per ID, so a coordinator outage stops new nodes from joining but does not stop running nodes, which keep generating IDs as long as their lease is valid.

Deep Dive: Why the Simple Answers Fall Short

UUID v4

A 122-bit random number. The collision probability is negligible, and it needs zero coordination — any machine can mint one locally. So why not stop here?

• Not sortable. Random bits mean two IDs created a second apart have no order relationship.
• Poor index locality. Inserting random keys into a B-tree scatters writes across the whole index, causing page splits and cache misses. On a large table this measurably hurts insert throughput.
• 128 bits. Twice the storage of a 64-bit integer in every index and foreign key.

UUIDs are a fine default when you truly need zero coordination and do not care about ordering (e.g. idempotency keys). They are a poor primary key at scale.

Database ticket server

Use a dedicated table whose auto-increment column hands out IDs. Sortable and simple — but it is a single point of failure and a write bottleneck: every ID is a database round trip.

The classic scaling trick (used by Flickr) is multiple ticket servers with stepped sequences. With two servers:

Server A: starts at 1, step 2  →  1, 3, 5, 7, ...
Server B: starts at 2, step 2  →  2, 4, 6, 8, ...

Now one server can die without halting ID generation, and load is split. But it still involves a network call per ID (or per batch), and extending it is awkward. It is a reasonable mid-scale answer; Snowflake is better.

Deep Dive: Snowflake

Twitter’s Snowflake is the canonical solution. It packs three things into a single 64-bit integer so that generation is a purely local operation, yet IDs are globally unique and time-ordered.

| 1 bit  | 41 bits            | 10 bits     | 12 bits    |
| sign   | timestamp (ms)     | machine id  | sequence   |
| (0)    | since custom epoch | 0–1023      | 0–4095     |

• 1 sign bit — always 0, keeps the number positive.
• 41-bit timestamp — milliseconds since a custom epoch. 2⁴¹ ms ≈ 69 years of IDs.
• 10-bit machine id — up to 1024 generator nodes.
• 12-bit sequence — a per-millisecond counter: 4096 IDs per millisecond per machine.

That yields 4096 × 1000 ≈ 4 million IDs per second per machine, and over 4 billion/sec across a full fleet — with no coordination on the hot path.

The generation logic

class Snowflake:
    EPOCH = 1700000000000          # custom epoch (ms)
    MACHINE_BITS = 10
    SEQUENCE_BITS = 12
    MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1   # 4095

    def __init__(self, machine_id: int):
        self.machine_id = machine_id          # 0..1023, assigned at startup
        self.sequence = 0
        self.last_ts = -1

    def next_id(self) -> int:
        ts = self._now()
        if ts == self.last_ts:
            # Same millisecond: increment the sequence
            self.sequence = (self.sequence + 1) & self.MAX_SEQUENCE
            if self.sequence == 0:            # sequence exhausted this ms
                ts = self._wait_next_ms(self.last_ts)
        else:
            self.sequence = 0                 # new millisecond, reset
        self.last_ts = ts
        return ((ts - self.EPOCH) << (self.MACHINE_BITS + self.SEQUENCE_BITS)) \
             | (self.machine_id << self.SEQUENCE_BITS) \
             | self.sequence

Why the timestamp goes first

Putting the timestamp in the high bits is the key trick: when you sort IDs numerically, you are sorting (approximately) by creation time. This gives:

• Rough time-ordering for free — no separate created_at needed for coarse ordering.
• Index locality — new IDs are monotonically increasing, so inserts append to the right edge of a B-tree index instead of scattering (the exact problem UUIDs cause).

“Roughly” is honest: two IDs from different machines in the same millisecond can tie or invert, because the machine id, not sub-millisecond time, breaks the tie. Snowflake gives approximate global ordering, which is almost always what you actually need.

Deep Dive: The Operational Gotchas

Snowflake’s elegance hides two real-world hazards an interviewer will probe.

Assigning machine ids

Every generator needs a unique 10-bit id. Hand-configuring 1024 machines is error-prone, so assign them dynamically from a coordination service:

• ZooKeeper / etcd: each node claims an unused id from a shared pool at startup and holds it via an ephemeral lease; on crash the lease expires and the id is reclaimable.
• In cloud environments you can derive it from a stable attribute (e.g. a slice of the instance id), as long as uniqueness is guaranteed.

A duplicate machine id is catastrophic — two machines minting the same IDs — so this must be enforced, not assumed.

Clock skew and backwards time

The timestamp comes from the machine’s wall clock, which can move backwards (NTP correction, VM pause/migration). If now() is less than the last timestamp used, naively continuing could regenerate IDs you already issued.

    def _now(self) -> int:
        ts = current_millis()
        if ts < self.last_ts:
            drift = self.last_ts - ts
            if drift <= MAX_BACKWARD_MS:       # tiny skew: wait it out
                ts = self._wait_until(self.last_ts)
            else:
                raise ClockMovedBackwards(drift)  # refuse, alert, do not emit
        return ts

The safe rule: never emit an ID with a timestamp earlier than one already used. For small backward jumps, block until the clock catches up. For large jumps, fail loudly rather than risk duplicates. Keep clocks disciplined with NTP, and avoid leap-second surprises.

Key Takeaways

1. State the tension first. Uniqueness is easy with central coordination; scalability and availability are easy without it. The design resolves that trade-off.

2. Know why the simple answers lose. UUIDv4: no coordination but unsortable and index-hostile. DB ticket server: sortable but a bottleneck/SPOF (mitigated, not fixed, by stepped multi-servers).

3. Snowflake is the standard answer. 64 bits = sign + 41-bit timestamp + 10-bit machine id + 12-bit sequence. Local generation, 4096 IDs/ms/node, ~69 years of range, no per-ID coordination.

4. Timestamp in the high bits buys ordering and index locality — monotonic inserts instead of the random scatter UUIDs cause. Ordering is approximate across machines, which is fine.

5. Respect the operational edges. Assign unique machine ids via ZooKeeper/etcd, and never let the clock moving backwards produce a duplicate — wait for small skew, fail loudly on large skew.

Snowflake-style IDs underpin databases, message systems, and object stores across the industry precisely because they deliver uniqueness, ordering, and compactness without a coordinator on the critical path.