System Design Interview Prep Crash Course/

...

/

Design a Unique ID Generator

Design a Unique ID Generator

Learn how to design a system that generates a unique ID.

We'll cover the following...

Motivation

Millions of events can happen per second in a large distributed system. Commenting on a post on Facebook, sharing a Tweet, and posting a picture on Instagram are just a few examples of such events. We need a mechanism to distinguish these events from each other. One such mechanism is the assignment of globally unique IDs to each of these events.

Unique IDs are important for identifying events and objects within a distributed system. However, designing a unique ID generator within a distributed system is challenging.

Let’s look at the requirements for a distributed unique ID generation system and then the solutions to this design problem.

Requirements for unique identifiers

The requirements for our system are as follows:

  • Uniqueness: We need to assign unique identifiers to different events for identification purposes.

  • Scalability: The ID generation system should generate at least one billion unique IDs per day.

  • Availability: Since multiple events happen even at the level of nanoseconds, our system should generate IDs for all the events that occur.

  • 64-bit numeric ID: We restrict the length to 64 bits because this bit size is enough for many years in the future. Let’s calculate the number of years after which our ID range will wrap around.

    Total numbers available: 2642^{64} = 1.8446744 x 101910^{19}

    Estimated number of events per day: 1 billion = 10910^{9}

    Number of events per year: 365 billion = 365×109365 \times 10^{9}

    Number of years to deplete identifier range: 264365×109\frac{2^{64}}{365\times10^{9}} ...