Example: ID generator for distributed systems

• Step 1: Questions
• Requirements after asking questions
• Step 2 - Propose high-level design and get buy-in
• Multi-master replication
• UUID
• Divide and conquer

Step 1: Questions

Candidate: What are the characteristics of unique IDs? Interviewer: IDs must be unique and sortable.

Candidate: For each new record, does ID increment by 1? Interviewer: 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.

Candidate: Do IDs only contain numerical values? Interviewer: Yes, that is correct.

Candidate: What is the ID length requirement? Interviewer: IDs should fit into 64-bit.

Candidate: What is the scale of the system? Interviewer: The system should be able to generate 10,000 IDs per second.

Requirements after asking questions

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.

Step 2 - Propose high-level design and get buy-in

Let us look at each of them, how they work, and the pros/cons of each option.

Multi-master replication

Increment by the number of servers.

Cons: It does not scale well when a server is added or removed.

UUID

UUID = 128 bit number. After generating 1 billion UUIDs every second for approximately 100 years would the probability of creating a single duplicate reach 50%

Cons: • IDs are 128 bits long, but our requirement is 64 bits. • IDs do not go up with time. • IDs could be non-numeric.

Pros: • Generating UUID is simple. No coordination between servers is needed so there will not be any synchronization issues. • The system is easy to scale because each web server is responsible for generating IDs they consume. ID generator can easily scale with web servers.

Divide and conquer