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
45 min · senior
senior

You are designing a unique ID generation service for a 50 million daily active user (DAU) social media startup. The system must generate globally unique, sortable IDs for posts, comments, and user actions. IDs must be generated with P99 latency under 200ms, support offline ID generation for mobile clients, and ensure IDs are cryptographically non-guessable to prevent enumeration attacks.

Constraints
  • P99 latency for ID generation must be under 200ms at peak load
  • IDs must be globally unique and roughly sortable by creation time
  • Offline clients must be able to generate IDs without server connectivity
  • IDs must be encrypted or obfuscated to prevent enumeration or guessing
  • System must handle 10 million ID generations per second at peak
  • ID collisions are unacceptable even under network partitions or clock skew
📋
Guided Steps
1/5
Step 1
Choosing the ID Generation Strategy
What approach will you use to generate unique IDs that are globally unique, sortable, and secure?
💡 Hint
Consider distributed ID generation algorithms that embed timestamp and node info, and how to prevent guessability.
Key Decision
Use Twitter Snowflake algorithm variant with 64-bit IDs embedding timestamp, node ID, and sequence number, combined with AES-128 encryption in CTR mode to obfuscate raw ID bits.
Interviewer Expectation
Mid: Names Snowflake for uniqueness and ordering. Senior: Explains embedding timestamp and node ID for sorting and uniqueness, and why AES-128 CTR mode encryption is needed to prevent enumeration.
⚠️Common Wrong Answer
Using UUIDv4 random IDs - leads to large ID size, no ordering, and no offline generation guarantees.
Step 2
Handling Offline ID Generation
How will offline clients generate IDs without server connectivity while ensuring no collisions when syncing back?
💡 Hint
Think about assigning unique node IDs or client IDs and sequence ranges to offline clients.
Key Decision
Assign each offline client a unique node ID via Redis and allocate sequence number ranges per client session; offline clients generate IDs locally using Snowflake logic with assigned node ID and sequence range.
Interviewer Expectation
Mid: Mentions client-side ID generation with assigned node ID. Senior: Details sequence range allocation per offline session to prevent collisions and how to handle clock skew on clients.
⚠️Common Wrong Answer
Allowing offline clients to generate IDs without coordination - causes collisions and breaks uniqueness guarantees.
Step 3
Ensuring Low Latency and High Throughput
How will you design the system to handle 10 million ID generations per second with P99 latency under 200ms?
💡 Hint
Consider horizontally scalable ID generation nodes and caching or batching techniques.
Key Decision
Deploy a fleet of stateless ID generation nodes behind a load balancer, each with a unique node ID allocated and health-checked via Redis; no central coordination during generation to keep latency low.
Interviewer Expectation
Mid: Describes multiple ID generators with unique node IDs. Senior: Explains Redis-based node ID allocation and health monitoring to prevent node ID conflicts and how stateless nodes enable horizontal scaling.
⚠️Common Wrong Answer
Centralized ID generator bottleneck - causes high latency and single point of failure.
Step 4
Preventing ID Enumeration and Guessing
How will you prevent attackers from guessing or enumerating IDs to scrape data or infer system state?
💡 Hint
Think about encrypting or obfuscating the ID bits and rate limiting API calls.
Key Decision
Encrypt raw Snowflake IDs using AES-128 in CTR mode with a rotating key before returning to clients; implement API rate limiting with Envoy proxy to prevent brute force enumeration.
Interviewer Expectation
Mid: Mentions encryption or obfuscation. Senior: Details AES-128 CTR mode encryption with key rotation and integration with Envoy for rate limiting and monitoring suspicious patterns.
⚠️Common Wrong Answer
Returning raw Snowflake IDs - exposes timestamp and node info, enabling enumeration and targeted attacks.
Step 5
API Design for Online and Offline Clients
What are the 3 core API endpoints your service exposes to support online and offline ID generation and syncing?
💡 Hint
Consider endpoints for requesting new IDs, syncing offline-generated IDs, and verifying uniqueness.
Key Decision
Expose POST /generate for online ID requests; POST /sync for clients to submit offline-generated IDs with node and sequence info; GET /status to check node ID assignments and health.
Interviewer Expectation
Mid: Names generate and sync endpoints. Senior: Explains request/response payloads, validation logic on /sync to detect collisions, and /status for client node ID management.
⚠️Common Wrong Answer
Single generate endpoint only - no support for offline syncing leads to collision risks.
🔌
API Design Challenge
Sketch 3 core API endpoints for the unique ID generation service that support online and offline clients and ensure uniqueness and security.
Hints
  • How does a client request a new ID when online?
  • How does an offline client generate an ID and later sync it?
  • How does the system verify and register offline-generated IDs to avoid collisions?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of Snowflake or equivalent algorithm embedding timestamp and node ID for uniqueness and ordering
  • Mechanism for offline clients to generate IDs with assigned node IDs and sequence ranges
  • Encryption of IDs to prevent enumeration and guessing
  • Horizontally scalable stateless ID generation nodes with unique node ID allocation
  • API design supporting online generation, offline sync, and node status
