How Would You Design a Distributed Unique ID Generator?
Learn how to design a distributed unique ID generator: Snowflake bit-packing, worker IDs, and UUID trade-offs.
Expected Interview Answer
A distributed unique ID generator produces globally unique, roughly time-sortable identifiers across many machines without coordination on every request, most commonly using a Snowflake-style scheme that packs a timestamp, a worker/machine ID, and a per-millisecond sequence number into a single 64-bit integer.
The timestamp bits (typically ~41 bits, milliseconds since a custom epoch) make IDs roughly sortable by creation time and dominate the ID’s magnitude, the worker ID bits (~10 bits) let up to a few thousand machines generate IDs independently without talking to each other, and the sequence bits (~12 bits) allow a single machine to mint thousands of unique IDs within the same millisecond by incrementing a local counter. Each node needs a stable, unique worker ID assigned at startup — via configuration, a coordination service like ZooKeeper, or a database allocation table — to guarantee no two nodes ever produce the same ID. Alternatives include database auto-increment with sharded ranges, UUIDv4 (fully random, not sortable, larger), and UUIDv7 (time-ordered, standardized), each trading off sortability, size, and coordination requirements differently.
- No coordination needed per request, so ID generation scales horizontally with no bottleneck
- IDs are roughly time-sortable, which keeps database indexes and pagination efficient
- Compact 64-bit integers are cheaper to store and index than 128-bit UUIDs
- Worker ID partitioning guarantees uniqueness across machines without a central counter
AI Mentor Explanation
A distributed ID generator is like how every ball bowled in international cricket gets a unique reference combining the match date, the ground’s registered code, and a running ball count within that over — no central office needs to approve each reference in real time. The date portion keeps references roughly ordered chronologically, the ground code lets multiple stadiums generate references independently without clashing, and the ball count lets a single stadium issue many references within the same match without collision. As long as every ground has a distinct, pre-assigned code, no two balls anywhere in the world ever get the same reference. That composite, coordination-free scheme is exactly how a Snowflake-style ID generator works.
Step-by-Step Explanation
Step 1
Assign a unique worker ID
Each generator node gets a stable, unique worker ID at startup via config, ZooKeeper, or a database allocation table.
Step 2
Read the current timestamp
On each ID request, take milliseconds since a custom epoch and left-shift it into the top bits of the ID.
Step 3
Pack worker ID and sequence
Embed the worker ID in the middle bits and an in-memory, per-millisecond sequence counter in the low bits.
Step 4
Handle clock and sequence overflow
If the sequence overflows within a millisecond, wait for the next millisecond; if the clock moves backward, reject or stall to avoid duplicate IDs.
What Interviewer Expects
- Describes the Snowflake bit-packing scheme (timestamp + worker ID + sequence)
- Explains how worker IDs are assigned uniquely without a central bottleneck per request
- Handles edge cases: sequence overflow within a millisecond, clock skew/backward time
- Compares against alternatives: UUIDv4, UUIDv7, database auto-increment with sharded ranges
Common Mistakes
- Proposing a single central counter/database as the only source of IDs (creates a bottleneck and single point of failure)
- Ignoring clock skew across machines and its effect on uniqueness/ordering
- Confusing this with plain UUIDv4 without discussing sortability trade-offs
- Forgetting to explain how worker IDs are allocated uniquely across nodes
Best Answer (HR Friendly)
“I would generate IDs locally on each machine by combining the current timestamp, a unique machine identifier, and a small counter, all packed into a single number. This means every machine can create IDs instantly without asking a central server for permission, while the IDs still stay roughly ordered by time and guaranteed unique across the whole system.”
Code Example
import time
EPOCH = 1704067200000 # custom epoch, ms
WORKER_BITS = 10
SEQUENCE_BITS = 12
MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1
class SnowflakeGenerator:
def __init__(self, worker_id):
assert 0 <= worker_id < (1 << WORKER_BITS)
self.worker_id = worker_id
self.sequence = 0
self.last_ts = -1
def next_id(self):
ts = int(time.time() * 1000)
if ts < self.last_ts:
raise Exception("clock moved backwards, refusing to generate id")
if ts == self.last_ts:
self.sequence = (self.sequence + 1) & MAX_SEQUENCE
if self.sequence == 0:
while ts <= self.last_ts:
ts = int(time.time() * 1000)
else:
self.sequence = 0
self.last_ts = ts
id_ = ((ts - EPOCH) << (WORKER_BITS + SEQUENCE_BITS)) \
| (self.worker_id << SEQUENCE_BITS) \
| self.sequence
return id_Follow-up Questions
- How would you detect and handle clock drift (NTP adjustments moving time backward) safely?
- How does UUIDv7 compare to a Snowflake ID for sortability and interoperability?
- How would you allocate worker IDs automatically in a Kubernetes deployment with autoscaling?
- What happens to ID generation throughput if the sequence bits are too small?
MCQ Practice
1. In a Snowflake-style ID, what does the worker ID bits field guarantee?
A unique worker ID per machine ensures IDs generated on different nodes never collide, without requiring per-request coordination.
2. Why are Snowflake-style IDs considered roughly time-sortable?
Placing the timestamp in the most significant bits makes newer IDs numerically larger, so they sort roughly by creation time.
3. What is a key trade-off of UUIDv4 compared to a Snowflake-style ID?
UUIDv4 is 128 bits of randomness with no inherent ordering, while Snowflake IDs are compact 64-bit integers that sort roughly by time.
Flash Cards
What three components make up a Snowflake-style ID? — A timestamp, a worker/machine ID, and a per-millisecond sequence number.
Why are Snowflake IDs roughly sortable? — The timestamp occupies the highest bits, so newer IDs are numerically larger.
How do machines avoid ID collisions without coordination? — Each machine has a unique pre-assigned worker ID embedded in every ID it generates.
What happens if the sequence counter overflows within a millisecond? — The generator waits/spins until the next millisecond before continuing to issue IDs.