Designing a Distributed Unique ID Generator

⚡ Difficulty: Beginner 📋 Prerequisites: System Design Fundamentals ⏱️ Reading time: 10 min 🏢 Asked at: Twitter, Discord, Instagram, Amazon, Flipkart

TL;DR

Every distributed system needs unique IDs — for users, orders, messages, posts. A single auto-increment DB column breaks at scale. This design explores 4 approaches: UUID, database sequences, Snowflake IDs, and range-based allocation.

flowchart LR
    SVC["Any Service<br/>needs an ID"]:::service
    IDG["ID Generator"]:::service
    DB[("Optional DB<br/>for coordination")]:::data

    SVC --> IDG
    IDG --> DB

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

In 2 sentences: Generate globally unique, roughly time-sorted, 64-bit IDs without a single point of failure. Twitter’s Snowflake approach (timestamp + machine ID + sequence) is the industry standard for most use cases.

Understanding the Problem

Almost every system needs unique identifiers. User IDs, order IDs, message IDs, transaction IDs — they must be globally unique across all servers, ideally sortable by creation time, and generated with extremely low latency (< 1ms). The challenge is generating these at scale (10K-100K IDs/sec) across multiple machines without coordination or collisions.

Prior Art We’re Drawing From

• Twitter Snowflake — The original distributed ID generator. 64-bit IDs composed of timestamp + datacenter + machine + sequence. Open-sourced in 2010, now the de facto standard. (Twitter Engineering Blog)
• Instagram Sharded IDs — Modified Snowflake using Postgres schemas to embed shard information into IDs. Generates IDs at the DB layer without a separate service. (Instagram Engineering)
• Discord Snowflakes — Twitter Snowflake adapted for Discord with epoch starting at Discord’s launch date. Used for messages, users, channels. (Discord Developer Docs)
• MongoDB ObjectId — 12-byte ID with timestamp + random + counter. No central coordination needed. Demonstrates the random + counter hybrid approach. (MongoDB Docs)

Naive First Cut

flowchart LR
    S1["Server 1"]:::service
    S2["Server 2"]:::service
    DB[("Single DB<br/>AUTO_INCREMENT")]:::data

    S1 --> DB
    S2 --> DB

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Just use AUTO_INCREMENT in a single MySQL/Postgres table.

Why this breaks:

• Single point of failure — if the DB goes down, no service can generate IDs
• Bottleneck — all ID generation is serialized through one DB
• Can’t scale horizontally — adding more app servers doesn’t help, the DB is the limit
• Sequential and guessable — exposes total count, easy to scrape
• Cross-datacenter latency — if services are in multiple regions, every ID requires a round-trip to one DB

The rest of the doc explores 4 production-ready alternatives.

Functional Requirements

Core

1. Generate globally unique IDs — no two IDs should ever collide across all services and servers
2. IDs must be 64-bit numeric — fits in a long/bigint, can be used as primary keys and sorted efficiently
3. Roughly time-ordered — IDs generated later should be larger than IDs generated earlier (enables range queries and chronological sorting)

Below the Line

• Human-readable (short URLs, display-friendly)
• Cryptographically unpredictable
• Embeddable shard/partition information
• Custom epoch support

Non-Functional Requirements

Core Entities

• ID — the 64-bit unique identifier itself
• Node — a machine/process that generates IDs (identified by a machine ID)
• Timestamp — millisecond-precision time component within the ID
• Sequence — per-node counter that resets each millisecond

The 4 Approaches

Approach 1: UUID

550e8400-e29b-41d4-a716-446655440000

128-bit random identifier. No coordination needed — any server can generate one independently.

Verdict: Use for cases where time-ordering doesn’t matter and you don’t need compact IDs (e.g., idempotency keys, distributed trace IDs).

Approach 2: Database Ticket Server

Two (or more) databases that hand out IDs from disjoint ranges.

flowchart LR
    SVC["Service"]:::service
    DB1["Ticket Server 1<br/>IDs: 1 3 5 7 ..."]:::data
    DB2["Ticket Server 2<br/>IDs: 2 4 6 8 ..."]:::data

    SVC --> DB1
    SVC --> DB2

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Server 1 increments by 2 starting at 1. Server 2 increments by 2 starting at 2. No collisions.

Verdict: Works for small-medium scale. Flickr used this pattern. But inflexible when adding/removing nodes.

Approach 3: Snowflake (Industry Standard)

A 64-bit ID composed of multiple fields packed into a single long integer.

| 1 bit unused | 41 bits timestamp | 5 bits datacenter | 5 bits machine | 12 bits sequence |

flowchart LR
    subgraph "64-bit Snowflake ID"
        A["0"]:::client
        B["41 bits<br/>timestamp ms"]:::edge
        C["5 bits<br/>datacenter"]:::service
        D["5 bits<br/>machine"]:::service
        E["12 bits<br/>sequence"]:::data
    end

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#60a5fa,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

How it works:

1. 41 bits for timestamp — milliseconds since a custom epoch (e.g., Twitter uses Nov 4, 2010). Gives ~69 years of IDs before overflow.
2. 5 bits datacenter ID — supports 32 datacenters
3. 5 bits machine ID — supports 32 machines per datacenter (1024 total nodes)
4. 12 bits sequence — counter per millisecond per machine. Supports 4096 IDs/ms/machine = 4 million IDs/sec per machine

