Design a Unique ID Generator in A Distributed System

Grokking System Design Interview, Volume II

Ask Author

Back to course home

0% completed

Vote For New Content

Design a Unique ID Generator in A Distributed System

Table of Contents

Contents are not accessible

Let's design a Unique Identifier Generator that ensures the creation of non-duplicating IDs, which helps in maintaining data accuracy and consistency across various systems.

Difficulty Level: Easy

1. What is a Unique ID Generator?

A Unique ID Generator creates distinct identifiers for items, users, or events, ensuring that each identifier is one-of-a-kind and there are no duplicates. This functionality is crucial for maintaining order and clarity in databases, user accounts, and inventory systems, similar to how assigning each student in a school a unique ID number prevents confusion. By automating this task, the generator makes it easier to manage, update, and accurately track information.

2. Requirements and Goals of the System

Let's write the system requirements to design a system according to these requirements:

Functional Requirements

ID Generation: The system should generate unique identifiers for items, users, or events, ensuring no duplicates exist.
Collision Detection: The system should detect and handle any potential ID duplication to maintain uniqueness.
Bit Requirement: The system should generate a 64-bit length ID to balance uniqueness, storage efficiency, and performance.
Sequential ID Generation: The system must generate IDs in a way that ensures later IDs are naturally larger than those created earlier.

Non-Functional Requirements

Scalability: The system should scale to accommodate an increasing number of nodes and generated IDs, ensuring consistent performance.
Availability: The system should ensure high availability with minimal downtime to maintain reliable operations.
Low Latency: The system should generate IDs with minimal latency, ensuring the process is fast enough for real-time requirements.
Consistency: Ensure that IDs are consistently unique across the entire distributed system to maintain data integrity.

3. Capacity Estimation and Constraints

Assume that we are managing a platform that has 500 million total users and 200 million daily active users, needing 5 unique IDs per day, the total IDs generated per second would be:

200 \text{ million users} \times 5 \text{ IDs/user/day} = 1 \text{ billion IDs/day}

Assuming the system operates 24/7:

\frac{1 \text{ billion IDs}}{24 \text{ hours} \times 3600 \text{ seconds/hour}} \approx 11,574 \text{ IDs/second}

Storage Estimates: Let’s assume each ID is stored temporarily and each ID is 64-bit (8 bytes) in length. The total storage needed per day would be:

1 \text{ billion IDs} \times 8 \text{ bytes/ID} = 8 \text{ GB/day}

For a month:

8 \text{ GB/day} \times 30 \text{ days} = 240 \text{ GB/month}

Bandwidth Estimates: With each ID being 8 bytes, the bandwidth required for transmitting IDs per second would be:

11,574 \text{ IDs/second} \times 8 \text{ bytes/ID} = 92,592 \text{ bytes/second} \approx 90.4 \text{ KB/second}

For a month:

90.4 \text{ KB/second} \times 3600 \text{ seconds/hour} \times 24 \text{ hours/day} \times 30 \text{ days} \approx 234.4 \text{ GB/month}

After having a clearer picture of all the system requirements let's dive into the different options we have to achieve our goal.

4. High-Level Design

This might seem like an easy problem, but ensuring the uniqueness of IDs in a system that handles thousands of tasks daily and making certain they are never repeated is a significant challenge. Let's understand its importance with the help of a scenario:

Now assume you're running a cloud service platform. Your system handles thousands of tasks every day, like user requests, data processing, and transaction logs. Each task needs a unique ID that never repeats. Without unique IDs, operations could get mixed up, logs would be unreliable, and the system would be less dependable. Therefore, implementing a robust ID generation strategy is critical to maintaining the system's efficiency and reliability.

Given the crucial role of unique IDs, we have multiple options available to achieve this. It is essential to carefully evaluate these options and choose the approach that best meets our specific requirements.

Approach 1: Sequential ID Generators

One straightforward way to generate unique IDs is by using the auto-increment feature in databases. This feature automatically assigns a new, unique number to each record added to a table. It ensures that every new entry gets a distinct identifier without manual effort. Here’s how it works:

