Design a unique ID generator in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Architecture

intermediate

Identify the correct architecture for a distributed unique ID generator

You want to design a system that generates unique IDs across multiple servers without collisions. Which architecture below best ensures uniqueness and scalability?

A A centralized server generates IDs sequentially and all clients request IDs from it.

B Clients generate random IDs independently without coordination.

C Each server generates IDs using a timestamp combined with a unique server ID and a sequence number.

D IDs are generated by hashing client IP addresses and timestamps.

💡 Hint

Think about how to avoid collisions and maintain scalability without a single bottleneck.

Option C uses a combination of timestamp, server ID, and sequence number to ensure uniqueness and scalability. Option C creates a bottleneck. Option C risks collisions. Option C can cause collisions and is not reliable.

❓ scaling

intermediate

Estimate the capacity of a unique ID generator system

Your unique ID generator uses 41 bits for timestamp (in milliseconds), 10 bits for machine ID, and 12 bits for sequence number per millisecond. How many unique IDs can the system generate per millisecond?

A 4096 IDs per second

B 4096 IDs per millisecond

C 1024 IDs per second

D 1024 IDs per millisecond

💡 Hint

Calculate how many IDs the sequence number allows per millisecond, then convert to per second.

12 bits for sequence number means 2^12 = 4096 IDs per millisecond. Since 1 second = 1000 milliseconds, total per second is 4096 * 1000 = 4,096,000 IDs. The question asks per millisecond but options focus on per millisecond or per second. The correct choice is 4096 IDs per millisecond.

❓ tradeoff

advanced

Choose the best tradeoff for ID length vs. uniqueness duration

You design a unique ID with 64 bits total. You can allocate bits between timestamp and sequence number. Allocating more bits to timestamp increases the time range IDs remain unique, but reduces IDs per millisecond. Allocating more bits to sequence number increases IDs per millisecond but shortens uniqueness duration. Which allocation is best for a system needing 10,000 IDs per millisecond and uniqueness for 10 years?

A 39 bits timestamp, 14 bits sequence number

B 41 bits timestamp, 12 bits sequence number

C 42 bits timestamp, 11 bits sequence number

D 38 bits timestamp, 15 bits sequence number

💡 Hint

Calculate if the timestamp bits cover 10 years and if sequence bits cover 10,000 IDs per millisecond.

14 bits sequence number = 16384 IDs per millisecond, which covers 10,000 IDs. 39 bits timestamp covers about 17 years (2^39 ms ≈ 17 years), which covers 10 years. Other options either have too few sequence bits or too few timestamp bits.

🧠 Conceptual

advanced

Identify the main challenge in distributed unique ID generation

What is the biggest challenge when designing a distributed unique ID generator that works across many servers?

A Ensuring IDs are cryptographically secure

B Minimizing the size of the ID to 16 bits

C Generating IDs that are human-readable

D Avoiding collisions without a central coordinator

💡 Hint

Think about what happens when multiple servers generate IDs independently.

The main challenge is avoiding collisions (duplicate IDs) without relying on a central server, which can become a bottleneck or single point of failure. Cryptographic security and human readability are less critical. Minimizing ID size to 16 bits is impractical for uniqueness.

❓ component

expert

Trace the request flow in a Snowflake-like ID generator system

In a Snowflake-like distributed ID generator, which sequence correctly describes the request flow when a client requests a new ID?

A 1,2,3,4,5,6

B 1,3,2,4,5,6

C 2,1,3,4,5,6

D 1,2,4,3,5,6

💡 Hint

Think about the logical order from request to ID generation and response.

The client first sends the request (1). The service checks timestamp (2). If timestamp same as last, increment sequence (3). If sequence maxed, wait (4). Then compose ID (5) and return it (6). Other orders break logical flow.

Practice

1. What is the primary purpose of a unique ID generator in a distributed system?

easy

A. To create identifiers that are distinct across all machines and time

B. To encrypt data for secure communication

C. To compress large files efficiently

D. To balance load between servers

Solution

1. Step 1: Understand the role of unique IDs

   Unique IDs ensure that each identifier is different from others, avoiding conflicts.

2. Step 2: Recognize distributed system needs

   In distributed systems, IDs must be unique across machines and time to prevent collisions.