Good to Have - 30%
  • Use of Redis for node ID allocation and health monitoring
  • Rate limiting and monitoring via Envoy proxy
  • Clock skew handling strategies for offline clients
  • Key rotation for encryption keys
Bonus - 10%
  • Detailed failure mode analysis for clock skew and network partitions
  • Discussion of trade-offs between ID size, latency, and security
Anti-patterns to Avoid
Using UUIDv4 random IDs - leads to large IDs, no ordering, and offline collision risks
Centralized ID generator causing latency bottleneck and single point of failure
Allowing offline clients to generate IDs without coordination - causes collisions
Returning raw Snowflake IDs without encryption - enables enumeration attacks
Polling-based ID generation APIs causing excessive load and latency spikes, e.g., at 50M DAU, polling causes 50M reconnects/min, collapsing system under load
Ignoring clock skew leading to duplicate or out-of-order IDs
✅
Model Answer
▼ Reveal

The system uses a Snowflake variant algorithm to generate compact, sortable, globally unique 64-bit IDs embedding timestamp, node ID, and sequence number. To prevent enumeration attacks, raw IDs are encrypted using AES-128 in CTR mode with rotating keys. Offline clients are assigned unique node IDs and allocated sequence number ranges via Redis to generate IDs locally without collisions. The system deploys stateless ID generation nodes behind a load balancer, each with a unique node ID managed and health-checked through Redis to enable horizontal scaling and high throughput of 10 million IDs per second with P99 latency under 200ms. API endpoints include POST /generate for online ID requests, POST /sync for offline clients to submit generated IDs with validation to detect collisions, and GET /status for node ID assignment and health monitoring. Envoy proxy enforces API rate limiting to prevent brute force enumeration. Clock skew is mitigated by client-server time synchronization and sequence number fallback mechanisms.

Key Decisions
  • Use Twitter Snowflake algorithm variant for ID generation to ensure uniqueness and ordering
  • Assign unique node IDs and sequence ranges to offline clients via Redis to prevent collisions
  • Encrypt IDs with AES-128 CTR mode and rotate keys regularly to prevent enumeration
  • Deploy stateless horizontally scalable ID generation nodes with Redis-based node ID allocation and health checks
  • Implement API endpoints to support online generation, offline syncing with collision detection, and node status monitoring
  • Use Envoy proxy for rate limiting to prevent brute force enumeration attacks
  • Mitigate clock skew via client-server time sync and sequence number fallback
  • Twitter Snowflake algorithm variant for compact, sortable, unique 64-bit IDs
  • AES-128 CTR mode encryption of raw IDs to prevent enumeration attacks
  • Unique node ID assignment via Redis for offline client ID generation and collision avoidance
  • Stateless horizontally scalable ID generation nodes behind load balancer for 10M QPS
  • Sequence number range allocation per offline client session to prevent collisions
  • Envoy proxy for API rate limiting and monitoring to prevent brute force enumeration
  • API endpoints: POST /generate, POST /sync, GET /status to support online/offline workflows
  • Clock skew mitigation via client-server time sync and sequence number fallback

Practice

(1/5)
1. A social network platform needs to efficiently query complex friend-of-friend relationships with low latency. Which database technology best suits this requirement?
easy
A. A wide-column store like Cassandra optimized for large-scale writes
B. A document store like MongoDB with embedded documents
C. A graph database designed to traverse relationships quickly
D. A relational database with normalized tables and JOINs

