Design a unique ID generator in HLD - System Design Exercise

Design: Unique ID Generator

Design covers the ID generation service, its architecture, data flow, and scaling. Does not cover client-side ID usage or storage.

Functional Requirements

FR1: Generate unique IDs that are globally unique across distributed systems

FR2: Support high request throughput of up to 100,000 ID requests per second

FR3: IDs should be sortable by creation time

FR4: IDs must be generated with low latency (p99 < 10ms)

FR5: System should be highly available with 99.9% uptime

FR6: Support multiple clients generating IDs concurrently

Non-Functional Requirements

NFR1: No single point of failure

NFR2: IDs must be collision-free even under network partitions

NFR3: System should scale horizontally

NFR4: Generated IDs should be compact (e.g., 64-bit or 128-bit)

NFR5: Avoid reliance on centralized databases for ID generation

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Timestamp provider

Node or machine identifier

Sequence number generator

API gateway or load balancer

Distributed coordination or consensus service (optional)

Cache or in-memory store for sequence state

Design Patterns

Snowflake ID generation pattern

UUID version 1 or 4

Database auto-increment with sharding

Timestamp + node ID + sequence number

Leader election for coordination

Reference Architecture

Load Balancer

↓

ID Generator Nodes

↓

Clients receive unique IDs

↓

Timestamp

Components

Load Balancer

Nginx or Cloud Load Balancer

Distributes incoming ID generation requests evenly across ID generator nodes

ID Generator Nodes

Custom service using Snowflake algorithm

Generate unique IDs using timestamp, node ID, and sequence number

Coordination Service

Apache ZooKeeper or etcd

Assigns unique node IDs and manages node membership to avoid collisions

Request Flow

1. Client sends request for unique ID to Load Balancer

2. Load Balancer forwards request to one of the ID Generator Nodes

3. ID Generator Node obtains current timestamp

4. Node uses its unique node ID assigned by Coordination Service

5. Node increments sequence number for IDs generated within the same millisecond

6. Node combines timestamp, node ID, and sequence number to form unique ID

7. Node returns generated unique ID to client

Database Schema

No persistent database required for ID generation. Coordination Service stores ephemeral node IDs and membership info.

Scaling Discussion

Bottlenecks

Sequence number overflow if too many IDs requested in one millisecond per node

Coordination service becoming a single point of failure

Load balancer overload under very high request rates

Clock synchronization issues causing duplicate or out-of-order IDs

Solutions

Increase number of ID generator nodes to distribute load

Use high-availability setup for coordination service with leader election

Implement client-side retries and backoff for load balancer failures

Use NTP or GPS for clock synchronization and monitor clock drift

If sequence overflows, wait for next millisecond or reject requests temporarily

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data flow, 10 minutes discussing scaling and failure handling, 5 minutes summarizing.

Explain why global uniqueness and ordering are important

Describe how timestamp, node ID, and sequence number combine to form unique IDs

Discuss trade-offs between centralized and decentralized approaches

Highlight how coordination service prevents node ID collisions

Address how system handles clock issues and high throughput

Mention scalability and fault tolerance strategies

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