Understand the Problem
In this chapter, you are asked to design a unique ID generator in distributed systems. Your first thought might be to use a primary key with the auto_increment attribute in a traditional database. However, auto_increment does not work in a distributed environment because a single database server is not large enough and generating unique IDs across multiple databases with minimal delay is challenging.
Here are a few examples of unique IDs:
Step 1 – Understand the problem and establish design scope
Asking clarification questions is the first step to tackle any system design interview question. Here is an example of candidate-interviewer interaction:
What are the characteristics of unique IDs?
IDs must be unique and sortable.
For each new record, does ID increment by 1?
The ID increments by time but not necessarily only increments by 1. IDs created in the evening are larger than those created in the morning on the same day.
Do IDs only contain numerical values?
Yes, that is correct.
What is the ID length requirement?
IDs should fit into 64-bit.
What is the scale of the system?
The system should be able to generate 10,000 IDs per second.
Above are some of the sample questions that you can ask your interviewer. It is important to understand the requirements and clarify ambiguities. For this interview question, the requirements are listed as follows:
-
IDs must be unique.
-
IDs are numerical values only.
-
IDs fit into 64-bit.
-
IDs are ordered by date.
-
Ability to generate over 10,000 unique IDs per second.
Finished reading?
Mark it complete to track your progress.