Design of Unique ID Generator

Motivation

There can be millions of events happening 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.

Assigning a primary key to an entry in a database is another use-case of a unique ID. Usually, an auto-increment feature of databases fulfills this requirement. But this won’t work for a distributed database, where different nodes will independently generate the identifiers. We will need a unique ID generator that could act as a primary key in a distributed setting (for example a horizontally-sharded table).

A unique ID helps identify a flow of an event in the logs and is useful in debugging. A real-world example of unique ID usage is Facebook’s end-to-end performance tracing and analysis system, CanopyCanopy: An End-to-End Performance Tracing and Analysis System. It uses TraceID to identify an event uniquely across the execution path (that can potentially touch hundreds of microservices to fulfill one user request).

Therefore, unique IDs are important for identifying events within a distributed system. However, designing a unique ID generator within a distributed system can be challenging. Let’s understand our requirements for a distributed unique ID generation system.

Requirements for unique identifiers

The requirements for our system are:

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

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

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

4. 64-bit numeric ID: We will restrict the length to 64 bits as this bit size would be enough for many years in the future. Let’s calculate after how many years our ID range will wrap around.

   Total numbers available = $2^{64}$ ...