Approach 1 : Sequential ID Generators

The image illustrates a distributed system in which multiple servers request unique IDs from a centralized service. Each server submits a request to this central hub, which then generates and issues a unique ID for the server's operations, ensuring there are no duplicates throughout the system. This ID generation is based on a monotonic strategy, meaning that IDs are consistently larger than those previously generated, ensuring a clear and chronological sequence.

However, this centralized model has significant challenges. As the number of nodes and ID requests increases, the central service can become a bottleneck, leading to delays and potential system overloads. Additionally, this model creates a single point of failure; if the central service goes down, the entire ID generation process stops, causing high latency and impacting the system's scalability and availability.

How can we address the issue of a single point of failure in the ID generation system?

To address the single point of failure and improve both fault tolerance and scalability, we can adopt a distributed approach where each server is assigned a unique prefix. This could be the server's network card ID, server ID, or IP address. Each server combines its prefix with an auto-incrementing sequence number to independently generate unique IDs. This approach minimizes bottlenecks and ensures ongoing operation even if a server fails. Here's how to implement this strategy:

The illustration shows a distributed system where each server has a dedicated service to request unique IDs. Each server has a unique prefix, like its IP address. When a server requests an ID, its dedicated service responds with a unique ID that combines the prefix with a sequence number (e.g., 192168001001-0001). This ensures globally unique IDs without collisions, as each service independently manages sequence numbers for its server.

However, this approach has significant challenges. Frequent database access by each dedicated service can cause performance delays and overloads. Additionally, if any service or database connection fails, it stops the server's ID generation, affecting scalability and availability.

Approach 2: UUID (Universally Unique Identifiers)

UUIDs offer a reliable solution for generating unique identifiers without the need for a centralized system or database queries, addressing the limitations encountered with sequential ID generators.

A UUID, or Universally Unique Identifier, is a 128-bit label used to uniquely identify information. For our system, we specifically use UUID version 4. This version generates IDs through a randomization process that significantly reduces the risk of duplicates.

But now the question arises why we're specifically using UUID Version 4?

UUID version 4 is chosen for our system because it generates unique IDs using a randomization process that does not rely on the system's state, such as timestamps or hardware addresses, which can introduce predictability and potential privacy concerns. This randomness ensures a high degree of uniqueness across distributed nodes without the need for synchronization, virtually eliminating the probability of duplication under typical usage scenarios.

Let's see how a UUID v4 looks like:

UUID v4

explanation of the UUID version 4 as shown in the above illustration:

Time Low (32 bits): Shown in light blue, these are the first eight characters, randomly chosen.
Time Mid (16 bits): In green, these four characters come next and are also randomly chosen.
Time High and Version (16 bits): The red section shows the next four characters, which includes a '4' to indicate it's a version 4 UUID.
Clock Sequence (16 bits): Marked in blue, this is the four-character sequence that's randomly generated to help ensure uniqueness.
Node (48 bits): The last twelve characters in brown, are randomly generated to complete the UUID.

This layout helps make each UUID unique, Let's see what it looks like in a system.

The illustration shows a system where each server independently generates unique IDs using UUIDs. Each server can create IDs on its own, making it easy to add or remove servers without any issues. If one server fails, the others continue to operate normally, ensuring the system remains highly available and reliable.

The main issue with UUID v4 design is that it generates 128-bit IDs instead of the required 64-bit IDs. Additionally, UUIDs do not ensure sequential order since they are generated randomly, which may not meet our requirement for sequential ID generation, which is a key requirement. Although the probability of UUID duplication is extremely low (50% chance after generating 1 billion UUIDs per second for 100 years), this design does not meet our needs for shorter, sequentially ordered IDs.

Approach 3: Snowflake by Twitter

The core issue we face with UUIDs is that the ID size is larger than our requirement and the generated IDs are random without any sequence. The solution to this problem is Snowflake, designed by Twitter, which offers a 64-bit ID with a time-based counter. This ensures IDs are unique and sequential. Snowflake IDs include additional information that makes them a strong option for our needs. Here’s a breakdown of the Snowflake ID structure:

