Bird
Raised Fist0

Why Unique ID Generation Is a Non-Trivial System Design Problem

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Why Unique ID Generation Is a Non-Trivial System Design Problem
Understanding the challenges and architectural decisions behind scalable, collision-free unique ID generation
mediumUnique ID GenerationFreq: common
Prerequisites:Distributed Systems BasicsDatabase Partitioning and ShardingCAP TheoremConsensus Algorithms
⚙️
Functional Requirements
  • Generate globally unique IDs without collisions across distributed services
  • Support high throughput ID generation (≥ 1 million IDs/sec)
  • IDs must be sortable by generation time for query efficiency
  • Provide low latency ID generation (≤ 5ms P99)
  • Allow ID generation without central coordination to avoid bottlenecks
  • Support ID generation across multiple data centers with eventual consistency
📊
Non-Functional Requirements
  • System must handle 2 billion daily active users generating ~40 IDs per user per day
  • Achieve 99.99% availability for ID generation service
  • Ensure ID uniqueness with zero collisions under all failure scenarios
  • Support 100ms P99 end-to-end latency for ID generation requests
  • Scale horizontally to handle 10x traffic growth without redesign
❓
Clarifying Questions to Ask
  • What is the expected QPS for ID generation at peak and average?
  • Are IDs required to be strictly monotonically increasing or just roughly time sortable?
  • Is there a requirement for IDs to be human-readable or fixed length?
  • Can the system tolerate eventual consistency or must IDs be immediately visible globally?
  • Are there constraints on ID size or format (e.g., 64-bit integer vs UUID)?
  • Should the system support offline ID generation or only online?
Out of Scope
✗ Designing the entire user messaging or event system that consumes IDs
✗ Handling ID usage semantics beyond uniqueness (e.g., authorization)
✗ Long-term archival or analytics on generated IDs
✗ Security aspects like ID encryption or obfuscation
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 unique IDs per day on average
  • Average ID size is 12 bytes (e.g., 96-bit ID)
  • Retention period for IDs is 30 days for audit/logging
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 IDs/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M IDs/sec
read qpsAssuming 5× read amplification: 925,926 × 5 ≈ 4.63M reads/sec
💾
Storage Estimate
daily storage2B × 40 × 12 bytes = 960 GB/day
retention storage960 GB × 30 days = 28.8 TB
with replication28.8 TB × 3 replicas = 86.4 TB total
🖥️
Server Estimate
id generation nodesAssuming each node handles 100K IDs/sec, need ~28 nodes for peak
storage nodesAssuming Cassandra nodes with 2 TB usable storage each, need ~44 nodes for 86.4 TB
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          | Client Service |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | ID Generation  |
          |   Service      |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Coordination   |
          |   Service      |
          +-------+--------+
                  |
                  v
          +-------+--------+
          |  Storage Layer |
          | (Cassandra DB) |
          +----------------+
🧩
Components
ID Generation Service
Generates unique IDs using a time + node + sequence scheme
Why thisSnowflake algorithm style approach enables decentralized ID generation with time-sortable 64-bit IDs and sub-millisecond latency
Why notCentralized UUID generators like UUIDv4 cause coordination bottlenecks and lack time ordering
Coordination Service
Manages node ID assignments and clock synchronization to avoid collisions
Why thisApache ZooKeeper provides reliable distributed coordination with ephemeral nodes and leader election
Why notEtcd or Consul add complexity and higher latency; ZooKeeper is battle-tested for coordination at scale
Storage Layer (Cassandra)
Stores generated IDs and metadata for audit and deduplication
Why thisCassandra offers linear write scalability, tunable consistency, and multi-datacenter replication
Why notRelational DBs like PostgreSQL require manual sharding and do not scale linearly at 2.78M writes/sec
Client Service
Requests unique IDs from ID Generation Service for downstream processing
Why thisStateless microservice layer enables horizontal scaling and fault isolation
Why notEmbedding ID generation logic in clients risks inconsistent ID formats and collisions
Monitoring & Alerting
Tracks ID generation latency, collision rates, and node health
Why thisPrometheus + Grafana provide real-time metrics and alerting for operational visibility
Why notBasic logging lacks real-time alerting and scalability for 2.78M writes/sec
🔄
Data Flow
1
Client Service → ID Generation Service
Request unique ID
Client sends ID generation request with minimal payload
2
ID Generation Service → Coordination Service
Fetch node ID and check clock
Ensures node has unique ID and synchronized clock to avoid collisions
3
ID Generation Service → Local Sequence Generator
Generate sequence number for current millisecond
Sequence resets every millisecond to maintain uniqueness
4
ID Generation Service → Client Service
Return generated unique ID
ID is time sortable and collision-free
5
ID Generation Service → Storage Layer
Persist generated ID metadata asynchronously
Supports audit and deduplication without blocking ID generation
6
Monitoring & Alerting → Operations Team
Send alerts on anomalies
Detects clock drift, node failures, or ID collisions

