Designing a Distributed Unique ID Generator: A System Design Interview Guide
2 views
"Design a unique ID generator for a distributed system" is a short but revealing interview question. It looks trivial until you realize that dozens of servers must create IDs simultaneously, without collisions, without a single bottleneck, and often roughly sorted by time.
Clarify requirements
Ask how many IDs per second are needed (say 100,000 across the fleet), whether IDs must be numeric and fit in 64 bits, whether they should be sortable by creation time, and whether they must be strictly sequential or just unique. Strict global sequence is expensive; roughly time-ordered is usually enough.
Option 1: database auto-increment
A single database sequence is simple and ordered, but it is a single point of failure and a throughput ceiling. A variation uses several databases, each incrementing by N with a different offset, but adding servers later is awkward.
Option 2: UUIDs
128-bit random UUIDs need no coordination and almost never collide. The downsides: they are long, not numeric, not time-ordered (for version 4), and they fragment database indexes. Newer time-ordered UUID versions help with ordering.
Option 3: ticket server or range allocation
A central service hands out blocks of IDs (for example 1,000 at a time) to each application server, which then assigns them locally. This reduces load on the central store, but IDs are only loosely ordered and a crash wastes part of a block, which is usually acceptable.
Option 4: Snowflake-style IDs
This is the answer most interviewers hope to hear. A 64-bit ID is split into fields: 1 sign bit, 41 bits of milliseconds since a custom epoch (about 69 years), 10 bits of machine ID (1,024 machines), and 12 bits of per-millisecond sequence (4,096 IDs per millisecond per machine). Each server generates IDs independently, and they sort by time.
Edge cases to discuss
- Clock skew: if a server's clock moves backwards, it must wait or refuse to generate IDs, or it risks duplicates. Use NTP and monotonic checks.
- Sequence overflow within one millisecond: block until the next millisecond.
- Machine ID assignment: use a coordination service or configuration at startup so no two servers share an ID.
Wrapping up
Compare the options in a quick table: coordination needed, ordering, size, and failure behavior. Then recommend Snowflake for most cases. Practicing this comparison out loud helps a lot. For extra support during the real interview, Linkjob AI (https://linkjob.ai) provides real-time help during live technical interviews, though a rehearsed structure is still your strongest asset.