Snowflake ID

The Snowflake ID structure consists of:

1-bit sign: Always set to 0 as IDs are positive numbers.
41-bit timestamp: Represents the number of milliseconds since a custom epoch, ensuring IDs are time-ordered.
- This allows for IDs to be generated for approximately 69.73 years (calculated as $(2^{41} / (365 \times 24 \times 60 \times 60 \times 1000))\$ .
10-bit worker ID: Identifies the machine or process generating the ID, allowing for 1024 different workers.
12-bit sequence number: Increments with each ID generated per millisecond per worker, allowing for 4096 unique IDs per millisecond per worker.

How can we determine the exact time an event occurred based on its Snowflake ID?

To determine the exact time an event occurred using its Snowflake ID, refer to the steps illustrated below:

To accurately determine the time an event occurred using a Snowflake ID, follow the steps demonstrated in the provided image:

Extract the Timestamp: Identify the 41-bit timestamp within the Snowflake ID. For example, in the image, the timestamp segment is 0010100100 001111110 1010011000 1100011011.
Convert to Decimal: Convert this binary segment to its decimal equivalent. In this case, it converts to 352721356343.
Add the Twitter Epoch: Snowflake IDs start counting milliseconds from a specific epoch known as the Twitter epoch, which is 1288834974657 milliseconds post Unix epoch. Adding this to the decimal timestamp gives:
- 352721356343 + 1288834974657 = 1641556331000.
Convert to UTC Time: Translate the combined timestamp into UTC time. According to the calculations, 1641556331000 corresponds to January 7, 2022, at 11:52:11 UTC.

Snowflake's system for creating unique IDs depends on keeping all networked computers perfectly in sync using the Network Time Protocol (NTP). Here are some issues this dependency can introduce:

Timing Sensitivity: NTP usually aligns computer clocks to within milliseconds, but network delays, setup errors, or disruptions can cause small mismatches in time. Even minor timing differences can lead Snowflake to generate duplicate IDs, compromising data accuracy.
Complex Management: Maintaining precise synchronization with NTP requires detailed setup and ongoing management, adding complexity to the system's operation.

Each point highlights the practical challenges and potential risks associated with relying on a system that needs such precise timing to function effectively.

How does NTP reliance affect Snowflake’s ID uniqueness?

Snowflake's ID system relies on Network Time Protocol (NTP) to synchronize server times. If servers fall out of sync, even by a tiny bit, they might end up creating IDs at the same moment.

For example, assume two clocks showing slightly different times: one might be a fraction of a second ahead. If both decide to create an ID at what they think is the same time, and both use the same order number, they'll end up creating identical IDs. This overlap shows why accurate timing is crucial for Snowflake's system to ensure each ID is unique.

Approach 4:TrueTime API

To solve the problems of ID duplication and ensure our IDs are generated in a precise sequential order, we can use Google’s TrueTime API. This is a special tool that helps keep time very accurate across different computers that are part of a large network, like those used by cloud services or large databases.

TrueTime combats the issue of time discrepancies in distributed systems by using a combination of GPS and atomic clocks. This setup ensures all participating machines in the network have an almost identical understanding of time, down to the milliseconds.

How Does TrueTime Ensure Precise Timekeeping Across Globally Distributed Systems?

TrueTime solves the challenge of time synchronization in distributed systems by integrating key components explained below:

GPS Masters: Think of GPS Masters as special servers that get super accurate time from GPS satellites in space. These satellites constantly send time signals, ensuring the servers know the exact time down to the millisecond.
Atomic Masters: Atomic Masters are like the most precise clocks you can imagine, using atoms to keep perfect time. These servers get time updates from GPS Masters every 30 seconds to stay accurate.
Compute Nodes: Compute Nodes are the regular servers that do most of the work, like processing data and generating IDs. They need to know the exact time to ensure everything runs smoothly. They get time updates from both GPS Masters and Atomic Masters to keep their clocks in sync.
Time Synchronization Protocols: These are the methods used to keep all the servers’ clocks in sync. Network Time Protocol (NTP) and Precision Time Protocol (PTP) help the Compute Nodes update their time frequently, so everyone is on the same page.

Now let's see how the work together with the help of the below illustration:

Let's understand the process how it works:

The synchronization process begins with the GPS Masters, which gather time signals from several GPS satellites.
This time data sets the standard for the Atomic Masters, which continuously adjust their time settings based on the GPS information to ensure ongoing accuracy.
Compute Nodes, crucial for operations like ID generation, regularly adjust their clocks with the Atomic Masters, often multiple times per second, to maintain precise time.

Now that we have understood the whole time tracking process let's move toward how it will work for ID generation.

Using TrueTime in ID Generation

When integrating TrueTime into an ID generation system, the approach can leverage the precise timing and uncertainty features to ensure uniqueness and order. By incorporating TrueTime API, we address the time synchronization issues faced with the Snowflake approach, enhancing reliability across distributed systems.

|------------------------------64 bits-------------------------------|
| Sign Bit |    TrueTime Timestamp    | Worker ID | Sequence Number  |
|   0      | 100101010101010101010101 | 0010010101| 000101010101     |
| (1-bit)  |   (41-bits)              | (10-bits) |    (12-bits)     |

Sign Bit (1-bit): Generally set to 0 to keep the ID positive.
TrueTime Timestamp (41-bits): This segment uses the earliest timestamp from TrueTime, ensuring that IDs are generated in chronological order. The use of the earliest helps maintain order even if there's some future adjustment in the system's perception of time.
Worker ID (10-bits): Identifies the server or process that generates the ID, allowing up to 1024 different sources.
Sequence Number (12-bits): Used to differentiate IDs generated within the same millisecond by the same worker, allowing up to 4096 IDs per millisecond per worker.

How does TrueTime ensure that two confidence intervals don’t overlap, and how is this used to generate unique IDs with TrueTime intervals?

TrueTime ensures that time intervals for events do not overlap, maintaining a clear order of events. Here's how it works:

Each event is assigned a time range, called a confidence interval, within which it occurred. For example, Event A might have a confidence interval of [start_A, end_A], and Event B might have a confidence interval of [start_B, end_B].

TrueTime guarantees that these intervals do not overlap if Event B happens after Event A. This is achieved by ensuring:

$A_{\text{ends}} < B_{\text{starts}}$

This confirms that Event B happens after Event A, establishing a clear sequence of events.

To generate unique IDs for these events, TrueTime uses the earliest timestamp from each interval. For instance, Event A might use start_A (e.g., 2 PM) and Event B might use start_B (e.g., 4 PM). This method ensures each event has a unique and ordered identifier based on when it started.

Now let's see how the system would look like considering a single server for processing:

In the described setup, when a client initiates an operation, the server communicates with Google Cloud Spanner to fetch the current timestamp. This timestamp is then used by the server to generate a unique 64-bit identifier (ID) for the operation, ensuring sequential and collision-free IDs across the distributed system.

By integrating the TrueTime API into our system, we ensure all defined requirements are met, including unique, sequential IDs, scalability, high availability, low latency, and data consistency across the distributed system.

However, the TrueTime API can increase system costs, making it unsuitable for smaller systems. Additionally, if two intervals overlap, we cannot guarantee the exact order of events. Spanner is expensive because it ensures high database consistency, and the cost is further elevated by its elaborate infrastructure and monitoring requirements.

As we conclude the TrueTime API stands out as the most effective solution for generating unique identifiers in distributed systems, ensuring precision and reliability. By harnessing GPS and atomic clocks, TrueTime overcomes the challenges of time discrepancies and ID duplication. Although implementing TrueTime via Google’s Cloud Spanner incurs higher costs, its benefits in ensuring data consistency, low latency, and high availability make it a valuable investment for large-scale, critical applications where accuracy is crucial.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible