Theory
Distributed Unique ID Generator (Snowflake)
📋 Overview
In a distributed system, generating unique, time-sortable IDs at scale is a critical requirement. A centralized database auto-increment is a bottleneck and a single point of failure. Solutions like Twitter's Snowflake algorithm provide a way to generate 64-bit, unique, and roughly time-ordered IDs across thousands of nodes without coordination.
🏗️ Core Principles & Characteristics
- The 64-Bit Structure:
- Sign Bit (1 bit): Reserved for future use.
- Timestamp (41 bits): Milliseconds since a custom epoch (provides ~69 years of IDs).
- Machine ID (10 bits): Unique ID for the specific server/datacenter (supports 1,024 nodes).
- Sequence (12 bits): A local counter for IDs generated in the same millisecond (supports 4,096 IDs per ms per node).
- Time-Sortable: Because the most significant bits are the timestamp, IDs are naturally sortable by time.
- No Coordination: Each node generates IDs independently using its pre-assigned Machine ID.
⚖️ Trade-offs: Pros & Cons
Pros
- High Throughput: Can generate millions of IDs per second across a cluster.
- Efficiency: 64-bit integers are much smaller and faster to index than 128-bit UUID strings.
- Sortability: Helps maintain database index performance (B-Tree locality) compared to random UUIDs.
Cons
- Clock Dependency: If a server's clock drifts significantly or moves backward (NTP sync), it can generate duplicate IDs.
- Machine ID Management: Requires a mechanism (like Zookeeper or etcd) to assign and track unique machine IDs to each node.
- Unpredictability: While time-ordered, IDs are not perfectly sequential, which might be a requirement for some legacy systems.
🌍 Real-World Implementation
- Twitter (Snowflake): The original implementation for generating Tweet IDs.
- Discord: Using a variant of Snowflake for messages, users, and server IDs.
- Instagram: Using a similar logical shard-based ID generation in PostgreSQL.
- E-commerce (Order IDs): Generating unique, non-guessable but sortable IDs for customer orders.
💡 Interview "Gotchas" & Tips
- UUID vs. Snowflake: UUID (128-bit) is easier but slow for DB indexing. Snowflake (64-bit) is optimized for performance and storage.
- The Clock Drift Problem: Explain how to handle clock skew (e.g., the generator service should refuse to generate IDs until the clock catches up).
- Base62 Encoding: Often, these numeric IDs are converted to Base62 (e.g.,
5fG3zL) for use in public-facing URLs (like YouTube video IDs).
📐 Suggested Architecture Primitives
- Zookeeper/etcd: For distributed coordination and Machine ID assignment.
- NTP (Network Time Protocol): To keep server clocks synchronized.
- Snowflake Algorithm: The logic for bit-shifting and masking to create the ID.
Canvas