Practice

(1/5)
1. In a CQRS system, a write request updates the primary database at Step 3. At Step 5, the read replica receives an update event. What is the state of the read replica at Step 6 immediately after receiving the event but before applying it?
easy
A. The read replica has already applied the update and serves the new data
B. The read replica rejects all reads until the update event is fully processed
C. The read replica switches to a read-only mode and queues incoming reads
D. The read replica still serves stale data until the update event is applied

Solution

  1. Step 1: Trace event arrival at read replica

    Upon receiving the update event, the read replica has not yet applied it, so data is stale.

  2. Step 2: Understand read replica behavior

    Read replicas serve stale data until the event is processed; they do not reject or queue reads.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Read replicas serve stale data until update applied [check]
Hint: Read replicas lag briefly, serve stale data until updated [check]
Common Mistakes:
2. In a system using Long Polling for server-to-client updates, at step 3 the client receives a response and immediately sends a new request. What is the client's state at step 4 before the server responds?
easy
A. The client is disconnected and will retry after a timeout due to connection closure.
B. The client has an open HTTP request waiting for the server response, and a new request is queued but not sent.
C. The client is waiting for the server response on the previous request, so no new request is sent yet.
D. The client has closed the previous connection and sent a new HTTP request, waiting for the next server response.

Solution

  1. Step 1: Trace Long Polling request lifecycle

    In Long Polling, the client sends a request and waits for the server to respond. Upon receiving the response, the client immediately sends a new request.

  2. Step 2: Determine client state at step 4

    At step 4, the previous connection is closed, and the client has an open new HTTP request waiting for the server's next response.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Long Polling client sends new request immediately after response [check]
Hint: Long Polling: response -> new request sent immediately [check]
Common Mistakes:
3. At 10x transaction volume, which component of a relational database system is most likely to become the bottleneck first, and why?
hard
A. The storage engine, because disk I/O bandwidth saturates quickly
B. The query optimizer, because it cannot generate execution plans fast enough
C. The lock manager, due to increased contention causing transaction delays
D. The network layer, as increased client connections overwhelm bandwidth

Solution

  1. Step 1: Identify bottleneck under high concurrency

    Lock manager handles concurrency control; at 10x load, lock contention increases exponentially.

  2. Step 2: Compare other components

    Query optimizer scales well with caching; storage and network scale with hardware upgrades; lock manager contention is harder to mitigate.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Lock manager contention -> first bottleneck at high transaction scale [check]
Hint: Lock manager contention grows fastest at scale [check]
Common Mistakes:
4. At 10x scale, which component in the API Gateway + BFF architecture is most likely to become the first bottleneck, and why?
hard
A. Microservices database, due to increased write contention
B. API Gateway, because it must maintain stateful WebSocket connections for all clients
C. BFF layer, as it performs CPU-intensive aggregation and transformation per request
D. Load balancer, due to limited connection handling capacity

Solution

  1. Step 1: Identify component workload at scale

    BFF performs CPU-intensive aggregation and transformation per request, which grows linearly with client requests.

  2. Step 2: Compare other components

    Microservices database, due to increased write contention is less likely first bottleneck as databases can be scaled horizontally or partitioned. API Gateway, because it must maintain stateful WebSocket connections for all clients is incorrect because API Gateway is typically stateless or uses connection offloading. Load balancer, due to limited connection handling capacity is wrong since load balancers scale well horizontally.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    BFF CPU-bound aggregation limits scale before other components [check]
Hint: BFF CPU-bound aggregation limits scale before others [check]
Common Mistakes:
5. At 10x scale, which component in a BM25-based search ranking system is most likely to become the bottleneck first and why?
hard
A. The query parser, because it must handle exponentially more complex queries
B. The inverted index storage, because random disk seeks increase linearly with index size
C. The document frequency updater, because maintaining accurate DF counts requires global coordination
D. The ranking component, because BM25 scoring requires expensive per-document computations that grow with candidate set size

Solution

  1. Step 1: Analyze scaling impact on components

    Query parser scales well with parallelism; DF updater can be sharded; ranking scales with candidate pruning.

  2. Step 2: Identify inverted index storage bottleneck

    Inverted index storage faces increased random disk seeks as index grows, causing latency spikes; disk I/O is harder to scale linearly than CPU or memory.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Disk I/O random seeks in inverted index storage bottleneck first [check]
Hint: Disk random seeks in inverted index grow fastest at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard