Distributed ID Generation
What you'll learn: How to generate unique, non-colliding IDs across multiple servers without coordinating every request.
When building a URL shortener at scale, a single database auto-increment counter becomes a bottleneck. You need multiple servers generating IDs simultaneously without duplicates—but coordinating between servers for every ID defeats the purpose of distribution.
The Core Problem
If Server A generates ID 12345 at the same moment Server B does, you have a collision. Traditional database sequences work fine for one server, but require coordination (locks, consensus) across many servers, introducing latency and complexity.
Solution 1: Snowflake IDs
Twitter's Snowflake approach packs a 64-bit ID with:
- Timestamp (41 bits): milliseconds since epoch
- Machine ID (10 bits): which server generated this
- Sequence (12 bits): counter within the same millisecond
Each server gets a unique machine ID. Within a millisecond, a server can generate 4,096 unique IDs. Since timestamp and machine ID differ, IDs never collide across servers.
Analogy: Think of airport codes. Each airport (server) has a unique 3-letter code. Flight numbers can repeat across airports, but "LAX 237" never conflicts with "JFK 237."
Solution 2: ID Ranges
Pre-allocate ranges to each server: Server 1 gets 1-1,000,000, Server 2 gets 1,000,001-2,000,000. Simple, but requires coordination when ranges exhaust and doesn't scale dynamically.
Solution 3: Database Sequences with Gaps
Use multiple databases with different offsets and increments. DB1 generates 1, 4, 7... while DB2 generates 2, 5, 8... Gaps exist, but no collisions.
Key Takeaway: Distributed ID generation embeds uniqueness into the ID structure itself (timestamp + machine ID) or pre-allocates ranges, eliminating the need for cross-server coordination on every request.