Design a Distributed Unique ID Generator
Design a globally distributed unique ID generation service (similar to Twitter Snowflake). Generated IDs must be 64-bit integers, globally unique, roughly time-sortable, and generated at high scale without cross-node network coordination.
Requirements
- ✓IDs must be globally unique across all nodes.
- ✓IDs must fit into a 64-bit integer (int64) for database index efficiency.
- ✓IDs must be roughly chronological / time-sortable.
- ✓High availability: service must generate at least 10,000 IDs per second per node with sub-millisecond latency.
- ✓No single point of failure and no runtime consensus round-trips (Paxos/Raft) in the ID generation path.
Constraints & Scale
- —64 bits maximum.
- —System lifetime: at least 50 years before epoch overflow.
- —Clock synchronization: tolerate minor NTP clock drift without generating duplicate IDs.
Understand
Guided mode
Why are UUID v4 unsuitable for high-throughput primary keys? Why is a centralized auto-increment database counter a bottleneck?
Context & Constraints — Human Reviewed
UUID v4 is 128-bit and non-sequential, causing B-tree fragmentation, page splits, and cache misses in database indexes. Centralized DB auto-increment introduces a single write bottleneck and single point of failure.
Trade-offs
- ⚖UUID v4: fully distributed, zero coordination, but 128-bit non-sequential degrades DB indexing.
- ⚖Centralized DB counter (Ticket Server): simple and sequential, but single point of failure and latency bottleneck.
- ⚖Snowflake 64-bit scheme: 64-bit, time-sortable, decentralized, but depends on system clock stability.
Concepts used in this stage