Solution

  1. Step 1: Identify query pattern

    Friend-of-friend queries require efficient traversal of relationships, which relational JOINs or document stores handle poorly at scale.

  2. Step 2: Match technology to pattern

    Graph databases optimize relationship traversal with index-free adjacency, enabling low-latency queries on connected data.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Graph DBs excel at relationship traversal, unlike wide-column or document stores [check]
Hint: Graph DBs excel at traversing relationships fast [check]
Common Mistakes:
2. For a system that must deliver messages with strict ordering per conversation and tolerate node failures, which architecture is best?
medium
A. Use a single Redis instance with sorted sets for ordering
B. Use a distributed cache with eventual consistency and no ordering guarantees
C. Use Kafka with partition key as conversation ID and consumer groups for processing
D. Use a relational DB with transaction logs for ordering guarantees

Solution

  1. Step 1: Analyze ordering and fault tolerance requirements

    Redis single instance (A) is a single point of failure and limited in scale. Relational DB (C) has high latency and limited throughput for 1M+ messages. Distributed cache with eventual consistency (D) cannot guarantee ordering.

  2. Step 2: Evaluate Kafka's partitioning and consumer groups

    Kafka partitions by conversation ID ensure ordering per conversation. Consumer groups allow scalable processing with fault tolerance. Kafka replicates partitions for node failure tolerance.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Kafka partitions + consumer groups -> ordering + fault tolerance [check]
Hint: Kafka partitions by key ensure ordering and fault tolerance [OK]
Common Mistakes:
3. If the event queue that propagates write updates to read replicas fails, what is the immediate failure mode observed in the system?
medium
A. Writes to the primary database fail due to backpressure from the queue
B. Read replicas stop receiving updates and serve stale data indefinitely until manual intervention
C. The system automatically switches to synchronous replication to maintain consistency
D. Clients receive errors on read requests due to read replica unavailability

Solution

  1. Step 1: Identify role of event queue

    The event queue asynchronously propagates updates to read replicas.

  2. Step 2: Trace failure impact

    If the queue fails, read replicas stop receiving updates and serve stale data indefinitely.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Queue failure causes stale reads, no automatic failover [check]
Hint: Event queue failure -> stale reads until fixed manually [check]
Common Mistakes:
4. At 10x scale, which component of a distributed Count-Min Sketch system is most likely to fail first and why?
hard
A. The network bandwidth saturates due to large sketch state synchronization
B. The sketch arrays in memory overflow due to fixed size limits
C. The hash functions become slower, increasing latency linearly
D. The centralized coordinator bottlenecks due to serializing all update requests

Solution

  1. Step 1: Identify bottleneck in distributed updates

    Centralized coordinator serializes updates to maintain consistency, limiting throughput.

  2. Step 2: Analyze other components

    Network bandwidth and hash function speed scale better; sketch arrays have fixed size but don't overflow.

  3. Step 3: Understand scale impact

    At 10x scale, coordinator becomes overwhelmed, causing update latency and failures.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Central coordinator serialization bottlenecks updates at scale [check]
Hint: Central coordinator serializes updates, bottlenecking at scale [check]
Common Mistakes:
5. At 10x scale, which component in the hotel booking system is most likely to fail first and why?
hard
A. The distributed lock service because it becomes a bottleneck coordinating locks across many nodes
B. The API Gateway because it cannot route the increased number of client requests efficiently
C. The Inventory Service because it maintains stateful caches that cannot be sharded easily
D. The relational database because it cannot handle the increased write throughput for reservations

Solution

  1. Step 1: Identify bottlenecks at 10x scale

    Distributed lock service coordinates exclusive access and must handle many concurrent lock requests.

  2. Step 2: Evaluate component scalability

    Relational DB (The relational database because it cannot handle the increased write throughput for reservations) can be scaled with sharding and read replicas. Inventory Service caches (The Inventory Service because it maintains stateful caches that cannot be sharded easily) can be sharded or invalidated. API Gateway (The API Gateway because it cannot route the increased number of client requests efficiently) can be horizontally scaled with load balancers. The lock service (The distributed lock service because it becomes a bottleneck coordinating locks across many nodes) is a centralized coordination point and becomes a bottleneck due to synchronization overhead and network latency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Distributed lock service bottlenecks first due to coordination overhead [check]
Hint: Distributed locks bottleneck first at scale due to coordination overhead [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