3. Final Answer:

   To create identifiers that are distinct across all machines and time -> Option A

4. Quick Check:

   Unique ID purpose = distinct identifiers [OK]

Hint: Unique IDs prevent duplicates across systems [OK]

Common Mistakes:

• Confusing unique ID with encryption
• Thinking unique ID compresses data
• Mixing load balancing with ID generation

2. Which of the following is a common component in a unique ID generator design?

easy

A. Encryption key for data security

B. Load balancer to distribute requests

C. Compression algorithm for data size reduction

D. Sequence number to avoid collisions within the same timestamp

Solution

1. Step 1: Identify components of unique ID generators

   Common components include timestamp, machine identifier, and sequence number.

2. Step 2: Understand sequence number role

   Sequence numbers help generate multiple unique IDs within the same timestamp to avoid collisions.

3. Final Answer:

   Sequence number to avoid collisions within the same timestamp -> Option D

4. Quick Check:

   Sequence number = collision avoidance [OK]

Hint: Sequence numbers prevent same-time ID clashes [OK]

Common Mistakes:

• Confusing encryption with ID generation
• Thinking compression is part of ID design
• Mixing load balancing with ID components

3. Consider a unique ID generator that uses a 41-bit timestamp, 10-bit machine ID, and 12-bit sequence number. What is the maximum number of unique IDs it can generate per millisecond per machine?

medium

A. 8192

B. 1024

C. 4096

D. 2048

Solution

1. Step 1: Understand bit allocation for sequence number

   The sequence number uses 12 bits, so max IDs per millisecond = 2^12.

2. Step 2: Calculate 2^12

   2^12 = 4096 unique IDs per millisecond per machine.

3. Final Answer:

   4096 -> Option C

4. Quick Check:

   2^12 = 4096 [OK]

Hint: 2^sequence_bits = max IDs/ms [OK]

Common Mistakes:

• Using machine ID bits instead of sequence bits
• Calculating 2^10 or 2^11 instead of 2^12
• Confusing total bits with sequence bits

4. A unique ID generator uses a timestamp, machine ID, and sequence number. If two machines generate IDs at the exact same millisecond with the same sequence number, what is the likely cause of duplicate IDs?

medium

A. Machine IDs are not unique or not included in the ID

B. Timestamp is too large

C. Sequence number is too long

D. The system uses encryption

Solution

1. Step 1: Analyze ID components for uniqueness

   Machine ID differentiates IDs from different machines at the same time.

2. Step 2: Identify cause of duplicates

   If machine IDs are missing or not unique, IDs from different machines can collide.

3. Final Answer:

   Machine IDs are not unique or not included in the ID -> Option A

4. Quick Check:

   Missing unique machine ID = duplicates [OK]

Hint: Unique machine ID prevents cross-machine duplicates [OK]

Common Mistakes:

• Blaming timestamp size for duplicates
• Thinking longer sequence number causes duplicates
• Confusing encryption with ID uniqueness

5. You need to design a unique ID generator for a global system with thousands of machines generating millions of IDs per second. Which design choice best ensures scalability and uniqueness?

hard

A. Generate random 64-bit numbers without coordination

B. Use a 64-bit ID combining timestamp, machine ID, and sequence number with synchronized clocks

C. Use only timestamp-based IDs without machine info

D. Assign IDs sequentially from a central server

Solution

1. Step 1: Consider scalability and uniqueness needs

   Global scale requires IDs unique across machines and time, with high throughput.

2. Step 2: Evaluate design options

   Combining timestamp, machine ID, and sequence number in 64 bits with synchronized clocks ensures uniqueness and scalability.

3. Step 3: Reject other options

   Random IDs risk collisions; timestamp-only lacks machine uniqueness; central server causes bottleneck.

4. Final Answer:

   Use a 64-bit ID combining timestamp, machine ID, and sequence number with synchronized clocks -> Option B

5. Quick Check:

   64-bit composite ID = scalable unique IDs [OK]

Hint: Combine time, machine, sequence for scalable unique IDs [OK]

Common Mistakes:

• Relying on random IDs risking collisions
• Ignoring machine ID causing duplicates
• Using central server causing bottlenecks