architect-handbook

Software Architect Handbook

View on GitHub

Design a unique ID generator in distributed systems

Overview

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.

Step 1: Understand the problem and establish design scope

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.

For this interview question, the requirements are listed as follows:

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

We consider the following options:

Multi-master replication

This approach uses the databases’ auto_increment feature. Instead of increasing the next ID by 1, we increase it by k, where k is te number of database servers in use.

Next ID to be generated is equal to the previous ID in the same server plus 2.

This solve some scalability issues because IDs can scale with the number of database servers. However, this strategy has some major drawbacks:

UUID: Universally unique identifier

A UUID is another easy way to obtain unique IDs. UUID is a 128-bit number used to identify information in computer systems. UUID has a very low probability of getting collusion. UUIDs can be generated independently without coordination between servers.

Wikipedia: “after generating 1 billion UUIDs every second for approximately 100 years, would the probability of creating creating a single duplicate reach 50%”.

Pros:

Cons:

Ticket server

Flicker developed ticket servers to generate distributed primary keys.

The idea is to use a centralized auto_increment feature in a single database server (Ticket Server).

Pros:

Cons:

Twitter snowflake approach

Twitter’s unique ID generation system called snowflake works with a divide and conquer approach. Instead of generating an ID directly, we divide an ID into different sections:

Layout of a 64-bit ID.

Step 3: Design deep dive

Datacenter IDs and machine IDs are chosen at the startup time, generally fixed once the system is up running. Any changes in datacenter IDs and machine IDs require careful review since an accidental change in those values can lead to ID conflicts. Timestamp and sequence numbers are generated when the ID generator is running.

Timestamp

The most important 41 bits make up the timestamp section. As timestamps grow with time, IDs are sortable by time.

The maximum timestamp that can be represented in 41 bits is ~69 years using an epoch time close to today’s date. After 69 years, we will need a new epoch time or adopt other techniques to migrate IDs.

Sequence number

Sequence number is 12 bits, which give us 2^12 = 4096 combinations. This field is 0 unless more than one ID is generated in a millisecond on the same server. In theory, a machine can support a maximum of 4096 new IDs per millisecond.

Step 4: Wrap up

We settle on snowflake as it supports all our use cases and is scalable in a distributed environment.