Design Unique ID Generator

Each machine can produce 4,096 IDs per millisecond (12-bit sequence). With 1,024 machines (10-bit machine_id), the system yields 4,096 x 1,024 x 1,000 = ~4.2 billion IDs/sec theoretical max. In practice, 1M+/sec sustained is the target.

A 41-bit timestamp in milliseconds covers 2^41 ms = ~69.7 years from a custom epoch. IDs are 64 bits = 8 bytes; base62-encoded they become ~11 characters.

The ID service is stateless per-request — each instance holds only its machine_id and a local clock + sequence counter. No database, no network call on the hot path.

• ID Service instances: one per application host (or sidecar). Generates IDs locally with zero network overhead.
• Zookeeper / etcd: assigns unique machine_ids on startup. Only needed at boot, not on the hot path.
• Alternative — Ticket Servers: dual-MySQL with odd/even auto-increment (Flickr's design). Centralized but simpler; acceptable at lower scale.

Snowflake (Twitter, 2010). The canonical design: 1 sign bit + 41-bit timestamp (ms since custom epoch, ~69 years) + 10-bit machine_id (1,024 machines) + 12-bit sequence (4,096 IDs per ms per machine). Total: 64 bits. IDs are k-sortable because the timestamp occupies the most-significant bits. Each machine generates IDs independently; the machine_id guarantees no collisions across hosts.

ULID (Universally Unique Lexicographically Sortable Identifier). 128 bits: 48-bit timestamp (ms, ~8,919 years) + 80-bit cryptographically random tail. No machine registration needed — randomness provides uniqueness. Tradeoff: slight collision probability (birthday problem at ~2^40 IDs/ms, negligible in practice). Encodes to 26 chars Crockford base32.

UUID v7 (RFC 9562). 128-bit, timestamp-first layout for B-tree index friendliness. Replaces UUID v4's fully-random approach with time-ordered prefix. Wider than Snowflake (128 vs 64 bits) but standardized and needs no coordinator.

Ticket Servers (Flickr, 2010). Two MySQL instances: one auto-increments by 2 starting at 1 (odd), the other starting at 2 (even). App round-robins between them. Simple, no clock dependency, but centralized — each MySQL is a SPOF risk. Flickr ran this in production for years.

Clock skew handling. Snowflake relies on the local clock. If NTP corrects the clock backward, the generator would produce IDs with a past timestamp — risking duplicates. Defense: if current_ms < last_ms, either refuse to generate (throw error) or spin-wait until the clock catches up. Critical invariant: never generate an ID with a timestamp older than the last generated ID.

sequenceDiagram
    participant App as Application
    participant Gen as ID Generator
    participant Clk as System Clock

    App->>Gen: generate_id()
    Gen->>Clk: current_time_ms()
    Clk-->>Gen: timestamp
    alt same ms as last call
        Gen->>Gen: sequence++
        alt sequence > 4095
            Gen->>Gen: spin-wait for next ms
            Gen->>Clk: current_time_ms()
            Clk-->>Gen: new timestamp
            Gen->>Gen: sequence = 0
        end
    else new ms
        Gen->>Gen: sequence = 0
    end
    Gen->>Gen: compose: sign|timestamp|machine|seq
    Gen-->>App: 64-bit ID
    App->>App: base62_encode(id) for URL use
          

1. Start with requirements, not solutions. Ask: how many IDs/sec? Must they be sortable? How compact? 64-bit or 128-bit acceptable? This shapes the entire design.
2. Draw the bit layout. Literally sketch 1 + 41 + 10 + 12 = 64 on the whiteboard. Interviewers love seeing the tradeoff between timestamp range, machine count, and per-ms throughput.
3. Address clock skew proactively. Mention NTP backward jump before being asked. The defense (refuse or wait) shows you understand the real-world failure mode that trips up Snowflake.
4. Know the alternatives. Snowflake vs ULID vs UUID v7 vs Ticket Server. Each has a sweet spot. Naming all four and their tradeoffs demonstrates breadth.
5. Mention base62 encoding. 64-bit integer to ~11-char URL-safe string. Shows you think about the consumer of IDs, not just the generator.