Design a Unique ID Generator in Distributed Systems

Traditional auto_increment doesn't work in distributed environments: a single DB server can't handle the scale, and generating unique IDs across multiple DBs with minimal delay is challenging.

Step 1 of 4: Understand the problem and establish design scope #

Goal: pin down the ID requirements before choosing an approach.

Requirements:

1. IDs must be unique
2. IDs must be sortable (increment by time, not necessarily by 1)
3. IDs are numerical values only
4. IDs fit into 64-bit
5. IDs ordered by date (evening IDs > morning IDs from the same day)
6. Generate over 10,000 unique IDs per second

Step 2 of 4: Propose high-level design and get buy-in #

Goal: compare the 4 standard approaches, then pick snowflake.

Approach 1: Multi-master replication #

Uses database auto_increment but increments by k (number of DB servers) instead of 1. Server 1: 1, 3, 5, ...; Server 2: 2, 4, 6, ...

Pros: some scalability. Cons: hard to scale with multiple data centers; IDs don't increase with time across servers; doesn't scale well when servers are added/removed.

Approach 2: UUID #

128-bit number, collision probability extremely low (1 billion UUIDs/sec for ~100 years → 50% chance of a single duplicate). Example: 09c93e62-50b4-468d-bf8a-c07e1040bfb2

Each web server generates IDs independently: no coordination needed.

Pros: simple, no synchronization issues, easy to scale. Cons: 128 bits (requirement is 64 bits); IDs don't go up with time; IDs could be non-numeric.

Approach 3: Ticket server #

Centralized auto_increment in a single DB server (Flickr approach).

Pros: numeric IDs, easy to implement, works for small/medium scale. Cons: single point of failure; multiple ticket servers introduce data synchronization challenges.

Approach 4: Twitter snowflake (chosen) #

Divide a 64-bit ID into sections:

Step 3 of 4: Design deep dive #

Goal: understand the bit budget: what limits each section.

Timestamp: 41 bits → max timestamp = 2^41 − 1 = 2,199,023,255,551 ms ≈ 69 years from the custom epoch. After 69 years, a new epoch time or migration is needed.

Sequence number: 12 bits = 2^12 = 4,096 combinations. Max 4,096 new IDs per millisecond per machine. Field is 0 unless >1 ID is generated in the same millisecond on the same server.

Datacenter IDs and machine IDs: chosen at startup, fixed while running. Changes require careful review to avoid ID conflicts.

Step 4 of 4: Wrap up #

Approaches evaluated: multi-master replication, UUID, ticket server, Twitter snowflake. Snowflake chosen: supports all requirements and is scalable in distributed environments.

Additional talking points:

1. Clock synchronization: ID generators on multiple cores/machines may have different clocks. Network Time Protocol (NTP) is the most popular solution
2. Section length tuning: fewer sequence bits + more timestamp bits for low-concurrency, long-term applications
3. High availability: the ID generator is mission-critical: must be highly available