Design Unique ID Generator
What is a Unique ID Generator?
A unique ID generator is a system that produces identifiers that are globally unique across distributed services. These IDs are used to identify entities like users, orders, transactions, or messages in large-scale systems.
Examples include Twitter’s Snowflake IDs, UUIDs, and database auto-increment keys.
Let’s begin by clarifying the requirements.
1. Clarifying Requirements
A system design interview should always start with a conversation to scope the problem. Here’s an example of how a candidate–interviewer discussion might flow:
Interviewer: "Let's design a distributed unique ID generator."
Candidate: "Great. First, I want to clarify the properties these IDs should have. Is global uniqueness the only hard requirement, or do they also need to be sortable?"
Interviewer: "Good question. Let's say they should be roughly sortable by the time of creation."Candidate: "Okay. And what about the format? Should they be numeric or can they be strings?"
Interviewer: "Let's stick to numeric, preferably a 64-bit integer, so it fits in a standard bigint column."
Candidate: "Got it. In terms of non-functional requirements, I'll assume the service needs to be highly available, low-latency, and horizontally scalable to handle millions of requests per second."
What is K-Sortability?
An ID is said to be K-sortable if it is roughly ordered by creation time meaning that newer IDs are usually greater than older ones, though slight out-of-order scenarios may occur due to distributed generation.
After gathering the details, we can summarize the key system requirements.
1.1 Functional Requirements
- Unique ID Generation: Generate globally unique IDs across distributed services. Each ID must fit within 64 bits.
- Time Ordering: IDs should be K-sortable, meaning they roughly increase with creation time.
1.2 Non-Functional Requirements
- High Availability: The service must be resilient to node failures. Aim for 99.99% availability.
- Scalability: The system must scale to handle very high throughput (millions of IDs/sec).
- Low Latency: ID generation should be extremely fast (e.g., <2ms).