Why this is great:

• No coordination — each machine generates independently using its own machine ID
• Time-sorted — IDs increase over time (timestamp is the most significant bits)
• 64-bit — fits in a bigint, great index performance
• High throughput — 4M IDs/sec per node without any network calls
• Unique — machine ID + sequence guarantees no collision within the same millisecond

Clock skew handling: If the system clock moves backward (NTP correction), either wait until the clock catches up, or refuse to generate IDs until the clock advances past the last timestamp used. Twitter’s Snowflake logs an error and waits.

Approach 4: Range-Based Allocation

A central service pre-allocates ID ranges to application servers. Each server generates IDs from its range without further coordination.

flowchart LR
    ALLOC["Range Allocator<br/>central service"]:::async
    S1["Server 1<br/>range: 1-1000"]:::service
    S2["Server 2<br/>range: 1001-2000"]:::service
    S3["Server 3<br/>range: 2001-3000"]:::service

    ALLOC --> S1
    ALLOC --> S2
    ALLOC --> S3

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef async fill:#3b1f5e,stroke:#c084fc,color:#e2e8f0

How it works:

1. Central allocator (backed by a DB) hands out ranges of 1000 or 10000 IDs at a time
2. Each app server increments locally within its range — zero network calls per ID
3. When a range is exhausted, fetch a new range from the allocator
4. If a server crashes mid-range, those unused IDs are simply wasted (acceptable)

Comparison Table

Recommended: Snowflake Implementation

For most interview answers, Snowflake is the go-to. Here’s the generation flow:

sequenceDiagram
    participant App as Application
    participant Gen as ID Generator (local)
    participant Clock as System Clock

    App->>Gen: generateId()
    Gen->>Clock: currentTimeMillis()
    Clock-->>Gen: timestamp
    Gen->>Gen: check if same ms as last ID
    alt Same millisecond
        Gen->>Gen: increment sequence
    else New millisecond
        Gen->>Gen: reset sequence to 0
    end
    Gen->>Gen: compose: timestamp | datacenter | machine | sequence
    Gen-->>App: 64-bit unique ID

No network calls. No DB lookups. Pure local computation.

Deep Dives

Deep Dive 1: Machine ID Assignment

Problem: Each node needs a unique machine ID (10 bits = 1024 possible). How do you assign these without collisions?

Bad: Hardcode machine IDs in config files. Error-prone, doesn’t work with auto-scaling.

Good: Use ZooKeeper or etcd. Each node claims a sequential ID on startup via an ephemeral node. If the node dies, the ID is released.

Great: Use the network interface MAC address or container hostname hash to derive a machine ID. No external dependency. Combine with a startup registration check to verify uniqueness.

Deep Dive 2: Clock Skew

Problem: NTP can adjust the system clock backward. If timestamp decreases, two IDs could have the same timestamp + sequence = collision.

Bad: Ignore it. Hope clocks are always correct.

Good: Detect backward clock movement. If clock goes back, wait (spin) until it catches up to the last known timestamp. Refuse to generate IDs during the wait.

Great: Use a logical clock component. Track lastTimestamp. If currentTime < lastTimestamp, either wait OR use the sequence bits more aggressively by continuing to increment from the last sequence value (borrowing from the future). Twitter’s approach: log an error and wait.

Deep Dive 3: Scaling Beyond 4M IDs/sec

Problem: One node generates 4M IDs/sec. What if you need 100M/sec?

Bad: Make the sequence field larger (fewer bits for timestamp → shorter lifespan).

Good: Run multiple generator instances (10 machines × 4M/sec = 40M/sec). The datacenter + machine bits already support 1024 nodes.

Great: For extreme scale, use the range-based approach as a hybrid. Pre-allocate Snowflake machine IDs dynamically and run hundreds of lightweight generator threads, each with its own machine ID.

Interview Cheat Sheet

What’s Expected at Each Level

Mid-level

Know that auto-increment doesn’t scale. Propose UUID or Snowflake. Explain the Snowflake bit layout and why 64-bit time-sorted IDs are preferred over 128-bit random UUIDs for database primary keys. Understand the trade-offs table.

Senior

Drive the discussion on clock skew handling, machine ID assignment strategies, and when to choose Snowflake vs range-based allocation. Discuss the index performance implications of random vs sequential IDs. Know that Twitter, Discord, and Instagram all use Snowflake variants.

Staff+

Discuss multi-region ID generation with region bits, capacity planning for the 69-year timestamp limit, and hybrid approaches for extreme throughput. Address the operational burden of ZooKeeper for machine ID assignment vs stateless alternatives. Cover how Snowflake IDs leak creation time (privacy concern for some products).

🎯 Key Takeaways

• Auto-increment is the naive solution — breaks at scale, SPOF, guessable
• Snowflake is the industry standard — 64-bit, time-sorted, no coordination, 4M IDs/sec/node
• UUID when ordering doesn’t matter — trace IDs, idempotency keys
• Range allocation for extreme scale — Google Spanner pattern, trades ordering for simplicity
• Clock skew is the main operational risk — detect and wait is the standard mitigation

Related Designs

• URL Shortener — uses Base62 ID generation for short links
• Pastebin — unique ID generation for paste URLs
• Key-Value Store — consistent hashing uses similar partitioning concepts