Design a Unique ID Generator in Distributed Systems

SQL databases have an AUTO_INCREMENT primary key: the database atomically increments a counter and assigns it to each new row. This works perfectly on a single database server. In a distributed system with multiple database servers, AUTO_INCREMENT breaks: two servers can assign the same ID to different records.

Requirements for a distributed ID generator: IDs must be unique across all nodes; IDs should be 64-bit integers; IDs should be ordered by time (new IDs should be numerically greater than old IDs — critical for range scans, pagination, and timeline ordering); the system should generate at least 10,000 IDs per second.

Each database server auto-increments by K (the number of servers) instead of 1. Server 1 generates 1, 3, 5, 7... and Server 2 generates 2, 4, 6, 8... This avoids conflicts between servers.

Problems: IDs are not globally sortable by time — server 2 may generate ID 4 before server 1 generates ID 3. Hard to add or remove servers without reconfiguring the increment step. Does not work well across data centers.

UUIDs (Universally Unique Identifiers) are 128-bit values generated independently on each machine without any coordination. Each server generates its own UUIDs — no central authority, no synchronization, no risk of collision in practice (the probability of collision is astronomically low).

Problems: 128 bits is larger than our 64-bit requirement. UUIDs are not sortable by time (UUID v1 embeds a timestamp but in a non-obvious bit layout; UUID v4 is random). UUIDs can contain non-numeric characters (they are typically represented as hex with hyphens).

Flickr built a dedicated "ticket server" — a single database server with an AUTO_INCREMENT table. Every service that needs a unique ID makes a request to the ticket server, which returns the next auto-incremented integer. IDs are guaranteed unique and monotonically increasing.

Problems: the ticket server is a single point of failure (if it goes down, ID generation stops for the entire system). You can add a secondary ticket server for redundancy, but then you have the same synchronization problem as multi-master replication. Does not scale beyond one region cleanly.

Twitter's Snowflake algorithm generates unique, time-sortable 64-bit IDs with no coordination between servers. The 64 bits are divided into sections:

Bit 1 (sign bit): always 0. Reserved for future use — keeps the number positive. Bits 2–42 (41 bits): milliseconds since a custom epoch (Twitter used November 4, 2010 as the epoch). 41 bits gives ~69 years of IDs before overflow. Bits 43–47 (5 bits): datacenter ID. Supports up to 32 datacenters. Bits 48–52 (5 bits): machine ID. Supports up to 32 machines per datacenter. Bits 53–64 (12 bits): sequence number. Incremented for each ID generated on the same machine within the same millisecond. Supports up to 4,096 IDs per millisecond per machine. Resets to 0 at the start of each new millisecond.

IDs generated later always have a larger timestamp, so they sort chronologically. No coordination between servers — each machine generates IDs independently. Globally unique because (datacenter ID, machine ID, millisecond, sequence) combination is always unique.

Clock synchronization: Snowflake relies on each machine's system clock being accurate. If a machine's clock drifts backward (due to NTP corrections), it might generate an ID with a timestamp smaller than the previous ID, breaking sort order or causing ID collisions. Fix: detect clock drift and refuse to generate IDs until the clock catches up. Use NTP (Network Time Protocol) for clock synchronization across machines.

Section length tuning: the 41/5/5/12 split is not fixed — tune it for your use case. If you need more machines than 32 per datacenter, allocate more bits to machine ID (reducing the sequence bits). If you expect very high per-machine throughput, allocate more sequence bits.

High availability: Snowflake ID generation is purely in-process with no network calls. It is extremely fast (microseconds per ID) and cannot be a single point of failure — each application server generates its own IDs independently.