System Design: Design a Unique ID Generator

Every system needs unique identifiers — user IDs, order IDs, message IDs. A single database’s AUTO_INCREMENT works until you shard or replicate. Then you need a strategy that generates globally unique IDs across multiple machines without coordination bottlenecks.

Requirements

• Unique: no two IDs ever collide, even across data centers.
• Sortable by time: IDs generated later should sort after earlier ones (useful for pagination and time-range queries).
• High throughput: generate 10,000+ IDs per second per machine.
• Low latency: ID generation should add under 1ms to a request.
• Compact: fit in a 64-bit integer (8 bytes) for efficient storage and indexing.

Approach 1: UUID

A UUID (v4) is a 128-bit random identifier: 550e8400-e29b-41d4-a716-446655440000.

UUID works for systems where sortability doesn’t matter and storage overhead is acceptable.

Approach 2: Database Ticket Server

Use a dedicated database with AUTO_INCREMENT as an ID service. Flickr popularized this with two ticket servers for redundancy.

Server 1: generates 1, 3, 5, 7, ...  (odd)
Server 2: generates 2, 4, 6, 8, ...  (even)

This works for moderate scale but becomes a bottleneck at high throughput.

Approach 3: Twitter Snowflake

Snowflake is the industry standard for 64-bit, time-sortable, distributed IDs. Each ID encodes the timestamp, machine identity, and a sequence number.

┌───┬──────────────────────────┬──────────┬──────────────┐
│ 0 │    Timestamp (41 bits)   │ Machine  │  Sequence    │
│   │    milliseconds since    │ ID (10)  │  number (12) │
│   │    custom epoch          │          │              │
└───┴──────────────────────────┴──────────┴──────────────┘
1b         41 bits               10 bits    12 bits

1 bit: sign (always 0)
41 bits: milliseconds since epoch → ~69 years
10 bits: machine ID → 1024 machines
12 bits: sequence → 4096 IDs per millisecond per machine

import time

class SnowflakeGenerator:
    def __init__(self, machine_id, epoch=1700000000000):
        self.machine_id = machine_id & 0x3FF  # 10 bits
        self.epoch = epoch
        self.sequence = 0
        self.last_timestamp = -1

    def _current_millis(self):
        return int(time.time() * 1000)

    def generate(self):
        timestamp = self._current_millis()

        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & 0xFFF  # 12 bits
            if self.sequence == 0:
                while timestamp <= self.last_timestamp:
                    timestamp = self._current_millis()
        else:
            self.sequence = 0

        self.last_timestamp = timestamp
        adjusted = timestamp - self.epoch

        return (adjusted << 22) | (self.machine_id << 12) | self.sequence

gen = SnowflakeGenerator(machine_id=1)
for _ in range(5):
    print(gen.generate())

Throughput: 4096 IDs/ms × 1024 machines = ~4 billion IDs/second across the cluster.

Sortability: since timestamp occupies the most significant bits, IDs are roughly time-ordered. IDs from different machines in the same millisecond aren’t strictly ordered, but they’re close enough for practical use.

Approach 4: ULID

ULID (Universally Unique Lexicographically Sortable Identifier) is a 128-bit ID that’s Crockford Base32 encoded: 01ARZ3NDEKTSV4RRFFQ69G5FAV.

 48 bits: timestamp (millisecond precision)
 80 bits: randomness

ULID is great when you want sortability without managing machine IDs and can accept 128-bit identifiers.

Handling Clock Skew

Snowflake’s correctness depends on monotonic timestamps. If a machine’s clock jumps backward (NTP adjustment), you could generate duplicate IDs.

Mitigations:

• Reject requests during clock rollback (the simple approach — Twitter does this).
• Wait until the clock catches up to the last seen timestamp.
• Use a logical clock that only increments, independent of wall time.

In practice, NTP adjustments are small (milliseconds), so rejecting requests during rollback causes negligible downtime.

Comparison Summary

Interview Tips

• Start by asking what properties the ID needs: uniqueness? sortability? compactness? This shows you design to requirements.
• If the interviewer says “64-bit, sortable, distributed” — go straight to Snowflake.
• Discuss clock skew proactively — it’s the main failure mode and interviewers want to hear you address it.
• Mention that Snowflake IDs are extractable: you can derive the timestamp and machine ID from any ID, which is useful for debugging.
• If asked about the custom epoch, explain that it maximizes the 41-bit timestamp range. Starting from Unix epoch 1970 wastes bits on decades of irrelevant history.